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 e
You've Got a BUD in Me: Authenticated Reads from Per-Block Write Logs is a research paper proposing a protocol that replaces global authenticated state trees with per-block write log digests called Block Update Digests (BUDs). This approach allows validators to support historical membership and exclusion proofs by authenticating each block's writes individually, rather than maintaining a structure spanning the entire state.
The protocol uses a Block Update Digest (BUD) to commit a key-sorted write log with predecessor pointers, and a SuperBUD to summarize last writes over a window. An exponential hierarchy of SuperBUDs enables interval-exclusion proofs with size logarithmic in the gap, drastically reducing construction costs. Key benefits include:
The paper argues that this method provides a principled alternative to state-spanning authenticated dictionaries, with formal proofs of soundness and completeness under standard cryptographic assumptions and honest-validator integrity.
The paper addresses a persistent scalability issue in blockchain light-client design: authenticated reads are normally backed by a global state structure, such as a Merkle tree or Merkle Patricia trie, that must be maintained and updated across the entire key/value state. As state grows, the cost of producing and verifying state proofs can become a bottleneck, and historical proofs are especially expensive because they often require access to old state roots or snapshots. The authors instead propose a write-centric design in which validators commit to the modifications made in each block and derive proofs from those per-block update logs.
At the core of the design is the Block Update Digest, or BUD, a commitment to a block’s write log. Each write entry is linked to the previous write for the same key via a predecessor pointer, forming a versioned chain of updates. This lets a verifier reason not only about the value written in a particular block, but about the evolution of a key across blocks. A SuperBUD then summarizes the latest writes over a window of blocks, compressing the history into a compact structure that can support membership and exclusion proofs for the state at the end of that window. The result is a proof system that can answer historical read queries without requiring a full snapshot of the global state for every queried block.
This matters because it separates the cost of authenticated reads from the size of the entire state and offers a more natural fit for blockchains with large, continuously evolving state. By anchoring proofs to per-block writes and window-level summaries, the design may reduce validator overhead, improve the efficiency of light clients and archival nodes, and make historical queries more practical for off-chain applications. More broadly, the work suggests that state verification does not have to be organized around a monolithic state tree; a versioned write log with layered summaries can provide a scalable alternative for membership, exclusion, and historical consistency proofs.