Problem vizantijskih generala:Kako da se dogovoriš kad neko laže

Najvažnije u nekoliko reči:

Problem vizantijskih generala (engl. Byzantine Generals Problem) je pitanje kako grupa da donese istu odluku kad ne zna ko u njoj laže. Zamisli kućni savet koji se preko poruka dogovara da li će se ulaz krečiti ove ili sledeće godine. Ako jedan komšija svakome napiše nešto drugo, deo zgrade kreči, a deo čeka.

U zgradi se to razreši na stepeništu. Računari koji zajedno čitaju isti radar ili vode zajedničku knjigu novca nemaju stepenište. Imaju samo poruke.

Opsada grada koja je u stvari priča o računarima

Leslie Lamport, Robert Shostak i Marshall Pease objavili su u julu 1982. rad „The Byzantine Generals Problem“ u časopisu ACM Transactions on Programming Languages and Systems (rad u PDF-u). Već u sažetku pišu da pouzdan računarski sistem mora da izdrži i deo koji se pokvari tako da različitim delovima sistema šalje različite podatke.

Da bi to objasnili, uzeli su priču. Nekoliko divizija vizantijske vojske ulogorilo se oko neprijateljskog grada. Svakom divizijom komanduje njen general, a generali razgovaraju samo preko glasnika. Posle izviđanja moraju da se slože oko plana, napad ili povlačenje. Neki od njih mogu da budu izdajnici koji namerno zbunjuju ostale.

Rad traži postupak koji ispunjava dva uslova. Svi pošteni generali moraju da izaberu isti plan. A kad naredbu izdaje pošten zapovednik, pošteni generali moraju da izvrše baš nju. Izdajnici smeju da rade šta hoće, a postupak mora da radi uprkos njima.

Generali su ovde računari. Pošten general je ispravan računar, izdajnik je pokvaren računar ili napadač, a glasnik je poruka preko mreže.

Zašto poruke same ne pomažu

Najmanji slučaj su tri generala, zapovednik i dva poručnika, i jedan izdajnik. Rad govori o usmenim porukama. To su poruke čiji sadržaj potpuno zavisi od pošiljaoca, pa izdajnik može da pošalje šta god hoće. Autori dodaju da računari jedni drugima obično šalju baš takve poruke.

U prvom slučaju zapovednik je pošten i obojici naređuje napad. Poručnik 2 je izdajnik i javlja poručniku 1 da je zapovednik rekao povlačenje. U drugom slučaju izdajnik je zapovednik. Poručniku 1 kaže napad, poručniku 2 povlačenje, a poručnik 2 to pošteno prenosi.

Poručnik 1 u oba slučaja ima iste dve poruke. Ne zna ko laže. Ako uvek posluša zapovednika, u drugom slučaju napada sam, jer poručnik 2 po istom pravilu sluša naredbu za povlačenje koju je dobio. Pošteni generali tada rade suprotne stvari. Rad zato zaključuje da tri generala sa jednim izdajnikom ne mogu da se slože nikakvim postupkom.

Autori upozoravaju i da je ovakvo objašnjenje samo skica. Strog dokaz upućuju na raniji rad iste trojke iz 1980. godine.

Izdajnika mora da bude manje od trećine

Iz slučaja sa tri generala rad izvodi opšte pravilo. Sa usmenim porukama dogovor je moguć samo ako je poštenih više od dve trećine. Ako izdajnika ima m, generala mora da bude najmanje 3m + 1. Isti rezultat stoji u radu iz 1980. godine „Reaching Agreement in the Presence of Faults“ (rad u PDF-u).

Na jednog izdajnika dolaze bar tri poštena generala. Od deset računara najviše tri smeju da lažu. To je 30%, ispod granice od jedne trećine, koja je oko 33%.

Kako četiri generala izlaze na kraj sa jednim izdajnikom, rad pokazuje postupkom koji je nazvao OM(1). Zapovednik pošalje naredbu, svaki poručnik prenese ostalima šta je dobio, a onda svako bira ono što ima većinu.

Ako laže poručnik 3, poručnik 2 ima dva puta napad i jednom povlačenje, pa napada, kako je zapovednik naredio. Ako laže zapovednik i svakome kaže nešto drugo, poručnici razmene šta su dobili i svako ima isti spisak od tri naredbe. Svi biraju isto. Za više izdajnika postupak ponavlja razmenu u više krugova, a broj poruka brzo raste.

Potpis zaustavlja laž, ali ne i pitanje ko sme da glasa

Generali lažu lako zato što usmenu poruku niko ne može da proveri. Rad zato uvodi potpisane poruke. Potpis poštenog generala ne može da se falsifikuje, svaka izmena potpisane poruke se primećuje, a potpis svako može da proveri. Isto rade digitalni potpisi u Bitcoinu.

Sa potpisima tri generala mogu da se slože, a postupak iz rada radi za bilo koliko izdajnika. Zapovednik izdajnik se sad sam otkrije. Kad poručnici razmene poruke, vide njegov potpis na dve različite naredbe, a to je mogao da uradi samo on.

Ali svi ovi postupci počinju od spiska. Jedna od pretpostavki rada je da primalac zna ko mu je poslao poruku. U delu o stvarnim računarima autori pišu da to u praksi znači stalne veze između računara, a ne mrežu kroz koju poruka prolazi preko tuđih uređaja. Potpis vredi tek kad se zna čiji je. Većina može da se broji tek kad se zna koliko ima glasača.

Na otvorenom internetu takvog spiska nema. Jedan čovek može da napravi hiljadu lažnih učesnika i preglasa sve ostale, o čemu piše tekst Šta je Sybil napad? Na tom mestu su zapinjali i raniji pokušaji digitalnog novca. Prva verzija b-moneyja tražila je kanal za poruke koji niko ne može da ometa.

Satoshi je pustio generale da glasaju radom

Skoro dve nedelje posle objave whitepapera jedan učesnik liste o kriptografiji napisao je Satoshiju da nije dovoljno da svi znaju isto. Treba i da svako zna da svi to znaju, a to je, kao kod vizantijskih generala, klasičan težak problem. Satoshi je 13. novembra 2008. odgovorio ovako:

„

„The proof-of-work chain is a solution to the Byzantine Generals' Problem.“ (Lanac dokaza o radu je rešenje problema vizantijskih generala, arhiva liste.)

Zatim je priču ispričao iznova. Svaki general ima računar i hoće da probije lozinku kraljeve bežične mreže. Uspeće samo ako većina napadne u isto vreme. Svejedno im je kada, samo da se slože. Vreme napada može da objavi svako, a važi ono koje se prvo čuje.

Problem je što mreža nije trenutna. Ako dvojica objave različita vremena skoro u isto vreme, deo generala prvo čuje jedno, a deo drugo. Zato svaki general na vremenu koje je prvo čuo počne da radi dokaz o radu, zadatak koji svi zajedno rešavaju u proseku za deset minuta. Ko ga reši, javi svima, a ostali nastavljaju na tom rešenju. Ko je radio na drugom vremenu, prelazi, jer je ovaj lanac sad duži.

Posle dva sata vreme napada pokriva lanac od 12 dokaza o radu. Iz težine tog lanca svaki general sam procenjuje koliko je računanja uloženo i vidi da je moralo da radi većina. „They had to all have seen it because the proof-of-work is proof that they worked on it.“ (Svi su morali da ga vide, jer je dokaz o radu dokaz da su na njemu radili.)

Ovde se glasa radom. Zato lažni učesnici ništa ne donose, jer rad ne može da se umnoži. Whitepaper to kaže pravilom „jedan procesor, jedan glas“, a odluku većine predstavlja lanac u koji je uloženo najviše rada (odeljak 4). U pravom Bitcoinu generali su rudari, a ono oko čega se slažu je redosled transakcija u lancu blokova.

Bitcoinov dogovor je sve sigurniji, ali nije konačan u trenutku

Kod Lamporta i saradnika odluka je konačna kad se završi poslednji krug poruka. Kod Bitcoina je svaki blok samo predlog koji posle može da zameni duži lanac. Kad dva rudara nađu blok skoro u isto vreme, mreža je kratko podeljena, dok jedna grana ne postane duža (odeljak 5). O takvoj podeli lanca piše tekst o forkovima.

Svaki novi blok na vrhu smanjuje šansu da napadač prepravi stariji. Satoshi je to izračunao u odeljku 11, a šta to znači za onoga ko prima novac, objašnjava tekst o tome koliko potvrda da sačekaš. Zato je ovaj dogovor verovatan, a ne apsolutan. Šansa da se odluka promeni pada sa svakim blokom, ali nikad ne postaje tačno nula.

I granica za izdajnike je drugačija. Whitepaper računa na to da pošteni čvorovi imaju većinu procesorske snage. Ko ima polovinu snage ili više, može da prepravi svoje skorašnje transakcije, kako objašnjava tekst o napadu 51%. Ni on, međutim, ne može da napravi blok sa tuđim bitcoinima ili sa novcem ni iz čega, jer takav blok svaki čvor odbacuje sam.

Prvi i poslednji red tabele Satoshi sažima u zaključku whitepapera. Čvorovi ne moraju da budu poznati, a poruke je dovoljno isporučiti po principu najbolje moguće isporuke. Čvorovi mogu da napuste mrežu i da se vrate, a lanac dokaza o radu tada prihvataju kao dokaz o onome što se desilo dok ih nije bilo (odeljak 12).

Šta iz ovoga sledi za tebe

Po nama, tačnije je reći da Bitcoin nije rešio Lamportov problem, nego da je postavio novi. Lamport pita kako da se poznati učesnici slože tačno i odmah. Bitcoin pita kako da se slože nepoznati, sa dogovorom koji jača kako vreme prolazi. Odgovor plaća strujom, a ne spiskom.

Za veći iznos sačekaj više potvrda, jer svaka sledeća smanjuje šansu da se plaćanje poništi. I veruj svom čvoru više nego tuđem, jer pravila proverava čvor, a ne broj onih koji ti nešto tvrde.

Šta dalje?

Ovo je drugi tekst dela staze o filozofiji i istoriji pokreta. Sledeći je tekst Antifragilnost Bitcoina: šta su udarci promenili u mreži, o tome kako je Bitcoin podneo grešku u kodu, podelu lanca, propast menjačnice i zabranu rudarenja.

Generali moraju da znaju ko je u igri. Bitcoin pita samo koliko je rada uloženo.