losowaliczba.pl

Losowanie, któremu nie trzeba wierzyć na słowo: jak działa drand

Zwykłemu losowaniu w internecie trzeba uwierzyć na słowo. Weryfikowalne losowanie zostawia dowód, czyli zapis, z którego każdy może sam przeliczyć wynik. Pokazujemy, skąd bierze się losowa wartość, której nikt nie zna przed losowaniem, i czego dowód nie jest w stanie potwierdzić.

Losowanie, któremu trzeba ufać

Kiedy strona losuje liczbę, widzisz tylko wynik. Nie wiesz, czy był to pierwszy rzut, czy dziesiąty. Nie wiesz też, czy ktoś po drodze nie zamienił go na wygodniejszy. Gdy losujecie, kto zmywa naczynia, nie ma to znaczenia. Przy konkursie z nagrodą, przy kolejności wystąpień albo w sporze przez internet ma już duże.

Weryfikowalne losowanie (ang. provably fair) odwraca tę sytuację. Zamiast zaufania wystarcza dowód. Wynik powstaje z losowej wartości, którą ogłasza się publicznie, ale dopiero po rozpoczęciu losowania. Wcześniej nie znał jej nikt, także właściciel strony. Potem każdy może sam powtórzyć obliczenia i sprawdzić wynik. Zacznijmy od tego, skąd biorą się takie publiczne losowe wartości.

Publiczna losowość: sieć drand

W serwisie losowaliczba.pl ich źródłem jest sieć drand. To rozproszona „radiolatarnia losowości” (ang. randomness beacon), czyli usługa, która w równych odstępach czasu ogłasza światu nową losową wartość. Siecią zarządza League of Entropy, grupa niezależnych organizacji: uczelni, firm i fundacji. Każda z nich utrzymuje własny węzeł, czyli serwer biorący udział we wspólnym losowaniu.

Serwis korzysta z quicknet, jednej z sieci drand. Co 3 sekundy odbywa się w niej nowe losowanie, nazywane rundą. Każda runda ma swój kolejny numer. Węzły wspólnie podpisują ten numer podpisem cyfrowym, czyli matematycznym potwierdzeniem, którego nie da się podrobić. Każdy węzeł dokłada tylko fragment podpisu. Gotowy podpis da się złożyć dopiero wtedy, gdy zbierze się wymagana liczba fragmentów, czyli próg. Taki podpis nazywa się podpisem progowym BLS. Na koniec z podpisu wylicza się skrót SHA-256, czyli krótki „odcisk palca” danych. Ten skrót jest losową wartością rundy.

Z takiej budowy wynikają trzy ważne cechy:

  • Nikt nie zna wyniku rundy z góry. Pojedynczy węzeł ma tylko swój fragment podpisu. Żeby poznać wynik przyszłej rundy przed czasem, musiałaby się zmówić co najmniej progowa liczba niezależnych uczestników.
  • Nikt nie podmieni wyniku rundy. Sieć ma jawny klucz publiczny, którym każdy może sprawdzić podpis. Dla danej rundy istnieje tylko jeden poprawny podpis. Nie da się więc podstawić innej losowej wartości.
  • Runda ma ustalony czas. Rundy pojawiają się regularnie co 3 sekundy od uruchomienia sieci. Z numeru rundy wynika więc moment jej publikacji, a z numeru zapisanego w dowodzie widać, kiedy losowano.

Trzy kroki weryfikowalnego losowania

Sama publiczna losowość jeszcze nie wystarczy. Gdyby strona mogła sięgnąć po dowolną rundę, wybrałaby taką, której znany już wynik jej odpowiada. Dlatego musi z góry wskazać przyszłą rundę, zanim ktokolwiek pozna jej wynik. Całe losowanie przebiega w trzech krokach.

  1. Zobowiązanie. Zanim cokolwiek zostanie wylosowane, strona wybiera najbliższą rundę, której jeszcze nie ma. Ta runda pojawi się najpóźniej za około 3 sekundy. Od tej chwili wynik jest przesądzony, choć nikt go jeszcze nie zna.
  2. Oczekiwanie. Sieć publikuje wybraną rundę. Strona pobiera jej dane i sprawdza podpis.
  3. Wyliczenie. Wynik powstaje z losowej wartości rundy według jawnego przepisu. Generator liczb wylicza z niej kolejne porcje danych, nazywane blokami. Każdy blok to skrót SHA-256 z trzech rzeczy: nazwy strumienia, losowej wartości rundy i numeru bloku. Nazwa strumienia to stały napis, inny dla każdego narzędzia. Program zamienia potem blok na liczbę z wybranego zakresu metodą odrzucania: blok, który dałby nierówne szanse, odrzuca i bierze następny. Dlaczego nie wystarczy zwykła reszta z dzielenia (modulo), wyjaśniamy w artykule o stronniczości modulo. Ta sama runda i te same ustawienia zawsze dają ten sam wynik.

Nazwa strumienia, na przykład losowaliczba-number-drand-v1, oddziela od siebie narzędzia. Dzięki niej z tej samej rundy powstają dwa różne, niezależne ciągi liczb: jeden dla kostki, drugi dla generatora liczb.

Wszystkie trzy kroki możesz przejść poniżej na prawdziwej rundzie:

Losowanie liczby od 1 do 100 krok po kroku

Demonstracja wykonuje prawdziwe weryfikowalne losowanie, tak samo jak generator liczb w trybie „Weryfikowalne”, i pokazuje każdy krok. Potrzebuje połączenia z siecią drand i trwa kilka sekund.

Co sprawdza weryfikacja

Po losowaniu zostaje dowód. To plik JSON, czyli zwykły tekst w uporządkowanym formacie. Zawiera numer rundy, jej losową wartość i podpis, a także ustawienia losowania i wynik. Gdy wkleisz go na stronie weryfikacji losowania, przeglądarka wykona cztery kroki:

  • pobierze wskazaną rundę z sieci drand i sprawdzi jej podpis,
  • sprawdzi, czy losowa wartość zapisana w dowodzie zgadza się z wartością tej rundy,
  • sprawdzi, czy użyto dokładnie tej rundy, którą dowód podaje jako zobowiązanie,
  • przeliczy wynik z ustawień zapisanych w dowodzie i porówna go z podanym.

Jeśli ktoś zmieni cokolwiek, na przykład wynik, ustawienia albo numer rundy, weryfikacja się nie powiedzie. Nie musisz przy tym ufać losowaliczba.pl. Przepis jest jawny, więc wszystkie obliczenia możesz powtórzyć we własnym programie.

Czego dowód nie dowodzi

Dowód ma jednak swoje granice. Pokazuje, że wynik pochodzi z danej rundy i z zapisanych ustawień. Nie potwierdza natomiast, ż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. Przed takim nadużyciem chronią proste ustalenia:

  • 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. Losowanie z innej godziny łatwo więc wychwycić.
  • Ustalcie z góry ustawienia i listę, na przykład uczestników na kole fortuny.
  • Ważne losowania przeprowadzajcie na żywo i od razu udostępniajcie dowód.

Ta sama luka przez ponad ćwierć wieku budziła podejrzenia wobec krzywych eliptycznych NIST. To wzory używane w kryptografii, zatwierdzone przez amerykański instytut normalizacyjny NIST. Ich autorzy opublikowali ziarno, czyli wartość początkową, z której wyliczono parametry krzywych. Ziarno pokazywało, skąd wziął się wynik. Nie wykluczało jednak, że ktoś wybrał go spośród wielu prób. Więcej piszemy w artykule o zagadce krzywych NIST.

Szybkie czy weryfikowalne?

Na koniec praktyczny wybór. W trybie „Szybkie” losowanie odbywa się na Twoim urządzeniu. Liczby wylicza przeglądarka swoim kryptograficznie bezpiecznym generatorem, czyli takim, którego wyników nie da się przewidzieć (WebCrypto). Taki wynik jest tak samo losowy i nie wymaga internetu, ale nie zostaje po nim dowód. Tryb „Weryfikowalne” przydaje się wtedy, gdy wynikowi ma zaufać ktoś inny niż Ty. Znajdziesz go w narzędziach: generator liczb, koło fortuny, generator Lotto, rzut kostką, rzut monetą, losowanie kolejności i losowanie mikołajkowe.