Protokół konsensusu Stellar został po raz pierwszy opisany w David Mazière w 2015 roku. Jest to "federacyjny system porozumienia bizantyjskiego", który pozwala zdecentralizowanym sieciom obliczeniowym bez liderów efektywnie osiągać konsensus w jakiejkolwiek decyzji. Sieć płatnicza Stellar wykorzystuje Stellar Consensus Protocol (SCP) do prowadzenia uzgodnionej historii transakcji, którą widzą wszyscy uczestnicy.
Uważa się, że protokoły konsensusu są trudne do zrozumienia. SCP jest prostszy od większości z nich, ale nadal dzieli tę reputację — częściowo z powodu błędnego przekonania, że "federacyjne głosowanie", któremu poświęcona jest pierwsza połowa artykułu naukowego, jest SCP. Ale to nieprawda! To tylko ważny element, który w drugiej części artykułu jest używany do stworzenia faktycznego protokołu konsensusu Stellar.
W tym artykule krótko opowiemy, czym jest "system porozumień", co może uczynić go "bizantyjskim" oraz dlaczego przekształcić bizantyjskiego systemu na "federacyjny". Następnie wyjaśnimy procedurę głosowania federacyjnego opisaną w artykule o SCP, a na końcu wyjaśnimy sam protokół SCP.
Systemy porozumień
System porozumień pozwala grupie uczestników osiągnąć konsensus w jakiejś kwestii, na przykład, co zamówić na obiad.
My w firmie Interstellar wdrożyliśmy własny system porozumienia obiadowego: zamawiamy to, co mówi nasz menedżer operacyjny John. To prosty i efektywny system porozumień. Wszyscy ufamy Johnowi i wierzymy, że codziennie znajdzie coś interesującego i pożywnego.
Ale co jeśli John nadużyje naszego zaufania? Może jedynie postanowić, że wszyscy powinniśmy zostać weganami. Za tydzień lub dwa prawdopodobnie obalimy go i przekażemy władzę Elizabeth. Ale nagle ona uwielbia awokado z anchois i myśli, że wszyscy powinni tacy być. Władza psuje. Dlatego lepiej znaleźć bardziej demokratyczną metodę: jakiś sposób, aby upewnić się, że różne preferencje są uwzględnione, zapewniając jednocześnie terminowy i jednoznaczny wynik, aby uniknąć sytuacji, w której nikt nie zamówi obiadu lub pięć osób złoży różne zamówienia, lub dyskusja przeciągnie się do wieczora.
Wydaje się, że rozwiązanie jest proste: przeprowadzić głosowanie! Ale to zwodnicze wrażenie. Kto zbierałby głosy i informował o wynikach? I dlaczego pozostali mieliby wierzyć temu, co powie? Najpierw możemy zagłosować na lidera, któremu ufamy w przeprowadzeniu głosowania — ale kto poprowadzi pierwszym to głosowanie? Co jeśli nie uda nam się wybrać lidera? Lub jeżeli się zgodzimy, a ten lider utknie na spotkaniu lub zachoruje?
Podobne problemy występują w rozproszonych sieciach komputerowych. Wszyscy uczestnicy lub węzły muszą uzgodnić jakieś rozwiązanie, na przykład, czyja kolej jest na aktualizację wspólnego pliku lub pobranie zadania z kolejki przetwarzania. W sieci kryptowalut węzły wielokrotnie muszą wybierać, jak wygląda pełna historia spośród kilku możliwych wersji, które czasami są sprzeczne. To porozumienie sieciowe gwarantuje odbiorcy, że moneta jest (a) ważna (nie sfałszowana) i (b) jeszcze nie została wydana gdzie indziej. Gwarantuje to również, że będzie mógł wydać monety w przyszłości, ponieważ nowy odbiorca będzie miał te same gwarancje z tych samych powodów.
Każdy system uzgodnień w rozproszonej sieci komputerowej musi być odporny na błędy: powinien dostarczać spójne wyniki mimo błędów, takich jak wolne linie komunikacyjne, nieodpowiadające węzły i nieprawidłowa kolejność wiadomości. Bizantyńska system uzgodnień jest dodatkowo odporny na "bizantyńskie" błędy: węzły, które podają fałszywe informacje, czy to z powodu błędów, czy z zamiarem podważenia systemu lub zdobycia jakiejś przewagi. "Bizantyńska" odporność na błędy — możliwość zaufania zbiorowemu rozwiązaniu, nawet gdy niektórzy członkowie grupy mogą kłamać lub w inny sposób łamać zasady podejmowania decyzji — nosi nazwę od , którzy próbowali skoordynować atak. u Anthony'ego Stevensona.
Rozważmy właściciela kryptowaluty Alice, która musi wybrać między zakupem smacznych lodów od Boba a spłatą długu Carol. Może Alice chce zapłacić obu jednocześnie, oszukując, wydając tę samą monetę. Aby to zrobić, musi przekonać komputer Boba, że moneta nigdy nie została przekazana Carol, i przekonać komputer Carol, że moneta nigdy nie została przekazana Bobowi. Bizantyjski system konsensusu czyni to praktycznie niemożliwym, stosując formę zasady większości, zwaną kwarumem. Węzeł w takiej sieci odmawia przejścia do określonej wersji historii, dopóki nie zobaczy, że odpowiednia liczba rówieśniczych węzłów – kwarum – zgadza się na to przejście. Gdy to nastąpi, utworzą wystarczająco dużą grupę wyborczą, aby zmusić pozostałe węzły sieci do zaakceptowania ich decyzji. Alice może zmusić niektóre węzły do kłamania w jej imieniu, ale jeśli sieć jest wystarczająco duża, jej próba zostanie stłumiona głosami uczciwych węzłów.
Ile węzłów jest potrzebnych do kworum? Jak najmniej, a dokładniej – kwalifikowana większość, aby walczyć z błędami i oszustwami. Ale aby obliczyć większość, trzeba znać całkowitą liczbę uczestników. W biurze Interstellar lub podczas wyborów okręgowych te liczby są łatwe do uzyskania. Ale jeśli twoja grupa to słabo określona sieć, w którą węzły mogą wchodzić i wychodzić według woli, bez zgody centrum, potrzebna jest federacyjna system wizantyjskiego konsensusu, zdolny do określenia kworum nie z wcześniej ustalonej listy węzłów, lecz dynamicznie, z ciągle zmieniającego się i nieuchronnie niepełnego obrazu węzłów w danym momencie.
Może się wydawać niemożliwe stworzenie kworum z punktu widzenia jednego węzła w rozległej sieci, ale jest to możliwe. Takie kworum może nawet zapewnić wyniki zdecentralizowanego głosowania. Dokument techniczny SCP pokazuje, jak to zrobić za pomocą procedury zwanej głosowaniem federacyjnym.
Dla niecierpliwych
Reszta artykułu szczegółowo opisuje głosowanie federacyjne i protokół konsensusu Stellar. Jeśli nie interesują cię szczegóły, oto ogólny zarys procesu.
- Węzły przeprowadzają rundy federalnego głosowania na «nominantów». Runda federalnego głosowania oznacza:
- Węzeł głosuje nad jakimś stwierdzeniem, na przykład «Proponuję wartość V»;
- Węzeł słucha głosów uczestników, aż znajdzie ten, który może «zaakceptować»;
- Węzeł szuka «kworum» dla tego stwierdzenia. Kworum «potwierdza» nominanta.
- Gdy węzeł jest w stanie potwierdzić jednego lub kilku nominantów, stara się «przygotować» «kartę do głosowania» poprzez kilka rund federalnego głosowania.
- Gdy węzeł jest w stanie sprawdzić gotowość karty do głosowania, stara się ją skommitować za pomocą jeszcze większej liczby rund federalnego głosowania.
- Gdy węzeł może potwierdzić komit karty do głosowania, może «eksternalizować» wartość tej karty, używając jej jako wyniku konsensusu.
Te kroki obejmują kilka rund federalnego głosowania, które w sumie tworzą jedną rundę SCP. Przyjrzyjmy się bliżej, co dzieje się na każdym etapie.
Głosowanie federalne
Głosowanie federalne to procedura określenia, czy sieć może się zgodzić na propozycję. W rundzie głosowania każdy węzeł musi wybrać jedną z potencjalnie wielu możliwych wartości. Nie może tego zrobić, dopóki nie będzie pewien, że inne węzły w sieci nie wybiorą innego wyniku. Aby być co do tego pewnymi, węzły wymieniają się strumieniem wiadomości tam i z powrotem, tak aby każdy potwierdził, nawet bez optymalizacji pod takie zadania, wygrywa i na obcym terenie: kworum węzeł przyjmuje to samo decyzję. Reszta tej sekcji wyjaśnia pojęcia w tym stwierdzeniu oraz jak przebiega cała procedura.
Kworum i przekroje kworum
Zacznijmy od definicji kworum. Jak omówiliśmy wcześniej, w zdecentralizowanej sieci z dynamicznym członkostwem niemożliwe jest z góry określenie liczby węzłów i, w związku z tym, ile potrzeba do większości. Głosowanie federalne rozwiązuje ten problem, wprowadzając nową ideę przekroju kworum (quorum slice): mały zestaw równego poziomu węzłów, którym węzeł ufa w przekazywaniu informacji o stanie głosowania w pozostałej części sieci. Każdy węzeł definiuje własny przekrój kworum (członkiem którego staje się de facto).
Formowanie kworum zaczyna się od przekroju kworum. Do każdego węzła dodawane są węzły jego przekroju. Następnie dodawane są członkowie przekrojów tych węzłów i tak dalej. W miarę postępu pojawia się coraz więcej węzłów, których nie można dodać, ponieważ zostały już uwzględnione w wycinku. Kiedy nie ma już nowych węzłów do dodania, proces się zatrzymuje: stworzyliśmy quorum poprzez „zamknięcie przechodnie” (transitive closure) wycinka quorum początkowego węzła.
Aby znaleźć quorum z danego węzła…
… dodajemy członków jego wycinka…
… następnie dodajemy członków wycinków tych węzłów.
Kontynuujemy, aż nie zostaną węzły do dodania.
Nie ma już węzłów do dodania. To quorum.
W rzeczywistości każdy węzeł może należeć do więcej niż jednego wycinka. Aby utworzyć quorum, wybierz tylko jeden z wycinków i dodaj członków; następnie wybierz dowolny wycinek dla każdego z członków i dodaj członków wycinka i tak dalej. Oznacza to, że każdy węzeł jest członkiem wielu możliwych quorum. tego Wybierz tylko jeden wycinek quorum na każdym etapie.
Jedno możliwe quorum. Lub alternatywna opcja…
… wybieramy inne wycinki…
…(gdy to możliwe)…
… tworzy inne quorum.
Jak węzeł dowiaduje się, w jakich wycinkach znajdują się inne węzły? Tak samo jak inne informacje o innych węzłach: z przekazów, które każdy węzeł przesyła do sieci, kiedy jego stan głosowania się zmienia. Każdy przekaz zawiera informacje o wycinkach węzła wysyłającego. W technicznym dokumencie SCP nie opisano mechanizmu komunikacji. Realizacje zazwyczaj wykorzystują
protokół gossip для гарантированной трансляции сообщений по всей сети.
Przypomnijmy, że w niefederacyjnej bizantyjskiej systemie uzgodnień kworum definiowane jest jako większość wszystkich węzłów. Bizantyjski system uzgodnień został zaprojektowany z perspektywy pytania: ile nieuczciwych węzłów jest w stanie wytrzymać system? W systemie z N węzłami, zaprojektowanym do przetrwania przy f awariach (oszustwach), węzeł musi być w stanie osiągnąć postęp, otrzymując odpowiedzi od N−f peerów, ponieważ f z nich może nie działać. Jednak otrzymując odpowiedzi od N−f peerów, można założyć, że wszystkie f peerów (od których węzeł nie otrzymał odpowiedzi) są w rzeczywistości uczciwe. Tak więc złośliwe są f z N−f peerów (od których otrzymano odpowiedzi). Aby węzły doszły do jednomyślności, uczciwa większość musi pochodzić od pozostałych węzłów, a więc potrzebujemy, aby N−f było większe niż 2f, czyli N > 3f. Tak więc system, zaprojektowany do przetrwania przy f awariach, zwykle będzie miał łącznie N=3f+1 węzłów i rozmiar kworum 2f+1. Gdy tylko propozycja przekroczy próg kworum, pozostałe człony sieci są przekonane, że wszelkie konkurencyjne propozycje poniosą porażkę. Tak więc sieć zbiega do wyniku.
Jednak w federacyjnej bizantyjskiej systemie uzgodnień nie tylko nie może być większości (ponieważ nikt nie zna ogólnego rozmiaru sieci), ale koncepcja większości jest całkowicie bezużyteczna! Jeśli członkostwo w systemie jest otwarte, ktoś może zdobyć większość, po prostu przeprowadzając tak zwaną atak Sybilli: wielokrotnie przyłączając się do sieci przez kilka węzłów. Dlaczego więc przechodnie zamknięcie przekroju można nazwać kwarumem, i jak on jest w stanie tłumić konkurencyjne propozycje?
Technicznie rzecz biorąc, w żaden sposób! Wyobraźcie sobie sieć z sześcioma węzłami, w której dwie trójki są odizolowane w przekroju kworum od siebie. Pierwsza podgrupa może podjąć decyzję, o której druga nigdy nie usłyszy, i odwrotnie. Dla tej sieci nie ma sposobu na osiągnięcie konsensusu (chyba że przypadkowo).
Dlatego SCP wymaga, aby dla głosowania federacyjnego (i zastosowania ważnych twierdzeń artykułu) sieć miała właściwość nazywaną przecięciem kworum.W sieci o tej właściwości każde dwa kworum, które można zbudować, zawsze pokrywają się przynajmniej w jednym węźle. Dla określenia dominujących nastrojów w sieci jest to tak samo skuteczne, jak posiadanie większości. Intuicyjnie oznacza to, że jeśli jakiekolwiek kworum zgadza się z twierdzeniem X, żadne inne kworum nigdy nie może zgodzić się z czymś innym, ponieważ musi zawierać jakiś węzeł z pierwszego kworum, które już zagłosowało za X.
Jeśli w sieci istnieje przecięcie kworum…
… wtedy każde dwa kworum, które możesz skonstruować…
… zawsze będą się przecinać.
(Oczywiście, nakładające się węzły mogą okazać się bizantyjskimi oszustami lub złymi w innych aspektach. W takim przypadku przecięcie kworum w ogóle nie pomaga sieci osiągnąć zgody. Z tego powodu wiele wyników w dokumencie technicznym SCP opiera się na wyraźnie wyrażonych założeniach, takich jak to, że w sieci pozostało przecięcie kworum nawet po usunięciu złych węzłów. Dla uproszczenia pozostawimy te założenia nijakimi w reszcie artykułu).
Może się wydawać nierozsądne oczekiwać, że w sieci niezależnych węzłów możliwe jest niezawodne przecięcie kworum. Ale są dwie przyczyny, dla których tak się dzieje.
Pierwsza przyczyna to istnienie samego internetu. Internet to idealny przykład sieci niezależnych węzłów z przecięciem kworum. Większość węzłów w internecie łączy się tylko z kilkoma innymi lokalnymi węzłami, ale te małe zbiory pokrywają się na tyle, że każdy węzeł jest dostępny z każdego innego węzła za pomocą jakiejś trasy.
Druga przyczyna jest specyficzna dla sieci płatniczej Stellar (najbardziej rozpowszechnione zastosowanie SCP). Każdy aktyw w sieci Stellar ma swojego emitenta, a wytyczne Stellar wymagają, aby każdy emitent wyznaczył jeden lub kilka węzłów w sieci do obsługi żądań wykupu. W Twoim interesie jest bezpośrednio lub pośrednio włączenie tych węzłów do przekrojów kworum dla każdego interesującego Cię aktywu. W ten sposób kworumy dla wszystkich węzłów zainteresowanych danym aktywem będą pokrywać się przynajmniej w tych węzłach wykupu. Węzły zainteresowane wieloma aktywami będą włączać do swoich przekrojów kworum wszystkie węzły wykupu odpowiednich emitentów i będą dążyć do łączenia wszystkich aktywów. Dodatkowo, wszelkie aktywa, które nie są w ten sposób powiązane z innymi w sieci, i nie muszą być powiązane — jest to zaplanowane, aby w tej sieci nie było pokrywania się kworum (na przykład banki w obszarze dolara czasami chcą handlować z bankami w obszarze euro i bankami z obszaru peso, dlatego znajdują się w tej samej sieci, ale nikt z nich nie interesuje się osobną siecią dzieci handlujących kartami baseballowymi).
Oczywiście, oczekiwanie pokrywania się kworum nie jest gwarancją. Inne bizantyjskie systemy zgód z powodu swojej złożoności w dużej mierze są zobowiązane do zapewnienia kworum. Ważnym innowacyjnym rozwiązaniem SCP jest to, że przenosi odpowiedzialność za tworzenie kworum z samego algorytmu konsensusu na poziom aplikacji. W ten sposób, chociaż głosowanie federacyjne jest dość powszechne w głosowaniach w dowolnych sprawach, jego niezawodność krytycznie zależy od szerszego znaczenia tych wartości. Niektóre hipotetyczne zastosowania mogą okazać się mniej wygodne do tworzenia dobrze powiązanych sieci niż inne.
Głosowanie, przyjęcie i potwierdzenie
W rundzie głosowania federacyjnego węzeł opcjonalnie zaczyna głosować na pewną wartość V. Oznacza to rozprzestrzenienie w sieci wiadomości: „Jestem węzłem N, moje przekroje kworum Q, i głosuję na V”. Kiedy węzeł głosuje w ten sposób, obiecuje, że nigdy nie głosował przeciwko V i nigdy nie będzie.
W transmisjach od węzłów peer-to-peer każdy węzeł widzi, jak głosują inne węzły. Gdy węzeł zbierze wystarczającą liczbę takich wiadomości, może śledzić przekroje kworum i spróbować znaleźć kworuma. Jeśli widzi kworum węzłów, które również głosują na V, może przejść do akceptacji V i przesłać nową wiadomość do sieci: „Jestem węzłem N, moje przekroje kworum Q i akceptuję V”. Akceptacja zapewnia silniejsze gwarancje niż proste głosowanie. Kiedy węzeł głosuje na V, nigdy nie może głosować na inne opcje. Ale jeśli węzeł akceptuje V, żaden węzeł w sieci nigdy nie zaakceptuje innej opcji (twierdzenie 8 w dokumencie technicznym SCP to udowadnia).
Oczywiście, istnieje duże prawdopodobieństwo, że od razu nie znajdzie się kworum węzłów, które zgodzą się na V. Inne węzły mogą głosować na inne wartości. Ale dla węzła istnieje jeszcze jeden sposób, aby przejść od prostego głosowania do akceptacji. N może zaakceptować inną wartość W, nawet jeśli na nią nie głosował i nawet jeśli nie widzi dla niej kworum. Aby zmienić swój głos, wystarczy zobaczyć blokującą zbiór węzłów, które zaakceptowały W. Blokujący zbiór to po jednym węźle z każdego z przekrojów kworum N. Jak sama nazwa wskazuje, jest on w stanie blokować jakąkolwiek inną wartość. Jeśli wszystkie węzły w takim zbiorze akceptują W, to (zgodnie z twierdzeniem 8) nigdy nie uda się utworzyć kworum akceptującego inną wartość, a zatem dla N również bezpiecznie jest zaakceptować W.
Węzeł N z trzema przekrojami kworum.
B-D-F to blokujący zbiór dla N: zawiera po jednym węźle z każdego z przekrojów N.
B-E jest również blokującym zbiorem dla N, ponieważ E pojawia się w dwóch przekrojach N.
Jednak blokujący zbiór to nie kworum. Byłoby zbyt łatwo oszukać węzeł N, aby zaakceptował pożądaną wartość, jeśli wystarczyłoby zhakować tylko jeden węzeł w każdym z przekrojów N. Dlatego akceptacja wartości to jeszcze nie koniec głosowania. Zamiast tego N musi potwierdzić wartość, tj. zobaczyć kworum węzłów, które ją akceptują. Jeśli dojdzie tak daleko, to, jak udowadnia dokument techniczny SCP (w twierdzeniu 11), pozostała część sieci również ostatecznie potwierdzi tę samą wartość, w związku z czym N zakończy głosowanie federacyjne z określoną wartością jako wynikiem.
Głosowanie federacyjne.
Proces głosowania, podejmowania decyzji i zatwierdzania działa jako jedna pełna runda głosowania federacyjnego. Protokół konsensusu Stellar łączy wiele takich rund, aby stworzyć kompletny system konsensusu.
Protokół konsensusu Stellar
Dwie najważniejsze cechy systemu konsensusu to bezpieczeństwo i odporność. Algorytm konsensusu jest "bezpieczny", jeśli nigdy nie może dać różnych wyników różnym uczestnikom (kopie historii Boba nigdy nie będą sprzeczne z Keri). "Odporność" oznacza, że algorytm zawsze wygeneruje wynik, czyli nie utknie.
Opisana procedura głosowania federacyjnego jest bezpieczna w tym sensie, że jeśli węzeł zatwierdzi wartość V, żaden inny węzeł nie zatwierdzi innej wartości. Jednak "nie zatwierdzi innej wartości" nie oznacza, że na pewno coś zatwierdzi. Uczestnicy mogą głosować na tak wiele różnych wartości, że żadna z nich nie osiągnie progu akceptacji. Oznacza to, że w głosowaniu federacyjnym brakuje odporność.
Protokół konsensusu Stellar wykorzystuje głosowanie federacyjne w taki sposób, aby zapewnić zarówno bezpieczeństwo, jak i odporność. (Gwarancje bezpieczeństwa i odporności SCP mają teoretyczny limit. Konstrukcja wybiera bardzo silną gwarancję bezpieczeństwa, poświęcając nieznacznie odporność, ale biorąc pod uwagę wystarczający czas, z dużym prawdopodobieństwem osiągnięty zostanie konsensus). Krótko mówiąc, idea polega na przeprowadzaniu kilku głosowań federacyjnych na temat różnych wartości, aż jedna z nich przejdzie przez wszystkie etapy głosowania SCP opisane poniżej.
Wartości, wobec których SCP dąży do konsensusu, mogą być historią transakcji, zamówieniem obiadu lub czymkolwiek innym, ale istotne jest, aby zauważyć, że to nie te wartości są przyjmowane ani potwierdzane. Zamiast tego głosowanie federacyjne odbywa się w odniesieniu do twierdzeń dotyczących tych wartości.
Pierwsze rundy głosowania federacyjnego odbywają się na etapie nominacji (nomination phase), w zestawie twierdzeń typu "Nominuję V", być może dla wielu różnych wartości V. Celem nominacji jest znalezienie jednego lub kilku twierdzeń, które przejdą przez akceptację i potwierdzenie.
Po znalezieniu potwierdzonych kandydatów, SCP przechodzi do etapu głosowania, którego celem jest znalezienie pewnego lokalu wyborczego (czyli pojemnika na proponowaną wartość) oraz kworum, które może ogłosić commitu jego (commit). Jeśli kworum zatwierdzi lokal wyborczy, jego wartość uznaje się za konsensus. Jednak zanim węzeł będzie mógł zagłosować za zatwierdzeniem lokalu wyborczego, musi najpierw potwierdzić odwołanie wszystkich lokali wyborczych z mniejszą wartością licznika. Te kroki — odwołanie lokali wyborczych w celu znalezienia tego, dla którego można potwierdzić zatwierdzenie — obejmują kilka rund federacyjnego głosowania na kilka oświadczeń o lokalach wyborczych.
W kolejnych sekcjach dokładniej opisano wyłanianie i głosowanie.
Wyłanianie
Na początku etapu wyłaniania każdy węzeł może spontanicznie wybrać wartość V i zagłosować za stwierdzeniem „Wyłaniam V”. Celem na tym etapie jest potwierdzenie wyłonienia pewnej wartości poprzez federacyjne głosowanie.
Może się zdarzyć, że wystarczająca liczba węzłów głosuje za wystarczająco różnymi oświadczeniami, a żadne wyłonienie nie może osiągnąć progu przyjęcia. Dlatego oprócz transmisji własnych głosów nominacyjnych, węzły „odzwierciedlają” nominacje swoich sąsiadów. Odzwierciedlenie (echo) oznacza, że jeśli węzeł głosuje za wyłonieniem V, ale widzi wiadomość od sąsiada głosującego za wyłonieniem W, to teraz zagłosuje zarówno za wyłonieniem V, jak i W. (Nie wszystkie głosy sąsiadów są odzwierciedlane podczas wyłaniania, ponieważ może to prowadzić do eksplozji różnych nominantów. SCP zawiera mechanizm regulacji tych głosów. Krótko mówiąc, istnieje formuła do określenia „priorytetu” sąsiada z punktu widzenia węzła, a odzwierciedlane są tylko głosy węzłów o wysokim priorytecie. Im dłużej trwa wyłanianie, tym niższy próg, dlatego węzeł rozszerza zestaw sąsiadów, których głosy będzie odzwierciedlał. Formuła priorytetu jako jedno z wejść uwzględnia numer slotu, więc wysoko priorytetowy węzeł równorzędny dla jednego slotu może być nisko priorytetowy dla innego i odwrotnie).
Konceptualnie wystąpienie równolegle zarówno V, jak i W to oddzielne głosy federacyjne, każdy z nich jest zdolny do osiągnięcia przyjęcia lub potwierdzenia. W praktyce, komunikaty protokołu SCP pakują te oddzielne głosy razem.
Chociaż głosowanie na wystąpienie V to obietnica, że nigdy nie zagłosuje się przeciwko wystąpieniu V, na poziomie aplikacji — w tym przypadku SCP — ustala się, co oznacza «przeciw». SCP nie postrzega twierdzenia sprzecznego z głosowaniem «Przedstawiam X», co oznacza, że nie ma komunikatu «Jestem przeciw wystąpieniu X», w związku z czym węzeł może głosować za wystąpieniem dowolnych wartości. Wiele z tych nominacji nie prowadzi do niczego, ale ostatecznie węzeł będzie mógł przyjąć lub potwierdzić jedną lub więcej wartości. Gdy tylko nominant zostanie potwierdzony, staje się kandydatem.
Wystąpienie SCP przy użyciu głosowania federacyjnego. Może być wiele wartości “B” przedstawionych przez równorzędne węzły i «odzwierciedlonych» przez jeden węzeł.
Wystąpienie kandydatów może prowadzić do pojawienia się kilku potwierdzonych kandydatów. Dlatego SCP wymaga, aby poziom aplikacji dostarczył jakiś sposób łączenia kandydatów w jeden kompozyt (composite). Metoda łączenia może być dowolna. Najważniejsze, że jeśli ta metoda jest deterministyczna, to każdy węzeł połączy tych samych kandydatów. W systemie głosowania na obiad «łączenie» może oznaczać po prostu rezygnację z jednego z dwóch kandydatów. (Ale w sposób deterministyczny: każdy węzeł musi wybrać tę samą wartość do resetu. Na przykład, wcześniejszy wybór w porządku alfabetycznym). W sieci płatności Stellar, gdzie ma miejsce głosowanie nad historią transakcji, łączenie dwóch proponowanych nominantów zakłada połączenie transakcji, które one zawierają, oraz ostatnich z ich dwóch znaczników czasu.
Techniczny opis SCP dowodzi (twierdzenie 12), że do końca fazy wystąpienia sieć w końcu zbiega się do jednego kompozytu. Ale jest problem: głosowanie federacyjne to protokół asynchroniczny (podobnie jak SCP). Innymi słowy, węzły nie są skoordynowane czasowo, a jedynie poprzez wiadomości, które wysyłają. Z perspektywy węzła nie jest jasne, kiedy zakończyło się faza zgłaszania. I choć wszystkie węzły ostatecznie dojdą do tego samego kompozytu, mogą wybrać różne ścieżki na tej drodze, tworząc po drodze różnych kandydatów kompozytowych, i nigdy nie mogą powiedzieć, który z nich jest ostateczny.
Ale to w porządku. Zgłaszanie to tylko przygotowanie. Najważniejsze jest ograniczenie liczby kandydatów w celu osiągnięcia konsensusu, który następuje w procesie głosowania (balloting).
Głosowanie
Bilet to para , gdzie counter to liczba całkowita, zaczynająca się od 1, a value to kandydat z etapu zgłaszania. Może to być własny kandydat węzła lub kandydat z sąsiedniego węzła, akceptowany przez ten węzeł. Mówiąc w uproszczeniu, podczas głosowania podejmuje się wielokrotne próby, aby sieć osiągnęła konsensus w sprawie jakiegoś kandydata w danym bilecie, prowadząc potencjalnie wiele federacyjnych głosowań dotyczących twierdzeń o biletach. Liczniki w biletach śledzą uczynione próby, a bilety z wyższymi licznikami mają priorytet nad biletami z niższymi licznikami. Jeśli bilet utknie, rozpoczyna się nowe głosowanie, teraz na bilecie .
Ważne jest rozróżnienie wartości (na przykład, co powinno być zamówieniem na obiad: pizza czy sałatki), biletów (para counter-value) i oświadczenia o biletach. Runda SCP obejmuje kilka rund federacyjnego głosowania, w szczególności w odniesieniu do takich twierdzeń jak:
- „Jestem gotów do zatwierdzenia biletu B” i
- „Ogłaszam zatwierdzenie biletu B”
Z perspektywy danego węzła konsensus osiągany jest, gdy znajduje on bilet B, dla którego może potwierdzić (to znaczy znaleźć kworum akceptujące) twierdzenie „Ogłaszam zatwierdzenie biletu B”. Od tego momentu można bezpiecznie działać według wartości wskazanej w B – na przykład złożyć to zamówienie na obiad. Nazywa się to eksternalizacją wartości. Gdy zatwierdzono akceptację biletu, węzeł może być pewny, że każdy inny węzeł dokonał eksternalizacji tej samej wartości lub na pewno dokonana ją w przyszłości.
Chociaż koncepcyjnie wiele federacyjnych głosowań odbywa się na podstawie deklaracji odnośnie wielu różnych głosów, wymieniają się one nie tak dużą ilością wiadomości, ponieważ każda wiadomość enkapsuluje szereg głosów. Jedna wiadomość zatem promuje stan wielu federacyjnych głosowań jednocześnie, na przykład: „Akceptuję zatwierdzenie głosów w zakresie od do .”
Co oznaczają terminy „przygotowany” (prepared) i „zatwierdzenie” (commit)?
Węzeł głosuje za zatwierdzeniem głosu, gdy jest przekonany, że inne węzły nie dokonają zatwierdzenia głosów z innymi wartościami. Przekonanie w tej kwestii jest celem przygotowania deklaracji. Głosowanie, w którym mówi się: „Jestem gotów zatwierdzić głos B”, jest obietnicą, że nigdy nie dokonam zatwierdzenia głosu o wartości mniejszej niż B, tzn. z mniejszym licznikiem (SCP wymaga, aby wartości w głosach miały określoną kolejność. Tak więc, głos jest mniejszy od , jeśli N1<N2, oraz jeśli N1=N2 i V1<V2). Te mniejsze głosy są „odrzucane” (aborted) w trakcie przygotowawczego głosowania, podczas gdy B jest uważane za „przygotowane”.
Dlaczego „Jestem gotów zatwierdzić głos B” oznacza „Obiecuję nigdy nie dopuszczać do zatwierdzenia głosów mniejszych niż B”? Ponieważ SCP definiuje abort jako przeciwieństwo commit. Głosowanie na przygotowanie głosu wiąże się także z głosowaniem na anulowanie niektórych innych głosów, i, jak omawialiśmy wcześniej, głosowanie w jedną stronę to obietnica, że nigdy nie zagłosuję przeciwko temu.
Zanim węzeł przekaże zatwierdzenie, musi najpierw znaleźć głos, który może potwierdzić jako przygotowany. Innymi słowy, przeprowadza federacyjne głosowanie na temat „Jestem gotów zatwierdzić głos B”, być może dla wielu różnych głosów, aż znajdzie ten, który akceptuje kworum.
Skąd pochodzą biuletyny do przygotowania głosowania? Najpierw węzeł przekształca przygotowanie do głosowania na , gdzie C to kandydat-kompozyt, stworzony na etapie nominacji. Jednak nawet po rozpoczęciu przygotowania do głosowania nominat może prowadzić do pojawienia się dodatkowych kandydatów, którzy staną się nowymi biuletynami. Tymczasem piramidy mogą mieć różnych kandydatów, a oni mogą stworzyć zbiór blokujący, który akceptuje „Jestem gotów do zatwierdzenia biuletynu B2”, co przekona węzeł do jego przyjęcia. Wreszcie, istnieje mechanizm czasu oczekiwania, który generuje nowe rundy federacyjnego głosowania na nowych biuletynach z wyższymi licznikami, jeśli obecne biuletyny utknęły.
Gdy węzeł znajdzie biuletyn B, który może potwierdzić jako przygotowany, transmituje nową wiadomość „Zatwierdź biuletyn B”. To głosowanie mówi piram, że węzeł nigdy nie wycofa się z B. W rzeczywistości, jeśli B jest biuletynem , to „Zatwierdź biuletyn ” oznacza bezwarunkową zgodę na głosowanie za gotowość każdego biuletynu od do . Ta dodatkowa wartość pomaga innym węzłom nadrobić zaległości z piratem podczas zatwierdzania, jeśli wciąż znajdują się na wcześniejszych etapach protokołu.
Na tym etapie warto jeszcze raz podkreślić, że są to protokoły asynchroniczne. Tylko dlatego, że jeden węzeł wysyła głosy na zatwierdzenie, nie oznacza, że jego rówieśnicy również to robią. Niektórzy z nich mogą wciąż głosować w sprawie oświadczeń dotyczących przygotowania do głosowania, inni mogą już zewnętrznie zdefiniować wartość. SCP wyjaśnia, jak węzeł powinien obsługiwać każdy typ wiadomości rówieśniczej niezależnie od jego fazy.
Jeśli wiadomość „Ogłaszam zatwierdzenie ” nie może być przyjęta lub potwierdzona, istnieje prawdopodobieństwo przyjęcia lub potwierdzenia wiadomości lub — lub, w każdym razie, dowolnego biuletynu z wartością C, a nie żadnym innym, ponieważ węzeł już obiecał nigdy nie cofnąć . Kiedy węzeł transmituje głosy na zatwierdzenie, będzie to C lub nic, w zależności od tego, jak daleko zajdzie konsensus. Jednak tego wciąż jest niewystarczająco, by węzeł mógł zewnętrznie przekazać C. Niektóre bizantyjskie zdrajcy (mniejsza grupa, opierając się na naszych założeniach o bezpieczeństwie) mogą okłamywać węzeł. Przyjęcie, a następnie potwierdzenie pewnego biuletynu (lub zakresu biuletynów) — oto co daje węzłowi pewność, by w końcu zewnętrznie przekazać C.
Głosowanie SCP poprzez federacyjne głosowanie. Nie pokazano: w każdej chwili może zadziałać licznik, zwiększając wynik w biuletynie (i być może tworząc nowy kompozyt z dodatkowych zgłoszonych kandydatów).
I to wszystko! Gdy sieć osiągnie konsensus, jest gotowa robić to wciąż i wciąż. W sieci płatności Stellar dzieje się to co około 5 sekund: wyczyn, który wymaga zarówno bezpieczeństwa, jak i odporności, gwarantowanych przez SCP.
SCP może to osiągnąć, opierając się na kilku rundach federacyjnego głosowania. Federacyjne głosowanie stało się możliwe dzięki koncepcji przekrojów kworum: zestawów równorzędnych węzłów, którym każdy węzeł zdecydował się ufać jako części swojego (subiektywnego) kworum. Ta konfiguracja oznacza, że można osiągnąć konsensus nawet w sieci z otwartym członkostwem i bizantyjskimi oszustwami.
Dalsze czytanie
- Oryginalny dokument techniczny SCP można znaleźć , a projekt specyfikacji dla jego wdrożenia.
- Oryginalny autor protokołu SCP, David Mazieres, w sposób uproszczony (ale wciąż techniczny) wyjaśnia jego .
- Być może zdziwiło cię, że w tym artykule nie znalazłeś terminów „mining” ani „proof of work”. SCP nie wykorzystuje tych metod, ale niektóre inne algorytmy konsensusu je stosują. Zain Wiserpoon napisał przystępny .
- prostej sieci, osiągającej konsensus podczas jednej pełnej rundy SCP.
- Dla czytelników zainteresowanych realizacjami SCP: zob. , używanej przez sieć płatniczą Stellar, lub , który napisałem dla lepszego zrozumienia SCP.
Źródło: habr.com
