Public randomness is an essential component of many real-world security protocols. In some applications, such as gambling and multiplayer games, randomness adds fun. In other applications, randomness provides a fair way to allocate non-divisible resources, ranging from green cards, to the assignment of circuit court judges to cases, to seeding in sports tournaments. It’s also used to allocate negative resources, like tax audits or secondary security screening at the airport.
Traditionally, we’ve relied on trusted authorities to generate randomness for these protocols, but in the web3 world, we’ll need to do better. In this post, we’ll explore approaches to building publicly verifiable randomness via distributed randomness beacons and then discuss some on-chain applications. (Part II, which is forthcoming, will specifically focus on leader election, while providing an assessment of alternate leader election approaches.)
Generating random numbers is a notoriously subtle task. For example, many cryptographic keys have been leaked because they relied on a faulty random number generator (for which Cloudflare’s wall of lava lamps would have served as a creative mitigation). That’s just private randomness, however, where only one party needs to generate and use it.
Public randomness, by contrast, is a multiparty process, which adds considerably to the difficulty. A good protocol for producing public randomness will have the following security properties:
Unbiasability is a weaker property than unpredictability because any protocol that is unpredictable must be unbiasable. Computer scientists would say unbiasability reduces to unpredictability, because if you can bias, you can predict. But sometimes we will want to reason about them separately because they may rely on different assumptions – for example, a dishonest majority might predict the outcome, but not bias it.
In addition to these properties, the protocol should be efficient to run and produce a large number of random bits. (In practice, it’s often sufficient for applications to produce 128 random bits, using them to seed a pseudorandom number generator [PNRG] to output more bits as needed. However, unpredictability should hold for each individual bit of the output to be usable for such applications as lotteries or resource allocations.) The protocol should also ideally be efficient in terms of communication and computation costs.
Different protocols might achieve these properties under different conditions. For example, some protocols might be unbiasable by any coalition of f1 malicious nodes and unpredictable by any coalition of f2<f1 malicious nodes. There are also different degrees of bias. For example, in some protocols a participant might be able to bias the output by “one bit” – meaning they can choose between one of two possible outputs. Other attacks might allow them to fix the output completely. Typically, however, we don’t want to tolerate any bias (or predictability) at all.
Cryptographers often start by thinking about an ideal solution to their problems. In the case of public randomness, a randomness beacon is an idealized service that regularly produces random output satisfying all of the necessary security requirements.
Such an idealized randomness beacon, similar to other cryptographic abstractions – such as random oracles or the generic group model – doesn’t exist in the real world. But it’s a useful goal to strive for and a useful model to reason about protocols that rely on public randomness.
We can consider a few approximations of an ideal randomness beacon.
A natural approach to the problems of centralized beacons is to design a decentralized cryptographic protocol for producing public randomness. This problem is somewhat like designing decentralized consensus protocols, only harder. Not only do all of the participants need to agree on an output (the randomness), but it should be impossible for a malicious participant in the protocol to bias or predict the output.
Protocols designed to simulate a randomness beacon are called distributed randomness beacons (DRBs). (Other names include “distributed coin-flipping.”) The problem has been studied for decades, with famous impossibility results proved in the 1980s, but interest has been reignited in the blockchain era. DRBs could be used to provide on-chain randomness, which would be a key ingredient to fair, secure, and transparent on-chain applications.
A very simple two-round protocol suffices for a DRB in the optimistic case. In round 1, each participant i generates a random value ri and publishes a cryptographic commitment ci=Commit(ri). In this application, the commitment can simply be a hash function like SHA-256. After each participant’s commitment is published, they are locked in to their choice of ri, but the commitments don’t reveal any information about other participants’ contributions. In round 2, every participant “opens their commitment” by publishing ri. All of the random values are then combined, for example by XORing them or (preferably) hashing their concatenation.
This protocol is simple and produces a random beacon output as long as even one of the participants chooses their ri randomly. Unfortunately, it suffers from a classic flaw: when all-but-one of the participants have revealed their random value, the last participant is able to compute the putative beacon output. If they don’t like it, they can refuse to publish their value, aborting the protocol. Ignoring a faulty participant’s contribution doesn’t fix the problem, because that still gives an attacker the choice between two beacon outputs (one calculated with their contribution and one without).
Blockchains offer a natural remedy to this problem: each participant can be required to put some funds in escrow that are seized if they don’t reveal their random contribution. This was exactly the approach taken by the classic RANDAO beacon on Ethereum. The downside of this approach is that the output can still be biased, which may be worthwhile financially for the attacker if the money in escrow is less than the amount of money riding on the result of the beacon. Better security against biasing attacks requires putting more coins in escrow.
Instead of trying to force all parties to reveal their random contribution, some protocols include a recovery mechanism so that even if a minority of participants drop out, the remainder can complete the protocol. It’s important that the protocol produces the same result in either case, so that parties cannot bias the result by choosing whether or not to drop out.
One approach to achieve this is to have each participant provide the others with shares of its secret, such that a majority of them can reconstruct it, using, for example, Shamir’s secret-sharing. An important property, however, is that the others can verify that the committed secret has been properly shared, requiring the use of a stronger primitive called publicly verifiable secret sharing (PVSS).
Several other recovery mechanisms are possible, but they all have the same limitation. If there are N participants, and we want resiliency if any group of up to f nodes drops out, then it must be the case that any group of N-f participants can compute the final result. But that also means a malicious coalition of N-f participants can predict the result in advance by privately simulating the recovery mechanism. This can also happen during the first round of the protocol, during which time such a coalition could modify their own randomness choices and bias the result.
Put another way, this means any coalition of N-f nodes must include at least one honest node. By simple algebra, N-f > f, so f < N/2, and these protocols inherently require an honest majority. This is a significant difference to the original security model of commit-reveal, which only requires f<N (at least one honest participant).
These protocols often also require significant communication costs to share the extra PVSS information between all nodes in each run of the protocol. The research community has done considerable work on this problem in the past several years, with research proposals including RandShare, Scrape, SecRand, HERB, or Albatross, but none appears to have seen real-world deployment.
Realizing that a group of N-f participants can compute the random beacon value in the above protocol leads to a somewhat simpler approach: share a long-term secret key between N parties and have them use it to evaluate a verifiable random function (VRF). The secret key is shared via a t-out-of-N threshold scheme, so that any t participants can compute the VRF (but a smaller coalition cannot). For t=N-f, this provides the same resiliency to f malicious nodes as the commit-reveal-recover protocols discussed above.
DFINITY pioneered this approach as part of their consensus protocol using threshold BLS signatures (which function as a VRF). The standalone drand randomness beacon uses essentially the same approach, with a set of participants threshold-BLS-signing a counter in each round. The League of Entropy is an open source instance of drand producing randomness every 30 seconds using 16 participating nodes (as of September 2022), run by a mix of companies and university research groups.
A downside of these approaches is that initializing the threshold key is relatively complex, as is reconfiguring the key when nodes join or leave. In the common case, though, the protocols are very efficient.
As described above, simply signing a counter value doesn’t add any fresh randomness per round, so if a sufficient number of participants’ keys are compromised, then the protocol will be predictable in every future round.
Chainlink VRF combines this approach (using the NSEC5 VRF) with an external source of randomness specified by parties requesting randomness, typically a recent blockchain header in practice. This data is then fed through a VRF which is run by either one party or thresholded to a group.
Ethereum’s Beacon Chain currently uses BLS-based VRFs: the proposer of each round adds their VRF value to the mix. This saves a round of communication compared to the commit-reveal paradigm (assuming a long-term BLS public key is registered once), although this design inherits some caveats of the commit-reveal approach including the possibility to bias the beacon’s output by withholding output.
Finally, a promising new direction is using time-based cryptography, specifically verifiable delay functions (VDFs). This approach promises to provide good communication efficiency and robustness with resilience to N-1 malicious nodes.
Going back to the original commit-reveal protocol, traditional commitments can be replaced with timed commitments to eliminate the problem of participants refusing to reveal their random contribution. Timed commitments can be opened efficiently by the original committer, or by anybody who is willing to compute a slow function (essentially a VDF). Thus, if any participant drops out of a commit-reveal protocol, their commitment can still be opened by others. It’s essential that the minimum time to open the commitment is long enough that it cannot be done during the first round (the commit phase) of the protocol, otherwise malicious participants could open others’ commitments quickly enough to modify their own contribution and bias the result.
An even more elegant one-round protocol is possible with modern VDFs: drop the commitment entirely. Each participant can simply publish their random contribution ri, and the final result is a combination of each participant’s contribution, run through a VDF. The time delay in computing the VDF ensures that nobody can choose their commitment in a way which biases the final output. This approach was proposed as UNICORN by Arjen Lenstra and Benjamin Wesolowski in 2015, and indeed was a key motivating application in the development of VDFs.
This approach has seen some practical deployment. Chia implements a version of this as part of its consensus protocol, using repeated-squaring VDFs in class groups. Starkware implemented a proof-of-concept VDF-based beacon using SNARK-based VDFs. Ethereum also plans to use this approach, building a dedicated ASIC for computing VDFs to generate randomness at the consensus layer.
***
Public randomness is an essential component of many protocols, but we still lack any standard DRB that provides high security. The design space is large and many hybrids and combinations of the above approaches are possible. For example, it’s possible to combine a VRF-based protocol with a VDF-based protocol, which adds fresh entropy, for example, as proposed by RandRunner. Ethereum’s Beacon Chain currently uses VRFs, although it may add VDFs in the future to eliminate the possibility of bias from block withholding attacks.
It’s also an open question when honest-majority protocols are acceptable. For a relatively small, vetted group of participants – like the League of Entropy – an honest majority assumption is reasonable. On the other hand, protocols which only require a single honest participant have an inherent advantage – more participants can only improve security. This means these protocols can potentially be deployed with open, permissionless participation.
In Part II, we will discuss the specific application of randomized leader election in consensus protocols, which has slightly different design goals and as a result has seen even more protocols and approaches proposed.
***
Joseph Bonneau is a Research Partner at a16z crypto. His research focuses on applied cryptography and blockchain security. He has taught cryptocurrency courses at the University of Melbourne, NYU, Stanford, and Princeton, and received a PhD in computer science from the University of Cambridge and BS/MS degrees from Stanford.
Valeria Nikolaenko is a Research Partner at a16z crypto. Her research focuses on cryptography and blockchain security. She has also worked on topics such as long-range attacks in PoS consensus protocols, signature schemes, post-quantum security, and multi-party computation. She holds a PhD in Cryptography from Stanford University under advisorship of Professor Dan Boneh, and worked on the Diem blockchain as part of the core research team.
***
Editor: Tim Sullivan
***
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. In addition, this content may include third-party advertisements; a16z has not reviewed such advertisements and does not endorse any advertising content contained therein.
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 or digital assets are for illustrative purposes only, and do not constitute an investment recommendation or 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.
