Guide to Verkle Trees in Ethereum

Paving the Way for Stateless Ethereum Clients

Ethereum, one of the leading blockchain platforms, relies on cryptographic data structures to ensure data integrity and security. Currently, Ethereum utilises Merkle trees for its state and transaction management. However, as the network grows, Merkle trees face scalability and efficiency challenges. 

This is where Verkle trees come into play. In this blog post, we'll delve into the current use of Merkle trees in Ethereum, the issues associated with them, and how Verkle trees aim to address these problems. We'll also explore the technical aspects of Verkle trees and discuss related Ethereum Improvement Proposals (EIPs) and their implications for the future of Ethereum.

The Current State: Merkle Trees in Ethereum

What Are Merkle Trees?

Merkle trees are cryptographic data structures that allow efficient and secure verification of large data sets. A Merkle tree consists of leaves (transactions) and nodes (hashes of these transactions). The tree is constructed by hashing pairs of nodes repeatedly until a single root hash, known as the Merkle root, is obtained. This root hash provides a unique fingerprint of the entire data set.

Source: https://static.javatpoint.com/tutorial/blockchain/images/blockchain-merkle-tree.png

Use of Merkle Trees in Ethereum

In Ethereum, Merkle trees are used in several key areas:

• State Trie: A modified Merkle Patricia Trie that stores the entire state of the Ethereum network, including account balances, contract storage, and more.
• Transaction Trie: Used to organize and verify transactions within a block.
• Receipts Trie: Stores transaction receipts, which include details like the outcome of transactions and logs generated by smart contracts.
  
  

Source: https://static.javatpoint.com/tutorial/blockchain/images/blockchain-merkle-tree2.png

Issues with Merkle Trees

While Merkle trees provide several advantages, they also come with significant drawbacks:

• Storage Inefficiency: The modified Merkle Patricia Trie used in Ethereum requires substantial storage space, leading to large state sizes.
• Slow Proof Generation: Generating proofs for state and transaction verification can be slow and computationally expensive.
• Scalability Concerns: As the Ethereum network grows, the inefficiencies in Merkle trees become more pronounced, hindering the network's scalability.

Enter Verkle Trees

Why do we need a stateless Ethereum?

Ethereum is currently grappling with the challenge of its ever-expanding blockchain size. 

Today, to validate the chain, you need to have a fully synced node containing the entire state. This is necessary because, currently, blocks don’t contain all the required state to execute them due to the cost of generating a witness with the current Merkle Patricia Trie. 

Clients need to store around 50 GB for the state alone and over 150 GB, including all Merkle proofs, which are increasing by roughly half that amount per year. As the state database increases in size, downloading, storing, and synchronizing data takes longer. Moreover, the costs of storing and accessing data on the blockchain can become prohibitively expensive, especially for smaller nodes and users wishing to participate in the network.

Stateless Ethereum provides these advantages - 

Reduced amount of data required to participate in the network

• No more never-ending network synchronizations
• Sustainable storage requirements

Reduced amount of data required to process

• Easier for smaller devices

Faster access to information

• Blocks contain all the information needed to process it
• Knowing the state of one’s account is faster

What Are Verkle Trees?

Verkle trees are a type of vector commitment tree, a cryptographic data structure that enables compact and efficient proofs of membership (or non-membership) for elements in a set. They are designed to address the shortcomings of Merkle trees, particularly in the context of blockchain applications where state size and verification efficiency are critical.

Key Characteristics of Verkle Trees:

1. Compact Proofs: Verkle trees generate smaller proofs compared to Merkle trees, which reduces the amount of data that needs to be transmitted and verified.
2. Efficient Verification: The verification process in Verkle trees is faster, making them more suitable for applications that require frequent state updates and checks.
3. Scalability: By reducing the size of proofs and improving verification efficiency, Verkle trees contribute to the overall scalability of the blockchain.

Solution to Statelessness

Verkle trees are a critical step on the path to stateless Ethereum clients. Stateless clients do not have to store the entire state database in order to validate incoming blocks. Instead of using their own local copy of Ethereum's state to verify blocks, stateless clients use a "witness" to the state data that arrives with the block. A witness is a collection of individual pieces of the state data that are required to execute a particular set of transactions and  cryptographic proof that the witness is really part of the full data. The witness is used instead of the state database. 

For this to work, the witnesses need to be very small, so that they can be safely broadcast across the network in time for validators to process them within a 12-second slot. The current state data structure is not suitable because witnesses are too large. Verkle trees solve this problem by enabling small witnesses, removing one of the main barriers to stateless clients.

With Verkle Trees EIP, blocks can be self-contained execution units that allow them to be verified without requiring any extra information, in particular, the full state of the chain.

Tree Structure: Merkle Patricia vs. Verkle Trees

The architecture of Verkle trees bears a resemblance to Ethereum’s current Merkle Patricia trees. Each node within a tree can be:

1. Empty
2. A leaf node containing a unique key and corresponding value
3. An intermediate node with a predetermined number of child nodes (denoted as the “width” of the tree).

The value of an intermediate node is derived from the hashed values of its child nodes. The position of a value within the tree is dictated by its key.

Source: https://ethereum.org/content/roadmap/verkle-trees/verkle.png

The primary distinction between Verkle trees and Merkle Patricia trees lies in their width. While Patricia trees achieve optimal efficiency at a width of 2, Verkle trees yield shorter proofs with increasing width. However, exceedingly high widths can hinder the speed of proof creation. Proposed Verkle trees for Ethereum possess a width of 256, but there’s a growing inclination to amplify this to 1024.

Commitments and Proofs

In Merkle trees, proof of a value necessitates the inclusion of all sister nodes. The reason is, that to compute a node’s value, the entire set of its sibling nodes is required. This continues recursively up to the root node. Verkle trees, however, circumvent the need for sister nodes by just supplying the path, augmented with minimal proof.

A pivotal distinction in Verkle trees is the use of polynomial commitments instead of standard hashes for node computations, which allow hashing of a polynomial and subsequent proof generation for any evaluation of the hashed polynomial.

A polynomial commitment is a cryptographic primitive that allows a prover to commit to a polynomial while enabling the verifier to later check that a claimed value is indeed a point on that polynomial, without revealing the polynomial itself.

How It Works

1. Commitment Phase: The prover computes a commitment to a polynomial P(x). This commitment is a compact representation of the polynomial.
2. Evaluation Phase: The prover can later provide a proof that the polynomial evaluates to a specific value at a given point  X0. This proof must convince the verifier without revealing  P(x).

Example -

Node Structure: Each node in the Verkle tree is committed using polynomial commitments, allowing for efficient proof creation.

Tree Width: Consider a Verkle tree with a width of 256 (each node can have up to 256 children).

Let’s say you need to prove the existence of a value V located at a specific position P in the tree.

In a traditional Merkle tree, you would need:

• V
• All sibling nodes along the path from V to the root (a lot of data).

In a Verkle tree, the proof includes:

• The specific value V: This is the actual data you are proving.
• Commitments for each level: These are the polynomial commitments at each level from the leaf node (where V is located) to the root.

Detailed Illustration

1. Leaf Node: Contains the value V and its key K.
2. Intermediate Nodes: Instead of sibling nodes, each intermediate node has a polynomial commitment that represents its children.
3. Proof Composition: To prove V, you only provide the path: V, and the polynomial commitments from each intermediate node up to the root.

This significantly reduces the data needed because polynomial commitments are smaller than the combined size of all sibling nodes.

Read More on Verkle Tree Structure.

This visual comparison highlights the differences in proof sizes and data requirements between Merkle and Verkle trees, illustrating the size advantages of Verkle proofs.

Source: https://www.nethermind.io/verkle-trees

Source: https://miro.medium.com/v2/resize:fit:1400/format:webp/1*OHvXZg8eCmzkjELmcqLx1w.png

Ethereum Improvement Proposals (EIPs) Related to Verkle Trees

Several EIPs have been proposed to integrate Verkle trees into Ethereum, including:

EIPs:

• EIP-6800: Ethereum state using a unified verkle tree (draft)
• EIP-4762: Statelessness gas cost change (draft)
• EIP-7545: Verkle proof verification precompile (draft)
• EIP-2935: Save historical block hashes in state (draft)

Spec PRs:

• The Verge consensus spec (draft PR)

Transition:

• Migration Strategies

Archive and other related docs:

• Verkle serialization format in SSZ
• Vitalik’s draft EIP (old)

Current progress

Verkle tree testnets are already up and running, but there are still substantial outstanding updates to clients that are required to support Verkle trees. You can help accelerate progress by deploying contracts to the testnets or running testnet clients.

Explore the Verkle Gen Devnet 2 testnet

• Updated EIP-4762 implementations
• Updated EIP-2935 with a ring buffer of size 8192

See the followingtutorialto know how to join the testnet.

Future of Verkle Trees in Ethereum

Bringing Verkle into Ethereum involves many changes in the protocol:

• A new data structure to save the state of the network
• A new gas accounting model
• A strategy to migrate the existing state from the MPT to the VKT
• A new set of cryptography primitives
• New fields at the block level

Verkle trees represent a significant advancement in the cryptographic data structures used by Ethereum. By addressing the limitations of Merkle trees, Verkle trees offer a promising solution to the scalability and efficiency challenges faced by the network. As the Ethereum community continues to explore and implement Verkle trees, the future of Ethereum looks brighter, with the potential for a more scalable, efficient, and user-friendly blockchain platform.

Understanding and embracing these changes is crucial for developers, researchers, and users who are invested in the future of Ethereum. The transition to Verkle trees marks an important step in the evolution of blockchain technology, ensuring that Ethereum remains at the forefront of innovation and development in the decentralised space.

References

1. Verkle Trees | Ethereum.org
2. Verkle Trees for Statelessness
3. Verkle Trees: Everything You Need to Know
4. Vitalik Buterin on Verkle Trees
5. Guillaume Ballet and Dankrad Feist on Verkle Trees
6. https://www.nethermind.io/verkle-trees