Verkle Trees: Polynomial Commitments (Part 2/2)

Part 1 ended with a problem: Merkle proofs in Ethereum's state trie are too large for stateless validation. At several MB per block, the bandwidth cost of including proofs would push solo validators toward data centers.

Verkle trees offer an answer: replace hash-based commitments with polynomial commitments. Each node stores a curve point instead of a hash, and nodes widen from 16 children to 256. Instead of proving a leaf by providing every sibling hash on the path to the root (~3 KB), the prover sends a small proof at each level (~150 bytes), roughly 20x smaller. By the end of this post, you'll understand how.

From Values to a Polynomial

The central idea is to build a vector commitment: a scheme that commits to many values and lets you prove any single one without revealing the others. This is what puts the "V" in Verkle (Vector commitment + Merkle).¹ Same tree structure, different commitment at each node.

We do it with polynomials. Represent all 256 children of a node as evaluations of a single polynomial:

$$P(x) = a_0 + a_1 x + a_2 x^2 + \cdots + a_{255} x^{255}$$

We pick positions $0, 1, \ldots, 255$ and choose the coefficients $a_0, \ldots, a_{255}$ so that:

$$P(i) = v_i \quad \text{for } i = 0, 1, \ldots, 255$$

This gives us a degree-255 polynomial that passes through every child value. Such a polynomial always exists and is unique: any $n$ position-value pairs determine exactly one polynomial of degree $n - 1$.² The algorithm that finds this polynomial is called Lagrange interpolation.

So far this is just algebra. We have a polynomial that encodes the children, but sharing $P$ directly would mean transmitting all 256 coefficients, no better than sending the children themselves. We need a way to compress $P$ into a short commitment. That's where elliptic curves come in.

One Curve Point for an Entire Polynomial

Heads up: all arithmetic from here on (the polynomial's coefficients, its evaluations, the elliptic curve's scalars) happens over the same finite field $\mathbb{F}_p$.

Suppose there's a secret scalar $s$ that nobody knows, but everyone has access to the following public parameters:

$$G, \ sG, \ s^2G, \ \ldots, \ s^dG$$

How $s$ is generated and destroyed is covered in the Appendix. For now, take these points as given. To commit to $P(x)$, the prover computes:

$$\begin{aligned} C &= a_0 \cdot G + a_1 \cdot sG + \cdots + a_d \cdot s^dG \\ &= P(s) \cdot G \end{aligned}$$

Note that the prover doesn't need $s$ to compute $C$: they just combine their polynomial's coefficients with the public parameters.³

The result is a single curve point (48 bytes compressed) that commits to the entire polynomial. Just as a collision-resistant hash won't produce the same output for two different inputs, this commitment is binding: two different polynomials $P \neq Q$ satisfy $P(s) \neq Q(s)$ with overwhelming probability, so their commitments $C = P(s) \cdot G$ are distinct.⁴

Each Verkle node now stores this $C$ instead of a hash. We have the commitment; now we need a way to prove what's inside it.

Opening Proofs: Proving a Single Value

Alice wants to open the commitment $C$ at position $z$ to verify it holds value $y$. The prover must convince her that $P(z) = y$ without revealing $P$ or any other child. How?

The key insight comes from polynomial algebra: if $P(z) = y$, then $P(x) - y$ has a root at $x = z$, so $(x - z)$ divides it evenly. We define the quotient polynomial:

$$Q(x) = \frac{P(x) - y}{x - z}$$

This division is exact if and only if $P(z) = y$. A false claim leaves a remainder, so the prover can't produce a valid $Q$.

The opening proof $\pi$ is simply a commitment to $Q$:

$$\pi = Q(s) \cdot G$$

One curve point. No siblings needed.

Now the verifier needs to check that $Q$ is legitimate. If the division was exact, multiplying back gives a polynomial identity that holds at every point, including $x = s$:

$$P(s) - y = Q(s) \cdot (s - z) \tag{1}$$

The verifier can't check this equation directly. They have $C = P(s) \cdot G$ and $\pi = Q(s) \cdot G$, but the curve points hide their scalars: extracting $P(s)$ or $Q(s)$ from them is the discrete logarithm problem. And $(s - z)$ requires knowing $s$, which nobody has.

Verifying the Proof with Pairings

A pairing $e$ is a function that takes a point from one curve group ($\mathbb{G}_1$) and a point from another ($\mathbb{G}_2$) and outputs an element in a target group, with the property of bilinearity:

$$e(aG_1, bG_2) = e(G_1, G_2)^{ab}$$

Feed in a point hiding some scalar $a$ and another hiding $b$, and the output captures their product. We can't extract $a$ or $b$, but we can check whether two products are equal by comparing pairing outputs.⁵ Pairings require two distinct curve groups; the $G$ we've been using lives in $\mathbb{G}_1$ (becoming $G_1$), and $G_2$ is a generator in $\mathbb{G}_2$. The public parameters also include $sG_2$.

The strategy: express each side of equation $(1)$ as a product of two scalars, then feed one factor into $\mathbb{G}_1$ and the other into $\mathbb{G}_2$. The right side naturally factors as $Q(s) \cdot (s - z)$. The left side is just $(P(s) - y) \cdot 1$, so we pair it with the plain generator $G_2$:

Left side: $(P(s) - y)G_1 = C - yG_1$, so

$$e(C - yG_1, G_2) = e(G_1, G_2)^{P(s) - y}$$

Right side: $Q(s) \cdot G_1 = \pi$ and $(s - z)G_2 = sG_2 - zG_2$, so

$$e(\pi, sG_2 - zG_2) = e(G_1, G_2)^{Q(s)(s-z)} $$

These are equal if and only if equation $(1)$ holds, so verification reduces to a single check:

$$e(C - yG_1, G_2) = e(\pi, sG_2 - zG_2) \tag{2}$$

The verifier knows every variable in this equation: $C$ and $\pi$ came from the prover, $y$ and $z$ are the claimed value and position, and $G_1$, $G_2$, $sG_2$ are public parameters. One pairing check, no siblings.

Putting It All Together

Step back and consider what we just built. A node with 256 children gets encoded as a polynomial and mapped to a single curve point. To open one child, the prover divides out the corresponding root, producing a quotient polynomial, and maps it to a second curve point. A pairing function then reaches across two curve groups and, through bilinearity, verifies the division was exact from the curve points alone. Two points, one check, done. That this works at all feels like reaching through a crack in the universe.

This commit-open-verify scheme is called KZG (Kate-Zaverucha-Goldberg): produce one commitment per node, one opening proof per level. A Merkle tree with width 16 needs ~8-10 levels and 15 sibling hashes (480 bytes) at each one. A Verkle tree with width 256 covers the same state in just ~3 levels,⁶ with a single ~48-byte proof at each:

Polynomial commitments also remove a tradeoff that hash-based Merkle proofs face. In a Merkle tree, narrower means smaller proofs (fewer siblings per level), but deeper means more disk reads per lookup (the bottleneck from Part 1's appendix). Stateless validation eases the depth side, but proof size still grows with width. With polynomial commitments, it doesn't: nodes can be wide and the tree shallow.

Ethereum's Verkle Proposal: IPA

The figures above reflect KZG proof sizes. Ethereum's Verkle tree proposal swapped in different building blocks: a different commitment type (Pedersen), proof technique (IPA), and curve (Bandersnatch). The architecture is the same; individual proofs are larger (~544 bytes) and verification slower, but the tradeoff worth it: no trusted setup. If the secret $s$ in a KZG ceremony were ever reconstructed, the entire scheme would break. For a state tree securing all of Ethereum's value, the community preferred eliminating that risk entirely.

At block level, Dankrad Feist's multiproof scheme merges all opening proofs across a block into a single constant-size proof (~200 bytes), regardless of how many state accesses the block contains.

What's Next

Verkle trees now look unlikely to make it into Ethereum: their reliance on elliptic curve cryptography isn't quantum-resistant, and the community is leaning toward a hash-based binary state tree instead. The ideas we built here (committing to data with polynomials, proving properties without revealing everything), though, are foundational to something bigger: zero-knowledge proofs. They provide a way to prove not only state access, but that an entire block's execution was correct in a single, compact proof. Smaller proofs don't solve every problem (e.g., someone still has to store the ever-growing state to construct blocks), but increasingly, the goal is to prove more and store less.

The cryptography behind zero-knowledge proofs, from arithmetic circuits to the difference between proof systems, is something I'll explore on this blog soon. Stay tuned.

Appendix