Wprowadzenie
„Generowanie liczb losowych jest zbyt ważne, aby pozostawić to przypadkowi“
Robert Caui, 1970
Artykuł ten poświęcony jest praktycznemu zastosowaniu rozwiązań wykorzystujących zbiorowe generowanie liczb losowych w nieufnej przestrzeni. W skrócie — jak i dlaczego losowość jest wykorzystywana w blockchainach, oraz kilka informacji na temat tego, jak odróżnić „dobrą” losowość od „złej”. Generowanie rzeczywiście losowej liczby jest niezwykle trudnym problemem nawet na pojedynczym komputerze i od dawna jest przedmiotem badań kryptografów. W zdecentralizowanych sieciach generowanie liczb losowych jest jeszcze bardziej skomplikowane i istotne.
W sieciach, w których uczestnicy sobie nawzajem nie ufają, możliwość wygenerowania niepodważalnej liczby losowej pozwala skutecznie rozwiązywać wiele kluczowych zadań i znacznie poprawić już istniejące schematy. Warto jednak zauważyć, że hazard i loterie wcale nie są tutaj głównym celem, jak może się wydawać niewprawnemu Czytelnikowi.
Generowanie liczb losowych
Komputery nie potrafią same generować liczb losowych, potrzebują do tego pomocy z zewnątrz. Komputer może uzyskać pewną losową wartość, wykorzystując na przykład ruchy myszy, ilość używanej pamięci, szumy na stykach procesora i wiele innych źródeł, zwanych źródłami entropii. Same te wartości nie są do końca losowe, ponieważ mieszczą się w określonym zakresie lub mają przewidywalny charakter zmian. Aby przekształcić takie liczby w rzeczywiste liczby losowe w zadanym zakresie, stosuje się kryptoprzekształcenia, które z nierównomiernie rozłożonych wartości źródła entropii generują równomiernie rozłożone wartości pseudolosowe. Otrzymane wartości nazywa się pseudolosowymi, ponieważ nie są one prawdziwie losowe, a deterministycznie wytworzone z entropii. Każdy dobry algorytm kryptograficzny, szyfrując dane, produkuje szyfrogramy, które statystycznie nie powinny różnić się od losowej sekwencji, więc do produkcji losowości można używać źródła entropii, które zapewnia jedynie dobrą niepowtarzalność i nieprzewidywalność wartości, nawet w małych zakresach; resztę pracy w rozpraszaniu i mieszaniu bitów w otrzymanej wartości wykona algorytm szyfrowania.
Aby zakończyć krótki wykład, dodam, że generacja liczb losowych nawet na jednym urządzeniu to jeden z filarów zapewnienia bezpieczeństwa naszych danych. Wygenerowane pseudolosowe liczby są używane przy nawiązywaniu zabezpieczonych połączeń w różnych sieciach, do generowania kluczy kryptograficznych, do balansowania obciążenia, kontroli integralności i wielu innych zastosowań. Bezpieczeństwo wielu protokołów zależy od możliwości wygenerowania niezawodnego, nieprzewidywalnego losowego źródła, zachowania go i nieujawniania go do następnego kroku protokołu, w przeciwnym razie bezpieczeństwo będzie zagrożone. Atak na generator pseudolosowych wartości jest niezwykle niebezpieczny i stawia pod znakiem zapytania całe oprogramowanie korzystające z generacji losowości.
Wszystko to powinniście wiedzieć, jeśli przeszliście podstawowy kurs kryptografii, dlatego kontynuujmy o sieciach zdecentralizowanych.
Losowość w blockchainach
Na początek omówię blockchainy z obsługą inteligentnych kontraktów, ponieważ to one w pełni mogą wykorzystać możliwości, jakie daje wysokiej jakości niepodważalna losowość. Następnie, dla skrótu, będę nazywać tę technologię “Publicznie Weryfikowalne Losowe Beacony” lub PVRB. Ponieważ blockchainy to sieci, w których informacje może weryfikować każdy uczestnik, kluczowym elementem nazwy jest “Publicznie Weryfikowalne”, tzn. każdy, kto zechce, może przy użyciu obliczeń uzyskać dowód na to, że otrzymana liczba umieszczona w blockchainie posiada takie właściwości:
- Wynik musi mieć w sposób udowodniony równomierny rozkład, tzn. oparty na udowodnionej odpornej kryptografii.
- Nie ma możliwości kontrolowania żadnego z bitów wyniku. W konsekwencji wynik nie może być wcześniej przewidziany.
- Nie można sabotować protokołu generacji przez nieuczestniczenie w protokole ani przez przeciążenie sieci atakującymi wiadomościami.
- Wszystko, co wcześniej wymieniono, musi być odporne na zmowy dozwolonej liczby nieuczciwych uczestników protokołu (na przykład 1/3 uczestników).
Każda możliwość zmowy niewielkiej grupy uczestników na uzyskanie nawet kontrolowanej parzystej/nieparzystej losowości – to luka w bezpieczeństwie. Każda możliwość grupy na zatrzymanie wydawania losowości – to luka w bezpieczeństwie. Ogólnie, problemów jest wiele, a to zadanie nie jest łatwe…
Wydaje się, że najważniejsze zastosowanie dla PVRB to różne gry, loterie i w ogóle wszelkiego rodzaju hazard w blockchainie. To rzeczywiście ważny kierunek, ale losowość w blockchainach ma i ważniejsze zastosowania. Rozważmy je.
Algorytmy konsensusu
PVRB ma ogromne znaczenie dla organizacji konsensusu sieciowego. Transakcje w blockchainach są zabezpieczone podpisem elektronicznym, dlatego "atak na transakcję" zawsze oznacza włączenie/wyłączenie transakcji w blok (lub w kilka bloków). Głównym zadaniem algorytmu konsensusu jest uzgodnienie kolejności tych transakcji oraz kolejności bloków, które je zawierają. Ważnym wymogiem dla rzeczywistych blockchainów jest finalność — możliwość sieci uzgodnienia, że łańcuch do zfinalizowanego bloku jest ostateczny i nigdy nie będzie wykluczony w wyniku pojawienia się nowego forka. Zwykle, aby uzgodnić, że blok jest ważny i co najważniejsze, finalny, należy uzyskać podpisy od większości producentów bloków (dalej BP — block-producers), co wymaga przynajmniej dostarczenia łańcucha bloków do wszystkich BP oraz rozsyłania podpisów między wszystkimi BP. Wraz ze wzrostem liczby BP, liczba wymaganych wiadomości w sieci rośnie wykładniczo, dlatego algorytmy konsensusu wymagające finalności, używane na przykład w konsensie pBFT Hyperledger, nie działają z wymaganą prędkością, zaczynając od kilku dziesiątek BP, wymagając ogromnej liczby połączeń.
Jeśli w sieci istnieje niekwestionowany i uczciwy PVRB, to nawet w najprostszym przybliżeniu można na jego podstawie wybrać jednego z producentów bloków i mianować go "liderem" na czas jednego okrążenia protokołu. Jeśli mamy N producentów bloków, z których M: M > 1/2 N jest uczciwy, nie cenzuruje transakcji i nie tworzy forków łańcucha w celu przeprowadzenia ataku "double spend", to wykorzystanie równomiernie rozłożonego niekwestionowanego PVRB pozwoli na wybór uczciwego lidera z prawdopodobieństwem M / N (M / N > 1/2). Jeśli każdemu przewodniczącemu przypiszemy własny przedział czasowy, w którym może on zablokować i zweryfikować łańcuch, a te przedziały będą równe czasowo, to łańcuch bloków uczciwych BP będzie dłuższy niż ten stworzony przez złośliwe BP, a algorytm konsensusu oparty na długości łańcucha po prostu odrzuci „zły”. Ta zasada przydzielania równych kwantów czasu każdemu BP została po raz pierwszy zastosowana w Graphene (poprzedniku EOS), co umożliwia zamykanie większości bloków jednym podpisem, znacznie redukując obciążenie sieci i pozwalając temu konsensusowi działać ekstremalnie szybko i stabilnie. Niemniej jednak, sieci EOS muszą obecnie korzystać ze specjalnych bloków (Last Irreversible Block), które są potwierdzane przez podpisy 2/3 BP. Bloki te służą zapewnieniu finalności (niemożności pojawienia się forków łańcucha rozpoczynających się przed ostatnim Last Irreversible Block).
Ponadto, w rzeczywistych implementacjach schemat protokołu jest bardziej skomplikowany - głosowania nad proponowanymi blokami odbywają się w kilku etapach, aby zachować działanie sieci w przypadku pominięcia bloków i problemów z siecią, ale nawet biorąc pod uwagę to, algorytmy konsensusu wykorzystujące PVRB wymagają znacznie mniej wiadomości między BP, co pozwala na ich szybsze działanie niż tradycyjne PВFT lub różne jego modyfikacje.
Najbardziej znanym przedstawicielem takich algorytmów jest: od zespołu Cardano, który, jak ogłoszono, posiada matematycznie udowodnioną odporność na istnienie zmowy wśród BP.
W Ouroboros PVRB jest używane do określenia tzw. „harmonogramu BP” - harmonogramu, według którego każdemu BP przypisywany jest jego czasowy slot na publikację bloku. Wielką zaletą użycia PVRB jest pełne „równość” BP (zgodnie z wielkościami ich sald). Uczciwość PVRB gwarantuje, że złośliwe BP nie mogą kontrolować harmonogramu czasowych slotów i w związku z tym nie mogą manipulować łańcuchem, uprzednio przygotowując i analizując forki łańcucha, a do wyboru forka wystarczy polegać po prostu na długości łańcucha, nie posługując się złożonymi metodami obliczania „użyteczności” BP i „wagi” jego bloków.
W większości przypadków, gdy w zdecentralizowanej sieci należy wybrać losowego uczestnika, najlepszym rozwiązaniem jest niemal zawsze PVRB, a nie deterministyczna opcja oparta na przykład na hashu bloku. Bez PVRB możliwość wpływania na wybór uczestnika prowadzi do ataków, w których atakujący, wybierając spośród kilku przyszłych opcji, może wybrać następnego skorumpowanego uczestnika lub od razu kilku, aby zapewnić sobie większy udział w podejmowaniu decyzji. Wykorzystanie PVRB dyskredytuje tego typu ataki.
Skalowanie i równoważenie obciążenia
PVRB może przynieść istotne korzyści również w zadaniach związanych ze zmniejszaniem obciążenia i skalowaniem płatności. Na początek warto zapoznać się z artykułem Riwesty „Elektroniczne bilety loteryjne jako mikropłatności”. Główna idea polega na tym, że zamiast dokonywać 100 płatności po 1 groszu od płatnika do odbiorcy, można zagrać w uczciwą loterię z nagrodą 1 $ = 100 groszy, gdzie płatnik przy każdej płatności 1 grosz przekazuje bankowi jeden ze swoich 100 „biletów loteryjnych”. Jeden z tych biletów wygrywa bankowi 1 $, i to właśnie ten bilet odbiorca może zarejestrować w blockchainie. Najważniejsze jest to, że pozostałe 99 biletów jest przekazywanych między odbiorcą a płatnikiem bez jakiegokolwiek zewnętrznego udziału, przez prywatny kanał i z dowolną potrzebną prędkością. Dobre opisanie protokołu opartego na tym schemacie w sieci Emercoin można przeczytać .
Ta схема ma kilka problemów, na przykład odbiorca może przestać obsługiwać płatnika natychmiast po otrzymaniu wygrywającego biletu, ale w wielu szczególnych zastosowaniach, takich jak taryfikacja minutowa czy subskrypcje elektroniczne, można je zignorować. Najważniejszym wymaganiem jest oczywiście uczciwość prowadzonej loterii, a do jej przeprowadzenia niezbędne jest PVRB.
Wybór losowego uczestnika jest niezwykle istotny również dla protokołów shardingu, których celem jest poziome skalowanie łańcucha bloków, pozwalając różnym BP przetwarzać jedynie swój zakres transakcji. To bardzo skomplikowane zadanie, zwłaszcza w kontekście bezpieczeństwa przy łączeniu shardów. Uczciwy wybór losowego BP, którego zadaniem jest odpowiedzialność za określony shard, podobnie jak w algorytmach konsensusu — jest także zadaniem PVRB. W systemach scentralizowanych shardów przydziela balansujący, który po prostu oblicza hash zapytania i wysyła go do odpowiedniego wykonawcy. W blockchainach wpływ na to przydzielenie może prowadzić do ataku na konsensus. Na przykład, zawartość transakcji może być kontrolowana przez napastnika, który ma możliwość kontrolowania, które transakcje trafiają do kontrolowanego przez niego shardu i manipulować łańcuchem bloków w nim. Dyskusję na temat problemu wykorzystania liczb losowych do zadań shardingu w Ethereum można przeczytać.
Sharding to jedno z najbardziej ambitnych i poważnych zadań w obszarze blockchain, a jego rozwiązanie pozwoli na budowę zdecentralizowanych sieci o fantastycznej wydajności i skali. PVRB to tylko jeden z ważnych elementów umożliwiających jego rozwiązanie.
Gry, protokoły ekonomiczne, arbitraż
Rola liczb losowych w przemyśle gier jest trudna do przecenienia. Wyraźne zastosowanie w kasynach online oraz niejawne przy obliczaniu efektów określonego działania gracza to bardzo skomplikowane problemy dla zdecentralizowanych sieci, gdzie nie ma możliwości polegania na centralnym źródle losowości. Niemniej jednak, losowy wybór może rozwiązywać wiele problemów ekonomicznych i pomagać w budowaniu prostszych i bardziej efektywnych protokołów. Załóżmy, że w naszym protokole występują spory dotyczące płatności za jakieś tanie usługi, a te spory pojawiają się stosunkowo rzadko. W takim przypadku, jeśli istnieje niepodważalny PVRB, klienci i sprzedawcy mogą umówić się na losowe rozstrzyganie sporów, ale z określoną prawdopodobnością. Na przykład, z prawdopodobieństwem 60% wygrywa klient, a z prawdopodobieństwem 40% — sprzedawca. Podejście to, na pierwszy rzut oka absurdalne, pozwala automatycznie rozstrzygać spory z dokładnie przewidywalnym udziałem wygranych/przegranych, co zadowala obie strony bez udziału osoby trzeciej i niepotrzebnej straty czasu. Co więcej, stosunek prawdopodobieństw może być dynamiczny i zależeć od pewnych globalnych zmiennych. Na przykład, jeśli firma radzi sobie dobrze, obserwuje się niską liczbę sporów i wysoką rentowność, firma może automatycznie przesuwać prawdopodobieństwo rozstrzygania sporów w stronę orientacji na klienta, na przykład 70/30 lub 80/20, i odwrotnie, jeśli spory pochłaniają dużo środków i są oszukańcze lub nieadekwatne, można przesuwać prawdopodobieństwo w drugą stronę.
Wiele interesujących zdecentralizowanych protokołów, takich jak tokenowe rejestry, rynki przewidywań, krzywe bondingowe i wiele innych, stanowi gry ekonomiczne, w których nagradzane jest dobre zachowanie, a złe jest karane. Często występują w nich problemy z bezpieczeństwem, których zabezpieczenia są sprzeczne. To, co jest chronione przed atakiem „wielorybów” z miliardami tokenów („big stake”), jest podatne na ataki tysięcy kont z niewielkimi balansami („sybil stake”), a środki podejmowane przeciwko jednemu atakowi, takie jak nieliniowe opłaty, mające na celu uczynienie pracy dużego stawki nieopłacalnej, zwykle są obalane przez inny atak. Ponieważ mówimy o grze ekonomicznej, odpowiednie wagi statystyczne można obliczyć z wyprzedzeniem i po prostu zastąpić opłaty zrandomizowanymi z odpowiednim rozkładem. Takie probabilistyczne opłaty są realizowane bardzo prosto, jeśli w blockchainie istnieje wiarygodne źródło losowości i nie wymagają żadnych skomplikowanych obliczeń, co komplikuje życie zarówno wielorybom, jak i sybilom.
Należy jednocześnie pamiętać, że kontrola nad jedną bit jednego w tej losowości pozwala oszukiwać, zmniejszając i zwiększając prawdopodobieństwa dwukrotnie, więc uczciwy PVRB jest najważniejszym składnikiem takich protokołów.
Gdzie znaleźć odpowiednią losowość?
W teorii, uczciwy losowy wybór w zdecentralizowanych sieciach pozwala zapewnić dowodową bezpieczeństwo niemal każdego protokołu przed zmową. Uzasadnienie jest dość proste — jeśli sieć umawia się co do jednego bitu 0 lub 1, a wśród uczestników mniej niż połowa jest nieuczciwa, to przy wystarczającej liczbie iteracji sieć z pewnością osiągnie konsensus w sprawie tego bitu z ustaloną prawdopodobieństwem. Po prostu dlatego, że uczciwa losowość wybierze 51 z 100 uczestników w 51% przypadków. Ale to w teorii, ponieważ w rzeczywistych sieciach, aby zapewnić taki poziom bezpieczeństwa, jak w artykułach, wymagana jest ogromna liczba wiadomości między hostami, skomplikowana kryptografia wieloetapowa, a każde skomplikowanie protokołu od razu dodaje nowe wektory ataku.
Dlatego wciąż nie widzimy w blockchainach udowodnionego, odpornego PVRB, który byłby używany na tyle długo, aby przeszedł testy prawdziwych aplikacji, wielu audytów, obciążeń, a co najważniejsze, rzeczywistych ataków, bez których trudno nazwać produkt rzeczywiście bezpiecznym.
Jednakże istnieje kilka obiecujących podejść, które różnią się wieloma szczegółami i które z całą pewnością rozwiążą ten problem. Przy nowoczesnych zasobach obliczeniowych, teoria kryptograficzna potrafi dość sprawnie przekształcać się w zastosowania praktyczne. W przyszłości z przyjemnością opowiemy o implementacjach PVRB: jest ich kilka, z każdą wiąże się zestaw ważnych właściwości i szczegółów realizacji, a za każdą stoi dobra idea. Tylko kilka zespołów zajmuje się generowaniem losowości, a doświadczenie każdego z nich jest niezwykle ważne dla wszystkich pozostałych. Mamy nadzieję, że nasze informacje pozwolą innym zespołom działać szybciej, uwzględniając doświadczenia wcześniejszych.
Źródło: habr.com
