Wybór lidera z losowych sygnałów nawigacyjnych i innych strategii

Wybór lidera w układzie blockchain ma na celu wybranie uczestnika, który określi następny blok, który ma zostać dołączony do łańcucha bloków. Zazwyczaj jeden walidator jest wybierany na slot ze zbioru walidatorów i otrzymuje prawo do przedłużenia łańcucha o nowy blok w tym gnieździe. (Zakładamy, że walidatorzy dotrzymują dokładnego czasu i zgadzają się co do aktualnego numeru slotu.) W tym artykule badamy strategie dla losowe wybory lidera w protokołach konsensusu. (Aby uzyskać więcej informacji na temat losowości, zobacz nasz wcześniejszy artykuł, Publiczne losowość i sygnalizatory losowości, Gdzie przyjrzeliśmy się niezależnym protokołom do generowania publicznie weryfikowalnej i nieprzewidywalnej losowości). 

Dlaczego wybór lidera ma znaczenie

Wybór uczciwych i aktywnych liderów ma kluczowe znaczenie dla zdrowego rozwoju sieci. Złośliwi walidatorzy nie powinni być w stanie wpływać na proces wyboru lidera, aby częściej stawać się liderami. W przeciwnym razie produkcja bloków może wpaść w ręce stron, które mogą cenzurować transakcje lub całkowicie zatrzymać blockchain. W protokołach konsensusu w stylu najdłuższego łańcucha lider tworzący nieprawidłowy blok (lub w ogóle nie blokujący) może spowodować tymczasowe rozwidlenie łańcucha. W protokołach konsensusu w stylu BFT zły lider uruchamia podprotokół zmiany widoku, który spowoduje narzut komunikacyjny. 

Alternatywa wyborów komitetowych

Powiązanym problemem jest wybór komitetu, w którym celem jest wybranie równomiernie losowego podzbioru walidatorów o określonej wielkości k. Ta funkcjonalność jest użyteczna sama w sobie, ponieważ podkomitety są często potrzebne w ustawieniach blockchain, aby zmniejszyć rozmiar zestawu walidatorów, aby przyspieszyć konsensus (wśród wielu przykładów są Sortowanie algorytmu i Wybór komitetu Ethereum). Ale wybór komitetu jest również przydatny w przypadku wyboru lidera, pozwalając weryfikatorom uniknąć ponownego przeprowadzenia protokołu wyboru lidera, jeśli wybrany lider się nie pojawi. Jeśli zamiast lidera zostanie wybrany komitet ze stałą kolejnością, drugi członek komitetu może zostać liderem, jeśli pierwszy nie jest dostępny. 

Właściwości dobrego protokołu wyborczego

W protokole wyboru lidera przywódcy powinni być nieprzewidywalni. Jeśli atakujący dowie się, kto jest nadchodzącym liderem, może przeprowadzić na niego atak typu „odmowa usługi” (DoS), aby uniemożliwić mu opublikowanie blokady. Atakujący może następnie obalić kolejnego lidera i tak dalej, zatrzymując łańcuch bloków. Nieprzewidywalność można również wzmocnić, aby upewnić się, że sam walidator nie nauczy się, kiedy będzie przewodzić, co może być ważne dla zapobiegania przekupstwu.

Proces wyboru lidera powinien mieć następujące trzy właściwości:

• Uczciwość: każdy uczciwy walidator ma prawdopodobieństwo 1/N być wybieranym ze zbioru N walidatory (zrelaksowane pojęcie dopuszcza uczciwość teorii gier budowanie wyborów lidera nawet w obecności złośliwej większości, choć z niestałą dolną granicą liczby rund).
• Nieprzewidywalność: przeciwnik poznaje następnego lidera dopiero po pewnym czasie T przed ogłoszeniem przez prowadzącego kolejnego bloku.
• Wyjątkowość: w każdym miejscu wybierany jest dokładnie jeden lider.

Tajne wybory lidera

Tajne wybory lidera to wybory nieprzewidywalne T = 0. W tym procesie lider nie jest nikomu znany, dopóki nie opublikuje bloku. Eliminuje to całkowicie okno na atak DoS: zanim lider się ujawni, atakujący nie wie, kogo zaatakować, a jego najlepsza strategia jest przypadkowa. A po tym, jak lider opublikuje swój blok, jest już za późno na atak, ponieważ lider wypełnił już swoją odpowiedzialność wobec protokołu. 

Pojęcie „po tym, jak lider opublikuje swój blok” jest w rzeczywistości uproszczeniem, ponieważ w prawdziwym świecie nie mamy natychmiastowej transmisji. Osoba atakująca z silną pozycją w sieci może zauważyć lidera, który jako pierwszy rozgłasza blok, i być w stanie szybko zepsuć lidera, utworzyć inny blok i przeforsować pierwotną transmisję. 

Chociaż jest to bardzo silny model atakującego, zaproponowano mechanizmy obronne przeciwko niemu. Algorand zaproponował tzw model wymazywania, w którym prowadzący faktycznie jest w stanie wymazać klucz niezbędny do podpisania bloku w swoim gnieździe zanim transmitując to, więc naprawdę jest już za późno na atak, zanim przywódca podejmie jakiekolwiek działania publiczne. Thaddeus Dryja, Quanquan C. Liu i Neha Narula, trzej badacze z MIT Media Lab, zaproponowane aby lider obliczył VDF na swoim bloku przed rozgłoszeniem, zapewniając, że adaptacyjny atakujący nie może zbudować alternatywnego prawidłowego bloku na czas, aby został zaakceptowany dla żądanego gniazda.

Inne metody wyborcze 

Najprostszym procesem wyboru lidera jest okrężne, gdzie przywódcy są wybierani w porządku deterministycznym. Pomimo tego, że podejście to jest przewidywalne, a tym samym podatne na ataki DoS, jest odpowiednie dla systemów z uprawnieniami, w których walidatory mają dobrą ochronę DoS.

Lidera można również wybrać za pomocą wyjścia zewnętrznego latarnia losowa, jeśli jest dostępny i uznany za bezpieczny. Niestety, uczestnikom konsensusu trudno jest samodzielnie uruchomić protokół rozproszonego sygnału nawigacyjnego losowości (DRB), ponieważ zazwyczaj zakładają one pojęcie niezawodnej transmisji lub konsensusu, co z kolei wymaga ponownego wyboru lidera, wprowadzając zależność cykliczną.

Aktualny Wybory lidera w Ethereum jest dobrym studium przypadku. Każdy nowy lider oblicza wynik funkcji weryfikowalnej losowości (VRF) (podpis BLS na numerze epoki) i XOR-uje ​​wartość w miksie. Wartość mieszanki pod koniec epoki i określa przywódców i podkomisje na czas trwania epoki i+2. Liderzy i ich harmonogram są przewidywalni na jedną epokę do przodu (obecnie ~6.4 min). Protokół jest podatny na ataki na sprawiedliwość, ponieważ ostatni lider może zdecydować się na opublikowanie lub wstrzymanie swojego udziału w miksie i tym samym wpłynąć na wynik kolejnych wyborów o jeden bit. Jeśli ostatni  k przywódcy zmawiają się, mogą wprowadzić k  fragmenty stronniczości i zwiększają prawdopodobieństwo wyboru złośliwych użytkowników. Fundacja Ethereum aktywnie pracuje nad bardziej zaawansowanymi technikami wyboru lidera, które omawiamy poniżej.

Wybory lidera oparte na VRF

Inne podejście, zapoczątkowane przez Algorand, Jest Wybory lidera oparte na VRF, co obejmuje każdy walidator prywatnie obliczający wyjście VRF i sprawdzający, czy wyjście spada poniżej progu. Ta procedura już odfiltrowuje większość walidatorów, ponieważ próg jest tak dobrany, że spadek poniżej niego jest mało prawdopodobny. Kilku pozostałych walidatorów ujawnia swoje wyniki VRF i wybierany jest ten, który ma najniższą wartość VRF. Takie podejście pozwala osiągnąć idealną nieprzewidywalność (lub tajemniczość), ale nie gwarantuje wyjątkowości. Niektórzy walidatorzy mogą nie otrzymywać wiadomości od wszystkich potencjalnych liderów i mogą założyć, że wybory wygrał niewłaściwy lider, co spowoduje, że walidatorzy odejdą od głównego łańcucha. 

Ocena VRF jest okresowo zaszczepiana sygnałem wyjściowym losowości, aby sami walidatorzy byli mniej przewidywalni, aby zobaczyć, które sloty będą prowadzić. Ta właściwość uniemożliwia atakującemu, który po cichu skompromituje walidator, nauczenie się gniazda, gdy walidator zostałby liderem, i rozpoczęcie ataku, gdy walidator ma ogłosić blok. Takie podejście pomaga również zapobiegać atakom korupcyjnym, w których walidator udowadnia podmiotom zewnętrznym, że będzie liderem w określonym slocie i zbiera łapówki w zamian za wykonanie jakiegoś zadania jako lider (np. zablokowanie transakcji).

Takie podejście, w którym liczba wybieranych liderów jest zmienną losową, nazywa się Probabilistyczne wybory lidera (PL). PLE może spowodować, że żaden lider nie zostanie wybrany na dane miejsce. Jest to równoznaczne z wyborem lidera, który jest złośliwy lub offline, ponieważ miejsce ostatecznie zostanie pominięte, zmniejszając wydajność protokołu konsensusu.

Ale największym zastrzeżeniem PLE jest to, że może zostać wybranych wielu przywódców, co wymaga jakiejś procedury rozstrzygania remisów. Powiązania stanowią zagrożenie dla konsensusu, ponieważ walidator ze zwycięskim wkładem może zgłosić to tylko połowie sieci, potencjalnie powodując niezgodę u wybranego lidera. Ponadto procesy rozwiązywania powiązań mogą wymagać dodatkowego czasu i komunikacji, co szkodzi wydajności. Dfinity, omówione bardziej szczegółowo w pierwszy post z tej serii wykorzystuje radiolatarnię losowości opartą na VRF, aby wybrać jednego lidera; jednak poświęca nieprzewidywalność, aby to zrobić. Idealnie, każdy proces wyboru lidera powinien całkowicie unikać więzi i nadal być nieprzewidywalny, co prowadzi nas do świętego Graala tego obszaru badawczego – Single Secret Leader Election.

Wybory pojedynczego tajnego lidera 

Celem Wybory pojedynczego tajnego lidera (SSLE) polega na wybraniu unikalnego lidera z zestawu walidatorów przy zachowaniu uczciwości i nieprzewidywalności. Protocol Labs przedstawiło to pojęcie jako problem badawczyoraz Dan Boneh, informatyk ze Stanford i doradca ds. badań kryptograficznych a16z, wraz z Sabą Eskandarian, Lucjanem Hanzlikiem i Nicolą Greco, zaproponowali później formalna definicja SSLE. Ta właściwość unikalności pozwala uniknąć ryzyka konsensusu i kosztów wydajności wynikających z procedur rozstrzygania sporów. Konkretnie, Sarah Azouvi z Protocol Labs i Danielle Cappelletti z Politecnico di Torino, pokazać że gdy SSLE jest używany w porównaniu z PLE w protokole o najdłuższym łańcuchu, bloki mogą być finalizowane znacznie szybciej (25 procent szybciej, gdy przeciwnik kontroluje jedną trzecią stawki). Dlatego opracowanie praktycznego protokołu SSLE jest ważnym problemem.

W najczęstszym podejściu, które nazwiemy oparte na losowaniu (używany zarówno w oryginalnym dokumencie SSLE, jak i propozycja Ethereum SSLE), każdy walidator rejestruje a nuncjusz które wygląda na przypadkowe, ale które mogą udowodnić, należy do nich. Nonces są następnie kompilowane w listę. Lista jest tasowana w taki sposób, że nonces zostają odłączone od walidatorów, którzy je przesłali; to znaczy, biorąc pod uwagę przetasowaną listę, żaden przeciwnik nie może powiedzieć, który walidator przesłał który identyfikator jednorazowy. Indeks listy jest następnie wybierany zgodnie z publicznością latarnia losowa, a lider ujawnia się, udowadniając, że nonce w tym indeksie przetasowanej listy należy do niego. 

Ponieważ wybrany jest tylko jeden indeks, protokół oparty na losowaniu zawsze generuje a wyjątkowy lider. Ponieważ losowy sygnał nawigacyjny jest zbudowany tak, aby generować równomiernie losowe wartości, protokół również sprawiedliwy: każdy walidator ma równe szanse na bycie wybranym. Ponadto, jeśli tasowanie jest wykonywane prawidłowo (tj. jednolicie losowo) i nonces stają się niemożliwe do powiązania z tożsamościami walidatorów, ten protokół również osiąga nieprzewidywalność.

Tasowanie jest konieczne, ponieważ po prostu wybranie indeksu z nietasowanej listy opartej na losowym sygnale nawigacyjnym już zapewniłoby wyjątkowość i rzetelność, nieprzewidywalność jest trudniejsza do osiągnięcia: jeśli przeciwnik wie, który walidator przesłał który identyfikator jednorazowy, wie też, kto przesłał identyfikator jednorazowy w wybranym indeks i może zidentyfikować lidera. 

Poniższe dwa podejścia przetasowują listę na różne sposoby. Prostszy jest tzw Propozycja SSLE Ethereum, w którym n walidatorzy przesyłają swoje identyfikatory jednorazowe za pośrednictwem Tora, aby odłączyć tożsamości walidatorów od ich identyfikatorów jednorazowych. Gdy wszyscy walidatorzy się zarejestrują, lista jest tasowana przy użyciu publicznego sygnału nawigacyjnego losowości, a walidatorzy stają się liderami w kolejności przetasowanej listy. Chociaż ten schemat jest praktyczny - wybory muszą być przeprowadzane tylko raz na n sloty – ta zależność od Tora może być niepożądana (podobnie jak poleganie na bezpieczeństwie jakiegokolwiek zewnętrznego protokołu). Co więcej, nie jest całkowicie nieprzewidywalny: po pierwszym n-1 przywódcy ujawniają się, finał nth znany jest lider.

Zamiast używać Tora, oryginalny dokument SSLE ma rejestr każdego walidatora do wyboru po kolei, dodając swój nonce do listy, tasując listę i ponowne losowanie nonces. Ta ponowna randomizacja oznacza, że ​​każdy identyfikator jednorazowy jest mapowany na nowy, niemożliwy do połączenia ciąg, tak że walidator, do którego należy, może nadal udowodnić własność ponownie losowego identyfikatora jednorazowego. Ponowna losowość sprawia, że ​​przeciwnik nie może powiedzieć, na której pozycji znalazł się dany nonce po tasowaniu, zakładając, że przynajmniej jeden tasujący jest uczciwy.

Chociaż to podejście do sekwencyjnego tasowania z oryginalnego dokumentu SSLE pozwala uniknąć polegania na Torze i osiąga formalne właściwości SSLE, jest kosztowne: za każdym razem, gdy rejestruje się nowy walidator, musi opublikować całą przetasowaną listę w łańcuchu bloków, ponownie losować wszystkie nonces i przedstawić dowód, że zrobili to uczciwie, co skutkuje liniową ilością komunikacji na walidatora. W przypadku niezmiennego zestawu walidatorów należy to zrobić (zamortyzować) raz na wybory, ponieważ lider ponownie rejestruje się po ujawnieniu dowodu na nonce. W artykule przedstawiono kompromis między wydajnością a przewidywalnością: zamiast tego możemy przetasować tylko mniejszy podzbiór listy, zmniejszając koszty, jeśli chcemy pozwolić na niewielką przewidywalność. Osiągnięcie właściwej równowagi między wydajnością a bezpieczeństwem jest trudne, w związku z czym protokoły SSLE nie są jeszcze szeroko stosowane w praktyce. 

Dogodnie, to podejście sekwencyjnego tasowania może być również wykorzystane do rozwiązania problemu wyboru komitetu, używając losowego sygnału nawigacyjnego do wybrania k różnych indeksów z listy jako członków komitetu. To miłe osiągnięcie, ponieważ problem nie jest trywialnie rozwiązany przez podejście oparte na VRF, ponieważ uruchomienie probabilistycznego protokołu opartego na VRF k razy mogą wybrać komitet o różnej wielkości w zależności od losowości. 

Inne podejścia do SSLE

Innym podejściem opartym na losowaniu jest Adaptacyjnie zabezpiecz SSLE od DDH. Ta konstrukcja jest nieco bardziej skomplikowana, ale zapewnia silniejsze poczucie bezpieczeństwa, chroniąc przed adaptacyjny przeciwnik w modelu wymazań Algoranda. Ten przeciwnik jest adaptacyjny, ponieważ może wybrać, które walidatory mają zostać uszkodzone podczas protokołu, a nie przed rozpoczęciem protokołu. 

Kolejnym wyzwaniem w SSLE jest wybór każdego walidatora z prawdopodobieństwem proporcjonalnym do jego stawki, a nie jednolicie losowo. Protokoły oparte na tasowaniu mogą naiwnie to osiągnąć, pozwalając każdemu walidatorowi na zarejestrowanie wielu jednorazowych punktów: jeden jednorazowy na każdą posiadaną jednostkę stawki. Jednak koszt tasowania rośnie liniowo wraz z liczbą jednostek stawki S, stając się bardzo kosztowna nawet przy realistycznym podziale stawek. elegancki SSLE oparty na MPC podejście ma złożoność rosnącą tylko z log S, a także pozwala uniknąć zaufanej konfiguracji lub sygnału nawigacyjnego losowości. Jednak w porównaniu z podejściami opartymi na tasowaniu wymaga większej liczby rund komunikacji (logarytmicznej liczby uczestników) na wybranego lidera

***

Podsumowaliśmy naszą analizę w tej przydatnej tabeli.

	Uczciwość	nieprzewidywalność/ Tajność*	Wyjątkowość
Okrągły	✓	✗	✓
Idealna losowość-latarnia	✓	✗	✓
Wybór lidera Ethereum (aktualny)	✗	✗	✓
Wybory lidera oparte na VRF (Algorand)	✓	✓	✗
SSLE	✓	✓	✓

* Latarnia okrężna jest w pełni przewidywalna, ale w pozostałych latarniach ✗ oznacza, że ​​pojęcie jest osiągnięte do pewnego ograniczonego stopnia: latarnia o idealnej losowości jest nieprzewidywalna, ale przeciwnik poznaje wyjście w tym samym czasie z wybranym liderem, stąd wybrany lider może zostać zaatakowany, zanim ogłosi blok; Sygnał nawigacyjny Etherum jest nieprzewidywalny do około 6 minut i może być lekko stronniczy, aby zaszkodzić uczciwości; Algorand wybiera wielu przywódców z małym prawdopodobieństwem.

SSLE to obiecujący kierunek, osiągający rzetelność, nieprzewidywalność i wyjątkowość. Dwa główne wyzwania stojące przed jego przyjęciem to wydajność i zdolność do uwzględnienia nierównomiernego rozkładu udziałów. Co więcej, podejścia SSLE oparte na losowaniu, które podkreślamy, zakładają istnienie bezstronnego losowego sygnału nawigacyjnego, co w praktyce nie jest łatwe do osiągnięcia. Ponieważ protokół SSLE został niedawno formalnie zdefiniowany, prawdopodobnie w niedalekiej przyszłości zobaczymy ulepszone protokoły odpowiadające na jego wyzwania. 

***

Miranda Chryste jest doktorantką informatyki na Uniwersytecie Columbia, gdzie jest członkiem Theory Group i Presidential Fellow. Jest także stażystką naukową w a16z crypto.

Józefa Bonneau jest partnerem badawczym w krypto a16z. Jego badania koncentrują się na kryptografii stosowanej i bezpieczeństwie blockchain. Prowadził kursy kryptowaluty na University of Melbourne, NYU, Stanford i Princeton, a także uzyskał tytuł doktora informatyki na Uniwersytecie w Cambridge oraz stopień BS/MS na Stanford.

Waleria Nikołaenko jest partnerem badawczym w krypto a16z. Jej badania koncentrują się na kryptografii i bezpieczeństwie blockchain. Zajmowała się również takimi tematami, jak ataki dalekiego zasięgu w protokołach konsensusu PoS, schematy sygnatur, bezpieczeństwo post-kwantowe i obliczenia wielostronne. Uzyskała doktorat z kryptografii na Uniwersytecie Stanforda pod kierunkiem profesora Dana Boneha i pracowała nad blockchainem Diem w ramach głównego zespołu badawczego.

***

Redaktor: Tim Sullivan

***

Wyrażone tutaj poglądy są poglądami poszczególnych cytowanych pracowników AH Capital Management, LLC („a16z”) i nie są poglądami a16z ani jej podmiotów stowarzyszonych. Niektóre informacje w nim zawarte zostały pozyskane ze źródeł zewnętrznych, w tym od spółek portfelowych funduszy zarządzanych przez a16z. Chociaż pochodzi ze źródeł uważanych za wiarygodne, a16z nie zweryfikowała niezależnie takich informacji i nie składa żadnych oświadczeń dotyczących trwałej dokładności informacji lub ich adekwatności w danej sytuacji. Ponadto treści te mogą zawierać reklamy osób trzecich; a16z nie przeglądał takich reklam i nie popiera żadnych zawartych w nich treści reklamowych.

Te treści są udostępniane wyłącznie w celach informacyjnych i nie należy ich traktować jako porady prawnej, biznesowej, inwestycyjnej lub podatkowej. Powinieneś skonsultować się w tych sprawach z własnymi doradcami. Odniesienia do jakichkolwiek papierów wartościowych lub aktywów cyfrowych służą wyłącznie celom ilustracyjnym i nie stanowią rekomendacji inwestycyjnej ani oferty świadczenia usług doradztwa inwestycyjnego. Ponadto treść ta nie jest skierowana ani przeznaczona do użytku przez jakichkolwiek inwestorów lub potencjalnych inwestorów iw żadnym wypadku nie można na nich polegać przy podejmowaniu decyzji o zainwestowaniu w jakikolwiek fundusz zarządzany przez a16z. (Oferta inwestycji w fundusz a16z zostanie złożona wyłącznie na podstawie memorandum dotyczącego oferty prywatnej, umowy subskrypcyjnej i innej odpowiedniej dokumentacji takiego funduszu i należy ją przeczytać w całości.) Wszelkie inwestycje lub spółki portfelowe wymienione, wymienione lub opisane nie są reprezentatywne dla wszystkich inwestycji w pojazdy zarządzane przez a16z i nie można zapewnić, że inwestycje będą opłacalne lub że inne inwestycje dokonane w przyszłości będą miały podobne cechy lub wyniki. Lista inwestycji dokonanych przez fundusze zarządzane przez Andreessena Horowitza (z wyłączeniem inwestycji, w przypadku których emitent nie wyraził zgody na publiczne ujawnienie przez a16z oraz niezapowiedzianych inwestycji w aktywa cyfrowe będące w obrocie publicznym) jest dostępna pod adresem https://a16z.com/investments /.

Wykresy i wykresy zamieszczone w niniejszym dokumencie służą wyłącznie celom informacyjnym i nie należy na nich polegać przy podejmowaniu jakichkolwiek decyzji inwestycyjnych. Wyniki osiągnięte w przeszłości nie wskazują na przyszłe wyniki. Treść mówi dopiero od wskazanej daty. Wszelkie prognozy, szacunki, prognozy, cele, perspektywy i/lub opinie wyrażone w tych materiałach mogą ulec zmianie bez powiadomienia i mogą się różnić lub być sprzeczne z opiniami wyrażanymi przez innych. Dodatkowe ważne informacje można znaleźć na stronie https://a16z.com/disclosures.