Randomness
Last updated
Last updated
Randomness in Proof of Stake blockchains is important for a fair and unpredictable distribution of validator responsibilities. Computers are bad at random numbers because they are deterministic devices (the same input always produces the same output). What people usually call random numbers on a computer (such as in a gaming application), are pseudo-random - that is, they depend on a sufficiently random seed provided by the user or another type of oracle, like a weather station for atmospheric noise, your heart rate, or even lava lamps, from which it can generate a series of seemingly-random numbers. But given the same seed, the same sequence will always be generated.
Though, these inputs will vary based on time and space, and it would be impossible to get the same result into all the nodes of a particular blockchain around the world. If nodes get different inputs on which to build blocks, forks happen. Real-world entropy is not suitable for use as a seed for blockchain randomness.
There are two main approaches to blockchain randomness in production today: RANDAO and VRF.
Polkadot uses VRF.
A verifiable random function (VRF) is a mathematical operation that takes some input and produces a random number along with a proof of authenticity that this random number was generated by the submitter. The proof can be verified by any challenger to ensure the random number generation is valid.
The VRF used in Polkadot is roughly the same as the one used in Ouroboros Praos. Ouroboros randomness is secure for block production and works well for BABE. Where they differ is that Polkadot's VRF does not depend on a central clock (the problem becomes - whose central clock?), rather, it depends on its own past results to determine present and future results, and it uses slot numbers as a clock emulator, estimating time.
Slots are discrete units of time six seconds in length. Each slot can contain a block, but may not. Slots make up epochs - on Polkadot, 2400 slots make one epoch, which makes epochs four hours long.
In every slot, each validator "rolls a die". They execute a function (the VRF) that takes as input the following:
The "secret key", a key specifically made for these die rolls.
An epoch randomness value, which is the hash of VRF values from the blocks in the epoch before last (N-2), so past randomness affects the current pending randomness (N).
The slot number.
The output is two values: a RESULT (the random value) and a PROOF (a proof that the random value was generated correctly).
The RESULT is then compared to a threshold defined in the implementation of the protocol (specifically, in the Polkadot Host). If the value is less than the threshold, then the validator who rolled this number is a viable block production candidate for that slot. The validator then attempts to create a block and submits this block into the network along with the previously obtained PROOF and RESULT. Under VRF, every validator rolls a number for themselves, checks it against a threshold, and produces a block if the random roll is under that threshold.
The astute reader will notice that due to the way this works, some slots may have no validators as block producer candidates because all validator candidates rolled too high and missed the threshold. We clarify how we resolve this issue and make sure that Polkadot block times remain near constant-time in the wiki page on consensus.
An alternative method for getting randomness on-chain is the RANDAO method from Ethereum. RANDAO requires each validator to prepare by performing many thousands of hashes on some seed. Validators then publish the final hash during a round and the random number is derived from every participant's entry into the game. As long as one honest validator participates, the randomness is considered secure (non-economically viable to attack).
RANDAO is optionally augmented with VDF.
Verifiable Delay Functions are computations that take a prescribed duration of time to complete, even on parallel computers. They produce unique output that can be independently and efficiently verified in a public setting. By feeding the result of RANDAO into a VDF, a delay is introduced that renders any attacker's attempt at influencing the current randomness obsolete.
VDFs will likely be implemented through ASIC devices that need to be run separately from the other types of nodes. Although only one is enough to keep the system secure, and they will be open source and distributed at nearly no charge, running them is neither cheap nor incentivized, producing unnecessary friction for users of the blockchains opting for this method.
Polkadot's research on blockchain randomness and sortition - contains reasoning for choices made along with proofs
Discussion on Randomness used in Polkadot - W3F researchers discuss the randomness in Polkadot and when it is usable and under which assumptions.
