Research and developments along verkle and The Verge

Content of the blog

I worked on verkle trie and state trie migration from MPTs to Verkle in reth execution client as part of my ethereum protocol fellowship cohort 5 from May 2024 to Nov 2024, will go through the depth of that work in this blog post along with explainations of related tech.

The Verge

Before explaining the verkle structure and my work, let's understand The Verge(the hardfork which will incorporate verkle and stateless validation of the ethereum L1).
The Verge is focused on enabling stateless validation of ethereum L1 by moving state storage to verkle trie, and the stateless validation is done by incorporating each block with a witness, which includes:
(i) the values (eg. code, balances, storage) at the specific locations in the state that the block will access
(ii) a cryptographic proof that those values are correct.
and then the execution of the new block is conducted using this witness instead of the local state storage, along with stateless validation.
The Verge will be beneficial in also adding these important aspects to L1 ecosystem:

• Cheaper light clients via smaller storage proofs.
• Stateless execution via inclusion of read pre-states in a block’s header, which may also result in performance improvements due to static state access.
• Raising the contract size limit by chunking bytecode and enabling partial code loading.
• State expiry becomes more palatable as the cost to “revive” state is lower.
  The Verge also focuses on a more long-term and ambitious goal of ultimately verifying all L1 execution using SNARKs.

My work as part of fellowship

My work focused mainly on moving the state storage model of reth EL engine to Verkle Trie from the current MPTs structure, modifying the parts that uses MPTs for state commitment and state root calculations, implementing gas costs changes to REVM as suggested by EIP-4762, construction of witness during block execution, to pass all the execution-layer spec tests designed for EIP-4762 and EIP-6800 which will enable reth to join Kaustinen devnet-7(latest devnet for testing verkle migration) and ultimately add stateless validation feature using witness instead of local state storage. The other long term research was also conducted on designing sync for when the verge is activated and how the data will be migrated from MPTs to VPTs after/during the hardfork.(see associated work here: https://hackmd.io/@W3tic1bbRka1R7HA1o1D_A/By_MyNy3h and https://notes.ethereum.org/@parithosh/verkle-transition).

Why not MPTs

The core challenge lies in the architectural design of MPTs, which creates significant inefficiencies for validation processes. Two fundamental limitations make MPTs particularly problematic for this use case. First, their hexary structure—where each node maintains sixteen child nodes—results in substantially larger proof sizes compared to binary alternatives. In concrete terms, a proof in an MPT requires approximately 3,840 bytes for a tree with 232 items, whereas a binary tree would need only 1,024 bytes for the same data structure.
The second critical limitation stems from MPTs' non-Merkelized code implementation. When validating account code, this design necessitates the inclusion of complete contract code in proofs, potentially reaching up to 24,000 bytes per instance. While there is some minor efficiency gain from branch repetition, the resulting data requirements remain impractically large for processing within a single slot.
Merkle Patricia tree is extremely unfriendly to implementing any cryptographic proof scheme as well, attempts to address these limitations through STARK implementation face two obstacles. The KECCAK hash function used in MPTs proves particularly resistant to efficient STARK processing.
While transitioning to a binary tree structure and implementing Merkelized code would reduce the worst-case scenario to approximately 10.4 MB, this still exceeds practical limitations for many nodes operating within single-slot constraints.
Morever, stateless validation in EL clients can also be enabled using Merkle proofs of the branches in MPTs for witness construction but the proof sizes are too big to be propagated over the network, you can see an associated work on this cross validation technology by geth team here: cross-validation using execution witness, this is currently live on geth: https://github.com/ethereum/go-ethereum/pull/30069.

Why verkle

Verkle trees use elliptic curve-based vector commitments to make much shorter proofs. The key unlock is that the piece of the proof corresponding to each parent-child relationship is only 32 bytes, regardless of the width of the tree. The only limit to the width of the tree is that if the tree gets too wide, proofs become computationally inefficient. The implementation proposed for Ethereum has a width of 256, apart from shorter proofs, verkle tries also provides various advantages:

• Verkle trees allow witnesses (proofs) to be efficiently updated when the underlying state changes, that is, when state changes, you can update a witness by:
  • Only modifying the path from the changed leaf to root, not needing to read the entire bottom level, just updating commitments at each level, this provides some advantages:
    • Mempool:
      • Transaction has proof of account balance
      • New block arrives, changing state
      • Can quickly update proof without full recomputation
    • Inclusion Lists:
      • Validator has proof of transaction validity
      • State changes from previous block
      • Efficiently updates proof for new state root

However, there are some bottlenecks in further scaling with verkle:

• State root updates are slower than with hash-based trees, resulting in longer sync times for full nodes.
• Verkle proofs are harder to SNARK-prove due to their 256-bit operations, requiring either high overhead or custom proof system components for efficient verification.
• Verkle trees rely on elliptic curve cryptography for their vector commitments, making them vulnerable to quantum computers which can break elliptic curve security through for eg. Shor's algorithm.

In today's world verkle gives us 2.6 MB worst case proves, this can be further reduced down to few KBs if we're able to STARK prove verkle, hence research has been going on to explore verkle alternatives which are Quantum resistant, and more STARK proving friendly.(discussed in detail in next section)

Zk friendliness of verkle and potential altervatives

Along with ongoing work on reth's stateless architecture I conducted research on alternatives to verkle trie, and zk-friendliness of verkle as well, a little in depth research conducted by me can be read here: exploring zk friendliness of verkle, since verkle is not quantum resistent, and not much Zk-frienliness of verkle is explored yet, a concept of STARKed binary hash trees is considered, if we assume a worst case scenario of 10.4 MB of witness size after using binary trie and merkelizing the code, then in STARKed binary hash tree we replace this 10.4 MB proof with a STARK of the proof. This gets us to the point where the proof itself consists of only the data being proven, plus ~100-300 kB fixed overhead from the actual STARK. The main challenge here is prover time. A 10.4 MB block means 330,000 hashes. If we add in the possibility of an attacker "mining" addresses with a long common prefix in the tree, the real worst case becomes around 660,000 hashes, hence we need to prove ~200,000 hashes per second, to achive this speed following main category of hash functions are considered:

• STARK-friendly hash functions like Poseidon and Ajtai
• conservative hash functions like SHA256 and BLAKE

STARK-friendly hashes (like Poseidon) achieve impressive performance with ~200,000 hashes/second on consumer laptops, easily meeting the worst-case requirement of 660,000 hashes per slot. The main hurdle is security validation - while specifically designed for STARK efficiency, these newer hash functions need extensive cryptanalysis before they can be trusted for L1 deployment.

Conservative hash functions (like SHA256 and BLAKE) currently perform much slower, managing only 10-30k hashes/second with existing STARK provers on consumer hardware. However, rapid advancements in STARK technology, particularly GKR-based approaches, show promise in boosting these rates to the necessary 100-200k range, potentially making these battle-tested hash functions viable without compromising security.