Randomness beacons in theory and practice
Joseph Bonneau
Real World Crypto
March 28, 2025
Dedicated to Ross Anderson (1956-2024)
An ideal randomness beacon [Rabin83]
Goals (high level):
time
epoch 1
4169
epoch 2
9772
epoch 3
6015
...
...
Beacons can power verifiable lotteries
Beacons can power verifiable lotteries
Many use cases beyond lotteries
Goal: Many applications driven by a public randomness beacon
State of the art has barely changed for millenia!
This talk: distributed randomness beacons
time
Ω1
Ω2
Ω3
...
entropy
entropy
entropy
Classic: Commit-Reveal
c3
c2
c1
Classic: Commit-Reveal
e3
e2
e1
Classic: Commit-Reveal
∅
e2
e1
DRB design comparison
Protocol | Per-Round Comm. | Threshold to Manipulate | Threshold to Predict | Threshold to Block | Notes |
commit-reveal-fail | O(n) | n | n | 1 | |
DRB design comparison
Protocol | Per-Round Comm. | Threshold to Manipulate | Threshold to Predict | Threshold to Block | Notes |
commit-reveal-fail | O(n) | n | n | 1 | |
commit-reveal-restart | O(n) | 1 | 1 | ∅ | |
Commit-reveal-punish
c1,$
c3,$
c2,$
Commit-reveal-punish
e2
e1
∅
$
$
DRB design comparison
Protocol | Per-Round Comm. | Threshold to Manipulate | Threshold to Predict | Threshold to Block | Notes |
commit-reveal-fail | O(n) | n | n | 1 | |
commit-reveal-restart | O(n) | 1 | 1 | ∅ | |
commit-reveal-punish | O(n) | 1 | 1 | ∅ | economic security |
Commit-reveal-punish: RANDAO
Commit-reveal-punish: RANDAO
Optimal RANDAO Manipulation in Ethereum. Kaya Alpturer, S. Matthew Weinberg. AFT 2024.
Commit-reveal-recover
c2 , PVSS(e2)
c1 , PVSS(e1)
c3, PVSS(e3)
Commit-reveal-recover
e2
e1
∅
e3
PVSS.reconstruct()
Ω
Commit-reveal-recover variants
DRB design comparison
Protocol | Per-Round Comm. | Threshold to Manipulate | Threshold to Predict | Threshold to Block | Notes |
commit-reveal-fail | O(n) | n | n | 1 | |
commit-reveal-restart | O(n) | 1 | 1 | ∅ | |
commit-reveal-punish | O(n) | 1 | 1 | ∅ | economic security |
commit-reveal-recover | O(n2) | t | t | n-t | |
Pseudorandom DRBs
e3
e2
e1
PubKeyDRB
Pseudorandom DRBs
σ3
σ2
σ1
VRF(ri , PubKeyDRB)
ri
Pseudorandom DRB variants
DRB design comparison
Protocol | Per-Round Comm. | Threshold to Manipulate | Threshold to Predict | Threshold to Block | Notes |
commit-reveal-fail | O(n) | n | n | 1 | |
commit-reveal-restart | O(n) | 1 | 1 | ∅ | |
commit-reveal-punish | O(n) | 1 | 1 | ∅ | economic security |
commit-reveal-recover | O(n2) | t | t | n-t | |
pseudorandom | O(n) | ∅ | t | n-t | requires setup; no forward security |
drand: a production pseudorandom DRB
Reveal-delay (Unicorn) [LW15]
e3
e1
e2
Reveal-delay (Unicorn) [LW15]
e3
e1
e2
Just
One
Honest
Node
Reveal-delay (Unicorn) [LW15]
e3
e1
e2
Ω
Reveal-delay (Unicorn) [LW15]
e1
e2?
?
Last revealer(s) can’t compute VDF fast enough to bias
e3?
Delay functions are a powerful tool
Fast
Intractable
Encryption
Decryption
Signing
Verification
Hashing
Key search
Discrete log
Factoring
Collision-
finding
Delay functions:
take a specified number of sequential steps
VDFs
Timed commitments
Time-lock encryption
Delay encryption
...
Delay-based DRB variants
Delay-based DRBs in practice: Chia
DRB design comparison
Protocol | Per-Round Comm. | Threshold to Manipulate | Threshold to Predict | Threshold to Block | Notes |
commit-reveal-fail | O(n) | n | n | 1 | |
commit-reveal-restart | O(n) | 1 | 1 | ∅ | |
commit-reveal-punish | O(n) | 1 | 1 | ∅ | economic security |
commit-reveal-recover | O(n2) | t | t | n-t | |
pseudorandom | O(n) | ∅ | t | n-t | requires setup; no forward security |
delay-based | O(n) | n | n | ∅ | added latency |
VDF designs are relatively new
Dishonest-majority DRB without delay functions?
Dishonest-majority DRB without delay functions?
Why design to tolerate n-1 dishonest nodes?
DRB design comparison
Protocol | Round Efficiency | Threshold to Manipulate | Threshold to Predict | Threshold to Block | Notes |
commit-reveal-fail | O(n) | n | n | 1 | |
commit-reveal-restart | O(n) | 1 | 1 | ∅ | |
commit-reveal-punish | O(n) | 1 | 1 | ∅ | economic security |
commit-reveal-recover | O(n2) | t | t | n-t | |
pseudorandom | O(n) | ∅ | t | n-t | requires setup; no forward security |
delay-based | O(n) | n | n | ∅ | added latency |
Which DRB should I use?
commit-reveal (vulnerable)
Clear economic model?
commit-reveal-punish
Honest majority?
delay-based DRB
Static participant set?
pseudorandom DRB
Small participant set?
commit-reveal-recover
committee-based DRB
yes
no
yes
yes
no
Open questions (protocol design)
Open questions (engineering)
Ensuring public trust is the primary challenge
Thank you!
For more, see 3 detailed surveys:
SoK: Decentralized randomness beacon protocols. Raikwar, Mayank, and Danilo Gligoroski. ACISP 2022. https://arxiv.org/pdf/2205.13333
SoK: Distributed Randomness Beacons. Kevin Choi, Athira Manoj and Joseph Bonneau. IEEE S&P 2023. https://eprint.iacr.org/2023/728
SoK: Public Randomness. Kavousi, Alireza, Zhipeng Wang, and Philipp Jovanovic. EuroS&P 2024. https://ieeexplore.ieee.org/stamp/stamp.jsp?arnumber=10629002
Required disclosures
The views expressed here are those of the individual AH Capital Management, L.L.C. (“a16z”) personnel quoted and are not the views of a16z or its affiliates. Certain information contained in here has been obtained from third-party sources, including from portfolio companies of funds managed by a16z. While taken from sources believed to be reliable, a16z has not independently verified such information and makes no representations about the enduring accuracy of the information or its appropriateness for a given situation.
This content is provided for informational purposes only, and should not be relied upon as legal, business, investment, or tax advice. You should consult your own advisers as to those matters. References to any securities, digital assets, tokens, and/or cryptocurrencies are for illustrative purposes only and do not constitute a recommendation to invest in any such instrument nor do such references constitute an offer to provide investment advisory services. Furthermore, this content is not directed at nor intended for use by any investors or prospective investors, and may not under any circumstances be relied upon when making a decision to invest in any fund managed by a16z. (An offering to invest in an a16z fund will be made only by the private placement memorandum, subscription agreement, and other relevant documentation of any such fund and should be read in their entirety.) Any investments or portfolio companies mentioned, referred to, or described are not representative of all investments in vehicles managed by a16z, and there can be no assurance that the investments will be profitable or that other investments made in the future will have similar characteristics or results. A list of investments made by funds managed by Andreessen Horowitz (excluding investments for which the issuer has not provided permission for a16z to disclose publicly as well as unannounced investments in publicly traded digital assets) is available at https://a16z.com/investments/.
Charts and graphs provided within are for informational purposes solely and should not be relied upon when making any investment decision. Past performance is not indicative of future results. The content speaks only as of the date indicated. Any projections, estimates, forecasts, targets, prospects, and/or opinions expressed in these materials are subject to change without notice and may differ or be contrary to opinions expressed by others. Please see https://a16z.com/disclosures for additional important information.
Backup slides
Detailed comparison in SoK paper
SoK: Distributed Randomness Beacons.
Kevin Choi, Athira Manoj and Joseph Bonneau.
IEEE Security & Privacy (Oakland) 2023
Current work on delay-based DRBs
Bicorn: eliminate delay function in optimistic case!
Bicorn: An optimistically efficient distributed randomness beacon
Kevin Choi, Arasu Arun, Nirvan Tyagi and Joseph Bonneau.
Financial Crypto 2023
https://eprint.iacr.org/2023/221
Cornucopia: scale to millions of contributors with an untrusted coordinator!
Cornucopia: Distributed randomness beacons at scale
Miranda Christ, Kevin Choi, and Joseph Bonneau.
(in submission)
VDFs are a potential game-changer
Do we need a dishonest majority?
Delay functions enable participatory protocols
Open questions
Papers cited
SoK: Distributed Randomness Beacons.
Kevin Choi, Athira Manoj and Joseph Bonneau.
IEEE Security & Privacy (Oakland) 2023
https://eprint.iacr.org/2023/728
Bicorn: An optimistically efficient distributed randomness beacon
Kevin Choi, Arasu Arun, Nirvan Tyagi and Joseph Bonneau.
Financial Crypto 2023
https://eprint.iacr.org/2023/221
Cornucopia: Distributed randomness beacons at scale
Miranda Christ, Kevin Choi, and Joseph Bonneau.
(in submission)
Commit-reveal-delay (Bicorn) [CATB23]
As secure as Unicorn, but with a fast optimistic case!
Commit-reveal-delay (Bicorn) [CATB23]
c3
c2
c1
Commit-reveal-delay (Bicorn) [CATB23]
e3
e2
e1
Ω
Commit-reveal-delay (Bicorn) [CATB23]
c3
c2
c1
Ω
Cornucopia [CCB24]
As secure as Unicorn, but with a constant-size broadcast!
Cornucopia [CCB24]
N users
Public Bulletin Board
Coordinator
Contribution ri
Inclusion proof πi
Commitment R
Result Ω = Delay(R)
Output Ω is guaranteed random if ri is random
... regardless of other participant’s actions!
Result Ω
Cornucopia [CCB24]
Security proven using a new accumulator property:
insertion security
Many combinations are possible
Slight improvement: better entropy combination
e3
e2
e1
Committee DRB options
Unbiasability security game
Ω0
Ω1
Ωb
b=1
honest run
infiltrated run
Unbiasability: Attacker has negligible advantage guessing b
Expected attack costs for commit-reveal-punish
Might be okay for low probability events
Approaches we won’t discuss in detail
Generalized security definition framework
Public randomness: an ancient challenge
kleroterion, Ancient Greece dice, Ancient Rome
DRB design flow chart
commit-reveal (vulnerable)
Clear economic model?
commit-reveal-punish
Honest majority?
delay-based DRB
Static participant set?
pseudorandom DRB
Small participant set?
commit-reveal-recover
yes
no
yes
yes
Many additional practical considerations
Long-term goal: deploying DRBs outside of web3
Key challenge: explaining limits of physical randomness, benefits of DRBs
Many avenues for future work
Detailed comparison in SoK paper
SoK: Distributed Randomness Beacons.
Kevin Choi, Athira Manoj and Joseph Bonneau.
IEEE Security & Privacy (Oakland) 2023
Important disclosures
The views expressed here are those of the individual AH Capital Management, L.L.C. (“a16z”) personnel quoted and are not the views of a16z or its affiliates. Certain information contained in here has been obtained from third-party sources, including from portfolio companies of funds managed by a16z. While taken from sources believed to be reliable, a16z has not independently verified such information and makes no representations about the enduring accuracy of the information or its appropriateness for a given situation.
This content is provided for informational purposes only, and should not be relied upon as legal, business, investment, or tax advice. You should consult your own advisers as to those matters. References to any securities, digital assets, tokens, and/or cryptocurrencies are for illustrative purposes only and do not constitute a recommendation to invest in any such instrument nor do such references constitute an offer to provide investment advisory services. Furthermore, this content is not directed at nor intended for use by any investors or prospective investors, and may not under any circumstances be relied upon when making a decision to invest in any fund managed by a16z. (An offering to invest in an a16z fund will be made only by the private placement memorandum, subscription agreement, and other relevant documentation of any such fund and should be read in their entirety.) Any investments or portfolio companies mentioned, referred to, or described are not representative of all investments in vehicles managed by a16z, and there can be no assurance that the investments will be profitable or that other investments made in the future will have similar characteristics or results. A list of investments made by funds managed by Andreessen Horowitz (excluding investments for which the issuer has not provided permission for a16z to disclose publicly as well as unannounced investments in publicly traded digital assets) is available at https://a16z.com/investments/.
Charts and graphs provided within are for informational purposes solely and should not be relied upon when making any investment decision. Past performance is not indicative of future results. The content speaks only as of the date indicated. Any projections, estimates, forecasts, targets, prospects, and/or opinions expressed in these materials are subject to change without notice and may differ or be contrary to opinions expressed by others. Please see https://a16z.com/disclosures for additional important information.
Strawman: Rock-Paper-Scissors
Ω = e1 + e2 + e3 (mod k)
Secure given any one honest participant... assuming perfect synchrony
e3
e2
e1
Manipulating Rock-Paper-Scissors with Δ>0
Ω* (forced beacon output)
e3
e2
e1
Public randomness: an ancient challenge
kleroterion, Ancient Greece dice, Ancient Rome
Verifiable Delay Functions [BBBF18]
V: efficient to verify
D: t-sequential to solve
F: unique output
API
Security goals
Timeline for a verifiable lottery
for p in players:
p.rank = H(p, R)
sort(players)
for p in players:
p.rank = H(p, R)
sort(players)
+
Timeline for a verifiable lottery (take 2)
for p in players:
p.rank = H(p, R)
sort(players)
+
Alice
Alice
Alice
Alice
Alice
Physical randomness can be faked
Physical randomness can fail
US conscription lottery, 1969
Physical randomness can fail
US conscription lottery, 1969
1. Load in order 2. Rotate axially 3. Draw from top
1
2
3
4
5
6
7
8
9
7
4
1
8
5
2
9
6
3
1
3
2
6
4
5
8
9
7
Physical randomness can fail
US conscription lottery, 1969
Commit-reveal: real-world example
Commit-reveal: real-world example
Commit-reveal: real-world example
Commit-reveal: real-world example
+ + =
(mod 6)
Beacons often implemented via authority
Committee-based DRBs
Committee-based DRBs
c2 , PVSS(e2)
c1 , PVSS(e1)
c3, PVSS(e3)
Ω
Committee selection strategies
Better
adaptive security
Example committee-based DRBs
Freshly generated entropy
Precommitted entropy
Public selection
Private selection
Ouroboros [KRBO 17]
RandHound [SJKGGKFF 17]
SPURT [DVIR 21]
OptRand [BSKN 23]
HydRand [SJSW 20]
GRandPiper [BSKN 21]
Algorand [GHMVZ 17]
Variant of NV [NNLNNLN 19]
Pros/cons of committee-based DRBs
Better SSLE would help
Observe: VDFs can patch many DRBs
DRB design flow chart
commit-reveal (vulnerable)
Clear economic model?
commit-reveal-punish
Honest majority?
delay-based DRB
Static participant set?
pseudorandom DRB
Small participant set?
commit-reveal-recover
committee-based DRB
yes
no
yes
yes
no
Commit-reveal-punish
DRB design flow chart
commit-reveal (vulnerable)
Clear economic model?
commit-reveal-punish
Honest majority?
delay-based DRB
Static participant set?
pseudorandom DRB
Small participant set?
commit-reveal-recover
committee-based DRB
yes
no
yes
yes
no
Commit-reveal-recover
e2
e1
e3
Ω
Commit-reveal-recover
Pseudorandom DRBs
Commit-reveal-recover
c2 , PVSS(e2)
c1 , PVSS(e1)
c3, PVSS(e3)
Commit-reveal-recover
e2
e1
e3
Ω
Commit-reveal-recover
e2
e1
∅
e3
PVSS.reconstruct()
Ω
Commit-reveal-recover variants
Commit-reveal-recover
DRB design flow chart
commit-reveal (vulnerable)
Clear economic model?
commit-reveal-punish
Honest majority?
delay-based DRB
Static participant set?
pseudorandom DRB
Small participant set?
commit-reveal-recover
committee-based DRB
yes
no
yes
yes
no
Delay-based DRBs
Delay-based DRBs