Problem generałów bizantyjskich bada, czy poprawne procesy uzgodnią jedną decyzję, gdy wadliwe działają dowolnie i wysyłają sprzeczne wiadomości różnym odbiorcom. Sformułowanie Lamporta, Shostaka i Pease’a z 1982 roku dowodzi dolnej granicy 3m+1 uczestników przy tolerancji m zdrajców w modelu wiadomości ustnych bez podpisów i opisuje rekurencyjne algorytmy dla wiadomości ustnych oraz podpisanych. Wyniki obowiązują przy dokładnych założeniach, nie są synonimem każdego konsensusu blockchain.
Lamport, Shostak i Pease opublikowali alegorię w ACM TOPLAS w lipcu 1982 r., aby objaśnić spójność interaktywną systemów replikowanych. Oddzieleni generałowie muszą wybrać jeden plan, choć zdrajca może przekazywać różne wersje różnym odbiorcom. Błąd bizantyjski jest silniejszy niż awaria stop: element może kłamać, zaprzeczać sobie, pomijać wiadomości lub wyglądać poprawnie tylko dla części systemu. [Lamport, Shostak & Pease — The Byzantine Generals Problem (1982)] [Pease, Shostak & Lamport — Reaching Agreement in the Presence of Faults (1980)]
Praca rozdziela IC1: wszyscy lojalni porucznicy wykonują ten sam rozkaz, oraz IC2: gdy dowódca jest lojalny, wykonują jego rozkaz. Współczesne odpowiedniki to zgodność lub safety, ważność oraz zakończenie lub liveness. Gwarancje wymagają jawnego modelu sieci, uwierzytelnienia i maksymalnej liczby błędów. [Lamport, Shostak & Pease — The Byzantine Generals Problem (1982)] [Pease, Shostak & Lamport — Reaching Agreement in the Presence of Faults (1980)]
W modelu ustnym znany jest bezpośredni nadawca, brak wiadomości można wykryć i każda para komunikuje się, ale zdrajca wysyła różne wartości. OM(m) rekursywnie przekazuje wartości i stosuje deterministyczną większość. Tolerowanie m procesów wymaga co najmniej 3m+1 uczestników, czyli ponad dwóch trzecich lojalnych. Przy trzech nie da się odróżnić kłamliwego dowódcy od kłamliwego kolegi. [Lamport, Shostak & Pease — The Byzantine Generals Problem (1982)]
Niepodrabialny podpis ujawnia sprzeczne komunikaty i uniemożliwia zmianę rozkazu podpisanego przez lojalnego uczestnika. Algorytm przekazuje nowe podpisane wartości i decyduje nad zebranym zbiorem. Przy idealnych założeniach dopuszcza dowolną liczbę zdrajców. Podpis dowodzi jednak pochodzenia, nie prawdy, terminowego dostarczenia ani uczciwości przejętego klucza; Dolev i Strong doprecyzowali granice rund. [Lamport, Shostak & Pease — The Byzantine Generals Problem (1982)] [Dolev & Strong — Authenticated Algorithms for Byzantine Agreement (1983)]
Gwarancja postępu zależy od czasu. Wynik Fischera–Lynch–Patersona z 1985 roku pokazuje, że całkowicie asynchroniczny deterministyczny system wiadomości z choć jednym procesem, który może się zatrzymać, dopuszcza wykonanie bez zakończenia konsensusu. FLP nie twierdzi, że rzeczywiste systemy nigdy się nie zgadzają. Żywotność wymaga dodatkowych założeń, jak późniejsze granice czasowe lub detektor awarii o określonych własnościach, albo protokołu losowego. Sam wybór lidera nie wystarcza. Podczas długiego podziału bezpieczny protokół może przestać kończyć operacje. [Fischer, Lynch & Paterson — Impossibility of Distributed Consensus with One Faulty Process (1985)] [NIST IR 8460 Initial Public Draft — State Machine Replication and Consensus with Byzantine Adversaries]
PBFT Miguela Castro i Barbary Liskov z 1999 roku przenosi zgodę bizantyjską na replikowaną maszynę stanów. Podstawowa konfiguracja n = 3f+1 toleruje f wadliwych replik. Przygotowanie obejmuje pre-prepare repliki głównej i 2f zgodnych wiadomości prepare; lokalne zatwierdzenie wymaga przygotowania oraz 2f+1 zgodnych wiadomości commit. Przecięcia kworów i reguły zmian widoku zapobiegają sprzecznym zatwierdzeniom. Uwierzytelnienie, numery sekwencji, punkty kontrolne i zmiany widoku obsługują fałszerstwo, powtórki, wzrost dziennika i wadliwego lidera. Znany skład i deterministyczna finalność różnią się od otwartej sieci Proof of Work. [Castro & Liskov — Practical Byzantine Fault Tolerance (1999)]
Bitcoin nie wykonuje OM ani PBFT i nie liczy nazwanych węzłów. Odporne na Sybile Proof of Work waży konkurujące historie skumulowaną pracą; każdy Full Node sam odrzuca bloki łamiące konsensus i śledzi ważny łańcuch z największą pracą. Tymczasowe rozgałęzienia są oczekiwane. Przy założeniach uczciwej większości pracy i komunikacji prawdopodobieństwo zastąpienia maleje wraz z głębokością, ale nie oznacza nieodwracalności matematycznej. Bitcoin Backbone formalizuje wspólny prefiks, wzrost i jakość przy jawnych założeniach pracy przeciwnika i sieci. [Nakamoto — Bitcoin: A Peer-to-Peer Electronic Cash System] [Garay, Kiayias & Leonardos — The Bitcoin Backbone Protocol]
Stwierdzenie, że Bitcoin rozwiązał problem, ukrywa zmianę modelu. Klasyczna zgoda zaczyna od stałej grupy znanych tożsamości i granicy f; Bitcoin dopuszcza zmienne pseudonimy oraz zewnętrzny rzadki zasób. Gwarancje nadal wymagają konkretnych założeń doręczenia. Proof of Work ogranicza Sybile, lecz nie zapobiega atakom eclipse, cenzurze, egoistycznemu wydobyciu, błędom oprogramowania ani reorganizacji przez większość mocy obliczeniowej. Model zagrożeń musi wskazać przeciwnika, czas, członków i finalność; samo BFT nie wystarcza. [Nakamoto — Bitcoin: A Peer-to-Peer Electronic Cash System] [Garay, Kiayias & Leonardos — The Bitcoin Backbone Protocol] [NIST IR 8460 Initial Public Draft — State Machine Replication and Consensus with Byzantine Adversaries]
Pełniejszy obraz uzyskasz, czytając to hasło razem z Nakamoto consensus, Proof of Work, Reguły konsensusu, Podwójne wydanie, Bitcoin, Finality.