Cześć, Habr!
W tym artykule opowiem o generowaniu pseudo-losowych liczb przez uczestników, którzy nie ufają sobie nawzajem. Jak zobaczymy poniżej, stworzenie „prawie” dobrego generatora jest dość proste, ale bardzo dobrego — już nie.
Dlaczego w ogóle uczestnicy, którzy sobie nie ufają, powinni generować losowe liczby? Jednym z zastosowań są dApps (decentralizowane aplikacje). Na przykład aplikacja, która przyjmuje zakład od uczestnika i albo podwaja kwotę z prawdopodobieństwem 49%, albo ją zabiera z 51%, będzie działać tylko wtedy, gdy może obiektywnie uzyskać losową liczbę. Jeśli haker może wpłynąć na wynik działania generatora losowości, a nawet w niewielkim stopniu zwiększyć swoje szanse na wypłatę w aplikacji, łatwo ją opróżni.
Kiedy projektujemy rozproszony protokół generowania losowych liczb, chcemy, aby miał on trzy właściwości:
Musi być obiektywny. Innymi słowy, żaden uczestnik nie powinien mieć wpływu na wynik generatora losowych liczb.
Musi być nieprzewidywalny. Innymi słowy, żaden uczestnik nie powinien mieć możliwości przewidzenia, jaka liczba zostanie wygenerowana (ani wydobycia jakichkolwiek jej właściwości) zanim zostanie ona wygenerowana.
Protokół musi być wykonalny, tzn. odporny na sytuację, w której jakiś procent uczestników wyłączy się z sieci lub celowo spróbuje zatrzymać protokół.
W tym artykule omówimy dwa podejścia: RANDAO + VDF oraz podejście oparte na kodach wygładzających. W następnej części szczegółowo omówimy podejście oparte na podpisach progowych.
Ale na początek przyjrzyjmy się prostemu i często stosowanemu algorytmowi, który jest wykonalny, nieprzewidywalny, ale nieobiektywny.
RANDAO
RANDAO to bardzo prosty i w związku z tym dość często stosowany sposób uzyskiwania losowości. Wszyscy uczestnicy sieci najpierw lokalnie wybierają pseudo-losową liczbę, następnie każdy uczestnik wysyła hash wybranej liczby. Następnie uczestnicy kolejno ujawniają swoje wybrane liczby, wykonują operację XOR na ujawnionych liczbach, a wynik tej operacji staje się rezultatem działania protokołu.
Krok publikacji haszy przed odkryciem liczb jest niezbędny, aby przestępca nie mógł wybrać swojej liczby po tym, jak zobaczy liczby pozostałych uczestników. Pozwoliłoby to mu na samodzielne określenie wyniku generatora liczb losowych.
W trakcie protokołu uczestnicy muszą dwukrotnie dojść do konsensusu: kiedy rozpocząć odkrywanie wybranych liczb, a tym samym zaprzestać przyjmowania haszy, oraz kiedy zakończyć przyjmowanie wybranych liczb i obliczyć wynikową liczbę losową. Podejmowanie takich decyzji między uczestnikami, którzy sobie nawzajem nie ufają, jest samo w sobie skomplikowanym zadaniem, do którego powrócimy w przyszłych artykułach; w tym artykule zakładamy, że taki algorytm konsensusu jest nam dostępny.
Jakie właściwości, które opisaliśmy powyżej, ma RANDAO? Jest nieprzewidywalny, ma tę samą żywotność, co leżący u jego podstaw protokół konsensusu, ale jest stronniczy. W szczególności przestępca może obserwować sieć i po tym, jak inni uczestnicy odkryją swoje liczby, może obliczyć ich XOR i zdecydować, czy odkrywać, czy nie odkrywać swojej liczby, aby wpłynąć na wynik. Chociaż nie pozwala to przestępcy na samodzielne określenie wyniku generatora liczb losowych, wciąż daje mu 1 bit wpływu. A jeśli przestępcy kontrolują kilku uczestników, liczba kontrolowanych przez nich bitów będzie równa liczbie uczestników znajdujących się pod ich kontrolą.
Wpływ przestępców można znacznie zmniejszyć, wymagając, aby uczestnicy odkrywali liczby w kolejności. Wtedy przestępca będzie mógł wpłynąć na wynik tylko wtedy, gdy odkrywa się jako ostatni. Chociaż wpływ jest znacznie mniejszy, algorytm wciąż pozostaje stronniczy.
RANDAO + VDF
Jednym z pomysłów na uczynienie RANDAO nieodparty jest to, że po tym, jak wszystkie liczby zostały odkryte i obliczono XOR, jego wynik jest podawany jako wejście do funkcji, która jest bardzo wolna w obliczeniach, ale pozwala na szybkie weryfikowanie poprawności obliczeń.
(vdf_output, vdf_proof) = VDF_compute(input) // to jest bardzo wolne
correct = VDF_verify(input, vdf_output, vdf_proof) // to jest bardzo szybkieTa funkcja nazywa się Verifiable Delay Function, czyli VDF. Jeśli obliczenie ostatecznego wyniku zajmuje więcej czasu niż etap ujawnienia liczb, to sprawca nie będzie w stanie przewidzieć efektu pokazu lub ukrywania swojej liczby, a tym samym straci możliwość wpływania na wynik.
Opracowanie dobrych VDF jest niezwykle trudne. Ostatnio dokonano kilku przełomów, na przykład i które sprawiły, że VDF stały się bardziej praktyczne, a Ethereum 2.0 w dłuższej perspektywie planuje wykorzystanie RANDAO z VDF jako źródła liczb losowych. Poza tym, że podejście to jest nieprzewidywalne i obiektywne, ma dodatkową zaletę polegającą na żywotności, jeśli przynajmniej dwóch uczestników jest dostępnych w sieci (pod warunkiem, że używany protokół konsensusu jest skuteczny przy tak niewielkiej liczbie uczestników).
Największa trudność tego podejścia polega na skonfigurowaniu VDF tak, aby nawet uczestnik z bardzo drogim specjalistycznym sprzętem nie był w stanie obliczyć VDF przed zakończeniem fazy ujawniania. W idealnym przypadku algorytm powinien mieć nawet znaczny zapas, powiedzmy 10x. Na poniższym rysunku pokazano atak uczestnika posiadającego specjalistyczne ASIC, który pozwala mu uruchomić VDF szybciej, niż czas przydzielony na ujawnienie potwierdzenia RANDAO. Taki uczestnik może nadal obliczać ostateczny wynik, wykorzystując i nie wykorzystując swojej liczby, a następnie na podstawie obliczeń decydować, czy ją pokazać, czy nie.
Dla wspomnianego powyżej rodziny VDF wydajność specjalistycznego ASIC może być ponad 100 razy wyższa niż w przypadku zwykłego sprzętu. Zatem jeśli faza ujawnienia trwa 10 sekund, to VDF obliczane na takim ASIC powinno zajmować ponad 100 sekund, aby uzyskać 10-krotny zapas bezpieczeństwa, a zatem to samo VDF obliczone na zwykłym sprzęcie powinno zająć 100 x 100 sekund = ~ 3 godziny.
Fundacja Ethereum planuje rozwiązać ten problem poprzez stworzenie własnych publicznych, darmowych ASIC. Gdy to nastąpi, 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 samo wykonalne dla protokołów, które nie mogą zainwestować w opracowanie własnych ASIC.
Wiele artykułów, filmów i innych informacji na temat VDF zebrano na .
Używamy kodów erasure
W tej sekcji przyjrzymy się protokołowi generowania liczb losowych, który wykorzystuje . Może on wytrzymać do ⅓ złośliwych aktorów, pozostając wykonalnym, i dopuszcza istnienie do ⅔ złośliwych aktorów, zanim będą mogli przewidzieć lub wpłynąć na wynik.
Główną ideą protokołu jest następująca. Dla uproszczenia załóżmy, że w nim uczestniczy dokładnie 100 osób. Załóżmy również, że wszyscy uczestnicy lokalnie mają jakiś prywatny klucz, a publiczne klucze wszystkich uczestników są znane wszystkim uczestnikom:
Każdy uczestnik lokalnie wymyśla długi ciąg, dzieli go na 67 części, tworzy kody erasure, aby uzyskać 100 udziałów, z których jakiekolwiek 67 wystarczy do odtworzenia ciągu, przypisuje każdemu z 100 udziałów jednemu z uczestników i szyfruje je za pomocą publicznego klucza tego samego uczestnika. Następnie wszystkie zakodowane udziały są publikowane.
Uczestnicy używają jakiegoś konsensusu, aby osiągnąć zgodność co do zakodowanych zestawów od konkretnych 67 uczestników.
Gdy konsensus zostanie osiągnięty, każdy uczestnik bierze zakodowane udziały w każdym z 67 zestawów, zaszyfrowane ich publicznym kluczem, deszyfruje wszystkie takie udziały i publikuje wszystkie takie odszyfrowane udziały.
Gdy 67 uczestników wykona krok (3), wszystkie uzgodnione zestawy mogą być całkowicie dekodowane i odtwarzane dzięki właściwościom kodów erasure, a ostateczna liczba może być uzyskana jako XOR początkowych ciągów, od których uczestnicy zaczęli w (1).
Można pokazać, że ten protokół jest bezstronny i nieprzewidywalny. Rezultatem jest losowa liczba, która zostaje określona po osiągnięciu konsensusu, ale nikomu nie jest znana, dopóki ⅔ uczestników nie zdekodują części zaszyfrowanych ich kluczem publicznym. W ten sposób losowa liczba jest określona wcześniej niż informacja wystarczająca do jej rekonstrukcji zostaje opublikowana.
Co się stanie, jeśli na kroku (1) jeden z uczestników wyśle innym uczestnikom zakodowane udziały, które nie są poprawnym kodem wymazującym dla jakiegoś łańcucha? Bez dodatkowych zmian, różni uczestnicy mogą nie być w stanie w ogóle zrekonstruować łańcucha lub zrekonstruują różne łańcuchy, co spowoduje, że różni uczestnicy otrzymają różne losowe liczby. Aby temu zapobiec, można zrobić następujące: każdy uczestnik, oprócz zakodowanych udziałów, oblicza również Wszystkich takich udziałów, i każdy uczestnik wysyła zarówno zakodowany udział, jak i korzeń drzewa Merkle oraz dowód włączenia udziału do drzewa Merkle. W konsensusie na kroku (2) uczestnicy nie tylko zgadzają się na wielu zestawach, ale na wielu konkretnych korzeniach takich drzew (jeżeli jakiś uczestnik odszedł od protokołu i wysłał różne korzenie drzewa Merkle różnym uczestnikom, a dwa takie korzenie pokazano podczas konsensusu, jego łańcuch nie jest włączany do zestawu wynikowego). Po zakończeniu konsensusu będziemy mieli 67 zakodowanych łańcuchów i odpowiadających im korzeni drzewa Merkle takich, że jest co najmniej 67 uczestników (niekoniecznie tych samych, którzy zaproponowali odpowiednie łańcuchy), dla których dla każdego z 67 łańcuchów jest wiadomość z udziałem kodu wymazującego i dowód włączenia ich udziału do odpowiedniego drzewa Merkle.
Kiedy na kroku (4) uczestnik odszyfrowuje 67 udziałów dla jakiegoś łańcucha i próbuje na ich podstawie zrekonstruować oryginalny łańcuch, możliwy jest jeden z wariantów:
Łańcuch zostaje zrekonstruowany, a jeśli następnie zostanie ponownie zakodowany kodami wymazującymi i obliczone zostanie drzewo Merkle dla obliczonych lokalnie udziałów, korzeń pokrywa się z tym, na którym osiągnięto konsensus.
Łańcuch zostaje zrekonstruowany, ale obliczony lokalnie korzeń nie odpowiada temu, na którym osiągnięto konsensus.
Łańcuch nie zostaje zrekonstruowany.
Łatwo zauważyć, że jeśli chociaż dla jednego uczestnika wystąpił przypadek (1), to dla wszystkich uczestników również wystąpi przypadek (1), i odwrotnie, jeśli tylko dla jednego uczestnika wystąpił przypadek (2) lub (3), to dla wszystkich uczestników wystąpi przypadek (2) lub (3). W ten sposób dla każdego wiersza w zbiorze albo wszyscy uczestnicy go pomyślnie odtworzą, albo wszyscy uczestnicy nie będą mogli go odtworzyć. Następnie wynikowa liczba losowa to XOR tylko tych wierszy, które uczestnicy mogli odtworzyć.
Podpisy progowe
Innym podejściem do losowości jest wykorzystanie tzw. podpisów progowych BLS. Generator liczb losowych oparty na podpisach progowych ma dokładnie te same gwarancje, co opisany powyżej algorytm oparty na kodach wymazujących, ale ma znacznie mniejszą asymptotykę liczby wiadomości przesyłanych przez sieć na każdą wygenerowaną liczbę.
Podpisy BLS to konstrukcja, która pozwala kilku uczestnikom stworzyć jeden wspólny podpis dla wiadomości. Takie podpisy są często używane w celu oszczędności miejsca i przepustowości, ponieważ nie wymagają rozsyłania wielu podpisów.
Częste zastosowanie podpisów BLS w protokołach blockchain, oprócz generowania liczb losowych, to podpisywanie bloków w protokołach BFT. Powiedzmy, że 100 uczestników tworzy bloki, a blok uznawany jest za ostateczny, jeśli 67 z nich go podpisuje. Wszyscy mogą przedstawić swoje części podpisu BLS i użyć jakiegoś algorytmu konsensusu, aby uzgodnić 67 z nich, a następnie połączyć je w jeden podpis BLS. Dowolne 67 (lub więcej) części mogą być używane do stworzenia ostatecznego podpisu, który będzie zależał od tego, które dokładnie 67 podpisów zostało połączonych, i dlatego może się różnić, ale mimo to, że różny wybór 67 uczestników stworzy różny podpis, każdy taki podpis będzie poprawnym podpisem dla bloku. Pozostałym uczestnikom wystarczy, by otrzymać przez sieć i sprawdzić tylko jeden podpis na każdy blok, zamiast 67, co znacząco zmniejsza obciążenie sieci.
Okazuje się, że jeśli klucze prywatne używane przez uczestników są generowane w określony sposób, to niezależnie od tego, jakie 67 podpisów (lub więcej, ale nie mniej) zostanie zebranych, powstały podpis będzie identyczny. Może to być wykorzystane jako źródło losowości: uczestnicy najpierw uzgadniają jakieś wiadomości, które podpiszą (może to być wynik RANDAO lub po prostu hasz ostatniego bloku, w rzeczywistości nie ma to znaczenia, byleby zmieniało się za każdym razem i było uzgodnione), a następnie tworzą dla niego podpis BLS. Wynik generacji będzie nieprzewidywalny, dopóki 67 uczestników nie dostarczy swoich części, a po tym wyjściowe dane będą już z góry określone i nie mogą zależeć od działań jakiegokolwiek uczestnika.
Takie podejście do losowości jest wykonalne, jeśli przynajmniej ⅔ uczestników jest online i postępuje zgodnie z protokołem, i jest uczciwe oraz nieprzewidywalne, dopóki przynajmniej ⅓ uczestników przestrzega protokołu. Ważne jest, aby zauważyć, że atakujący, który kontroluje więcej niż ⅓, ale mniej niż ⅔ uczestników, może zatrzymać protokół, ale nie może przewidzieć ani wpłynąć na jego rezultat.
Podpisy progowe same w sobie to bardzo ciekawy temat. W drugiej części artykułu szczegółowo omówimy, jak one działają i jak dokładnie należy generować klucze uczestników, aby podpisy progowe mogły być używane jako generator liczb losowych.
Na zakończenie
Ten artykuł to pierwszy z serii artykułów technicznych na blogu. . NEAR to protokół blockchain i platforma do tworzenia zdecentralizowanych aplikacji z akcentem na prostotę programowania oraz łatwość użytkowania dla końcowych użytkowników.
Kod protokołu jest otwarty, nasza implementacja jest napisana w Rust, można ją znaleźć .
Można zobaczyć, jak wygląda rozwój na platformie NEAR i eksperymentować w online-IDE, .
Śledzić wszystkie wiadomości po rosyjsku można w i w , a po angielsku w oficjalnym .
Do zobaczenia wkrótce!
Źródło: habr.com
