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 attesting 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 |
|---|---|
|
128 blocks |
|
512 blocks |
|
132 revelations |
|
1/8 ꜩ |
|
8,000,000,000 |
The variables BLOCKS_PER_CYCLE and PRESERVED_CYCLES are already defined
in the proof of stake page.