Protokół konsensusu Stellar został po raz pierwszy opisany w Davida Maziera w 2015 r. Jest to „federalny system porozumień bizantyjskich”, który umożliwia zdecentralizowanym sieciom obliczeniowym pozbawionym przywódców skuteczne osiąganie konsensusu w sprawie decyzji. Sieć płatnicza Stellar korzysta z protokołu Stellar Consensus Protocol (SCP), aby zachować spójną historię transakcji, która jest widoczna dla wszystkich uczestników.
Protokoły konsensusu są uważane za trudne do zrozumienia. SCP jest prostszy niż większość z nich, ale nadal podziela tę reputację - częściowo z powodu błędnego poglądu, że „głosowanie federacyjne”, które jest tematem pierwszej połowy artykułu naukowego, to SCP. Ale to nieprawda! Jest to po prostu ważny element składowy, który wykorzystano w drugiej połowie artykułu rzeczywisty Gwiezdny protokół konsensusu.
W tym artykule pokrótce wyjaśnimy, czym jest „system porozumień”, co może uczynić go „bizantyjskim” i dlaczego uczynić system bizantyjski „federalnym”. Następnie wyjaśnimy procedurę głosowania federacyjnego opisaną w artykule SCP, a na koniec wyjaśnimy sam protokół SCP.
Systemy umów
System porozumień pozwala grupie uczestników osiągnąć konsensus w jakiejś sprawie, np. co zamówić na lunch.
W Interstellar wdrożyliśmy własny system umów obiadowych: zamawiamy to, co mówi nasz menadżer operacyjny, John. Jest to prosty i skuteczny system zawierania umów. Wszyscy ufamy Johnowi i wierzymy, że każdego dnia znajdzie dla niego coś ciekawego i pożywnego.
A co, jeśli Jan nadużyje naszego zaufania? Może samodzielnie zdecydować, że wszyscy powinniśmy zostać weganami. Za tydzień lub dwa prawdopodobnie obalimy go i oddamy władzę Elżbiecie. Ale nagle uwielbia awokado z anchois i uważa, że każdy powinien taki być. Władza deprawuje. Lepiej więc znaleźć bardziej demokratyczną metodę: sposób, aby uwzględnić różne preferencje, a jednocześnie zapewnić terminowy i jednoznaczny wynik, tak aby nikt nie zamawiał lunchu, pięć osób nie złożyło różnych zamówień lub nie doszło do dyskusji przeciąga się do wieczora.
Wydawałoby się, że rozwiązanie jest proste: zagłosuj! Ale jest to mylne wrażenie. Kto będzie zbierał karty do głosowania i ogłaszał wyniki? I dlaczego inni mieliby wierzyć w to, co mówi? Być może możemy pierwszy głosujcie na przywódcę, któremu ufamy, że poprowadzi głosowanie – ale kto je poprowadzi pierwszy głosując? A co jeśli nie dojdziemy do porozumienia w sprawie lidera? A co jeśli dojdziemy do porozumienia, ale ten lider utknie na spotkaniu lub pójdzie na zwolnienie lekarskie?
Podobne problemy występują w rozproszonych sieciach komputerowych. Wszyscy uczestnicy lub węzły muszą zgodzić się na jakąś decyzję, na przykład na to, czyja kolej ma zaktualizować udostępniony plik lub usunąć zadanie z kolejki przetwarzania. W sieci kryptowalut węzły wielokrotnie muszą wybierać, jak wygląda pełna historia z kilku możliwych wersji, które czasami są ze sobą sprzeczne. Niniejsza umowa sieciowa zapewnia odbiorcę, że moneta jest (a) ważna (nie jest fałszywa) i (b) nie została jeszcze wydana gdzie indziej. Daje to również pewność, że będzie mógł wydać monety w przyszłości, ponieważ nowy odbiorca będzie miał takie same gwarancje z tych samych powodów.
Każdy system konsensusu w rozproszonej sieci komputerowej musi być odporny na błędy: musi dawać spójne wyniki pomimo błędów, takich jak wolne łącza, niereagujące węzły i nieprawidłowa kolejność komunikatów. bizantyjski System porozumienia jest dodatkowo odporny na błędy „bizantyjskie”: węzły podające fałszywe informacje, czy to na skutek błędu, czy też w ramach celowej próby osłabienia systemu lub uzyskania jakiejś przewagi. „Bizantyjska” tolerancja na błędy – zdolność zaufania decyzji grupy, nawet jeśli niektórzy członkowie grupy mogą kłamać lub w inny sposób nie przestrzegać zasad podejmowania decyzji – nazywa się który próbował koordynować atak. u Anthony'ego Stevensa.
Weźmy pod uwagę Alice, właścicielkę kryptowalut, która musi wybierać pomiędzy kupnem pysznych lodów od Boba a spłatą długu Carol. Być może Alicja chce zapłacić im obu na raz, oszukańczo wydając tę samą monetę. Aby to zrobić, musi przekonać komputer Boba, że moneta nigdy nie została wypłacona Carol i przekonać komputer Carol, że moneta nigdy nie została wypłacona Bobowi. Bizantyjski system porozumień praktycznie uniemożliwia to, stosując formę rządów większości zwaną kworum. Węzeł w takiej sieci odmawia przejścia do określonej wersji historii, dopóki nie upewni się, że wystarczająca liczba równorzędnych użytkowników – kworum – zgodzi się na takie przejście. Gdy to nastąpi, utworzą blok głosowania wystarczająco duży, aby zmusić pozostałe węzły sieci do wyrażenia zgody na ich decyzję. Alicja może zmusić niektóre węzły do kłamstwa w jej imieniu, ale jeśli sieć jest wystarczająco duża, jej próba zostanie pokonana głosami uczciwych węzłów.
Ile węzłów jest wymaganych do uzyskania kworum? Przynajmniej większość, czy raczej większość kwalifikowana, aby zwalczać błędy i oszustwa. Aby jednak policzyć większość, musisz znać całkowitą liczbę uczestników. Liczby te łatwo sprawdzić w biurze Interstellar lub w wyborach okręgowych. Jeśli jednak twoja grupa jest luźno zdefiniowaną siecią, do której węzły mogą wchodzić i wychodzić według własnego uznania bez zgody centrum, wówczas potrzebujesz federalny bizantyjski system porozumień umożliwiający określenie kworum nie na podstawie z góry określonej listy węzłów, ale dynamicznie, na podstawie stale zmieniającej się i nieuchronnie niekompletnej migawki węzłów w danym momencie.
Stworzenie kworum z perspektywy pojedynczego węzła w rozległej sieci może wydawać się niemożliwe, a jednak jest możliwe. Takie kworum może nawet gwarantować wyniki głosowania zdecentralizowanego. Biała księga SCP pokazuje, jak to zrobić za pomocą procedury zwanej w głosowaniu federalnym.
Dla niecierpliwych
W pozostałej części artykułu bardziej szczegółowo opisano głosowanie federacyjne i protokół konsensusu Stellar. Jeśli nie interesują Cię szczegóły, oto ogólny przegląd procesu.
- Węzły przeprowadzają rundy głosowania federalnego w sprawie „nominatów”. Federalna runda głosowania oznacza:
- Węzeł głosuje za jakąś instrukcją, np. „Proponuję wartość V”;
- Węzeł nasłuchuje głosów partnerów, dopóki nie znajdzie takiego, który może „odbierać”;
- Węzeł szuka „kworum” dla tego stwierdzenia. Kworum „potwierdza” kandydaturę.
- Gdy węzeł może potwierdzić jednego lub więcej kandydatów, próbuje „przygotować” „kartę do głosowania” w kilku rundach głosowania federacyjnego.
- Gdy węzeł jest w stanie sprawdzić, czy karta do głosowania jest gotowa, próbuje ją zatwierdzić w jeszcze większej liczbie rund głosowania stowarzyszonego.
- Gdy węzeł może potwierdzić zatwierdzenie karty do głosowania, może „uzewnętrznić” wartość tej karty do głosowania, wykorzystując ją jako wynik konsensusu.
Kroki te obejmują wiele rund stowarzyszonego głosowania, które łącznie tworzą jedną rundę SCP. Przyjrzyjmy się bliżej temu, co dzieje się na każdym kroku.
Głosowanie federacyjne
Głosowanie stowarzyszone to procedura określająca, czy sieć może zgodzić się 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ć, jeśli nie ma pewności, że inne węzły w sieci nie wybiorą innego wyniku. Aby się o tym przekonać, węzły wymieniają lawinę komunikatów tam i z powrotem, aby wszyscy mogli się połączyć potwierdzoneŻe kworum węzłów akceptuje To samo decyzja. W pozostałej części tej sekcji wyjaśniono terminy użyte w tym zdaniu oraz przebieg całej procedury.
Kwora i wycinki kworum
Zacznijmy od określenia kworum. Jak omówiliśmy powyżej, w zdecentralizowanej sieci z dynamicznym członkostwem nie można z góry określić liczby węzłów, a zatem ilu jest potrzebnych dla większości. Głosowanie federalne rozwiązuje ten problem, wprowadzając nowy pomysł kworum (wycinek kworum): mały zestaw elementów równorzędnych, którym węzeł ufa w zakresie przekazywania informacji o statusie głosowania reszcie sieci. Każdy węzeł definiuje swój własny wycinek kworum (którego de facto staje się członkiem).
Tworzenie kworum rozpoczyna się od zmniejszenia kworum. Do każdego węzła dodawane są węzły wycięte. Następnie dodawane są terminy plasterków te węzły i tak dalej. W miarę kontynuacji pojawia się coraz więcej węzłów, których nie można dodać, ponieważ są już uwzględnione w wycinku. Kiedy nie ma już więcej nowych węzłów do dodania, proces się zatrzymuje: utworzyliśmy kworum poprzez „przechodnie zamknięcie” wycinka kworum węzła początkowego.
Aby znaleźć kworum z danego węzła...
... dodaj elementy swojego kawałka...
...następnie dodajemy elementy wycinkowe tych węzłów.
Kontynuujemy, aż nie będzie już żadnych węzłów do dodania.
Nie ma już żadnych węzłów do dodania. To jest kworum.
W rzeczywistości każdy węzeł może pojawić się w więcej niż jednym plasterku. Aby utworzyć kworum, wybierz tylko jeden z wycinków i dodaj członków; następnie wybierz dowolny plasterek dla każdego elementu i dodaj elementy to ciąć i tak dalej. Oznacza to, że każdy węzeł jest członkiem wielu możliwych kworów.
Na każdym etapie wybierz tylko jeden wycinek kworum.
Jedno możliwe kworum. Lub alternatywa...
...wybierz inne plasterki...
…(kiedy to możliwe)…
... tworzy kolejne kworum.
Skąd węzeł wie, w których plasterkach znajdują się inne węzły? Podobnie jak inne informacje o innych węzłach: z transmisji, które każdy węzeł transmituje do sieci, gdy zmienia się jego stan głosowania. Każda emisja zawiera informacje o wycinkach węzła wysyłającego. Biała księga SCP nie określa mechanizmu komunikacji. Implementacje zazwyczaj używają dla gwarantowanej transmisji wiadomości w całej sieci.
Przypomnijmy, że w niefederalnym bizantyjskim systemie porozumień kworum definiuje się jako większość wszystkich węzłów. System porozumień bizantyjskich projektowany jest z punktu widzenia pytania: ile nieuczciwych węzłów może tolerować system? W systemie N węzłów zaprojektowanym tak, aby przetrwać f awarii, węzeł powinien móc robić postępy, otrzymując informację zwrotną od N-f równorzędnych węzłów, ponieważ f z nich może nie działać. Jednak otrzymawszy odpowiedź od równorzędnych partnerów N−f, możemy założyć, że wszyscy równorzędni f (od których węzeł nie otrzymał odpowiedzi) są faktycznie uczciwi. Zatem f z N−f peerów (od których otrzymano odpowiedź) jest złośliwych. Aby węzły osiągnęły ten sam konsensus, większość pozostałych węzłów musi być uczciwa, to znaczy potrzebujemy, aby N−f było większe niż 2f lub N > 3f. Zatem zazwyczaj system zaprojektowany tak, aby przetrwać f awarii, będzie miał łącznie N=3f+1 węzłów i wielkość kworum wynoszącą 2f+1. Gdy wniosek przekroczy próg kworum, reszta sieci jest przekonana, że jakiekolwiek konkurencyjne propozycje odniosą porażkę. W ten sposób sieć zbiega się do wyniku.
Ale w federalnym systemie porozumień bizantyjskich nie tylko nie może być większości (ponieważ nikt nie zna całkowitego 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 tzw. atak Sybil: wielokrotne podłączanie się do sieci na wielu węzłach. Dlaczego więc można nazwać przechodnie zamknięcie plasterka kworumi w jaki sposób jest w stanie stłumić konkurencyjne propozycje?
Technicznie nie ma mowy! Wyobraź sobie sieć sześciu węzłów, w której dwie trojaczki są odizolowane w swoich wycinkach kworum. Pierwsza podgrupa może podjąć decyzję, o której druga nigdy nie usłyszy i odwrotnie. Sieć ta nie ma możliwości osiągnięcia konsensusu (z wyjątkiem przypadku).
Dlatego też SCP wymaga, aby w przypadku głosowania federacyjnego (i aby ważne twierdzenia zawarte w artykule miały zastosowanie) sieć musiała posiadać właściwość zwaną przecięcie kworów. W sieci o tej właściwości dowolne dwa kwora, które można utworzyć, zawsze nakładają się na siebie w co najmniej jednym węźle. Aby określić dominujące nastroje w sieci, jest to tak samo dobre, jak posiadanie większości. Intuicyjnie oznacza to, że jeśli jakiekolwiek kworum zgodzi się na stwierdzenie X, żadne inne kworum nie będzie mogło zgodzić się na nic innego, ponieważ koniecznie będzie w nim znajdować się jakiś węzeł z pierwszego kworum, który już głosował na X.
Jeżeli w sieci występuje przecięcie kworów...
...wtedy dowolne dwa kwora, jakie możesz zbudować...
...zawsze będą się przecinać.
(Oczywiście nakładające się węzły mogą okazać się bizantyjskie lub w inny sposób złe. W tym przypadku przecięcie kworum w ogóle nie pomaga sieci w osiągnięciu porozumienia. Z tego powodu wiele wyników w białej księdze SCP opiera się na wyraźne założenia, takie jak to, co pozostanie po przekroczeniu kworum sieci nawet po usunięciu uszkodzonych węzłów. Dla uproszczenia zostawmy te założenia domniemany w dalszej części artykułu).
Oczekiwanie, że możliwe będzie niezawodne przekroczenie kworum w sieci niezależnych węzłów, może wydawać się nierozsądne. Ale są dwa powody, dla których tak się dzieje.
Pierwszym powodem jest istnienie samego Internetu. Internet jest doskonałym przykładem sieci niezależnych węzłów z przecinającymi się kworami. Większość węzłów w Internecie łączy się tylko z kilkoma innymi węzłami lokalnymi, ale te małe zestawy nakładają się na siebie na tyle, że do każdego węzła można dotrzeć z każdego innego węzła na jakiejś trasie.
Drugi powód jest specyficzny dla sieci płatniczej Stellar (najczęstsze zastosowanie SCP). Każdy zasób w sieci Stellar ma emitenta, a wytyczne Stellar wymagają od każdego emitenta wyznaczenia jednego lub więcej węzłów w sieci w celu przetwarzania żądań wykorzystania. W Twoim najlepszym interesie leży bezpośrednie lub pośrednie uwzględnienie tych węzłów w wycinkach kworum dla każdego zasobu, który Cię interesuje. Kwora dla wszystkich węzłów zainteresowanych danym zasobem będą wówczas nakładać się przynajmniej w tych węzłach umorzenia. Węzły zainteresowane wieloma aktywami uwzględnią wszystkie węzły umorzenia odpowiednich emitentów w swoich wycinkach kworum i będą dążyć do połączenia wszystkich aktywów w jedną całość. Ponadto wszelkie zasoby, które nie są połączone w ten sposób z innymi w sieci, oraz nie należy łączyć - jest to zaprojektowane tak, aby w tej sieci nie było nakładania się kworum (przykładowo banki ze strefy dolarowej czasami chcą handlować z bankami ze strefy euro i bankami ze strefy peso, więc są w tej samej sieci, ale nie ma z nich dba o wydzieloną sieć dzieci sprzedających karty baseballowe).
Oczywiście ожидание przekroczenie kworum nie jest gwarancja. Inne bizantyjskie systemy porozumień w dużej mierze zawdzięczają swoją złożoność gwarancji kworów. Ważną innowacją SCP jest to, że usuwa on odpowiedzialność za tworzenie kworów z samego algorytmu konsensusu i przenosi ją na poziom aplikacji. Zatem chociaż głosowanie federacyjne jest na tyle powszechne, że można głosować w dowolnej sprawie, jego wiarygodność w rzeczywistości zależy w decydującym stopniu od szerszego znaczenia tych znaczeń. Niektóre hipotetyczne zastosowania mogą nie sprzyjać tworzeniu dobrze połączonych sieci tak jak inne.
Głosowanie, akceptacja i potwierdzenie
W rundzie głosowania stowarzyszonego węzeł opcjonalnie rozpoczyna głosowanie na pewną wartość V. Oznacza to rozgłaszanie do sieci komunikatu: „Jestem węzłem N, moje wycinki kworum to 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 tego nie zrobi.
W przypadku transmisji peer-to-peer każdy węzeł widzi, jak głosują pozostałe. Gdy węzeł zbierze wystarczającą liczbę tych komunikatów, może śledzić wycinki kworum i próbować znaleźć kwora. Jeżeli stwierdzi kworum równorzędnych członków, którzy również głosują na V, może przystąpić do głosowania przyjęcie V i wyślij do sieci tę nową wiadomość: „Jestem węzłem N, moje wycinki kworum to Q i akceptuję V”. Akceptacja zapewnia silniejszą gwarancję niż zwykłe głosowanie. Kiedy węzeł głosuje na V, nigdy nie może głosować na inne opcje. Ale jeśli węzeł zaakceptuje V, żaden węzeł w sieci nigdy nie zaakceptuje innej opcji (dowodzi tego twierdzenie 8 w oficjalnym dokumencie SCP).
Oczywiście istnieje duże prawdopodobieństwo, że nie będzie od razu kworum węzłów zgodnych z V. Pozostałe węzły mogą głosować na inne wartości. Istnieje jednak inny sposób, w jaki węzeł może przejść od prostego głosowania do akceptacji. N może przyjąć inną wartość dla W, nawet jeśli na nią nie głosował i nawet jeśli nie widzi dla niej kworum. Aby podjąć decyzję o zmianie swojego głosu, po prostu zobacz zestaw blokujący węzły, które zaakceptowały W. Zbiór blokujący to jeden węzeł z każdego z wycinków kworum N. Jak sama nazwa wskazuje, może blok jakiekolwiek inne znaczenie. Jeśli wszystkie węzły w takim zbiorze zaakceptują W, to (zgodnie z Twierdzeniem 8) nigdy nie będzie możliwe utworzenie kworum, które przyjmie inną wartość, a zatem N może bezpiecznie zaakceptować W.
Węzeł N z trzema wycinkami kworum.
BDF jest zbiorem blokującym dla N: zawiera jeden węzeł z każdego wycinka N.
BE jest także zbiorem blokującym dla N, ponieważ E pojawia się w dwóch wycinkach N.
Jednak grupa blokująca nie stanowi kworum. Zbyt łatwo byłoby oszukać węzeł N, aby przyjął żądaną wartość, gdyby wystarczyło zhakowanie tylko jednego węzła w każdym wycinku N. Dlatego zaakceptowanie wartości nie oznacza końca głosowania. Zamiast tego N musi potwierdzić wartość, to znaczy zobaczyć, że kworum węzłów ją akceptuje. Jeśli zajdzie tak daleko, to, jak dowodzi biała księga SCP (w Twierdzeniu 11), reszta sieci również ostatecznie potwierdzi tę samą wartość, więc N zakończy głosowanie federacyjne z określoną wartością jako wynikiem.
Głosowanie federacyjne.
Proces głosowania, akceptacji i potwierdzenia stanowi jedną pełną rundę głosowania stowarzyszonego. Protokół konsensusu Stellar łączy wiele z tych rund, tworząc kompletny system konsensusu.
Protokół Stellar Konsensusu
Dwie najważniejsze właściwości systemu konsensusu to: - bezpieczeństwo и przeżywalność. Algorytm konsensusu jest „bezpieczny”, jeśli nigdy nie może dać różnych wyników różnym uczestnikom (kopia historii Boba nigdy nie będzie sprzeczna z Carol). „Żywotność” oznacza, że algorytm zawsze da wynik, to znaczy nie utknie.
Opisano federalną procedurę głosowania bezpieczna w tym sensie, że jeśli węzeł potwierdzi wartość V, żaden inny węzeł nie potwierdzi innej wartości. Ale „nie potwierdzi innego znaczenia” nie oznacza, że koniecznie coś potwierdzi. Uczestnicy mogą głosować na tak wiele różnych wartości, że nic nie osiągnie progu akceptacji. Oznacza to, że w głosowaniu federalnym nie ma przeżywalność.
Protokół konsensusu Stellar wykorzystuje głosowanie federacyjne w sposób zapewniający zarówno bezpieczeństwo, jak i przeżywalność. (Gwarancje bezpieczeństwa i przetrwania SCP mają teoretyczne granice. W projekcie wybrano bardzo silną gwarancję bezpieczeństwa, poświęcając niewielkie ograniczenie przeżywalności, ale przy wystarczającej ilości czasu istnieje duże prawdopodobieństwo osiągnięcia konsensusu.) W skrócie, pomysł polega na tym, aby mieć wiele federacyjnych głosów na wiele wartości, dopóki jedna z nich nie przejdzie przez wszystkie fazy głosowania SCP opisane poniżej.
Wartościami, co do których SCP szuka konsensusu, może być historia transakcji, zamówienie na lunch lub coś innego, ale należy pamiętać, że nie są to wartości akceptowane ani potwierdzane. Zamiast tego głosowanie federalne odbywa się zgodnie z wypowiedzi na temat tych wartości.
Odbywają się pierwsze tury głosowania federalnego etap nominacji (faza nominacji), na zestawie stwierdzeń takich jak „Nominuję V”, być może dla wielu różnych wartości V. Celem nominacji jest znalezienie jednego lub więcej stwierdzeń, które przechodzą akceptację i potwierdzenie.
Po znalezieniu możliwych do sprawdzenia kandydatów, SCP przechodzi do fazy głosowania, której celem jest znalezienie konkretnego biuletyn (czyli kontener na proponowaną wartość) i kworum, które można zadeklarować popełniać za to (popełnić). Jeżeli w głosowaniu zostanie stwierdzone kworum, jego wartość zostaje przyjęta jako konsensus. Zanim jednak węzeł będzie mógł głosować nad zatwierdzeniem głosowania, musi najpierw potwierdzić anulowanie wszystkie karty do głosowania z niższą wartością licznika. Kroki te — anulowanie kart do głosowania w celu znalezienia takiej, którą można zatwierdzić — obejmują wiele rund stowarzyszonego głosowania w sprawie wielu roszczeń dotyczących kart do głosowania.
W poniższych sekcjach opisano bardziej szczegółowo nominację i głosowanie.
Nominacja
Na początku fazy nominacji każdy węzeł może spontanicznie wybrać wartość V i oddać głos na stwierdzenie „Nominuję V”. Celem na tym etapie jest potwierdzenie nominacji o określonej wartości w drodze głosowania federacyjnego.
Być może wystarczająca liczba węzłów głosuje nad wystarczająco różnymi propozycjami, aby żadna nominacja nie mogła osiągnąć progu akceptacji. Dlatego też, oprócz transmitowania własnych głosów na nominacje, węzły „odzwierciedlają” nominacje swoich rówieśników. Echo oznacza, że jeśli węzeł głosuje na nominację V, ale zobaczy wiadomość od sąsiada głosującego na nominację W, będzie teraz głosował zarówno na V, jak i W. (Nie wszystkie głosy równorzędnych są powtarzane podczas nominacji, ponieważ może to prowadzić do eksplozji różnych nominowanych. SCP zawiera mechanizm regulujący te głosy. Krótko mówiąc, istnieje formuła określająca „priorytet" partnera z punktu widzenia węzła i uwzględniane są tylko głosy węzłów o wysokim priorytecie. Im dłuższa nominacja tym niższy próg, więc węzeł rozszerza zbiór równorzędnych partnerów, których głosy będzie odzwierciedlał.Formuła priorytetu uwzględnia numer szczeliny jako jedno z danych wejściowych, więc równorzędny element o wysokim priorytecie dla jednego gniazda może być równorzędnym elementem o niskim priorytecie inny i odwrotnie).
Koncepcyjnie nominacja jest równoległa, zarówno V, jak i W to oddzielne głosy federalne, z których każdy indywidualnie może uzyskać akceptację lub potwierdzenie. W praktyce komunikaty protokołu SCP łączą te poszczególne głosy razem.
Chociaż głosowanie na nominację V stanowi obietnicę, że nigdy nie będziemy głosować przeciwko nominacji V, to na poziomie wniosku – w tym przypadku SCP – ustala się, co oznacza „przeciw”. SCP nie widzi stwierdzenia sprzecznego z głosowaniem „Ja nominuję X”, to znaczy nie ma komunikatu „Jestem przeciwny nominowaniu X”, więc węzeł może głosować za wyznaczeniem dowolnych wartości. Wiele z tych nominacji prowadzi donikąd, ale ostatecznie węzeł będzie w stanie zaakceptować lub potwierdzić jedną lub więcej wartości. Gdy kandydat zostanie zatwierdzony, zostaje nim kandydat.
Nominacja SCP w drodze głosowania federacyjnego. Może być wiele wartości „B” zaproponowanych przez rówieśników i „odzwierciedlonych” przez węzeł.
Nominacje mogą skutkować wieloma potwierdzonymi kandydatami. Dlatego SCP wymaga, aby warstwa aplikacji zapewniała metodę łączenia kandydatów w jednego złożony (złożony). Metoda łączenia może być dowolna. Najważniejsze jest to, że jeśli ta metoda jest deterministyczna, wówczas każdy węzeł będzie łączyć tych samych kandydatów. W systemie głosowania przy obiedzie „zjednoczenie” może po prostu oznaczać odrzucenie jednego z dwóch kandydatów. (Ale w sposób deterministyczny: każdy węzeł musi wybrać tę samą wartość, aby zresetować. Na przykład wcześniejszy wybór w kolejności alfabetycznej). W sieci płatniczej Stellar, gdzie głosuje się nad historią transakcji, połączenie dwóch proponowanych nominacji polega na połączeniu zawartych w nich transakcji i najnowszego z ich dwóch znaczników czasu.
Biała księga SCP dowodzi (Twierdzenie 12), że pod koniec fazy rozbudowy sieć ostatecznie zbiega się w pojedynczy element złożony. Ale jest problem: głosowanie federacyjne jest protokołem asynchronicznym (jak SCP). Innymi słowy, węzły nie są koordynowane przez czas, ale jedynie przez wysyłane przez nie komunikaty. Z punktu widzenia węzła nie jest jasne, kiedy skończył faza przedłużenia. I chociaż wszystkie węzły ostatecznie dojdą do tego samego kompozytu, mogą po drodze obrać różne trasy, tworząc po drodze różnych kandydatów na kompozyt i nigdy nie będą w stanie stwierdzić, który z nich jest ostateczny.
Ale to normalne. Nominacja to tylko przygotowanie. Najważniejsze jest ograniczenie liczby kandydatów, aby osiągnąć konsensus, który następuje w procesie głosowanie (głosowanie).
Działanie
Biuletyn to para , gdzie licznik jest liczbą całkowitą zaczynającą się od 1, a wartość jest kandydatem z etapu nominacji. Może to być własny kandydat węzła lub kandydat sąsiedniego węzła zaakceptowany przez ten węzeł. Z grubsza rzecz ujmując, głosowanie obejmuje wielokrotne próby wymuszenia w sieci osiągnięcia konsensusu w sprawie jakiegoś kandydata w danej karcie do głosowania poprzez odbycie potencjalnie wielu głosów federacyjnych w sprawie oświadczeń dotyczących głosowania. Liczniki na kartach do głosowania śledzą podjęte próby, a karty do głosowania z większą liczbą głosów mają pierwszeństwo przed kartami do głosowania z mniejszą liczbą. Jeśli biuletyn utknie, rozpoczyna się nowe głosowanie, teraz na karcie do głosowania .
Ważne jest, aby odróżnić wartości (np. jaka powinna być kolejność lunchu: pizza czy sałatki), biuletyny (para przeciwwartości) i oświadczenia o kartach do głosowania. Runda SCP obejmuje kilka rund głosowania federalnego, w szczególności w sprawie następujących stwierdzeń:
- „Jestem gotowy do głosowania B” i
- „Ogłaszam zatwierdzenie karty do głosowania B”
Z punktu widzenia danego węzła konsensus zostaje osiągnięty, gdy znajdzie kartę do głosowania B, dla której może potwierdzić (czyli znaleźć kworum akceptujące) stwierdzenie „Popieram kartę do głosowania B”. Od tego momentu można bezpiecznie działać w oparciu o wartość określoną w B - na przykład składając to zamówienie na lunch. Nazywa się to eksternalizacja znaczenia. Po potwierdzeniu akceptacji głosowania węzeł może mieć pewność, że jakikolwiek inny węzeł przekazał tę samą wartość na zewnątrz lub zrobi to w przyszłości.
Chociaż wiele głosowań federacyjnych jest koncepcyjnie przeprowadzanych w oparciu o roszczenia dotyczące wielu różnych kart do głosowania, nie wymieniają one tak wielu komunikatów, ponieważ każdy komunikat zawiera pewną liczbę kart do głosowania. W ten sposób jedna wiadomość promuje stan wielu głosów federacyjnych na raz, na przykład: „Akceptuję karty do głosowania zatwierdzającego o wartości od zanim "
Co oznaczają terminy „przygotowany” i „zaangażowany”?
Węzeł głosuje za zatwierdzeniem karty do głosowania, gdy ma pewność, że inne węzły nie zatwierdzą kart do głosowania o innych wartościach. Przekonanie o tym jest celem przygotowania wniosku. Głos mówiący „Jestem gotowy oddać kartę B” jest obietnicą, że nigdy nie oddam karty do głosowania mniejszej niż B, czyli o mniejszej liczbie głosów (SCP wymaga, aby wartości na kartach do głosowania były w określonej kolejności. Tym samym newsletter mniej , jeśli N1
Dlaczego „Jestem gotowy oddać kartę do głosowania B” oznacza „Obiecuję, że nigdy nie oddam karty do głosowania mniejszej niż B”? Ponieważ SCP definiuje przerwanie jako przeciwieństwo zatwierdzenia. Głosowanie w sprawie przygotowania karty do głosowania wiąże się także z głosowaniem nad dyskwalifikacją niektórych innych kart do głosowania i, jak omawialiśmy wcześniej, głosowanie za jedną rzeczą oznacza obietnicę, że nigdy nie będziemy głosować przeciwko niej.
Przed rozesłaniem zatwierdzenia węzeł musi najpierw znaleźć biuletyn, który może potwierdzić jako przygotowany. Innymi słowy, przeprowadza wspólne głosowanie na temat „Jestem gotowy do głosowania B”, prawdopodobnie w wielu różnych kartach do głosowania, aż do znalezienia takiej, która uzna kworum.
Skąd pochodzą karty do głosowania służące do przygotowania głosowania? W pierwszej kolejności węzeł transmituje przygotowania do głosowania na <1,C>, gdzie C jest złożonym kandydatem powstałym na etapie nominacji. Jednak nawet po rozpoczęciu przygotowań do głosowania nominacje mogą skutkować pojawieniem się dodatkowych kandydatów jako nowych kart do głosowania. Tymczasem równorzędni mogą mieć różnych kandydatów i mogą utworzyć zestaw blokujący, który akceptuje „Jestem gotowy zatwierdzić głosowanie B2”, co przekona węzeł, aby również to zaakceptował. Wreszcie istnieje mechanizm przekroczenia limitu czasu, który generuje nowe rundy głosowania federacyjnego na nowych kartach do głosowania z większą liczbą głosów, jeśli bieżące karty do głosowania są zablokowane.
Gdy tylko węzeł znajdzie kartę do głosowania B, którą może potwierdzić jako przygotowaną, wysyła nowy komunikat „Zatwierdź kartę do głosowania B”. To głosowanie mówi innym, że węzeł nigdy nie zrezygnuje z B. W rzeczywistości, jeśli B jest kartą do głosowania , a następnie „Zatwierdź kartę do głosowania " oznacza bezwarunkową zgodę na oddanie głosu pod kątem gotowości każdej karty do głosowania do <∞, s>. Ta dodatkowa wartość pomaga innym uczestnikom dogonić partnera zatwierdzającego, jeśli nadal znajdują się na wcześniejszych etapach protokołu.
Na tym etapie warto jeszcze raz podkreślić, że są to protokoły asynchroniczne. To, że jeden węzeł wysyła głosy za zatwierdzeniem, nie oznacza, że jego koledzy też to robią. Niektórzy z nich mogą nadal głosować nad oświadczeniami w ramach przygotowań do głosowania, inni mogli już uzewnętrznić ich znaczenie. SCP wyjaśnia, w jaki sposób węzeł powinien przetwarzać każdy typ wiadomości równorzędnej, niezależnie od jej fazy.
Jeśli pojawi się komunikat „Ogłosiłem zatwierdzenie » nie można odebrać ani potwierdzić, czyli prawdopodobieństwo przyjęcia lub potwierdzenia wiadomości Lub - lub w każdym razie dowolną kartę do głosowania o wartości C, a nie inną, ponieważ węzeł już obiecał, że nigdy nie będzie anulowany . Do czasu, gdy węzeł rozgłosi głosy za zatwierdzeniem, będzie to C lub nic, w zależności od tego, jak daleko sięga konsensus. Jednak to jeszcze nie wystarczy, aby węzeł uzewnętrznił C. Niektórzy bizantyjscy równorzędni (którzy stanowią mniej niż kworum, w oparciu o nasze założenia dotyczące bezpieczeństwa) mogą okłamywać węzeł. Zaakceptowanie, a następnie potwierdzenie pewnej karty do głosowania (lub zakresu kart do głosowania) daje węzłowi pewność, że w końcu uzewnętrzni C.
Głosowanie SCP w drodze głosowania federacyjnego. Nie pokazano: licznik czasu może włączyć się w dowolnym momencie, zwiększając liczbę głosów na karcie do głosowania (i prawdopodobnie tworząc nowy zbiór dodatkowych nominowanych kandydatów).
I to wszystko! Gdy sieć osiągnie konsensus, jest gotowa robić to wielokrotnie. W sieci płatniczej Stellar dzieje się to mniej więcej raz na 5 sekund: jest to wyczyn wymagający zarówno bezpieczeństwa, jak i trwałości gwarantowanej przez SCP.
SCP może to osiągnąć, opierając się na wielu rundach głosowania federacyjnego. Głosowanie stowarzyszone jest możliwe dzięki koncepcji wycinków kworum: zestawów elementów równorzędnych, którym każdy węzeł zdecydował się zaufać w ramach swojego (subiektywnego) kworum. Taka konfiguracja oznacza, że konsensus można osiągnąć nawet w sieci o otwartym członkostwie i bizantyjskich oszustwach.
Dalsza lektura
- Można znaleźć oryginalną białą księgę SCP I projekt specyfikacji jego wdrożenia.
- Oryginalny autor protokołu SCP, David Mazier, wyjaśnia to w uproszczony (ale wciąż techniczny) sposób. .
- Być może byłeś zaskoczony, że w tym artykule nie znalazłeś terminów „wydobywanie” ani „dowód pracy”. SCP nie używa tych metod, ale niektóre inne algorytmy konsensusu tak. Zane Witherspoon napisał przystępny .
- prosta sieć, która osiąga konsensus w ciągu jednej pełnej rundy SCP.
- Dla czytelników zainteresowanych wdrożeniami SCP: zob , wykorzystywane przez sieć płatniczą Stellar, lub , który napisałem dla lepszego zrozumienia SCP.
Źródło: www.habr.com