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

Rasmus Dahlberg; Tobias Pulls; Roel Peeters

Paper 2016/683

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

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

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

Metadata

Available format(s): PDF
Publication info: Published elsewhere. Minor revision. To appear in NordSec 2016
Keywords: authenticated data structure
Contact author(s): rasmus gd dahlberg @ gmail com
History: 2016-08-31: last of 2 revisions; 2016-07-12: received; See all versions
Short URL: https://ia.cr/2016/683
License: CC BY

BibTeX

@misc{cryptoeprint:2016/683,
      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},
      url = {https://eprint.iacr.org/2016/683}
}