What is a random beacon and why do we need it for Flow?

There are many sub-protocols in Flow, whose security relies on random sampling from a specific population. Examples:

• Assigning verification nodes to check specific chunks of a block. Here, the population are all verification nodes. For each chunk we need to select a relatively small number of verification nodes to check the chunk's computation.
• Before a new epoch starts, we need to partition all collector nodes (population) for the next epoch into clusters.

For this random sampling process to be secure and resilient against byzantine participants, we require some important properties:

1. The random sample must be deterministic and verifiable.

   All nodes should be able to re-generate the sample locally to confirm that it was generated properly. Thereby a malicious node can't bias the sample in its favour.

   Generally, we achieve this by using a specific seed and a pre-determined deterministic Pseudo Random Number Generator (PRNG). Thereby, any node that knows the seed can re-generate the sample locally by running the PRNG.

2. The sample needs to be unbiasable by a few malicious colluding nodes.

3. The sample needs to be unpredictable till it is generated.

   For performance reasons, Flow works with probabilistic safety guarantees. We accept that with vanishing (yet non-zero probability), a faulty result could not be discovered and committed into the chain. Probabilistic safety is sufficient for all practical purposes, if and only if it is very expensive to attempt to inject a faulty result (we slash the node) and the chances of being successful with such an attack are sufficiently low.

   To guarantee low success probability, we need the sample to be unpredictable. Otherwise, an attacker could play by the rules until favourable situation occurs and then attack the network.

A random beacon is a solution to this challenge. It can be used to generate seeds for PRNGs in a unpredictable, unbiasable and verifiable way.

Pseudo-Random-Number Generator Seeds

The Random Beacon produces a source of randomness ([48]byte).

In a nutshell, the source of randomness provides a starting point for initializing pseudo-random-number generators locally within the nodes.

The source of randomness should not be used as a seed for a Pseudo-Random-Number-Generator directly since its structure is not uniform (it is a cryptographic BLS signature). Instead the seed is obtained by hashing the source of randomness to “uniformize” its entropy over all the seed bits. We use an extendable output function (xof) to generate the number of seed bytes we need.

Details

• The output sequence of a pseudo-random-number generator (PRNG) depends only on the prng's seed and the customizer. Hence, two prngs initialized with the same seed and customizer, will generate identical sequences.
• We only have a single source of randomness. But we have various different tasks that require randomness. We would like to avoid using the same random sequence for different tasks, we therefore use the customizer to diversify the random sequences per task.