Wprowadzenie
„Generowanie liczb losowych jest zbyt ważne, aby pozostawiać je przypadkowi”.
Roberta Cavue’a, 1970
Artykuł poświęcony jest praktycznemu zastosowaniu rozwiązań wykorzystujących zbiorczą generację liczb losowych w niezaufanym środowisku. W skrócie, jak i dlaczego random jest używany w blockchainach i trochę o tym, jak odróżnić „dobry” random od „złego”. Wygenerowanie prawdziwie losowej liczby jest niezwykle trudnym problemem, nawet na jednym komputerze, i jest od dawna badane przez kryptografów. Cóż, w sieciach zdecentralizowanych generowanie liczb losowych jest jeszcze bardziej złożone i ważne.
To właśnie w sieciach, w których uczestnicy nie ufają sobie nawzajem, możliwość wygenerowania niepodważalnej liczby losowej pozwala nam skutecznie rozwiązać wiele krytycznych problemów i znacząco ulepszyć istniejące schematy. Co więcej, hazard i loterie nie są tutaj celem numer jeden, jak mogłoby się początkowo wydawać niedoświadczonemu czytelnikowi.
Generowanie liczb losowych
Komputery nie są w stanie samodzielnie generować liczb losowych; wymagają do tego pomocy z zewnątrz. Komputer może uzyskać pewną losową wartość, na przykład z ruchów myszy, ilości wykorzystanej pamięci, prądów błądzących na pinach procesora i wielu innych źródeł zwanych źródłami entropii. Same wartości nie są całkowicie losowe, ponieważ mieszczą się w pewnym zakresie lub mają przewidywalny wzór zmian. Aby zamienić takie liczby w liczbę prawdziwie losową w danym zakresie, stosuje się do nich kryptotransformacje w celu uzyskania równomiernie rozłożonych wartości pseudolosowych z nierównomiernie rozłożonych wartości źródła entropii. Wynikowe wartości nazywane są pseudolosowymi, ponieważ nie są tak naprawdę losowe, ale są deterministycznie wyprowadzane z entropii. Każdy dobry algorytm kryptograficzny podczas szyfrowania danych generuje szyfrogramy, które powinny być statystycznie nie do odróżnienia od sekwencji losowej, zatem do uzyskania losowości można wykorzystać źródło entropii, które zapewnia jedynie dobrą powtarzalność i nieprzewidywalność wartości nawet w małych zakresach, reszta pracy to rozpraszanie i mieszanie bitów. Wynikowa wartość zostanie przejęta przez algorytm szyfrujący.
Aby uzupełnić krótki program edukacyjny dodam, że generowanie liczb losowych nawet na jednym urządzeniu jest jednym z filarów zapewnienia bezpieczeństwa naszym danym.Wygenerowane liczby pseudolosowe wykorzystywane są przy ustanawianiu bezpiecznych połączeń w różnych sieciach, do generowania klucze kryptograficzne, do równoważenia obciążenia, monitorowania integralności i do wielu innych zastosowań. Bezpieczeństwo wielu protokołów zależy od możliwości wygenerowania niezawodnego, zewnętrznie nieprzewidywalnego losu, przechowywania go i ujawniania dopiero w następnym kroku protokołu, w przeciwnym razie bezpieczeństwo zostanie zagrożone. Atak na generator wartości pseudolosowych jest niezwykle niebezpieczny i bezpośrednio zagraża całemu oprogramowaniu wykorzystującemu generowanie losowości.
Powinieneś to wszystko wiedzieć, jeśli wziąłeś podstawowy kurs kryptografii, więc kontynuujmy temat sieci zdecentralizowanych.
Losowe w blockchainach
Na początek opowiem o blockchainach ze wsparciem dla smart kontraktów, to one potrafią w pełni wykorzystać możliwości, jakie daje wysokiej jakości, niezaprzeczalna losowość. Dalej, dla zwięzłości, nazwę tę technologię „Publicznie weryfikowalne losowe sygnalizatory”lub PVRB. Ponieważ blockchainy to sieci, w których informacje mogą być weryfikowane przez dowolnego uczestnika, kluczową częścią nazwy jest „Publicly Verible”, tj. Każdy może skorzystać z obliczeń, aby uzyskać dowód, że wynikowa liczba umieszczona na blockchainie ma następujące właściwości:
- Wynik musi mieć możliwy do udowodnienia równomierny rozkład, tj. być oparty na możliwej do udowodnienia silnej kryptografii.
- Nie ma możliwości kontrolowania żadnego bitu wyniku. W rezultacie nie można z góry przewidzieć wyniku.
- Nie można sabotować protokołu generowania poprzez nieuczestniczenie w protokole lub przeciążanie sieci komunikatami ataku
- Wszystko to musi być odporne na zmowę dopuszczalnej liczby nieuczciwych uczestników protokołu (np. 1/3 uczestników).
Jakakolwiek możliwość zmowy niewielkiej grupy uczestników w celu wytworzenia nawet kontrolowanego parzystego/nieparzystego wyniku losowego stanowi lukę w zabezpieczeniach. Jakakolwiek możliwość zatrzymania przez grupę losowej emisji stanowi lukę w zabezpieczeniach. Generalnie problemów jest wiele, a zadanie to nie jest łatwe...
Wydaje się, że najważniejszym zastosowaniem PVRB są różne gry, loterie i ogólnie wszelkiego rodzaju gry hazardowe na blockchainie. Rzeczywiście jest to ważny kierunek, ale losowość w blockchainach ma jeszcze ważniejsze zastosowania. Przyjrzyjmy się im.
Algorytmy konsensusu
PVRB odgrywa ogromną rolę w organizowaniu konsensusu sieciowego. Transakcje w blockchainach chronione są podpisem elektronicznym, zatem „atak na transakcję” polega zawsze na włączeniu/wykluczeniu transakcji w bloku (lub kilku blokach). A głównym zadaniem algorytmu konsensusu jest uzgodnienie kolejności tych transakcji i kolejności bloków zawierających te transakcje. Niezbędną właściwością prawdziwych łańcuchów bloków jest także ostateczność – zdolność sieci do uzgodnienia, że łańcuch aż do sfinalizowanego bloku jest ostateczny i nigdy nie zostanie wykluczony ze względu na pojawienie się nowego forku. Zwykle, aby ustalić, że blok jest ważny i co najważniejsze ostateczny, konieczne jest zebranie podpisów od większości producentów bloków (zwanych dalej BP – block-producentami), co wymaga co najmniej dostarczenia łańcucha bloków do wszystkich BP i rozdawanie podpisów pomiędzy wszystkimi BP. Wraz ze wzrostem liczby BP, liczba niezbędnych komunikatów w sieci rośnie wykładniczo, dlatego algorytmy konsensusu wymagające ostateczności, stosowane np. w konsensusie Hyperledger pBFT, nie działają z wymaganą szybkością, zaczynając od kilkudziesięciu BP, wymagając ogromna ilość połączeń.
Jeżeli w sieci istnieje niezaprzeczalny i uczciwy PVRB, to nawet w najprostszym przybliżeniu można na jego podstawie wybrać jednego z producentów bloków i wyznaczyć go na „lidera” podczas jednej rundy protokołu. Jeśli mamy N producentów bloków, w tym M: M > 1/2 N są uczciwi, nie cenzurują transakcji i nie rozwidlają łańcucha w celu przeprowadzenia ataku „podwójnego wydatku”, wówczas zastosowanie równomiernie rozłożonego, niekwestionowanego PVRB pozwoli z prawdopodobieństwem wybrać uczciwego lidera M / N (M / N > 1/2). Jeśli każdemu liderowi przydzielony zostanie własny przedział czasu, w którym może wygenerować blok i zweryfikować łańcuch, a odstępy te są równe w czasie, wówczas łańcuch bloków uczciwych BP będzie dłuższy niż łańcuch utworzony przez złośliwe BP, a konsensus algorytm opiera się na długości łańcucha. Po prostu odrzuci „zły”. Ta zasada przydzielania równych odcinków czasu każdemu BP została po raz pierwszy zastosowana w Graphene (poprzedniku EOS) i pozwala na zamknięcie większości bloków jednym podpisem, co znacznie zmniejsza obciążenie sieci i pozwala na niezwykle szybkie i skuteczne działanie konsensusu stale. Jednak sieć EOS musi teraz korzystać ze specjalnych bloków (Last Irreversible Block), co potwierdzają podpisy 2/3 BP. Bloki te służą zapewnieniu ostateczności (niemożność rozpoczęcia wideł łańcucha przed ostatnim ostatnim nieodwracalnym blokiem).
Również w rzeczywistych wdrożeniach schemat protokołu jest bardziej skomplikowany - głosowanie na proponowane bloki odbywa się w kilku etapach, aby utrzymać sieć w przypadku brakujących bloków i problemów z siecią, ale nawet biorąc to pod uwagę, algorytmy konsensusu wykorzystujące PVRB wymagają znacznie mniej komunikatów pomiędzy BP, co pozwala na ich szybsze wykonanie niż tradycyjny PVFT lub jego różne modyfikacje.
Najwybitniejszym przedstawicielem takich algorytmów: od zespołu Cardano, co uważa się za matematycznie udowodnione przeciwko zmowie BP.
W Ouroboros PVRB służy do zdefiniowania tzw. „harmonogramu BP” – harmonogramu, według którego każdemu BP przypisany jest własny przedział czasowy na publikację bloku. Dużą zaletą stosowania PVRB jest całkowita „równość” BP (ze względu na wielkość ich bilansów). Integralność PVRB zapewnia, że złośliwe BP nie mogą kontrolować planowania przedziałów czasowych, a zatem nie mogą manipulować łańcuchem poprzez wcześniejsze przygotowanie i analizowanie forków łańcucha, a aby wybrać fork, wystarczy po prostu polegać na długości łańcucha, bez stosowania skomplikowanych sposobów obliczania „użyteczności” BP i „wagi” jego bloków.
Ogólnie rzecz biorąc, we wszystkich przypadkach, gdy w zdecentralizowanej sieci należy wybrać losowego uczestnika, PVRB jest prawie zawsze najlepszym wyborem, a nie opcją deterministyczną opartą na przykład na haszu bloku. Bez PVRB możliwość wpływania na wybór uczestnika prowadzi do ataków, w których atakujący może wybierać spośród wielu przyszłości, aby wybrać kolejnego skorumpowanego uczestnika lub kilka na raz, aby zapewnić większy udział w decyzji. Stosowanie PVRB dyskredytuje tego typu ataki.
Skalowanie i równoważenie obciążenia
PVRB może być również bardzo przydatny w zadaniach takich jak redukcja obciążenia i skalowanie płatności. Na początek warto się zapoznać Rivesta „Elektroniczne losy na loterię jako mikropłatności”. Ogólna koncepcja jest taka, że zamiast dokonywać 100 wpłat 1c od płatnika na rzecz odbiorcy, można zagrać w uczciwą loterię z nagrodą 1$ = 100c, gdzie wpłacający przekazuje bankowi po jednym ze 1 swoich „biletów na loterię” za każdy 100c płatność. Jeden z tych losów wygrywa słoik o wartości 1 dolara i to właśnie ten bilet odbiorca może zapisać w blockchainie. Najważniejsze jest to, że pozostałych 99 biletów jest przesyłanych pomiędzy odbiorcą a płatnikiem bez udziału zewnętrznego, kanałem prywatnym i z dowolną prędkością. Można przeczytać dobry opis protokołu opartego na tym schemacie w sieci Emercoin .
Schemat ten ma kilka problemów, np. odbiorca może przestać obsługiwać płatnika natychmiast po otrzymaniu zwycięskiego biletu, ale w przypadku wielu zastosowań specjalnych, takich jak naliczanie minutowe lub elektroniczne abonamenty na usługi, można je pominąć. Głównym wymogiem jest oczywiście uczciwość loterii, a do jej realizacji absolutnie niezbędny jest PVRB.
Wybór losowego uczestnika jest również niezwykle ważny w przypadku protokołów shardingu, których celem jest poziome skalowanie łańcucha bloków, umożliwiając różnym BP przetwarzanie tylko ich zakresu transakcji. Jest to niezwykle trudne zadanie, szczególnie pod względem bezpieczeństwa podczas łączenia fragmentów. Sprawiedliwy wybór losowego BP w celu przypisania osób odpowiedzialnych za konkretny fragment, podobnie jak w algorytmach konsensusu, jest również zadaniem PVRB. W systemach scentralizowanych fragmenty są przydzielane przez moduł równoważący, który po prostu oblicza skrót na podstawie żądania i wysyła go do wymaganego modułu wykonującego. W blockchainach możliwość wpływania na to przypisanie może prowadzić do ataku na konsensus. Na przykład zawartość transakcji może być kontrolowana przez osobę atakującą, może on kontrolować, które transakcje trafiają do kontrolowanego przez niego sharda i manipulować znajdującym się w nim łańcuchem bloków. Możesz przeczytać dyskusję na temat problemu używania liczb losowych do zadań shardingu w Ethereum
Sharding to jeden z najambitniejszych i najpoważniejszych problemów w dziedzinie blockchain, a jego rozwiązanie pozwoli na budowę zdecentralizowanych sieci o fantastycznej wydajności i objętości. PVRB to tylko jedna z ważnych blokad umożliwiających rozwiązanie tego problemu.
Gry, protokoły gospodarcze, arbitraż
Rola liczb losowych w branży gier jest trudna do przecenienia. Wyraźne użycie w kasynach online i ukryte użycie przy obliczaniu efektów działania gracza to niezwykle trudne problemy w przypadku zdecentralizowanych sieci, w których nie można polegać na centralnym źródle losowości. Jednak losowy wybór może również rozwiązać wiele problemów ekonomicznych i pomóc w tworzeniu prostszych i bardziej wydajnych protokołów. Załóżmy, że w naszym protokole występują spory dotyczące zapłaty za niektóre niedrogie usługi, a spory te zdarzają się dość rzadko. W takim przypadku, jeśli istnieje niekwestionowany PVRB, klienci i sprzedawcy mogą zgodzić się na rozstrzyganie sporów losowo, ale z określonym prawdopodobieństwem. Na przykład z prawdopodobieństwem 60% wygrywa klient i z prawdopodobieństwem 40% wygrywa sprzedawca. Takie podejście, z pierwszego punktu widzenia absurdalne, pozwala na automatyczne rozstrzyganie sporów z precyzyjnie przewidywalnym udziałem wygranych/przegranych, co odpowiada obu stronom, bez udziału strony trzeciej i niepotrzebnej straty czasu. Co więcej, współczynnik prawdopodobieństwa może być dynamiczny i zależeć od pewnych zmiennych globalnych. Przykładowo, jeśli firma dobrze sobie radzi, ma małą liczbę sporów i wysoką rentowność, może automatycznie przesunąć prawdopodobieństwo rozwiązania sporu w stronę klientocentryzmu, np. 70/30 lub 80/20 i odwrotnie, jeśli spory pochłaniają dużo pieniędzy i są oszukańcze lub nieodpowiednie, możesz przesunąć prawdopodobieństwo w innym kierunku.
Duża liczba interesujących zdecentralizowanych protokołów, takich jak rejestry sterowane tokenami, rynki prognostyczne, krzywe więzi i wiele innych, to gry ekonomiczne, w których dobre zachowanie jest nagradzane, a złe zachowanie jest karane. Często zawierają problemy związane z bezpieczeństwem, w przypadku których zabezpieczenia są ze sobą sprzeczne. To, co jest chronione przed atakiem „wielorybów” za pomocą miliardów tokenów („duża stawka”), jest podatne na ataki tysięcy kont z małymi saldami („stawka sybil”) oraz środki podjęte przeciwko pojedynczemu atakowi, takie jak nie- Opłaty liniowe tworzone w celu uczynienia pracy z dużą stawką nieopłacalną są zwykle dyskredytowane przez kolejny atak. Ponieważ mówimy o grze ekonomicznej, można z góry obliczyć odpowiednie wagi statystyczne i po prostu zastąpić prowizje losowymi z odpowiednim rozkładem. Takie probabilistyczne prowizje realizuje się niezwykle prosto, jeśli blockchain ma wiarygodne źródło losowości i nie wymaga skomplikowanych obliczeń, utrudniających życie zarówno wielorybom, jak i sybilom.
Jednocześnie należy w dalszym ciągu pamiętać, że kontrola nad pojedynczym bitem w tej losowości pozwala oszukiwać, zmniejszając i zwiększając prawdopodobieństwa o połowę, dlatego uczciwy PVRB jest najważniejszym elementem takich protokołów.
Gdzie znaleźć odpowiedni losowy?
Teoretycznie uczciwy losowy wybór w zdecentralizowanych sieciach sprawia, że prawie każdy protokół jest w sposób udowodniony bezpieczny przed zmową. Uzasadnienie jest dość proste — jeśli sieć zgadza się na pojedynczy bit 0 lub 1, a mniej niż połowa uczestników jest nieuczciwa, to przy wystarczającej liczbie iteracji sieć ma gwarancję osiągnięcia konsensusu w sprawie tego bitu ze stałym prawdopodobieństwem. Po prostu dlatego, że uczciwy losowiec wybierze 51 ze 100 uczestników w 51% przypadków. Ale to teoretycznie, bo... w prawdziwych sieciach, aby zapewnić taki poziom bezpieczeństwa jak w artykułach, wymagana jest duża liczba wiadomości między hostami, złożona kryptografia wieloprzebiegowa, a każda komplikacja protokołu natychmiast dodaje nowe wektory ataku.
Dlatego nie widzimy jeszcze w blockchainach sprawdzonego, odpornego PVRB, który byłby używany wystarczająco długo, aby został przetestowany przez rzeczywiste aplikacje, wielokrotne audyty, obciążenia i oczywiście prawdziwe ataki, bez których trudno nazwać produkt naprawdę bezpieczny.
Istnieje jednak kilka obiecujących podejść, różnią się one wieloma szczegółami i jedno z nich na pewno rozwiąże problem. Dzięki nowoczesnym zasobom obliczeniowym teorię kryptografii można dość sprytnie przełożyć na praktyczne zastosowania. W przyszłości chętnie porozmawiamy o implementacjach PVRB: obecnie jest ich kilka, każda ma swój własny zestaw ważnych właściwości i cech implementacyjnych, a za każdą stoi dobry pomysł. W randomizację zaangażowanych jest niewiele zespołów, a doświadczenie każdego z nich jest niezwykle ważne dla pozostałych. Mamy nadzieję, że nasze informacje pozwolą innym zespołom działać szybciej, biorąc pod uwagę doświadczenia swoich poprzedników.
Źródło: www.habr.com