Paper 2016/683

Efficient Sparse Merkle Trees: Caching Strategies and Secure (Non-)Membership Proofs

Rasmus Dahlberg and Tobias Pulls and Roel Peeters

Abstract

A sparse Merkle tree is an authenticated data structure based on a perfect Merkle tree of intractable size. It contains a distinct leaf for every possible output from a cryptographic hash function, and can be simulated efficiently because the tree is sparse (i.e., most leaves are empty). We are the first to provide complete, succinct, and recursive definitions of a sparse Merkle tree and related operations. We show that our definitions enable efficient space-time trade-offs for different caching strategies, and that verifiable audit paths can be generated to prove (non-)membership in practically constant time~($<4$~ms) when using SHA-512/256. This is despite a limited amount of space for the cache---smaller than the size of the underlying data structure---and full security in the multi-instance setting.