You've Got a BUD in Me: Authenticated Reads from Per-Block Write Logs
Researchers propose BUD, per-block write-log digests enabling blockchain validators to serve historical membership and exclusion proofs far cheaper than state-wide tries.
The paper introduces Block Update Digests (BUD), which authenticate each block's write log with predecessor pointers, plus a SuperBUD and exponential hierarchy to turn long unchanged intervals into short proofs. Soundness against adversarial provers and up to f Byzantine validators is proven under archive, attestation, and committee evidence assumptions. Benchmarks show a 50x state-size increase raises the base-BUD path only 1.24x versus 3.1x for in-memory and 69.5x for disk-backed Merkle Patricia tries, with read payloads below 800 bytes and p99 warm verification at 146 microseconds.
- BUD authenticates per-block write logs instead of whole-state structures
- Supports historical membership and exclusion proofs with logarithmic digest counts
- Proved sound against adversarial provers and f Byzantine validators
- 1.24x path growth at 50x state size vs 69.5x for disk-backed MPT
- Read payloads under 800 bytes; 146 microseconds p99 warm verification
Full article167 words · extracted from arxiv.org · click to collapse
Blockchains usually pay for authenticated reads by maintaining a structure that spans the entire state. We show how validators can support historical membership and exclusion proofs by authenticating each block's writes instead. A Block Update Digest (BUD) commits a write log whose predecessor pointers link successive modifications of each key. A SuperBUD summarizes last writes over a window; an exponential hierarchy turns long unchanged intervals into short proofs. The digest count is logarithmic in the gap within the hierarchy's range, with one additional digest per top-level window beyond it. We prove soundness against adversarial provers and up to f Byzantine validators, and completeness for queries anchored by a post-deployment modification, assuming archive, attestation, and committee evidence is available. Across a 50x increase in state size, the measured base-BUD path rises by 1.24x, compared with 3.1x and 69.5x for in-memory and cache-bounded disk-backed Merkle Patricia tries. On the synthetic trace, two-digest read-layer payloads stay below 800 bytes, and warm hash-path verification takes at most 146 microseconds at p99.
Text extracted automatically; images, tables and formatting may be missing. Original: https://arxiv.org/abs/2609.11251