Blockchain validators enable efficient historical data proofs with write logs

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

Cryptography and SecurityDatabasesDistributed, Parallel, and Cluster Computing

Summary

Blockchain systems need a way to prove that data was or wasn’t part of their history, which usually costs extra computational work over all stored data. The authors propose a way for participants called validators to prove past states by only focusing on the changes each new block made, instead of tracking the whole dataset. They introduce structures called Block Update Digests (BUDs) that link successive changes to data keys, and a hierarchy that lets proofs stay small and quick even if data hasn’t changed for a long time. Their approach reduces proof sizes and verification times significantly compared to other common methods, making it more efficient for blockchains to provide historical proofs.

What this means in practice

  • For blockchain engineers: Create lightweight historical proofs of data existence and non-existence on blockchains without maintaining full state structures.
  • For distributed ledger operators: Improve validator efficiency and reduce proof sizes when processing and verifying historical blockchain states over long periods.

Authors

Alejandro Ranchal-Pedrosa, Cody Littley, Ben Marsh

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 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.
View PDFOpen arXiv