Jak działa weryfikowalne losowanie i drand

Losowanie, któremu trzeba ufać

Kiedy strona losuje liczbę, widzisz tylko wynik. Nie wiesz, czy był to pierwszy rzut, czy dziesiąty, ani czy ktoś po drodze nie poprawił go na wygodniejszy. Przy wyborze, kto zmywa naczynia, to bez znaczenia. Przy konkursie z nagrodą, losowaniu kolejności wystąpień albo sporze przez internet – już tak.

Weryfikowalne losowanie (ang. provably fair) odwraca sytuację: zamiast prosić o zaufanie, daje dowód. Wynik wynika z publicznej losowości, której nikt nie znał przed losowaniem, i każdy może go przeliczyć sam.

Publiczna losowość: sieć drand

Źródłem tej losowości jest drand – rozproszona „radiolatarnia losowości” (ang. randomness beacon), którą prowadzi League of Entropy, grupa niezależnych organizacji: uczelni, firm i fundacji. Każda z nich utrzymuje własny węzeł sieci.

Sieć quicknet, z której korzysta losowaliczba.pl, co 3 sekundy publikuje nową, ponumerowaną rundę. Węzły tworzą ją wspólnie: każdy dokłada fragment podpisu, a gotowy podpis powstaje dopiero z fragmentów wymaganej liczby węzłów (tzw. podpis progowy BLS). Losowość rundy to skrót SHA-256 tego podpisu.

• Nikt nie zna rundy z góry. Pojedynczy węzeł ma tylko swój fragment. Żeby poznać albo zablokować przyszłą rundę, musiałaby się zmówić co najmniej progowa liczba niezależnych uczestników.
• Nikt nie podmieni rundy. Podpis każdy sprawdzi publicznym kluczem sieci, a dla danej rundy istnieje tylko jeden poprawny podpis. Nie da się więc wybrać innej losowości.
• Runda ma ustalony czas. Numer rundy wyznacza moment jej publikacji, więc z dowodu widać, kiedy losowano.

Trzy kroki weryfikowalnego losowania

1. Zobowiązanie. Zanim cokolwiek zostanie wylosowane, strona wybiera najbliższą rundę, której jeszcze nie ma – pojawi się najpóźniej za około 3 sekundy. Od tej chwili wynik jest przesądzony, ale nikt go jeszcze nie zna.
2. Oczekiwanie. Sieć publikuje wybraną rundę. Strona pobiera ją i sprawdza podpis.
3. Wyliczenie. Wynik powstaje z losowości rundy według jawnego przepisu. Generator liczb liczy na przykład kolejne bloki jako SHA-256 z nazwy strumienia, losowości i numeru bloku, a blok zamienia na liczbę z zakresu metodą odrzucania (o tym, dlaczego nie zwykłą resztą z dzielenia, piszemy w artykule o stronniczości modulo). Ta sama runda i te same ustawienia zawsze dają ten sam wynik.

Nazwa strumienia (np. losowaliczba-number-drand-v1) rozdziela narzędzia: z tej samej rundy kostka i generator liczb dostają różne, niezależne ciągi.

Co sprawdza weryfikacja

Dowód to plik JSON z numerem rundy, jej losowością i podpisem, ustawieniami losowania i wynikiem. Na stronie weryfikacji losowania przeglądarka:

• pobiera wskazaną rundę z sieci drand i sprawdza jej podpis,
• porównuje losowość z dowodu z losowością rundy,
• sprawdza, że użyto dokładnie tej rundy, do której strona się zobowiązała,
• przelicza wynik z ustawień zapisanych w dowodzie i porównuje go z podanym.

Zmiana czegokolwiek – wyniku, ustawień, numeru rundy – sprawia, że weryfikacja się nie powiedzie. Do sprawdzenia nie trzeba ufać losowaliczba.pl: przepis jest jawny i można go powtórzyć własnym programem.

Czego dowód nie dowodzi

Dowód potwierdza, że wynik wynika z danej rundy i danych ustawień. Nie potwierdza, że było to jedyne losowanie. Ktoś mógłby losować wiele razy, za każdym razem z inną rundą, i pokazać tylko wynik, który mu odpowiada. Dlatego:

• umówcie się wcześniej na godzinę losowania – dowód zawiera numer rundy i czas zobowiązania, a każda runda ma stały czas publikacji, więc losowanie z innej godziny łatwo wychwycić,
• ustalcie z góry listę i ustawienia, np. uczestników na kole fortuny,
• przy ważnych losowaniach losujcie na żywo i udostępnijcie dowód od razu.

Szybkie czy weryfikowalne?

Tryb „Szybkie” losuje lokalnie, kryptograficznie bezpiecznym generatorem przeglądarki (WebCrypto). Jest tak samo losowy i działa bez internetu, ale nie zostawia dowodu. Tryb „Weryfikowalne” przydaje się wtedy, gdy wynikowi ma zaufać ktoś inny niż Ty. Mają go generator liczb, koło fortuny, generator Lotto, rzut kostką, rzut monetą i losowanie kolejności.