Verifiable Random Functions in Consensus

Consensus protocols require randomness for leader election, committee selection, and shard assignment. The randomness must satisfy three properties: unpredictability (no one can predict the output before it is revealed), unbiasability (no participant can manipulate the output to their advantage), and public verifiability (anyone can verify the output is correct without trusting the generator). Naive approaches fail: a single node's random number is manipulable, and commit-reveal schemes allow last-revealer bias. Verifiable Random Functions (VRFs) solve all three requirements.

A Verifiable Random Function (VRF), introduced by Micali, Rabin, and Vadhan in 1999, is a pseudo-random function that provides a proof of correctness. A VRF has three algorithms: KeyGen generates a key pair (SK, PK); Prove(SK, alpha) produces (beta, pi) where beta is the output and pi is a proof; and Verify(PK, alpha, beta, pi) returns valid or invalid. The output beta is indistinguishable from random to anyone who does not know SK (VRF pseudorandomness), and the proof pi is unforgeable (VRF uniqueness). The proof size is O(1) — constant regardless of input.