Block Update Digests: Membership Proofs Without a Global State Tree

Authors: Cody Littley, Alejandro Ranchal-Pedrosa (@alranpe), Omar Garcia — Sei Labs

TL;DR: BUDs are a membership proof scheme that scales with per-block write volume rather than total state size, without requiring a global state trie on the critical path.

Motivation

Membership proofs (a.k.a. state proofs, as served by eth_getProof) allow offchain observers to cryptographically verify onchain values without trusting a third party. The standard approach builds a Merkle trie over the entire state, so that a signature on the root hash, together with a Merkle path, proves inclusion or exclusion of any key.

The cost of this approach scales with total state size: every block must update a tree whose leaves span millions of accounts and storage slots. For high-throughput EVM-equivalent chains the overhead becomes a prohibitive bottleneck, both in raw computation and in the database layout it forces. Even Ethereum L1 carries significant complexity and I/O cost from maintaining the global state trie.

We propose Block Update Digests (BUDs), an incremental authenticated data structure that decouples state commitment cost from total state size, scaling it instead with per-block update volume. BUDs compose with a hierarchical digest layer we call SuperBUDs and with on-demand touch transactions to cover the full spectrum of latency, proof size, and cost requirements.

Differences with Binary State Trees and Verkle Trees

The Ethereum L1 roadmap has converged on binary state trees (EIP-7864) as the long-term state commitment mechanism, with a path toward O(1)O(1) SNARK verification of state proofs. For chains committed to maintaining a global authenticated data structure on the consensus-critical path, these proposals represent a clear improvement over the current MPT. BUDs address a different question entirely and are complementary, not competing.

BUDs address a different architectural question: should the authenticated data structure live on the consensus-critical path at all?

A global state tree, regardless of how efficiently it is implemented (MPT, binary, Verkle), requires every validator to maintain and update a trie-shaped data structure during block execution. The trie constrains database layout, introduces I/O amplification proportional to tree depth on every write, and entangles execution throughput with state commitment cost. Even a perfect binary trie with O(\log n)O(logn) paths imposes O(w \cdot \log n)O(w⋅logn) hash computations per block for ww state writes, and the database must store intermediate nodes in a trie-friendly layout.

BUDs take the position that for high-throughput execution environments, the trie is the wrong abstraction to place on the validator’s critical path. Instead, validators produce a lightweight per-block digest (cost proportional to the write set alone, with no dependence on total state size) and the full proof infrastructure is delegated to archive nodes. The state itself can live in whatever flat key-value store layout is optimal for raw execution speed, with no trie-shaped I/O constraints.

This is an architectural choice, not a temporary workaround. Chains that adopt BUDs are not “waiting to migrate to a better trie”; they are choosing not to maintain a global trie on the critical path at all.

Note that the SNARK verification argument is symmetric: a BUD Merkle proof can also be SNARK-verified, and the circuit is simpler because the BUD tree is smaller (proportional to the block write set, not the full state). If the endgame is SNARK-verified state proofs for cross-chain bridges and light clients, both approaches get there; the question is purely about the cost imposed on validators during block production.

Core Idea

BUDs

A BUD is a small Merkle tree built over the changes produced by a single block (or, more generally, by any contiguous window of kk blocks). Each leaf records:

1. the key,
2. its new value,
3. the current block number, and
4. the previous block number at which the key was last modified.

Field (4) is the critical addition: it threads a per-key modification chain through the BUD sequence, so that two adjacent BUD entries for the same key can attest that nothing changed in between. To support this, each entry in the key-value store carries 8 extra bytes of metadata recording the block height of its last modification (plus 1 byte for a serialization version field).

Figure 1: Structure of a BUD Merkle tree. Each leaf records (key, new value, current block #, previous block # modified). The BUD hash is signed by validators with quorum > (n+f)/2 stake.

BUD tree diagram1600×815 127 KB

Validators sign BUD hashes and aggregate signatures in the usual way (quorum of > (n+f)/2>(n+f)/2 stake, where at most ff is adversarial). BUDs are then streamed to archive nodes for long-term storage and proof serving.

Because the tree is built only over the keys touched in a block, its construction cost is proportional to the block’s write set, not to the global state size. A block that modifies 10,000 keys builds a tree over 10,000 leaves regardless of whether the total state contains 100 million entries.

SuperBUDs

A single BUD proves a key’s value at the block where it was modified, but a light client querying the current value of a key last written dd blocks ago would naively need to check dd BUDs for exclusion. SuperBUDs compress this linear scan into a logarithmic one.

A level-\ellℓ SuperBUD spans e^\elleℓ blocks (for a configurable base ee; we use e = 2e=2 as a concrete instantiation) and is produced at block heights that are multiples of e^\elleℓ. Internally, a SuperBUD is a Merkle trie mapping each key touched within its span to the latest block number at which it was modified. Two adjacent SuperBUDs at the same level can be merged into a single SuperBUD at the next level by taking the union of their key sets and, for keys appearing in both, keeping only the more recent block number. This merge is a single O(n)O(n) coordinated traversal of the two sorted tries.

A SuperBUD proof for a given key shows either (a) the highest block within the span at which the key was modified, or (b) that the key was not modified within the span at all. Combined with a BUD proof at the identified block, this yields a full membership proof.

Figure 2: The SuperBUD hierarchy over blocks B0–B11 with base e=2e=2. Level-1 SuperBUDs span 2 blocks, level-2 span 4, level-3 span 8. Adjacent SuperBUDs at the same level merge into the next level via a single O(n)O(n) traversal.

SuperBUD hierarchy timeline1380×340 28.2 KB

Latency and proof size. If the last modification was dd blocks ago, the client needs a SuperBUD at level \lceil \log_e d \rceil⌈loged⌉. In the worst case, the client waits up to e^{\lceil \log_e d \rceil}e⌈loged⌉ blocks for the next aligned window at that level to close. The wait is therefore worst-case linear in staleness, but what the hierarchy buys is proof compactness: a logarithmic number of digest lookups and a constant number of Merkle paths, rather than a linear chain of per-block exclusion proofs.

Touch Transactions

Where SuperBUDs trade latency for proof compactness without on-chain cost, touch transactions offer the inverse trade-off: pay a small on-chain fee to get an immediate BUD proof at the current block, regardless of how stale the key is.

A touch transaction does not modify a key’s value; it only updates the “last modified” metadata and produces an entry in the current block’s BUD. This is analogous to the touch command in a Unix shell: refresh the timestamp without altering content. Touch transactions are priced according to the chain’s existing resource metering (per unit of state access and metadata write), so they introduce no new DoS surface beyond what the fee schedule already accounts for.

Together, SuperBUDs and touch transactions span the full latency/cost design space: cost-sensitive users wait for SuperBUDs; latency-sensitive users touch.

Proof Strategies

BUDs and SuperBUDs compose into several proof strategies, each with different trade-offs.

Single BUD proof. If the queried block height coincides with a modification (or a touch), one BUD proof suffices. Extremely compact, but only available at modification points.

Double BUD proof. Two consecutive BUD proofs for the same key, where the second’s “previous block modified” field points to the first, prove the value at any block in between. The per-key modification chain guarantees no intermediate changes were missed.

BUD + SuperBUD. A BUD proof at the last modification combined with a SuperBUD whose span covers both that modification and the target block. The SuperBUD attests that no later modification exists within its span. Compact and cheap, but with moderate latency for recently modified entries and higher latency for stale ones.

Figure 3: Strategy BUD + SuperBUD. A BUD proof at block B2 combined with a SuperBUD spanning A–C proves the value of key K at any block up to the SuperBUD’s upper boundary, without a touch transaction.

BUD + SuperBUD strategy diagram1441×940 64.8 KB

BUD + multiple SuperBUDs. For lower latency without a touch transaction, chain several adjacent SuperBUDs to cover the gap. Less compact (proof size grows with staleness) but avoids on-chain cost.

First-modification proof. If a BUD entry has “previous block modified” equal to -1−1, it attests that the key did not exist before that block (back to a configurable proof cutoff). Useful for exclusion proofs and for keys that were recently created.

Design Choices and Flexibility

The construction is deliberately modular. We highlight the main axes of flexibility:

BUD granularity. We present the 1:1 case (one BUD per block) as the default, but BUDs can equally be produced every kk blocks over the preceding window. This amortizes signing overhead at the cost of slightly coarser proofs.

SuperBUD base and schedule. The base ee of the hierarchy controls the branching factor. With e = 2e=2, levels double in span (2, 4, 8, 16, …) and the maximum merge depth LL determines the maximum proof age: the system supports proofs for any block within the last e^LeL blocks. Larger ee reduces the number of levels but increases the worst-case wait. The production schedule (aligned to multiples of e^\elleℓ) can be offset or staggered if the chain’s finality cadence makes certain boundaries more natural.

Max proof age and tombstones. Deleting a key must not destroy its modification chain. Instead of removing the entry, the state writes a tombstone (nil value, preserved “last modified” metadata). A configurable max proof age (e.g. days or months of blocks) bounds how long tombstones persist: once a tombstone is older than the cutoff it is garbage collected. Proofs generated before the cutoff remain valid and verifiable indefinitely; what expires is the ability to generate new proofs for very old blocks.

Exclusion proofs. SuperBUDs alone cannot prove exclusion because they do not assert anything about the pre-existing state of a key. A full exclusion proof requires a BUD entry (possibly created via a touch transaction on a non-existent key, which produces a tombstone). This is a deliberate design trade-off: the edge case of proving the absence of a key that has never existed and has no tombstone is sufficiently niche that requiring a touch transaction is acceptable.

Comparison with Global State Trees

The core trade-off: a global trie gives immediate proofs for any key at any recent block, at the cost of entangling execution with trie maintenance. BUDs give immediate proofs only at modification points (or on-demand via touch), but free the execution layer from any trie-shaped constraint.

Target and Next Steps

BUDs are a permanent architectural alternative to maintaining a global state tree on the consensus-critical path. They are not a transitional mechanism for chains waiting to adopt a better trie, nor a complement layered on top of an existing trie. Rather, BUDs are designed for chains that choose not to maintain a global authenticated data structure in the validator’s critical path at all, delegating proof infrastructure to archive nodes in exchange for unconstrained execution throughput.

The primary audience is high-throughput EVM-equivalent L1s and rollups where state trie maintenance has become or is becoming the execution bottleneck. For Ethereum L1, where the binary tree migration (EIP-7864) is already underway, BUDs are not a natural fit. For chains designing their state commitment strategy from scratch, or reconsidering it as state grows, BUDs offer a fundamentally different scaling path.

We are preparing an informational EIP to formalize the construction. We welcome discussion on the design, parameter choices, and potential adoption paths.

The full RFC is available for review; we will link it once the EIP draft is published.

Open Questions

We welcome discussion on the following:

1. Parameter choices: What values of base ee and max proof age are appropriate for high-throughput chains in practice? Is e=2e=2 the right default, or would a larger branching factor better suit typical key age distributions?
2. Exclusion proof edge cases: The requirement for a touch transaction to prove absence of a key that has never existed is a deliberate trade-off. Is this acceptable in practice, or does it need a different solution?
3. Archive node incentives: BUDs delegate proof serving entirely to archive nodes. What incentive structures ensure archive nodes remain available and honest over long time horizons?
4. Adoption path: For chains already running a global state trie, what is the least disruptive migration path toward BUDs?