owned this note
owned this note
Published
Linked with GitHub
# Randomness On Chain: A Suspiciously Devious Problem and Some Solutions
Written by neepheid, cha0sg0d, yush_g, with thoughts by ludens
Note: All of the thinking in this post has already been done many times in the past, including [this blog post](https://blockdoc.substack.com/p/randao-under-the-hood) and [this research conference](https://vdfresearch.org/). Our goal with this post is to strip away all the complexity of understanding eth2 and instead discuss the specific usecase of randomness in smart contracts.
## Introduction -- usecases for on-chain randomness
- Having an on-chain source of randomness enables of host of games, NFT mints, and financial mechanisms.
- Currently, most Dapp developers use a randomness oracle (like Chainlink) or some version of the hash of a previous block (blockhash).
- As discussed below, a blockhash can be easily manipulated by a malicious actor and there is [overhead](https://docs.chain.link/vrf/v2/subscription/examples/get-a-random-number) and [cost](https://docs.chain.link/vrf/v2/subscription/) involved with setting up Chainlink, as well as a trust assumption on their protocol
- Baked into the core Ethereum protocol is a "reasonably" (defined below) random value referred to as `PREVRANDAO` that is generated by the proposer of each block, accessible via the `difficulty` opcode.
- This post will share some background about how the `PREVRANDAO` value works and propose a use case for on-chain games that enables developers to access a better source of randomness than `blockhash` in just a few lines of code.
## Why blockhash doesnt work on L1
- It's very easy to manipulate this. Anyone can just run a node, collect transactions, and simulate sending an extra transaction of 0.00001 eth, 0.00002 eth, etc, and see what would bias the blockhash to be correct. They could then just send that transaction to the mempool, where it would be picked up and included if the gas was high enough -- it doesn't take being a sophisticated block producer or even being a staking validator to do so.
## Why blockhash mostly works on most L2s
- For L2s in which there is a centralized sequencer and mostly-private mempool, the only person who can even simulate the sequencer is likely the org running the L2 itself. This is the case for both Optimism and Arbitrum, for instance.
- This means blockhash is a reasonable randomness seed in the sense that users cannot take advantage of it, but the sequencer can
- For decentralized sequencers, this becomes more difficult.
## Why difficulty = PREVRANDAO opcode works for most L1 contracts
- RANDAO is updated every block, if the proposer contributes their block.
- Note: When people online say that RANDAO is updated every epoch, what they are referring to is that the specific RANDAO value every 32 blocks is used to determine the next set of validators, and the other 31 values per epoch, while useless for influencing the consensus layer, still update each block.
- The specific function is $PREVRANDAO_{new} = PREVRANDAO \oplus hash(sign_{bls}(pk_{proposer}, epoch\_number))$ -- since the proposer changes each block, this changes every block. Thus, randomness does in fact update with each honest proposer submitting a block, and thus the value is different on chain every block (this can be verified by looking at a [few](https://etherscan.io/block/15991533#consensusinfo) [consecutive](https://etherscan.io/block/15991534#consensusinfo) [etherscan](https://etherscan.io/block/15991535#consensusinfo) blocks' consensusinfo).
- The issue with this is that a malicious proposer still has 1 bit of influence over the value, by choosing to not submit their randomness (i.e. their BLS signature) that block. The randomness then will not change and be the same 2 blocks in a row. If the reward for doing so on-chain is more than the slashing penalty, it is economically advantageous to execute this policy as a block builder.
## How to make PREVRANDAO work on an L2
- PREVRANDAO only works on contracts deployed to the L1, not to L2
- We might be able to "fetch" recent L1 randomness on Bedrock by using the [L1Block](https://github.com/ethereum-optimism/optimism/blob/develop/packages/contracts-bedrock/contracts/L2/L1Block.sol) predeploy.
- However, the L2 will know the L1 randomness in advance, so this isn't an advisable solution
- We recommend that L2's define their own PREVRANDAO, which can be set to the value of hash(signature(L2 block number, sequencer public key)). To avoid the sequencer from manipulating on-chain events where this value would be convenient, it can be XOR'ed with the most recent L1 PREVRANDAO value, which puts some bound on how far in advance they can start to grind blockhashes/transactions for randomness. This can be fraud proved quite easily as well.
- Note that any solution that depends on a centralized sequencer will mean that this sequencer can grind through values and exploit on chain mechanisms if they wanted to. This shifts the trust assumption from all MEV players on the L1 to the single L2 sequencer, but is still a strong trust assumption nevertheless.
## The VDF on blockhash solution
Unfortunately, because VDFs have been [largely disproven](https://ethresear.ch/t/statement-regarding-the-public-report-on-the-analysis-of-minroot/16670/2), security of this is now a bit more dubious. I think you can still just jack up the advantage and calibrate over time as people calculate it faster, but you open yourself to one-time attacks.
We want a solution where randomness is atomic from the perspective of the user (i.e. they only send 1 transaction) and no one can manipulate any aspect of it, not even 1 bit. Consider this, for determining the randomness at any block n. The value of this rnadomness is $$VDF_{24\ seconds}(blockhash_{n-3})$$
To break this down, imagine seeding a 24 second verifiable delay function on the blockhash. The important thing about 24 is that it is more than 12, since blocks must be 12 seconds long in proof of stake (in proof of work, this wouldn't work since block times are variable). Then, any block producer might be able to change this value, but they wouldn't have enough time to calculate the effect of changing the blockhash before having to publish it, so it would not be manipulatable. Then, the first person to correctly send the VDF on chain at block n would pass the VDF verification function that updates the randomness stored on chain for everyone queried at block n. Since any client interacting with the randomness at that block would need the value of this VDF, default frontend game clients can run the VDF bashing behind the scenes as well, which has the added benefit of sometimes being able to score the player some of this MEV reward.
Notably, this randomness can also be submitted by any MEV searcher if we reimburse gas for updating randomness, and either run our own MEV searcher or publicize on keepr.network. This means the user (game player, NFT buyer, etc) only has to interact with 1 transaction on the chain.
## Proof of concept walkthrough: random on-chain weather
In this scheme, we split weather changes into $n$-block "spans", where every $n$th block provides the random weather seed for the next $n$ blocks (including itself).
*For example, with spans of length 5, the $RANDAO$ value for block 10 acts as the random seed for blocks 10, 11, 12, 13, and 14.*
1. Once block $b$ is mined, it's $RANDAO$ value is revealed and the weather for this "span" can be calculated off-chain.
2. The smart contract cannot access $RANDAO$ directly, so players who interact between block $b$ and $b+n$ must *pass in* $RANDAO_b$, which the contract can then verify.
3. Finally, the contract uses $RANDAO_b$ as a random seed to calculate the weather.
- For example, if there are four possible weather states, the weather could be $RANDAO_b$ modulus 4.
- You could also cache the randomness for block $b$ and fetch that on each contract call.
There isn't a specific "execution time". We just commit to some future blocks randomness and use that to impact subsequent player events.
To briefly expand on the signficance of the abovee a construction, let's imagine what can happen in a game with on-chain weather. Note that the objective is *not* that the weather is unknown when submitting a transaction, it's that the weather cannot be manipulated.
This mirrors our real world:
1. At any given moment, the weather is known.
2. I have a strong estimation of what the weather will be in the near future.
3. I cannot predict what
- TO ANSWER: To what extent is my 2019 macbook slower than the fastest ASIC in the world on i.e. minroot?