Randomness¶
Introduction¶
Randomness is crucial in Proof of Stake (PoS) blockchains to ensure a fair and unpredictable distribution of validator duties. However, computers are inherently deterministic, meaning the same input always produces the same output. What we typically refer to as "random" numbers on a computer are actually pseudo-random. These numbers rely on an initial "seed," which can come from external sources like atmospheric noise, heart rates, or even lava lamps. While this may seem random, given the same "seed," the same sequence of numbers will always be generated.
In a global blockchain network, relying on real-world entropy for randomness isn’t feasible because these inputs vary by time and location. If nodes use different inputs, blockchains can fork. Hence, real-world randomness isn't suitable for use as a seed in blockchain systems.
Currently, two primary methods for generating randomness in blockchains are used: RANDAO and VRF (Verifiable Random Function). Polkadot adopts the VRF approach for its randomness.
VRF¶
A Verifiable Random Function (VRF) is a cryptographic function that generates a random number and proof that ensures the submitter produced the number. This proof allows anyone to verify the validity of the random number.
Polkadot's VRF is similar to the one used in Ouroboros Praos, which secures randomness for block production in systems like BABE (Polkadot’s block production mechanism).
The key difference is that Polkadot's VRF doesn’t rely on a central clock—avoiding the issue of whose clock to trust. Instead, it uses its own past results and slot numbers to simulate time and determine future outcomes.
How VRF Works¶
Slots on Polkadot are discrete units of time, each lasting six seconds, and can potentially hold a block. Multiple slots form an epoch, with 2400 slots making up one four-hour epoch.
In each slot, validators execute a "die roll" using a VRF. The VRF uses three inputs:
- A "secret key," unique to each validator, is used for the die roll
- An epoch randomness value, derived from the hash of VRF outputs from blocks two epochs ago (N-2), so past randomness influences the current epoch (N)
- The current slot number
This process helps maintain fair randomness across the network.
Here is a graphical representation:
The VRF produces two outputs: a result (the random number) and a proof (verifying that the number was generated correctly).
The result is checked by the validator against a protocol threshold. If it's below the threshold, the validator becomes a candidate for block production in that slot.
The validator then attempts to create a block, submitting it along with the PROOF and RESULT.
So, VRF can be expressed like:
(RESULT, PROOF) = VRF(SECRET, EPOCH_RANDOMNESS_VALUE, CURRENT_SLOT_NUMBER)
Put simply, performing a "VRF roll" generates a random number along with proof that the number was genuinely produced and not arbitrarily chosen.
After executing the VRF, the RESULT is compared to a protocol-defined THRESHOLD. If the RESULT is below the THRESHOLD, the validator becomes a valid candidate to propose a block for that slot. Otherwise, the validator skips the slot.
As a result, there may be multiple validators eligible to propose a block for a slot. In this case, the block accepted by other nodes will prevail, provided it is on the chain with the latest finalized block as determined by the GRANDPA finality gadget. It's also possible for no block producers to be available for a slot, in which case the AURA consensus takes over. AURA is a fallback mechanism that randomly selects a validator to produce a block, running in parallel with BABE and only stepping in when no block producers exist for a slot. Otherwise, it remains inactive.
Because validators roll independently, no block candidates may appear in some slots if all roll numbers are above the threshold.
Note
The resolution of this issue and the assurance that Polkadot block times remain near constant-time can be checked on the PoS Consensus page.
RANDAO¶
An alternative on-chain randomness method is Ethereum's RANDAO, where validators perform thousands of hashes on a seed and publish the final hash during a round. The collective input from all validators forms the random number, and as long as one honest validator participates, the randomness is secure.
To enhance security, RANDAO can optionally be combined with a Verifiable Delay Function (VDF), ensuring that randomness can't be predicted or manipulated during computation.
Note
More information about RANDAO can be found in the ETH documentation.
VDFs¶
Verifiable Delay Functions (VDFs) are time-bound computations that, even on parallel computers, take a set amount of time to complete.
They produce a unique result that can be quickly verified publicly. When combined with RANDAO, feeding RANDAO's output into a VDF introduces a delay that nullifies an attacker's chance to influence the randomness.
However, VDF likely requires specialized ASIC devices to run separately from standard nodes.
Warning
While only one is needed to secure the system, and they will be open-source and inexpensive, running them involves significant costs without direct incentives, adding friction for blockchain users.
Additional Resources¶
- Polkadot's research on blockchain randomness and sortition - contains reasoning for choices made along with proofs
- Discussion on Randomness used in Polkadot - W3F researchers explore when and under what conditions Polkadot's randomness can be utilized
| Created: October 16, 2024