Paper 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.