RANDAO: Under the Hood
Ethereum’s POS dreams came true because of RANDAO - it was the only one which could replicate the chaos known as 'randomness', on chain.
Randomness is crucial in cryptography. For example, we need a private key to access the assets in an Ethereum account. This private key should be randomly generated in a way that no one else can generate it. Why can’t you just think of a random number on your own? Turns out, humans are really poor sources of randomness.
We need to rely on computers to generate random numbers for us. If a secure random number generator is used, the key will be unpredictable and the system will be secure. Hence, “secure random” simply means “unpredictably random”.
Randomness in Computing
Computers are deterministic machines. A program should always result in the same output when given the same input. Modern computers still need random numbers for a lot of important applications. For instance, if you don’t have access to random numbers, anyone can figure out the private key for your Ethereum account. It is obvious that there must be a technique for computers to produce "randomness".
To produce random numbers, computers typically rely on the notion of "reasonably unpredictable" external inputs. In computer science, random numbers usually come from Pseudorandom Number Generators (PRNGs).
The seed is a starting point from which computations are performed to generate a reasonably random number. The seed can be anything - the cursor movement on your screen (check BitAddress), Cloudfare’s camera focusing on lava lamps or the chaotic radio noise generated by nature. Computers collect entropy and then “stretch” the available entropy into more bits needed for cryptographic purposes by using cryptographic hash functions.
If the seed is generated by us and the same math is used on it every time, how can we consider it random? The point is, when enough difficult-to-repeat seeds are combined, the outcome is reasonably random. This is relatively trustworthy because it is hard for a human to repeatedly move their mouse in the same way over a display made of millions of pixels.
The Need for Randomness
How does Ethereum decide who’s turn is it to propose a block, and which validators should attest to that proposal? How does it make this choice among the numerous shards and thousands of validators active at any given time? It needs randomness.
In a safe setting, a predictable protocol could work well. But we must presume that our protocol will be attacked, and predictability leaves a lot of room for successful attacks. There is an issue though - there are no sources of randomness on a blockchain.
Some rely on the blockhash, which is acceptable for basic provably fair gambling. In PoW, it seems rational for a miner to misbehave if their profit from manipulating the blockhash is greater than the block reward. In PoS, we need to consider validator selection. If the validator currently in charge of producing a block can manipulate it so that the blockhash turns into a seed that will once more choose them or one of their other validator clients as the proposing validator, they can hoard the proposal queue and keep proposing, preventing others from making significant profits.
Undoubtedly, there is a need for stronger randomness on blockchains, especially for Proof of Stake.
Block Proposers
It’s a blockchain - someone will have to produce blocks. There are many possible ways to select a block producer, but there is one key property we need to preserve - the selection process must be fair to all validators.
Assuming the same amount of stake (can be modified to work for varying stakes), a simple solution would be to make a sorted list of validators, and then allow each validator to produce a block based on their position in the list. This “round-robin” system gives an equal chance to each validator, without needing any randomness. But an attacker will know well in advance who’s going to produce blocks and when. They could then plan DoS attacks on a certain validator and prevent them from producing a block. Or validators could conspire with their neighbours to make the network come to a halt for a considerable length of time.
Since these attacks become a lot harder to execute when there’s no predictability, we have a solution: use random numbers to pick block producers in each epoch. We just need to ensure that the process of generating random numbers is hard to rig.
Committees
Sharding is a major step in Ethereum’s roadmap. A sharded Ethereum relies on committees (certain groups of validators) to perform actions like voting on whether a block is valid within a shard. Committees are crucial for the security of such a system.
If an attacker gains 2/3rds of a committee voting on the validity of a shard block, then they might cause an invalid shard to be considered valid by the rest of the network. Although users can submit fraud proofs in case of such an event, the chain would still have to be rolled back to the point before the invalid shard. This would be pretty inconvenient, a major disruption. Hence, we need a good source of randomness that prevents such an event from happening.
Note: There will only be one block proposer if Danksharding happens, but the gist remains the same.
Applications
Many blockchain applications, like on-chain poker and lotteries, rely on good sources of randomness. These applications are only as good as their mechanism for generating random numbers.
Since generating securely random numbers is a tough task, it is important for the protocol to provide primitives like randomness - application developers shouldn’t have to worry about these things.
On-Chain Randomness
If we were dealing with a single computer, we could simply generate a random number using a CSPRNG and our job would be done. But it’s a blockchain that we’re dealing with. Unlike a computer, Ethereum is a closed system - isolated from the outside world.
Transactions are the only way for data to enter Ethereum. To get a random number into Ethereum, someone will have to create a transaction that holds this number. A preliminary solution to this problem would be to assign this job to a single individual, but there’s a problem here: we will have no way to know whether they’re really publishing random numbers or numbers that just seem random. They could simply be publishing a number that will help them win a lottery on Ethereum.
Although the potential solutions to this problem are varied, there’s one central idea behind them all - minimizing any single entity’s power to manipulate this random number. Most solutions achieve this by having multiple individuals collectively create a random number.
RANDAO
RANDAO is a system for “reasonably random" number generation in a decentralized manner. The fundamental idea: a large number of individuals work together to produce a random number rather than entrusting the responsibility to any single person.
An elementary form of RANDAO is to have each member of a group generate a random number on their own. These random numbers are then combined in a way that ensures that each of these numbers have an equal influence on the outcome.
Mixing Functions
Systems using RANDAO need a function that takes input values from each participant and produces an output. This function is called the mixing function. Mixing functions follow the general syntax:
mix (input₁ + input₂ + … + inputₙ) → output
There is one central property that all mixing functions must preserve: all inputs have an equal impact on the output value. So we must avoid functions that simply discard every other input value or always return a constant value. Since RANDAO systems accept numbers as inputs, we can represent each input as a string of bits (0s and 1s).
Let’s consider a simple mixing algorithm using ‘Exclusive Or’ or XOR. The output of a XOR is 1 if an odd number of inputs are true (that is, have the value 1). So, a XOR (denoted using ⊕) with two input bits would result in an output bit according to these rules:
0 ⊕ 0 = 0
0 ⊕ 1 = 1
1 ⊕ 0 = 1
1 ⊕ 1 = 0
RANDAO inputs are numbers that are represented using multiple bits. Let’s say I have to find 1111 ⊕ 1001 = ?
We’ll simply apply the operation bitwise, from left to right. Since 1 ⊕ 1 = 0, the leftmost bit of our output is 0. Similarly, the second digit from the left will be 1 and so on. We get the result 1111 ⊕ 1001 = 0110.
If there are more than two numbers as inputs, we can perform XOR by moving from left to right. For instance,
1111 ⊕ 1001 ⊕ 0101
= (1111 ⊕ 1001) ⊕ 0101
= 0110 ⊕ 0101
= 0011
A simple RANDAO mixing function with XOR would be:
mix (input₁ ⊕ input₂ ⊕ … ⊕ inputₙ) → output
The mixing function can be anything - it doesn’t have to be a XOR. Let’s say we use a cryptographic hash function to combine the inputs. The function would then take the form:
hash (inputₙ + hash(inputₙ₋₁ + … + hash(input₂ + input₁) → output
The Last Participant Advantage
What we’ve looked at: a simple RANDAO system. There’s a major problem here though. If the participants can see each others’ inputs, the last participant has an advantage - they can change their input to get a value they like.
Let’s consider a simple RANDAO system using a XOR mixing function with 5 inputs. For example, the first four values are: 1000, 0101, 1110 and 1001. The resultant XOR value would be:
1000 ⊕ 0101 ⊕ 1110 ⊕ 1001
= 1101 ⊕ 1110 ⊕ 1001
= 0011 ⊕ 1001
= 1010
An attacker can now easily pick a value that ensures the final output is a number they’ll like. For instance, the attacker wants the final value to be 0000. They can simply calculate the current value and then submit it as their input. If they want the result to be 1111, they can simply flip each of the bits of the current value. This way, an attacker can manipulate the result to be any number they’d like.
This attack is not limited to a XOR mixing function, it could also happen in the mixing function using hashes. It would be a slightly harder though - an attacker will have to test a bunch of potential values. We prefer mixing functions of this sort, where it’s relatively tougher to cheat.
To Commit, or Not to Commit
The last participant can cheat because they know what the other participants’ inputs. What if the participants don’t have to reveal their inputs to the other participants? This would be problematic if there wasn’t a way to check whether they really did submit the number they claim to have submitted. Fortunately, there is a way: cryptographic commitments.
Cryptographic commitments are a way to hide a secret in a manner that makes it impossible to lie about the original secret later. Given a commitment, the value of the original secret can’t be figured out. But given a potential secret value, we can check whether its corresponding commitment is the same as the commitment of the original secret. If the commitments are the same, then the potential secret must be the original secret. This scheme is frequently called commit-reveal.
One way to implement a commitment is to simply use a hash function - each participant submits the hash of their input value instead of submitting the value itself. The original value can’t be guessed from the commitment (hash), and it is easy to check whether the commitment actually corresponds to a specific value.
There’s still an issue (we never run out of issues in this space!) with commitments - while they prevent a participant from changing their number at the last moment, they don’t actually force the participant to reveal their number. While this flaw doesn’t really break RANDAO, it does make RANDAO somewhat biased.
The final participant only gets one more chance to find a favourable number. If the last n people to reveal their inputs are conspiring, then they have a total of 2ⁿ attempts. Although this scenario is not perfect, it is a significant improvement from the unlimited attempts one got without commitments in place. This is good enough for Ethereum.
RANDAO in Ethereum
RANDAO was always a part of the Beacon Chain’s design to fulfil its need of in-protocol randomness. The chain maintains a RANDAO value and with each block, the proposer adds a random contribution to the existing RANDAO value. The RANDAO value is not updated if there is no block in a slot.
Put simply, every block included in the chain has a verifiable random value. This value is provided by the validator who proposed the block. As the block gets processed, its random value gets mixed with the chain’s RANDAO value. Hence, each block proposer contributes to the chain’s RANDAO value. The benefit in doing so: even if one contributor’s random value is weak, the cumulative result will still be unpredictably random.
The chain also stored the past RANDAO values in addition to its current value. This can be used for the recalculation of past committee assignments, which in turn enables slashing historical attestations even months down the line.
While the block proposer has no choice about what it contributed to the RANDAO, they do have the choice to withhold their block. This means that a proposer either contributed a single verifiable random value, or they commit nothing.
The Beacon Chain runs RANDAO once every epoch. The designated validator reveals a commitment within each block. These revealed values are combined to create a random number at the end of each epoch.
Contributing to RANDAO
We’d used the term “verifiable random value” in the above section. What does that mean? Put simply, it’s the duty of a block proposer to include a field (called randao_reveal) containing the block’s contribution to the chain’s RANDAO value. “Verifiable” refers to the fact that this value cannot be arbitrary, even though it is random in nature - otherwise the proposer might as well include a value of their choice.
In any given block, there is only a single valid contribution that the proposer can make, and this contribution can be verified by all other nodes. At the same time, this contribution cannot be predicted by any other node. A block with an incorrect reveal is invalid.
Hash Onions
In early concepts of verifiable randomness, each validator had to pre-commit to a “hash onion”. A validator would provide a random number before becoming a part of the beacon chain. The outcome of repeatedly cryptographically hashing that number a huge number of times (thousands of times) would be included by the validator when registering its initial deposit, as a commitment.
The validator’s contribution to RANDAO would then be the pre-image of that commitment when a block was proposed (peeling one layer off the onion). Only the proposer could calculate this value because a cryptographic hash is not invertible, but it is simple for anybody to verify. The new commitment is then saved after the disclosure, and so forth. This plan is workable, but there are complications and edge cases.
BLS Signatures
With the introduction of BLS signatures to the protocol, an obvious replacement for hash onions became available. This approach takes into consideration the fact that each validator already has closely guarded, secret random value - the secret key which validators use to sign block and attestations. The digital signatures produced using this secret key are random. As a result, the block proposers’ BLS signatures are a great source of the randomness we need to update the RANDAO.
Switching to BLS signatures led to a simpler protocol and also allowed the existence of multi-party (distributed) validators. Since BLS signatures can be aggregated, signatures from multiple validators can be combined into a single threshold signature, in turn enabling them to function as a single validator.
For these reasons, BLS signatures are now used as entropy contributions (randao_reveal) to update RANDAO.
Updating the RANDAO
A validator includes the field randao_reveal (of the BLS signature type) when they propose a block. This signature is a result of using the proposer’s secret key over the epoch number. This signature is first verified using the proposer’s public key before being mixed into the RANDAO.
The hash of this signature is then mixed in to the chain’s RANDAO value using the xor operator.
Lookahead
The duties of any block proposer or committee member should, in theory, not be known before they become active. But in the real world, they need some notice in advanced to prepare for their duties. Hence, validators get notified of their duties at least one epoch in advance (a maximum of two).
If an attacker holds a large portion of the stake, then might, for instance, be able to carry out a DoS attack against block proposers for some time. This might allow the attacker to predict RANDAO’s output further down the line than allowed normally. The attacker might then use this knowledge to their advantage - like strategically exiting validators or making deposits to gain control of a committee.
This attack is not easy to carry out, but it has a simple solution. The maximum feasible lookahead (set to 4 epochs) an attacker might achieve is taken into consideration. All activations and exits are then delayed by this amount. This gives new randomness time to enter via block proposals from honest validators, rendering any manipulation by the entering or exiting validators irrelevant.
Verifiable Delay Functions
We know that RANDAO is susceptible to bias, but it is not susceptible enough to break the protocol. The resultant randomness is good enough for the protocol.
After the Merge, Ethereum’s smart contract layer will have access to RANDAO. Since biasability in consensus layer might not be as problematic as biasability in a huge lottery, we need to consider how the commit-reveal RANDAO model can be improved.
Using a verifiable delay function (VDF) is the long term solution to the biasability problem. Although the output of a VDF is guaranteed to be computed slowly, the output can be verified quickly.
VDFs are essentially slow-running algorithms that cannot be made faster by running them simultaneously on multiple computers. The time it takes a regular computer to find an output can be altered by tuning a parameter in the VDF. While VDFs are intriguing on their own, they really come into their own when combined with RANDAO.
The concept of incorporating VDFs revolves around RANDAO updates coming from the VDF’s output. We can first feed the RANDAO result into a VDF and utilise the output as our final random number rather than just using the RANDAO result directly.
A proposer would have to decide whether to commit its randao_reveal before it is possible for it to compute the future output of the VDF. As a result, the RANDAO is free from opportunistic bias.
Despite the fact that a lot of work has been put on building and defining VDFs, there is currently no active plan to deploy one in Ethereum.
This marks the end of this article. ヽ(•‿•)ノ
If you have any suggestions, comments or just want to suggest a song– you can find me on Twitter at @gryptooo . Thanks for reading. :)