Herodotus: Proving Ethereum’s State Using Storage Proofs on Starknet
TL;DR:
- StarkWare and Herodotus have created a way to prove Ethereum blocks all the way back to genesis
- This is accomplished using the power of cryptographic proofs and block hashes
- It achieves the goals of EIP-2935 — a way to access historical block hashes older than 256 blocks in a chain-native way, and unlocks new use cases for Defi and more
- This technology is being brought to Ethereum as a public good by Herodotus and StarkWare
Introduction
Being able to access historical state on Ethereum in a provable way is important — but until now all you could access in a trustless manner was the history of the past hour.
But Starknet is a vibrant, innovative ecosystem that pushes the edge of what’s possible. And now, thanks to Herodotus and StarkWare, you can retrieve — in a chain-native and provable way — all Ethereum block hashes all the way back to the genesis block.
Let’s look in detail at how Herodotus and StarkWare achieved this and what it all means. We’ll start with a background on storage proofs.
What are Storage Proofs?
Storage proofs allow us to prove that a certain state existed at some point in the past, and without having to trust any third party. With storage proofs, trust is built into the mathematics. Storage proofs can also be used to access this state across different chains.
In a recent article on storage proofs, we introduced Herodotus, the team leading the research and innovation of storage proofs. The Herodotus team has now created a way to make storage proofs even better by providing trustless proving of Ethereum all the way back to the genesis block.
Let’s look at how Herodotus achieved this and why it’s important.
Proving Ethereum’s Genesis Block On-Chain
First, we need to understand how Ethereum block headers and block hashes work.
So, What is a Block Header and a Block Hash?
A block header is the section of a block that summarizes all the information kept in that block. It includes the hash of the parent block, the block timestamp, the state root, and more.
Ethereum block header and state merkle tree (source)
There is a lot of information kept inside the block header. For this article, we’re particularly interested in the state root. Let’s look at why.
In the diagram above you can see, just below the block header, the Ethereum Account State. Every Ethereum account has an associated storage space where that account’s variables are stored (essentially, the smart contract’s state). A cryptographic commitment of the account’s storage is hashed and stored as a storage root along with the account balance, nonce, and code hash. Together, this all acts as a basic summary of this account’s state.
A Merkle Patricia Trie of all the Ethereum account states is constructed, and its hash is stored in the block header as the state root (labeled stateRoot in the diagram above). This state root contains all the information you need to prove the state of the entire Ethereum network at any particular point in time.
Finally, since every block on Ethereum (and EVM chains) contains this state root, and since every block also has an associated string called the block hash (which is the result of hashing everything inside the block header including the state root), the block hash acts as a cryptographic commitment of the entire Ethereum state at a particular time.
Historical Block Hashes on EVM
Since so much key information is kept in the block hashes, we often need to access them historically.
In Solidity, if we want to retrieve the block hash of the block that was mined two blocks ago (the backward count starts from the block in which a transaction is included), we use the following syntax:
bytes32 lastBlockHash = blockhash(block.number - 2);Pretty simple. But there’s a catch — this block-hash method can only retrieve the block hash for the last 256 blocks. With an average of 12-second blocks on Ethereum, that’s 51.2 minutes of history on-chain.
For someone who wishes to use historical block hashes as a source of entropy (randomness), the 256 limit is generally good enough. However, if you want to use block hashes for fetching the historical state of the chain at a specific block, a 51-minute history is not nearly enough (compared to an eight-year history of the Ethereum blockchain).
This 256 limit of on-chain block hash retrieval was primarily a design choice made for state storage efficiency and to mitigate potential state growth problems.
Herodotus Gives Access to the Complete History of Block Hashes
So, how does Herodotus solve this limitation and allow us to:
- access the complete history of block hashes on Ethereum
- prove Ethereum’s state all the way back to the genesis block
- and all in a trustless manner?
The key is the power of cryptographic proofs.
Let’s delve deeper by dividing the Herodotus Historical Block Hash Accumulator procedure into steps:
Step 1. Registering a recent block hash
On the Ethereum mainnet, a recent block hash is registered in a smart contract named the SharpFactsAggregator smart contract. The block hash can be retrieved using the block hash opcode (opcode value 0x40) and saved in the aforementioned smart contract as a simple string variable. The corresponding block number can also be registered for access later on.
Let’s assume that the registered block number is block 18,000,000. From Etherscan, we can see that the block hash of this block is 0x95b1…4baf3.
Step 2. Proving the block hash of the latest block
The next step is to retrieve the block header (from an archival node) for block 18,000,000, compute its block hash in an off-chain computation, and compare it to the registered block hash 0x95b1…4baf3. This calculation is also run through a prover to create a proof of this computation.
The block hash for this block is added to a Merkle Mountain Range (MMR). This is a variation of a Merkle tree such that appending new elements to the tree does not require significant computation.
Step 3. Proving the block hash of block X-1
Once we have proven that the block header retrieved from the archival node is valid, we retrieve the block header for block X-1, compute its block hash, and compare it with the parentHash value for block X. (It is available in the X’s block header that we retrieved earlier).
If the hashes match, we know that the block header for X-1 is also valid. Since this whole computation can be modeled as a function, a STARK proof of this computation can be created simultaneously. Hence, a proof of validity for the block header of block X-1 is created (see diagram below).
Step 4. Recursively proving the block hashes for previous blocks
The block hashes are computed similarly for all the previous blocks until we reach all the way back to the Genesis block — the first block on the Ethereum mainnet. These are all appended to the MMR tree, thus creating a final MMR root.
It should be noted that all of these computations are done off-chain with a simultaneous generation of proof of computation by Herodotus.
Step 5. Publishing of proof on-chain and subsequent use
Once the final MMR root is generated, this root can be published on-chain (on a Proofs Aggregation smart contract) along with the proof of computation for the millions of blocks. Since the generated STARK proofs are exponentially cheaper to verify, the cost of verifying these proofs on-chain is reasonable.
And there we have it! We’ve created a way to access Ethereum’s state all the way back to the genesis block.
These MMRs (called “historical block hash accumulators” by the Herodotus team) achieve the goals of EIP-2935 proposed by Vitalik Buterin and Tomasz Stanczak in 2020 — a way to access historical block hashes older than 256 blocks. This was a problem that had remained unsolved for over three years! And yet, Herodotus and Starknet achieved it without having to make any protocol-level changes.
Some key points to note on the process above:
- Herodotus processes the blocks in batches of ~1350 blocks, and the proof is published on-chain for every single batch. Once the whole process is completed for the first 18,000,000 blocks on Ethereum, the MMR root for the history of the block can be updated periodically as new blocks are added to the chain’s history.
- Once the MMR root is available on-chain, it becomes possible to prove the inclusion of every single block hash in the MMR (that’s a basic property of Merkle trees).
- Before sending the proof onto the Ethereum mainnet, the Herodotus team’s prover uses SHARP, created by the StarkWare team. The primary benefit of the SHARP system is its ability to decrease costs and enhance the efficiency of the generated proofs.
- The workflow described above is being duplicated for two independent MMRs — one that uses the Keccak256 hashing function and one that uses the Poseidon. On Ethereum, the Keccak256 variant will be used, while Starknet will use the Poseidon variant.
- The MMR root for the Ethereum mainnet is also sent to Starknet using the native Starknet L1-to-L2 messaging protocol for use on Starknet. The Herodotus Block Hash Accumulator also enables Ethereum historical data access on Starknet. The Starknet L1-to-L2 messaging system can be used to relay an L1 block hash and the verified MMR root to Starknet in a secure manner. Once on Starknet, storage proofs of historical Ethereum data can be verified against these commitments.
New Opportunities with the Herodotus Block Hash Accumulators
These block hash accumulators are being brought to Ethereum by Herodotus and StarkWare as a public good. Once the final MMR roots are published on Ethereum mainnet, along with proofs of computation, any developer can utilize them for accessing a provable state of the chain for any time since inception.
Since the MMR roots for Ethereum are also going to be sent to Starknet via the native messaging protocol cross-chain, cross-chain state information can be accessed in a simple yet trustless manner. DeFi protocols could benefit from historical state proofs by utilizing the information about a specific account balance or leveraged positions of an account at any point in time. More robust random number generation using a larger history of block hashes becomes possible. Cross-chain voting becomes simplified without users having to bridge assets before they cast their votes on an L2. And much more.
Conclusion
In the evolving world of blockchain scalability, decentralization, and verifiability, teams on Starknet are emerging as beacons of innovation. Projects created in Starknet are becoming key elements in scaling Ethereum. As we delve into this new future, familiarizing yourself with the ecosystem will position you for what lies ahead.
Read more about projects in the Starknet ecosystem here.
