Verifierbara slumpfunktioner i konsensus

Konsensusprotokoll kräver slumpmässighet för ledarval, kommittéurval och shardtilldelning. Slumpmässigheten måste uppfylla tre egenskaper: oförutsägbarhet (ingen kan förutsäga utfallet innan det avslöjas), obiaserbarhet (ingen deltagare kan manipulera utfallet till sin fördel) och offentlig verifierbarhet (vem som helst kan verifiera att utfallet är korrekt utan att lita på den som genererade det). Naiva metoder misslyckas: en enda nods slumptal kan manipuleras, och commit-reveal-scheman tillåter att den som avslöjar sist påverkar utfallet. Verifiable Random Functions (VRF) uppfyller alla tre kraven.

En Verifiable Random Function (VRF), som introducerades av Micali, Rabin och Vadhan 1999, är en pseudoslumpfunktion som tillhandahåller ett korrekthetsbevis. En VRF har tre algoritmer: KeyGen genererar ett nyckelpar (SK, PK); Prove(SK, alpha) producerar (beta, pi), där beta är outputen och pi är ett bevis; och Verify(PK, alpha, beta, pi) returnerar valid eller invalid. Outputen beta kan inte skiljas från slumpmässighet av någon som inte känner till SK (VRF-pseudoslumpmässighet), och beviset pi är oförfalskbart (VRF-unikhet). Bevisets storlek är O(1) — konstant oavsett indata.

Den mest använda VRF-konstruktionen är ECVRF (IETF RFC 9381), som bygger på svårigheten hos diskreta logaritmer på elliptiska kurvor. Givet en privat nyckel x och indata alpha beräknar bevisföraren H = hash-to-curve(PK, alpha) (avbildar alpha till en kurvpunkt) och därefter gamma = x * H (skalärmultiplikation). VRF-outputen beta = keccak(gamma). Beviset pi använder ett Schnorr-liknande nollkunskapsargument: bevisföraren binder sig till ett slumpmässigt k, beräknar utmaningen c = hash(H, gamma, k*G, k*H), svaret s = k - c*x och producerar pi = (gamma, c, s). Verifieringen kontrollerar Schnorr-ekvationerna och beräknar beta på nytt.

Algorand (Silvio Micali et al., 2017) var först med att använda VRF i blockkedjekonsensus. I varje omgång utvärderar varje validator i hemlighet VRF(SK, round || seed) för att få ett slumpmässigt resultat. Resultatet jämförs med en tröskel: om VRF_output < stake_fraction * threshold väljs validatorn till kommittémedlem eller blockproposerare. Endast validatorn känner till att den har valts tills den publicerar sitt block eller sin röst tillsammans med VRF-beviset. Denna kryptografiska självselektering eliminerar behovet av ett offentligt ledarval och gör Algorand motståndskraftigt mot riktade överbelastningsattacker mot kända kommande ledare.

Cardanos Ouroboros Praos (den aktuella versionen i drift) använder VRF:er för val av slotledare. För varje epoch härleds ett nytt slumpmässigt seed från blockkedjan. Varje stakepool-operatör (SPO) utvärderar VRF(SK, slot || epoch_seed) för varje slot i epoken. Om resultatet underskrider en tröskel som är proportionell mot operatörens insats blir denne slotledare och får producera ett block. VRF-beviset inkluderas i blockhuvudet, vilket gör det möjligt för vem som helst att verifiera att SPO:n valdes på legitim grund. Detta ger Cardano bevisbar säkerhet mot adaptiva angripare som lär sig ledarschemat mitt under en epoch.

Ethereum använder RANDAO (ackumulerade BLS-signaturer) i stället för VRF:er som slumphetskälla. RANDAO är enklare – ingen ytterligare kryptografisk primitiv behövs utöver BLS – men är känsligt för bias från den sista avslöjaren: en blockproposerare som kan förutse att dess RANDAO-bidrag skulle ge ett ogynnsamt resultat kan undanhålla sitt block (på bekostnad av blockbelöningen). VRF-baserat val döljer vem som har valts tills denne avslöjar sig, vilket helt eliminerar denna angreppsmöjlighet. Avvägningen är att VRF medför kryptografisk komplexitet (hash-to-curve och bevisgenerering), medan RANDAO återanvänder befintlig BLS-infrastruktur.

Chainlink VRF tillhandahåller verifierbar slumpmässighet som en tjänst för smarta kontrakt. Ett konsumentkontrakt begär slumpmässighet genom att betala LINK-tokens. En Chainlink-orakelnod har ett VRF-nyckelpar. Noden utvärderar ECVRF(SK, seed), där seed härleds från blockhashen och en nonce som användaren tillhandahåller, och skickar sedan (beta, pi) till kedjan. VRF-koordinatoravtalet verifierar beviset innan det vidarebefordrar det slumpmässiga resultatet till konsumenten. Detta ger smarta kontrakt tillgång till manipulationsresistent slumpmässighet utan att kedjan behöver implementera en inbyggd VRF-slumphetskälla – användbart för NFT-prägling, lotterier och spel.

Signal Protocol använder VXEdDSA (Verifiable X25519 EdDSA), en VRF-konstruktion över Curve25519. När en avsändare genererar en signatur för en förnyckel för engångsbruk används VRF för att skapa en deterministisk men oförutsägbar nonce från meddelandet och avsändarens nyckel. Detta förhindrar återanvändning av nonce (vilket skulle bryta EdDSA:s säkerhet) samtidigt som signaturerna förblir verifierbara. VRF-beviset gör det möjligt för mottagaren att verifiera att nonce härleddes korrekt, vilket hindrar avsändaren från att välja en skadlig nonce som skulle kunna möjliggöra attacker för att återvinna nyckeln. VXEdDSA visar att VRF:er är ett allmänt kryptografiskt verktyg även utanför konsensus.

Verifierbara fördröjningsfunktioner (VDF:er) förväxlas ibland med VRF:er. En VDF kräver sekventiell beräkning i minst T steg (egenskapen tidslås) och producerar ett resultat med ett kort korrekthetsbevis. VDF:er används för att motverka bias från den sista avslöjaren i RANDAO: Ethereums planerade VDF-lager skulle göra att varje manipulationsförsök kräver att en VDF körs i förväg, vilket tar längre tid än attackfönstret. VRF:er ger omedelbar privat utvärdering, medan VDF:er ger långsam offentlig utvärdering. De kompletterar varandra: VDF:er förhindrar bias från den sista avslöjaren och VRF:er förhindrar förutsägelse av ledaren.

VRF-urval ger en viktig säkerhetsförbättring mot adaptiva angripare. I PBFT och Tendermint är ledarens identitet känd i förväg enligt ett round-robin-schema, vilket gör det möjligt för en angripare att utsätta nästa ledare för en DDoS-attack innan denne föreslår ett block. VRF-baserat val (Algorand, Cardano) håller ledarens identitet hemlig tills blocket publiceras – då har blocket redan föreslagits, så en DDoS-attack kommer för sent. Detta kallas adaptiv säkerhet eller oförutsägbart ledarval. Den kryptografiska egenskap som möjliggör detta är att VRF-resultatet är pseudorandomiserat för alla som saknar den privata nyckeln.

Korrekt implementering av VRF:er kräver omsorg på flera punkter. Hash-to-curve måste använda en algoritm med konstant tidsåtgång och jämn fördelning (IETF RFC 9380 definierar standardiserade metoder för att förhindra tidsläckor). VRF-nonce k i beviset måste härledas deterministiskt från (SK, alpha) med RFC 6979 – om k återanvänds eller om ett svagt slumpmässigt k används läcker den hemliga nyckeln (samma sårbarhet som vid återanvändning av nonce i ECDSA). Bevisstorleken för ECVRF-P256-SHA256-TAI är 80 byte och för ECVRF-ED25519-SHA512-ELL2 är den 80 byte – båda lämpar sig för inkludering i kedjan. VRF:ens unikhetsegenskap garanterar att det inte finns två giltiga bevis för samma par (SK, alpha).

VRF:er producerar pseudorandomiserade resultat med kryptografiska korrekthetsbevis och uppfyller därmed kraven på oförutsägbarhet, obiaserbarhet och offentlig verifierbarhet. ECVRF (RFC 9381) är standardkonstruktionen över elliptiska kurvor. Algorand använder kryptografisk självselektering med VRF för att stå emot adaptiva angripare. Cardano Ouroboros Praos använder VRF:er för ledarval för varje slot. Chainlink VRF tillhandahåller verifierbar slumpmässighet till smarta kontrakt. VRF:er kompletterar VDF:er (som hanterar bias från den sista avslöjaren) och står i kontrast till RANDAO (som använder ackumulerade BLS-signaturer och har en känd svaghet i form av bias från den sista avslöjaren).