You’ve Got a BUD in Me: Authenticated Reads from Per-Block Write Logs Alejandro Ranchal-Pedrosa1 , Cody Littley1 , and Ben Marsh1,2 1
arXiv:2609.11251v1 [cs.CR] 10 Sep 2026
2
Sei Labs University of Portsmouth
Abstract. 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 50× increase in state size, the measured base-BUD path rises by 1.24×, compared with 3.1× and 69.5× 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 µs at p99.
1
Introduction
A blockchain validator typically writes to a small part of the state, then updates an authenticated structure spanning every account and storage key. That structure makes reads easy to prove: a signed root and a path establish a key’s value. It also makes every validator pay for those proofs during execution. Each of a block’s w writes changes an O(log N ) path through N state entries, with database accesses shaped by the tree. In a standard EVM client, state-root computation can cost roughly an order of magnitude more than transaction execution [21]. Systems address this cost by deferring the root, assigning it to specialized nodes, or replacing it with an incremental digest that cannot answer point queries. QMDB offers a particularly relevant alternative: it makes authenticated storage efficient and supports historical reads, but still maintains a state-spanning structure, including reclamation work on the update path [36]. This paper asks whether historical point proofs require that global authenticated structure at all. Our answer starts with the write log. A Block Update Digest (BUD) commits one block’s key-sorted writes, adding the height of each key’s previous modification. If a write at height b points back to a, the key was unchanged between them: the
2
A. Ranchal-Pedrosa et al.
record at a proves its value throughout [a, b). Tombstones preserve these links across deletion. When no later write is available, a SuperBUD summarizes the last modification of every key written in a window. An aligned exponential hierarchy combines those summaries into a proof that the value remained unchanged for d blocks, using O(log d) attested digests when d < eL+1 and O(L + d/eL ) in general. A suitable single window or a qualifying touch transaction can shorten that proof. Validators retain ordinary flat state with one 8-byte metadata field per entry, build a Merkle tree over each block’s writes, and form larger windows by linear merges. Untrusted archives retain these committed objects and serve historical proofs. The cost of authenticated construction follows write volume; ordinary state access still depends on the database and its cache. This separation motivates two QMDB comparisons: short-run update cost and sustained reclamation (Sections 6.2 and H.7). Contributions. We give a read protocol that combines per-block commitments, predecessor records, and mergeable window summaries into historical membership and exclusion proofs (Sections 3 and 4). We characterize how the window schedule trades maintenance cost against proof size and waiting time (Sections 4 and 4.3). We prove soundness against Byzantine validators and adversarial provers, and completeness for queries with a post-deployment modification anchor under the stated archive, attestation, and committee assumptions (Section 5). Our implementation compares the base-BUD path with Merkle Patricia tries, NOMT, and QMDB, and measures the hierarchy and proof trade-offs on synthetic workloads and an Ethereum account-access trace (Section 6).
2
Related Work
QMDB is closest in historical functionality: its authenticated append-only storage uses back-references to trace a key across versions [36]. Those links remain under a state-spanning authenticated structure; BUD links cross independently attested per-block roots. QMDB also reclaims storage by relocating live entries on the update path. This makes reclamation part of the comparison, beyond the cost of producing a root. Our sustained experiment finds no distinguishable latency penalty from forced reclamation at N = 107 , but records 2.6× larger databasefile growth; behavior near the much higher default eligibility threshold remains unmeasured (Section H.7). NOMT and LVMT also reduce merklization cost while retaining a global authenticated structure [15,19,28]. Other systems defer or relocate authentication work. Monad and Ethereum defer a global root, while MegaETH delegates its maintenance [23,24,21]. Solana and Sui instead use incremental multiset digests that update independently of state size but do not provide point inclusion or exclusion proofs [26,25,30,2,18]. Ethereum’s post-execution access-list proposal commits a per-block list, but retains the global root and requires revealing the list to prove one entry [33].
You’ve Got a BUD in Me
3
Stateless-client and vector-commitment designs retain a global dictionary commitment and move witnesses between participants [13,4,9,32,14,29,17]; witness churn remains fundamental [10]. Authenticated logs and persistent dictionaries support historical membership by committing snapshots or cumulative history [22,11,1,27]. BUDs combine established ingredients into a different read protocol: predecessor links and window summaries prove unchanged intervals across independent block commitments, with explicit rules for activation, deletion, and attestation. Its contribution is this protocol and its maintenance–proof-size– waiting trade-off. Additional comparisons appear in Section A.
3
Model and preliminaries
Adversary, network, and cryptography. A probabilistic polynomial-time adversary controls at most f members of every applicable digest-signing committee, learns their complete state, and may deviate arbitrarily on their behalf. Within committee epoch ρ, write Πρ for the committee and nρ = |Πρ |. We use the familiar committee choice nρ = 3f + 1 and attestation threshold τ = 2f + 1 as the reference configuration. The read protocol itself needs only f < τ ≤ nρ − f : every accepted digest has an honest signer, and honest signers can produce it without Byzantine participation. These conditions apply after consensus finality; they do not replace the underlying consensus assumptions (Sections B.4 and 4.3). The network is asynchronous: messages may be delayed arbitrarily, while consensus finalizes a common chain. No timing assumption is used for soundness. Any bound involving an attestation lag λ is conditional on the explicit availability assumption of Section 4.3; pure asynchrony does not imply such a bound. All protocol objects use an injective, prefix-free canonical byte encoding enc. Integer widths and signedness, key and value lengths, and the encodings of ⊥, −1, and uninit are fixed by the protocol. The hash function H is collision resistant. The signature scheme is existentially unforgeable under chosen-message attack in the multi-user setting. If attestations use aggregation, committee public keys are validated at registration and the aggregate scheme is rogue-key secure (for example through proof-of-possession registration); verifying the individual signatures is also sufficient. Committee authentication. The verifier starts from a trusted chain checkpoint C and uses a chain-specific predicate AuthCom(C, ρ, Πρ , χρ ) to check committee evidence χρ , such as authenticated committee transitions or a consensus lightclient proof. We assume the predicate accepts only the committee selected by the canonical chain descending from C. A fixed trusted committee is the special case in which ρ never changes and χρ is empty. The per-epoch corruption bound and signature assumption apply for every epoch whose signatures the verifier accepts. A deployment exposed to later compromise of historical signing keys must additionally use key erasure, signatures with forward security, or a checkpoint policy that excludes those epochs.
4
A. Ranchal-Pedrosa et al.
Authenticated maps. Both objects use canonical positional Merkle roots over key-sorted entries. Their domain-separated commitment MRT,I (z) binds the object type and index, leaf count, every position, padding, and tree shape. Inclusion opens one position. Exclusion opens the empty root, a boundary, or two adjacent positions bracketing the query; all openings share one root and leaf count. Adjacency prevents an omission between nonconsecutive leaves. The byte-level definition and all four forms appear in Section B.1. Blockchain, state, and write logs. Consensus finalizes a common totally ordered sequence of blocks at heights n = 1, 2, . . ., and honest validators execute each of them deterministically against a replicated key-value state, writing and possibly deleting a set of keys. That set, after resolving repeated writes to the same key by intra-block last-write-wins, is the canonical write log of block n, ∆n = {(k1 , v1 ), . . . , (kwn , vwn )}, over a key space K and a value space V ∪ {⊥} where ⊥ denotes deletion. Each key appears at most once in ∆n , every honest validator derives the same log, and we write keys(∆n ) for its keys and wn = |∆n |. Fix a deployment origin H0 , the height at which authenticated logging begins, and let σ0 be the canonical state immediately before block H0 . The modification set is Mod(k) = {n ≥ H0 : k ∈ keys(∆n )}. Write out(v) = v unless v = ⊥, in which case out(v) = ∅. For h ≥ H0 , the canonical value is
val(k, h) =
out(v), σ0 (k), ∅,
if a = max(Mod(k) ∩ [H0 , h]) exists and (k, v) ∈ ∆a , if no such a exists and k ∈ dom(σ0 ),
(1)
otherwise.
The notation separates a deleted value from missing history. The value marker ⊥ means deletion; the read result ∅ means that the key is absent. The predecessor field instead holds a height or one of two markers: −1 for an absent entry, and uninit for a key present in σ0 with no recorded modification yet. We call the latter key unactivated. Its first record can anchor reads from its own height onward, but cannot prove earlier absence. Keeping uninit distinct from −1 prevents that false claim. Honest-validator state integrity. At H0 , every honest validator begins from the same canonical application state and protocol metadata. A validator that joins a later signing committee first obtains the canonical application state, predecessor metadata, garbage collection state, and required open hierarchy state through the chain’s assumed sound state-sync or checkpoint procedure. Thereafter, honest validators apply finalized state transitions, activation, and garbage collection deterministically. The adversary cannot corrupt an honest validator’s memory or persistent storage except through those transitions. Thus the flat state lacks a public state-wide authenticated root, but is not assumed immune to arbitrary local corruption. A validator with corrupted state or predecessor metadata is Byzantine for the corresponding execution.
You’ve Got a BUD in Me
5
Problem statement. A membership claim says val(k, h) = v ∈ V; an exclusion claim says val(k, h) = ∅. If the last modification of k at or below h wrote ⊥, that record proves exclusion however old it is. If Mod(k) ∩ [H0 , h] = ∅, there is no record at or below h: the key may retain a value from σ0 , or it may have been absent throughout. A later record with predecessor −1 can certify the latter case only over its bounded sentinel interval, while a record with predecessor uninit deliberately makes no backward claim. We therefore guarantee completeness for the anchored query domain Q = { (k, h) : Mod(k) ∩ [H0 , h] ̸= ∅ }, while allowing sentinel certificates for some additional exclusion queries. A read system lets anyone learn val(k, h) without holding the state and without trusting whoever answers. An untrusted prover, holding the write logs and validators’ attestations, runs Prove(k, h) and returns a claimed value y ∈ V ∪ {∅} and a certificate π; a verifier, holding no application state but able to authenticate the committee, runs Verify(k, h, y, π). We separate cryptographic correctness from availability. The protocol is a read system if it satisfies the following properties. First, soundness: for every adversary controlling at most f members of each applicable committee, the probability of producing (k, h, y, π) such that Verify accepts and y = ̸ val(k, h) is negligible. Second, completeness: for every (k, h) ∈ Q, once the required records, span maps, attestations, and committee evidence are retrievable and every used epoch can be authenticated, an honest prover produces an accepting certificate with y = val(k, h). The assumptions needed for a bounded delay appear in Section 5.1.
4
The Protocol: BUDs and SuperBUDs
Validators keep the replicated state as a flat map with no public state-wide authenticated root, subject to the local-integrity assumption of Section 3. An activated entry stores (v, last(k)), where last(k) is its most recent modification height, while an unactivated entry stores (v, uninit). The implementation may encode uninit as a reserved value of the same 8-byte field. Two digest types do the work: a BUD commits one block’s write log, and a SuperBUD summarizes modifications across several blocks. An optional touch transaction creates a fresh BUD record on demand. The construction below specifies how validators build and attest these objects and how a verifier combines their paths into a historical read. Figure 1 connects the record format to the hierarchy; Table 2 collects the notation. 4.1
BUDs and predecessor records
While executing block n, the client processes each (k, v) ∈ ∆n in canonical order. If the entry is activated, it sets p := last(k). If the entry is present but unactivated, it sets p := uninit. Only if no entry is present does it set p := −1. It then emits (k, v, n, p) and writes (v, n) at k. Thus p = −1 certifies genuine pre-state absence, whereas p = uninit records the first post-deployment modification of a key whose
6
A. Ranchal-Pedrosa et al.
earlier history is not authenticated.3 Since ∆n resolves repeated writes by lastwrite-wins, a key modified several times inside block n yields exactly one record. When its predecessor field is numeric, that field names the last block strictly below n that modified k; an implementation that applies writes as it executes must therefore read last(k) before the block’s first write to k, or canonicalize the log before emitting records. A deletion writes (⊥, n) and keeps the entry as a tombstone, so a key deleted and later rewritten still carries a pointer across the deletion. An entry thus carries one extra field, a block height, which our implementation stores in 8 bytes. Garbage collection runs deterministically after the writes of a block and never removes an entry written in that block. Sort the canonical records by key and write ri = (ki , vi , n, pi ). The block update digest of height n is Un = MRBUD,n (r1 , . . . , rwn ). Validators attest Un once block n is final (Section 4.3). An inclusion proof opens a position containing (k, v, n, p); the verifier checks both the key and the embedded height against the query and BUD index. An exclusion proof uses one of the four canonical authenticated-map forms above. In particular, an interior exclusion opens positions i and i + 1, rather than merely two leaves whose keys surround k. The boundary forms handle keys below the first or above the last record, and the distinguished empty root handles wn = 0. A numeric fourth field turns these per-block statements into interval statements. If the record at height b carries the numeric pointer a, nothing touched k in between, so the value written at a is still the value at every height in [a, b). The records of an activated key therefore form a backward-linked chain across the digest sequence. Garbage collection keeps deleted entries around for a while. A tombstone written at height m survives until the chain reaches m + η, where the retention window η is a governance parameter; live values are never collected. An absent entry means that the key was absent from σ0 and has not been modified since H0 , or that it was deleted at least η blocks ago and untouched since. Its value is therefore ∅ throughout the last η heights, clipped at H0 . Once the entry for k is gone, a later write at height b emits p = −1 even though k may have been written long before, so the sentinel reaches down to b − η. Both collection and the window are optional (Section D). Retention bounds only the backward reach of a sentinel proof. It affects neither soundness nor the claimed completeness for Q, whose certificates begin from actual modification records retained by the archive. Touch transactions. If the last write at or below h is at a, a certificate must account for (a, h]; with BUDs alone that costs h − a exclusions. A touch transaction forces a write at the current height t, preserving the value or writing a tombstone when the key is absent. Its record (k, v, t, p) is an ordinary anchor when h = t. For h < t, a numeric p ≤ h creates a Next extension from p, while p = −1 is a sentinel only when t − η ≤ h < t; p = uninit makes no claim below t. 3
Reading the pointer is not an extra access. Execution already fetches the entry in order to write it, and a deployment maintaining a homomorphic digest of state must read the previous value anyway to remove it from the multiset [18,2].
You’ve Got a BUD in Me Ua (x, vx , a, px )
7
4 (k, v, a, p)
mem., k 7→ a
3
BUD: values and predecessor links
2
SW
1
excl. ex.
ℓ=0 x 7→ b
k 7→ a
SuperBUD: last write in W Leaves sorted by key (x < k).
(a) Contents of the commitments.
H0
a
s
h
(b) Aligned windows over block height.
Fig. 1. From records to interval proofs. (a) A BUD opens the value at a; a SuperBUD opens the last write in its window, without storing that value. Two-leaf trees illustrate the contents; roots also bind their type and height or interval. (b) The aligned hierarchy at e = 2, L = 4, η = 16, with BUDs at level 0. For d = 11, the staircase opens k 7→ a in the shaded level-3 window, then excludes k over [s, h] using successively smaller windows. Parent maps merge their children’s entries by taking the latest height for each key.
Thus touch is a paid constant-size shortcut only when its predecessor or sentinel interval reaches the target, not a completeness mechanism for arbitrary history. The cases are expanded in Section B.2. 4.2
SuperBUDs
A touch consumes block space and has only the reach stated above. SuperBUDs instead answer stale queries passively. For an interval W = [s, t], its span map is MW = {k 7→ max(Mod(k) ∩ W ) : Mod(k) ∩ W ̸= ∅}: it stores each modified key and its final modification in W . Sorting this map by key gives the SuperBUD SW : the commitment MRSuperBUD,(s,t) applied to that sorted sequence, and attested after t is final. Opening k 7→ m clears the portion of W above m; excluding k clears all of W . S For partialWmaps, let A ∨ B keep the greater height for each key. If W = i Wi , then MW = i MWi , so a parent is built by a linear merge of its materialized child maps. Roots alone cannot be merged, and a merged span cannot generally be narrowed; details appear in Section B.3. Window schedules. A schedule fixes which intervals receive SuperBUDs. We use the aligned hierarchy of Figure 1: for base e ≥ 2 and eL ≤ η, a level-ℓ window starts at H0 + jeℓ and ends at H0 + (j + 1)eℓ − 1. Level 0 is a BUD; each higher map is the pointwise maximum of its e children. Beyond BUDs this closes (1 − e−L )/(e − 1) < 1/(e − 1) digests per block, and each write enters at most one map per level. For d = h − a ≥ 1, the staircase clears (a, h] by first opening k 7→ a in the level ℓ′ = min{⌊loge d⌋, L} window containing a, then greedily tiles the remainder through h with aligned windows of decreasing level. The anchoring window closes
8
A. Ranchal-Pedrosa et al.
below h, and the number of exclusions is at most B(d), where ( (e − 1) ⌊loge d⌋ + 1 , d < eL+1 , B(d) = ⌊d e−L ⌋ + (e − 1)L, d ≥ eL+1 .
(2)
Every window a staircase uses has closed at or before h. Under Aatt (λ), all of its attestations are therefore retrievable by height h+λ. A single later-closing window may instead yield a two-digest proof, but alignment does not guarantee one; the staircase is immediate for every anchored query. The construction, boundary case, and alternative schedules are detailed in Sections B.3 and G; Section 6.4 compares their trade-offs. 4.3
Attestation and read certificates
BUDs and SuperBUDs use the same attestation rule. Once their roots are authenticated, a read reduces to opening a value and showing that no later write changed it before the requested height. Attestation. For a digest D, let c(D) be its closure height: set c(Un ) = n and c(SW ) = max W . Let ρ(D) be the committee epoch assigned to c(D). An honest validator signs only after closure is final, at most once per type-and-index pair, and only the digest it derives from the finalized chain. The signed message is mD = enc(BUDAttest, chainID, protocolVersion, ρ(D), type(D), index(D), D) . A digest is attested by signatures from at least τ distinct members of Πρ(D) ; aggregate verification binds the signer set and checks its membership. Soundness needs τ > f , while production without Byzantine participation also needs τ ≤ nρ − f . Quorum-intersection uniqueness can additionally be required via 2τ > nρ + f , but is stronger than this paper’s soundness argument needs. Soundness and honest-only availability are feasible for nρ ≥ 2f + 1; requiring all three gives nρ ≥ 3f + 1. Section B.4 derives these ranges. A chain maintaining a separate replica-agreement digest over the same write log may bind it in the same signed message; the rule authenticates both digest types, not just SuperBUDs. For a finite lag guarantee, define Aatt (λ) to hold when every canonical digest D and τ valid signatures on mD are retrievable by height c(D) + λ. This assumption includes construction capacity, responsive signers, and delivery; asynchrony alone does not imply it. Without it, soundness is unchanged and completeness is conditional on eventual construction and retrieval. Certificate forms and verification. When k was written at h itself, the BUD of that height contains the record and one path answers. Most heights are not like that, so a certificate has two parts. An anchor exhibits a modification height at or below h and the value written there: an inclusion path for a record
You’ve Got a BUD in Me
9
prev = a
(a) Empty
(b) Next Ua
a
a = h
(c) Cover k 7→ a
Ub
Ua
h
(d) sentinel excl.
b p = −1
excl.
Ub
SW a
h
b−η
h
b
Ua
Fig. 2. Four certificate forms. (a) The anchor answers at h = a. (b) A successor brackets h. (c) Span proofs clear (a, h] while Ua supplies the value. (d) A sentinel certifies bounded absence. All roots are attested; the text specifies the acceptance checks.
(k, v, a, p) against an attested BUD Ua with a ≤ h. An extension rules out every modification in (a, h], making the anchor’s height the last relevant one. Three extensions are available (illustrated in Figure 2): (Empty) Nothing, when h = a. The interval is empty and the anchor answers alone. (Next) The next write to k, an inclusion path for a record (k, v ′ , b, a) against an attested BUD Ub with b > h. Its pointer refers to a, so no block between the two modified k. (Cover) Paths against the SuperBUDs of whichever windows the schedule commits, and against BUDs, which are the windows of a single height. An exclusion path clears a whole window lying above a; an inclusion path for k 7→ a clears the part above a of the window that holds a, since being the last modification inside it leaves the rest write free. The cleared parts must together cover (a, h]. Exclusion claims admit a second kind of anchor, which needs no extension. A record (k, v, b, −1) is emitted only when the entry for k is genuinely absent immediately before block b. By Lemma 51(ii), this proves val(k, h) = ∅ for every h ∈ [b − η, b) ∩ [H0 , b). We call this a sentinel anchor. A record carrying uninit is an activation record, not a sentinel, and makes no claim below its own height. Verify authenticates every named committee and threshold attestation, verifies each canonical map opening against its exact type and index, and checks leaf counts, positions, path lengths, and left–right choices. It then enforces the anchor and extension conditions above for one common key. In particular, a Cover must clear every integer height in (a, h]; an ordinary anchor forces y = out(v); and a sentinel must open (k, v, b, −1) in Ub , satisfy b − η ≤ h < b, and force y = ∅. The verifier never interprets uninit as a sentinel or numeric predecessor, and rejects heights below H0 or certificates using an unauthenticated committee epoch. These are the acceptance rules; Sections B.1 and B.2 give their byte
10
A. Ranchal-Pedrosa et al.
Table 1. Passive strategies and active touch shortcuts. Rows involving an anchor a use d = h − a; waits are additional to ordinary attestation availability. Only the touch rows carry a fee. For h < t, a touch with p = uninit, with p > h, or with p = −1 and h < t − η gives no constant-digest certificate. Equation (2) bounds S5 exclusions; the total also includes the ordinary anchor and, when distinct, the anchoring span map. Strategy
Digests
Additional wait
Anchor only (S1) Sentinel (S2) Double BUD (S3) Single SuperBUD (S4) Staircase (S5)
1 1 2 2
none none next write window closure ≤ B(d) + 2 none
h=a p = −1 and b − η ≤ h < b successor carries prev = a covering tail is write free
Touch–Next Touch–sentinel Touch at target
2 1 1
emitted p = a ≤ h < t p = −1 and t − η ≤ h < t h=t
touch attest. touch attest. touch attest.
Applies when
(k, h) ∈ Q, d ≥ 1
encoding and a consolidated checklist. Section 5.3 states the trust and availability assumptions. Choosing a proof strategy. BUDs let the prover choose evidence suited to the key’s history: a fresh write needs one path, a successor can certify the gap, and a cold key can use SuperBUDs. Table 1 names and prices the five strategies from Section 4.3; a is the last modification at or below h, and d = h − a. All five strategies are passive. S5 is available for every query in Q with d ≥ 1 once the digests through h are attested, using at most B(d) + 2 digests. S3 and S4 reduce that count to two when a successor or covering window is available. S4 also needs a write-free tail through the window’s closure, including any heights beyond h. A touch transaction buys a new record but retains the reach limits of Section 4.1 and Table 1: it cannot manufacture sentinel evidence for an absent query older than η, or prove a legacy key’s pre-activation value. Waiting for S3 has no deadline; a schedule may instead guarantee a covering window within a bounded wait (Section G).
5
Correctness
The argument uses two facts: predecessor fields bind records to the relevant part of a key’s history, and the canonical positional Merkle encoding binds accepted openings to the committed map. Full invariants and proofs appear in Section C. Lemma 51 (Predecessor consequences). Every canonical record (k, v, b, p) satisfies: (i) if p ∈ / {−1, uninit}, then p = max(Mod(k) ∩ [H0 , b)); (ii) if p = −1, then
You’ve Got a BUD in Me
11
val(k, h) = ∅ for every h ∈ [b − η, b) ∩ [H0 , b); and (iii) if p = uninit, the record is the first post-H0 modification of an initially present key and makes no claim about earlier heights. Proof sketch. Induct over block height. A write copies the entry’s current marker before storing the new height, while a nonwrite preserves it. A tombstone is collected only after its retention interval, so a subsequently absent entry was absent throughout the trailing η heights. The full state invariant and induction are in Lemma C1. 5.1
Soundness and completeness
Lemma 52 (Authenticated-map binding and exclusion). For a canonical commitment D = MRT,I (z) to a strictly key-sorted sequence, except with negligible probability an accepting inclusion opens the canonical entry at its claimed position, and an accepting exclusion for k implies that z contains no entry with key k. Proof sketch. The committed type, index, count, positions, and domain separators bind each accepted path to its canonical leaf. Adjacent interior openings, or the proper boundary opening, then imply exclusion by strict ordering. The full reduction accompanies Lemma C2. Theorem 53 (Soundness). The read system of Section 4.3 is sound. Proof sketch. Condition on no signature forgery or hash collision. Since τ > f , every accepted digest has an honest signer and is canonical; Lemma 52 then gives each opening its claimed meaning. An ordinary anchor fixes the write at a. Empty has a = h; Next uses Lemma 51(i); and Cover clears every height in (a, h]. Thus Equation (1) fixes y = out(v). A sentinel is valid only over the interval of Lemma 51(ii), and uninit is never interpreted as a numeric predecessor or sentinel. These cases exhaust verification; the proof of Theorem C3 gives the full case analysis. Completeness applies to the domain Q defined in Section 3, assuming that the required archive objects, attestations, and committee evidence are retrievable and every used epoch can be authenticated. A finite delay also requires Aatt (λ), continued archive availability, and committee authentication by height h + λ. Outside Q, an activation record makes no backward claim and a sentinel reaches only η blocks (Section E). Theorem 54 (Completeness). The read system of Section 4.3 is complete. Under the finite-delay assumptions above, a certificate for every (k, h) ∈ Q is available by height h + λ. Proof sketch. Let a = max(Mod(k) ∩ [H0 , h]). The BUD at a anchors the value; if a = h, Empty finishes. Otherwise choose ℓ′ = min{⌊loge (h − a)⌋, L}. Its aligned window containing a ends below h and clears the initial suffix, and the greedy base-e staircase partitions the remainder into closed write-free windows. Every
12
A. Ranchal-Pedrosa et al.
used window closes by h, so the theorem’s attestation, archive, and committee hypotheses supply all evidence by h + λ. A later direct successor can shorten the result but is unnecessary. See the proof of Theorem C4.
5.2
Costs
Authenticated-commitment work follows block write volume rather than live-state size. For block n, constructing the BUD requires sorting wn records and then O(wn ) hashes; the aligned hierarchy adds O(L) amortized map-entry work per write, and tombstone collection is O(1) amortized. Validators retain flat state but no authenticated structure over K or state-tree interior nodes. Ordinary state access can nevertheless retain cache and storage dependence on N , as Section 6.2 shows. An Panchor path costs O(log wa ) hashes, Next adds O(log wb ), and Cover adds i O(log si ) over span maps of sizes si . Implementation details and complete wire accounting appear in Section F.
5.3
Trust anchors, acceptance horizon, and availability
The construction starts from canonical state σ0 at H0 and a trusted checkpoint C for committee authentication. BUDs do not commit to σ0 itself: auditing the complete state needs a separate trusted commitment, while reads in Q rely on honest signers deriving digests from canonical execution. Every accepted epoch must satisfy the historical-key corruption bound of Section 3; key erasure, signatures with forward security, or later checkpoints are needed if that bound cannot be maintained. Activation and cutover. An existing chain can activate legacy keys by scanning the state in deterministic chunks and emitting value-preserving writes. The scan skips keys already activated by ordinary traffic; it must retain activation status or postpone tombstone collection until each key has been considered. The first record carries uninit and supports reads only from its own height onward. After the scan and at most another eL blocks of hierarchy construction, BUDs can replace trie proofs for anchored queries once the evidence is available; earlier heights can still use archived roots. Lazy activation on the first ordinary write or touch avoids the scan but leaves untouched legacy keys outside Q indefinitely. It has no finite cutover guarantee. Section I gives migration and state-sync details. Certificate production requires the records, maps, attestations, and committee evidence to remain retrievable. Missing evidence can prevent a read, but cannot make a false certificate verify. The finite-delay assumptions are stated in Section 5.1. Measured byte totals cover records, entries, identifiers, and Merkle paths; full wire cost also includes each digest’s attestation and uncached evidence for each committee epoch (Section F).
You’ve Got a BUD in Me
6
13
Evaluation
The evaluation follows the design’s division of work: validators apply and commit updates, while provers assemble historical certificates. We measure state-size sensitivity and QMDB’s reclamation tradeoff (Section 6.2), certificate cost and strategy availability (Section 6.3), and the price of extra SuperBUDs (Section 6.4). 6.1
Setup
All systems replay the same blocks. bud includes flat-state application and BUD construction; baselines are a simplified in-memory Merkle Patricia trie, a disk-backed version, NOMT [15], and QMDB [36]. The prototype trie omits RLP and Ethereum’s account/storage split. Synthetic traces vary N and w and include deletions. We also replay an Ethereum account-access trace covering 24,576 blocks, with 445 marked accounts per block on average. Accounts identified from public RPC data are treated as writes and densely remapped. Marking can include unchanged accounts and miss internal changes; storage writes, deletions, and actual values are unavailable. These results describe recurrence and workload sensitivity under the benchmark encoding, not native Ethereum-client performance (Section H.1). Commitment points comprise 128 measured blocks on an Apple M4 with 16 GB RAM. Only the disk-backed trie is cache-capped; NOMT and QMDB use their defaults, so absolute comparisons are configuration-specific. Certificate experiments run for 6η blocks and build every applicable strategy for each sampled anchor and staleness. Event sampling favors recurring keys; uniform-key sampling chooses an observed key uniformly, then one of its events, giving cold keys equal weight. Verification times cover warm hash paths. Section H.1 gives the full settings and sampling methods. The prototype benchmarks replay and hash proofs; activation, digest domain separation, and end-to-end attestation verification are not implemented. 6.2
Commitment cost
Growing the synthetic state from 104 to 5·105 keys at w = 2,000 raises bud time from 1.19 to 1.47 ms (1.24×), versus 3.1× for the in-memory trie and 69.5× for the cache-capped disk trie; NOMT rises from 43.6 to 464.8 ms, while QMDB is nearly flat (Figure 3(a)). The residual bud increase is flat-state lookup, not commitment construction. On the Ethereum trace, bud changes by 1.16× from 104 to 106 keys, versus 13.9× for the disk trie. At N = 105 , bud uses 0.67–0.89 µs per synthetic write and 0.75 µs per marked account (Figure 3(b)). QMDB: update cost and reclamation. QMDB also avoids a steep state-size penalty and reaches 0.80 µs per write at w = 105 , against BUD’s 0.89. Its appendonly authenticated storage has a different maintenance obligation: reclaiming superseded regions relocates live entries in updater threads on which block
14
A. Ranchal-Pedrosa et al.
per-block wall time (ms), p50 with p99 whisker
Q1: per-block commitment cost vs state size N BUD (KV apply + commit) MPT (disk-backed, sled) MPT (in-memory) NOMT QMDB synthetic, w = 2,000 (solid) Ethereum trace, w ≈ 375–496 (dashed)
103
Synthetic 2
Ethereum
3
5
Backend w=10 w=2·10 w=10
102
101
100
104
105 state size N (keys)
w≈375
bud
0.77
0.67
0.89
0.75
mpt
7.26
2.23
1.23
2.74
NOMT
356.44 123.37
5.46
295.49
QMDB
322.24
0.80
74.82
17.17
106
(a) State-size sweep.
(b) Mean replay time per key.
Fig. 3. Commitment-cost results. (a) Per-block p50 versus state size (p99 whiskers): solid is synthetic (w = 2,000), dashed is 128-block Ethereum trace windows (w ≈ 375– 496). Only the disk mpt is cache-capped. (b) Mean end-to-end time per key at N = 105 , in µs; bud includes state application and BUD construction, but excludes SuperBUD maintenance. Trace scope and measurement boundaries are in Section H.1.
completion waits. BUD’s tombstone expiry requires no such relocation to maintain authentication. We therefore test reclamation separately in a 20,000-block replay at N = 107 , w = 2,000, and 2% deletions. We lower only the live-entry gate from 20 million to 500,000 per shard, repeat each configuration twice, and confirm activation through advancing reclamation watermarks. The latency difference is smaller than between-run variation, but active reclamation grows database files by 7.2 GiB versus 2.7 GiB when inactive (2.6×). These are retained-file deltas; physical device writes were not instrumented. This is the measured tradeoff; behavior near the default gate of roughly 3.2·108 live entries remains unmeasured. Section H.7 gives the activation settings, watermark checks, and storage measurements. 6.3
Certificate cost and strategy choice
Read-layer size follows the staircase analysis: on the synthetic trace, S3 remains near 453 bytes, S4 below 800 bytes, and S5 grows logarithmically to about 12 kB; every measured S5 exclusion count satisfies Equation (2). Warm hash-path verification reaches at most 146 µs at p99 (Figure 4(a)). Attestation checks are additional: a separate BLS12-381 benchmark, using preaggregated keys for 67 of 100 authenticated signers, takes about 0.65 ms to batch-verify the two aggregate signatures for S3 or S4 (Section H.1). Under the same benchmark encoding, our prototype trie produces a 2,087-byte inclusion proof for the easier current-value query. Strategy availability is recurrence-sensitive. At d = 1, S3 is cheapest for 84.2% of uniform-key synthetic queries but 28.4% on the Ethereum trace: half of its observed accounts appear only once and have no recorded successor. S4 fills much of this gap but decays with staleness (Figure 4(b)). By d = 64, the mean S5
You’ve Got a BUD in Me Q3: certificate size vs staleness d (write-event family)
Q3: S4 empirical availability by family vs the single-level lower bound 1.0
104
write_event (synthetic) uniform_key (synthetic) write_event (Ethereum) uniform_key (Ethereum) single-level model (lower bound)
0.8 S3 (double BUD) S4 (single SuperBUD) S5 (staircase) synthetic trace (solid) recorded Ethereum trace (dashed)
103
S4 availability
certificate size (bytes, log scale)
15
0.6 0.4 0.2 0.0
100
101
102 103 staleness d (log scale)
104
105
100
(a) Certificate size.
101
102 103 staleness d (log scale)
104
105
(b) S4 availability.
Fig. 4. Read-layer certificate size and S4 availability versus staleness. Solid: synthetic (η = 16,384, w = 50); dashed: Ethereum account-access trace (η = 4,096, full-trace mean w ≈ 445). Bytes use the benchmark encoding; totals exclude attestation and committee evidence (Section H.2).
cover is about 5.5 windows in both workloads. History therefore changes strategy availability more than cover size at fixed staleness. Component costs, complete shares, and skew sensitivity appear in Sections H.2, H.3 and H.5. 6.4
Schedules and hierarchy parameters
Measured digest rates equal (1 − e−L )/(e − 1) at every reported precision, and every sampled S5 exclusion count satisfies Equation (2). At fixed η = 4,096, moving from (e, L) = (2, 12) to (8, 4) lowers extra digests per block from 0.9998 to 0.1428 and roughly halves p99 block time, while the mean cover grows from 4.5 to 8.5 windows and S4 availability falls by about ten percentage points (Section H.4). Full striding starts a size-eℓ window every eℓ−1 blocks, rather than every eℓ blocks. At e = 4 it produces 4.0× as many digests as aligned, raising synthetic S4 availability from 83.7% to 96.0%; the Ethereum trace shows the same tradeoff (Section H.6). Our single-level baseline uses disjoint 64-block SuperBUDs, producing 21× fewer digests than aligned but leaving more gaps to S5. For gaps whose required cover fits within the level cap, at least two evenly staggered phases guarantee a bounded-wait two-digest proof (Section G).
7
Conclusion
Historical reads can be authenticated without making every validator maintain an authenticated copy of the entire state. BUDs prove writes; predecessor links and SuperBUDs prove what stayed unchanged. Together they support historical membership and exclusion with construction work tied to write volume and an explicit trade-off between proof size and waiting time. Our prototype confirms the value of this separation: over a 50× increase in state size, the base-BUD path grows by 1.24×, versus 3.1× and 69.5× for the two trie baselines. Validators execute
16
A. Ranchal-Pedrosa et al.
against flat state and attest changes; untrusted archives assemble the proofs. The global authenticated structure is no longer a prerequisite for authenticated reads.
References 1. Anagnostopoulos, A., Goodrich, M.T., Tamassia, R.: Persistent authenticated dictionaries and their applications. In: Davida, G.I., Frankel, Y. (eds.) Information Security. Lecture Notes in Computer Science, vol. 2200, pp. 379–393. Springer Berlin Heidelberg, Berlin, Heidelberg (2001). https://doi.org/10.1007/3-540-45439-X_ 26, https://doi.org/10.1007/3-540-45439-X_26 2. Bellare, M., Micciancio, D.: A new paradigm for collision-free hashing: Incrementality at reduced cost. In: Fumy, W. (ed.) Advances in Cryptology—EUROCRYPT ’97. Lecture Notes in Computer Science, vol. 1233, pp. 163–192. Springer, Berlin, Heidelberg (1997). https://doi.org/10.1007/3-540-69053-0_13, https://doi. org/10.1007/3-540-69053-0_13 3. Bender, M.A., Farach-Colton, M.: The LCA problem revisited. In: LATIN 2000: Theoretical Informatics. Lecture Notes in Computer Science, vol. 1776, pp. 88– 94. Springer (2000). https://doi.org/10.1007/10719839_9, https://doi.org/ 10.1007/10719839_9 4. Boneh, D., Bünz, B., Fisch, B.: Batching techniques for accumulators with applications to IOPs and stateless blockchains. In: Boldyreva, A., Micciancio, D. (eds.) Advances in Cryptology – CRYPTO 2019. Lecture Notes in Computer Science, vol. 11692, pp. 561–586. Springer (2019). https://doi.org/10.1007/ 978-3-030-26948-7_20, https://doi.org/10.1007/978-3-030-26948-7_20 5. Buterin, V.: Plasma Cash: Plasma with much less per-user data checking. Ethereum Research (Mar 2018), https://ethresear.ch/t/ plasma-cash-plasma-with-much-less-per-user-data-checking/1298 6. Buterin, V.: RSA accumulators for Plasma Cash history reduction. Ethereum Research (Oct 2018), https://ethresear.ch/t/ rsa-accumulators-for-plasma-cash-history-reduction/3739 7. Buterin, V.: A state expiry and statelessness roadmap. Ethereum Research notes (Jun 2021), https://notes.ethereum.org/@vbuterin/verkle_and_state_ expiry_proposal 8. Chase, M., Deshpande, A., Ghosh, E., Malvai, H.: SEEMless: Secure end-to-end encrypted messaging with less trust. In: Proceedings of the 2019 ACM SIGSAC Conference on Computer and Communications Security. pp. 1639–1656. CCS ’19, Association for Computing Machinery, New York, NY, USA (Nov 2019). https://doi. org/10.1145/3319535.3363202, https://doi.org/10.1145/3319535.3363202 9. Chepurnoy, A., Papamanthou, C., Srinivasan, S., Zhang, Y.: Edrax: A cryptocurrency with stateless transaction validation. Cryptology ePrint Archive, Paper 2018/968 (2018), https://eprint.iacr.org/2018/968 10. Christ, M., Bonneau, J.: Limits on revocable proof systems, with implications for stateless blockchains. In: Baldimtsi, F., Cachin, C. (eds.) Financial Cryptography and Data Security. Lecture Notes in Computer Science, vol. 13951, pp. 54–71. Springer (2023). https://doi.org/10.1007/978-3-031-47751-5_4, https://doi. org/10.1007/978-3-031-47751-5_4 11. Crosby, S.A., Wallach, D.S.: Efficient data structures for tamper-evident logging. In: Proceedings of the 18th USENIX Security Symposium. pp. 317–334. USENIX Association, Montreal, Canada (Aug 2009), https://www.usenix.org/legacy/ event/sec09/tech/full_papers/crosby.pdf
You’ve Got a BUD in Me
17
12. Datar, M., Gionis, A., Indyk, P., Motwani, R.: Maintaining stream statistics over sliding windows. SIAM Journal on Computing 31(6), 1794– 1813 (2002). https://doi.org/10.1137/S0097539701398363, https://doi.org/ 10.1137/S0097539701398363 13. Dryja, T.: Utreexo: A dynamic hash-based accumulator optimized for the Bitcoin UTXO set. Cryptology ePrint Archive, Paper 2019/611 (2019), https://eprint. iacr.org/2019/611 14. Gorbunov, S., Reyzin, L., Wee, H., Zhang, Z.: Pointproofs: Aggregating proofs for multiple vector commitments. In: Proceedings of the 2020 ACM SIGSAC Conference on Computer and Communications Security. pp. 2007–2023. CCS ’20, Association for Computing Machinery, New York, NY, USA (2020). https://doi.org/10.1145/ 3372297.3417244, https://doi.org/10.1145/3372297.3417244 15. Habermeier, R.: Introducing NOMT. Blog post (May 2024), https://www.rob. tech/blog/introducing-nomt/ 16. Hu, Y., Hooshmand, K., Kalidhindi, H., Yang, S.J., Popa, R.A.: Merkle2 : A lowlatency transparency log system. In: 2021 IEEE Symposium on Security and Privacy (SP). pp. 285–303. IEEE (May 2021). https://doi.org/10.1109/SP40001.2021. 00088, https://doi.org/10.1109/SP40001.2021.00088 17. Leung, D., Gilad, Y., Gorbunov, S., Reyzin, L., Zeldovich, N.: Aardvark: An asynchronous authenticated dictionary with applications to account-based cryptocurrencies. In: 31st USENIX Security Symposium (USENIX Security 22). pp. 4237–4254. USENIX Association, Boston, MA (Aug 2022), https://www.usenix. org/conference/usenixsecurity22/presentation/leung 18. Lewi, K., Kim, W., Maykov, I., Weis, S.: Securing update propagation with homomorphic hashing. Cryptology ePrint Archive, Paper 2019/227 (2019), https: //eprint.iacr.org/2019/227 19. Li, C., Beillahi, S.M., Yang, G., Wu, M., Xu, W., Long, F.: LVMT: An efficient authenticated storage for blockchain. In: 17th USENIX Symposium on Operating Systems Design and Implementation (OSDI 23). pp. 135–153. USENIX Association, Boston, MA (Jul 2023), https://www.usenix.org/conference/osdi23/ presentation/li-chenxing 20. Malvai, H., Kokoris-Kogias, L., Sonnino, A., Ghosh, E., Oztürk, E., Lewi, K., Lawlor, S.: Parakeet: Practical key transparency for end-to-end encrypted messaging. In: Proceedings 2023 Network and Distributed System Security Symposium. NDSS 2023, Internet Society (2023). https://doi.org/10.14722/ndss.2023.24545, https:// doi.org/10.14722/ndss.2023.24545 21. MegaLabs: MegaETH: Unveiling the first real-time blockchain (2024), https:// www.megaeth.com/research 22. Melara, M.S., Blankstein, A., Bonneau, J., Felten, E.W., Freedman, M.J.: CONIKS: Bringing key transparency to end users. In: 24th USENIX Security Symposium (USENIX Security 15). pp. 383–398. USENIX Association, Washington, D.C. (Aug 2015), https://www.usenix.org/conference/usenixsecurity15/ technical-sessions/presentation/melara 23. Monad Foundation: Asynchronous execution (2026), monad documentation, https: //docs.monad.xyz/monad-arch/consensus/asynchronous-execution 24. Noyes, C., Robinson, D., Drake, J., Wahrstätter, T.: EIP-7862: Delayed state root (2024), https://eips.ethereum.org/EIPS/eip-7862 25. Prumo, B.: SIMD-0223: Removes Accounts Delta Hash. Solana Improvement Documents (Jan 2025), https://github.com/ solana-foundation/solana-improvement-documents/blob/main/proposals/ 0223-removes-accounts-delta-hash.md
18
A. Ranchal-Pedrosa et al.
26. Prumo, B., Cesena, E., Siegel, J., Kim, S.: SIMD-0215: Homomorphic hashing of account state. Solana Improvement Documents (Dec 2024), https://github.com/solana-foundation/solana-improvement-documents/ blob/main/proposals/0215-accounts-lattice-hash.md 27. Pulls, T., Peeters, R.: Balloon: A forward-secure append-only persistent authenticated data structure. In: Pernul, G., Ryan, P.Y.A., Weippl, E. (eds.) Computer Security – ESORICS 2015. Lecture Notes in Computer Science, vol. 9327, pp. 622– 641. Springer International Publishing, Cham (2015). https://doi.org/10.1007/ 978-3-319-24177-7_31, https://doi.org/10.1007/978-3-319-24177-7_31 28. Raju, P., Ponnapalli, S., Kaminsky, E., Oved, G., Keener, Z., Chidambaram, V., Abraham, I.: mLSM: Making authenticated storage faster in Ethereum. In: 10th USENIX Workshop on Hot Topics in Storage and File Systems (HotStorage 18). USENIX Association, Boston, MA (Jul 2018), https://www.usenix.org/ conference/hotstorage18/presentation/raju 29. Srinivasan, S., Chepurnoy, A., Papamanthou, C., Tomescu, A., Zhang, Y.: Hyperproofs: Aggregating and maintaining proofs in vector commitments. In: 31st USENIX Security Symposium (USENIX Security 22). pp. 3001–3018. USENIX Association, Boston, MA (Aug 2022), https://www.usenix.org/conference/ usenixsecurity22/presentation/srinivasan 30. Sui Foundation: Sui full node gRPC enum and scalar type definitions (2026), sui documentation, https://docs.sui.io/references/fullnode-protocol-types 31. Todd, P.: Merkle mountain ranges. OpenTimestamps design documentation (Oct 2012), https://github.com/opentimestamps/opentimestamps-server/ blob/master/doc/merkle-mountain-range.md 32. Tomescu, A., Abraham, I., Buterin, V., Drake, J., Feist, D., Khovratovich, D.: Aggregatable subvector commitments for stateless cryptocurrencies. In: Galdi, C., Kolesnikov, V. (eds.) Security and Cryptography for Networks. Lecture Notes in Computer Science, vol. 12238, pp. 45–64. Springer (2020). https://doi.org/10. 1007/978-3-030-57990-6_3, https://doi.org/10.1007/978-3-030-57990-6_3 33. Wahrstätter, T., Feist, D., D’Amato, F., Brouwer, J., Hagopian, I., Selmo, F., Rahul, Stefan: EIP-7928: Block-level access lists (2025), https://eips.ethereum. org/EIPS/eip-7928 34. Yang, X., Zhang, Y., Wang, S., Yu, B., Li, F., Li, Y., Yan, W.: LedgerDB: A centralized ledger database for universal audit and verification. Proceedings of the VLDB Endowment 13(12), 3138–3151 (2020). https://doi.org/10.14778/ 3415478.3415540, https://doi.org/10.14778/3415478.3415540 35. Yue, C., Dinh, T.T.A., Xie, Z., Zhang, M., Chen, G., Ooi, B.C., Xiao, X.: GlassDB: An efficient verifiable ledger database system through transparency. Proceedings of the VLDB Endowment 16(6), 1359–1371 (2023). https://doi.org/10.14778/ 3583140.3583152, https://doi.org/10.14778/3583140.3583152 36. Zhang, I., Zarick, R., Wong, D., Kim, T., Pellegrino, B., Li, M., Wong, K.: QMDB: Quick merkle database. arXiv preprint arXiv:2501.05262 (Jan 2025), https:// arxiv.org/abs/2501.05262
You’ve Got a BUD in Me
19
Appendix guide. The main text gives the protocol, its guarantees, and the experimental findings. The appendices make those claims checkable: exact encodings and verifier checks in Section B, full proofs in Section C, schedule derivations in Section G, and workloads and measurements in Section H. Retention, trust, and migration details appear in Sections D to F and I. Table 2. Notation used throughout the construction and evaluation. Term or symbol Meaning BUD Merkle root of one block’s canonical, key-sorted write log. SuperBUD Merkle root of the span map MW for an interval W . ∆n Canonical write log produced by block n. N Number of live state entries. wn Number of distinct keys written in block n. H0 Deployment origin, below which the write logs make no claim. Mod(k), val(k, h) Modification heights of key k and its canonical value at height h. h, a, d = h − a Query height, latest modification at or below h, and staleness d. p Previous-modification field: a height, −1, or uninit. uninit Marker for an initially present key with no post-H0 modification. η Tombstone-retention window, maximum reach of a sentinel anchor. e, L, ℓ Hierarchy base, highest configured level, and a level index. W, MW A block interval and its map from each modified key to its last modification in W . 1≤φ≤e Number of staggered schedules committed at each hierarchy level. f, τ, λ Byzantine bound, attestation threshold, and attestation lag.
A
Additional related work
Solana mixes a lattice hash of all accounts into each bank hash, while Sui commits an elliptic-curve multiset hash of live objects [26,25,30]. Both follow incremental multiset hashing [2,18]. Ethereum’s deferred-root and post-execution access-list proposals reduce synchronous work, but the global root remains; proving one access-list entry also requires the list [24,33]. Aardvark is the closest stateless design: validators retain a commitment, untrusted servers prove, and a version window admits stale proofs [17]. Unlike BUDs, these commitments span the dictionary. Key-transparency systems authenticate epoch values and append-only directory evolution [22,8,20,16]; tamper-evident logs and persistent dictionaries support membership at historical snapshots [11,1,27]. Plasma Cash addresses interval exclusion with RSA accumulators [5,6]. Verifiable ledger databases instead assume a trusted operator [34,35], while Ethereum state expiry parallels our retention window and touches [7]. SuperBUDs resemble history trees and Merkle
20
A. Ranchal-Pedrosa et al.
Mountain Ranges [11,31]; their hierarchy authenticates bucketing analogous to exponential histograms [12], and staggered windows resemble sparse tables for idempotent aggregates [3].
B
Encodings and protocol derivations
Section 4 gives the construction and all acceptance rules. This appendix fixes the exact Merkle encoding, collects the verifier checks, and derives the merge and threshold formulas. It supplies implementation detail without adding a new proof mechanism or trust assumption. B.1
Canonical authenticated maps
Let T ∈ {BUD, SuperBUD}, let I be an object index, and let z = (z1 , . . . , zm ) have strictly increasing keys. The strings leaf, pad, node, root, and empty are distinct domain separators. For m > 0, put M = 2⌈log2 m⌉ and form a complete tree with leaves ( H leaf ∥ enc(m, i, zi ) , 1 ≤ i ≤ m, xi = H pad ∥ enc(m, i) , m < i ≤ M. An internal node with children x, y is H(node ∥ x ∥ y). If R is the tree root, define MRT,I (z) = H(root ∥ enc(T, I, m, R)). For m = 0, define MRT,I (()) = H(empty ∥ enc(T, I, 0)). An inclusion proof supplies m, a position i ∈ {1, . . . , m}, its entry, and one sibling per level; the bits of i − 1 determine left–right choices. An exclusion proof for k has one of four forms: (i) m = 0 and the root is the distinguished empty root; (ii) position 1 opens to a key greater than k; (iii) consecutive positions i, i + 1 open to keys k ′ < k < k ′′ ; (iv) position m opens to a key less than k. All openings in one proof use the same type, index, root, and leaf count. B.2
Touch and certificate checks
For a touch record (k, v, t, p) and target h: (i) if h = t, the record is an ordinary anchor; (ii) if h < t, p ∈ / {−1, uninit}, and p ≤ h, it is a Next extension for the anchor at p; (iii) if p = −1, it is a sentinel anchor only when t − η ≤ h < t; and (iv) if p = uninit, it activates the key but says nothing below t. For every digest D, Verify requires AuthCom(C, ρ(D), Πρ(D) , χρ(D) ) = 1 and checks the signer set, threshold, signed message, type, index, and root. It verifies the leaf count, position, path length, and left–right choices of every map proof; an interior exclusion must open positions i, i + 1 under one root and count.
You’ve Got a BUD in Me
21
All components name one key. An ordinary anchor opens (k, v, a, p) in Ua with a ≤ h. Empty requires h = a; Next opens (k, v ′ , b, a) in Ub with b > h; and Cover admits only an inclusion k 7→ a in a window containing a or an exclusion against its named interval, with the cleared integer intervals covering all of (a, h]. Verify forces y = out(v) for an ordinary anchor. A sentinel opens (k, v, b, −1) in Ub , binds the embedded height to the BUD index, requires b − η ≤ h < b, and forces y = ∅. It rejects h < H0 , an unauthenticated epoch, and every attempt to interpret uninit as a sentinel or numeric predecessor. B.3
SuperBUD construction and aligned hierarchy
For partial maps, A ∨ B retains the larger height for a key in both and the sole entry W for a key in only one. If intervals W1 , . . . , Wr have union W , then MW = i MWi because the last modification in a union is the maximum of the last modifications in its parts; overlaps are harmless. A validator can therefore assemble a span in time linear in the total size of materialized child maps. Roots alone do not suffice: it must merge the entries and merklize again. The merge also discards older entries for keys modified twice, so a span cannot generally be narrowed. Dropping the oldest height is the special case used by the sliding schedule of Section G. The exact aligned intervals are Wℓ,j = [H0 + jeℓ , H0 + (j + 1)eℓ − 1],
ℓ ∈ {0, . . . , L},
j ≥ 0.
A level-(ℓ + 1) window is the disjoint union of its e level-ℓ children, so MWℓ+1,j = MWℓ,ej ∨ · · · ∨ MWℓ,ej+e−1 . Level ℓ closes every eℓ blocks; beyond the BUD this gives (1 − e−L )/(e − 1) digests per block and at most L + 1 times write-log growth, because each write is final for its key in at most one window per level. For d = h − a, take the level ℓ′ = min{⌊loge d⌋, L} window containing a. Since ℓ′ e ≤ d, it closes strictly below h. Opening k 7→ a clears its suffix. Starting after that window, at level j take ⌊Rj /ej ⌋ aligned windows and carry the remainder downward. This greedy base-e decomposition clears the rest through h and gives the exclusion bound of Equation (2). Including Ua and a distinct anchoring SuperBUD, the certificate names at most B(d) + 2 digests. The level-ℓ window containing a also contains h exactly when (a − H0 ) mod eℓ < eℓ − d. A prover may use the first such closed window whose map still contains k 7→ a; a later write within that window would invalidate S4. Wider levels close later. Alignment can miss at every level: if a − H0 ≡ −1 (mod eL ), the anchor lies immediately below every aligned boundary. The staircase remains available without an additional wait. B.4
Attestation details
An aggregate signature binds the exact signer set; committee public keys must be validated at registration and the aggregate scheme must resist rogue-key attacks, for example through proofs of possession. Verifying individual signatures is also sufficient. The threshold requirements have separate roles:
22
A. Ranchal-Pedrosa et al.
1. τ > f puts an honest signer in every accepted attestation; 2. τ ≤ nρ − f permits production without Byzantine participation; 3. 2τ > nρ + f makes two threshold sets intersect honestly and gives quorumintersection uniqueness. The third is stronger than soundness requires. All three are feasible exactly when nρ ≥ 3f + 1, with ⌈(nρ + f + 1)/2⌉ ≤ τ ≤ nρ − f . Soundness plus honest-only availability needs only nρ ≥ 2f + 1 and f < τ ≤ nρ − f . A deployment maintaining a separate replica-agreement digest over ∆n , such as a homomorphic multiset hash [18,2], may bind it in the same signed message. This optimization does not change the thresholds.
C
Correctness proofs
The proof rests on two binding properties: numeric predecessor fields identify the preceding modification, and an absent entry implies bounded past absence. The reserved marker uninit makes no statement about the pre-deployment history. Lemma C1 (Full pointer invariant). For every height n ≥ H0 and key k, after block n executes: (i) if the entry is present and last(k) ̸= uninit, then last(k) = max(Mod(k) ∩ [H0 , n]); (ii) if the entry is present and last(k) = uninit, then Mod(k) ∩ [H0 , n] = ∅; (iii) if the entry is absent, then val(k, h) = ∅
for every h ∈ [n − η, n] ∩ [H0 , n];
(iv) every record (k, v, n, p) with p ∈ / {−1, uninit} satisfies p = max(Mod(k) ∩ [H0 , n)); (v) every record (k, v, n, −1) satisfies val(k, h) = ∅
for every h ∈ [n − η, n) ∩ [H0 , n);
(vi) every record (k, v, n, uninit) is the first modification since H0 of an initially present key and makes no claim about heights below n. Proof. Initially, a key in dom(σ0 ) is present with marker uninit, while a key outside that domain has no entry. This establishes the corresponding base cases. For n = H0 , the interval asserted in part (v) is empty; the remaining claims follow directly after the first transition. Suppose n > H0 and the claims hold after block n−1. If block n writes k, there are three cases. If the entry carries a numeric predecessor p, part (i) at n−1 shows that p is the greatest earlier modification height, proving part (iv). If it carries
You’ve Got a BUD in Me
23
uninit, part (ii) shows that this is the first post-deployment modification, proving part (vi). If no entry is present, part (iii) at n − 1 proves absence throughout [n − η, n) ∩ [H0 , n), proving part (v). In all three cases execution stores (v, n), establishing part (i). If block n does not write k, an entry absent after block n − 1 remains absent; the interval in part (iii) shifts forward by one height and val(k, n) = ∅. A present entry and its marker are unchanged unless the entry is an expired tombstone that is collected. In the unchanged case, parts (i) and (ii) persist. In the collection case, the tombstone was written at some m ≤ n − η and remains the last modification of k. Consequently val(k, h) = ∅ for every h ≥ m, including the interval required by part (iii). C.1
Soundness and completeness
Lemma C2 (Authenticated-map binding and exclusion). Let D = MRT,I (z) be the canonical commitment to a strictly key-sorted sequence z. Except with negligible probability, an accepting inclusion proof at position i opens the canonical entry zi , and an accepting exclusion proof for k implies that z contains no entry with key k. Proof. Compare an accepting computation with the canonical tree. If the supplied type, index, or leaf count differs, equality of the outer digests gives a collision in H. Otherwise, if the supplied entry at position i differs from the canonical entry, either the distinct leaf inputs have the same hash, or the first level at which distinct child pairs produce the same parent gives a collision. Thus every accepted opening is canonical at its claimed position. For an interior exclusion, the accepted openings are therefore the canonical entries at consecutive positions i and i + 1. Strict sorting leaves no entry with key between them. The boundary cases follow because the opened entry is the first or last canonical entry. Finally, accepting the empty form for a nonempty sequence would equate domain-separated empty and nonempty roots and again yield a collision. Theorem C3 (Soundness). The read system of Section 4.3 is sound. Proof. Condition on the event that no signature forgery and no hash collision occurs; the complementary event has negligible probability. Consider any digest D named by an accepting certificate. The verifier authenticates Πρ(D) , and the attestation contains signatures from more than f committee members. At least one signer is therefore honest. By Section 4.3, that signer signed only the digest independently derived from the finalized chain. Deterministic execution and the state-integrity assumption imply that D is canonical. By Lemma C2, every accepted inclusion opens the corresponding canonical entry and every accepted exclusion establishes canonical absence. First suppose the certificate has an ordinary anchor (k, v, a, p) against Ua . It proves that (k, v) ∈ ∆a , and hence that block a wrote v to k. We show that
24
A. Ranchal-Pedrosa et al.
every accepted extension establishes Mod(k) ∩ (a, h] = ∅. For Empty, h = a. For Next, the certificate opens a canonical record (k, v ′ , b, a) with b > h. By Lemma C1(iv), a = max(Mod(k) ∩ [H0 , b)), so there is no modification in (a, b) and hence none in (a, h]. For Cover, an exclusion proof for window W establishes Mod(k) ∩ W = ∅. An inclusion proof for k 7→ a establishes that a is the final modification of k in W , and therefore clears W ∩ (a, ∞). A BUD supplies the same statement for a singleton window. Since Verify checks that the cleared intervals cover every integer height in (a, h], no modification occurs there. Thus, in every ordinary-anchor case, a = max(Mod(k) ∩ [H0 , h]), and Equation (1) gives val(k, h) = out(v). The output check forces y = out(v), covering both membership and tombstone exclusion. It remains to consider a sentinel anchor. Its canonical record has the form (k, v, b, −1), and Verify requires b − η ≤ h < b. By Lemma C1(v), val(k, h) = ∅, and the sentinel output check forces y = ∅. A record carrying uninit cannot enter this case. These cases exhaust all accepting certificates. Completeness is claimed only for Q. A query outside Q may concern either an untouched member of σ0 or a key absent throughout [H0 , h]. A later uninit record makes no backward claim and cannot certify the first case. A later record (k, v, b, −1) certifies the second case only when h < b ≤ h + η. In particular, a touch at height t supplies usable sentinel evidence only if t ≤ h + η; it cannot repair an arbitrarily old query. Assume that the canonical archive objects, attestations, and committee evidence needed by a query in Q are retrievable, and that the verifier can authenticate every epoch used. For a finite delay, also assume Aatt (λ), continued archive availability, and committee authentication by height h + λ. Theorem C4 (Completeness). The read system of Section 4.3 is complete. Under the finite-delay assumptions above, a certificate for every (k, h) ∈ Q is available by the time the chain finalizes height h + λ. Proof. Take (k, h) ∈ Q and let a = max(Mod(k) ∩ [H0 , h]). The honest prover can open the canonical record (k, v, a, p) against Ua . If a = h, this anchor with Empty is an accepting certificate. Suppose a < h and write d = h − a. Then Mod(k) ∩ (a, h] = ∅. Let ℓ′ = min{⌊loge d⌋, L}
You’ve Got a BUD in Me
25
′
and let W ⋆ be the level-ℓ′ aligned window containing a. Since eℓ ≤ d, the right endpoint of W ⋆ lies strictly below h. If ℓ′ > 0, its span map contains k 7→ a; if ℓ′ = 0, the ordinary anchor supplies the corresponding singleton statement. Starting immediately after W ⋆ , the greedy base-e decomposition partitions the remaining heights through h into aligned windows of nonincreasing level. None contains a modification of k, so each supplies an exclusion proof. Together with the anchoring inclusion, these paths clear all of (a, h]. Every window used by the staircase closes at or before h. Under Aatt (λ), its attestation is retrievable by height h + λ. The prover returns y = out(v), which equals val(k, h) by Equation (1). If a later record at height b > h actually carries p = a, then Next supplies a shorter certificate once Ub is attested. Completeness does not depend on such a record.
D
Unbounded retention
A finite η is needed only to collect tombstones and to bound how far a sentinel record with p = −1 may reach. It does not limit certificates for queries in Q, which begin from an actual modification record. Setting η = ∞ retains every tombstone, at the cost of storage proportional to cumulative deletions. A record with p = −1 then proves that an initially absent key remained absent back to H0 . An unactivated member of σ0 is different: its first later write or touch emits uninit and makes no backward claim. A key with no record still needs a later write or touch before any record can mention it. With no finite retention window, η no longer determines the top hierarchy level. The deployment chooses L independently, and queries with d ≥ eL+1 use the capped branch of Equation (2).
E
Queries outside the completeness domain
Queries outside Q. Suppose Mod(k) ∩ [H0 , h] = ∅. If k ∈ dom(σ0 ), a later activation record carries p = uninit and deliberately makes no claim about the value at h. If k ∈ / dom(σ0 ), a later record (k, v, b, −1) proves absence at h exactly when h < b ≤ h + η, by Lemma 51(ii). Once h + η has passed without such a record, no future sentinel under finite retention can certify that old query. These limitations do not affect the completeness claim on Q.
F
Operational assumptions and complete costs
Trust anchors and cumulative binding. The canonical state σ0 and verifier checkpoint C are independent anchors. The former determines validator execution after H0 ; the latter authenticates committees and need not contain application state. A BUD is not a standalone state root. Instead, σ0 plus the ordered
26
A. Ranchal-Pedrosa et al.
committed logs determines one evolving state. A verifier wishing to reconstruct or audit that entire state needs a separate trusted commitment to σ0 and access to the logs. A point read in Q uses local certificates and the fact that an honest signer derived every accepted digest from canonical execution. Epochs and historical keys. Every digest is checked against the committee assigned to its closure epoch, including when one certificate spans several epochs. The verifier requires AuthCom(C, ρ, Πρ , χρ ) = 1 for each and may impose an acceptance horizon through checkpoint policy. That horizon applies to every digest, not merely the target or anchor. With reusable signatures, no more than f accepted historical keys may become adversarial while an epoch remains acceptable. Key erasure, signatures with forward security, or a later checkpoint fixing historical digests is required when that continuing bound cannot be maintained. Availability. Verification cannot force an archive or signer to answer. Generation needs the relevant BUD records, span maps, Merkle material, attestations, and uncached committee-transition evidence. Missing objects can prevent production or acceptance but cannot make an incorrect certificate verify. Hence finite delay depends on Aatt (λ), continued object availability, and authentication of every relevant epoch by h + λ; without them, completeness is conditional on eventual retrieval and authentication. Complete wire accounting. Let D(π) be the named digests and R(π) their distinct committee epochs. Up to fixed headers, X X |π|wire = |π|read + |att(D)| + (|Πρ | + |χρ |). D∈D(π)
ρ∈R(π) ρ not cached
Here att(D) includes the signature or aggregate and signer set. |π|read comprises records, entries, identifiers, and Merkle authentication data. Our byte experiments exclude attestations, committee-transition proofs, checkpoint data, and transport. Committee descriptors and evidence can be cached across queries; a stateless verifier adds them once per represented epoch. Implementation work. After sorting, a BUD is a fixed number of data-parallel hash rounds over a contiguous buffer already produced by execution, with no disk access on its commitment path. A disk-backed state trie instead updates scattered interior nodes. This explains the structural comparison; the measured configurations and their limitations are given in Sections 6.2 and H.1.
G
Window schedule
The main construction uses the aligned hierarchy of Section 4.2. Here we compare it with three alternatives: committing only one SuperBUD size, staggering several windows of each size, and closing a window of every size at every block. Figure 5 shows the four schedules.
You’ve Got a BUD in Me (a) one size, m = 4
27
(b) aligned, e = 2 (φ = 1) 8
4
4 2
1
1
(c) φ-phase, e = 2, φ = 2
(d) per-block sliding
8
8
4 2 1
··· ···
4 2
···
1
Fig. 5. Four ways to place SuperBUD windows over eight heights. Dark boxes are BUDs. (a) One fixed SuperBUD size. (b) The aligned hierarchy used in the main construction. (c) Two staggered schedules per size; for e = 2, this is full striding. (d) A window of every size ending at every height.
One SuperBUD size. The simplest baseline fixes a size m and commits the disjoint intervals [H0 + jm, H0 + (j + 1)m − 1] for j ≥ 0. It adds only 1/m digests per block, but gaps not covered by these SuperBUDs must be filled with BUDs. φ-phase schedule. At level ℓ, a window has size E = eℓ . Aligned schedule starts one such window every E blocks. Full striding starts one every E/e blocks, giving e possible schedules of each size. A φ-phase hierarchy commits φ of these schedules, including phase zero and spacing the remaining phases as evenly as possible. Thus φ = 1 is aligned and φ = e is fully strided. Every placed window is the disjoint union of e aligned windows from the level below and uses the same merge rule. Per-block sliding. This schedule closes one window of every size at every height. Moving [s, t] forward by one block uses M[s+1,t] = { k 7→ m ∈ M[s,t] : m > s }. A validator removes entries whose last modification is exactly s, applies ∆t+1 , and rebuilds the new Merkle tree. The resulting proofs are small, but rebuilding L roots at every height makes this schedule expensive. Lemma G1 (Alternative schedule costs). Fix η = eL and count attested digests beyond the BUD, amortized per block. (i) One SuperBUD size m. The digest rate is 1/m, archive growth is at most twice the write log, and a cover uses √ at most ⌊d/m⌋ + 2(m − 1) windows. This bound is minimized at m = Θ( d).
28
A. Ranchal-Pedrosa et al.
(ii) φ-phase schedule. The digest rate is φ(1 − e−L )/(e − 1) and archive growth is at most φ(L + 1) times the write log. All aligned windows remain available. Writing q = ⌈e/φ⌉, if φ ≥ 2 and 1 ≤ d ≤ (e − q)η/e, every a admits a e2 committed window of size less than e−q d that contains [a, h] and closes fewer than that many blocks after h. (iii) Per-block sliding. The digest rate is L, worst-case archive growth is Θ(η) times the write log, and worst-case build work is Θ(wη) per block. Once h ≥ H0 + η − 1, every 1 ≤ d ≤ eL admits a two-digest certificate with no wait beyond attestation. Proof. (i) Use at most m − 1 BUDs before the first size-m boundary, ⌊d/m⌋ complete SuperBUD windows, and at most m − 1 BUDs in the tail. Every window closes by h, and a write √ enters at most one fixed-size span map. Minimizing the bound gives m = Θ( d). (ii) A level-ℓ window beginning at a multiple of eℓ−1 is the disjoint union of e aligned level-(ℓ − 1) windows. Level ℓ closes φ windows every eℓ blocks, and a write appears in at most φ maps at that level, giving the stated digest and archive rates. Let E = eℓ . The gap between committed starts is at most qE/e, while a window of size E covers [a, h] when its start lies in [h − E + 1, a], an interval of E − d possible starts. A committed start exists whenever E − d ≥ qE/e, or e E ≥ e−q d. For φ ≥ 2 we have q < e, and the stated bound on d ensures that E = η satisfies the inequality. The least configured power of e satisfying it is e2 below e−q d, with the same asymptotic closing delay. (iii) A height belongs to eℓ sliding windows at level ℓ, giving worst-case archive growth Θ(eL ) = Θ(η), attained when writes use distinct keys. Closing every level P at every height costs O(w ℓ≤L eℓ ) = O(wη) per block, with the same worst-case tightness. Repeated writes to a small key set can cost less. For E = e⌈loge d⌉ , the size-E window ending at h either equals (a, h] and supplies one exclusion path, or contains a and supplies one inclusion path for k 7→ a. The window exists only if h − E + 1 ≥ H0 , which is guaranteed after the stated ramp-up. Earlier queries can use the staircase or individual BUD exclusions.
Choosing the schedules. Committing one SuperBUD size minimizes the digest rate, but its cover grows linearly with d once m is fixed. Per-block sliding gives two-digest proofs after ramp-up without waiting, but its worst-case Θ(wη) build cost rules it out for the validator path. The φ-phase family lies between these extremes. Aligned schedule (φ = 1) is cheapest, but an anchor immediately below a boundary can miss every covering window. For φ ≥ 2 and d ≤ (e − ⌈e/φ⌉)η/e, a window of size O(d) covers [a, h] and closes within O(d) blocks. Either that window yields S4 or an earlier rewrite yields S3. Within this configured reach, φ = 2 is the cheapest bounded-wait schedule; its digest rate remains below one per block for e ≥ 3. Section 6.4 measures aligned schedule, full striding, and the one-size baseline. Sliding is evaluated analytically.
You’ve Got a BUD in Me
H
29
Evaluation details
The main results rely on three checks: every backend replays the same blocks, every applicable proof strategy is built for each sampled query, and QMDB’s reclamation is verified to be active before its cost is compared. This appendix gives those checks and the full results behind Section 6.
H.1
Systems, workloads, and sampling
All backends implement one replay interface. bud applies writes to flat state and builds the BUD, rather than measuring commitment alone. The in-memory mpt is simplified and omits RLP and Ethereum’s separate account and storage tries, deliberately favoring it; the disk version is content addressed and capped at a 16 MiB cache. NOMT and QMDB retain their defaults. QMDB reclamation does not activate under those defaults in our runs; Section H.7 lowers only its live-entry threshold in a separately marked experiment. The prototype implements flat-state replay, previous-write pointers, BUD and SuperBUD construction, and hash-path certificate checks. Initial-state activation, the specified digest domain separation and canonical tree encoding, and end-toend attestation verification are not implemented. Certificate checks trust the supplied digests; the BLS benchmark below measures signatures separately. The results characterize construction cost and proof shape under the implemented encoding. They do not constitute an integrated implementation of the full formal protocol. Each commitment-sweep point prepopulates N keys and times 128 complete block replays, including state application and commitment but excluding attestation, signing, and certificate generation. We report p50 with p99 whiskers. Runs use an Apple M4 with 16 GB RAM. Certificate and hierarchy experiments run for 6η blocks, so every level closes repeatedly; their verification timings cover warm hash paths. In a separate BLS12-381 benchmark, a client using preaggregated keys for 67 of 100 authenticated signers spent about 0.65 ms on the two batch-verified aggregate signatures for S3 or S4. Committee authentication and signer-key aggregation are outside that timed operation. The synthetic certificate workload uses N = 105 keys and w = 50 distinct writes per block, sampled from a Zipf distribution with s = 1. It runs for 6η = 98,304 blocks with η = 16,384, e = 4, L = 7, and a 2% deletion rate. For every sampled anchor and staleness d, we build every applicable strategy rather than only the cheapest. Event sampling draws a replay event, either a synthetic modification or an account occurrence in the Ethereum trace, and therefore weights keys by their observed frequency. Uniform-key sampling first draws uniformly from keys observed in the workload and then selects one of that key’s events. The latter gives rarely recurring keys equal weight without assuming that client queries follow the event distribution.
30
A. Ranchal-Pedrosa et al.
Ethereum account-access trace. We replay 24,576 blocks spanning approximately 3.4 days, from height 25,800,000 through 25,824,575. It uses η = 4,096, e = 4, and L = 6. From public RPC data we mark transaction senders and recipients, fee and withdrawal recipients, created contracts, and log-emitting contracts, and replay each distinct marked account as one putative account write. The trace contains an average of 445 distinct marked accounts per block. This construction captures observed account access, with two limits. First, a marked account need not have changed, while an account changed through unobserved internal execution need not be marked. Second, the RPC data omits storage-slot writes, account deletions, and post-execution values. It therefore does not supply the execution-complete block-level access list specified by EIP-7928 [33]. Our Ethereum results measure how this observed account sequence affects path depth, recurrence gaps, and strategy availability. They do not estimate full-EVM write volume, deletion behavior, or end-to-end client cost. Only the synthetic workload exercises tombstone anchors and S2. Addresses are mapped injectively to dense identifiers for replay indexing. This preserves equality patterns, per-block distinct-account counts, and recurrence gaps, and hence the strategy-availability statistics and the path depths of our balanced positional Merkle trees. It does not purport to preserve native address serialization, production Patricia-trie shape, or database locality. Moreover, the reported byte totals serialize the benchmark’s fixed-width record representation, not native Ethereum account and storage keys. The Ethereum trace’s certificate sizes should therefore be read as hash-path costs under that representation, rather than production Ethereum wire sizes; native-width keys change the explicit opened-leaf payload but not the number of path hashes.
H.2
Certificate costs
For the read-layer payload defined in Section 5.3, the synthetic workload’s S1 and S2 cost 219–227 bytes, and S3 remains at 452–454 bytes, and S4 grows from 515 to 790 bytes as its SuperBUDs contain more keys. S5 grows logarithmically from 901 to 11,984 bytes. Every S5 exclusion count satisfies Equation (2); warm hash-path verification reaches at most 146 µs at p99. Under the same benchmark record encoding, our prototype mpt produces a 2,087-byte inclusion proof for the easier current-value query. S3 and S4 remain below that size, while S5 exceeds it at larger staleness. On the Ethereum trace, S3 costs 677–710 bytes. Its larger per-block markedaccount sets produce deeper BUD paths than the synthetic workload, as predicted by the O(log wn ) anchor cost in Section 5.2. At d = 64, the mean S5 cover is approximately 5.5 windows in both workloads and under both sampling rules (Table 3). Write history therefore changes which strategy applies much more than it changes cover size at a fixed staleness.
You’ve Got a BUD in Me
31
Table 3. Workload comparison at matched staleness. Strategy shares name the cheapest applicable strategy; S4 availability counts S4 whenever it exists. All listed stalenesses lie below both retention windows.
S3 share at d = 1 S4 share at d = 1 S4 availability at d = 512 S5 windows at d = 64
Write-event sampling
Uniform-key sampling
synthetic
Ethereum
synthetic
Ethereum
97.0% 3.0% 69.2% 5.55
79.0% 21.0% 82.3% 5.52
84.2% 15.8% 84.6% 5.47
28.4% 71.5% 88.5% 5.61
Q3: realized cheapest-first strategy mix vs staleness d, by anchor-sampling family family: uniform_key family: write_event
1.0
1.0
0.4
64 12 8 25 6 51 2 10 24 20 48 40 96 81 9 16 2 38 32 4 76 65 8 53 6
staleness d
1
0.0
4
S3 (double BUD) S4 (single SuperBUD) S5 (staircase)
0.2
64 12 8 25 6 51 2 10 24 20 48 40 96 81 9 16 2 38 32 4 76 65 8 53 6
8 16 32
1
0.0
4
S3 (double BUD) S4 (single SuperBUD) S5 (staircase)
0.2
0.6
8 16 32
0.4
2
fraction of queries
0.8
0.6
2
fraction of queries
0.8
staleness d
Fig. 6. Cheapest applicable strategy by staleness on the synthetic workload (η = 16,384, e = 4, L = 7, w = 50), under uniform-key sampling (left) and event sampling (right).
H.3
Strategy availability
Figures 6 and 7 report the cheapest applicable strategy. These shares differ from S4 availability in Figure 4(b), which counts every query for which S4 exists, even when another strategy is cheaper. On the synthetic workload, S3 serves most queries at d = 1. S4 is more useful for keys without a nearby successor; its availability falls with staleness from 90.6% to 32.9% under event sampling and from 99.9% to 42.9% under uniform-key sampling. The Ethereum trace contains a much larger population without observed successors. Repeated appearances have a median gap of 8 blocks, yet 50.4% of its 1.68 million marked accounts appear only once. That fraction describes the 3.4-day observation window, not a steady state; a longer trace may reveal later writes. Under uniform-key sampling on the Ethereum trace, S4 is the most common strategy at every sampled d < η and retains a majority through d = 2,048. At d ≥ η, S4 availability reaches zero because no configured level spans the interval. This does not rule out a proof: the anchor at a remains valid (Section 5.1), and S5 remains available from archived digests.
32
A. Ranchal-Pedrosa et al. Q3: strategy mix vs staleness d on the recorded Ethereum trace, by anchor-sampling family family: uniform_key family: write_event 1.0
1.0
0.8 0.6 0.4
staleness d
64 12 8 25 6 51 2 10 24 20 48 40 96 81 92 16 38 4
8 16 32
S3 (double BUD) S4 (single SuperBUD) S5 (staircase)
1
64 12 8 25 6 51 2 10 24 20 48 40 96 81 92 16 38 4
8 16 32
0.0
4
0.2
0.0
2
0.2
4
0.4
2
fraction of queries
S3 (double BUD) S4 (single SuperBUD) S5 (staircase)
0.6
1
fraction of queries
0.8
staleness d
Fig. 7. Cheapest applicable strategy by staleness on the Ethereum account-access trace (η = 4,096, e = 4, L = 6, w ≈ 445), under uniform-key sampling (left) and event sampling (right). Accounts observed only once favor S4 over S3 under uniform-key sampling. Table 4. Hierarchy trade-offs at η = 4,096 and d ∈ [64, 128), with w = 50. Extra digests exclude the mandatory BUD; block p99 covers state updates, BUD construction, and hierarchy maintenance; S5 windows is the mean cover size over queries in the stated staleness range.
H.4
(e, L)
Block p99 Extra S5 digests/blk (µs) windows
S4 avail.
(2, 12) (4, 6) (8, 4)
0.999756 0.333252 0.142822
79.9% 76.5% 69.8%
2,485.8 1,517.9 1,235.0
4.51 6.01 8.52
Hierarchy parameters
The sweep in Table 4 fixes N = 105 , w = 50, η = 4,096, and d ∈ [64, 128), and runs each configuration for 6η blocks. Larger e means fewer maintained levels. In every run, the measured digest rate equals (1 − e−L )/(e − 1) to the reported precision, and every S5 exclusion count satisfies Equation (2). H.5
Skew sensitivity
We repeat the synthetic experiment with s ∈ {0.8, 1, 1.2} at (e, L) = (4, 6). Across all queries, mean S5 size changes by 35%, largely because greater skew produces fresher anchors. Restricting the comparison to d ∈ [64, 128) reduces the variation to 5.6%; the mean cover remains between 5.98 and 6.01 windows. Skew therefore changes anchor age much more than proof cost at a fixed staleness. H.6
Schedule sweep
The schedule comparison in Table 5 replays the same two 4,096-block traces under the aligned schedule, full striding, and one SuperBUD size m = 64. The synthetic trace has w = 50; the Ethereum segment averages w ≈ 478. We do not benchmark φ = 2 separately because its bounded-wait guarantee follows from
You’ve Got a BUD in Me
33
Table 5. Schedule comparison over one 4,096-block replay, at η = 4,096 and e = 4, √ with the single level sized m = 64 = η. Within each workload, all schedules replay the same trace. Extra digests exclude the mandatory BUD. S4 availability is measured at query time. Wait is in blocks, and its median includes only queries for which S4 becomes available before the replay ends.
Schedule
Extra Archive S5 windows digests/blk B/blk p50/p99
S4 avail.
Wait p50 (blocks)
Synthetic Zipf trace (w = 50) φ = 1 (aligned) 0.3333 4,252 φ = e (strided) 1.3286 11,810 Single level 0.0156 1,959
4/12 4/12 13/71
83.7% 96.0% 46.1%
14 2 23
Ethereum trace, first η blocks (w ≈ 478) φ = 1 (aligned) 0.3333 41,904 φ = e (strided) 1.3286 110,813 Single level 0.0156 20,215
4/12 4/12 10/72
83.3% 96.6% 39.6%
14 2 22
Lemma G1(ii). Per-block sliding remains analytical because its worst-case build work is Θ(wη). S4 availability in Table 5 is aggregated over log-uniform valid historical queries at the head of a one-window replay and is not directly comparable with the per-staleness values in Figure 4(b). For each retained anchor, the sampler records its first later modification, rejects a draw that crosses that successor or the replay head, and verifies the complete staircase certificate. Wait medians include only queries for which S4 appears before the replay ends; queries still waiting are excluded. These conditions apply equally to all three schedules. H.7
QMDB reclamation under forced activation
The short commitment sweeps leave a central maintenance question unanswered: what happens when QMDB reclaims its append-only files? It moves live entries out of superseded regions in per-shard updater threads on which block completion waits. This coupling motivates the experiment; its latency cost must be measured. We test QMDB v0.2.0, commit f14a2a0. Its default live-entry gate is 20·106 entries per shard, roughly 3.2·108 keys across 16 evenly populated shards, and is checked before the utilization rule. Our runs reach only N = 107 . We track the oldest-active serial-number and last-pruned twig watermarks, which remain flat under the default configuration. QMDB’s published evaluation includes much larger insertion workloads [36]; our experiment isolates reclamation under the stated configuration and deletion workload, without claiming to reproduce that scale. We replay 20,000 blocks from a state of N = 107 keys, with w = 2,000 writes per block and 2% deletions. Cumulative writes turn the state over four times; each configuration runs twice on the same trace. BUD collects tombstones at η = 4,096. Under QMDB’s defaults, reclamation watermarks remain flat across
34
A. Ranchal-Pedrosa et al. Q7: steady-state tail (R1, blocks with T >= 1) 100
103
10−1 P(block time > x)
per-block wall time (ms, log scale)
Q7: per-block wall time vs block (R1) BUD QMDB (defaults, compaction dormant) QMDB (compaction active, non-default threshold) turnover T = 1
102
10−2 10−3
101
10−4 0
2500
5000
7500
10000 12500 measured block
15000
(a) Per-block wall time.
17500
20000
BUD QMDB (defaults, compaction dormant) QMDB (compaction active, non-default threshold)
101 102 per-block wall time (ms, log scale)
103
(b) Steady-state tail.
Fig. 8. Long-run replay at N = 107 , w = 2,000, and 2% deletions over 20,000 measured blocks. QMDB’s default reclamation remains inactive. Lowering the live-entry threshold to force reclamation changes latency by less than the between-repetition range but yields 2.6× greater database-file growth. The base-BUD replay is shown only for context: unlike QMDB’s complete authenticated storage engine, it excludes SuperBUD maintenance, attestation, and signing.
all 40,000 measured blocks, confirming that no reclamation occurs. Steady-state QMDB cost is 51.2 µs per write, against 17.2 µs at the same w in Figure 3(b). Since reclamation watermarks remain flat, the difference cannot be attributed to reclamation; the compared points also differ in state size. The base-BUD path is 1.1 µs per write, but that is not a functionally matched full-system comparison. To measure active reclamation, we lower the threshold to 5·105 entries per shard, the only non-default setting. QMDB’s utilization rule then activates reclamation during prepopulation, and it continues throughout the replay: the summed oldest-active serial-number watermark advances by 1.07·108 and the pruning watermark by roughly 56,000 twigs per repetition. The serial-number delta bounds retired entries; it is not a direct count of live-entry relocations. Its steady-state cost is 48.7 µs per write, within the inactive configuration’s 5.7% between-run spread. Per-block p99.9 is 0.63–0.84 s with reclamation active, against 0.74–0.88 s when inactive. The clearest measured difference is database-file growth. The active run grows by 7.2 GiB, against 2.7 GiB when inactive, and ends at 8.6 GiB rather than 4.0 GiB. These deltas measure database files retained on disk. Physical device writes were not instrumented, so the result establishes greater file growth rather than device-level write amplification. Heavy per-block tails appear in both QMDB configurations and in the BUD replay, so these data do not attribute the tails to reclamation. Steady-state p99.9 exceeds p50 by 7–10× for QMDB and by 13× for the base-BUD path. Rerunning the dense point from Figure 3(b) at N = 107 for 400 blocks of 105 writes gives 29.6 µs per write, again with flat reclamation watermarks. The improvement relative to QMDB’s smaller-batch run is consistent with amortization of per-block overhead; it is not evidence about reclamation cost.
You’ve Got a BUD in Me
35
At N = 107 , QMDB amortizes active reclamation without a detectable latency penalty, while its database files grow faster. This supports the main text’s storage tradeoff and limits its performance claim: relocation shares the block-completion path, but we have not shown that it becomes a bottleneck. The open measurement is sustained reclamation near the default live-entry gate, where both latency and storage behavior may differ.
I
Deployment
Activation. The activation procedure in Section 5.3 requires consensus rules for chunk assignment, scan order, and the ordering of synthetic and ordinary writes within a block. Every inherited entry starts with marker uninit. An activation write preserves the current value and emits that marker; an ordinary write that activates the key first makes the scan skip it. Neither first record may carry −1. The implementation must retain activation status or postpone tombstone collection until the scan considers the key, so a previously activated key is not mistaken for an untouched one. Choosing chunks of roughly the normal per-block write volume keeps activation work comparable to ordinary traffic. For example, at N = 108 and w = 2·104 , one such pass takes approximately 5,000 blocks; the configured hierarchy then needs at most one top-level window to reach its post-activation steady state. A key’s first record can anchor claims from that record’s height onward. Its uninit marker cannot establish the key’s value at any earlier height. Lazy activation avoids the scan: a legacy key activates on its first later ordinary write or touch, which likewise emits uninit. This leaves untouched members of σ0 outside the anchored query domain indefinitely, so lazy activation has no finite cutover time and cannot answer their earlier reads. Optional checkpoints. The construction needs no standalone state root. A deployment may still attest periodic snapshots for state sync or as a current-state bridge anchor. A usable snapshot contains the live state, the per-entry metadata of Section 4.1, and either the open hierarchy or enough recent logs to rebuild it. It does not replace the modification history required for historical queries. Archive incentives. The availability assumption is stated in Section F. Replication, sharding, payments, and availability bonds are deployment choices; keeping every key range retrievable remains open. Migration and rollback. A migration may run the trie and BUDs together. After a complete activation scan, allow at most another eL ≤ η blocks for hierarchy construction. Cutover replaces proofs for anchored queries once their evidence is available; never-written absent keys remain outside Q, and earlier heights can use archived roots. Lazy activation has no finite cutover deadline. Rollback reconstructs the trie from flat state and runs both systems while new trie roots accumulate.