Weryfikowalne funkcje losowe w konsensusie

Protokoły konsensusu wymagają losowości do wyboru lidera, wyboru komitetu i przydzielania shardów. Losowość musi spełniać trzy warunki: nieprzewidywalność (nikt nie może przewidzieć wyniku przed jego ujawnieniem), odporność na manipulację (unbiasability — żaden uczestnik nie może zmienić wyniku na swoją korzyść) oraz publiczną weryfikowalność (każdy może sprawdzić poprawność wyniku bez zaufania do generatora). Naiwne podejścia zawodzą: liczba losowa pojedynczego węzła może być zmanipulowana, a schematy commit-reveal pozwalają ostatniemu ujawniającemu wpłynąć na wynik. Verifiable Random Functions (VRF) spełniają wszystkie trzy wymagania.

Verifiable Random Function (VRF), wprowadzona przez Micaliego, Rabina i Vadhana w 1999 roku, to funkcja pseudolosowa, która dostarcza dowód poprawności. VRF obejmuje trzy algorytmy: KeyGen generuje parę kluczy (SK, PK); Prove(SK, alpha) tworzy (beta, pi), gdzie beta jest wynikiem, a pi dowodem; natomiast Verify(PK, alpha, beta, pi) zwraca valid lub invalid. Wynik beta jest nieodróżnialny od losowego dla każdego, kto nie zna SK (pseudolosowość VRF), a dowodu pi nie można podrobić (jednoznaczność VRF). Rozmiar dowodu wynosi O(1) — jest stały niezależnie od danych wejściowych.

Najczęściej wdrażaną konstrukcją VRF jest ECVRF (IETF RFC 9381), oparta na trudności problemu logarytmu dyskretnego na krzywych eliptycznych. Dla klucza prywatnego x i danych wejściowych alpha dowodzący oblicza H = hash-to-curve(PK, alpha) (odwzorowanie alpha na punkt krzywej), a następnie gamma = x * H (mnożenie skalarne). Wynik VRF beta = keccak(gamma). Dowód pi wykorzystuje argument wiedzy zerowej w stylu Schnorra: dowodzący zobowiązuje się do losowego k, oblicza wyzwanie c = hash(H, gamma, k*G, k*H), odpowiedź s = k - c*x, a następnie zwraca pi = (gamma, c, s). Weryfikacja sprawdza równania Schnorra i ponownie oblicza beta.

Algorand (Silvio Micali i in., 2017) był pionierem zastosowania VRF w konsensusie blockchaina. W każdej rundzie każdy walidator prywatnie oblicza VRF(SK, round || seed), aby uzyskać losowy wynik. Wynik jest porównywany z progiem: jeśli VRF_output < stake_fraction * threshold, walidator zostaje wybrany na członka komitetu lub proponującego blok. Tylko walidator zna swój wybór do chwili rozgłoszenia bloku lub głosu wraz z dowodem VRF. Ta kryptograficzna samoselekcja eliminuje potrzebę publicznego wyboru lidera, dzięki czemu Algorand jest odporny na ukierunkowane ataki typu denial-of-service na znanych przyszłych liderów.

Ouroboros Praos w Cardano (obecnie wdrożona wersja) używa VRF do wyboru lidera slotu. W każdej epoce z blockchaina wyprowadzane jest nowe losowe ziarno. Każdy operator puli stakingowej (SPO) oblicza VRF(SK, slot || epoch_seed) dla każdego slotu w epoce. Jeśli wynik jest niższy od progu proporcjonalnego do posiadanego udziału, operator zostaje liderem slotu i może utworzyć blok. Dowód VRF jest umieszczany w nagłówku bloku, dzięki czemu każdy może zweryfikować, że SPO został wybrany zgodnie z zasadami. Zapewnia to Cardano dowodliwe bezpieczeństwo przeciwko adaptacyjnym przeciwnikom, którzy poznają harmonogram liderów w trakcie epoki.

Ethereum używa RANDAO (sumy zgromadzonych podpisów BLS), a nie VRF, jako mechanizmu dostarczającego losowość. RANDAO jest prostsze — nie wymaga dodatkowego prymitywu kryptograficznego poza BLS — ale jest podatne na stronniczość ostatniego ujawniającego: proponujący blok, który może przewidzieć, że jego wkład do RANDAO doprowadzi do niekorzystnego wyniku, może wstrzymać publikację bloku (tracąc przy tym nagrodę za blok). Wybór oparty na VRF ukrywa, kto został wybrany, aż do chwili ujawnienia się, całkowicie eliminując tę możliwość ataku. Kompromis polega na tym, że VRF zwiększa złożoność kryptograficzną (hash-to-curve i generowanie dowodów), podczas gdy RANDAO ponownie wykorzystuje istniejącą infrastrukturę BLS.

Chainlink VRF udostępnia smart kontraktom weryfikowalną losowość jako usługę. Kontrakt korzystający z usługi żąda losowości, płacąc tokenami LINK. Węzeł wyroczni Chainlink posiada parę kluczy VRF. Węzeł oblicza ECVRF(SK, seed), gdzie seed jest wyprowadzane z hasha bloku i nonce dostarczonego przez użytkownika, a następnie przesyła (beta, pi) on-chain. Kontrakt koordynatora VRF weryfikuje dowód, zanim przekaże losowy wynik kontraktowi odbiorcy. Dzięki temu smart kontrakty uzyskują dostęp do odpornej na manipulacje losowości bez konieczności implementowania przez blockchain natywnego mechanizmu VRF — jest to przydatne przy wybijaniu NFT, loteriach i grach.

Signal Protocol używa VXEdDSA (Verifiable X25519 EdDSA), konstrukcji VRF opartej na Curve25519. Gdy nadawca generuje podpis jednorazowego klucza prekey, VRF służy do utworzenia deterministycznego, ale nieprzewidywalnego nonce na podstawie wiadomości i klucza nadawcy. Zapobiega to ponownemu użyciu nonce (które naruszyłoby bezpieczeństwo EdDSA), a jednocześnie zachowuje możliwość weryfikacji podpisów. Dowód VRF pozwala odbiorcy zweryfikować, że nonce został prawidłowo wyprowadzony, uniemożliwiając nadawcy wybranie złośliwego nonce, który mógłby umożliwić ataki prowadzące do odzyskania klucza. VXEdDSA pokazuje, że VRF jest ogólnym narzędziem kryptograficznym wykraczającym poza konsensus.

Weryfikowalne funkcje opóźniające (VDF) bywają mylone z VRF. VDF wymaga sekwencyjnych obliczeń przez co najmniej T kroków (właściwość blokady czasowej) i generuje wynik wraz z krótkim dowodem poprawności. VDF są używane do ograniczania stronniczości ostatniego ujawniającego w RANDAO: planowana warstwa VDF w Ethereum sprawiłaby, że każda próba manipulacji wymagałaby wcześniejszego uruchomienia VDF, co trwałoby dłużej niż okno ataku. VRF zapewnia natychmiastowe prywatne obliczenia, a VDF — publiczne powolne obliczenia. Technologie te się uzupełniają: VDF zapobiega stronniczości ostatniego ujawniającego, a VRF zapobiega przewidywaniu lidera.

Wybór za pomocą VRF zapewnia istotną poprawę bezpieczeństwa przeciwko adaptacyjnym przeciwnikom. W PBFT i Tendermint tożsamość lidera jest znana z wyprzedzeniem (harmonogram rotacyjny), co pozwala przeciwnikowi przeprowadzić atak DDoS na następnego lidera, zanim ten zaproponuje blok. Wybór oparty na VRF (Algorand, Cardano) utrzymuje tożsamość lidera w tajemnicy aż do rozgłoszenia bloku — w tym momencie blok został już zaproponowany, więc atak DDoS następuje zbyt późno. Nazywa się to bezpieczeństwem adaptacyjnym lub nieprzewidywalnym wyborem lidera. Właściwość kryptograficzna, która to umożliwia, polega na tym, że wynik VRF jest pseudolosowy dla każdej osoby nieposiadającej klucza prywatnego.

Poprawna implementacja VRF wymaga zwrócenia uwagi na kilka kwestii. Hash-to-curve musi używać stałoczasowego algorytmu o rozkładzie jednostajnym (IETF RFC 9380 definiuje ustandaryzowane metody zapobiegające wyciekom informacji przez czas działania). Wartość VRF nonce k w dowodzie musi być deterministycznie wyprowadzana z (SK, alpha) za pomocą RFC 6979 — ponowne użycie k lub użycie słabego losowego k ujawnia klucz prywatny (jest to ta sama podatność co w przypadku ponownego użycia nonce w ECDSA). Rozmiar dowodu dla ECVRF-P256-SHA256-TAI wynosi 80 bajtów, a dla ECVRF-ED25519-SHA512-ELL2 również 80 bajtów — oba warianty nadają się do umieszczania on-chain. Właściwość jednoznaczności VRF gwarantuje, że dla tej samej pary (SK, alpha) nie istnieją dwa poprawne dowody.

Dlaczego wybór lidera oparty na VRF zapewnia silniejsze bezpieczeństwo niż wybór lidera według harmonogramu rotacyjnego?

VRF generuje pseudolosowe wyniki wraz z kryptograficznymi dowodami poprawności, zapewniając nieprzewidywalność, niemożność manipulowania rozkładem i publiczną weryfikowalność. ECVRF (RFC 9381) jest standardową konstrukcją opartą na krzywych eliptycznych. Algorand używa kryptograficznej samoselekcji opartej na VRF, aby zapewnić odporność na adaptacyjnych przeciwników. Cardano Ouroboros Praos używa VRF do wyboru lidera dla każdego slotu. Chainlink VRF udostępnia smart kontraktom weryfikowalną losowość. VRF uzupełnia VDF (które rozwiązują problem stronniczości ostatniego ujawniającego) i różni się od RANDAO (które używa zgromadzonych podpisów BLS i ma znaną słabość związaną z ostatnim ujawniającym).