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 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.

.. _vdf_alpha:

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 <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_alpha:

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-CONSENSUS_RIGHTS_DELAY``. It is the VDF output (or, in its
absence, the RANDAO output) computed from nonces to which delegates commit
during cycle ``n-2-CONSENSUS_RIGHTS_DELAY``.

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-CONSENSUS_RIGHTS_DELAY`` 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``, :ref:`potentially adjusted
by the adaptive issuance coefficient <adaptive_issuance_alpha>`, 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``,
:ref:`potentially adjusted by the adaptive issuance coefficient
<adaptive_issuance_alpha>`, 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``
     - 192 blocks
   * - ``NONCE_REVELATION_THRESHOLD``
     - 768 blocks
   * -  ``MAX_ANON_OPS_PER_BLOCK``
     - 132 revelations
   * - ``SEED_NONCE_REVELATION_TIP``
     -  1/8 ꜩ
   * - ``VDF_DIFFICULTY``
     - 8,000,000,000

The variables ``BLOCKS_PER_CYCLE`` and ``CONSENSUS_RIGHTS_DELAY`` are already defined
in the :doc:`proof of stake <proof_of_stake>` page.