Cryptology ePrint Archive: Report 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.

Category / Keywords: implementation / merkle proofs, streaming

Date: received 10 Jan 2021

Contact author: luke at sia tech

Available format(s): PDF | BibTeX Citation

Version: 20210112:075915 (All versions of this report)

Short URL: ia.cr/2021/038


[ Cryptology ePrint archive ]