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

• URL: http://arxiv.org/abs/2606.17111v1
• Date: Mon, 15 Jun 2026 07:16:07 GMT
• Title: Fractional Verkle Trees: A Hypertree Decomposition and Verified Proof Serialization Architecture for High-Performance Blockchain State Accumulators
• Abstract summary: We present Fractional Verkle Trees (FVT), a hypertree serialization decomposition global state into N independent sub-accumulators coordinated by a Merkle commitment tree.<n> Benchmarks on Apple M1 Pro show 57% heap allocation reduction (566,760 to 242,004 bytes per 10K$), parallel insertion at 2,433 ns/op, and network-wide elimination of 4.85 PB/year across 6,000 full nodes.
• Score: 0.0
• License: http://creativecommons.org/licenses/by-nc-sa/4.0/
• 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 burden home validators. We identify four inefficiencies in the reference go-verkle implementation \cite{kaur2025goverkle, kaur2025goethereum}: (1) phantom node creation during non-existent account deletion; (2) 64-byte database keys triggering excessive LSM-tree compaction; (3) redundant memory copying in proof deserialization; (4) a Proof of Absence wire format incompatibility causing non-deterministic serialization. We present Fractional Verkle Trees (FVT), a hypertree decomposition partitioning global state into N independent sub-accumulators coordinated by a Merkle commitment tree, achieving improved cache locality, zero-lock-contention goroutine-parallel commitment computation, and faster root recomputation (91 $μ$s vs $\sim$500 ms). We address each inefficiency via existence checks, 32-byte SHA256 node references, zero-copy reference-counted buffers, and HashMap-based lexicographic deduplication. Benchmarks on Apple M1 Pro show 57\% heap allocation reduction (566,760 to 242,004 bytes per 10K proofs), parallel insertion at 2,433 ns/op, and network-wide elimination of 4.85 PB/year across 6,000 full nodes, advancing the Ethereum stateless roadmap.

Related papers

• Guppy: Efficient Light Clients via Recursive Zero-Knowledge Proofs [5.013078222067036]
  Traditional light clients rely on validators committing to the entire blockchain state at every block via a state commitment such as a Merkle tree.<n>Maintaining large and ever-growing state trees imposes a significant burden on validators and lies on the critical path of block production.<n>We present Guppy, a protocol that achieves this by having validators commit to just the verifiable state updates.
  arXiv  Detail & Related papers  (2026-09-07T20:41:39Z)
• SANE: State Anomaly Neutralization for Stable Extreme-Context Delta-Rule Models [53.86918766240095]
  Delta-Rule recurrent models maintain a fixed-size state, enabling $O(1)$ inference memory but potentially becoming unstable under extreme-context extrapolation.<n>We propose textbfState Anomaly Neutralization (SANE), which applies adaptive $tanh$ compression at chunk boundaries while preserving the intra-chunk parallel structure.
  arXiv  Detail & Related papers  (2026-08-23T10:41:07Z)
• TreeWY: Speculative Verification for Gated DeltaNet Hybrids [0.0]
  Modern open models are hybrids: layers are linear-attention (Gated DeltaNet, GDN) layers carrying a small fixed-size recurrent state instead of a growing key-value cache.<n>Today's systems snapshot the full recurrent state at every draft position for GDN layers, and those snapshots cannot be shared across branches of a draft tree.<n>We compute every draft node's output with a single triangular solve and reconstruct only the one accepted state on commit.
  arXiv  Detail & Related papers  (2026-08-21T10:31:15Z)
• vToken: Token-Level Virtualization for Reclaimable KV Caches [18.919429120080277]
  PagedAttention uses fixed-size memory blocks to reduce allocator-level fragmentation.<n>Recent KV eviction algorithms operate at a token granularity finer than block-level management.<n>We present vToken, a lightweight token-level virtualization layer that decouples logical token liveness from physical block placement.
  arXiv  Detail & Related papers  (2026-08-13T14:01:21Z)
• Bole: Efficient Tree Speculation for Hybrid-Attention Language Models [14.999732832367307]
  Hybrid-attention large language models combine full attention with recurrent linear attention to reduce long-context inference costs.<n>Existing tree-speculation systems are designed around the key--value caches of full-attention models.<n>We present Bole, a kernel--runtime co-design that enables efficient tree speculation for hybrid-attention LLMs.
  arXiv  Detail & Related papers  (2026-08-03T03:43:14Z)
• Lightweight Tamper-Evident Log Integrity Verification for IoT Edge Environments: A Merkle Tree Pipeline with Adaptive Chunking [0.4779196219827507]
  Integrity of audit logs produced by Internet of Things (IoT) devices is a prerequisite for post-incident forensics, regulatory compliance, and operational accountability.<n>This paper presents a lightweight and evaluated integrity verification pipeline that combines Merkle-tree commitments with resource-aware adaptive chunking.<n>The proposed pipeline operates in three stages: (i) resource-aware batch ingestion via adaptive chunk sizing, (ii) Merkle-tree construction with O(logn) inclusion proof generation, and (iii) deterministic single-entry verification against a trusted root anchor.
  arXiv  Detail & Related papers  (2026-04-30T09:16:43Z)
• Efficient Test-Time Inference via Deterministic Exploration of Truncated Decoding Trees [68.04613115686509]
  Self-consistency boosts inference-time performance by sampling multiple reasoning traces in parallel and voting.<n>We propose Distinct Leafion (DLE), a deterministic decoding method that treats truncated sampling as a pruned tree and systematically enumerates distinct leaves instead of sampling with replacement.<n>DLE explores higher-quality reasoning traces, yielding better performance on math, coding, and general reasoning tasks.
  arXiv  Detail & Related papers  (2026-04-22T12:42:03Z)
• WorldDB: A Vector Graph-of-Worlds Memory Engine with Ontology-Aware Write-Time Reconciliation [0.0]
  WorldDB is a memory engine built on three commitments: (i) every node is a world, (ii) nodes are content-addressed and immutable, and (iii) edges are write-time programs.<n>On LongMemEval-s (500 questions, 115k-token conversational stacks), WorldDB with Claude Opus 4.7 as answerer achieves 96.40% overall / 97.11% task-averaged accuracy.
  arXiv  Detail & Related papers  (2026-04-20T16:30:53Z)
• Goose: Anisotropic Speculation Trees for Training-Free Speculative Decoding [13.709230136542594]
  Speculative decoding accelerates large language model inference by drafting multiple candidate tokens and verifying them in a single forward pass.<n>Existing training-free methods draft from a single token source and shape their trees without distinguishing candidate quality across origins.<n>We observe that two common training-free token sources - n-gram matches copied from the input context, and statistical predictions from prior forward passes - differ dramatically in acceptance rate.<n>We prove that the number of tokens accepted per step is at least as large as that of either source used alone.
  arXiv  Detail & Related papers  (2026-04-02T13:48:42Z)
• EAGLE-Pangu: Accelerator-Safe Tree Speculative Decoding on Ascend NPUs [5.19049674298842]
  We present a system that ports tree speculative decoding to a Pangu teacher backend on Ascend NPUs.<n>Eagles-Pangu improves end-to-end decoding throughput by 1.27x on average, up to 2.46x at p99.
  arXiv  Detail & Related papers  (2026-03-09T08:30:04Z)
• Beyond Scattered Acceptance: Fast and Coherent Inference for DLMs via Longest Stable Prefixes [10.877713536966601]
  Longestahead Prefix (LSP) scheduler is a training-free and model-agnostic inference paradigm based on monolithic prefix absorption.<n>LSP evaluates token stability via a single forward pass, dynamically identifies a contiguous left-aligned block of stable predictions.<n>It snaps its boundary to natural linguistic or structural acceptances before an atomic commitment.
  arXiv  Detail & Related papers  (2026-03-05T18:25:26Z)
• dParallel: Learnable Parallel Decoding for dLLMs [77.24184219948337]
  Diffusion large language models (dLLMs) offer parallel token prediction and lower inference latency.<n>Existing open-source models still require nearly token-length decoding steps to ensure performance.<n>We introduce dParallel, a simple and effective method that unlocks the inherent parallelism of dLLMs for fast sampling.
  arXiv  Detail & Related papers  (2025-09-30T16:32:52Z)
• UniTok: A Unified Tokenizer for Visual Generation and Understanding [63.23796622553615]
  Visual generative and understanding models typically rely on distinct tokenizers to process images.<n>We introduce UniTok, a unified tokenizer featuring a novel multi-codebook quantization mechanism.<n>In terms of final performance, UniTok sets a new record of 0.38 rFID and 78.6% zero-shot accuracy on ImageNet.
  arXiv  Detail & Related papers  (2025-02-27T17:47:01Z)
• Don't Get Lost in the Trees: Streamlining LLM Reasoning by Overcoming Tree Search Exploration Pitfalls [83.89771461061903]
  Recent advancements in tree search algorithms guided by verifiers have significantly enhanced the reasoning capabilities of large language models (LLMs)<n>Recent advancements in tree search algorithms guided by verifiers have significantly enhanced the reasoning capabilities of large language models (LLMs)<n>We identify two key challenges contributing to this inefficiency: $textitover-exploration$ due to redundant states with semantically equivalent content, and $textitunder-exploration$ caused by high variance in verifier scoring.<n>We propose FETCH, a flexible, plug-and-play system compatible with various tree search algorithms.
  arXiv  Detail & Related papers  (2025-02-16T16:12:01Z)
• BTR: Binary Token Representations for Efficient Retrieval Augmented Language Models [77.0501668780182]
  Retrieval augmentation addresses many critical problems in large language models. Running retrieval-augmented language models (LMs) is slow and difficult to scale due to processing large amounts of retrieved text. We introduce binary token representations (BTR), which use 1-bit vectors to precompute every token in passages.
  arXiv  Detail & Related papers  (2023-10-02T16:48:47Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.