Herodotus How to use Starknet rollup to prove Ethereum state?

Original: Herodotus: Proving Ethereum’s State Using Storage Proofs on Starknet

Translation and Proofreading: “Starknet Chinese Community”

Summary

• StarkWare and Herodotus have collaborated to develop a proof-of-history method to trace all blocks on Ethereum from its inception.
• This is achieved through the use of cryptographic proofs and block hashes.
• It achieves the goals of EIP-2935—accessing historical block hashes of more than 256 blocks in a chain-native way, unlocking new possibilities for use cases such as DeFi.
• Herodotus and StarkWare bring this technology as a public good to Ethereum.

Introduction

Accessing historical states in a provable manner on Ethereum is extremely important. However, until now, the historical records that we were able to access trustlessly were limited to the past hour.

However, Starknet is a vibrant ecosystem that consistently pushes the boundaries of what is possible. Thanks to Herodotus and StarkWare, we can now trace and retrieve all Ethereum block hashes since the genesis block in a chain-native and provable manner.

• Drive to earn？In-depth analysis of DePIN’s business model in Dimo’s race track project.
• Exclusive Interview with Hack VC Managing Partner Alexander LianGuaick The Hacker of Investors, The Technology Expert of Investments
• The Battle of the East for the Location of Transnational Cryptocurrency Companies (Part 2) Is Hong Kong More Suitable for Mining?

Let’s delve into how Herodotus and StarkWare have achieved this goal and what it all means. We’ll start by discussing the background knowledge of storage proofs.

What Are Storage Proofs?

Storage proofs allow us to prove that a certain state existed at a specific point in the past without relying on any trusted third party. Through storage proofs, trust is built into mathematics. Storage proofs can also be used for cross-chain access to these states.

In a recent article about storage proofs, we introduced the team leading storage proof research and innovation—Herodotus. Currently, the Herodotus team has implemented a new technology that can provably verify Ethereum states without trust since the genesis block, greatly improving storage proof performance.

Let’s explore how Herodotus achieves this and its importance.

Proving the Genesis Block of Ethereum On-chain

First, we need to understand how Ethereum block headers and block hashes work.

What Are Block Headers and Block Hashes?

A block header is a part of a block that summarizes all the information contained in that block, including the hash of the parent block, the timestamp, the state root, and more.

Ethereum Block Header and State Merkle Tree (source)

The block header contains a lot of information. In this article, we will focus on the state root. Let’s take a closer look at the reason.

By looking at the above image, we can see that below the block header is the Ethereum account state. Each Ethereum account has an associated storage space, which is used to store variables for that account (essentially the state of the smart contract). The encrypted commitment of the account storage, along with the account balance, random number, and code hash, is stored as the storage root. Together, these basically constitute a summary of the account state.

A Merkle Patricia tree, which contains the state of all Ethereum accounts, is built, and its hash value is stored as the state root in the block header (marked as stateRoot in the above image). This state root contains all the information required to prove the entire Ethereum network state at any specific point in time.

Finally, since every block on Ethereum (and EVM chains) contains this state root, and each block also has an associated string called the block hash (which is the result of hashing all the contents within the block header, including the state root), the block hash is the encrypted commitment of the entire Ethereum state at a specific point in time.

Historical Block Hash Values on EVM

Considering that block hash values contain a lot of crucial information, we often need access to their historical records.

In Solidity, if we want to retrieve the block hash values of two blocks mined before (counted backwards from the block that includes the transactions), we can use the following syntax:

“`solidity
blockhash(block.number – count)
“`

The method is very simple. But there is one catch – this block hash method can only retrieve the hash values of the most recent 256 blocks. Considering Ethereum’s average block time of 12 seconds, this corresponds to a historical record on the chain of 51.2 minutes.

For those who want to use historical block hash values as a source of entropy (randomness), the limitation of 256 blocks is usually sufficient. However, in terms of Ethereum’s eight-year history, if you want to use block hash values to obtain the historical state at a specific block, 51 minutes of historical record is far from enough.

This limitation of retrieving 256 block hash values on-chain is primarily for improving state storage efficiency and reducing potential state growth issues.

Herodotus Enables Access to Complete Historical Block Hash Value Records

How does Herodotus overcome this limitation and make it possible for us to:

– Access the complete historical record of Ethereum block hash values
– Prove the entire Ethereum state since the genesis block
– And do it all in a trustless manner

The key lies in the power of cryptographic proofs.

Let’s delve into the program steps of the Herodotus historical block hash value accumulator:

Step 1: Register a Recent Block Hash Value

On the Ethereum mainnet, a recently mined block hash will be registered in a smart contract called SharpFactsAggregator. The block hash can be retrieved using the block hash opcode (opcode value 0x40) and stored as a simple string variable in the aforementioned smart contract. The corresponding block number can also be registered for future access.

Assuming the registered block number is 18,000,000, we can see through Etherscan that the hash value of this block is 0x95b1…4baf3.

Step Two: Proving the Hash Value of the Latest Block

The next step is to retrieve the block header information of block 18,000,000 from an archival node, calculate its block hash value off-chain, and compare it with the registered block hash value 0x95b1…4baf3. This calculation process will also create a proof using a prover.

The hash value of this block is added to the Merkle Mountain Range. This is a variant of the Merkle tree that allows for adding new elements without extensive computation.

Step Three: Proving the Hash Value of Block X-1

Once we have proven the validity of the block header retrieved from the archival node, we then get the block header of block X-1, calculate its hash value, and compare it with the parent hash value of block X (which can be found in the block header of block X we retrieved earlier).

If the hash values match, we can confirm the validity of the block header of block X-1 as well. As the entire computation can be modeled as a function, a STARK proof for this computation can be created simultaneously. This results in a proof of validity for the block header of X-1 (see the image below).

Step Four: Recursively Proving the Hash Values of Previous Blocks

Perform similar computational processing for the block hash values of all previous blocks until tracing back to the genesis block of the Ethereum mainnet. These hash values will be appended to the MMR tree, creating a final MMR root.

It is important to note that these computations are done off-chain, and Herodotus simultaneously generates computational proofs.

Step Five: Publishing the Proof on-chain and Its Subsequent Uses

Once the final MMR root is generated, it can be published on-chain along with the computational proofs for millions of blocks (on a proof aggregator smart contract). Due to the extremely low verification cost of the generated STARK proofs, the cost of on-chain verification of these proofs becomes reasonable.

We have implemented a method to trace and access all states from the Ethereum genesis block.

The Herodotus team refers to these MMRs as “Historical Block Hash Accumulators,” achieving the goal proposed by Vitalik Buterin and Tomasz Stanczak in EIP-2935 in 2020, which aims to access historical data from more than 256 blocks. This has been a pending issue for over three years! However, Herodotus and Starknet have achieved this goal without any protocol-level changes.

Some key points about the process:

• Herodotus processes batches of approximately 1350 blocks, and the proofs for each batch are published on the chain. Once the entire processing flow for the first 18 million Ethereum blocks is completed, the MMR root of the block history can be regularly updated as new blocks are added to the chain.

Once the MMR root is found on the chain, it can be used to prove that the MMR contains the hash value of each block (which is a fundamental property of a Merkle tree).

Before sending the proof to the Ethereum mainnet, the proofers from the Herodotus team use the SHARP system created by the StarkWare team. The main advantage of the SHARP system is that it can reduce costs and improve the efficiency of proof generation.

This workflow is being replicated in two independent MMRs, one using the Keccak256 hash function and the other using Poseidon. Ethereum will use the Keccak256 variant, while Starknet will use the Poseidon variant.

The MMR root of the Ethereum mainnet is sent to Starknet via the native Starknet L1-to-L2 message passing protocol for use on Starknet. The Herodotus Block Hash Accumulator also enables access to Ethereum’s historical data on Starknet. The message system from L1 to L2 in Starknet can be used to securely forward L1 block hashes and verified MMR roots to Starknet. Once on Starknet, these commitments can be used to verify storage proofs of Ethereum’s historical data.

New Opportunities with Herodotus Block Hash Accumulator

Herodotus and StarkWare bring the Block Hash Accumulator as a public good to Ethereum. Once the final MMR root and computational proofs are published on the Ethereum mainnet, any developer can utilize them to access provable states from any point in the chain’s history.

Since Ethereum’s MMR root is also sent to Starknet via the native cross-chain message protocol, cross-chain state information can be accessed in a simple and trustless manner. DeFi protocols can benefit from historical state proofs by leveraging information such as the balance of an account or leveraged positions at specific points in time. Generating more robust random numbers using records from larger historical block hashes becomes possible. Cross-chain voting becomes simpler, and users no longer need to transfer assets across chains before voting on L2. Additionally, it opens up various other possibilities.

Conclusion

In the world of blockchain, where scalability, decentralization, and verifiability are constantly developing, the Starknet team is becoming a beacon of innovation. Projects created on Starknet are becoming crucial elements in scaling Ethereum. As we delve into this new future, familiarizing yourself with the Starknet ecosystem will lay the foundation for your future growth.

We will continue to update Blocking; if you have any questions or suggestions, please contact us!