Randomness generation

Overview

This document presents the randomness generation protocol, used to select the delegates to participate in the consensus, as well as the cryptographic primitives used.

Cryptographic primitives

We introduce RANDAO and Verifiable Delay Functions, two cryptographic protocols for generating random values.

RANDAO

RANDAO is a simple multi-party protocol used to generate a random seed based on a ‘’commit and reveal’’ scheme (similar in spirit with the RANDAO protocol).

During the setup of the protocol, the cryptographic primitives and security parameters are chosen. The members participating in the protocol can also be chosen at this stage.

During the first phase (the “commitment” phase) each party commits to a random value, called the nonce, and publishes the commitment. Typically, a hash function is used for committing.

During the second phase, (the “nonce revelation” phase) each party reveals their nonce. The revealed nonces are then verified with respect to the commitments. Typically, this means checking that the hash of each revealed nonce is equal to its corresponding commitment. If the verification fails, the nonce is discarded, otherwise it is accepted.

Once the revelation phase is finished, nonces are combined to generate the seed. More precisely, the nonces are hashed together in the same order as the commitment publication. In the case of a rolling RANDAO, the previous seed may be used to initialize the hash.

We make the assumption that at least one participant is honest, that is, it has indeed chosen a random value and this value was revealed. This is a necessary condition for the seed to be random. The randomness could however be biased as this protocol suffers from the following low-impact weakness: if a malicious participant can make sure she is the last revealer, then she can choose whether to reveal its committed value, effectively choosing between two different predetermined seeds.

Verifiable Delay Function

Verifiable Delay Functions, also called VDFs, are a recent cryptographic primitive formalized in 2018. They can be seen as a trapdoor-less timelock: the goal of a VDF is making sure a party cannot compute a value before a specific time.

This new cryptographic building block is based on modular squaring in a group of unknown order (e.g. class groups or MPC-generated RSA groups) that is believed to be expensive and hard to parallelize.

More precisely, the goal of a VDF is for a user to compute a certain value h = g^2^T mod N G and a proof of correctness π_h by recursive modular squarings of h. The variables g, h, T and N are respectively the challenge, solution (or output), the difficulty parameter and the -unknown- group order. The main difference between VDF and timelocks is that the latter offers a backdoor to efficiently generate the challenge from the solution.

To this day, two main schemes exist for generating VDF proofs: Wesolowski and Pietrzak. The former presents shorter proofs and is based on a stronger security assumption (adaptive root assumption) while the latter is computationally cheaper and based on a weaker security assumption (low order assumption).

Protocol

Randomness generation overview

The randomness generation uses both RANDAO and VDF, based on class groups and using Wesolowski proofs. It can be summed up as follows. We first use RANDAO to produce biasable entropy which is used as a VDF challenge to generate an unbiasable seed (given the adversary cannot compute the VDF solution before the reveal time ends). To ensure liveness, we fallback to RANDAO entropy if no VDF output was published and verified on-chain.

Concretely, the random seed for cycle n is a 256-bit long number computed at the end of cycle n-1-PRESERVED_CYCLES. It is the VDF output (or, in its absence, the RANDAO output) computed from nonces to which delegates commit during cycle n-2-PRESERVED_CYCLES.

Every BLOCKS_PER_COMMITMENT levels, the corresponding block contains a nonce commitment. More precisely, a block contains a commitment if and only if its cycle position modulo BLOCKS_PER_COMMITMENT is BLOCKS_PER_COMMITMENT - 1. The nonce is a 256-bit number generated by the block proposer and its commitment is included in the block header. The commitment is simply the hash of the nonce.

The committed nonce must be revealed by the original block proposer during the nonce revelation phase, that is during the first NONCE_REVELATION_THRESHOLD blocks, of cycle n-1-PRESERVED_CYCLES under penalty of forfeiting all of its expected endorsing rewards for that cycle. The associated security deposit and baking rewards are not affected. The RANDAO output is then computed and stored on-chain as the temporary seed for cycle n. The RANDAO output is the bitstring obtained by iterating through the nonces revealed in cycle n-1 as follows: initially it is the seed of cycle n-1; at each iteration, the new bitstring is the hash of the concatenation of the previous bitstring with the iterated revealed nonce.

A nonce revelation is an operation and multiple nonce revelations can thus be included in a block. A reward SEED_NONCE_REVELATION_TIP is given for including a revelation. Revelations are free operations which do not compete with transactions for block space. Up to MAX_ANON_OPS_PER_BLOCK revelations, wallet activations and denunciations can be contained in any given block.

During the rest of the cycle, informally called the VDF revelation period, any party can query the protocol for the seed computation status, which can be one of the following:(1) the VDF revelation period has not yet started, i.e. the nonce revelation phase is still ongoing, (2) a VDF solution has already been successfully submitted, and (3) no VDF solution has been submitted. In this latter case, the status also provides the information needed to compute the VDF solution: hash seeds for computing the VDF discriminant (a prime number defining the class group) and the VDF challenge; more precisely the random seed of cycle n-1 for the VDF discriminant and the current RANDAO output for the VDF challenge. Any party can compute a VDF solution and publish it on-chain together with a proof of correctness. If the verification of the solution and proof succeeds, the seed for cycle n is then updated with the solution: its value is set to be the hash of the RANDAO output and the VDF solution.

A VDF revelation is an operation. A reward SEED_NONCE_REVELATION_TIP is given for the first correct VDF revelation, subsequent VDF revelation operations being discarded.

Randomness generation parameters

Parameter name

Parameter value

BLOCKS_PER_COMMITMENT

64 blocks

NONCE_REVELATION_THRESHOLD

32 blocks

MAX_ANON_OPS_PER_BLOCK

132 revelations

SEED_NONCE_REVELATION_TIP

1/8 ꜩ

VDF_DIFFICULTY

1,000,000,000

The variables BLOCKS_PER_CYCLE and PRESERVED_CYCLES are already defined in the proof of stake page.