Co je problém byzantských generálů a jak jej řeší Bitcoin?

Matematický hlavolam v originále zvaný The Byzantine Generals Problem je 20stránková stať amerických informatiků poprvé publikovaná v roce 1982.

Jakožto ukázkový příklad teorie her si klade otázku, zda účastníci určité situace mohou dosáhnout shody – konsensu na řešení dané situace, když neví a nemohou si nijak ověřit, jestli ostatní mluví pravdu nebo lžou.

Matematický problém ztvárňuje pěkná alegorie

Složité technické záležitosti přenechme odborníkům a pojďme si problém ukázat v poněkud pohádkovější podobě.

Představme si několik generálů, jejichž cílem je dobýt hrad, avšak jejichž vojska jsou od sebe vzájemně vzdálena na několik kilometrů.

Pokud generálové na hrad zaútočí v jeden okamžik, řekněme za svítání, hrad padne. Pokud však některý z nich vyrazí dříve či později a útok nebude koordinován, generálové utrpí porážku a bitvu prohrají.

Generálové se tak musí domluvit na přesném čase útoku. Jelikož zde chybí centrální nadřízená autorita a všichni generálové jsou si rovni, jeden se rozhodne zaútočit za svítání a vyšle o tom ostatním zprávu.

Jeho posel však může být zajat, stejně tak mohou obránci hradu vyslat falešného posla se záměrně špatným časem. Navíc se proslýchá, že mezi generály je zrádce, který oznámí čas, kdy zaútočí, ačkoli tak nemá v plánu učinit…

Je tedy vůbec možné, aby generálové dosáhli shody předtím, než dojde k útoku?

Zdroj: Wikipedia.org

Bitcoin tohle řeší!

Uspokojivé řešení tohoto problému se nenašlo až do roku 2008, kdy Satoshi Nakamoto publikoval bitcoinový whitepaper. Generálům bez moderních technologií by sice neporadil, otázku jak dosáhnout konsensu bez centrální autority v současném světě ale vyřešil.

Na místo generálů nastupují těžaři, respektive jejich počítače, jejichž cílem není dobýt město, ale vést účetní knihu, u které je opět nutné, aby jejím zápisům mohli všichni důvěřovat. I v moderním pojetí problému se vyskytuje riziko, že komunikace nebude pravdivá a někdo se pokusí podvádět.

K vyřešení dosud nevyřešeného použil Satoshi metodu důkazu prací – Proof of Work (PoW). Více informací o těžbě a konsensuálních mechanismech najdete v našem dalším článku:

Práci ve světě blockchainu nahrazuje velmi náročný matematický výpočet, jehož výsledkem je tzv. hash. Aby těžaři hash nalezli, musí vynaložit nemalé množství energie a výpočetní kapacity.

Pokud jste s principem těžby Bitcoinu seznámeni, víte, že záznamy v účetní knize jsou zapisovány do bloků, kdy každý nový blok v sobě obsahuje otisk těch předchozích. Každý nový blok si pro náš případ můžeme představit jako nový útok na město, o kterém rozhoduje 1 z generálů/těžařů.

Ostatní těžaři (generálové) pak v případě, že k nim dorazí dvě verze blockchainu (plánů útoku), uznají za správný ten, který obsahuje nejvíce validovaných bloků, tedy je delší.

A to je odpověď na náš problém. Neboť nejdelší řetězec se také rovná největší obtížnosti, největší vykonané práci (obětování elektrické energie a výpočetního výkonu) a právě na něm se shodlo nejvíce těžařů. Právě u něj se předpokládá, že je nejpravdivější.

U Bitcoinu navíc nemusí dojít ke 100% shodě, počítá se tedy s tím, že někdo bude podvádět a pokusí se účetní knihu zfalšovat. Pro fungování stačí shoda většiny (51 %), o systému se říká, že je Byzantine Fault Tolerant (odolný vůči byzantské chybě).