什么是稀疏默克尔树（Sparse Merkle Tree）

短命女 2022-11-05 11:49 193阅读 0赞

### 文章目录 ###

*  什么是默克尔树（Merkle Tree）
 *   *  默克尔树的存在证明
     *  默克尔树的不存在证明
 *  什么是稀疏默克尔树（Sparse Merkle Tree）
 *   *  稀疏默克尔树的存在证明
     *  稀疏默克尔树的不存在证明

# 什么是默克尔树（Merkle Tree） #

稀疏默克尔树（Sparse Merkle Tree）  
参考URL: https://blog.csdn.net/hello2mao/article/details/103399776

Merkle 树的叶子是数据块的 hash 值。非叶节点是其对应子节点串联字符串的 hash。

如下图所示，A、B、C、D是数据块，H()代表哈希函数。

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2ludGhhdA_size_16_color_FFFFFF_t_70]’

## 默克尔树的存在证明 ##

默克尔树的存在证明，也叫做**默克尔证明，这些证明能够表明一个叶节点是默克尔树的一部分。**

例如，为了证明数据A（严格来说是A的哈希H(A)）存在于此默克尔树中，只需要给出H(B)和H(H©+H(D))，就可以计算出根哈希，然后和原根哈希一比较即可。

## 默克尔树的不存在证明 ##

不太容易实现。

# 什么是稀疏默克尔树（Sparse Merkle Tree） #

稀疏默克尔树（Sparse Merkle Tree，SMT）与默克尔树基本类似，**只是数据是有序的。**

例如有一个四个叶子节点的SMT，然后有数据A和D，那么这SMT如下：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2ludGhhdA_size_16_color_FFFFFF_t_70 1]可以看到，A和D被有序的放到了索引是0和3的位置，而所以是1和2的位置是null。

## 稀疏默克尔树的存在证明 ##

与默克尔树的存在证明一致，只需要给出H(null)和H(H(null)+H(D))。

且SMT的值可以在O(log(n)) 时间内进行更新、插入或删除操作。

## 稀疏默克尔树的不存在证明 ##

与默克尔树最大的区别在于，稀疏默克尔树可以方便的实现不存在证明。

例如需要证明C不存在，**那么只需证明索引3处是null即可，也就转化为常规的默克尔证明，只需给出H(H(A)+H(null))和H(D)**，如下图所示：

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2ludGhhdA_size_16_color_FFFFFF_t_70 2]

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2ludGhhdA_size_16_color_FFFFFF_t_70]: /images/20221023/3ba70224188f4b32b96712d55b67442d.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2ludGhhdA_size_16_color_FFFFFF_t_70 1]: /images/20221023/9b771b19900c49c58b9543d42dc5e49d.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2ludGhhdA_size_16_color_FFFFFF_t_70 2]: /images/20221023/9a83b2ee048341779d5e2cbc22215654.png