An Analysis of Verifiable Randomness in Web3

February 19, 2024 - 5 min read

Randomness is critical for ensuring fair, unpredictable, and unbiasable outcomes in distributed systems, yet can be subject to manipulation without the proper design.

Verifiable Randomness in Web3

On-chain verifiable randomness is a crucial resource in Web3 applications. This is especially the case with online lotteries, blockchain gaming, NFT minting and trait generation, leader selection, digital resources allocation, and much more. It is the ingredient which levels the playing field for participants so that outcomes can’t be predicted by anyone before they occur, especially node operators or other participants who might try to gain asymmetrical knowledge and advantages.

Access to verifiable sources of randomness also enables other cryptographic protocols, like multiparty computations and zero-knowledge proofs. These protocols have a variety of their own applications, with uses including privacy-preserving machine learning, the creation of zk Bridges, and verifiable computing. The only question now is: What is verifiable randomness?

What is “Verifiable” or “Good” Randomness?

In our previous blog, we stated that verifiable or “good” randomness, which leads to the generation of a truly random number, is:

Unpredictable: No one can compute the number ahead of time.
Unbiasable: The random number cannot be biased to make specific numbers more likely to appear than others (e.g., the number is always even or always odd).
Publicly verifiable: Anyone can verify that the random number is correctly generated.

In our Distributed Verifiable Random Function (dVRF) whitepaper, we discussed that the Supra dVRF randomness service protocol satisfies the above three properties and hence provides good randomness. Now, the main question is:

How to identify whether a randomness service protocol is generating verifiable “good” randomness or “bad” (i.e., non-verifiable) randomness?

In a series of blogs, we will explore how to generate and consume verifiable randomness in the Web3 space. Starting with post, we’ll dive into randomness service protocols utilizing commit-reveal schemes. We refer to the broader concept of commit-reveal as the commit-reveal paradigm.

Analysis of the Commit-Reveal Paradigm

Let’s start with the plain commit-reveal paradigm to argue that it is impossible to obtain unbiasable randomness in this paradigm. Later, we will also explore the same vulnerabilities that will cause trouble in the commit-reveal paradigm in which smart contracts are deployed.

In the plain commit-reveal paradigm, the randomness provider and the user commit to random values x and susing a hash function H. Upon exchanging the commitments, the provider and the user reveal x and s to each other. Both the user and provider verify the revealed values against the commitments. If the commitments verify, they compute the randomness rand=H(x, s). We illustrate this paradigm below:

Figure 1. Flowchart of Commit-Reveal paradigm

Since the user receives x from the provider after exchanging the commitments, the user can preemptively compute the output. This is a fundamental design flaw as the user can continue/stall the protocol in Step 4 if the output is favorable/unfavorable. This would allow the user to maximize their profit. The provider cannot complete the execution without obtaining s from the user since s remains secret. Hence, the output can be biased.

This is undesirable in the Web3 space, where the on-chain randomness of the user is ideally generated by the provider after the user has initiated the randomness request. This is irrespective of whether the user will continue/abort the protocol later.

Impossibility and Get Around

It’s impossible to achieve unbiased randomness using commit-reveal without any trusted assumption. This was shown by Cleve that two parties cannot generate unbiased randomness without any assumption. That’s because one of the parties will always receive their output first and then decide to abort the protocol if the output is unfavorable, similar to the attack shown previously.

However, in the Web3 space, the user and provider can access smart contracts. The smart contracts act as a trusted party to perform correct computation over public values. The randomness service uses smart contracts to generate unpredictable, unbiasable, and publicly verifiable randomness.

However, this is easier said than done, especially in the commit-reveal paradigm. We show that the existing randomness service of Pyth Entropy lies in this paradigm and deploys smart contracts, yet they fail to produce unbiasable random output.

Vulnerability in Pyth Entropy

The Pyth Entropy protocol operates in the commit-reveal paradigm where the provider initially commits to a sequence of random values (x₁, x₂,…x_N) on the Entropy Smart Contract (SC). The SC stores these commitments.

The user initiates a request by choosing a random value s. The user commits to s as c and then sends c to the SC. The SC stores c and assigns a unique sequence number – reqid (denoted as i in Pyth Entropy), to the user. The user sends reqid to the provider through a HTTP request and receives x_reqid. The user reveals (s, x_reqid) to the Entropy SC.

The SC verifies x_reqid (w.r.t. to the stored commitments) and c, and then it computes the randomness rand. The Pyth Entropy protocol can be visualized below:

Figure 2. Flowchart of Pyth Entropy

A malicious user attacks the protocol by precomputing rand=H(s, x_reqid) once it obtains x_reqid from the provider. If the output is favorable, then the user continues the protocol, otherwise it aborts the protocol. This enables the user to maximize its chance of winning in an online lottery game where the user’s randomness is taken into consideration while deciding the winners.

With Supra, a clan of nodes is used instead of a single node. As a result, single nodes aren’t able to affect or withhold the random outputs as none of them are able to anticipate the outcome beforehand. A client cannot prevent the output from getting uploaded on-chain once it has initiated the randomness request.

Conclusion

This is the first of a series of blog posts on on-chain verifiable randomness. In this post, we discussed the impossibility of obtaining unbiasable output in the plain commit-reveal paradigm. Then, we showed that even in the presence of smart contracts there are existing protocols that fail to provide unbiasable randomness.

In the next few posts, we will discuss how to formally capture the properties of unpredictability, unbiasability and public verifiability that are essential for on-chain randomness. Then we’ll dive deep into the VRF-based and Beacon-based approaches for on-chain verifiable randomness.

We have performed a formal analysis of randomness services here.