Verifiable Off-Chain Calculations
Thanks to Rocket Scientists Valdorff and poupas as well as Relic Protocol researcher and developer tjbecker for discussing this design and giving early feedback.
One of the current oDAO duties is providing an oracle for rETH. The exchange rate is defined using the current supply of rETH and the ETH backing it. ETH is spread across many locations: the minipool contracts (on the execution layer), validators (on the beacon chain), the node distributor contracts, the deposit pool, the rETH contract, and the smoothing pool. Outside of the validator balances, all of these live on the execution layer, so one might think that it is as simple as looping over them and summing them up. But since on-chain computation costs gas and there is limit on how much we can spend (the block gas limit), this kind of loop is not possible at the scale of Rocket Pool. This section describes a design that addresses this challenge without the need for trusted oracles and lets anyone participate in updating the rETH rate. I begin with introducing some concepts that it uses before at first, before giving an overview and conclude by exploring some more potential application within Rocket Pool.
Building Blocks
Merkle trees make blockchains work: they are a way to commit to data efficiently and allow for cheap verification of values. (See Merkling in Ethereum for an intro.) A Merkle Sum Tree is a special Merkle tree where each leaf has a numeric value and each inner node contains the hash and the sum of the children. This means that the root of a Merkle Sum Tree is a commitment to all the leaves as well as to the sum over all leaves. For example, Vitalik recently suggested using them as a proof-of-solvency for CEXes: The exchange would build a tree over all user balances to prove their total liabilities. Each user would be able to verify that their correct balance was included in the total using a Merkle proof. Combined with a proof of assets, this would prove solvency of the exchange while preserving user privacy.
An Ethereum block header contains merkle roots as well, in particular the state root, which allows merkle proofs about the state of Ethereum at that block. The EVM gives access to the 256 most recent block hashes (that's 51.2 minutes) through the BLOCKHASH opcode. That means we can for example prove the balance of a specific address or the value of a smart contract variable at a certain block. Relic Protocol makes such Historical State Proofs accessible and allows proofs beyond the EVM's 256 block limitation.
Optimistic Fault Proofs are used by optimistic rollups like Optimism and Arbitrum. Anyone can make an assertion about state — in the case of rollups about the state of the L2 — and commits to it by providing a Merkle root. The system is called "optimistic", because the assertion will be accepted without a proof after a challenge period. During the challenge period anyone can provide a fault proof (also known as fraud proof) to prevent the value from being accepted. Non-interactive fault proofs allow proving the incorrectness of an assertion directly, while interactive fault proofs require multiple rounds between the asserter and the challenger.
Putting it all Together
Lets say we are interested in adding up all the ETH belonging to rETH across all the minipool smart contracts (this could be extended to include node fee distributors). The idea is to use an optimistic system where anyone can calculate the sum off-chain and commit to that value by providing the root of a Merkle Sum Tree. During a challenge period, anyone can produce a fault proof to invalidate a proposed solution. Fault proofs use historical state proofs to show why the submitted root is incorrect. If a proposal isn't challenged, that value is used to update the rETH rate.
Non-Interactive Version
In this version, the attester would submit on-chain:
The block number for which balances are calculated (no older than 256 blocks)
as calldata: indexed balances of each minipool
The smart contract would then:
store the corresponding block hash
calculate and store the root of the Merkle Sum Tree
store the number of leaves
The Rocket Pool contracts maintain an indexed set of minipool addresses and also store the number of items in the set, which allow a challenger to provide two types of proofs: if a proposer provided too little or too many values, a challenger can provide a historical state proof about the correct number of minipools at that block, using the stored block hash. Second, they can challenge any element of the sum. Since the challenger has access to the calldata, they can construct a Merkle proof for every leaf included in the tree.They can also use historical state proofs to prove the correct value for that index (using the link between index and address, the balance of that address and other relevant on-chain data like the commission of that minipool). This implementation could again be limited by what we can do within the constraints of the block gas limit. Rocket Pool already has over 13,000 minipools and that number will only go up with LEB8s and potentially even lower collateral requirements in the future. It may not be viable to provide that amount of calldata and calculate a root for it on-chain.
Interactive Version
This version provides better scalability, at the cost of requiring one extra round. As before, the attester provides the block number for which balances are calculated. In this version, they also commit to the number of minipools they are submitting balances for. Instead of submitting every balance, they provide hash values and partial sums for all nodes at some pre-defined level of the tree:
The smart contract again stores the block hash and again calculates the root of a Merkle Sum Tree given the data. A challenger again has two options: Prove that the number of minipools is invalid as before or pick a hash value and partial sum pair that is incorrect. In the latter case, the challenger basically begins the non-interactive version dicussed above, but with reversed roles: The challenger provides calldata of balances for the partial tree and the smart contract derives the hash and partial sum, which must be different from what the attester submitted. Now the attester is granted a challenge period to prove that the challenger submitted bad data. If the attester fails to do so, his proposal is rejected.
Incentives
The attester has to put up collateral that is locked during the challenge period. If the submission is successful, the collateral is returned and they receive a reward. A challenger is also required to provide collateral. The winner of a challenge receives the collateral of both parties. In the interactive version, the gas cost of the attestation step and the challenge step can be tuned based on which level of the tree the attester submits. Since the reward for the attester needs to cover this gas cost, it might make sense to minimize gas for attestation, while ensuring that the challenge can be executed within the block gas limit. This would make the challenge process expensive, but we can ensure profitability by choosing high enough collateral values.
Other Applications
Beacon Chain Balances
Once the beacon root is available on the execution layer, the same design could be applied to aggregate beacon chain balances for the rETH update. State proofs would use the beacon root instead of a block hash.
Snapshot RPL Rewards
A big challenge with the current RPL rewards system is that rewards for each node depend on the total effective RPL staked, since rewards for a node are relative to that total. For every RPL price it is necessary to recalculate and sum effective RPL staked for each node. This kind of loop is again problematic because of gas and could also be solved through verifiable off-chain calculation.
Last updated
