Paper 2016/683

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

Rasmus Dahlberg, Tobias Pulls, and Roel Peeters


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 being authenticated---and full (concrete) security in the multi-instance setting.

Note: This article is the final version submitted by the authors to NordSec.

Available format(s)
Publication info
Published elsewhere. MINOR revision.To appear in NordSec 2016
authenticated data structure
Contact author(s)
rasmus gd dahlberg @ gmail com
2016-08-31: last of 2 revisions
2016-07-12: received
See all versions
Short URL
Creative Commons Attribution


      author = {Rasmus Dahlberg and Tobias Pulls and Roel Peeters},
      title = {Efficient Sparse Merkle Trees: Caching Strategies and Secure (Non-)Membership Proofs},
      howpublished = {Cryptology ePrint Archive, Paper 2016/683},
      year = {2016},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.