Byzantine Generals Problem

Představte si oddíly rozmístěné kolem města. Musí společně zaútočit, nebo společně ustoupit; rozdělený postup by je mohl zničit. Velitel rozesílá rozkazy, jenže někdo může zradit a druhým sdělovat různé věci. Jak mají spolehliví účastníci postupovat, aby nakonec udělali totéž? Nejde o skutečnou bitvu z dějin. Je to myšlenkový příklad pro počítače, které si mají udržovat shodný záznam. Třeba několik serverů, tedy počítačů zajišťujících společnou službu, musí stejně rozhodnout, zda už byla určitá platba zpracována. Nestačí, že každý dostal nějakou odpověď: odpovědi musí zapadat do společného rozhodnutí. [1] [9]

Leslie Lamport, Robert Shostak a Marshall Pease tento problém představili ve známé podobě v červenci 1982, po své práci o dohodě při selháních z roku 1980. Zrádce v příběhu zastupuje součást systému, jejíž chování už nemůžeme předvídat. Počítač nemusí pouze přestat pracovat. Může poslat správnou odpověď jednomu sousedovi a chybnou druhému, některé zprávy vynechat nebo tvrdit, že viděl něco jiného. Příčinou může být útok i porucha programu. Pojem byzantská chyba popisuje to, co ostatní pozorují, nikoli úmysl zařízení. Obvyklá zkratka BFT (Byzantine Fault Tolerance) označuje schopnost systému takové chování za stanovených podmínek snášet. [1] [2]

Původní úloha má dvě podmínky. IC1 požaduje, aby všichni spolehliví podřízení přijali stejný rozkaz. IC2 dodává, že je-li spolehlivý i velitel, musí přijmout právě jeho rozkaz. Bez druhé podmínky by šlo zdánlivě vše vyřešit pravidlem „vždy ustupte“, které by však ignorovalo poctivého velitele. V počítačových systémech se rozlišuje bezpečnost, tedy nepřipuštění rozporných výsledků, a živost, tedy schopnost vůbec dospět k výsledku. Další pravidla určují, které výsledky jsou přípustné. Shodný záznam sám o sobě nedokazuje, že vstupní tvrzení odpovídalo skutečnému světu. [1] [9]

Označme velitele A a jeho podřízené B a C. C dostane od A pokyn k útoku, ale B mu tvrdí, že velitel nařídil ústup. Lže B, nebo velitel poslal každému jiný rozkaz? Bez dále ověřitelného podpisu C obě situace nemusí rozlišit. Stejná nejistota může nastat u B. Kdyby oba vždy poslechli přímo velitele, zrádný A je rozdělí; kdyby jeho rozkaz vždy ignorovali, poruší podmínku pro poctivého velitele. Pro tuto úlohu se třemi účastníky a jedním možným zrádcem proto žádný vždy úspěšný postup bez podpisů neexistuje. Jde o nedostatek rozlišitelných informací, ne o pomalé počítače. [1] [9]

V klasickém modelu bez podpisů je pro m možných zrádců potřeba alespoň n ≥ 3m+1 účastníků: proti jednomu tedy čtyři. Písmeno n označuje celkový počet účastníků, m nejvyšší počet zrádců, s nímž počítáme. Neznamená to jen přidat hlas a jednou spočítat většinu. Postup OM(m) nechává účastníky opakovaně předávat, co slyšeli, a vyhodnocovat zprávy podle stejných pravidel; základ OM(0) jednoduše přebírá velitelovu hodnotu nebo dohodnutou náhradní hodnotu. Model přitom předpokládá známé účastníky, přímá spojení, správné doručení odeslané zprávy, znalost bezprostředního odesílatele a možnost poznat, že zpráva chybí. „Bez podpisů“ tedy neznamená „bez jakéhokoli ověření původu“. Bez těchto předpokladů samotný počet čtyři nic nezaručuje. [1] [9]

S ověřitelným digitálním podpisem (Digital Signature) může B předat C důkaz, co velitel skutečně podepsal. Takový podpis vytváří program pomocí soukromého klíče, tajného číselného údaje. Ostatní jej ověří odpovídajícím veřejným klíčem, aniž by potřebovali znát ten soukromý. Podvodník nemůže beze stopy změnit rozkaz poctivého účastníka ani jeho podpis napodobit. Algoritmus podepsaných zpráv šíří podepsané hodnoty a používá společné pravidlo výběru. V tomto modelu mizí uvedený požadavek na poctivou většinu, ale zůstávají předpoklady nepadělatelných podpisů, doručování a načasování kol. Práce Doleva a Stronga z roku 1983 dále zkoumá potřebný počet kol. Ani platný podpis nezaručuje pravdivost obsahu či včasné doručení a neprokazuje, že soukromý klíč nebyl odcizen. Je to důkaz původu určité zprávy, nikoli potvrzení, že se odesílateli dá ve všem věřit. [1] [3]

Když server neodpovídá, ostatní nevědí, zda se zastavil, nebo má jen velmi pomalé spojení. Výsledek FLP, který v roce 1985 publikovali Michael Fischer, Nancy Lynch a Michael Paterson, tuto nejistotu přesně vymezuje. Procesem se tu myslí běžící program. Deterministický postup při stejném stavu a stejném vstupu provede stejný další krok; nevybírá ho náhodně. V plně asynchronním systému, kde není známa horní mez zpoždění, nemůže deterministický postup zaručit dokončení dohody ve všech přípustných průbězích, pokud může selhat i jediný proces zastavením. Platí to i při spolehlivém, ale neomezeně pomalém doručování. Neříká to, že dohoda nikdy nevznikne. Praktické systémy přidávají časové předpoklady, vhodný detektor selhání nebo náhodnost. Při rozdělení sítě může být bezpečnější počkat než potvrdit dva neslučitelné výsledky. [4] [13] [8]

Miguel Castro a Barbara Liskov v roce 1999 popsali Practical Byzantine Fault Tolerance, zkráceně PBFT, pro službu provozovanou v několika známých kopiích. Tyto kopie, označované jako repliky, běží na různých serverech a průběžně zpracovávají stejné požadavky. Nejde o odložené záložní soubory. V základní konfiguraci n = 3f+1 dovoluje f chybných kopií. Ze čtyř serverů může jeden selhávat byzantsky; dvě skupiny po třech se překrývají nejméně ve dvou serverech, z nichž alespoň jeden musí být spolehlivý. Takové skupině potřebných souhlasů se říká kvórum. Samotný průnik ale nestačí: rozhodují i pravidla jednotlivých fází a výměny vedoucího. Podrobněji, stav prepared vyžaduje požadavek, zprávu pre-prepare a 2f odpovídajících prepare od různých replik v jiné roli než vedoucí. Lokální potvrzení navíc vyžaduje 2f+1 zpráv commit, případně včetně vlastní. Ověřování původu, pořadová čísla a kontrolní body brání podvržení, opakování a nekonečnému růstu záznamu. Bezpečnost nespoléhá na časové meze, dokončování práce však potřebuje další podmínky pro zpoždění. [5] [10] [11] [12]

Bitcoin nemá předem uzavřený seznam serverů. Kdyby rozhodoval každý nově vytvořený účet jedním hlasem, útočník by si mohl vyrobit většinu: tomu se říká Sybil Attack. Proof of Work proto váže tvorbu bloků na výpočetní práci. Blok je dávka transakcí přidaná do společné historie. Full Node, tedy počítač s programem, který samostatně kontroluje pravidla, nejprve odmítne neplatné bloky a potom mezi platnými větvemi sleduje tu s největší nahromaděnou prací. Bitcoin nespouští OM ani PBFT; dočasné rozvětvení je součástí jeho fungování. Při odpovídající převaze poctivého výkonu a podmínkách komunikace další potvrzení snižují riziko přepsání historie, nevytvářejí však absolutní nevratnost. Výzkum Bitcoin Backbone zkoumá právě tyto podmínky: jak se historie shodují, jak řetězec roste a jaký podíl bloků mohou vytvořit poctiví účastníci. [6] [7]

U tvrzení „síť dosahuje konsenzu“ má smysl hledat konkrétní odpovědi: kdo se smí účastnit, co může útočník ovládat, jak dlouho mohou zprávy cestovat a za jakých podmínek se rozhodnutí může změnit? Ani Proof of Work neodstraňuje všechny potíže. Eclipse Attack izoluje uzel od poctivých protějšků, cenzura vynechává transakce a Selfish Mining pracuje se zadržováním vytěžených bloků. Zůstávají také chyby softwaru a možnost přepsat část historie při dostatečné převaze útočníka. Ani většinový výkon však nepřinutí správně fungující Full Node přijmout blok porušující jeho pravidla. Příběh generálů je užitečný právě tím, že nás učí ptát se na podmínky dohody, místo abychom věřili samotnému názvu technologie. [6] [7] [8]