Problém byzantských generálů zkoumá, zda se korektní procesy dokážou shodnout na jediném rozhodnutí, když vadné procesy mohou jednat libovolně a různým příjemcům posílat protichůdné zprávy. Formulace Lamporta, Shostaka a Pease z roku 1982 dokazuje pro neautentizované ústní zprávy dolní mez 3m+1 účastníků při toleranci m zrádců a popisuje rekurzivní algoritmy pro ústní i podepsané zprávy. Jde o výsledky platné za přesných předpokladů, ne o synonymum každého blockchainového konsensu.
Lamport, Shostak a Pease zveřejnili vojenskou alegorii v ACM TOPLAS v červenci 1982, aby vysvětlili interaktivní konzistenci replikovaného počítačového systému. Oddělení generálové musí zvolit jediný plán, přestože jeden či více zrádců může různým příjemcům tvrdit něco jiného. Byzantská porucha je proto silnější než pád procesu: vadná součást může lhát, rozesílat rozporné hodnoty, zprávy zamlčet nebo se jen části systému jevit jako korektní. [Lamport, Shostak & Pease — The Byzantine Generals Problem (1982)] [Pease, Shostak & Lamport — Reaching Agreement in the Presence of Faults (1980)]
Článek odděluje dva požadavky. IC1: všichni loajální poručíci vykonají stejný rozkaz. IC2: je-li velící generál loajální, každý loajální poručík vykoná rozkaz, který velitel poslal. Moderní konsensus příbuzné vlastnosti označuje jako shodu či bezpečnost, platnost a ukončení či živost. Smysl mají pouze spolu s uvedeným modelem sítě, autentizací a maximálním počtem poruch. [Lamport, Shostak & Pease — The Byzantine Generals Problem (1982)] [Pease, Shostak & Lamport — Reaching Agreement in the Presence of Faults (1980)]
V modelu ústních zpráv příjemce pozná odesílatele doručené zprávy, chybějící zprávu lze zjistit a každá dvojice procesů spolu může komunikovat; zrádce však může různým lidem poslat různé hodnoty. Algoritmus OM(m) rekurzivně přeposílá hodnoty přes ostatní poručíky a použije deterministickou většinu. Bez podpisů je k toleranci m byzantských procesů potřeba nejméně 3m+1 účastníků, tedy více než dvě třetiny loajálních. Tři procesy jednoho zrádce nezvládnou, protože loajální příjemce nerozliší lživého velitele od lživého kolegy. [Lamport, Shostak & Pease — The Byzantine Generals Problem (1982)]
Nezfalšovatelný podpis odhalí rozeslání rozporných hodnot a zrádce nemůže změnit podepsaný rozkaz loajálního účastníka. Lamportův algoritmus podepsaných zpráv přeposílá dosud neviděné podepsané hodnoty a nad shromážděnou množinou provede stejné deterministické rozhodnutí. Za ideálních předpokladů článku lze tolerovat libovolný počet zrádců. Podpis však dokládá původ, nikoli pravdivost obsahu, včasné doručení ani poctivost kompromitovaného klíče. Dolev a Strong později zpřesnili autentizovanou shodu i hranice počtu kol. [Lamport, Shostak & Pease — The Byzantine Generals Problem (1982)] [Dolev & Strong — Authenticated Algorithms for Byzantine Agreement (1983)]
Možnost zaručit postup závisí na časování. Výsledek Fischer–Lynch–Paterson z roku 1985 ukazuje, že v úplně asynchronním deterministickém systému se zprávami může už jediný proces, který smí havarovat, ponechat přípustný běh bez ukončení konsensu. FLP netvrdí, že se skutečné systémy nikdy neshodnou. Záruka živosti vyžaduje dodatečné předpoklady, například pozdější časové meze nebo detektor poruch s určenými vlastnostmi, případně změnu na randomizovaný protokol. Samotné jmenování lídra nestačí. Při dlouhém rozdělení sítě může bezpečný protokol přestat dokončovat operace. [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 Castra a Barbary Liskov z roku 1999 převádí byzantskou shodu na replikovaný stavový automat. V základní konfiguraci n = 3f+1 toleruje f byzantských replik. Připravenost zahrnuje pre-prepare od primární repliky a 2f odpovídajících zpráv prepare; lokální potvrzení vyžaduje připravenost a 2f+1 odpovídajících zpráv commit. Průniky kvór a pravidla změny pohledu brání rozporným potvrzením. Autentizace, pořadová čísla, kontrolní body a změny pohledu řeší padělání, opakování, růst záznamu a vadného lídra. Známá sada replik a deterministická finalita se liší od otevřené sítě Proof of Work. [Castro & Liskov — Practical Byzantine Fault Tolerance (1999)]
Bitcoin nepoužívá algoritmus OM ani PBFT a nepočítá pojmenované uzly. Proof of Work odolný vůči Sybil útokům váží soupeřící historie nahromaděnou prací; každý Full Node samostatně odmítá bloky porušující pravidla konsensu a sleduje platný řetězec s největší kumulovanou prací. Dočasná rozvětvení jsou očekávaná. Za předpokladů o poctivé převaze práce a komunikaci klesá pravděpodobnost přepsání s hloubkou potvrzení, nejde však o matematickou nevratnost. Model Bitcoin Backbone formalizuje společný prefix, růst a kvalitu řetězce při výslovně určeném podílu útočné práce a síťových podmínkách. [Nakamoto — Bitcoin: A Peer-to-Peer Electronic Cash System] [Garay, Kiayias & Leonardos — The Bitcoin Backbone Protocol]
Tvrzení, že Bitcoin vyřešil problém byzantských generálů, je zkratka zakrývající změnu modelu. Klasická shoda začíná pevnou skupinou se známými identitami a mezí f; Bitcoin připouští pseudonymní proměnlivé účastníky a vnější vzácný zdroj. Jeho záruky přesto potřebují konkrétní předpoklady o doručování zpráv. Proof of Work omezuje vliv Sybil identit, ale nezabraňuje eclipse útokům, cenzuře, selfish miningu, chybám softwaru ani reorganizaci při většinovém hashratu. Model hrozeb musí vymezit útočníka, časování, členství a finalitu; samotné označení BFT nestačí. [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]
Pro nejúplnější obraz čtěte toto heslo společně s Nakamotův konsensus, Proof of Work, Konsensuální pravidla, Dvojí útrata, Bitcoin, Pravděpodobnostní finalita vypořádání.