Verkle Trees: Everything You Need To Know

And how it plays in Vitalik’s Ethereum End Game

Photo by Marita Kavelashvili on Unsplash

Introduction

As Ethereum continues to scale and evolve, Verkle trees emerge as a vital component. Like Merkle trees, Verkle trees facilitate the storage of vast data, allowing the generation of succinct proofs for any subset of that data. The distinguishing feature of Verkle trees is their ability to produce significantly smaller proof sizes. For instance, a traditional binary Merkle tree proof for a billion data pieces would be approximately 1 kilobyte. In contrast, a Verkle tree proof for the same data would be under 150 bytes. This drastic reduction in proof size paves the way for the practicality of stateless clients.

Figure 1: A comparison of proof sizes between traditional Merkle trees and Verkle trees.

Origins and Significance

The concept of Verkle trees was first presented by John Kuszmaul in a 2018 paper. Although relatively new, their potential impact on cryptographic constructs is undeniable. This article delves into the essence of Verkle trees and the cryptographic nuances underpinning them. While Verkle trees rely on more intricate cryptography, their complexity is arguably less daunting than some advanced cryptographic elements in modern ZK SNARK systems.

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.

Figure 2: An illustration of a hexary Verkle tree containing six (key, value) pairs.

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 being, 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 vector commitments instead of standard hashes for node computations. Vector commitments enable the creation of short proofs affirming that a value is part of a committed list. In practice, even more potent than vector commitments are polynomial commitments, which allow hashing of a polynomial and subsequent proof generation for any evaluation of the hashed polynomial.

Figure 3: A depiction of a Verkle tree proof, emphasizing the absence of sister nodes and the inclusion of concise proofs connecting each commitment.

Merging the Proofs

Verkle trees exploit the properties of polynomial commitments to generate a single, constant-sized proof, capable of substantiating all parent-child links for infinite keys. This is accomplished via a scheme that implements multiproofs through random evaluation.

The specifics of this proof generation, while intricate, can be elucidated further in detailed technical articles. The chief computational burden in proof generation involves formulating a polynomial of a certain form, with the remainder of the proofing process involving polynomial commitment validation.

Key Characteristics and Implications

Proofs using this architecture possess several notable properties:

1. Proof sizes remain consistent regardless of the number of evaluations.
2. Values can be inferred from other elements in the Verkle proof.
3. Only the leaves (keys and values) being proven and the commitments along their path to the root are necessary.

Given a width-256 tree and nn nodes, a proof would typically require the keys and values being validated, complemented by an average of three commitments for every value spanning from that value to the root.