Improving Randomness in Tezos with Verifiable Delay Functions

In this article we explain how a novel cryptographic primitive called a Verifiable Delay Function (VDF) improves random seed generation in Tezos. This novel feature was announced in July, and went live with the activation of the Kathmandu protocol in September.

Randomness in a blockchain

Tezos is a blockchain that relies on a consensus mechanism based on proof-of-stake, which requires that participants be chosen at random for each cycle. These participants, or delegates, are appointed to bake and endorse blocks for which they earn rewards. Since a delegate’s stake can fluctuate, randomness is used as a mechanism to fairly distribute baking and endorsing rights based on a discrete probability distribution in proportion to the delegate’s stake.

However, since a blockchain is supposed to be deterministic (everything should be re-computable), how can we achieve randomness? Further discussion on why randomness is challenging in a blockchain can be found here. It is important to be able to produce random numbers in a way that can’t be gamed, since participants have a strong incentive to cheat in order to get more rights and thus more rewards.

Various approaches to getting random numbers in blockchains have been devised. Generally they either rely on external submissions of values that are provably random, or they combine multiple values produced by participants into a single random value. These range from VRF (Verifiable Random Function) solutions, including Chainlink’s VRF to the RANDAO algorithm used in Ethereum. The Tezos whitepaper describes our MPC (multiparty computation) commit-and-reveal scheme. While it precedes Ethereum’s RANDAO, we have subsequently adopted the term since the algorithms are similar.¹

Randomness in Tezos with RANDAO

Prior to Kathmandu, Tezos only used RANDAO (that is, our variant of it). The basic idea is to incentivize participants to submit random values, or “nonces”, that we combine on-chain into a “random seed”. When selected to submit one of these values, delegates stand to lose part of their rewards for a given cycle if they fail to do so.

RANDAO works as follows: to compute a seed for cycle n i.e. seedn, we go back in time to cycle n-2-PRESERVED_CYCLES (PRESERVED_CYCLES is a protocol constant, set to 5 at the time of writing) where we asked delegates to submit commitments to random values commitments{n-2-PRESERVED_CYCLES}. The commitments are hashes of random values. Submitting hashes rather than the random values themselves at this stage is done to prevent an adversary from adaptively choosing its random value to its advantage, for instance to achieve more baking rights and thereby more rewards. In the following cycle, n-1-PRESERVED_CYCLES, the delegates were asked to submit their random values nonces{n-1-PRESERVED_CYCLES}. If the hash of these values equals the corresponding commitment, we store them. The seed is finally computed at the end of the cycle as the hash of the previous target seed and the stored revealed values (in the order in which they were committed): seedn = Randao{n-1-PRESERVED_CYCLES} = Hash(seed{n-1}, nonces{n-1-PRESERVED_CYCLES}). As long as one of the participants is honest (that is, they submit an honestly generated random value), and the hash function is secure, so is the scheme.

Last revealer’s advantage

As previously stated, this algorithm is deemed secure if at least one honest member participates. However, the algorithm isn’t perfect as it can offer an advantage to the last revealer. The last revealer, seeing all revealed values, can choose whether to reveal their commitment or not, in effect choosing a seed between two potential values, resulting in “biasable randomness”. In truth, the advantage can extend to that last n revealers if they collude.

This potential for bias can be mitigated in various ways. Examples include using a 1 bit clock and Avalanche’s RANDAO construction.

The other main alternative to RANDAO for generating unbiased randomness is Threshold Relay which is used in DFINITY. However, it relies on an expensive distributed key generation mechanism ( \(\mathcal{O}(n^2)\) messages for n members) and high liveness requirements—the beacon may stall if even 15% of honest players go offline.

Unbiased randomness with Verifiable Delay Functions

Currently, the most sophisticated method to remove this bias in RANDAO is by using a Verifiable Delay Function (VDF). VDFs are a novel cryptographic primitive that allow a verifier to check that a value was computed by a prover as a result of a long computation. Appending a VDF phase after our current RANDAO scheme would prevent any participant from anticipating what the next seed might be, because the fast hash function is replaced by a (provably) long computation. While VDFs are state-of-the-art cryptographic primitives they were recently integrated into Tezos with the activation of the Kathmandu protocol upgrade. Ethereum is planning to add VDF for random number generation in the future².

For the implementation of the underlying cryptographic primitive, we adapt the VDF library developed by Chia. Chia however doesn’t use it for random number generation, but rather for creating time slots in its consensus algorithm, to prove some amount of elapsed time.

Seed Generation with VDF

The diagram below illustrates the steps in creating a random seed with VDF.

RANDAO with VDF works as follows:

1. In cycle # n-2-PRESERVED_CYCLES the parties publish commitments to random values;
2. In cycle # n-1-PRESERVED_CYCLES the nonces are revealed, but the revelation phase is now shortened from the entirety of the cycle to only the first NONCE_REVELATION_THRESHOLD blocks;
3. At block NONCE_REVELATION_THRESHOLD, the RANDAO output is then computed and used to instantiate a hidden order group (an algebraic group whose number of elements is unknown), and a challenge to compute a VDF solution for. Any party can query the information needed to compute the VDF solution through RPCs;
4. The first baker to disclose the correct solution before the end of cycle n-1-PRESERVED_CYCLES receives a small tip;
5. The random seed for cycle n is then computed as either the hash of the RANDAO output and the VDF solution, if a valid VDF solution is received, or the RANDAO output otherwise.

That is, seedn = Hash(Randao{n-1-PRESERVED_CYCLES}, VDF{n-1-PRESERVED_CYCLES}), or seedn = Randao{n-1-PRESERVED_CYCLES} if no valid VDF was submitted in cycle n-1-PRESERVED_CYCLES.

Note that even with a valid VDF output we still use the time-tested RANDAO when computing the randomness seed, as shown in step 5, in order to make the whole system more robust. Indeed, while the VDF output can be considered as unpredictable it may not be random enough, hashing it guarantees the seed randomness. See the Tezos documentation and this Medium article for more details on VDF.

Conclusion

The regular upgrade cycles of the Tezos protocol mean the latest advances in cryptographic research can be quickly implemented into the protocol. While the RANDAO protocol is used in a number of blockchains, and while VDFs are widely discussed, Tezos is currently the only blockchain which uses it for randomness generation, making random seed generation in Tezos highly robust compared to its competitors.

And that is the ethos of Tezos: to continuously monitor new research and technological developments, evaluate what’s best suited to be adopted, and integrate it quickly.