Verkle Trees — The Future of Blockchain State

1// HASH COMMITMENT (Merkle Tree)
2// Parent node commits to 16 children by hashing them all:
3parent_hash = Hash(child_0 | child_1 | ... | child_15)
4
5// To PROVE child_3 is genuine:
6// Verifier needs:
7//   - value of child_3
8//   - hashes of child_0, child_1, child_2, child_4, ... child_15
9//     (all 15 OTHER children)
10// Verifier computes:
11//   recomputed = Hash(c0 | c1 | c2 | CHILD_3 | c4 | ... | c15)
12//   check: recomputed == parent_hash
13
14// Cost: 15 × 32 bytes = 480 bytes of proof data PER NODE
15// With 15 nodes in path: 15 × 480 = 7,200 bytes minimum
16// Plus RLP encoding overhead: 10-15KB total

1// POLYNOMIAL COMMITMENT (Verkle Tree — IPA/KZG scheme)
2//
3// SETUP (mathematical):
4// Think of 256 children as points on a polynomial curve:
5//   f(0) = child_0, f(1) = child_1, ..., f(255) = child_255
6// The "commitment" C is a compact encoding of this polynomial:
7//   C = commit(f)  → 32-48 bytes regardless of f's size
8//
9// To PROVE child_42 is genuine:
10// Prover produces an "evaluation proof":
11//   π = prove(f, 42, f(42))  → 32-48 bytes
12//
13// Verifier checks:
14//   verify(C, 42, child_42, π)  → true/false
15//
16// CRITICAL: π is the SAME SIZE regardless of the number of children!
17// 256 children → same 32-48 byte proof as 2 children
18// No sibling data needed at all
19//
20// Full proof for an account:
21// depth × (commitment + evaluation_proof) = depth × ~64 bytes
22// For depth 8: 8 × 64 = 512 bytes
23// Compare: Merkle depth 15: 15 × 480 = 7,200 bytes

1// PEDERSEN COMMITMENT — Intuition (not exact code)
2//
3// Setup: we have fixed public elliptic curve points:
4//   G_0, G_1, G_2, ..., G_255  (256 "basis points", public)
5//
6// To commit to 256 values [v_0, v_1, ..., v_255]:
7//   C = v_0 × G_0 + v_1 × G_1 + ... + v_255 × G_255
8//
9// C is a single elliptic curve point — 32-48 bytes
10// It "encodes" all 256 values cryptographically
11//
12// BINDING: You cannot change any v_i without changing C
13// HIDING: C alone reveals nothing about individual values
14//
15// To prove "v_42 = X":
16// The IPA (Inner Product Argument) protocol lets you prove:
17//   "C commits to a polynomial f where f(42) = X"
18//   in O(log n) rounds, producing a proof of size O(log n)
19//
20// For n=256: log(256) = 8 rounds → proof is ~8 × 32 bytes = 256 bytes
21// vs Merkle: 255 sibling hashes × 32 bytes = 8,160 bytes
22//
23// The ratio: 8,160 / 256 ≈ 32× smaller just from this one node
24// Across the whole tree: 100× smaller overall

1// EIP-6800 defines a new key structure for Verkle trees:
2// Key = 32 bytes = stem (31 bytes) + suffix (1 byte)
3//
4// STEM identifies an account:
5stem = keccak256(address)[0:31]   // first 31 bytes of address hash
6// All data for ONE account shares the SAME stem!
7//
8// SUFFIX identifies what type of data:
9// suffix = 0  → account version
10// suffix = 1  → account balance
11// suffix = 2  → account nonce
12// suffix = 3  → code hash
13// suffix = 4  → code size
14// suffix = 64-127 → code chunks (contract bytecode)
15// suffix = 128-255 → storage slots 0-127
16
17// This is a HUGE change from current MPT:
18// Current: account metadata and storage are in SEPARATE tries
19//   → account trie + storage trie = 2 separate proofs
20// Verkle: account metadata AND nearby storage are in the SAME tree
21//   → one proof covers balance + nonce + first 128 storage slots
22
23// Example: proving Alice's balance
24// Current Ethereum: prove path in account trie (15KB)
25// Verkle: prove stem=hash(alice)[0:31], suffix=1 (~150 bytes)

1// ETHEREUM MPT PROOF (current):
2// Path depth: ~15 nodes
3// Each node proof:
4//   - 15 sibling hashes × 32 bytes = 480 bytes
5//   - RLP length prefixes: ~20 bytes
6//   - Node type tag: ~5 bytes
7// Per node: ~505 bytes × 15 nodes = 7,575 bytes
8// Plus leaf value (RLP-encoded account): ~100-200 bytes
9// Total: 7,700 - 15,000 bytes (7-15KB)
10//
11// ─────────────────────────────────────────────────────
12//
13// VERKLE TREE PROOF (proposed):
14// Path depth: ~4 nodes
15// Each node proof:
16//   - 1 Pedersen commitment C: 32 bytes
17//   - 1 IPA evaluation proof π: 8 × 32 bytes = 256 bytes
18//     (IPA rounds: log₂(256) = 8 rounds)
19// But! IPA proofs AGGREGATE across nodes:
20//   - Total proof for full path: ~576 bytes (non-aggregated)
21//   - With aggregation across multiple keys: ~150-200 bytes/key
22//
23// The magic of aggregation:
24// When proving 10 leaves from the same block:
25// MPT: 10 × 10KB = 100KB of proof data
26// Verkle: ~10 × 150 + shared_parts ≈ 2-3KB total
27// Ratio: 100KB → 2-3KB = 33-50× better with aggregation

1// CHALLENGE: Migrating ~200M state objects without downtime
2//
3// Current Ethereum state (as of 2024):
4// - ~180M accounts (incl. contracts)
5// - ~100B+ storage slots (mainly in large contracts)
6// - MPT has ~1.5B+ nodes in LevelDB
7//
8// Naive migration: hash all accounts → build Verkle tree
9// Time estimate: several days of downtime
10// → Completely unacceptable
11//
12// ACTUAL PLAN: Lazy/Overlay Migration
13// Phase 1: At fork block, NEW writes go to Verkle tree
14//           Old state remains in MPT temporarily
15//           Dual tree maintained briefly
16//
17// Phase 2: When old MPT account is FIRST ACCESSED after fork:
18//           → Migrate it to Verkle tree
19//           → Delete from MPT
20//           → Record that it was migrated
21//
22// Phase 3: After 1-2 years, assume all accessed accounts migrated
23//           Background process migrates remaining rarely-used accounts
24//           MPT retired entirely
25//
26// Risk: During dual-tree period, nodes must maintain both structures
27// Memory and storage overhead: ~50% during transition

1// WRITE COST COMPARISON (approximate)
2
3// Per-node write operations:
4
5Ethereum MPT (current):
6  keccak256(node data)         → ~30ns per call
7  RLP encoding                 → ~50ns per node
8  Total per node write:        → ~80-120ns
9
10Verkle Tree (proposed):
11  Pedersen commitment update   → ~2-5μs per node
12    (elliptic curve scalar mul)
13  IPA proof generation (prover)→ ~50-200ms for full block witness
14  Total per node write:        → ~2-6μs (25-50× slower than keccak)
15
16Substrate Patricia:
17  Blake2b-256(node)            → ~20ns per call
18  SCALE encoding               → ~20ns per node
19  Total per node write:        → ~40-60ns
20
21// KEY MITIGATION:
22// Write path (commitment update) and proof path (witness gen) are SEPARATE:
23// - Commitment update happens at each block end (~2-6μs/node × depth)
24//   → Acceptable: 10,000 state changes × 4 nodes deep × 4μs = 160ms
25//   → Current MPT: 10,000 × 15 nodes × 0.1μs = 15ms
26//   → Verkle write: ~10× slower than MPT
27//
28// - Witness generation (for stateless): only done by BLOCK PROPOSERS
29//   → Other nodes just verify witnesses (very fast, ~few ms)
30//   → Block proposers have extra time to generate witnesses