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: ia.cr/2016/683
Discussion forum: Show discussion | Start new discussion
[ Cryptology ePrint archive ]