Paper 2021/038

Streaming Merkle Proofs within Binary Numeral Trees

Luke Champine

Abstract

We describe the binary numeral tree—a type of binary tree uniquely suited to processing unbounded streams of data—and present a number of algorithms for efficiently constructing and verifying Merkle proofs within such trees. Specifically, we present existence proofs for single leaves, for a contiguous range of leaves, and for multiple disjoint ranges. We also introduce Merkle "diff" proofs, which assert that an arbitrary modification was correctly applied to an existing tree. Each algorithm, operating on a tree with $n$ leaves and $k$ disjoint proof ranges, requires $\mathcal{O}(\log_2(n))$ space and $\mathcal{O}(n)$ time, and yields proofs of size $\mathcal{O}(k\log_2 (n))$. Furthermore, each algorithm operates in streaming fashion, requiring only a single in-order pass over the leaf data.

Metadata
Available format(s)
PDF
Category
Implementation
Publication info
Preprint. MINOR revision.
Keywords
merkle proofsstreaming
Contact author(s)
luke @ sia tech
History
2021-01-12: received
Short URL
https://ia.cr/2021/038
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2021/038,
      author = {Luke Champine},
      title = {Streaming Merkle Proofs within Binary Numeral Trees},
      howpublished = {Cryptology ePrint Archive, Paper 2021/038},
      year = {2021},
      note = {\url{https://eprint.iacr.org/2021/038}},
      url = {https://eprint.iacr.org/2021/038}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.