Verkle TreesThe path to stateless clients

Ethereum is currently grappling with the challenge of its ever-expanding blockchain size. 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.

The state's growth is permanent and relatively inexpensive, presenting another issue. Even if the cost of increasing the state is raised, there is no way to make someone pay for the actual impact on the network, which is eternal.

Weak statelessness removes the need to store the entire state for verifying new blocks, enabling fully stateless block validation on Ethereum. This approach also allows validation on lightweight machines like Raspberry Pi (without SSD) and mobile phones. Moreover, the Ethereum Virtual Machine (EVM) would benefit from fraud proofs, such as fraud-proof protected light clients and EVM as a shard.

Verkle Trees can be used as the state commitment scheme to achieve weak statelessness. They generate small, efficient-to-verify witnesses and gas cost changes can be made to ensure that state access costs reflect the cost of witnesses.

Implementing state expiry can help keep the active state under control, which remains relevant for block builders.

Verkle Trees have a tree-like structure similar to Merkle Trees, but with a more efficient vector commitment scheme. Instead of hashing the d nodes, each node commits to the d nodes themselves using a vector commitment scheme.

Another Merkle Tree inefficiency is that each proof has to include all the siblings for each node on the path to the leaf. For example, d-arry Merkle Trees need (d-1)logdn for a single proof. The hash function is a poor vector commitment because a proof requires all siblings to be given thus inflating the witness size.

For Ethereum, the Inner Product Arguments on Pedersen Commitments is used as the vector commitment scheme.

The verkle tree structure makes for shallower trees, reducing the amount of stored data. The real power of Verkle Trees lies in their ability to produce smaller proofs, or witnesses, needed for block validation. These smaller proofs propagate more quickly through the network, enabling stateless clients - nodes that don't store state - to verify blocks with significantly reduced resource consumption. These proofs can be further compressed using the multi-proof scheme, as outlined in a research paper by Dankrad Feist, researcher at the Ethereum Foundation.

While not yet formalized in an EIP, the proposal is widely accepted in the Ethereum community. The roadmap outlines a transition phase, during which the final switch from Merkle to Verkle tree will occur. The community is currently deliberating several potential transition processes, with proposed schemes available for review.

Verkle Tree proposal Proposed transition schemes