Verifizierbare Zufallsfunktionen im Konsens

Konsensprotokolle benötigen Zufälligkeit für die Wahl von Leadern, die Auswahl von Komitees und die Zuweisung von Shards. Diese Zufälligkeit muss drei Eigenschaften erfüllen: Unvorhersagbarkeit (niemand kann die Ausgabe vor ihrer Veröffentlichung vorhersagen), Unbeeinflussbarkeit (kein Teilnehmer kann die Ausgabe zu seinem Vorteil manipulieren) und öffentliche Verifizierbarkeit (jeder kann die Korrektheit der Ausgabe überprüfen, ohne dem Erzeuger vertrauen zu müssen). Naive Ansätze scheitern: Die Zufallszahl eines einzelnen Knotens kann manipuliert werden, und bei Commit-Reveal-Verfahren kann der letzte Aufdecker die Ausgabe beeinflussen. Verifiable Random Functions (VRFs) erfüllen alle drei Anforderungen.

Eine Verifiable Random Function (VRF), die 1999 von Micali, Rabin und Vadhan eingeführt wurde, ist eine pseudozufällige Funktion, die einen Korrektheitsbeweis liefert. Eine VRF verfügt über drei Algorithmen: KeyGen erzeugt ein Schlüsselpaar (SK, PK); Prove(SK, alpha) erzeugt (beta, pi), wobei beta die Ausgabe und pi ein Beweis ist; und Verify(PK, alpha, beta, pi) liefert valid oder invalid zurück. Die Ausgabe beta ist für alle, die SK nicht kennen, nicht von einer Zufallszahl zu unterscheiden (VRF-Pseudozufälligkeit), und der Beweis pi ist nicht fälschbar (VRF-Eindeutigkeit). Die Beweisgröße ist O(1) – konstant unabhängig von der Eingabe.

Die am weitesten verbreitete VRF-Konstruktion ist ECVRF (IETF RFC 9381), die auf der Schwierigkeit des diskreten Logarithmus auf elliptischen Kurven basiert. Für einen privaten Schlüssel x und die Eingabe alpha berechnet der Beweiserzeuger H = hash-to-curve(PK, alpha), indem alpha auf einen Kurvenpunkt abgebildet wird, und anschließend gamma = x * H (Skalarmultiplikation). Die VRF-Ausgabe beta = keccak(gamma). Der Beweis pi verwendet ein Schnorr-ähnliches Zero-Knowledge-Argument: Der Beweiserzeuger legt sich auf ein zufälliges k fest, berechnet die Challenge c = hash(H, gamma, k*G, k*H), die Antwort s = k - c*x und gibt pi = (gamma, c, s) aus. Bei der Verifizierung werden die Schnorr-Gleichungen geprüft und beta erneut berechnet.

Algorand (Silvio Micali et al., 2017) war Vorreiter beim Einsatz von VRFs im Blockchain-Konsens. In jeder Runde berechnet jeder Validator privat VRF(SK, round || seed), um eine Zufallsausgabe zu erhalten. Die Ausgabe wird mit einem Schwellenwert verglichen: Gilt VRF_output < stake_fraction * threshold, wird der Validator als Komiteemitglied oder Block-Proposer ausgewählt. Nur der Validator kennt seine Auswahl, bis er seinen Block bzw. seine Abstimmung zusammen mit dem VRF-Beweis verbreitet. Diese kryptografische Selbstauswahl macht eine öffentliche Leader-Wahl überflüssig und schützt Algorand dadurch vor gezielten Denial-of-Service-Angriffen auf bekannte bevorstehende Leader.

Cardanos Ouroboros Praos (die aktuell eingesetzte Version) verwendet VRFs für die Wahl der Slot-Leader. In jeder Epoche wird aus der Blockchain ein neuer Zufalls-Seed abgeleitet. Jeder Stakepool-Betreiber (SPO) berechnet für jeden Slot der Epoche VRF(SK, slot || epoch_seed). Liegt die Ausgabe unter einem Schwellenwert, der proportional zu seinem Stake ist, ist er der Slot-Leader und darf einen Block erzeugen. Der VRF-Beweis ist im Block-Header enthalten, sodass jeder überprüfen kann, dass der SPO rechtmäßig gewählt wurde. Dadurch erhält Cardano beweisbare Sicherheit gegen adaptive Angreifer, die den Leader-Zeitplan innerhalb der Epoche erfahren.

Ethereum verwendet RANDAO (akkumulierte BLS-Signaturen) statt VRFs für sein Zufallsbeacon. RANDAO ist einfacher — es benötigt keine zusätzliche kryptografische Primitive über BLS hinaus —, ist aber anfällig für den Last-Revealer-Bias: Ein Block-Proposer, der vorhersehen kann, dass sein RANDAO-Beitrag ein ungünstiges Ergebnis hervorbringen würde, kann seinen Block zurückhalten (auf Kosten seiner Blockbelohnung). Die auf VRFs basierende Wahl verbirgt, wer gewählt wurde, bis diese Person sich zu erkennen gibt, und beseitigt diesen Angriffsvektor vollständig. Der Kompromiss: VRF bringt zusätzliche kryptografische Komplexität (Hash-to-curve, Beweiserzeugung) mit sich, während RANDAO die vorhandene BLS-Infrastruktur wiederverwendet.

Chainlink VRF bietet verifizierbare Zufälligkeit als Dienst für Smart Contracts. Ein Consumer-Contract fordert Zufälligkeit an, indem er LINK-Token bezahlt. Ein Chainlink-Orakelknoten verfügt über ein VRF-Schlüsselpaar. Der Knoten berechnet ECVRF(SK, seed), wobei seed aus dem Block-Hash und einem vom Nutzer bereitgestellten nonce abgeleitet wird, und übermittelt anschließend (beta, pi) on-chain. Der VRF-Koordinator-Contract überprüft den Beweis, bevor er die Zufallsausgabe an den Consumer weiterleitet. So erhalten Smart Contracts Zugriff auf manipulationsresistente Zufälligkeit, ohne dass die Blockchain ein natives VRF-Beacon implementieren muss – nützlich für das Minting von NFTs, Lotterien und Spiele.

Das Signal Protocol verwendet VXEdDSA (Verifiable X25519 EdDSA), eine VRF-Konstruktion über Curve25519. Wenn ein Sender eine Signatur für einen einmalig verwendeten Prekey erzeugt, wird die VRF verwendet, um aus der Nachricht und dem Senderschlüssel einen deterministischen, aber nicht vorhersagbaren Nonce zu erzeugen. Dies verhindert die Wiederverwendung von Nonces, die die Sicherheit von EdDSA beeinträchtigen würde, und sorgt zugleich dafür, dass die Signaturen verifizierbar bleiben. Der VRF-Beweis ermöglicht es dem Empfänger zu überprüfen, dass der Nonce korrekt abgeleitet wurde, und verhindert, dass der Sender einen manipulierten Nonce wählt, der Angriffe zur Schlüsselwiederherstellung ermöglichen könnte. VXEdDSA zeigt, dass VRFs auch über den Konsens hinaus ein vielseitiges kryptografisches Werkzeug sind.

Verifiable Delay Functions (VDFs) werden manchmal mit VRFs verwechselt. Eine VDF erfordert eine sequenzielle Berechnung über mindestens T Schritte (Zeitschloss-Eigenschaft) und erzeugt eine Ausgabe mit einem kurzen Korrektheitsbeweis. VDFs werden zur Abmilderung des Last-Revealer-Bias bei RANDAO eingesetzt: Die geplante VDF-Schicht von Ethereum würde dazu führen, dass jeder Manipulationsversuch die vorherige Berechnung einer VDF erfordert, die länger dauert als das Angriffsfenster. VRFs ermöglichen eine sofortige private Auswertung; VDFs eine langsame öffentliche Auswertung. Sie ergänzen einander: VDFs verhindern den Last-Revealer-Bias, VRFs die Vorhersage von Leadern.

Die Auswahl mittels VRF bietet eine wesentliche Sicherheitsverbesserung gegenüber adaptiven Angreifern. In PBFT und Tendermint ist die Identität des Leaders im Voraus bekannt (Round-Robin-Zeitplan), sodass ein Angreifer den nächsten Leader bereits vor dessen Vorschlag per DDoS angreifen kann. Eine VRF-basierte Auswahl (Algorand, Cardano) hält die Identität des Leaders geheim, bis der Block verbreitet wird — dann wurde der Block bereits vorgeschlagen, sodass ein DDoS zu spät kommt. Das wird adaptive Sicherheit oder unvorhersehbare Leader-Wahl genannt. Die dafür entscheidende kryptografische Eigenschaft besteht darin, dass die VRF-Ausgabe für jeden ohne privaten Schlüssel pseudorandom ist.

Die korrekte Implementierung von VRFs erfordert die Beachtung mehrerer Punkte. Hash-to-curve muss einen Algorithmus verwenden, der in konstanter Zeit und gleichförmig arbeitet (IETF RFC 9380 definiert standardisierte Verfahren, um Timing-Leaks zu verhindern). Der VRF-Nonce k im Beweis muss deterministisch aus (SK, alpha) mithilfe von RFC 6979 abgeleitet werden — die Wiederverwendung von k oder ein schwaches zufälliges k legt den geheimen Schlüssel offen (dieselbe Schwachstelle wie bei der Wiederverwendung von ECDSA-Nonces). Die Beweisgröße von ECVRF-P256-SHA256-TAI beträgt 80 Byte; für ECVRF-ED25519-SHA512-ELL2 ebenfalls 80 Byte — beide eignen sich für die Aufnahme on-chain. Die Eindeutigkeitseigenschaft von VRFs garantiert, dass für dasselbe Paar (SK, alpha) keine zwei gültigen Beweise existieren.

Warum bietet eine Leader-Wahl auf Basis von VRFs eine höhere Sicherheit als eine Round-Robin-Planung der Leader?

VRFs erzeugen pseudozufällige Ausgaben mit kryptografischen Korrektheitsbeweisen und erfüllen damit die Eigenschaften Unvorhersagbarkeit, Unverzerrbarkeit und öffentliche Überprüfbarkeit. ECVRF (RFC 9381) ist die Standardkonstruktion über elliptischen Kurven. Algorand verwendet die kryptografische Selbstauswahl durch VRFs, um Widerstandsfähigkeit gegen adaptive Angreifer zu erreichen. Cardano Ouroboros Praos verwendet VRFs für die Leader-Wahl pro Slot. Chainlink VRF stellt Smart Contracts verifizierbare Zufälligkeit bereit. VRFs ergänzen VDFs (die den Last-Revealer-Bias behandeln) und unterscheiden sich von RANDAO (das akkumulierte BLS-Signaturen mit einer bekannten Schwäche des letzten Aufdeckers verwendet).