W jaki sposób blockchain zgadza się co do stanu sieci w obecności szeregu wadliwych procesów?
Sieci rozproszone, próbując rozwiązać ten problem, zastosowały algorytmy. Jednak nie każdy blockchain stosuje te same rozwiązania. Należy zacząć od genezy całego zagadnienia. Nieformalnie, zawiera się on w dwóch pytaniach w kontekście sieci:
- Co się stanie, gdy dany użytkownik sieci postanowi nie przestrzegać zasad, tym samym próbując manipulować stanem rejestru?
- Co się stanie, gdy liczniejsza grupa użytkowników, niestanowiąca większości, podejmie taką próbę?
Problem dwóch armii
Problem ten został po raz pierwszy opisany w roku 1975 przez E. A. Akkonyunlu, K. Ekanadham oraz R. V. Huber z State University of New York at Stony Brook. Opisuje on abstrakcyjny scenariusz, w którym to dwóch generałów próbuje zaatakować wspólnego wroga. Każdy z generałów posiada własną armię. W pojedynkę żadna z nich nie jest w stanie pokonać przeciwnika, dlatego muszą ze sobą współpracować. Sytuacja na pierwszy rzut oka wydaje się prosta do rozwiązania. Wystarczy porozumieć się co do momentu wspólnego uderzenia.
Jednak jest jeden haczyk. Każda z armii stacjonuje na dwóch odległych od siebie wzgórzach. Obóz, w którym przebywa wróg, znajduje się w dolinie pomiędzy sojuszniczymi oddziałami generałów. W celu porozumienia się i zdecydowania co do chwili ataku, Generał 1 musi wysłać posłańca z wiadomością przez terytorium wroga. W związku z tym istnieje ryzyko, że wysłannik zostanie pojmany. W rezultacie Generał 1 zaatakuje obóz wroga, podczas gdy Generał 2 i jego armia pozostanie w pieleszach.
W sytuacji powodzenia, Generał 2 musi potwierdzić, że otrzymał wiadomość. Wysyła więc swojego posłańca powtarzając proces. Prowadzi to do ciągłego rozgrywania scenariusza. Ponadto, obaj generałowie muszą wziąć pod uwagę fakt, że posłaniec musiał przedrzeć się przez obóz wroga. Fakt ten budzi wątpliwości co do autentyczności wiadomości. W związku z tym nie ma możliwości zagwarantowania pewnego, zgodnego planu ataku obu armii. W dalszej części artykułu będę posługiwał się skrótami: G - Generał, G2 - Generał 2, G3 - Generał 3.
Problem bizantyjskich generałów
Problem ten opiera się na podobnym scenariuszu. Z tą różnicą, że generałów jest więcej, niż dwóch. Ponadto, jeden z nich posiada uprawnienie do zainicjowania pierwotnego ataku (dalej będę go określał jako Naczelny Dowódca). Ponownie celem jest zgoda stron, co do planu działania.Tym razem należy wziąć pod uwagę możliwość, że niektórzy generałowie mogą być zdrajcami, próbującymi przeszkodzić w osiągnięciu porozumienia.
Dowódcy muszą wypracować odpowiedni algorytm, który zapewni, że:
- Wszyscy lojalni generałowie zdecydują się na ten sam plan działania. Posłuszni dowódcy muszą podążać zgodnie z wyznaczonym algorytmem. Algorytm musi zagwarantować spełnienie warunku A, bez względu na to co generałowie-zdrajcy postanowią zrobić w zaistniałym scenariuszu.
- Niewielka liczba zdrajców nie może wpłynąć na adaptację złego planu ataku przez lojalnych dowódców.
Próbując być obiektywnym, ciężko jest określić, co jest właściwym działaniem, dlatego plan uznany przez większość, uważany jest za wiarygodny. W takiej sytuacji, konsensus może zostać osiągnięty tylko, gdy zostaną spełnione dwa warunki:
- Wszyscy lojalni generałowie spełniają ten sam rozkaz.
- Jeżeli Naczelny Dowódca należy do grona lojalnych generałów, wówczas każdy posłuszny generał wykonuje jego rozkaz.
Naczelny Dowódca wysyła dwie takie same informacje. Niestety, Generał 2 przekazuje zmienioną wiadomość, tym samym wprowadzając w błąd lojalnego Generała 1. Konsensus nie może zostać osiągnięty.
Kolejny przykład opiera się na sytuacji, w której Naczelny Dowódca wysyła dwie różne wiadomości. Generał 1 otrzymuje sprzeczne informacje. Nie jest w stanie stwierdzić, która z nich należy do zdrajcy.
Zgodnie z powyższym algorytmem konsensus może być tylko w sytuacji, gdy 2/3 generałów jest uczciwych. Jeśli zdrajcy przekraczają 1/3, konsensus nie zostaje osiągnięty, armie nie koordynują swojego ataku, a wróg wygrywa.
Kiedy więc konsensus może zostać osiągnięty?
- Naczelny Dowódca przesyła v do każdego generała.
- G wysyła v to G2, G3 wysyła x to G2.
- G2 otrzymuje 3 wiadomości v, v oraz x. Ostateczna decyzja to większość głosów z G, G2, G3. W rezultacie osiągnięto konsensus.
Co w sytuacji, gdy Naczelny Dowódca jest zdrajcą?
- Naczelny Dowódca wysyła 3 wartości: x do G, y do G2, z do G3.
- G przesyła x do G2 oraz G3 | G2 przesyła y do G oraz G3 | G3 przesyła z do G oraz G2
- G, G2, G3 posiadają te same wartości (x, y, z).
Byzantine Fault Tolerance oraz jego znaczenie dla technologii blockchain
Czytając o kryptowalutach, możemy natknąć się na określenie Byzantine Fault Tolerance (dalej: BFT). BFT jest cechą charakteryzującą system, który toleruje klasę niepowodzeń, które należą do problemu generałów bizantyjskich. Algorytm przedstawiony w poprzednim rozdziale posiada cechę BFT, dopóki liczba zdrajców nie jest większa niż 1/3 wszystkich dowódców.
Blockchain zmuszony jest korzystać z algorytmu, dzięki któremu będzie mógł zapanować nad ewentualnym chaosem spowodowanym przez “zdrajców”. Dlatego tak bardzo istotnym elementem dla rejestru jest posiadanie mechanizmu, który zapobiegnie takiej awarii. W sytuacji braku BFT, dany użytkownik jest w stanie przesyłać fałszywe informacje, wpływając tym samym na wiarygodność danego blockchaina.
Źródła:
- http://hydra.infosys.tuwien.ac.at/teaching/courses/AdvancedDistributedSystems/download/1975_Akkoyunlu,%20Ekanadham,%20Huber_Some%20constraints%20and%20tradeoffs%20in%20the%20design%20of%20network%20communications.pdf
- https://people.eecs.berkeley.edu/~luca/cs174/byzantine.pdf