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

Category / Keywords: authenticated data structure

Original Publication (with minor differences): To appear in NordSec 2016

Date: received 7 Jul 2016, last revised 31 Aug 2016

Contact author: rasmus gd dahlberg at gmail com

Available format(s): PDF | BibTeX Citation

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

Version: 20160831:073914 (All versions of this report)

Short URL:

Discussion forum: Show discussion | Start new discussion

[ Cryptology ePrint archive ]