Welcome to the resource topic for 2021/038
Title:
Streaming Merkle Proofs within Binary Numeral Trees
Authors: 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.
ePrint: https://eprint.iacr.org/2021/038
See all topics related to this paper.
Feel free to post resources that are related to this paper below.
Example resources include: implementations, explanation materials, talks, slides, links to previous discussions on other websites.
For more information, see the rules for Resource Topics .