Merkle trees and Verkle trees

You have a large set of records. You want to publish a short commitment now, and later convince someone of one record without sending the set. That is the job of an authenticated data structure.

A hash commits to one string. SHA-256 of one blob is a fixed fingerprint of that blob. To check it, hash the blob again and compare. A match says this is the same string. It says almost nothing about any other string: a different payment, or the rest of a file, is a different hash, and this fingerprint does not contain those bytes.

A tree of hashes commits to a set. Hash each record into a leaf. Hash the leaves in pairs, then hash the pairs, until one root remains. Change any leaf and the hashes above it change, so the root changes. That one published value stands for the whole set.

A membership proof is a small subset of those hashes. To prove leaf 3 is in the set, send the leaf plus the sibling hash at each step on the path to the root. A balanced tree of n leaves needs about log₂(n) siblings: three hashes when there are eight leaves, about twenty when there are a million. The verifier hashes the leaf together with those siblings, in order, and checks the root they already know. The other leaves stay where they are. Each sibling already summarizes its side of the tree.

A Verkle tree keeps this shape and replaces the hash at each parent with a vector commitment, so the proof no longer carries every sibling. The toy below has eight payment records. The hashes are real SHA-256, drawn as the first four bytes so the structure fits on the screen. The Verkle half is a picture of the idea plus a labeled byte model. It does not run a pairing.

Open the explainer (full page). The tabs are also deep links: build, proof, Verkle, side by side.

Why a root is worth publishing

Suppose eight people hand you a payment each. You can publish the list. Anyone can read it, and anyone can see that you did not swap an entry, because they have the entries. That only works while the list is small enough to ship.

Publish a hash of the whole list and the commitment is 32 bytes, but a single disputed payment still requires the other seven, because a hash checks out only when you rehash the exact preimage. The commitment got small. The proof did not.

A tree fixes the second half. Each record is hashed on its own. Pairs of digests are hashed, then pairs of those, until one root remains. The root is the commitment. A proof of one record is the sibling digest at each level: enough to recompute the root, and nothing else. The verifier does not learn the other records. They learn that this record sits in the set that produced the root they already trust.

Membership is the toy in this post. Non-membership is the same walk with a different claim. If the leaves are sorted, you prove the two neighbors that bracket the missing key, and the verifier sees an empty gap. A sparse Merkle tree does it by proving that the leaf at that key is the empty value. The sibling machinery does not change. What changes is the statement.

A Merkle tree from eight records

The records, in order:

Two rules, and they are the whole construction.

A leaf is SHA-256 of the UTF-8 bytes of leaf: concatenated with the record. The prefix is domain separation, so a leaf digest cannot be confused with an internal one. The first four bytes:

A parent is SHA-256 of the raw 32-byte left digest concatenated with the raw 32-byte right digest. Not the hex text. The bytes. The parent of leaves 0 and 1 begins fb695a13. The parent of leaves 2 and 3 begins 84b7b765. Fold once more and the left half of the tree begins dba8d9cc. The root of all eight begins c30897e6. In full:

c30897e6570caeccb406c237e266c0ed4ecea84750c8a4d63ee5d56f961a5e32

You can recompute leaf 2 with nothing but a hash function:

import hashlib
hashlib.sha256(b"leaf:carol->dave").hexdigest()
# 02a8b4d9b5ed58091146b02e769127d3f46273ef1055d4c53421c854a0608601

The diagram hashes the same bytes. Hover a node for the rest of the digest.

Try it. Watch the tree build. Leaves appear, then each parent, then the root. Press Play or Next. Then edit one record. Only the path to the root goes amber and changes. Every other parent was hashed from children you did not touch, and a hash does not move unless its input does.

That dirty path is the update cost. One leaf, three parents, four hashes. A balanced tree of a million leaves is about twenty hashes, still only the path. The rest of the tree is idle. Changing a leaf does not rebalance the tree and does not rebuild it. You publish a new root. The pairs you already computed stay paired.

Adding a leaf is the same kind of work. The toy’s eight leaves fill a perfect binary tree, and a ninth record does not fit that shape. The append does not reshuffle those eight into a new balanced tree, and it does not pad them out to sixteen and rehash the upper half. The finished eight-leaf tree becomes the left child, untouched, old root included. The new leaf is the right child. For ivy->alice that leaf begins baa050c5, and the published root begins 3ac3ec43: one new hash of the old root’s raw bytes and that leaf. Two hashes are computed. The other fifteen nodes are reused as they stand. log₂(9) is a little more than three; this path is shorter than that because the tree is not rebalanced. In a deeper tree that you do keep balanced, the path you rehash is still only about log₂(n) long.

Try it. On the build tab, once the root is up, press Add 9th record. The node marked REUSED keeps the old root c30897e6. The new root is different. The ninth record in the toy is ivy->alice. Remove the 9th record and the worked example comes back.

What a Merkle proof contains

Take leaf 2, carol->dave, digest 02a8b4d9. The verifier has the root and this record. You send the sibling at each level. There are three, because a full binary tree of eight leaves is three levels deep. log2(8) = 3. That is the whole size argument: one sibling per level, and a balanced tree has log2(n) levels. Proof size is O(log n) hashes, 32 bytes each.

The siblings for leaf 2:

1. On the right, leaf 3, 73d803b9. The running digest is the left child, so the parent is H(running ∥ sibling) = 84b7b765.
2. On the left, the other pair in this half, fb695a13. Now the running digest is the right child, so H(sibling ∥ running) = dba8d9cc.
3. On the right, the other half of the tree, a4ae810a. H(running ∥ sibling) = c30897e6.

That last value is the root. The proof checked out. The verifier never saw Alice’s payment, or Frank’s, or anyone’s but Carol’s. The sibling hashes already summarize those subtrees. Changing any byte of any sibling, or any byte of the record, moves the recomputed root. The published root is the only thing the verifier was holding. A mismatch is a failed proof. There is no partial credit.

Try it. Open the proof, click leaf 2, and step until the folds reach the root. Then press Tamper on one sibling, or edit its eight hex digits, and press Verify. Restore brings the same walk back to a pass. The box edits the first four bytes of the real digest and leaves the other 28 alone.

Ninety-six bytes for this tree: 3 × 32. The record itself is extra, and both kinds of proof in the next section carry the value, so the interesting comparison is the overhead. A million leaves is about 20 × 32 = 640 bytes for one key. Still small. The pain shows up when the tree gets wide, and when you prove many keys at once.

Where this pattern already earns its keep

Bitcoin headers and light clients

A block header carries a Merkle root of its transactions. A light client stores headers, not block bodies. To believe one transaction is in a block, it takes the transaction and the Merkle branch (the sibling hashes) and recomputes the root, then compares it to the header. The block might hold thousands of transactions. The proof holds a few dozen hashes. This is simplified payment verification. The client is not checking every transaction. It is checking that this one is inside a header it already accepted.

Git

A commit points at a tree object. A tree is a sorted listing of names and the hashes of blobs or subtrees. The hash of that listing is the commitment to the directory. Change one file and every directory hash on the path to the commit changes. Nothing off that path changes. It is the same dirty-path picture as the toy. Git’s tree is not a fixed binary Merkle tree. It hashes a listing. The authenticated-path idea is the same, which is why two people with the same commit hash have the same files, byte for byte.

Ethereum state, only as a bridge

Execution clients today commit to state with a hexary Merkle-Patricia trie. Account keys are paths of nibbles, sixteen ways at each step. Nodes are hashed. The state root sits in the block header. You can prove one account with the nodes on its path. It works, and it has worked for years. Patricia tries add prefix compression (extension nodes) on top of the Merkle idea, which is why a proof is not a clean log16(n) hashes. The witnesses are bulky. That bulk is the problem Verkle trees are aimed at. A separate deep dive on nibbles and extension nodes is worth doing after this one. This post only needs the bridge: Ethereum already publishes a root, and the thing it wishes were smaller is the proof.

Files, and certificate logs

A CDN or an installer can publish a Merkle root over chunks of a file. A client downloads the chunks it needs, plus a proof, and checks the root it pinned earlier. Certificate Transparency logs append certificates to a Merkle tree and hand out an inclusion proof under a signed tree head. A monitor can check that a certificate is in the log a browser actually saw. Inclusion is the same fold-the-siblings procedure as leaf 2 above.

Why wide trees hurt, and why many keys hurt more

A hash is a blunt vector commitment. To check H(c0 ∥ c1 ∥ … ∥ c7) you need every child. A proof of one child in a node of width w ships the other w − 1 children. The tree gets shallower, log_w(n) levels, but the product (w − 1) · log_w(n) gets worse as w grows. Binary is the best width if hashing is your only tool. “Just make the trie wider” does not shrink witnesses. It inflates them. The diagram’s Verkle tab shows the eight-wide case: proving one child of a hashed row costs the other seven digests, 224 bytes, against 96 bytes for the binary tree of the same eight records.

Many keys add a second problem. k independent proofs cost about k log n hashes. Sharing helps. Two neighboring keys reuse the siblings near the root, and a multiproof sends those once. The union of the paths is still large when the keys are scattered, which is what a block of unrelated state lookups looks like. Clustered keys are cheap. Scattered keys are the workload.

Light clients and stateless validators feel this as bandwidth. A stateless Ethereum client would receive, with each block, a witness: the state the block touches, plus a proof that those values sit under the previous state root. The witness has to cross the network inside a 12-second slot. ethereum.org (page update 24 June 2026) puts a 1,000-leaf witness at about 3.5 MB for a 7-level Merkle trie and about 150 kB for a 4-level Verkle tree, roughly 23 times smaller. EIP-6800 frames the same bottleneck: a hexary Patricia proof of one account is on the order of 3 kB, and a block that touches thousands of accounts does not fit comfortably in a slot. The structure is what makes the Merkle witness heavy. A faster hash function does not fix it.

What changes in a Verkle tree

Verkle is “vector commitment” welded to “Merkle”. The tree still has a root. A parent still summarizes its children. The summary is no longer a hash of the concatenation.

A vector commitment C binds a list v0, v1, …, v_{w-1} into one short value. An opening proves “position i is vi” without revealing the other positions. A multiproof proves several positions, often as a single short opening. Width stops multiplying the proof. That is the entire reason to bother.

What a vector commitment gives you. Three properties, and they are enough for the tree:

1. Binding. The same C cannot be opened to two different values at the same position.
2. A succinct opening. The proof does not grow with the width. This is the property a hash lacks.
3. Batching. Many positions, and in the schemes that matter here many commitments, can share one proof.

KZG (Kate, Zaverucha, Goldberg) is the clean textbook way to get those properties. Treat the vector as the evaluations of a polynomial, commit to the polynomial with a structured reference string, and open an index with a constant-size proof: one group element, 48 bytes compressed on BLS12-381. A pairing is how the verifier checks that proof. Pairings are the same family of tools Groth16 uses. You do not need a pairing to understand the tree. The tree only needs “C commits to the vector, and π opens positions.” The pairing write-up is a separate post, for when the opening itself is the question.

In the picture, one wide node holds the eight records and a single seal C. The seal you see is a label (a truncated hash) so the row has a handle. A real commitment is a group element. Proving three positions lights three cells and one opening card. The Merkle column, for the same three cells, fills with sibling hashes.

Try it. Play the Verkle contrast. It starts as a wide hash (seven siblings), narrows to the binary proof (three), then replaces both with one opening. The last steps ask for leaves 0, 3, and 7 together. Click cells if you want a different set.

For those three leaves the binary multiproof is four sibling hashes, 128 bytes, after sharing. The single-node Verkle opening stays 48 bytes. The toy is too small for a dramatic ratio. The shape is the lesson: adding keys grows the Merkle bag and does not grow the opening.

Side by side

The counter in the last tab is pedagogical, and it says so. It counts 32-byte sibling hashes on one side and 48-byte KZG elements on the other. It does not count the values, which both proofs carry. It is not an Ethereum witness encoder: no stems, no extension nodes, no RLP, no IPA proof bytes. The 3.5 MB and 150 kB figures above are the published comparison. The counter is there so you can watch the shape change as you add keys.

Two presets are worth running on a tree of 2^24 leaves, width 256, which is the shape of the counter’s “large” model:

• 1,000 clustered keys. Merkle 512 bytes, Verkle 288 bytes. Locality makes a Merkle multiproof tiny, because the paths share almost everything above a small subtree.
• 1,000 spread keys. Merkle 448,768 bytes, Verkle 60,336 bytes. This is the scattered-witness case. The Verkle number is still only commitments and one opening. The ethereum.org 150 kB figure is larger because a real witness also carries the values and a different proof system. Same direction, different encoding.

Try it. Open the side-by-side tab. Leave it on the eight-leaf picture and toggle Both, Merkle, and Verkle. Step Play and watch the Merkle count climb while the opening arrives once. Then press 1,000 spread and 1,000 clustered. The picture stays a sketch. The counter uses the big tree. “How the counter counts” is the disclosure under the numbers, and it is worth opening once.

When I would pick which

I would pick a Merkle tree when the proofs are few and narrow, updates have to be cheap, and I want no setup and no elliptic curves. Bitcoin inclusion, Certificate Transparency, git, content-addressed files, and any system whose assumption should be “we have a hash” all live here. A binary Merkle tree is also much easier to implement correctly. If I only ever prove one key, and a kilobyte is fine, the Merkle proof is already small. In the eight-leaf toy the two overheads are 96 bytes and 48 bytes. That is not a reason to take on a commitment scheme.

I would pick a Verkle tree when one commitment covers a huge state and the thing I ship all day is a witness for many scattered keys. That is the stateless-client problem. The win shows up in the multiproof, and in the freedom to make nodes wide without shipping the siblings. If a block’s accesses are scattered across a 2^24-leaf tree, the counter’s gap is hundreds of kilobytes against tens of kilobytes, before counting the Patricia encoding that makes today’s witnesses larger still.

If the witness is most of a node, hashing is honest and fine: you were going to send those bytes anyway. Verkle earns its complexity when the node is wide and the block touches a few slots of it.

Limits, said plainly

Verkle trees move complexity into the commitment. KZG’s structured reference string is a real trust assumption, or a real ceremony. Inner-product arguments avoid that ceremony and cost more to prove; that is the direction of the Ethereum spec, on the Bandersnatch curve, precisely so the deployment does not depend on a setup. Either way, updating a node is far more expensive than hashing two children, and the implementations are young next to SHA-256. A quantum computer that breaks discrete log and pairings breaks KZG and IPA. It does not, by itself, break a Merkle tree built on a post-quantum hash. None of this is a reason to ignore the idea. It is the reason a Merkle tree is still the default everywhere the witness is already small enough.

What to try next

Slow the build down and edit a single leaf until the dirty path is obvious. Tamper with one sibling and watch the fold miss the root. When that feels mechanical, the useful deep dive is the Merkle-Patricia trie: nibbles, extension nodes, and why Ethereum’s current witnesses are larger than a clean binary proof of the same keys. After that, tie the opening card in the Verkle picture to an actual KZG open. One polynomial, one evaluation proof, and the pairing check that makes “position i is v” stick. The Groth16 post is that pairing machinery, when you want it. You do not need it for the tree.

• Share this article: