Partnered With:

a16z: Building public randomness for Web3 via decentralized random beacons

a16z crypto

Read this article in 23 Minutes

Randomness provides a fair way to distribute indivisible resources.

Original title: 《 Public Randomness and Randomness Beacons 》

Original author: Joseph Bonneau, Valeria Nikolaenko, a16z crypto research partner

Original translation: Shaun@DAOrayaki.org, DoraFactory

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 distribute indivisible resources, from green cards to case assignments to circuit court judges to seeds for sports games. It is also used to distribute negative resources, such as tax audits or secondary security at airports.

Traditionally, we’ve relied on trusted authorities to generate randomness for these protocols, but in the web3 world, we need to do better. In this post, we’ll explore ways to build publicly verifiable randomness via distributed random beacons, and then discuss some on-chain applications. (The upcoming second part will focus specifically on leader election, while also providing an evaluation of alternative leader election methods.)

Expected Properties

Generating random numbers is a notoriously delicate task. For example, many cryptographic keys have been leaked because they relied on a flawed random number generator (Cloudflare’s lava lamp wall can serve as a creative mitigation). However, this is only private randomness, where only one party needs to generate and use it. In contrast, public randomness is a multi-party process, which greatly increases the difficulty. A good protocol for generating public randomness will have the following security properties:

Unbiased: No attacker or coalition of attackers should be able to bias the output. Reliable: No attacker should be able to prevent the protocol from producing output.

Verifiable: Anyone can easily verify the protocol output and should see the same output as everyone else.

Unpredictable: If the protocol produces an output at time T1, then no one should be able to predict anything about the output until some time T0

Unbiasedness is a weaker property than unpredictability, because any unpredictable protocol must be unbiased. Computer scientists would say that unbiasedness reduces to unpredictability, because if you are biased, you can predict. But sometimes we want to reason about them separately, because they may rely on different assumptions - for example, a dishonest majority may predict the outcome but not be biased against it.

In addition to these properties, the protocol should be able to run efficiently and produce a large number of random bits. (In practice, it is often sufficient for an application to generate 128 random bits, using them to seed a pseudorandom number generator [PNRG] to output more bits as needed. However, unpredictability should be maintained for each individual bit of the output for use in such applications as lotteries or resource allocation.) Ideally, the protocol should also be efficient in terms of communication and computational cost.

Different protocols may achieve these properties under different conditions. For example, some protocols may be unbiased 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, participants may be able to bias the output by "one bit" - meaning they can choose between one of two possible outputs. Other attacks may allow them to fix the output entirely. Typically, however, we don't want to tolerate any bias (or predictability) at all.

Cryptographic Ideal: Randomness Beacon

Cryptologists often start by thinking about an ideal solution to a problem. In the case of public randomness, a randomness beacon is an idealized service that periodically produces random output that satisfies all the necessary security requirements.

This idealized randomness beacon, similar to other cryptographic abstractions — such as random oracles or the universal group model — does not exist in the real world. But it is a useful goal, and a useful model to reason about protocols that rely on public randomness.

We can consider some approximations to the ideal randomness beacon.

Centralized beacons: The simplest way to generate good randomness is through a centralized third party with services like the NIST randomness beacon or random.org, which generate randomness from atmospheric noise and are certified for use in gambling. This reliance on a third party completely undermines the idea of decentralization. Indeed, in the example above, we have to trust that the organization in question is generating the randomness correctly, without any cryptographic proof.

Physical displays of randomness: Many traditional lotteries rely on public displays, which might, for example, consist of someone reaching into a container of ping-pong balls with different numbers on them. Unfortunately, these are often easy to manipulate. For example, a certain ball s could be placed in a refrigerator, and then the selector could be told to pick the cold ones.

Natural beacons: A common idea is to use random natural phenomena like weather or cosmic background radiation as beacons. Unfortunately, none of the proposed sources provide strong consensus. Different observers will see slightly different values, which requires reintroducing a trusted party for official measurements, with all the drawbacks of centralized beacons.

Semi-centralized beacons: A better approach would be to get randomness directly from Bitcoin block headers or stock closing prices, which is easier to verify publicly and harder for any one party to fully control. However, subtle attacks on proof-of-work blockchain randomness and stock price randomness still exist. For example, using blockchain headers, miners can choose to keep blocks whose headers produce beacon values they don't like. Or, they can choose to break a tie when they find two colliding blocks based on their preferred beacon output.

Decentralized Randomness Beacon (DRB)

A natural way to solve the centralized beacon problem is to design a decentralized cryptographic protocol to generate public randomness. This problem is a bit like designing a decentralized consensus protocol, only harder. Not only do all participants need to agree on the output (randomness), but malicious participants in the protocol should not be able to bias or predict the output.

Protocols designed to emulate randomness beacons are called distributed randomness beacons (DRBs). (Other names include “distributed coin-flipping.”) This problem has been studied for decades, with a famous impossibility result proved in the 1980s, but interest has been reignited in the blockchain era. DRBs can be used to provide on-chain randomness, which will be a key element of fair, secure, and transparent on-chain applications.

Classic Approach: Commit-Reveal Protocols

In the optimistic case, a very simple two-round protocol suffices for DRBs. 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 into their chosen ri, but the commitment does not reveal any information about the contributions of other participants. In round 2, each participant “unlocks their commitment” by publishing ri. All random values are then combined, for example by XORing them or (preferably) hashing their concatenation.

The protocol is simple, and produces a random beacon output whenever one of the participants randomly chooses their ri. Unfortunately, it suffers from a classic flaw: when all participants have revealed their random values, the last participant is able to compute the supposed beacon output. If they don't like it, they can refuse to publish their value, aborting the protocol. Ignoring the contribution of the wrong participant does not solve the problem, because this still lets the attacker choose between two beacon outputs (one computed with their contribution, and one not).

Blockchains offer a natural remedy for this problem: each participant could be required to put some funds in escrow, which can be forfeited if they don't reveal their random contribution. This is 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 could be worthwhile for an attacker if the funds in escrow are less than the amount on the beacon result. Better security against bias attacks would require putting more tokens in escrow.

Commitment-Reveal-Recovery Protocols

Instead of trying to force all parties to reveal their random contributions, some protocols include a recovery mechanism so that even if a few participants drop out, the remaining participants can complete the protocol. It is important that the protocol produces the same result in either case, so that parties cannot bias the result by choosing whether to drop out.

One way to achieve this is to have each participant provide a share of its secret to the others, so that a majority of them can reconstruct it using, for example, Shamir's secret sharing. However, an important property is that others can verify that the committed secret has been shared correctly, which requires the use of a stronger primitive called publicly verifiable secret sharing (PVSS).

Several other recovery mechanisms are possible, but they all have the same limitations. If there are N participants, and we want resilience if any group of at most f nodes drops out, then any group of N - f participants must be able to compute the final result. But it also means that a malicious coalition of N-f participants can predict the outcome in advance by privately simulating the recovery mechanism, which can also happen in the first round of the protocol, during which such a coalition can modify their own randomness choices and bias the outcome.

In other words, this means that any coalition of N-f nodes must contain 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 very different from the original commit-reveal security model, which only requires f < N (at least one honest participant).

These protocols also typically incur significant communication costs to share the additional PVSS information between all nodes in each run of the protocol. The research community has done quite a bit of work on this problem over the past few years, with proposals such as RandShare, Scrape, SecRand, HERB, or Albatross, but none seem to have seen actual deployment.

Verifiable Random Function-Based Protocols

Realizing that a set of N-f participants can compute the random beacon value in the above protocol leads to a simpler approach: share a long-term key between the N parties, and have them use it to evaluate a verifiable random function (VRF). The key is shared via a t-out-of-N threshold scheme, so any t participants can compute the VRF (but a smaller coalition cannot). For t=N- Realizing that a set of N-f participants can compute the random beacon value in the above protocol leads to a simpler approach: share a long-term key between the N parties, and have them use it to evaluate a verifiable random function (VRF). The keys are shared via a t-out-of-N threshold scheme, so any t participants can compute the VRF (but a smaller coalition cannot). For t=N-f, this provides the same resilience to f malicious nodes as the commit-reveal-recover protocol discussed above.

DFINITY pioneered this approach as part of its consensus protocol, using threshold BLS signatures (which serve as the VRF). The independent drand randomness beacon uses essentially the same approach, with a threshold set of participants - BLS-signing a counter in each round. The Entropy Alliance is an open source instantiation of drand that generates randomness every 30 seconds using 16 participating nodes (as of September 2022), run by a combination of companies and university research groups.

The downside to these approaches is that initializing the threshold keys is relatively complex, as is reconfiguring the keys when nodes join or leave. However, in the common case, the protocol works very well.

As mentioned above, simply signing a counter value does not add any new randomness in each 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 the parties requesting randomness, typically the most recent blockchain header in practice. This data is then fed through a VRF that is either run by a party or thresholded to a set.

Ethereum’s beacon chain currently uses a BLS-based VRF: each round proposers add their VRF value to the mix. This saves one round of communication compared to the commit-reveal paradigm (assuming long-term BLS public keys are registered once), although this design inherits some of the caveats of the commit-reveal approach, including the possibility of biasing the beacon output by withholding outputs.

Protocols based on verifiable delay functions

Finally, a promising new direction is to use time-based cryptography, specifically verifiable delay functions (VDFs). This approach promises good communication efficiency and robustness, with resiliency 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 contributions. Timed commits can be effectively turned on by the original proposer or anyone willing to compute a slow function (essentially a VDF). Therefore, if any participant exits the commit-reveal protocol, their commitments can still be opened by others. It is critical that the minimum time commitments are opened is long enough that it cannot be completed in the first round of the protocol (the commit phase), otherwise a malicious participant could open the commitments of others quickly enough to modify their own contributions and bias the outcome.

Modern VDFs allow for a more elegant one-round protocol: abandoning commitments altogether. Each participant can simply publish their random contribution ri, and the final result is the combination of each participant's contributions, run through the VDF. The time delay in computing the VDF ensures that no one can choose their commitments in such a way as to bias the final output.

This approach was proposed as UNICORN by Arjen Lenstra and Benjamin Wesolowski in 2015, and is indeed a key incentive application in VDF development. This approach has seen some real-world deployments. Chia implemented a version as part of its consensus protocol, using a repeated-squared VDF in class groups. Starkware implemented a proof-of-concept VDF beacon using a SNARK-based VDF. Ethereum also plans to use this approach, building a dedicated ASIC to compute VDFs to generate randomness at the consensus layer.

Public randomness is an important 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, one could combine a VRF-based protocol with a VDF-based protocol, which adds new entropy, such as proposed by RandRunner. Ethereum's beacon chain currently uses VRF, but VDFs may be added in the future to eliminate the possibility of bias from block withholding attacks.

It is also an open question when honest majority protocols are acceptable. For a relatively small, vetted group of participants - such as the Entropy League - the honest majority assumption is reasonable. On the other hand, protocols that only require a single honest participant have an inherent advantage - more participants can only improve security. This means that these protocols will likely 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 therefore proposes more protocols and approaches.