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
- Tags
- authenticated-data-structuresblockchainbyzantine-fault-tolerancecryptographic-proofsdistributed-systemsmerkle-tree
- Products
- Block Update Digest (BUD)
From the original article
1 min read at arxiv.orgBlockchains 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.
By Alejandro Ranchal-Pedrosa · arxiv.org
A short excerpt; the article and its images belong to the publisher. Summary, key facts and assessment above are AI-written from the article and can be wrong.