Blockchain od začátečníka 4 - tak na tom se asi shodneme, ne? (distribuovaný konsenzus)

Základní vlastností blockchain je, že jde o datovou strukturu, která prokazatelně a neměnitelně udržuje historii všech zápisů, je to log, kronika, ve které se nesmí přepisovat ani gumovat a která jen roste. Být to jeden uzel, tak to zkrátka přidáváte do nějakého souboru a je to, nicméně my chceme systém distribuovaný. A co je ještě horší, tak masivně distribuovaný s neustálým umíráním a rozením jednotlivých členů a většinou i za přítomnosti takových, co nejednají čestně. Všechny nody se musí shodnout na jedné historii, na jedné verzi pravdy a k tomu potřebujeme nějaký mechanismus pro distribuovaný konsenzus. Dnes si popíšeme jeden velmi populární v běžných distribuovaných systémech (konkrétně půjde o Ralf, který je například v Hashicorp produktech Consul a Vault nebo je pod kapotou MongoDB), ale hned jak ho pochopíme, tak si na něm ukážeme jeho zásadní limity, které ho v extrémně nepřátelském prostředí činí nevhodným. Ano - bude potřeba se podívat, co trápí Byzantského generála.

Konsenzus na příkladu Raft algoritmu

Jak se mohou nody shodnout na jedné verzi pravdy? Raft na to jde vlastně docela jednoduše. Pokud by byl jeden node v roli lídra a přes něj se zapisovalo a současně by našel mechanismus jak distribuovat data (například bloky našeho blockchainu), tak by to mohlo fungovat. Tedy za předpokladu, že najdeme také způsob, jak lídra zvolit, když se stávajícímu králi udělá špatně.

Volba lídra

Všechny nody začnou ve stavu follower, kdy čekají na zprávy od lídra. Nicméně na začátku žádného nemáme, takže obvykle po 150-300ms ztratí nějaký node trpělivost a rozjede nové volby. Právě náhodně zvolený rozptyl timeoutu způsobí, že se nepokusí kandidovat všichni najednou. Nicméně připusťme, že třeba 2 z 5 nodů do toho půjdou. Zvýší číslo volebního období (term) na dvojku, zahlasují sami pro sebe a obrátí se na ostatní voliče. Ti fungují jednoduše - hlasovat v každém volebním období mohou jen jednou, takže pokud jsou také kandidáty, tak už to mají za sebou (hlasovali už pro sebe) a pokud ne, tak zvednou ruku pro prvního kandidáta co přijde (pro dané volební období - číslo term). Kandidát, který dostane většinu hlasů, se stane lídrem, ostatní budou follower. Pokud by to vyšlo nerozhodně, vyhlásí se předčasné volby - objeví se kandidát s novým volebním obdobím, tedy vyšším číslem term (v mém případě trojka). Lídr je pak ten, kdo komunikuje s veřejností.

Replikace logu

Když se má přidat nový záznam, například blok, udělá to lídr a tento blok bude mít ve stavu appended. Stejný příkaz pošle ostatním uzlům, ti si to také uloží do stavu appended a pokud lídr dostane potvrzení od většiny nodů, považuje celou záležitost za jistou. Blok si dá do stavu commited, tedy má ho fyzicky uložený a stejnou instrukci pošle nodům a ti udělají totéž. Pokud by byl nějaký node chvilku mimo (třeba se restartoval), lídr mu to zkouší posílat znova, takže ho follower doběhne. Lídr při svém požadavku na followery referencuje předchozí blok podle trvale rostoucího čísla (index zápisu) a sděluje číslo term, takže pokud by data na followerovi vypadala jinak (předchozí blok tam třeba nemá nebo nesouhlasí term), odmítne to. Každé vrácené OK od followera tak současně potvrzuje, že jeho log souhlasí s logem lídra. Pokud něco nesouhlasí, lídr a follower najdou místo, kde jim to ještě sedí a od tohoto bodu follower záznamy smaže a nahradí je těmi od lídra.

A co kdyby lídr umřel dřív, než všechny nody mají všechny bloky? Tady se to vyřeší tím, že v rámci voleb se odmítají kandidáti, kteří nemají poslední bloky, čímž vyhraje někdo jiný a ten je followerům dosype. Raft není nějak zvlášť sofistikovaný a je to schválně - má být alternativou k Paxos (použitém například v Zookeeper), který je podstatně složitější na pochopení a implementaci a dělají se v něm časté chyby.

To je celé, to bylo jednoduché, že? Můžeme to tedy uzavřít? Bohužel ne - v MongoDB se nody možná mezi sebou poznají a instaluje je administrátor, takže asi ví co dělá, ale ve světě blockchain není bezmezná víra v jednotlivé nody chytrá. Mohou být cinknutí a to může mít důsledky, o kterých vědí i Byzantští generálové v jednom myšlenkovém experimentu.

Problém Byzantských generálů

Máte třeba 9 generálů a ti se dohadují přes posly se zprávami zda zaútočí na hrad. Pokud se dohodnou pro útok a zaútočí společně, vyhrají. Pokud se dohodnou na ústupu, je to v pohodě. Pokud ale někdo zaútočí a někdo ne, bude to katastrofa - díky nedostatečné síle útočníci umřou a úspěchem posílení rytíři z hradu doběhnou i ty ustupující a taky je pobijí. Co potřebujeme? Distribuovaný konsenzus, to už jsme přece probrali. Jenže - někteří generálové mohou být zrádci a záměrně lžou nebo poslové zprávy zahazují, modifikují a tak podobně. Zrádce jednomu řekne útočíme, jinému ustupujeme. To je samozřejmě problém.

Raft není vůči tomuto tolerantní (není BFT - Byzantine Fault Tolerant). Cinknutý generál se snadno stane lídrem a pak třeba při replikaci logu záměrně řekne každému něco jiného a konzistence dat je pryč. Připojeným followerům sdělí, že jsou v nekonzistentním stavu a že je potřeba posledních pět záznamů odmazat a nahradit je tím, co lídr řekne (a ten může říct každému i něco jiného). Cinknutý follower třeba zase bude schválně komunikovat pomalu nebo jen na některé nody (někdo ho vidí, někdo ne), bude tvrdit, že data commitnul a přitom to neudělal nebo se bude neustále přepínat do kandidáta a vyhlašovat nové volby nebo, aby to nebylo tak nápadné, různými výpadky a zprávami bude vyvolávat časté bezvládí a opakované volby (v průběhu nichž systém nemůže řešit logy, tedy dělat to co hlavně má).

Raft tedy pro blockchain nebude dostatečný, pokud nezajistíme necinknutelnost nodů. O to se můžeme pokusit například autentizací nodů nebo tím, že software s kódem bude podepsaný s řetězcem důvěry až do hardwaru (na TPM čip například) a šifrováním celého procesu v paměti s confidential computing (např. SGX nebo TGX od Intelu, SEV-SNP od AMD nebo CCA od ARMu). I tak možná budeme chtít předcházet náhodným chybám, které nejsou záměrné a robustnější algoritmus jako je PBFT bude vhodnější. Často ale mohou mít omezení ve škálovatelnost nebo potřebě rozumné latence.

Zatímco PBFT lze najít u permissioned blockchainů (soukromé nebo konsircium), veřejné blockchainy používají jiné metody. Dvě hodně zajímavé jsou Proof of Work a Proof of Stake - a na ty se vrhnu příště.



Blockchain od začátečníka 7 - co za to mají (ekonomické pobídky ve veřejných sítích) Blockchain
Blockchain od začátečníka 6 - zaruč se svým majetkem (Proof of Stake) Blockchain
Blockchain od začátečníka 5 - máš to odmakané? (Proof of Work) Blockchain
Blockchain od začátečníka 3 - transakce ověřené rostoucím binárním stromem (merkle tree) Blockchain
Blockchain od začátečníka 2 - bloky řetězené za sebou Blockchain