Czy możliwe jest generowanie liczb losowych, jeśli nie mamy do siebie zaufania? Część 1

Hej Habra!

W tym artykule omówię generowanie liczb pseudolosowych przez uczestników, którzy sobie nie ufają. Jak zobaczymy poniżej, wdrożenie „prawie” dobrego generatora jest dość proste, ale bardzo dobrego jest trudne.

Dlaczego konieczne byłoby generowanie liczb losowych wśród uczestników, którzy sobie nie ufają? Jednym z obszarów zastosowań są aplikacje zdecentralizowane. Na przykład aplikacja, która przyjmuje zakład od uczestnika i albo podwaja kwotę z prawdopodobieństwem 49%, albo odbiera z prawdopodobieństwem 51%, będzie działać tylko wtedy, gdy będzie mogła bezstronnie otrzymać losową liczbę. Jeśli atakujący może wpłynąć na wynik generatora liczb losowych, a nawet nieznacznie zwiększyć swoją szansę na otrzymanie wypłaty w aplikacji, z łatwością go zniszczy.

Projektując protokół generowania rozproszonych liczb losowych, chcemy, aby miał on trzy właściwości:

1. Musi być bezstronny. Innymi słowy, żaden uczestnik nie powinien w żaden sposób wpływać na wynik generatora liczb losowych.

2. Musi być nieprzewidywalny. Innymi słowy, żaden uczestnik nie powinien być w stanie przewidzieć, jaka liczba zostanie wygenerowana (ani wywnioskować o jakichkolwiek jej właściwościach) przed jej wygenerowaniem.

3. Protokół musi być opłacalny, czyli odporny na to, że określony procent uczestników odłącza się od sieci lub celowo próbuje zatrzymać protokół.

W tym artykule przyjrzymy się dwóm podejściu: Randao + VDF i podejściu opartemu na kodach kasowania. W kolejnej części szczegółowo przeanalizujemy podejście oparte na podpisach progowych.

Ale najpierw przyjrzyjmy się prostemu i powszechnie używanemu algorytmowi, który jest wykonalny, nieprzewidywalny, ale stronniczy.

Randao

Randao to bardzo proste i dlatego dość powszechnie stosowane podejście do generowania losowości. Wszyscy uczestnicy sieci najpierw lokalnie wybierają liczbę pseudolosową, następnie każdy uczestnik wysyła hash wybranej liczby. Następnie uczestnicy na zmianę ujawniają wybrane przez siebie liczby i wykonują na ujawnionych liczbach operację XOR, a wynik tej operacji staje się wynikiem protokołu.

Krok publikowania skrótów przed ujawnieniem liczb jest konieczny, aby atakujący nie mógł wybrać swojego numeru po zapoznaniu się z numerami pozostałych uczestników. Pozwoliłoby mu to praktycznie samodzielnie określić wynik generatora liczb losowych.

W trakcie protokołu uczestnicy muszą dwukrotnie podjąć wspólną decyzję (tzw. konsensus): kiedy zacząć ujawniać wybrane liczby, a tym samym przestać akceptować hashe, a kiedy przestać akceptować wybrane liczby i obliczać wynikową losowość numer. Podejmowanie takich decyzji pomiędzy uczestnikami, którzy sobie nie ufają, samo w sobie nie jest zadaniem łatwym i powrócimy do tego w kolejnych artykułach, w tym artykule założymy, że taki algorytm konsensusu jest nam dostępny.

Które z opisanych powyżej właściwości posiada Randao? Jest nieprzewidywalny, ma taką samą żywotność jak leżący u jego podstaw protokół konsensusu, ale jest stronniczy. W szczególności osoba atakująca może obserwować sieć, a gdy inni uczestnicy ujawnią swoje liczby, może obliczyć ich XOR i zdecydować, czy ujawnić swoją liczbę, czy nie, aby wpłynąć na wynik. Chociaż uniemożliwia to atakującemu samodzielne określenie wyjścia generatora liczb losowych, nadal daje mu 1 bit wpływu. A jeśli atakujący kontrolują kilku uczestników, wówczas liczba kontrolowanych przez nich bitów będzie równa liczbie kontrolowanych przez nich uczestników.

Wpływ atakujących można znacznie ograniczyć, wymagając od uczestników ujawniania liczb w odpowiedniej kolejności. Wtedy atakujący będzie mógł wpłynąć na wynik tylko wtedy, gdy zostanie otwarty jako ostatni. Chociaż wpływ jest znacznie mniejszy, algorytm jest nadal stronniczy.

Randao+VDF

Jednym ze sposobów zapewnienia bezstronności RANDAO jest: po ujawnieniu wszystkich liczb i obliczeniu XOR, jego wynik jest wprowadzany na wejście funkcji, czego obliczenie zajmuje bardzo dużo czasu, ale pozwala sprawdzić poprawność obliczenia bardzo szybko.

(vdf_output, vdf_proof) = VDF_compute(input) // это очень медленно
correct = VDF_verify(input, vdf_output, vdf_proof) // это очень быстро

Funkcja ta nosi nazwę Weryfikowalnej Funkcji Opóźnienia (VDF). Jeżeli obliczenie wyniku końcowego zajmie więcej czasu niż etap ujawnienia liczby, wówczas atakujący nie będzie w stanie przewidzieć efektu pokazania lub ukrycia swojej liczby, w związku z czym straci możliwość wpływania na wynik.

Opracowanie dobrych VDF jest niezwykle trudne. W ostatnim czasie doszło do kilku przełomów, m.in. to и Ten, co uczyniło VDF bardziej praktycznym w praktyce, a Ethereum 2.0 planuje w dłuższej perspektywie używać Randao z VDF jako źródła liczb losowych. Oprócz tego, że podejście to jest nieprzewidywalne i bezstronne, ma ono dodatkową zaletę: jest wykonalne, jeśli w sieci dostępnych jest co najmniej dwóch uczestników (zakładając, że zastosowany protokół konsensusu jest wykonalny w przypadku tak małej liczby uczestników).

Największym wyzwaniem związanym z tym podejściem jest skonfigurowanie VDF w taki sposób, że nawet uczestnik dysponujący bardzo drogim specjalistycznym sprzętem nie będzie w stanie obliczyć VDF przed zakończeniem fazy odkrywania. W idealnym przypadku algorytm powinien mieć nawet znaczny margines bezpieczeństwa, powiedzmy 10x. Poniższy rysunek przedstawia atak aktora wyposażonego w wyspecjalizowany układ ASIC, który pozwala mu uruchomić VDF szybciej niż czas przeznaczony na ujawnienie potwierdzenia RANDAO. Uczestnik taki może w dalszym ciągu obliczyć wynik końcowy wykorzystując lub nie korzystając ze swojej liczby, a następnie na podstawie wyliczenia zdecydować, czy ma go pokazać, czy nie.

W przypadku wspomnianej powyżej rodziny VDF wydajność dedykowanego układu ASIC może być ponad 100 razy wyższa niż w przypadku konwencjonalnego sprzętu. Zatem jeśli faza wdrażania trwa 10 sekund, wówczas VDF obliczony na takim układzie ASIC musi zająć więcej niż 100 sekund, aby uzyskać 10-krotny margines bezpieczeństwa, a zatem ten sam VDF obliczony na standardowym sprzęcie musi zająć 100x 100 sekund = ~ 3 godziny.

Fundacja Ethereum planuje rozwiązać ten problem tworząc własne, publicznie dostępne, bezpłatne układy ASIC. Gdy to nastąpi, wszystkie inne protokoły również będą mogły korzystać z tej technologii, ale do tego czasu podejście Randao+VDF nie będzie tak opłacalne w przypadku protokołów, które nie mogą inwestować w rozwój własnych układów ASIC.

Na stronie zebrano wiele artykułów, filmów i innych informacji o VDF ta strona.

Używamy kodów kasowania

W tej sekcji przyjrzymy się protokołowi generowania liczb losowych, który wykorzystuje kasowanie kodów. Może tolerować do ⅓ atakujących, pozostając wykonalnym, i pozwala na istnienie do ⅔ atakujących, zanim będą mogli przewidzieć wynik lub wpłynąć na niego.

Główna idea protokołu jest następująca. Dla uproszczenia załóżmy, że uczestników jest dokładnie 100. Załóżmy również, że wszyscy uczestnicy lokalnie mają jakiś klucz prywatny, a klucze publiczne wszystkich uczestników są znane wszystkim uczestnikom:

1. Każdy uczestnik lokalnie tworzy długi ciąg, dzieli go na 67 części, tworzy kody kasowania, aby uzyskać 100 udziałów, tak aby dowolne 67 wystarczyło do odzyskania ciągu, przypisuje każdy ze 100 udziałów jednemu z uczestników i szyfruje je za pomocą klucz publiczny tego samego uczestnika. Wszystkie zakodowane udziały są następnie publikowane.

2. Uczestnicy korzystają z pewnego rodzaju konsensusu, aby osiągnąć porozumienie w sprawie zakodowanych zestawów od konkretnych 67 uczestników.

3. Po osiągnięciu konsensusu każdy uczestnik bierze zakodowane udziały w każdym z 67 zestawów zaszyfrowanych swoim kluczem publicznym, odszyfrowuje wszystkie takie udziały i publikuje wszystkie takie odszyfrowane udziały.

4. Gdy 67 uczestników wykona krok (3), wszystkie uzgodnione zestawy można całkowicie odkodować i zrekonstruować ze względu na właściwości kodów kasowania, a ostateczną liczbę można uzyskać jako XOR początkowych wierszy, od których uczestnicy zaczęli w (1) .

Można wykazać, że protokół ten jest bezstronny i nieprzewidywalny. Wynikowa liczba losowa jest ustalana po osiągnięciu konsensusu, ale nie jest znana nikomu, dopóki ⅔ uczestników nie odszyfruje części zaszyfrowanych ich kluczem publicznym. Zatem liczba losowa jest ustalana przed publikacją informacji wystarczających do jej rekonstrukcji.

Co się stanie, jeśli w kroku (1) jeden z uczestników prześle pozostałym uczestnikom zakodowane udziały, które nie są poprawnym kodem kasowania dla jakiegoś ciągu znaków? Bez dodatkowych zmian różni uczestnicy albo w ogóle nie będą mogli odzyskać ciągu, albo odzyskają różne ciągi, co spowoduje, że różni uczestnicy otrzymają inną liczbę losową. Aby temu zapobiec, możesz wykonać następujące czynności: każdy uczestnik oprócz zakodowanych udziałów również wykonuje obliczenia Drzewo Merkli wszystkie takie udziały i wysyła każdemu uczestnikowi zarówno sam zakodowany udział, jak i korzeń drzewa merkle oraz dowód włączenia udziału do drzewa merkle. W ramach konsensusu w kroku (2) uczestnicy nie tylko uzgadniają zestaw zbiorów, ale także zestaw konkretnych korzeni takich drzew (jeśli jakiś uczestnik odstąpił od protokołu i wysłał różne korzenie drzewa merkle do różnych uczestników, i dwa takie pierwiastki są pokazywane podczas konsensusu, jego wiersz nie jest uwzględniany w zestawie wyników). W wyniku konsensusu otrzymamy 67 zakodowanych linii i odpowiadające im korzenie drzewa Merkle, tak że będzie co najmniej 67 uczestników (niekoniecznie tych samych, którzy zaproponowali odpowiednie linie), którzy dla każdej z 67 linii mają komunikat z udziałem kodu kasowania oraz dowód wystąpienia ich udziału w odpowiednim drzewie zniknął.

Gdy w kroku (4) uczestnik rozszyfruje 67 uderzeń dla danego ciągu i spróbuje zrekonstruować z nich oryginalny ciąg, możliwa jest jedna z opcji:

1. Ciąg zostanie przywrócony, a jeśli następnie zostanie ponownie zakodowany poprzez wymazanie, a drzewo Merkle zostanie obliczone dla lokalnie obliczonych udziałów, pierwiastek pokrywa się z tym, co do którego osiągnięto konsensus.

2. Wiersz został przywrócony, ale obliczony lokalnie pierwiastek nie jest zgodny z tym, przy którym osiągnięto konsensus.

3. Wiersz nie został przywrócony.

Łatwo pokazać, że jeśli opcja (1) wystąpiła u co najmniej jednego uczestnika powyżej, to opcja (1) wystąpiła u wszystkich uczestników i odwrotnie, jeśli opcja (2) lub (3) wystąpiła u co najmniej jednego uczestnika, to dla wszystkich uczestników nastąpi opcja (2) lub (3). Zatem dla każdego wiersza w zestawie albo wszyscy uczestnicy pomyślnie go odzyskają, albo wszyscy uczestnicy nie odzyskają go. Wynikowa liczba losowa jest wówczas XOR tylko tych wierszy, które uczestnicy byli w stanie odzyskać.

Podpisy progowe

Innym podejściem do losowości jest użycie tak zwanych sygnatur progowych BLS. Generator liczb losowych oparty na sygnaturach progowych ma dokładnie takie same gwarancje, jak opisany powyżej algorytm oparty na kodzie kasowania, ale ma znacznie niższą asymptotyczną liczbę komunikatów przesyłanych siecią dla każdej wygenerowanej liczby.

Podpisy BLS to projekt, który umożliwia wielu uczestnikom utworzenie jednego wspólnego podpisu dla wiadomości. Podpisy te są często używane w celu zaoszczędzenia miejsca i przepustowości, ponieważ nie wymagają wysyłania wielu podpisów. 

Powszechnym zastosowaniem podpisów BLS w protokołach blockchain, oprócz generowania liczb losowych, jest podpisywanie blokowe w protokołach BFT. Załóżmy, że 100 uczestników tworzy bloki, a blok uważa się za ostateczny, jeśli podpisze go 67 z nich. Wszyscy mogą przesłać swoje części podpisu BLS i użyć algorytmu konsensusu, aby uzgodnić 67 z nich, a następnie połączyć je w jeden podpis BLS. Do utworzenia ostatecznego podpisu można użyć dowolnych 67 (lub więcej) części, co będzie zależeć od tego, które 67 podpisów zostało połączonych i dlatego może się różnić, chociaż różne wybory dokonane przez 67 uczestników spowodują utworzenie innego podpisu, każdy taki podpis będzie ważny podpis pod blokiem. Pozostali uczestnicy muszą wówczas odebrać i zweryfikować tylko jeden podpis na blok zamiast 67 w sieci, co znacznie zmniejsza obciążenie sieci.

Okazuje się, że jeśli klucze prywatne, którymi posługują się uczestnicy, zostaną wygenerowane w określony sposób, to niezależnie od tego, jakich 67 podpisów (lub więcej, ale nie mniej) zostanie zagregowanych, otrzymany podpis będzie taki sam. Można to wykorzystać jako źródło losowości: uczestnicy najpierw uzgadniają jakąś wiadomość, którą podpiszą (może to być wynik RANDAO lub po prostu skrót ostatniego bloku, nie ma to większego znaczenia, pod warunkiem, że zmienia się za każdym razem i jest spójny) i utwórz dla niego podpis BLS. Wynik generacji będzie nieprzewidywalny, dopóki 67 uczestników nie dostarczy swoich części, a potem wynik generacji jest już z góry określony i nie może zależeć od działań żadnego uczestnika.

Takie podejście do losowości jest wykonalne, o ile co najmniej ⅔ uczestników online przestrzega protokołu, oraz jest bezstronne i nieprzewidywalne, o ile co najmniej ⅓ uczestników przestrzega protokołu. Należy zauważyć, że osoba atakująca kontrolująca więcej niż ⅓, ale mniej niż ⅔ uczestników może zatrzymać protokół, ale nie może przewidzieć jego wyników ani na nie wpływać.

Same sygnatury progowe to bardzo ciekawy temat. W drugiej części artykułu szczegółowo przeanalizujemy, jak one działają i jak dokładnie należy wygenerować klucze uczestnika, aby podpisy progowe mogły służyć jako generator liczb losowych.

Na zakończenie

Ten artykuł jest pierwszym z serii technicznych artykułów na blogu BLISKO. NEAR to protokół i platforma blockchain do tworzenia zdecentralizowanych aplikacji, z naciskiem na łatwość programowania i łatwość użytkowania dla użytkowników końcowych.

Kod protokołu jest otwarty, nasza implementacja jest napisana w Rust, można ją znaleźć tutaj.

Możesz zobaczyć, jak wygląda rozwój NEAR i poeksperymentować w internetowym środowisku IDE tutaj.

Wszystkie aktualności w języku rosyjskim można śledzić pod adresem grupa telegramów i grupa na VKontakteoraz w języku angielskim w wersji oficjalnej świergot.

Do zobaczenia wkrótce!

Źródło: www.habr.com