Konsensus w blockchainsteemCreated with Sketch.

in #pl-artykuly6 years ago

nagłówekx22.jpg

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ę?
W pierwszej części tego tekstu, opowiem o koncepcjach, które doprowadziły do utworzenia takich protokołów jak Proof of Work czy Proof of State. Zaczniemy od “Problemu dwóch armii” (The Two generals problem).

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.
1 GEAFIKA.jpg

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:

  1. 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.
  2. 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:

  1. Wszyscy lojalni generałowie spełniają ten sam rozkaz.
  2. Jeżeli Naczelny Dowódca należy do grona lojalnych generałów, wówczas każdy posłuszny generał wykonuje jego rozkaz.
Problem opisany przez L.Lamport, R.Shostak oraz M.Pease nie ma rozwiązania w sytuacji, gdy do porozumienia musi dojść grupa trzech generałów, w której znajduje się jeden zdrajca. Badacze posłużyli się dwoma możliwymi wariantami: atak lub odwrót.

2GRAFIKA.jpg
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.
3GRAFIKA.jpg
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?

4GRAFIKA.jpg

  1. Naczelny Dowódca przesyła v do każdego generała.
  2. G wysyła v to G2, G3 wysyła x to G2.
  3. 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.
Należy pamiętać, że konsensus nie określa co jest dobrym planem. Algorytm zapewnia tylko, że generałowie dojdą do porozumienia co do tego samego planu działania.

Co w sytuacji, gdy Naczelny Dowódca jest zdrajcą?

5GRAFIKA.jpg

  1. Naczelny Dowódca wysyła 3 wartości: x do G, y do G2, z do G3.
  2. G przesyła x do G2 oraz G3 | G2 przesyła y do G oraz G3 | G3 przesyła z do G oraz G2
  3. G, G2, G3 posiadają te same wartości (x, y, z).
Strony osiągają konsensus, gdyż każda z nich posiada te same wartości. Zgodnie z powyższym przykładem, nawet jeśli x, y, z są różne, wartość funkcji większości(x,y,z) jest taka sama.

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:

Sort:  

Motyw z dowódcami i zdrajcami przypadł mi do gustu. ;)
Dobry artykuł i świetnie wytłumaczone zagadnienie.

Coin Marketplace

STEEM 0.35
TRX 0.12
JST 0.040
BTC 70734.57
ETH 3561.52
USDT 1.00
SBD 4.75