Research
A BUD You Can Count On: Efficient, Verifiable Membership Proofs
Each block changes only a small fraction of blockchain state, yet producing a state root forces validators to update an authenticated tree that spans every account and storage key — work that, in a…

- arXiv
- 2609.11251
- Published
- 2026-09-10
- Authors
- Alejandro Ranchal-Pedrosa, Cody Littley, Ben Marsh
AI summary
A BUD You Can Count On: Efficient, Verifiable Membership ProofsOverview
Research area: Blockchain state management and authenticated data structures — specifically how validators commit to blockchain state and how anyone can later verify a read (membership or exclusion proof) of that state.
Technical level: Advanced. The paper combines formal protocol definitions, soundness/completeness proofs, and systems benchmarking, though the central idea (commit to writes, not to the whole state) is explainable in plain terms.
Scope (one sentence): The paper introduces Block Update Digests (BUDs) and SuperBUDs, a scheme that lets validators keep only ordinary flat state while still serving verifiable proofs of current and historical values, including deletion.
What This Paper Is About
Each block changes only a small fraction of blockchain state, yet producing a state root forces validators to update an authenticated tree that spans every account and storage key — work that, in a standard EVM client, can cost roughly an order of magnitude more than transaction execution. The authors ask whether verifiable reads can instead be supported from the writes alone, without any global authenticated structure. Their answer is a per-block commitment to the write log, linked to each key's previous modification, plus interval summaries that prove a value stayed unchanged without checking every intervening block.
Key Contributions
-
Block Update Digests (BUDs). A Merkle commitment to a single finalized block's writes, where each record ("budlet") contains a key, its new value, the block height, and a predecessor link to the key's previous recorded modification. The predecessor link is what lets two records establish a value across an entire height range.
-
SuperBUDs and the staircase proof. Mergeable span maps summarizing which keys were modified over longer intervals and at what last height. Because the merge operation is associative, commutative, and idempotent, overlapping intervals compose cleanly, and a reader can prove an unchanged interval using at most
B(d)+2digests via base-ealigned windows. -
A prior-value record variant (BUD⁺). An optional record format that also stores the value held immediately before a block's first write to a key, so a single successor BUD supplies both the earlier value and evidence that nothing intervened — replacing the baseline's two BUD openings and one separate attestation, at the cost of larger records. The paper gives the corresponding correctness rules and a byte-cost comparison against the baseline successor strategy.
-
Proofs and an empirical comparison. Soundness against Byzantine validators and adversarial provers, and completeness for reads anchored after deployment (with full proofs in an appendix), plus an implementation comparing the base-BUD path against Merkle Patricia tries, NOMT, and QMDB on synthetic workloads and an Ethereum account-access trace.
Main Findings
-
Sparse writes are where BUDs win biggest. For 100 writes among 10⁵ keys, base-BUD replay took 0.77 μs per write versus 7.26 μs for the in-memory Merkle Patricia trie — a 9.4× difference.
-
Authentication cost barely tracks state size. A 50× increase in state size raised the measured base-BUD cost by just 1.24×.
-
QMDB's garbage collection is expensive, and BUDs avoid that cost. In paired QMDB experiments, lowering the garbage-collection activation threshold raised process CPU time by 1.3–2.7× and device bytes written by 1.6–2.4× relative to its dormant configuration, even where median latency improved. BUD authentication requires no corresponding relocation of live entries.
-
Proof payloads stay compact. In the evaluated baseline, two-digest read-layer payloads stay below 800 bytes, and warm hash-path verification takes at most 146 μs at p99.
-
Five baseline proof strategies, with different digest counts. Anchor only (1 digest, no wait), sentinel (1 digest), successor link (2 digests, waits for next write), one SuperBUD (2 digests, waits for interval end), and staircase (≤
B(d)+2digests, no wait). The prior-value successor reduces the successor strategy from 2 digests to 1 without changing its wait. -
Deletions are handled through tombstones and sentinels. A deletion writes
(⊥, n); tombstones are retained for a configured window η and then collected. After collection, a later write with predecessor−1acts as a sentinel proving absence only across[b−η, b) ∩ [H₀, b)— it does not prove the key never existed. Setting η = ∞ disables collection. -
The prior-value saving is conditional, not universal. The saving equals the omitted opening plus its attestation minus the added prior-value bytes; there is no universal break-even block size or percentage saving. For fixed-width values the added bytes do not grow with block size, while the omitted path grows logarithmically.
-
No network-timing assumption is needed. Soundness and completeness do not require a bound on message delay; completeness does require proof data to become available.
Methodology in Plain English
The authors start by defining precisely what a "read" should return: for a key k and height h, either the value written by the latest block at or before h that touched k, or the deployment-time value if no logged write exists, or "absent" including deletions. They then design commitment objects that match this definition — one per block (BUD) and one per interval (SuperBUD) — and specify exactly which openings a verifier must check for each certificate form.
To keep things practical, validators maintain ordinary flat state plus an 8-byte predecessor field per retained entry, and attest to each digest only after the relevant block is final, using a threshold of signatures from a committee. The authors prove that no adversary can make a verifier accept a wrong value, and that an honest prover can always produce a valid certificate for any query whose key was modified at or after the deployment height, provided the records and attestations are retrievable.
For evaluation, they implement the base-BUD path and compare it against Merkle Patricia tries, NOMT, and QMDB, using synthetic workloads and a trace of Ethereum account accesses, and they run paired QMDB experiments to separate garbage-collection relocation work from other effects. A multi-level window hierarchy (windows of lengths 1, 2, 4, 8, 16 with base e = 2 and depth L = 4) is benchmarked with summary maintenance enabled, and tail latencies are reported.
Why This Matters
The paper separates two things that blockchain clients have long treated as one: maintaining local storage and maintaining a global authenticated commitment. If validators can keep flat state and still answer verifiable reads, the state-root hot path stops scaling with total state size — a structural change for client design at a time when state growth is a persistent operational cost.
Real-world applications:
- Light clients and wallets verifying an account balance or storage slot without holding state or trusting an RPC provider.
- Historical and archival queries — proving what a value was at a past block, or that a key was absent, for auditing, accounting, or dispute resolution.
- Rollups and bridges reading L1 state with verifiable proofs rather than trusted oracle responses.
- Node operators and RPC providers serving proofs from archived write logs without maintaining a full authenticated tree, and avoiding garbage-collection work that relocates live entries.
Industry relevance: The comparison set is deliberately practical — Merkle Patricia tries, NOMT, QMDB, and an Ethereum account-access trace — and the paper engages directly with deployed designs (Monad, MegaETH, Solana, Sui, Guppy, stateless-client and vector-commitment proposals). That places it in the conversation about how production clients should commit to state.
Future Directions
- Window-schedule design. The paper's aligned hierarchy is one choice; it explicitly points to an appendix examining schedules that trade more summaries for more frequent short proofs, and notes that alignment can prevent a single SuperBUD from replacing the whole staircase.
- Combining BUDs with succinct proofs for old state. The authors call it "an interesting direction" to combine Guppy's succinct proofs for old state with the practicality of BUDs and SuperBUDs for frequently modified state; Guppy's present protocol leaves non-inclusion to future work, which BUDs address through deletions and bounded sentinel intervals.
- Handling historical committee compromise. The read protocol assumes the bound of
fcompromised keys holds for every historical epoch whose signatures are accepted; a deployment that cannot preserve that needs key erasure, forward-secure signatures, or a trusted later checkpoint. - Deployment and format choice. Whether to run the baseline or the prior-value format is a deployment decision with workload-dependent economics, and the authors leave the byte-cost behavior with variable-length values and the full certificate-size effects of enriched exclusion openings as practical questions.
Target Audience
Blockchain protocol researchers and client engineers working on state commitment, stateless clients, or proof-serving infrastructure will get the most from this paper, along with cryptographers interested in authenticated data structures built from per-block logs rather than global trees. Archivists, RPC and indexing teams, and technically confident readers who already understand Merkle proofs will find the certificate taxonomy and cost analysis directly actionable; readers new to the area should start with the introduction and Figure 1, which illustrate the core idea before the formal model.
Authors’ abstract
A block typically changes only a small fraction of blockchain state, yet producing a state root makes validators update an authenticated tree spanning it all. We show how to support verifiable reads from the writes alone. We introduce Block Update Digests (BUDs), that commit to a block's writes and link each key touched in that block to its previous modification. An optional prior-value record lets one successor BUD authenticate the value between modifications, replacing the…
The full abstract on arXiv