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 <https://github.com/randao/randao>`_).

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 initilialise the hash.

We make the assumption that at least one participant is honest, that is, it
has indeed chosen a random value and this values 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 VDF, are a recent cryptographic
primitive formalised in 2018. They can be seen as a trapdoor-less timelock:
the goal of 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 and T are respectively called the challenge,
solution, and difficulfy parameter. 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 the VDF proofs:
`Wesolowski <https://eprint.iacr.org/2018/623>`_ and
`Pietrzak <https://eprint.iacr.org/2018/627>`_.
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 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 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* to compute the
VDF solution and publish it on-chain together with a proof of randomness.
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 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.

.. _rg_constants_alpha:

Randomness generation parameters
^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^

.. list-table::
   :widths: 55 25
   :header-rows: 1

   * - Parameter name
     - Parameter value
   * - ``BLOCKS_PER_COMMITMENT``
     - 64 blocks
   * - ``NONCE_REVELATION_THRESHOLD``
     - 64 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 :doc:`proof of stake <proof_of_stake>` page.