You've Got a BUD in Me: Authenticated Reads from Per-Block Write Logs

Alejandro Ranchal-Pedrosa; Cody Littley; Ben Marsh

Source-linked AI summary

You've Got a BUD in Me: Authenticated Reads from Per-Block Write Logs

Alejandro Ranchal-Pedrosa, Cody Littley, Ben Marsh

arXiv:2609.11251v1Sep 10, 2026cs.CRcs.DBcs.DC

TL;DR

Blockchains typically authenticate reads with a structure spanning the entire state, imposing update costs even when blocks modify little state. This paper authenticates per-block writes with BUDs, predecessor links, and hierarchical SuperBUD summaries, proving soundness and anchored completeness. Across a 50× state-size increase, the base-BUD path grew 1.24× versus 3.1× and 69.5× for trie baselines.

Problem
Historical authenticated reads typically rely on a state-spanning structure, causing validators to update paths across the state even when blocks modify only a small portion.
Method
BUDs commit per-block writes with predecessor pointers, while SuperBUDs and an exponential hierarchy summarize unchanged intervals for historical membership and exclusion proofs.
Results
Across a 50× increase in state size, the base-BUD path grows 1.24× versus 3.1× and 69.5% for the two trie baselines.
Takeaways & Limitations
Authenticated historical reads need not require every validator to maintain an authenticated copy of the entire state.
Takeaways & Limitations
Completeness applies to queries anchored by a post-deployment modification and assumes retrievable archive, attestation, and committee evidence.

Abstract

from arXiv · show

Blockchains usually pay for authenticated reads by maintaining a structure that spans the entire state. We show how validators can support historical membership and exclusion proofs by authenticating each block's writes instead. A Block Update Digest (BUD) commits a write log whose predecessor pointers link successive modifications of each key. A SuperBUD summarizes last writes over a window; an exponential hierarchy turns long unchanged intervals into short proofs. The digest count is logarithmic in the gap within the hierarchy's range, with one additional digest per top-level window beyond it. We prove soundness against adversarial provers and up to f Byzantine validators, and completeness for queries anchored by a post-deployment modification, assuming archive, attestation, and committee evidence is available. Across a 50x increase in state size, the measured base-BUD path rises by 1.24x, compared with 3.1x and 69.5x for in-memory and cache-bounded disk-backed Merkle Patricia tries. On the synthetic trace, two-digest read-layer payloads stay below 800 bytes, and warm hash-path verification takes at most 146 microseconds at p99.

1 Introduction

The paper replaces state-spanning authenticated structures with per-block write commitments and linked summaries for historical reads. It establishes the protocol’s security and evaluates its proof and scaling trade-offs.

1 Introduction: Historical reads can use per-block BUDs, predecessor links, and SuperBUDs instead of a global authenticated state structure.BUDs commit writes, predecessor pointers identify unchanged intervals, and SuperBUDs summarize the last modification in a window.
1 Introduction: The hierarchy reduces unchanged-interval proof costs to O(log d) digests within its range and O(L + d/e^L) more generally.A single window or qualifying touch transaction can shorten the proof.
1 Introduction: The protocol proves soundness against Byzantine validators and adversarial provers, and completeness for post-deployment modification anchors under archive and authentication assumptions.The implementation also measures comparisons with Merkle Patricia tries, NOMT, and QMDB.

2 Related Work

Related systems either retain a state-spanning authenticated structure, defer or delegate global authentication, or provide incremental digests without point proofs. BUDs instead combine per-block commitments with predecessor links and window summaries.

2 Related Work: QMDB supports historical reads with back-references but retains a state-spanning authenticated structure and performs reclamation on the update path.The comparison therefore includes sustained reclamation, not only root-production cost.
2 Related Work: Incremental multiset digests update independently of state size but do not provide point inclusion or exclusion proofs.Other systems defer, delegate, or retain global authentication work.
2 Related Work: BUDs combine predecessor links and window summaries to prove unchanged intervals across independently committed blocks, including activation, deletion, and attestation rules.This is presented as a different read protocol built from established ingredients.

3 Model and preliminaries

The model defines authenticated historical values and exclusions over finalized blockchain write logs, with committee-authenticated digests and explicit treatment of initialization and deletion. The protocol targets anchored queries and separates soundness from certificate availability.

3 Model and preliminaries: The reference committee configuration uses n_ρ = 3f + 1 and τ = 2f + 1, while protocol soundness and honest-only availability require f < τ ≤ n_ρ − f.Quorum-intersection uniqueness is stronger than the soundness argument requires.
3 Model and preliminaries: Committee authentication requires the verifier to validate the committee selected by the canonical chain, with stronger key-protection measures needed after historical-key compromise.The latter measures include key erasure, forward-secure signatures, or checkpoint exclusion.
3 Model and preliminaries: Canonical positional Merkle roots support inclusion and adjacent-position exclusion proofs over key-sorted entries.Adjacency prevents an omitted key from appearing between nonconsecutive opened leaves.
3 Model and preliminaries: The canonical write log resolves repeated writes within a block by last-write-wins and records deletions using ⊥.Each honest validator derives the same finalized log.
3 Model and preliminaries: The uninit predecessor marker distinguishes an unactivated key from genuine absence, preventing unsupported backward claims before its first modification.The read result ∅ denotes absence, whereas ⊥ denotes deletion.
3 Model and preliminaries: Completeness is guaranteed for queries with at least one modification at or below the requested height once records, attestations, and committee evidence are retrievable.Soundness requires accepted certificates to return the canonical value except with negligible probability.

4 The Protocol: BUDs and SuperBUDs

BUDs commit block write logs, while SuperBUDs summarize final modifications over aligned windows; predecessor pointers and hierarchical span maps turn these commitments into historical membership and exclusion proofs. The design trades maintenance and waiting time against proof size.

4 The Protocol: BUDs and SuperBUDs: A BUD commits each block’s key-sorted write records, including values, heights, and predecessor pointers, while validators attest its root after finality.Canonical exclusion proofs use boundary, empty-root, or adjacent-position forms.
4 The Protocol: BUDs and SuperBUDs: A numeric predecessor proves that the value written at height a remains unchanged throughout [a, b) until the next modification at b.Deletion uses tombstones so later writes preserve the backward link.
4 The Protocol: BUDs and SuperBUDs: The −1 sentinel certifies bounded absence only within the retention window, whereas uninit makes no claim before a key’s first post-deployment modification.Retention limits sentinel reach but not completeness for archived modification anchors.
4 The Protocol: BUDs and SuperBUDs: SuperBUDs commit each key’s final modification within a window, allowing an opening to clear the window above that modification or an exclusion to clear the whole window.Parent span maps merge child maps by retaining the greater height for each key.
4 The Protocol: BUDs and SuperBUDs: The aligned exponential hierarchy uses level-0 BUDs and higher-level maps formed by pointwise maxima over e children.Each write enters at most one map per level, with maintenance below 1/(e − 1) digests per block beyond BUDs.
4 The Protocol: BUDs and SuperBUDs: For an anchor gap d, the staircase clears the interval with at most B(d) exclusions, and every used window is closed by the query height.This makes its attestations retrievable under the stated bounded-delay assumption.

5 Correctness

The correctness results establish soundness for authenticated historical reads and completeness for anchored queries under explicit evidence and committee assumptions.

5 Correctness: Predecessor records identify the latest prior modification, certify bounded absence for sentinel records, and leave uninit records without backward claims.These cases determine how anchors, successors, sentinels, and activations are interpreted.
5 Correctness: Soundness holds against adversarial provers and up to f Byzantine validators when accepted digests include honest signers and canonical openings.The proof uses τ > f, authenticated-map binding, predecessor semantics, and interval coverage.
5 Correctness: Completeness guarantees a certificate for every query in Q by height h + λ under archive, attestation, committee, and finite-delay assumptions.Outside Q, activation records do not prove backward history, while sentinels cover only η blocks.
5 Correctness: Authenticated construction scales with write volume: BUD creation sorts w_n records and hashes O(w_n) entries, while hierarchy maintenance adds O(L) amortized work per write.Flat-state access can still depend on database cache and state size N.
5 Correctness: A certificate uses O(log w_a) anchor hashes, O(log w_b) successor hashes, and span-map paths for covered intervals.Complete wire accounting includes additional implementation details and evidence components.

6 Evaluation

The evaluation finds that BUD commitment cost is relatively insensitive to state size, while certificate size, availability, and maintenance depend on hierarchy design and workload history.

6 Evaluation: A 50× state-size increase raises BUD time 1.24×, versus 3.1× for the in-memory trie and 69.5× for the cache-capped disk trie.BUD rises from 1.19 to 1.47 ms; the residual increase is attributed to flat-state lookup.
6 Evaluation: Forced QMDB reclamation increases retained database-file growth from 2.7 GiB to 7.2 GiB, or 2.6×, while latency differences remain within between-run variation.Behavior near the default gate remains unmeasured.
6 Evaluation: Two-digest synthetic read-layer payloads remain below 800 bytes, while warm hash-path verification reaches at most 146 µs at p99.S3 remains near 453 bytes; S5 grows logarithmically to about 12 kB, excluding attestation and committee evidence.
6 Evaluation: At d = 1, S3 is cheapest for 84.2% of uniform-key synthetic queries but 28.4% on the Ethereum trace, reflecting recurrence-sensitive availability.By d = 64, mean S5 cover is about 5.5 windows in both workloads.
6 Evaluation: Moving from (e, L) = (2, 12) to (8, 4) lowers extra digests per block from 0.9998 to 0.1428 but increases mean cover from 4.5 to 8.5 windows.S4 availability falls by about ten percentage points in this comparison.

7 Conclusion

The paper concludes that authenticated historical reads can be built from independently attested write commitments rather than a validator-maintained authenticated structure spanning all state.

7 Conclusion: BUDs authenticate writes, while predecessor links and SuperBUDs authenticate unchanged intervals across blocks.The resulting protocol supports historical membership and exclusion proofs.
7 Conclusion: Construction work is tied to write volume, with proof size and waiting time exposed as an explicit hierarchy trade-off.Validators execute against flat state and attest changes; untrusted archives assemble proofs.
7 Conclusion: Unlike incremental multiset digests, BUDs provide point inclusion and exclusion proofs, while unlike global-root designs they avoid retaining a state-wide authenticated structure.The comparison includes deferred-root, access-list, stateless, and historical-log approaches.
7 Conclusion: SuperBUD hierarchies combine history-tree-like authentication, exponential-histogram bucketing, and staggered-window techniques.These connections describe the construction’s relationship to prior primitives.

B Encodings and protocol derivations

The encodings and derivations define canonical authenticated maps, query-record semantics, and an aligned exponential hierarchy that decomposes historical gaps into attested windows.

B Encodings and protocol derivations: Canonical positional Merkle commitments bind object type, index, leaf count, positions, padding, and tree shape.Inclusion opens one position; exclusion opens an empty root, boundary, or adjacent bracketing positions.
B Encodings and protocol derivations: Query records distinguish ordinary anchors, Next extensions, bounded sentinels, and uninit activations according to predecessor and target heights.An uninit record activates a key but makes no claim below its own height.
B Encodings and protocol derivations: SuperBUD union merges retain the maximum last-modification height for each key, allowing overlapping child maps to be combined and re-merklized.Roots alone do not suffice because validators must merge entries before constructing the parent commitment.
B Encodings and protocol derivations: Aligned level-(ℓ + 1) windows are disjoint unions of e level-ℓ children, yielding (1 − e^-L)/(e − 1) additional digests per block.Each write is final for its key in at most one window per level.
B Encodings and protocol derivations: A greedy base-e decomposition of the gap clears the interval after the anchor and gives the exclusion bound with at most B(d) + 2 named digests.The level containing the anchor first clears its suffix, after which aligned windows cover the remainder.
B Encodings and protocol derivations: Threshold conditions separate honest inclusion, Byzantine-independent production, and honest quorum intersection, with n_ρ ≥ 3f + 1 sufficient for all three.Soundness plus honest-only availability needs only n_ρ ≥ 2f + 1.

C.1 Soundness and completeness

The read system is sound against adversarial provers and Byzantine validators, and complete for anchored queries when required archive, attestation, and committee evidence is available.

Accepted inclusion and exclusion openings bind to canonical key-sorted write-log entries, so covered intervals cannot hide modifications.
Theorem C3 establishes soundness for the Section 4.3 read system.
For ordinary anchors, predecessor links and cleared windows determine the last modification and force the returned value or tombstone result.
Completeness excludes queries with no post-deployment modification anchor, while finite retention limits old sentinel-based absence proofs outside Q.
Theorem C4 guarantees a certificate for every anchored query in Q by height h + λ under finite-delay availability and authentication assumptions.
The verifier relies on independent state and committee trust anchors, authenticated historical epochs, and retrievable archive objects rather than a standalone BUD state root.

G Window schedule

The schedule comparison spans fixed-size, aligned, staggered, and per-block sliding windows, trading digest and construction costs against proof coverage, waiting time, and payload structure.

Window placements: Figure 5 compares fixed-size, aligned, staggered, and every-height window placements, with dark boxes marking BUDs.
Alternative schedules: A fixed SuperBUD size adds only 1/m digests per block, but uncovered gaps require BUDs and can produce a linear cover in d.
Alternative schedules: For φ ≥2 and d ≤(e −⌈e/φ⌉)η/e, a committed window of size less than e2 e−qd covers the interval and closes fewer than that many blocks after h.
Alternative schedules: Two-digest certificates are available for per-block sliding after ramp-up, but its worst-case build work is Θ(wη) per block.
Choosing the schedules: The φ-phase schedule trades maintenance cost against proof coverage: φ = 1 is cheapest, while φ ≥2 bounds coverage gaps with windows of size O(d).The aligned hierarchy is the main construction; full striding uses all phases, while intermediate schedules commit φ phases.
Experimental scope: The prototype measures construction cost and proof shape, but does not implement activation, end-to-end attestation verification, or the full formal protocol.
Experimental scope: The Ethereum trace uses dense identifiers and fixed-width records, so its certificate bytes represent hash-path costs rather than production wire sizes.

H.2 Certificate costs

Certificate payloads remain small for short strategies, while S5 grows logarithmically with staleness; Ethereum’s larger marked-account sets produce deeper BUD paths.

219–227 bytes for S1/S2 and 452–454 bytes for S3 keep short-strategy synthetic payloads compact.
S4 grows from 515 to 790 bytes, while S5 increases logarithmically from 901 to 11,984 bytes as staleness rises.
Warm hash-path verification reaches at most 146 µs at p99, while S3 and S4 remain below the 2,087-byte prototype-MPT inclusion proof.
677–710 bytes for S3 on Ethereum reflects deeper BUD paths from larger per-block marked-account sets.
At d = 64, mean S5 cover is approximately 5.5 windows in both workloads and under both sampling rules.

H.3 Strategy availability

Strategy availability depends strongly on write recurrence and staleness: S3 favors recent successors, S4 covers successor-poor keys, and hierarchy parameters govern longer intervals.

S3 serves most synthetic queries at d = 1, whereas S4 availability falls from 90.6% to 32.9% under event sampling and from 99.9% to 42.9% under uniform-key sampling.
50.4% of 1.68 million marked Ethereum accounts appear only once, creating a much larger population without observed successors.
Under uniform-key Ethereum sampling, S4 is the most common strategy for every sampled d < η and retains a majority through d = 2,048.
By d = 64, mean S5 cover is about 5.5 windows in both workloads, so history changes strategy availability more than cover size at fixed staleness.
H.5 Skew sensitivity: Across skew settings, mean S5 size changes by 35% overall but only 5.6% for d ∈[64, 128), while mean cover stays between 5.98 and 6.01 windows.
Schedule comparison: The schedule comparison evaluates aligned, full-striding, and m = 64 SuperBUD schedules, while per-block sliding has worst-case build work Θ(wη).

H.7 QMDB reclamation under forced activation

Forced QMDB reclamation shows similar measured latency but substantially greater database-file growth, while the experiment does not establish behavior near the default gate.

The base-BUD path measures 1.1 µs per write but excludes SuperBUD maintenance, attestation, and signing, so it is not functionally matched to QMDB.
48.7 µs per write with active reclamation falls within the inactive configuration’s 5.7% between-run spread, with overlapping per-block p99.9 ranges.
The forced-reclamation setting lowers QMDB’s threshold to 5·10^5 entries per shard, while the default gate remains inactive at N = 10^7.
7.2 GiB versus 2.7 GiB of database-file growth accompanies active versus inactive reclamation, ending at 8.6 GiB versus 4.0 GiB.
Heavy per-block tails occur in both QMDB configurations and the BUD replay, so these data do not attribute tail latency to reclamation.
The open boundary is sustained reclamation near QMDB’s default live-entry gate, where latency and storage behavior may differ.