Asynchroniczne Bizantyjskie Porozumienie z Optymalną Odpornością i Liniową Złożonością

Sytuacja początkowa:

• 7 węzłów otrzymało propozycję bloku A (głosują: 1)
• 3 węzły bizantyjskie próbują promować blok B (głosują: 0)
• Węzły bizantyjskie mogą: opóźniać wiadomości, wysyłać sprzeczne informacje, kłamać o swoich głosach

Działanie protokołu:

1. Runda 1: Węzły wymieniają swoje głosy przez A-Cast (reliable broadcast)
   • Poprawne węzły widzą większość dla wartości 1
   • Bizantyjskie węzły próbują wprowadzić chaos, ale A-Cast gwarantuje spójność
2. Runda 2: Protokół Vote wykrywa silną większość (strength = 2) dla wartości 1
   • Wszystkie poprawne węzły zgadzają się na blok A
   • Węzły wysyłają COMPLETE i kończą protokół

Wynik: Wszystkie 7 poprawnych węzłów akceptuje blok A, mimo że 3 węzły były bizantyjskie.

Jeśli poprawne procesy nie odtworzą tego samego sekretu, to protokół wykryje co najmniej \(t(n - 3t)\) błędnych par procesów.

Błędna para \(\{i, j\}\) oznacza, że co najmniej jeden z procesów \(i\) lub \(j\) jest bizantyjski.

Pole skończone: Wszystkie operacje wykonywane są w \(\mathbb{Z}_p\) dla dużej liczby pierwszej \(p\).

TYPE FieldElement
    // Elementy w Z_p dla dużej liczby pierwszej p
    // Wszystkie operacje arytmetyczne są mod p
    p : Prime  // np. 2^256 - 189

Symetryczny dwuwymiarowy wielomian stopnia \(t\):

CLASS SymmetricBivariatePolynomial
    degree : Integer = t
    
    coefficients : Matrix[t+1][t+1]
        // a_{ij} gdzie i+j ≤ t
        // WARUNEK: a_{ij} = a_{ji} (symetria)
    
    FUNCTION Evaluate(x, y) → FieldElement
        RETURN Σ_{i,j: i+j≤t} a_{ij} · x^i · y^j
    
    FUNCTION GetUnivariate(x_fixed) → UnivariatePolynomial
        // Zwraca f(y) = F(x_fixed, y)
        RETURN wielomian w y stopnia t

Jednowymiarowy wielomian (przekrój):

CLASS UnivariatePolynomial
    degree : Integer = t
    coefficients : Array[t+1]  // [c_0, c_1, ..., c_t]
    
    FUNCTION Evaluate(y) → FieldElement
        RETURN Σ_{i=0}^{t} c_i · y^i
    
    FUNCTION InterpolateFrom(points) → UnivariatePolynomial
        // Interpolacja Lagrange'a z t+1 punktów
        // Danych: {(x_1, y_1), ..., (x_{t+1}, y_{t+1})}
        RETURN unikalny wielomian stopnia ≤ t

FUNCTION IVSS_Share(secret s, round r)
│
├─ // Krok 1: Wybierz symetryczny wielomian dwuwymiarowy
│  SELECT random symmetric bivariate polynomial F(x, y)
│      WHERE degree(F) = t AND F(0, 0) = s
│
├─ // Krok 2: Wyślij przekroje do procesów
│  FOR k = 1 TO n DO
│      f_k(y) ← F(k, y)              // Jednowymiarowy wielomian
│      A-Cast f_k to process k    // Niezawodny broadcast
│
├─ // Krok 3: Czekaj na potwierdzenia równości
│  WAIT FOR candidate set M WHERE:
│      1. |M| ≥ n - t
│      2. ∀i,j ∈ M: received A-Cast "EQUAL:(i,j)"
│      3. ∀i,j,p,q ∈ M: received A-Cast "CHECKED_r: p, q, {i,j}" from p
│         // To sprawdza, że {i,j} nie jest błędną parą w historii
│
├─ // Krok 4: Ogłoś zbiór kandydatów
│  A-Cast "CANDIDATE_SET: M"
│
└─ COMPLETE sharing phase

// Stan lokalny
LOCAL STATE:
    received_poly : Polynomial ← null
    consistent_peers : Set[ProcessID] ← ∅

─────────────────────────────────────────────────────

UPON RECEIVE polynomial f_k FROM dealer
│
├─ received_poly ← f_k
│
└─ FOR j = 1 TO n DO
       point ← f_k(j)                // Ewaluuj wielomian w j
       SEND point to process j       // Bezpośrednia wiadomość

─────────────────────────────────────────────────────

UPON RECEIVE point p_j FROM process j
│
├─ IF received_poly(j) = p_j THEN     // Test spójności
│      // f_k(j) powinno równać się f_j(k) (symetria!)
│      A-Cast "EQUAL:(k, j)"
│
└─ ELSE
       // Niezgodność! Co najmniej jeden z {k, j} jest bizantyjski
       // Nie wysyłamy EQUAL

─────────────────────────────────────────────────────

UPON RECEIVE "CANDIDATE_SET: M" FROM dealer
│
├─ // Weryfikacja zbioru kandydatów
│  VERIFY:
│      1. |M| ≥ n - t
│      2. ∀i,j ∈ M: received "EQUAL:(i,j)" via A-Cast
│      3. ∀i,j,p,q ∈ M: received "CHECKED_r: p, q, {i,j}" from p
│      4. ∀i,j ∈ M: {i,j} ∉ FP_k
│         // Sprawdź lokalną listę błędnych par
│
└─ IF verification passes THEN
       OUTPUT "Sharing Complete"
       STORE (M, received_poly)  // Do użycia w rekonstrukcji

FUNCTION IVSS_Reconstruct(instance_id) → secret
│
├─ // FAZA 1: Broadcast wielomianów
│  IF I am in set M THEN
│      A-Cast my_polynomial f_k
│      // Wysyłam wielomian, który otrzymałem od dealera
│
├─ // FAZA 2: Zbierz i interpoluj
│  WAIT FOR polynomials from set IS WHERE:
│      • |IS| ≥ n - 2t
│      • IS ⊆ M
│      • All polynomials in IS are consistent:
│        ∀i,j ∈ IS: f_i(j) = f_j(i)  // Test symetrii!
│
├─ // Jeśli test symetrii zawiedzie dla pary {i,j}:
│  IF ∃ i,j ∈ candidates : f_i(j) ≠ f_j(i) THEN
│      ADD {i, j} to FP_k  // Wykryto błędną parę!
│      // Kontynuuj szukanie większego spójnego zbioru IS
│
├─ // Interpolacja dwuwymiarowego wielomianu
│  INTERPOLATE symmetric bivariate polynomial F
│      from {f_i | i ∈ IS}
│      // Używamy własności: F(i,y) = f_i(y) dla każdego i ∈ IS
│      // Ponieważ |IS| ≥ n-2t > t, możemy zrekonstruować F stopnia t
│
├─ reconstructed_secret ← F(0, 0)
│
├─ // FAZA 3: Zatwierdzenie w historii
│  A-Cast "READY_TO_COMPLETE"
│  ADD instance_id to CoreInvocations_k^r
│      // Ta instancja staje się częścią historii
│
└─ // FAZA 4: Finalizacja
   WAIT FOR (n - t) "READY_TO_COMPLETE" messages
   RETURN reconstructed_secret

FUNCTION ReconstructBivariate(slices : {f_1, f_2, ..., f_k}) → F(x,y)
│   // slices: zbiór k ≥ t+1 wielomianów, gdzie f_i(y) = F(i, y)
│
├─ // Krok 1: Weryfikacja spójności (test symetrii)
│  FOR EACH pair (i, j) in slices DO
│      ASSERT f_i(j) = f_j(i)          // Warunek symetrii
│      IF NOT satisfied THEN
│          DETECT_FAULTY_PAIR({i, j})
│          RETURN ERROR
│
├─ // Krok 2: Interpolacja Lagrange'a
│  // Dla każdej pary (i,j), znamy wartość F(i,j) = f_i(j)
│  points ← {(i, j, f_i(j)) | i,j ∈ indices of slices}
│
├─ // Krok 3: Zbuduj F(x,y) stopnia t
│  F(x, y) ← BivariateLagrangeInterpolation(points, degree=t)
│      // Interpolujemy z więcej niż (t+1)² punktów
│      // Symetria gwarantuje unikalność
│
└─ RETURN F

// Stan globalny
GLOBAL STATE:
    FP_k : Set[{ProcessID, ProcessID}] ← ∅
        // Błędne pary: nieuporządkowane pary {i,j} gdzie ≥1 jest bizantyjski
    
    CoreInvocations_k^r : List[InstanceID] ← []
        // Historia pomyślnie zakończonych instancji IVSS w rundzie r

─────────────────────────────────────────────────────

FUNCTION InitCertification()
    FP_k ← ∅
    CoreInvocations_k^0 ← []
    START background monitoring

─────────────────────────────────────────────────────

AT START OF ROUND r (r > 1)
│
└─ A-Cast CoreInvocations_k^{r-1}
       // Informuj wszystkich o swoich akcjach z poprzedniej rundy

─────────────────────────────────────────────────────

UPON RECEIVE CoreInvocations_l^r FROM process l
│
├─ // Sprawdź wszystkie instancje z historii procesu l
│  FOR EACH instance I in CoreInvocations_l^r DO
│      │
│      ├─ // Pobierz zbiór M z instancji I
│      │  LET M = candidate_set(I)
│      │
│      └─ // Sprawdź spójność wielomianów dla wszystkich par w M
│         FOR EACH i, j ∈ M DO
│             IF received f_i and f_j in IVSS-R of I THEN
│                 IF f_i(j) ≠ f_j(i) THEN
│                     // WYKRYTO NIEZGODNOŚĆ!
│                     ADD {i, j} to FP_k
│                     LOG "Faulty pair detected: {i, j} in instance " + I
│
└─ // Zapewnij wykonanie kroków protokołu dla historii l
   FOR EACH invocation I in CoreInvocations_l^r DO
       COMPLETE sharing protocol of I
       COMPLETE Step 1 of IVSS[r]-R of I
       // Różne procesy mogą zakończyć różne instancje

─────────────────────────────────────────────────────

FUNCTION VerifySet(M : Set[ProcessID], round r) → Boolean
│   // Sprawdź, czy zbiór M może być zaakceptowany w rundzie r
│
├─ // Warunek a: Otrzymano historię od wszystkich w M
│  FOR EACH l ∈ M DO
│      IF NOT received CoreInvocations_l^{r'} for all r' < r THEN
│          RETURN false
│
├─ // Warunek b: Otrzymano wielomiany od wszystkich w historii
│  FOR EACH l ∈ M DO
│      FOR EACH instance I in ⋃_{r'DO
│          LET M_I = candidate_set(I)
│          FOR EACH i ∈ M_I DO
│              IF NOT received f_i in IVSS-R of I THEN
│                  RETURN false
│
├─ // Warunek c: Żadna para w M nie jest w FP_k
│  FOR EACH i, j ∈ M WHERE i ≠ j DO
│      IF {i, j} ∈ FP_k THEN
│          RETURN false  // Odrzuć: zawiera błędną parę
│
└─ RETURN true  // Wszystkie pary zweryfikowane

─────────────────────────────────────────────────────

WHEN VerifySet(M, r) returns true FOR processes k, l and pair {i,j}
│
└─ A-Cast "CHECKED_r: k, l, {i, j}"
       // Potwierdzam, że {i,j} nie jest błędną parą według historii l przed r

FUNCTION Vote(round r, input_bit x_k) → (value, confidence)
│
├─ // FAZA 1: Wymiana wartości wejściowych
│  A-Cast "INPUT: (k, x_k)"
│
│  WAIT FOR (n - t) INPUT messages
│      LET A_k = {senders of received INPUT messages}
│
│  my_vote_1 ← MAJORITY_BIT(A_k)      // 0 jeśli remis
│
│  A-Cast "VOTE1: (k, A_k, my_vote_1)"
│
├─ // FAZA 2: Pierwsze głosowanie
│  WAIT FOR (n - t) VOTE1 messages
│      LET B_k = {j | received VOTE1 from j AND A_j ⊆ A_k}
│
│  my_vote_2 ← MAJORITY_BIT(votes in B_k)
│
│  A-Cast "REVOTE: (k, B_k, my_vote_2)"
│
├─ // FAZA 3: Zbieranie ponownych głosów
│  WAIT FOR (n - t) REVOTE messages
│      LET C_k = {j | received REVOTE from j AND B_j ⊆ B_k}
│
└─ // LOGIKA DECYZYJNA
   IF all votes in B_k equal σ THEN
       RETURN (σ, 2)                  // Silna większość
   
   ELSE IF all revotes in C_k equal σ THEN
       RETURN (σ, 1)                  // Słaba większość
   
   ELSE
       RETURN (⊥, 0)                  // Brak większości

─────────────────────────────────────────────────────

FUNCTION MAJORITY_BIT(set S) → {0, 1}
│
├─ count_0 ← |{j ∈ S | bit[j] = 0}|
├─ count_1 ← |{j ∈ S | bit[j] = 1}|
│
└─ RETURN (count_1 > count_0) ? 1 : 0     // Domyślnie 0 przy remisie

FUNCTION GetCommonCoin(round r) → {0, 1}
│
├─ // FAZA 1: Dzielenie sekretów
│  // Każdy proces jest dealerem dla n instancji IVSS
│  FOR j = 1 TO n DO
│      IVSS[r, j]-S.Start(RANDOM_VALUE())
│      // Proces j dzieli losową wartość
│
├─ // FAZA 2: Zbierz zestawy załączników
│  WAIT UNTIL (t + 1) IVSS-S instances complete for me
│      LET T_k = {dealers of completed secrets}
│
│  A-Cast "ATTACH: T_k"
│
├─ // FAZA 3: Akceptacja
│  A_k ← ∅
│
│  FOR EACH "ATTACH: T_j" received FROM j DO
│      IF T_j ⊆ T_k THEN
│          ADD j to A_k
│
│  WAIT UNTIL |A_k| ≥ n - t
│
│  A-Cast "ACCEPT: A_k"
│
├─ // FAZA 4: Włącz rekonstrukcję
│  WAIT FOR (n - t) "ACCEPT: A_j" messages
│      LET S_k = {senders}
│
│  A-Cast "RECONSTRUCT_ENABLED: (H_k = A_k, S_k)"
│
├─ // FAZA 5: Rekonstruuj sekrety
│  FOR EACH j ∈ A_k DO
│      FOR EACH k ∈ T_j DO
│          RUN IVSS[r, k]-R
│
└─ // FAZA 6: Oblicz monetę
   WAIT UNTIL all reconstructions complete
   
   u ← ⌈0.87 × n⌉                    // Próg probabilistyczny
   
   FOR EACH k ∈ H_k DO
       value_k ← reconstructed_secret[k] mod u
   
   IF EXISTS k ∈ H_k : value_k = 0 THEN
       RETURN 0
   ELSE
       RETURN 1

FUNCTION ABA(input_bit x_k) → {0, 1}
│
├─ // INICJALIZACJA
│  round ← 0
│  estimate ← x_k
│  START CertificationProtocol() in background
│      // Protokół certyfikacji działa równolegle przez cały czas
│
└─ // GŁÓWNA PĘTLA
   LOOP forever
   │
   ├─ round ← round + 1
   │
   ├─ // FAZA 1: Głosowanie
   │  (vote_val, vote_strength) ← Vote(round, estimate)
   │
   ├─ // FAZA 2: Wspólna moneta
   │  coin_val ← ICC(round)
   │
   ├─ // FAZA 3: Logika decyzyjna (Canetti & Rabin)
   │  IF vote_strength = 2 THEN          // Silna większość
   │      estimate ← vote_val
   │      A-Cast "COMPLETE: estimate"
   │      // Uwaga: Kontynuuj do następnej rundy, aby pomóc innym
   │  
   │  ELSE IF vote_strength = 1 THEN     // Słaba większość
   │      estimate ← vote_val
   │  
   │  ELSE                                // Brak większości
   │      estimate ← coin_val
   │
   └─ // FAZA 4: Sprawdzenie terminacji
      UPON receiving (t + 1) "COMPLETE: v" messages
          OUTPUT v
          TERMINATE

// Nadawca
FUNCTION Broadcast(value)
    SEND MSG(value) to all processes

─────────────────────────────────────────────────────

// Odbiorcy (Proces k)
LOCAL STATE:
    received_echo : Set[ProcessID] ← ∅      // Kto wysłał ECHO
    received_ready : Set[ProcessID] ← ∅     // Kto wysłał READY
    sent_echo : Boolean ← false
    sent_ready : Boolean ← false
    delivered : Boolean ← false

─────────────────────────────────────────────────────

UPON RECEIVE MSG(val) FROM sender
│
└─ IF NOT sent_echo THEN
       SEND ECHO(val) to all processes
       sent_echo ← true

─────────────────────────────────────────────────────

UPON RECEIVE ECHO(val) FROM process j
│
├─ ADD j to received_echo[val]
│
└─ IF |received_echo[val]| ≥ n - t AND NOT sent_ready THEN
       // Próg: n - t (większość + t)
       SEND READY(val) to all processes
       sent_ready ← true

─────────────────────────────────────────────────────

UPON RECEIVE READY(val) FROM process j
│
├─ ADD j to received_ready[val]
│
├─ IF |received_ready[val]| ≥ t + 1 AND NOT sent_ready THEN
│      // Amplifikacja: t + 1
│      SEND READY(val) to all processes
│      sent_ready ← true
│
└─ IF |received_ready[val]| ≥ 2t + 1 AND NOT delivered THEN
       // Dostarczenie: 2t + 1
       delivered ← true
       TRIGGER A-Cast-Complete(val)

Problem kliki (NP-zupełny):

• Dany: Graf \(G = (V, E)\) z dowolnymi krawędziami
• Znaleźć: Największy zbiór wierzchołków gdzie WSZYSTKIE pary są połączone krawędzią
• Złożoność: Wykładnicza \(O(2^n)\) - trzeba sprawdzić wszystkie podzbiory

Nasz protokół (wielomianowy):

• Nie mamy grafu z góry! Graf jest konstruowany dynamicznie przez procesy
• Nie szukamy - procesy budują zbiór \(M\) inkrementalnie
• Dealer wybiera dowolny zbiór \(M\) spełniający warunki (nie maksymalny!)
• Złożoność: Wielomianowa \(O(n^2)\) - sprawdzenie wszystkich par

Konfiguracja: n=20, t=6, bizantyjskie: {3, 7, 11, 15, 17, 19}

Dealer wysyła wielomiany, procesy wymieniają punkty...

// Dealer (przypuśćmy proces 1, poprawny) otrzymuje wiadomości:

received_equal = {
    (1,2), (1,4), (1,5), (1,6), (1,8), ..., // Para (1, poprawny proces)
    (2,4), (2,5), (2,6), (2,8), ...,        // Para (poprawny, poprawny)
    ...
    // BRAK: (3,x) dla wielu x - proces 3 jest bizantyjski
    // BRAK: (7,x) dla wielu x - proces 7 jest bizantyjski
}

// Algorytm dealera (WIELOMIANOWY!):

candidates = {1, 2, 4, 5, 6, 8, 9, 10, 12, 13, 14, 16, 18, 20}  // Poprawne procesy
M = ∅

// Sprawdź każdy kandydat (O(n) iteracji):
FOR EACH i ∈ candidates DO
    is_valid = true
    
    // Sprawdź z już dodanymi do M (O(|M|) iteracji):
    FOR EACH j ∈ M DO
        IF NOT (received_equal.contains((i,j)) AND 
                  all_checked(i,j)) THEN
            is_valid = false
            BREAK
    
    IF is_valid THEN
        M.add(i)
        
        // Sprawdź próg
        IF |M| ≥ n - t THEN  // ≥ 14
            BREAK  // Sukces! Mamy M

// Wynik: M = {1,2,4,5,6,8,9,10,12,13,14,16,18,20}
// Rozmiar: 14 ≥ 14 = n-t ✓
// Złożoność: O(n²) - WIELOMIANOWA!

Analiza:

• Zewnętrzna pętla: maksymalnie \(n\) iteracji
• Wewnętrzna pętla: maksymalnie \(|M| \leq n\) iteracji
• Całkowita złożoność: \(O(n \times n) = O(n^2)\)
• Dla n=20: ~400 operacji (wykładniczna byłaby ~\(10^6\))
• Dla n=100: ~10,000 operacji (wykładniczna byłaby ~\(10^{30}\))

# Klonowanie repozytorium
git clone https://github.com/poneciak57/async-agreement-protocol.git
cd async-agreement-protocol/async-agreement-protocol-3

# Kompilacja
go build -o aba-sim main.go

# Uruchomienie symulacji (czyta ze standardowego wejścia)
echo "10 3 1 0 1 1 0 1 0" | ./aba-sim

# Format wejścia:
# Linia 1: n t (liczba procesów, liczba bizantyjskich)
# Linia 2: input_1 input_2 ... input_{n-t} (bity wejściowe dla uczciwych procesów)

# Przykład z plikiem wejściowym:
cat > input.txt << EOF
10 3
1 0 1 1 0 1 0
EOF
./aba-sim < input.txt

# Tryb cichy (tylko wynik końcowy):
./aba-sim -silent < input.txt

# Uruchom wszystkie testy automatyczne
./test.sh

# Skrypt wykonuje:
# 1. Kompiluje generator (gen.go) i program główny (main.go)
# 2. Dla każdego testu (1-100):
#    - Generuje losowe wejście (n, t, bity)
#    - Uruchamia symulację w trybie -silent
#    - Weryfikuje zgodność wyników wszystkich uczciwych procesów
# 3. Wyświetla podsumowanie (PASSED/FAILED)

# Przykładowe wyjście:
Starting tests...
Test 1 PASSED (n=10, t=3)
Test 2 PASSED (n=15, t=4)
...
Test 100 PASSED (n=20, t=6)
All 100 tests passed!

# Alternatywnie - testy jednostkowe Go:
go test -v ./tests/...

========== Symulacja ABA ==========
Parametry: n=10, t=3, bizantyjskie: [2, 5, 7]

--- Runda 1 ---
Vote: Silna większość dla 1 (confidence=2)
Procesy poprawne: wysyłają COMPLETE:1
Wykryte błędne pary: 12

--- Runda 2 ---
Procesy otrzymują (t+1)=4 wiadomości COMPLETE:1
Wszystkie poprawne procesy TERMINUJĄ z wartością: 1

========== Wyniki ==========
✓ Konsensus osiągnięty: 1
✓ Liczba rund: 2
✓ Wszystkie poprawne procesy zgodne: TAK
✓ Całkowita liczba wykrytych błędnych par: 12
✓ Czas symulacji: 1.23s

========== Symulacja ABA ==========
Parametry: n=10, t=3, wejścia: [1,0,1,0,1,0,1,1,0,1]

--- Runda 1 ---
Vote: Brak większości (confidence=0)
ICC: Generowanie wspólnej monety...
Wspólna moneta: 0
Estimate poprawnych procesów: 0
Wykryte błędne pary: 8

--- Runda 2 ---
Vote: Słaba większość dla 0 (confidence=1)
ICC: Generowanie wspólnej monety...
Wspólna moneta: 1
Estimate pozostaje: 0
Wykryte błędne pary: 15

--- Runda 3 ---
Vote: Silna większość dla 0 (confidence=2)
Procesy poprawne: wysyłają COMPLETE:0
Wykryte błędne pary: 18

--- Runda 4 ---
Procesy otrzymują (t+1)=4 wiadomości COMPLETE:0
Wszystkie poprawne procesy TERMINUJĄ z wartością: 0

========== Wyniki ==========
✓ Konsensus osiągnięty: 0
✓ Liczba rund: 4
✓ Wszystkie poprawne procesy zgodne: TAK
✓ Całkowita liczba wykrytych błędnych par: 18
✓ Czas symulacji: 2.87s