Verifioitavat satunnaisfunktiot konsensuksessa

Konsensusprotokollat tarvitsevat satunnaisuutta johtajien valintaan, komiteoiden valintaan ja shardien määritykseen. Satunnaisuuden on täytettävä kolme ominaisuutta: ennustamattomuus (kukaan ei voi ennustaa tulosta ennen sen paljastamista), vinoutumattomuus (mikään osallistuja ei voi manipuloida tulosta edukseen) ja julkinen todennettavuus (kuka tahansa voi todentaa tuloksen oikeellisuuden luottamatta sen tuottajaan). Naiivit lähestymistavat epäonnistuvat: yhden solmun satunnaislukua voidaan manipuloida, ja commit-reveal-menetelmät mahdollistavat viimeisen paljastajan aiheuttaman vinouman. Verifiable Random Functions (VRF) ratkaisevat kaikki kolme vaatimusta.

Verifiable Random Function (VRF), jonka Micali, Rabin ja Vadhan esittelivät vuonna 1999, on pseudorandom-funktio, joka tarjoaa oikeellisuustodisteen. VRF:llä on kolme algoritmia: KeyGen luo avainparin (SK, PK); Prove(SK, alpha) tuottaa parin (beta, pi), jossa beta on tuloste ja pi on todiste; ja Verify(PK, alpha, beta, pi) palauttaa arvon valid tai invalid. Tuloste beta on erottamaton satunnaisesta kenelle tahansa, joka ei tunne SK:ta (VRF:n pseudorandomisuus), ja todistetta pi ei voi väärentää (VRF:n yksikäsitteisyys). Todisteen koko on O(1) — vakio syötteestä riippumatta.

Laajimmin käytössä oleva VRF-rakenne on ECVRF (IETF RFC 9381), joka perustuu elliptisen käyrän diskreetin logaritmin ongelman vaikeuteen. Kun käytettävissä ovat yksityinen avain x ja syöte alpha, todistaja laskee H = hash-to-curve(PK, alpha) (muuntaen alphan käyrän pisteeksi) ja sitten gamma = x * H (skalaarikertolasku). VRF:n tuloste beta = keccak(gamma). Todiste pi käyttää Schnorrin kaltaista nollatietotodistusta: todistaja sitoutuu satunnaiseen k:hon, laskee haasteen c = hash(H, gamma, k*G, k*H), vastauksen s = k - c*x ja tuottaa pi = (gamma, c, s). Todennuksessa tarkistetaan Schnorrin yhtälöt ja lasketaan beta uudelleen.

Algorand (Silvio Micali ym., 2017) oli ensimmäisiä lohkoketjukonsensuksia, joissa VRF:ää hyödynnettiin. Jokaisella kierroksella jokainen validaattori laskee yksityisesti arvon VRF(SK, round || seed) saadakseen satunnaistuloksen. Tulosta verrataan kynnysarvoon: jos VRF_output < stake_fraction * threshold, validaattori valitaan toimikunnan jäseneksi tai lohkon ehdottajaksi. Vain validaattori itse tietää valinnastaan, kunnes hän lähettää lohkonsa tai äänensä verkkoon yhdessä VRF-todisteen kanssa. Tämä kryptografinen itsevalinta poistaa julkisen johtajan valinnan tarpeen ja tekee Algorandista vastustuskykyisen tunnettuihin tuleviin johtajiin kohdistuvia kohdennettuja palvelunestohyökkäyksiä vastaan.

Cardanon Ouroboros Praos (nykyinen käytössä oleva versio) käyttää VRF:iä slotin johtajan valintaan. Jokaisella epochilla lohkoketjusta johdetaan uusi satunnainen siemen. Jokainen stake pool -operaattori (SPO) laskee VRF(SK, slot || epoch_seed) -arvon jokaiselle epochin slotille. Jos tulos alittaa operaattorin panokseen suhteutetun kynnysarvon, operaattori on slotin johtaja ja saa tuottaa lohkon. VRF-todiste sisällytetään lohkon otsakkeeseen, joten kuka tahansa voi todentaa, että SPO valittiin asianmukaisesti. Tämä antaa Cardanolle todistettavan suojan adaptiivisia vastustajia vastaan, vaikka nämä saisivat johtajien aikataulun selville kesken epochin.

Ethereum käyttää satunnaisuuslähteenä RANDAOta (kumulatiivisia BLS-allekirjoituksia) VRF:ien sijaan. RANDAO on yksinkertaisempi — BLS:n lisäksi ei tarvita muuta kryptografista primitiiviä — mutta se on altis viimeisen paljastajan vinoumalle: lohkon ehdottaja, joka voi ennakoida RANDAO-osuutensa johtavan epäedulliseen tulokseen, voi jättää lohkonsa julkaisematta (menettäen lohkopalkkion). VRF-pohjainen valinta pitää valitun osapuolen henkilöllisyyden salassa siihen asti, että tämä ilmoittaa itsestään, joten tämä hyökkäysreitti poistuu kokonaan. Kompromissina VRF lisää kryptografista monimutkaisuutta (hash-to-curve ja todisteen muodostaminen), kun taas RANDAO hyödyntää olemassa olevaa BLS-infrastruktuuria.

Chainlink VRF tarjoaa älysopimuksille todennettavaa satunnaisuutta palveluna. Kuluttajasopimus pyytää satunnaisuutta maksamalla LINK-tokeneita. Chainlinkin oraakkelisolmulla on hallussaan VRF-avainpari. Solmu laskee arvon ECVRF(SK, seed), jossa seed johdetaan lohkon tiivisteestä ja käyttäjän antamasta nonce-arvosta, ja lähettää arvot (beta, pi) ketjuun. VRF-koordinaattorisopimus todentaa todisteen ennen satunnaistuloksen välittämistä kuluttajasopimukselle. Näin älysopimukset saavat käyttöönsä manipulointia kestävää satunnaisuutta ilman, että ketjuun tarvitsee toteuttaa natiivia VRF-satunnaisuuslähdettä — tämä on hyödyllistä NFT-lyönneissä, arpajaisissa ja peleissä.

Signal Protocol käyttää VXEdDSA:ta (Verifiable X25519 EdDSA), Curve25519-käyrän päällä toimivaa VRF-konstruktiota. Kun lähettäjä luo kertakäyttöisen prekey-allekirjoituksen, VRF:n avulla viestistä ja lähettäjän avaimesta tuotetaan deterministinen mutta ennustamaton nonce. Tämä estää noncen uudelleenkäytön (joka murtaisi EdDSA:n turvallisuuden) ja pitää samalla allekirjoitukset todennettavina. VRF-todisteen avulla vastaanottaja voi todentaa, että nonce johdettiin oikein, mikä estää lähettäjää valitsemasta haitallista nonce-arvoa, joka voisi mahdollistaa avaimen palauttamiseen johtavia hyökkäyksiä. VXEdDSA osoittaa, että VRF:t ovat yleiskäyttöinen kryptografinen työkalu myös konsensuksen ulkopuolella.

Verifioitavat viivefunktiot (VDF:t) sekoitetaan joskus VRF:iin. VDF edellyttää peräkkäistä laskentaa vähintään T askeleen ajan (aikalukko-ominaisuus) ja tuottaa tuloksen sekä lyhyen oikeellisuustodisteen. VDF:iä käytetään RANDAO:n viimeisen paljastajan vinouman torjumiseen: Ethereumiin suunniteltu VDF-kerros tekisi jokaisesta manipulointiyrityksestä etukäteen suoritettavan VDF:n edellyttämän hyökkäyksen, ja sen suorittaminen kestäisi hyökkäysikkunaa kauemmin. VRF:t mahdollistavat välittömän yksityisen laskennan, kun taas VDF:t mahdollistavat julkisen mutta hitaan laskennan. Ne täydentävät toisiaan: VDF:t estävät viimeisen paljastajan vinouman, VRF:t estävät johtajan ennustamisen.

VRF-valinta parantaa turvallisuutta merkittävästi adaptiivisia vastustajia vastaan. PBFT:ssä ja Tendermintissa johtajan henkilöllisyys tiedetään etukäteen (round-robin-aikataulun perusteella), joten vastustaja voi kohdistaa DDoS-hyökkäyksen seuraavaan johtajaan ennen tämän ehdotusta. VRF-pohjainen valinta (Algorand, Cardano) pitää johtajan henkilöllisyyden salassa lohkon julkaisemiseen asti — silloin lohko on jo ehdotettu, joten DDoS-hyökkäys saapuu liian myöhään. Tätä kutsutaan adaptiiviseksi turvallisuudeksi tai ennustamattomaksi johtajan valinnaksi. Tämän mahdollistava kryptografinen ominaisuus on se, että VRF:n tulos näyttää pseudosatunnaiselta kaikille, joilla ei ole yksityistä avainta.

VRF:ien oikea toteutus edellyttää huolellisuutta useissa kohdissa. Hash-to-curve-menetelmän on käytettävä vakioajan ja tasaisen jakauman tuottavaa algoritmia (IETF:n RFC 9380 määrittelee standardoidut menetelmät ajoitusvuotojen estämiseksi). Todisteessa käytettävä VRF:n nonce k on johdettava deterministisesti arvosta (SK, alpha) RFC 6979:n avulla — k:n uudelleenkäyttö tai heikon satunnaisen k:n käyttö paljastaa salaisen avaimen (sama haavoittuvuus kuin ECDSA:n noncen uudelleenkäytössä). ECVRF-P256-SHA256-TAI:n todisteen koko on 80 tavua ja ECVRF-ED25519-SHA512-ELL2:n todisteen koko on 80 tavua — molemmat soveltuvat ketjuun sisällytettäviksi. VRF:n yksikäsitteisyysominaisuus takaa, ettei samalle (SK, alpha) -parille ole olemassa kahta kelvollista todistetta.

VRF:t tuottavat pseudosatunnaisia tuloksia, joihin liittyy kryptografinen oikeellisuustodiste, ja täyttävät ennustamattomuuden, vääristämättömyyden ja julkisen todennettavuuden vaatimukset. ECVRF (RFC 9381) on elliptisille käyrille perustuva standardikonstruktio. Algorand käyttää VRF-pohjaista kryptografista itsevalintaa suojautuakseen adaptiivisilta vastustajilta. Cardanon Ouroboros Praos käyttää VRF:iä kunkin slotin johtajan valintaan. Chainlink VRF tarjoaa älysopimuksille todennettavaa satunnaisuutta. VRF:t täydentävät VDF:iä (jotka torjuvat viimeisen paljastajan vinoumaa) ja eroavat RANDAEsta (joka käyttää kumulatiivisia BLS-allekirjoituksia ja jonka tunnettu heikkous liittyy viimeiseen paljastajaan).