Publiczne losowość i sygnalizatory losowości

Losowość publiczna jest podstawowym składnikiem wielu rzeczywistych protokołów bezpieczeństwa. W niektórych aplikacjach, takich jak hazard i gry wieloosobowe, losowość dodaje frajdy. W innych zastosowaniach losowość zapewnia sprawiedliwy sposób przydzielania niepodzielnych zasobów, począwszy od zielonych kart, przez przydzielanie sędziów sądów okręgowych do spraw, aż po rozstawienie w turniejach sportowych. Służy również do przydzielania ujemny zasobów, takich jak kontrole podatkowe lub wtórna kontrola bezpieczeństwa na lotnisku.

Tradycyjnie polegaliśmy na zaufanych organach przy generowaniu losowości dla tych protokołów, ale w świecie web3 musimy działać lepiej. W tym poście omówimy podejścia do budowania publicznie weryfikowalnej losowości za pomocą rozproszone beacons losowości a następnie omów niektóre aplikacje w łańcuchu. (Część II, która nadchodzi, skoncentruje się w szczególności na wyborach liderów, zapewniając jednocześnie ocenę podejść do wyborów liderów zastępczych). 

Pożądane właściwości

Generowanie liczb losowych to niezwykle subtelne zadanie. Na przykład wiele kluczy kryptograficznych zostało ujawnionych, ponieważ: polegał na wadliwym generatorze liczb losowych (dla której ściana Cloudflare'a) lampy lawowe służyłoby jako kreatywne łagodzenie). To jest tylko prywatna przypadkowość, jednak tylko jedna strona musi je wygenerować i wykorzystać.

Natomiast losowość publiczna jest procesem wielostronnym, co znacznie zwiększa trudność. Dobry protokół do tworzenia losowości publicznej będzie miał następujące właściwości bezpieczeństwa:

• Bezstronny: Żaden napastnik ani koalicja atakujących nie powinna mieć możliwości zniekształcania wyników. 
• Niezawodność: Żaden atakujący nie powinien być w stanie uniemożliwić protokołowi generowania danych wyjściowych.
• Sprawdzalny: Każdy może łatwo zweryfikować dane wyjściowe protokołu i powinien widzieć te same dane wyjściowe, co wszyscy inni.
• Nieobliczalny: Jeśli protokół generuje dane wyjściowe w czasie T₁, nikt nie powinien być w stanie przewidzieć niczego na temat wyjścia przed upływem czasu T₀<T₁, najlepiej z T₀ bardzo blisko do T₁.

Nieobciążalność jest słabszą właściwością niż nieprzewidywalność, ponieważ każdy nieprzewidywalny protokół musi być nieobiektywny. Informatycy powiedzieliby, że bezstronność zmniejsza do nieprzewidywalności, ponieważ jeśli potrafisz stronniczość, możesz przewidzieć. Ale czasami będziemy chcieli rozumować o nich osobno, ponieważ mogą opierać się na różnych założeniach – na przykład nieuczciwa większość może przewidzieć wynik, ale nie będzie go stronniczyć.

Oprócz tych właściwości protokół powinien działać wydajnie i generować dużą liczbę losowych bitów. (W praktyce często wystarczy, aby aplikacje wytworzyły 128 losowych bitów, używając ich do zaszczepienia generatora liczb pseudolosowych [PNRG], aby wyprowadzić więcej bitów w razie potrzeby. Jednak nieprzewidywalność powinna utrzymywać się dla każdego pojedynczego bitu danych wyjściowych, aby można go było wykorzystać do takich aplikacje takie jak loterie lub alokacje zasobów). Protokół powinien również być w idealnym przypadku wydajny pod względem kosztów komunikacji i obliczeń.

Różne protokoły mogą osiągnąć te właściwości w różnych warunkach. Na przykład, niektóre protokoły mogą być nieobiektywne przez jakąkolwiek koalicję f₁ złośliwe węzły i nieprzewidywalne przez jakąkolwiek koalicję f₂<f₁ złośliwe węzły. Istnieją również różne stopnie uprzedzeń. Na przykład w niektórych protokołach uczestnik może być w stanie obciążyć dane wyjściowe o „jeden bit” – co oznacza, że ​​może wybrać jeden z dwóch możliwych wyników. Inne ataki mogą pozwolić im na całkowite naprawienie wyjścia. Zazwyczaj jednak nie chcemy w ogóle tolerować żadnych uprzedzeń (ani przewidywalności).

Ideał kryptograficzny: Rbeacons andomness

Kryptografowie często zaczynają od wymyślenia idealnego rozwiązania swoich problemów. W przypadku losowości publicznej a latarnia losowa to wyidealizowana usługa, która regularnie generuje losowe dane wyjściowe spełniające wszystkie niezbędne wymagania bezpieczeństwa.

Taki wyidealizowany beacon losowości, podobny do innych abstrakcji kryptograficznych – takich jak losowe wyrocznie czy generyczny model grupowy – nie istnieje w prawdziwym świecie. Ale jest to pożyteczny cel, do którego należy dążyć, i użyteczny model wnioskowania o protokołach, które opierają się na publicznej losowości. 

Możemy rozważyć kilka przybliżeń idealnego beaconu losowości.

• Scentralizowane sygnały nawigacyjne: Najłatwiejszym sposobem na wygenerowanie dobrej losowości jest skorzystanie ze scentralizowanej strony trzeciej z usługami takimi jak Sygnał losowości NIST or random.org, który generuje losowość z hałasu atmosferycznego i jest akredytowany do użytku w grach hazardowych. To poleganie na osobie trzeciej całkowicie podważa filozofię decentralizacji. Rzeczywiście, w powyższym przykładzie musimy ufać, że odpowiednie organizacje poprawnie generują losowość, bez żadnego dowodu kryptograficznego.
• Fizyczna losowość wyświetla: Wiele tradycyjnych loterii opiera się na publicznym pokazie, który może obejmować na przykład osobę sięgającą do pojemnika z piłeczkami pingpongowymi z różnymi liczbami. Niestety często można nimi łatwo manipulować. Na przykład, niektóre kulki można umieścić w zamrażarce i można powiedzieć selektorowi, aby wybrał te zimne.
• Naturalne latarnie morskie: Częstym pomysłem jest wykorzystanie losowych zjawisk naturalnych, takich jak pogoda lub kosmiczne promieniowanie tła, jako latarni. Niestety, wszystkie proponowane źródła nie zapewniają silnego konsensusu. Różni obserwatorzy zobaczą nieco inne wartości, co wymaga ponownego wprowadzenia zaufanej strony do przeprowadzenia oficjalnego pomiaru, ze wszystkimi wadami scentralizowanego sygnału nawigacyjnego.
• Częściowo scentralizowane beacony: Lepszym podejściem byłoby uzyskanie losowości z Nagłówki bloków Bitcoin bezpośrednio lub z ceny zamknięcia akcji, który jest łatwiejszy do publicznej weryfikacji i trudniejszy do całkowitej kontroli dla jednej ze stron. Jednak subtelne ataki wciąż istnieją na obu losowość blockchain dowodu pracy i losowość cen akcji. Na przykład w przypadku nagłówków łańcucha bloków górnicy mogą zdecydować się na wstrzymanie bloków, których nagłówki generują wartość sygnału nawigacyjnego, która im się nie podoba. Mogą też zdecydować się na zerwanie wiązań, gdy zostaną znalezione dwa kolidujące bloki na podstawie ich preferowanego sygnału wyjściowego.

Zdecentralizowane losowe sygnały nawigacyjne (DRB)

Naturalnym podejściem do problemów scentralizowanych sygnałów nawigacyjnych jest zaprojektowanie zdecentralizowanego protokołu kryptograficznego do generowania losowości publicznej. Ten problem przypomina projektowanie zdecentralizowanych protokołów konsensusu, tylko trudniej. Nie tylko wszyscy uczestnicy muszą zgodzić się na wynik (losowość), ale złośliwy uczestnik protokołu nie powinien mieć wpływu na wynik ani go przewidzieć.

Protokoły zaprojektowane do symulacji losowego sygnału nawigacyjnego nazywane są rozproszonymi sygnałami nawigacyjnymi losowości (DRB). (Inne nazwy to „rozproszone rzucanie monetą”). Problem był badany od dziesięcioleci, z słynne wyniki niemożliwości udowodnione w latach 1980., ale zainteresowanie ponownie wzrosło w erze blockchain. DRB można wykorzystać do zapewnienia losowości w łańcuchu, która byłaby kluczowym składnikiem sprawiedliwych, bezpiecznych i przejrzystych aplikacji w łańcuchu.

Klasyczne podejście: protokoły potwierdź-ujawnij

Bardzo prosty protokół z dwoma rundami wystarczy dla DRB w optymistycznym przypadku. W pierwszej rundzie każdy uczestnik i generuje losową wartość r_i i publikuje zobowiązanie kryptograficzne c_i=Popełniać(r_i). W tej aplikacji zobowiązanie może być po prostu funkcją skrótu, taką jak SHA-256. Po opublikowaniu zobowiązania każdego uczestnika, zostają oni zablokowani do wyboru r_i, ale zobowiązania nie ujawniają żadnych informacji o wkładach innych uczestników. W drugiej rundzie każdy uczestnik „otwiera swoje zobowiązanie” publikując r_i. Wszystkie losowe wartości są następnie łączone, na przykład przez ich XOR lub (najlepiej) hashowanie ich konkatenacji.

Ten protokół jest prosty i generuje losowy sygnał wyjściowy, o ile nawet jeden z uczestników wybierze swój r_i losowo. Niestety, ma on klasyczną wadę: kiedy wszyscy oprócz jednego z uczestników ujawnią swoją losową wartość, ostatni uczestnik jest w stanie obliczyć przypuszczalny sygnał wyjściowy sygnału nawigacyjnego. Jeśli im się to nie podoba, mogą odmówić opublikowania swojej wartości, przerywając protokół. Ignorowanie wkładu wadliwego uczestnika nie rozwiązuje problemu, ponieważ nadal daje to atakującemu wybór między dwoma wyjściami beaconów (jednym obliczonym z jego wkładem i jednym bez).

Blockchainy oferują naturalne rozwiązanie tego problemu: każdy uczestnik może zostać poproszony o umieszczenie pewnych środków w depozycie, które zostaną przejęte, jeśli nie ujawni swojego losowego wkładu. Takie właśnie podejście przyjął klasyk Randao beacon na Ethereum. Minusem tego podejścia jest to, że wyniki mogą być nadal nieobiektywne, co może być opłacalne finansowo dla atakującego, jeśli pieniądze w depozycie są mniejsze niż kwota pieniędzy związana z wynikiem beaconu. Lepsze zabezpieczenie przed atakami stronniczymi wymaga umieszczenia większej ilości monet w depozycie.

Protokoły typu „zatwierdź-ujawnij-odzyskaj”

Zamiast próbować zmusić wszystkie strony do ujawnienia swojego losowego wkładu, niektóre protokoły zawierają mechanizm odzyskiwania, dzięki czemu nawet jeśli mniejszość uczestników zrezygnuje, pozostali mogą ukończyć protokół. Ważne jest, aby protokół dawał ten sam wynik w obu przypadkach, aby strony nie mogły fałszować wyniku, decydując o rezygnacji lub nie.

Jednym ze sposobów osiągnięcia tego jest przekazanie każdemu uczestnikowi udostępnienia innym swojego sekretu, tak aby większość z nich mogła go odtworzyć, używając na przykład Dzielenie się sekretem Shamira. Ważną właściwością jest jednak to, że inni mogą zweryfikować, czy przekazany sekret został prawidłowo udostępniony, co wymaga użycia silniejszego prymitywu zwanego publicznie weryfikowalnym udostępnianiem sekretu (PVSS).

Możliwych jest kilka innych mechanizmów odzyskiwania, ale wszystkie mają to samo ograniczenie. Jeśli tam są N uczestników i chcemy odporności, jeśli jakakolwiek grupa do f węzłów odpada, to musi być tak, że jakakolwiek grupa Nf uczestnicy mogą obliczyć wynik końcowy. Ale oznacza to również złośliwą koalicję Nf uczestnicy mogą z wyprzedzeniem przewidzieć wynik, prywatnie symulując mechanizm odzyskiwania. Może się to również zdarzyć podczas pierwszej rundy protokołu, podczas której taka koalicja może modyfikować własne wybory losowości i fałszować wynik. 

Innymi słowy, oznacza to każdą koalicję Nf węzły muszą zawierać co najmniej jeden uczciwy węzeł. Za pomocą prostej algebry Nf > f, więc f < N/2, a protokoły te z natury wymagają uczciwej większości. Jest to znacząca różnica w stosunku do oryginalnego modelu zabezpieczeń commit-reveal, który wymaga jedynie f<N (przynajmniej jeden uczciwy uczestnik).

Protokoły te często wymagają również znacznych kosztów komunikacji, aby udostępnić dodatkowe informacje PVSS między wszystkimi węzłami w każdym przebiegu protokołu. Społeczność naukowa wykonała znaczną pracę nad tym problemem w ciągu ostatnich kilku lat, z propozycjami badawczymi obejmującymi: RandUdostępnij, Zeskrobać, SecRand, HERBlub Albatros, ale wydaje się, że żaden z nich nie widział rzeczywistego wdrożenia.

Weryfikowalne protokoły oparte na losowych funkcjach

Zdając sobie sprawę, że grupa Nf uczestnicy mogą obliczyć losową wartość sygnału nawigacyjnego w powyższym protokole, co prowadzi do nieco prostszego podejścia: udostępnij długoterminowy tajny klucz między N imprezach i poproś ich, aby wykorzystali je do oceny weryfikowalna funkcja losowa (VRF). Klucz tajny jest udostępniany przez a t-poza-N schemat progów, tak aby każdy t uczestnicy mogą obliczyć VRF (ale mniejsza koalicja nie). Do t=Nf, zapewnia to taką samą odporność na: f złośliwe węzły, takie jak protokoły commit-reveal-recover omówione powyżej.

DFINITY pionierem tego podejścia jako część ich protokołu konsensusu przy użyciu progowych podpisów BLS (które działają jako VRF). Samodzielny pić randomity beacon wykorzystuje zasadniczo to samo podejście, z zestawem uczestników z progiem-BLS-podpisującym licznik w każdej rundzie. The Liga Entropii to instancja typu open source drand produkująca losowość co 30 sekund przy użyciu 16 uczestniczących węzłów (stan na wrzesień 2022 r.), prowadzona przez mieszankę firm i uniwersyteckich grup badawczych. 

Wadą tych podejść jest to, że inicjowanie klucza progu jest stosunkowo złożone, podobnie jak rekonfiguracja klucza, gdy węzły dołączają lub odchodzą. Jednak w powszechnym przypadku protokoły są bardzo wydajne. 

Jak opisano powyżej, samo podpisanie wartości licznika nie dodaje żadnej nowej losowości na rundę, więc jeśli naruszona zostanie wystarczająca liczba kluczy uczestników, protokół będzie przewidywalny w każdej kolejnej rundzie.

Łańcuch VRF kombajny to podejście (przy użyciu NSEC5 VRF) z zewnętrznym źródłem losowości określonym przez strony żądające losowości, zazwyczaj w praktyce jest to niedawny nagłówek łańcucha bloków. Te dane są następnie przesyłane przez VRF, który jest obsługiwany przez jedną stronę lub progowany do grupy.

Ethereum Łańcuch nawigacyjny obecnie wykorzystuje VRF oparte na BLS: proponujący każdą rundę dodaje do miksu swoją wartość VRF. Oszczędza to rundę komunikacji w porównaniu z paradygmatem commit-reveal (zakładając, że długoterminowy klucz publiczny BLS jest rejestrowany raz), chociaż ten projekt dziedziczy pewne zastrzeżenia podejścia commit-reveal, w tym możliwość odchylenia wyjścia sygnału nawigacyjnego poprzez wstrzymanie danych wyjściowych .

Weryfikowalne protokoły oparte na funkcjach opóźnienia

Wreszcie, obiecującym nowym kierunkiem jest wykorzystanie kryptografii opartej na czasie, w szczególności weryfikowalnych funkcji opóźniających (VDF). Takie podejście obiecuje zapewnić dobrą wydajność komunikacji i solidność z odpornością na N-1 złośliwe węzły. 

Wracając do pierwotnego protokołu commit-reveal, tradycyjne zobowiązania można zastąpić zobowiązania czasowe aby wyeliminować problem uczestników odmawiających ujawnienia swojego losowego wkładu. Zobowiązania czasowe mogą być efektywnie otwierane przez pierwotnego zatwierdzającego lub przez każdego, kto chce obliczyć powolną funkcję (zasadniczo VDF). Tak więc, jeśli któryś z uczestników zrezygnuje z protokołu ujawniania zobowiązań, jego zobowiązanie nadal może zostać otwarte przez innych. Istotne jest, aby minimalny czas otwarcia zobowiązania był wystarczająco długi, aby nie można tego zrobić podczas pierwszej rundy (faza zatwierdzenia) protokołu, w przeciwnym razie złośliwi uczestnicy mogliby otworzyć zobowiązania innych wystarczająco szybko, aby zmodyfikować swój wkład i zniekształcić wynik .

Jeszcze bardziej elegancki jednokierunkowy protokół jest możliwy dzięki nowoczesnym VDF: całkowicie odrzuć zobowiązanie. Każdy uczestnik może po prostu opublikować swój losowy wkład r_i, a ostateczny wynik jest kombinacją wkładu każdego uczestnika, przepuszczaną przez VDF. Opóźnienie czasowe w obliczaniu VDF zapewnia, że ​​nikt nie może wybrać swojego zaangażowania w sposób, który zniekształca końcowy wynik. Takie podejście zostało zaproponowane jako UNICORN autorstwa Arjena Lenstry i Benjamina Wesołowskiego w 2015 roku i rzeczywiście była kluczowym motywującym zastosowaniem w rozwój VDF.

Takie podejście doczekało się praktycznego wdrożenia. Udział implementuje wersję tego jako część swojego protokołu konsensusu, używając VDF o powtarzającym się kwadratu w grupach klasowych. Starkware wdrożone beacon oparty na VDF przy użyciu plików VDF opartych na SNARK. Ethereum też plany w użyciu to podejście, budowanie dedykowanego układu ASIC do obliczania VDF w celu generowania losowości w warstwie konsensusu.

***

Losowość publiczna jest podstawowym elementem wielu protokołów, ale nadal brakuje nam standardowego DRB, który zapewniałby wysoki poziom bezpieczeństwa. Przestrzeń projektowa jest duża i możliwych jest wiele hybryd i kombinacji powyższych podejść. Na przykład, możliwe jest połączenie protokołu opartego na VRF z protokołem opartym na VDF, który dodaje świeżą entropię, na przykład, zgodnie z propozycją RandRunner. Ethereum's Beacon Chain obecnie używa VRF, chociaż może w przyszłości dodać VDF, aby wyeliminować możliwość stronniczości z ataków blokujących.

Jest to również otwarte pytanie, kiedy protokoły uczciwej większości są akceptowane. Dla stosunkowo niewielkiej, zweryfikowanej grupy uczestników – jak Liga Entropii – założenie uczciwej większości jest rozsądne. Z drugiej strony protokoły, które wymagają tylko jednego uczciwego uczestnika, mają nieodłączną zaletę – większa liczba uczestników może tylko poprawić bezpieczeństwo. Oznacza to, że te protokoły mogą być potencjalnie wdrażane przy otwartym, bezprawnym udziale.

W części II omówimy konkretne zastosowanie losowych wyborów liderów w protokołach konsensusu, które mają nieco inne cele projektowe i w rezultacie zaproponowano jeszcze więcej protokołów i podejść.

***

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.