Sparse Merkle Tree

1. 引言

前序博客有：

• Merkle tree及其在区块链等领域的应用
• Merkle tree proof

2. Merkle tree

Merkle tree可看成是对一组数据的密码学承诺，类似：

2.1 Merkle tree包含证明

如需证明A包含在上述树中，仅需要发送A, H(B), H(H(H(C)+H(D)))，验证root哈希能否匹配即可。

2.2 Merkle tree不包含证明

Merkle tree很容易进行包含证明，但不容易实现“不包含”证明，除非公开整棵树的内容，但这违背了使用Merkle tree的初衷。

3. Sparse Merkle tree

Sparse Merkle tree与标准Merkle tree类似，但是Sparse Merkle tree的data是带索引的，且每个datapoint会放入 datapoint索引 对应的叶子节点。

假设某Merkle tree有4个叶子节点，对该树填充(A, D)。由于A为字母笔的首字母，放于第一个叶子节点处，D放在第4个叶子节点处。而对于第2个和第3个叶子节点，将保持为空，实际实现时，会设置特殊值（如null）：

3.1 Sparse Merkle tree包含证明

Sparse Merkle tree包含证明 与上面的Merkle tree包含证明类似：
为证明A在树中，仅需要提供A、H(null)、H(H(null)+H(D))即可。

3.2 Sparse Merkle tree不包含证明

如需证明C不在上面的sparse merkle tree中，将很简单：
因C若在树中，其应在第3个叶子节点，若不在树中，第3个叶子节点必须为null。

不包含证明即为：以标准merkle证明第3个叶子节点是null，仅需提供null、H(D)、H(H(A)+H(null))。

sparse Merkle tree的最大特点在于：其确实在Merkle tree中代表了key-value stores。

4. Sparse Merkle tree的缺点

Sparse Merkle tree的最大优点在于：可提供高效不包含证明。
但是，这也意味着sparse Merkle tree将非常非常大，26个字母看起来不多，但大多数时候处理的是$2^{256}$哈希值，手工构建这样的sparse merkle tree需要太多的索引。

2016年论文Efficient Sparse Merkle Trees——Caching Strategies and Secure (Non-)Membership Proofs等技术 可高效生成Merkle tree。但这些技术的关键在于 巨大sparse merkle tree 大多数情况下是系数的。H(null)为常量值，H(H(null))也是常量值，以此类推等等。因此可缓存树的大多数部分。

5. Sparse Merkle tree应用场景

Plasma Cash使用sparse Merkle tree来存储deposited assets信息。每种Plasma Cash asset都有唯一的ID。当某资产转移给某新用户时，会在spare Merkle tree中相应的asset索引中包含一笔交易。然后使用“包含证明”（或“不包含证明”）来证明 某特定历史交易是有效的。

参考资料

[1] 2018年博客 What’s a Sparse Merkle Tree?