Understanding Verkle Trees in Ethereum

·

Verkle Trees represent a pivotal advancement in the evolution of Ethereum’s scalability and efficiency, especially as part of the broader ETH2.0 (now Ethereum consensus layer) upgrades. Compared to traditional Merkle Trees, Verkle Trees dramatically reduce proof sizes—critical for improving network performance and enabling stateless clients. For a dataset of one billion entries, while a Merkle proof may require up to 1 kilobyte, a Verkle proof needs no more than 150 bytes. This leap in efficiency makes Verkle Trees a cornerstone of Ethereum's future infrastructure.

This article dives into the mechanics, benefits, and cryptographic foundations of Verkle Trees, exploring how they outperform Merkle Trees and enable scalable blockchain architectures.

What Are Merkle Trees?

Before understanding Verkle Trees, it’s essential to grasp the basics of Merkle Trees, a foundational data structure in blockchain technology.

A Merkle Tree is an accumulator that allows efficient and secure verification of whether a specific element exists within a large dataset. Each leaf node contains a hash of a key-value pair (e.g., key: 06, value: 32), and internal nodes contain hashes of their children.

👉 Discover how next-gen blockchain structures are redefining scalability

To prove that (06: 32) exists in the tree, a prover must provide all sibling hashes along the path from leaf to root—marked in red in typical diagrams. The verifier then recomputes the root hash and compares it with the known valid root.

However, as the tree grows deeper and wider, the proof size increases logarithmically:

Additionally, each level requires hash computations, increasing verification workload. This becomes impractical at scale—prompting the need for more efficient alternatives like Verkle Trees.

Introducing Verkle Trees

Verkle Trees, introduced by John Kuszmaul in 2018, address the limitations of Merkle Trees by replacing cryptographic hashes with vector commitments, specifically leveraging polynomial commitments such as KZG.

The core idea? Reduce proof size without sacrificing security or decentralization.

In a k-ary Verkle Tree:

Each node stores:

  1. A value (e.g., hashed key-value pair)
  2. A proof π that this value is part of its parent’s commitment

For example:

This hierarchical structure enables compact proofs across multiple levels.

The Power of Polynomial Commitments

While vector commitments offer constant-size proofs (O(1)), their construction and update costs (O(n²) and O(n)) make them inefficient for large-scale use. Enter polynomial commitments, a more practical solution.

Polynomial commitments allow one to commit to a polynomial P(x) such that later, one can prove evaluations like P(z) = y without revealing the entire polynomial.

Two prominent schemes are:

These commitments are points on elliptic curves (e.g., BLS12-381), typically 32–48 bytes—ideal for lightweight verification.

KZG Single-Point Proofs

Given a polynomial P(x), its commitment is denoted [P(s)]₁, where s is a secret trusted setup parameter.

If P(z) = y, then (x − z) divides (P(x) − y). We define:

Q(x) = (P(x) − y) / (x − z)

The prover computes [Q(s)]₁ and sends it as proof.

The verifier checks:

e([Q(s)]₁, [s − z]₂) = e([P(s) − y]₁, [1]₂)

via bilinear pairing.

By the Schwartz-Zippel Lemma, the probability of a malicious prover forging this proof is negligible.

👉 See how advanced cryptography powers modern blockchains

Multi-Point KZG Proofs

To prove multiple values—say P(z₀)=y₀, ..., P(zₖ₋₁)=yₖ₋₁—we use interpolation.

Let:

Then:

V(x) divides (P(x) − I(x)) → exists Q(x) such that P(x) − I(x) = V(x)·Q(x)

Prover sends:

Verifier computes:

And checks:

e([P(s) − I(s)]₁, [1]₂) = e([Q(s)]₁, [V(s)]₂)

Crucially, proof size remains constant, regardless of the number of points—only two group elements (~96 bytes with BLS12-381).

Verkle Trees in Ethereum

Ethereum plans to adopt Verkle Trees to replace Merkle Patricia Trees for state storage, enabling stateless clients and reducing sync overhead.

Like Merkle Patricia Trees, nodes come in three types:

Each internal node has width 16 (hexadecimal indexing: 0–F). To prove a leaf (0101 0111 1010 1111 → 1213):

  1. Prove that hash of (key, value) is at index 1010 in Inner Node B
  2. Prove that commitment of Node B (cm_B) is at index 0111 in Inner Node A
  3. Prove that commitment of Node A (cm_A) is at index 0101 in Root

Each level uses a polynomial commitment fᵢ(x) representing the node's contents.

Compressing Multiple Proofs

Instead of verifying each level separately (costly due to multiple pairings), we compress proofs using random linear combinations.

Given polynomials f₀(x), ..., fₘ₋₁(x) and evaluation points z₀, ..., zₘ₋₁, we want to prove:

fᵢ(zᵢ) = yᵢ for all i

For each, there exists quotient polynomial qᵢ(x) such that:

fᵢ(x) − yᵢ = (x − zᵢ)·qᵢ(x)

Now generate random scalars r₀,...,rₘ₋₁, and combine quotients:

g(x) = Σ rᵢ·qᵢ(x)

Prover commits to g(x) → [g(s)]₁

Pick random t, define:

h(x) = Σ rᵢ·fᵢ(x)

Then:

h(t) − g(t) = Σ rᵢ·yᵢ

Compute quotient:

q(x) = (h(x) − g(x) − y) / (x − t)

Send [q(s)]₁ as final proof.

Verifier recomputes required terms and validates via pairing check.

This reduces multiple pairing operations into just one, significantly cutting verification cost.

Key Properties of Verkle Trees

  1. Constant-sized multi-proof support: Proof size doesn’t grow with the number of values proven.
  2. Implicit values: Values (yᵢ) are derived as hashes from lower layers—no need to transmit explicitly.
  3. Implicit indices: Key paths determine indices (zᵢ)—no extra data needed.
  4. Public data only: Only keys, values, and path commitments are required—fully transparent and verifiable.

These properties make Verkle Trees ideal for Ethereum’s vision of scalable, lightweight clients.

Frequently Asked Questions (FAQ)

Q: Why are Verkle Trees better than Merkle Trees?
A: Verkle Trees produce much smaller proofs—logarithmic in base k instead of binary—and enable stateless verification with minimal bandwidth usage.

Q: Do Verkle Trees require trust assumptions?
A: When using KZG commitments, they rely on a trusted setup (like zk-SNARKs). However, alternatives like IPA avoid this but have larger proofs.

Q: When will Ethereum implement Verkle Trees?
A: While not yet live, Verkle Trees are under active research and testing. They are expected to play a role post-danksharding for further scalability gains.

Q: Can Verkle Trees handle dynamic updates efficiently?
A: Yes—updating a single leaf affects only its path to root, with update complexity O(k logₖ n), making them suitable for high-throughput environments.

Q: Are Verkle Trees quantum-resistant?
A: Not fully. Like most pairing-based crypto (e.g., KZG), they’re vulnerable to quantum attacks. Post-quantum alternatives are being explored.

Conclusion

Verkle Trees mark a transformative step in Ethereum’s journey toward mass adoption. By slashing proof sizes and enabling stateless clients, they unlock new possibilities for scalability, accessibility, and efficiency.

Backed by advanced cryptography like polynomial commitments and multi-proof compression techniques, Verkle Trees exemplify how innovation in theoretical computer science directly fuels real-world blockchain progress.

👉 Explore cutting-edge crypto innovations shaping the future

As Ethereum continues evolving, embracing concepts like Verkle Trees will be key to building a faster, leaner, and more decentralized web.