Problém byzantských generálů

Byzantská porucha je libovolná porucha, která ukazuje různé symptomy různým pozorovatelům.^[3] Byzantské selhání je narušení služeb systému kvůli byzantské poruše v systémech, které vyžadují konsenzus mezi distribuovanými uzly.^[4]

Odolnost proti byzantským poruchám lze dosáhnout, pokud mezi loajálními generály (tj. těmi, kteří netrpí poruchou) panuje většinová shoda o strategii. Chybějícím zprávám může být dána implicitní hodnota hlasu. Chybějícím zprávám může být například dána “nulová“ hodnota. Dále, Pokud je shoda, že nulové hlasy jsou ve většině, předpřiřazená implicitní strategie může být použita (například ústup).^[5]

Typickým mapováním tohoto příběhu na počítačové systémy je, že počítače jsou generálové a jejich komunikační spoje jsou poslové. Ačkoli problém je formulována jako analogie rozhodování a problému datové bezpečnosti, v elektronice nemůže být vyřešen pouze kryptografickými digitálními podpisy, protože závady jako je nesprávné napětí se mohou šířit procesem šifrování. Určitá komponenta se tedy může jevit jako fungující další komponentě a jako vadná jiné komponentě, což brání dosažení shody v otázce, zda je první komponenta vadná nebo ne.^[3]

Formální definice:

Je dán systém n komponent, z nichž t je vadných (odpovídajících zrádným, nepoctivým generálům), a mezi všemi komponentami vedou pouze dvoubodové komunikační kanály.^[6]

Kdykoli se komponenta A pokusí vyslat hodnotu x, ostatní komponenty mohou vzájemně diskutovat a ověřovat konzistenci vysílání komponenty A, a nakonec se shodnout na společné hodnotě y.

Řekneme, že systém odolává byzantskému selhání, pokud komponenta A může vysílat hodnotu x, tak že:

1. Pokud A je poctivá, pak se všechny poctivé komponenty dohodnou na hodnotě x.
2. V každém případě se všechny poctivé komponenty shodnou na stejné hodnotě y.

Problém byl studován jak pro synchronní tak pro asynchronní komunikaci.

Předpokládá se, že výše uvedený komunikační graf je úplným grafem (tj. každá komponenta může komunikovat s každou jinou), ale komunikační graf nemusí být úplný.

Úloha může být také rozvolněna na „realističtější“ problém, kde se nepoctivé komponenty spolu nedomlouvají, aby svedly ostatní k chybě. Právě pro tento případ byly navrženy praktické algoritmy.

Problém dosažení byzantského konsensu formuloval a formalizoval Robert Shostak, který jej nazval problémem interaktivní konzistence. Tuto práci uskutečnil v roce 1978 v rámci projektu SIFT sponzorovaného NASA^[7] v laboratoři počítačových věd společnosti SRI International. SIFT (Software Implemented Fault Tolerance) byl dítětem Johna Wensleyho, a byl založen na myšlence použití více univerzálních počítačů, které by spolu komunikovaly prostřednictvím párovaných zpráv, aby dosáhly shody, i když by některé z počítačů byly vadné.

Na začátku projektu nebylo jasné, kolik počítačů bude celkem potřeba, aby bylo zaručeno, že spiknutí n vadných počítačů nemůže „zmařit“ úsilí správně fungujících počítačů o dosažení shody. Shostak ukázal, že je jich potřeba nejméně 3n+1, a navrhl dvoukolový protokol 3n+1 pro zasílání zpráv, který by fungoval pro n=1. Jeho kolega Marshall Pease zobecnil algoritmus pro libovolné n > 0, a dokázal, že 3n+1 je jak nezbytné tak dostačující. Tyto výsledky, spolu s pozdějším důkazem dostatečnosti 3n při použití digitálních podpisů od Leslie Lamporta, byly publikovány v zásadním článku, Reaching Agreement in the Presence of Faults (Dosažení shody v přítomnosti selhání.)^[8] Autoři získali za tento článek v roce 2005 cenu Edsgera W. Dijkstry.

Pro snazší porozumění problému interaktivní konzistence vymyslel Lamport barvitou alegorii, v níž skupina armádních generálů připravuje plán útoku na město. Původní verze příběhu byla o velitelích albánské armády. Na návrh Jacka Goldberga byl název změněn, aby se někdo nemohl cítit uražen a nakonec se ustálil na „byzantských generálech“.^[9] Stejní autoři prezentovali tuto formulaci problému spolu s některými dalšími výsledky v roce 1982 ve článku „Problém byzantských generálů“ (anglicky The Byzantine Generals Problem).^[5]

Účelová funkce odolnosti proti byzantskému selhání je schopna bránit proti chybám komponent systému se symptomy nebo bez symptomů, které brání jiným komponentám systému dosáhnout vzájemné shody, kde taková shoda je potřebná pro správné fungování systému.

Zbývající správně fungující komponenty systému odolného proti byzantskému selhání budou schopny pokračovat v poskytování požadovaných služeb systému, předpokládá existenci dostačujícího počtu korektně fungujících komponent pro zachování služby.

Byzantská selhání jsou považována za nejobecnější a nejobtížnější třídu chyb mezi příčinami selhání. Zastavení při selhání (anglicky fail-stop) je naopak nejjednodušší třídou chyb. Předpokládá, že uzel, který selže, prostě přestane fungovat, což mohou ostatní uzly snadno detekovat. Naproti tomu byzantská selhání nemají žádná omezení, což znamená, že vadný uzel může generovat libovolná data, včetně dat, která vypadají jako od funkčního uzlu. Byzantská selhání tedy mohou mást systémy detekce selhání, kvůli čemuž je obtížné dosáhnout odolnosti proti selhání. Bez ohledu na analogii, byzantské selhání nemusí být bezpečnostním problémem, na kterém se podílí nepřátelské lidské rozhraní: může se jednat o čistě elektrické nebo softwarové selhání.

Termín porucha/závada (anglicky fault) a selhání (anglicky failure) se zde používají podle standardní definice,^[10] které vytvořila společná komise pro „Základní koncepty a terminologii“ založená technickým výborem IEEE Computer Society pro spolehlivou výpočetní techniku a odolnost proti poruchám a pracovní skupinou IFIP 10.4 pro spolehlivou výpočetní techniku a odolnost proti poruchám.^[11] Viz také dependability.

Odolnost proti byzantským selháním se zabývá pouze konzistencí vysílání, což je vlastnost, kdy jedna komponenta vysílá jednu hodnotu všem ostatním komponentám, všechny přijmou právě tuto hodnotu nebo v případě, že rozesílač není konzistentní, ostatní komponenty se dohodnou na společné hodnotě samy. Tento druh odolnosti proti selhání nezahrnuje korektnost samotné hodnoty; například nepřátelská komponenta, která úmyslně pošle nesprávnou hodnotu, ale pošle tuto hodnotu konzistentně všem komponentám, nebude ve schématu odolnosti proti byzantskému selhání zachycena.

Několik řešení popsali Lamport, Shostak, a Pease v roce 1982.^[5] Povšimli si, že problém generálů lze redukovat na řešení problému „Velitele a poručíků“ kde všichni loajální poručíci musí fungovat ve shodě, a že jejich akce musí odpovídat tomu, co velitel nařídil, pokud je velitel je loajální:

• Jedno řešení uvažuje scénáře, ve kterým mohou být zprávy podvržené, ale které budou byzantsky odolné proti chybám, dokud podíl neloajálních generálů je menší než jedna třetina jejich počtu. Nemožnost vypořádat se s jednou třetinou nebo větším množstvím zrádců jednoznačně omezuje dokazování, že problém jednoho velitele a dvou poručíků nemůže být vyřešen, pokud velitel je zrádný. Abychom to viděli, předpokládejme, že máme zrádného velitele A, a dva poručíky B a C:, když A rozkazuje poručíkovi B zaútočit a poručíkovi C ustoupit, a B a C si navzájem posílají zprávy, pak ani B ani C nemůže zjistit, kdo je zrádce, protože to nemusí nutně být A; druhý poručík mohl zprávu od A zfalšovat. Lze ukázat, že pokud počet generálů je n a z nich je t zrádců, pak řešení problému existuje, pouze tehdy, když n > 3t a komunikace je synchronní (s omezeným zpožděním).^[12]
• Druhé řešení vyžaduje nezfalšovatelné podpisy zpráv. Pro systémy kritické z hlediska bezpečnosti informací mohou digitální podpisy (v moderních počítačových systémech, jich lze v praxi dosáhnout použitím asymetrické kryptografie) poskytovat odolnost proti byzantskému selhání při existenci libovolného počtu zrádných generálů. Pro systémy kritické z hlediska bezpečnosti (kde „bezpečnost informací“ znamená odolnost proti inteligentním hrozbám, zatímco „bezpečnost“ je odolnost proti přirozeným nebezpečím činnosti nebo mise), jednoduché kódy pro detekci chyb, např. CRC, poskytují slabší, ale často postačující ochranu za mnohem nižší cenu. To platí pro byzantská i nebyzantská selhání. Někdy navíc bezpečnost informací oslabuje fyzickou bezpečnost a naopak. Metody kryptografického digitálního podpisu tedy nejsou dobrou volbou pro systémy vyžadující fyzickou bezpečnost, pokud neexistuje také konkrétní bezpečnostní hrozba.^[13] Zatímco kódy pro detekci chyb, např. CRCs, jsou lepší než kryptografické techniky, ani jedno neposkytuje dostatečnou ochranu pro aktivní elektroniky v systémech kritických z hlediska fyzické bezpečnosti. To je ilustrováno scénářem Schrödingerova CRC, kde zpráva chráněná CRC s jediným byzantským vadným bitem prezentuje různá data různým pozorovatelům a každý pozorovatel zaznamená (vidí) platné CRC.^[3][4]
• Také jsou prezentovány variace na první dvě řešení poskytující v některých situacích odolnost proti byzantským selháním, kde ne všichni generálové mohou vzájemně přímo komunikovat.

Kolem roku 1980 bylo navrženo několik architektur systému, které implementovaly odolnost proti byzantským selháním. Patří k nim: Draperovo FTMP,^[14] MMFCS společnosti Honeywell,^[15] a SIFT organizace SRI.^[7]

V roce 1999 Miguel Castro a Barbara Liskovová představili algoritmus „Practical Byzantine Fault Tolerance“ (PBFT),^[16] který poskytuje replikaci vysoce výkonných byzantských stavových strojů, zpracování tisíc požadavků za sekundu se submilisekundovým zvyšuje latence.

Po PBFT bylo navrženo několik BFT protokolů pro zlepšení jeho robustnosti a výkonnosti. Například Q/U,^[17] HQ,^[18] Zyzzyva,^[19] a ABsTRACTs,^[20] které jsou zaměřeny na otázky výkonnosti a ceny; naproti tomu jiné protokoly, jako Aardvark^[21] a RBFT,^[22] se zaměřovaly na problémy jeho robustnosti. Adapt^[23] se pokoušel využít existující BFT protokoly a adaptivním přepojováním mezi nimi zlepšit robustnost a výkonnost systému při změnách podmínek. Byly také navrženy BFT protokoly, které vkládají důvěryhodné komponenty pro omezení počtu kopií, například A2M-PBFT-EA^[24] a MinBFT.^[25]

Několik příkladů byzantských selhání, ke kterým došlo, je uvedeno ve dvou ekvivalentních odborných článcích v časopisech.^[3][4] Tyto a další příklady jsou popsány na WWW stránkách NASA DASHlink.^[26]

Byzantské poruchy byly pozorovány nepříliš často a v nepravidelných intervalech během testování trvanlivosti nově zkonstruované třídy ponorek Virginia, přinejmenším do roku 2005 (kdy byly problémy veřejně oznámeny).^[27]

Síť Bitcoin pracuje paralelně a vytváří blockchain s funkcí Proof-of-Work (důkaz vykonané práce), která umožňuje systému překonat byzantské chyby a dosáhnout koherentní globální pohledu na stav systému. Některé Proof-of-Stake blockchainy také používají BFT algoritmy.^[28]

Některé letecké systémy, např. systém kontroly letu (Aircraft Information Management System využívající síť ARINC 659 SAFEbus) Boeingu 777 nebo 787 jsou založeny na odolnosti proti byzantskému selhání; protože jde o systémy pracující v reálném čase, jejich odolnost proti byzantskému selhání musí mít velmi nízké latence. Například SAFEbus může dosáhnout odolnosti proti byzantskému selhání v řádu mikrosekund dodatečné latence.^[29][30][31] Projekt kosmické lodi Dragon se ve svém návrhu zabývá odolností proti byzantským poruchám.^[32]

Mechanismy tolerance proti byzantským poruchám využívají komponenty, které opakují přicházející zprávy (nebo pouze jejich podpisy) jiným příjemcům této přicházející zprávy. Všechny tyto mechanismy předpokládají, že funguje opakování bloků zpráv šíření byzantských symptomů. Pro systémy, které mají vysoký stupeň bezpečnosti nebo jejichž bezpečnost je kritická, musí být prověřeno, že tyto předpoklady skutečně na přijatelné úrovni chrání před selháním. Při dokazování pomocí testování je jednou z potíží vytváření dostatečně širokého rozsahu signálů s byzantskými symptomy.^[33] Takové testování pravděpodobně bude vyžadovat specializované injektory selhání.^[34][35]

V tomto článku byl použit překlad textu z článku Byzantine fault na anglické Wikipedii.

• DEIRMENTZOGLOU, Evangelos; PAPAKYRIAKOPOULOS, Georgios; PATSAKIS, Constantinos, 2019. A Survey on Long-Range Attacks for Proof of Stake Protocols. IEEE Access. Roč. 7, s. 28712–28725. DOI 10.1109/ACCESS.2019.2901858. S2CID 84185792. 

• Atomický commit
• Brooksův–Iyengarův algoritmus
• Paxos (informatika)
• Kvantová byzantská dohoda
• Problém dvou armád
• Bezkonfliktní replikovaný datový typ

• Obrázky, zvuky či videa k tématu Problém byzantských generálů na Wikimedia Commons
• odolnost Byzantine Fault Tolerance in the RKBExplorer