Random Beacons

A random beacon should satisfy:

• Unpredictability: No node can predict the output before it is published.
• Unbiasability: No node can influence the distribution of the output. Strictly stronger than unpredictability, since an adversary may not predict the exact output but could still skew it.
• Public verifiability: Any node can verify the output was correctly generated without trusting the operator.
• Availability (guaranteed output delivery): The beacon produces output on schedule even if some nodes are faulty or adversarial.

For a comprehensive survey, see [8].

• Commit-reveal: Participants commit to hash of secret, then reveal. Output derived from all reveals (e.g., XOR). Vulnerable to last-revealer attack and abort.
• Threshold cryptography: (e.g., threshold BLS in DRand). Output is deterministic once \(t+1\) honest shares are contributed, preventing bias. Requires a DKG (distributed key generation) phase.
• VDFs (Verifiable Delay Functions): Require prescribed sequential time to compute, fast to verify (e.g., repeated squaring in groups of unknown order [9], [10]). Used as post-processing on a biasable source so the output is fixed before any party can react.
• VRFs (Verifiable Random Functions): Secret-key holder produces pseudorandom output with proof of correctness. Used in Algorand [11] and Ouroboros Praos [12] for private leader election. A building block, not a standalone beacon.
• PVSS (Publicly Verifiable Secret Sharing): Allows recovery of a participant's contribution if they go offline. Used in SCRAPE [13], RandHerd [14], and DFINITY's beacon [15].

• Last-revealer attack: In commit-reveal or XOR-based schemes (including RANDAO), the last party to reveal can choose to abort, gaining 1 bit of influence per abort. Motivates threshold and VDF-based designs.
• Grinding attacks: Adversary tries many possible inputs to find a favorable output. Relevant to block-hash-based randomness. Ouroboros Praos mitigates this with VRFs.
• Liveness attacks: Adversary refuses to participate to prevent output. Threshold schemes ($t$-of-\(n\)) tolerate up to \(n-t\) failures.
• Front-running: If beacon output is visible before dependent transactions finalize, adversaries can act on it.

1. According to [16], global coins can substitute a local coin and can speed up protocols.
2. Asynchronous distributed protocols need randomness since no deterministic protocols exist due to [17]. So we can use the first application to speed up asynchronous protocols.
3. The Ouroboros sequence of works, the only-known provably secure Proof-of-stake protocols, need randomness to ensure eventual consistency.
4. Leader/committee election, e.g., Algorand uses VRFs for cryptographic sortition [11]
5. Parameter generation - trusted setup ceremonies for zk-SNARKs use beacon outputs to ensure no party could have predicted the seed [18].