Proof PeaksISSUE #12 of 38

verkle trees · stateless witnesses

ZeekaVSThe Collision

Zeeka saysVerkle trees swap Merkle siblings for vector commitments, shrinking proofs from hundreds of hashes to a handful of openings — the key to stateless Ethereum clients.

A Merkle proof must include every sibling along the path, so a wide, deep tree means big witnesses. Verkle trees replace each node with a vector commitment that can prove one child without exposing its siblings. That lets the branching width grow huge (≈256) while the proof stays tiny — roughly one opening per level instead of (width−1) hashes per level.

The consequence is profound: witnesses become small enough to ship inside every block, so a stateless client can validate without storing the full state at all. The trade-off is more CPU for the commitment math and a complex migration from the existing MPT. The demo computes Merkle vs verkle witness sizes for a 250-million-key state.

Power-ups you unlock

Vector commitments prove a child without revealing siblings
Much higher branching width (≈256) with tiny proofs
Witness size ≈ depth, independent of node width
Small enough to ship a witness with every block
Enables stateless clients that hold no full state

The Collision attacks — common mistakes

Expecting verkle to be faster to compute (it trades CPU for proof size)
Assuming Merkle proof size is independent of width (it is not)
Underestimating the migration complexity from the MPT
Confusing data availability with state witnesses

Boss battleCompute Merkle vs verkle witness sizes for a 250M-key state at width 16 vs 256 and compare.

Example code

<!doctype html><html><head><meta charset="utf-8"></head>
<body style="background:#06040d;color:#e6e0ff;font-family:monospace;padding:20px"><pre id="o"></pre>
<script>
// why verkle? witness size. Merkle ≈ (width−1)·depth sibling hashes;
// verkle ≈ depth openings, regardless of width.
function sizes(numKeys, width){
  const depth = Math.ceil(Math.log(numKeys)/Math.log(width));
  return { depth, merkleHashes:(width-1)*depth, verkleOpenings:depth };
}
const N = 250000000;                               // ~ethereum account-count scale
const a = sizes(N, 16);                            // hex Merkle (width 16)
const b = sizes(N, 256);                           // verkle (width 256)
document.getElementById('o').textContent = [
  'proving 1 key in a ' + N.toLocaleString() + '-key state:',
  'hex Merkle  width 16  → depth ' + a.depth + ', ~' + a.merkleHashes + ' sibling hashes',
  'verkle      width 256 → depth ' + b.depth + ', ~' + b.verkleOpenings + ' openings',
  'verkle witness ~' + Math.round(a.merkleHashes / b.verkleOpenings) + '× smaller',
  '→ small enough to ship with every block → stateless clients'
].join('\n');
</script></body></html>

▶ Open the interactive comic issue

‹ Merkle Patricia Tries · Ethereum State Deep Zk Proofs · Completeness · Soundness · Zero-Knowledge ›