Skip to content
Crypto.world

Research

Fractional Verkle Trees: A Hypertree Decomposition and Verified Proof Serialization Architecture for High-Performance Blockchain State Accumulators

Ethereum's planned move from Merkle Patricia Tries to Verkle Trees shrinks block witnesses dramatically, but the reference implementation carries performance and correctness problems that hurt home…

Fractional Verkle Trees: A Hypertree Decomposition and Verified Proof Serialization Architecture for High-Performance Blockchain State Accumulators
arXiv
2606.17111
Published
2026-06-15
Authors
Ekleen Kaur, Everton Fraga

AI summary

Overview

Research area: Blockchain state accumulators and cryptographic commitment schemes — specifically Verkle Trees as specified for Ethereum under EIP-6800, and the systems-level engineering of the reference Go implementation (go-verkle).

Technical level: Advanced. The paper assumes familiarity with polynomial/vector commitments, elliptic curve groups (Bandersnatch/Banderwagon), authenticated data structures, LSM-tree storage engines, and Go runtime behaviour (garbage collection, sync.Pool, atomics).

Scope (one sentence): The paper diagnoses four concrete correctness and performance defects in the reference go-verkle implementation, fixes them, and proposes "Fractional Verkle Trees" — a decomposition of the global state into N independent sub-accumulators coordinated by a binary Merkle tree — evaluated with benchmarks on Apple M1 Pro hardware.

What This Paper Is About

Ethereum's planned move from Merkle Patricia Tries to Verkle Trees shrinks block witnesses dramatically, but the reference implementation carries performance and correctness problems that hurt home validators. The authors identify four such problems — phantom node creation during deletion of non-existent accounts, oversized 64-byte database keys, redundant copying during proof deserialization, and a proof-of-absence wire-format incompatibility between clients — and repair each one. On top of those fixes, they propose splitting the single monolithic Verkle tree into many smaller independent "hypertrees" under one global root, so that state updates can be computed in parallel and fit better in CPU cache.

Key Contributions

  1. Fractional Verkle Trees (FVT), a hypertree decomposition. The global state is partitioned deterministically across N independent sub-accumulators using φ(addr) = BigEndian(SHA-256(addr)[0:4]) mod N, coordinated by a binary Merkle tree of depth ⌈log₂ N⌉. Because sub-trees share no mutable state, commitment computation is goroutine-parallel with zero lock contention.

  2. Correction of four implementation defects in go-verkle. (a) An existence check before deletion that eliminates phantom InternalNode creation; (b) a 32-byte NodeRef = SHA-256 of the uncompressed commitment point, replacing 64-byte point keys and paired with an enriched HashedNode carrying a cached commitment; (c) zero-copy proof deserialization via RefCountedBuffer, ProofView, and DeserializeProofBatchZeroCopy; (d) deterministic Proof-of-Absence serialization using HashMap-based deduplication with lexicographic sorting, plus a fix to the DepthExtensionPresent encoding that emitted k OtherStems entries rather than 1 when k > 1 missing stems shared a PoA stem.

  3. A Merkle coordinator instead of a nested Verkle coordinator. The authors trade ⌈log₂ N⌉ × 32 bytes of proof overhead for root recomputation at 91 µs versus roughly 500 ms for an equivalent Verkle commitment over 1000 leaves.

  4. The first empirical benchmark of FVT-style decomposition as a live-blockchain state accumulator, in contrast to prior FVT work (Iavich et al., 2025) that applied hypertree decomposition only to the signature domain using a Python prototype with analytical cost estimates.

Main Findings

  • Insertion benchmarks (Apple M1 Pro, synthetic accounts with SHA-256 address derivation): FVT serial insertion at 36,043 ns/op versus a baseline of 14,807 ns/op; parallel insertion at 2,433 ns/op with goroutine concurrency; coordinator root computation at 91 µs.

  • Proof deserialization memory: heap allocation falls from 566,760 to 242,004 bytes per 10K proofs, a 57% reduction.

  • Proof size for a representative mainnet case of 8 absent storage slots: FVT proofs measure 864 bytes versus 647 bytes for monolithic proofs — larger in absolute terms, reflecting the coordinator overhead the authors explicitly accept.

  • Network-wide allocation savings: the optimizations eliminate 4.85 PB/year of heap allocation across 6,000 full nodes processing 7,200 blocks daily.

  • Phantom nodes: unchecked deletion of non-existent accounts contributed non-zero scalars to parent polynomial evaluations and caused 35% state trie inflation on mainnet replay.

  • Database key halving: moving from 64-byte to 32-byte node references drops per-internal-node child reference storage from 16 KB to 8 KB (256 references), a 32 MB saving across one million nodes, and yields a 50% reduction in write amplification; the paper attributes a 4× increase in compaction frequency to the 64-byte keys.

  • cowChild cost: enriching HashedNode with a cached commitment pointer makes cowChild O(1) by pointer dereference, measured at 114 ns versus 173 ns on real nodes (34% reduction, eliminating interface dispatch overhead).

  • Cache locality at N = 1000: each hypertree's working set is approximately 200 KB, fitting within commodity x86 L3 cache (6–24 MB); the monolithic tree at |σ| = 2.5 × 10⁸ entries has a per-block working set exceeding 20 GB.

  • Proof-size asymptotics: reduced from O(d · 32) to O(d′ · 32 + ⌈log₂ N⌉ · 32) bytes, a measured 2× reduction at N = 1000.

  • Root rebuild cost: the global root rebuilds in O(N) SHA-256 operations, approximately 90 µs at N = 1024, once per block.

  • Inconsistency in the stated speedup: Section 2.5 states the Merkle coordinator enables "16,000× faster root recomputation than a Verkle coordinator," while the comparison of 91 µs against roughly 500 ms is elsewhere described as a 5,000× improvement. Both figures appear in the paper; they are not reconciled.

Methodology in Plain English

The authors worked in four layers. First, they read the reference Go code closely enough to find correctness bugs — for example, a deletion routine that silently did nothing, leaving later code to create trie paths for accounts that never existed. Second, they patched each bug with a minimal, targeted change: check whether the account's stem exists before deleting, hash commitment points down to 32 bytes so the database sees smaller keys, replace per-proof heap copies with reference-counted views over the original network buffer, and sort and deduplicate proof-of-absence stems so every client serializes them identically.

Third, they designed the hypertree split: hash the address, take the first four bytes, and use that modulo N to decide which of N sub-trees owns the account. Each sub-tree is an ordinary Verkle tree, so the underlying cryptography is unchanged; only the composition changes. A small binary Merkle tree over the N sub-tree roots supplies the single global root that consensus needs. Fourth, they implemented the whole thing in Go and benchmarked it on an Apple M1 Pro against synthetically generated accounts whose addresses are derived with SHA-256, comparing serial and parallel insertion, root computation time, proof sizes, and heap allocation with and without the changes. The paper's evaluation is empirical rather than analytical, which the authors present as a differentiator from prior FVT work.

Why This Matters

Impact on research. The paper argues that the Verkle tree literature has treated the accumulator as a monolithic object rooted at one commitment, and that no prior work decomposed a polynomial commitment accumulator into independent sub-trees while preserving a single global root. It also argues that the systems-level pathologies — disk I/O patterns, GC pressure, cross-client serialization incompatibility — are absent from the literature despite emerging at deployment scale. The four defects it identifies sit at the storage-engine and wire-format layers, meaning they are consensus-safety issues rather than mere performance annoyances.

Real-world applications:

  • Home validator operation, where the paper frames GC pauses on 16 GB hardware as a cause of missed attestations.
  • Stateless client verification, which depends on compact witnesses (the paper cites 2–4 MB MPT witnesses under EIP-4762 versus roughly 576-byte IPA multiproofs).
  • Cross-client interoperability, where the proof-of-absence encoding mismatch caused failures against rust-verkle.
  • State database engineering for any system using LSM-tree-backed authenticated storage, where key size directly multiplies compaction overhead.

Industry relevance. The authors are affiliated with Amazon Web Services, and the work targets Ethereum's stateless roadmap directly. Notably, the decomposition is transparent to consensus: the global root is computed differently, but binding, soundness, and proof-of-absence correctness are claimed to reduce to the security of the underlying Verkle commitment and SHA-256 collision resistance — so no protocol change is required to adopt it.

Future Directions

  • Reconciling the coordinator speedup figures. The 5,000× and 16,000× claims for Merkle-versus-Verkle root recomputation should be pinned to a single measured baseline.
  • Combining algebraic batching with geometric partitioning. The authors note that Boneh, Bünz, and Fisch batching techniques could be applied inside each hypertree to further reduce proof sizes, describing the two approaches as complementary rather than competing.
  • Tuning N. The paper evaluates N = 1000 and N = 1024 for cache-fit and root-rebuild cost, but the optimal value depends jointly on L3 cache size, block-level access patterns, and the ⌈log₂ N⌉ × 32 bytes of proof overhead added per proof; that trade-off is not resolved.
  • Closing the proof-size gap. FVT proofs are larger than monolithic proofs in the measured scenario (864 versus 647 bytes for 8 absent storage slots). Whether the coordinator overhead can be amortized across larger access sets, or reduced structurally, remains open.

Target Audience

Blockchain protocol engineers and client developers working on Ethereum state management, particularly those implementing or reviewing Verkle tree code; applied cryptographers interested in how commitment schemes behave under production storage and concurrency constraints; and systems researchers studying LSM-tree key design, zero-copy deserialization, and GC pressure in latency-sensitive distributed systems. Readers without background in polynomial commitments and Go runtime internals will find the architectural sections accessible but the correctness arguments and code walkthroughs demanding.

Authors’ abstract

Modern blockchain state management faces a critical scalability bottleneck: maintaining cryptographic commitments over hundreds of millions of entries becomes computationally prohibitive. Ethereum's transition to Verkle Trees: polynomial commitment accumulators reducing proof sizes from O(width * depth) to O(depth) via constant-size IPA vector commitments, is a critical step toward stateless operation. Yet, current implementations exhibit pathological characteristics that…

The full abstract on arXiv
Read the original paper