Cryptology ePrint Archive: Report 2018/955

Compact Sparse Merkle Trees

Faraz Haider

Abstract: A Sparse Merkle tree is based on the idea of a complete Merkle tree of an intractable size. The assumption here is that as the size of the tree is intractable, there would only be a few leaf nodes with valid data blocks relative to the tree size, rendering the tree as sparse. We present a novel approach called Minimum distance path algorithm to simulate this Merkle tree of intractable size which gives us efficient space-time trade-offs. We provide the algorithms for insertion, deletion and (non -) membership proof for a leaf in this Compact Sparse Merkle tree.

Category / Keywords: implementation / zero knowledge, hash functions

Original Publication (in the same form):

Date: received 8 Oct 2018

Contact author: haider faraz at outlook com

Available format(s): PDF | BibTeX Citation

Version: 20181009:160729 (All versions of this report)

Short URL:

[ Cryptology ePrint archive ]