Efficient Sparse Merkle Trees - Caching Strategies and Secure (Non-)Membership Proofs
Efficient Sparse Merkle Trees - Caching Strategies and Secure (Non-)Membership Proofs
复制标题
高效的稀疏 Merkle 树 - 缓存策略和安全（非）会员证明
DOI：
10.1007/978-3-319-47560-8_13
复制
发表时间：
2016
期刊：
影响因子：
--
通讯作者：
R. Peeters
中科院分区：
文献类型：
--
作者：
Rasmus Dahlberg;T. Pulls;R. Peeters
稀疏Merkle树是一种基于难以处理大小的完美Merkle树的认证数据结构。对于来自密码散列函数的每个可能的输出，它包含不同的叶，并且可以有效地模拟，因为树是稀疏的(即，大多数叶是空的)。我们是第一个为稀疏Merkle树和相关操作提供完整、简洁和递归定义的公司。我们证明了我们的定义能够对不同的缓存策略进行有效的时空折衷，并且当使用SHA-512/256时，可以生成可验证的审计路径来在几乎恒定的时间(<；4ms)内证明(非)成员资格。这是尽管缓存的空间有限(小于正在进行身份验证的底层数据结构的大小)，并且在多实例设置中具有完全(具体)的安全性。
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.