Updating Randomness - VDF

Context

This MR attempts to make the randomness generation of Tezos more secure by using Verifiable Delayed Functions (VDF). Linked to issue 2844.

At the moment, Tezos uses a commit and proof algorithm called RANDAO where, in a first phase, each member of a committee publishes a commitment of some random coin and, in a second phase, publishes the commitment openings, i.e. the random coins. The revealed values are then combined by hashing them together in order to generate a random seed. The unrevealed values are discarded.

This algorithm is deemed secure if at least one honest member participates. However, it produces "biasable randomness" as it suffers from the “last revealer” attack: the last revealer, seeing all revealed values, can choose to their advantage whether to reveal their commitment, i.e. choosing a seed between two potential values.

Verifiable Delay Functions (VDF) 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, prevents any participant from anticipating what could be the next seed because the fast hash function is replaced by a (provably) long computation.

This MR depends on the class_group_vdf library, which would be a new Tezos dependency (c.f. tezos/opam-repository).

Reviewing the MR

Manually testing the MR

The MR can be tested by running the tezt test for the VDF computation daemon:

dune exec tezt/tests/main.exe -- --file vdf_test.ml

and the protocol tests, particularly proto_alpha/lib_protocol/test/integration/consensus/test_seed.ml

Checklist

• Create and import VDF library to tezos environment

• Update randomness generation to use VDF

  • Limit reveal nonce in time
  • Add VDF module
  • Add VDF reveal operation in apply and incentivize it
  • Update cycle end to choose VDF output if present else RANDAO

• Tests

• Document

• Document the interface of any function added or modified (see the coding guidelines)

• Document any change to the user interface, including configuration parameters (see node configuration)

• Provide automatic testing (see the testing guide).

• For new features and bug fixes, add an item in the appropriate changelog (docs/protocols/alpha.rst for the protocol and the environment, CHANGES.rst at the root of the repository for everything else).

• Select suitable reviewers using the Reviewers field below.

• Select as Assignee the next person who should take action on that MR