图解默克尔树

胡键
更新于 2020-02-04 17:36
阅读 3340

iden3.io 的 blog 最近发表了一篇关于默克尔树的图解文章，相当不错，特摘取了文章的图解部分。

[原文链接](https://blog.shifudao.com/posts/2020-02/%E5%9B%BE%E8%A7%A3%E9%BB%98%E5%85%8B%E5%B0%94%E6%A0%91.html)

[iden3.io 的 blog]([Blog](https://blog.iden3.io/) 最近发表了[一篇关于默克尔树的图解文章](https://blog.iden3.io/merkle-trees-visual-introduction.html)，相当不错，特摘取了文章的图解部分。

## 默克尔树规范

![image.png](https://img.learnblockchain.cn/2020/02/05_/232214195.png)

包含数据的区块组成了树的叶子。

![image.png](https://img.learnblockchain.cn/2020/02/05_/677451357.png)

首先，为每个数据区块创建父节点，其值为它们后代数据区块的哈希。

![image.png](https://img.learnblockchain.cn/2020/02/05_/665312212.png)

然后，两两分组父节点，将它们值的哈希保存于上一级的树节点中。

![image.png](https://img.learnblockchain.cn/2020/02/05_/967801882.png)

重复此过程直至一个节点，其为树的根。

## 防篡改

![image.png](https://img.learnblockchain.cn/2020/02/05_/424748274.png)

假设叶子节点数据被恶意篡改

![image.png](https://img.learnblockchain.cn/2020/02/05_/293860977.png)

将导致上一级节点的哈希值与之不匹配

![image.png](https://img.learnblockchain.cn/2020/02/05_/730399603.png)

因此不得不继续篡改该节点

![image.png](https://img.learnblockchain.cn/2020/02/05_/780379755.png)

同理，不得不依次篡改上一级节点

![image.png](https://img.learnblockchain.cn/2020/02/05_/341714907.png)

最终，来到了根节点，无法篡改，因为此节点在链上一直处于被跟踪的状态。

## 证明数据的有效性

![image.png](https://img.learnblockchain.cn/2020/02/05_/180150630.png)

现要证明 data0 是默克尔树的一员

![image.png](https://img.learnblockchain.cn/2020/02/05_/946745125.png)

首先需要找到从数据区块到根节点的一条路径

![image.png](https://img.learnblockchain.cn/2020/02/05_/540018381.png)

然后找到该路径上 data0 兄弟区块

![image.png](https://img.learnblockchain.cn/2020/02/05_/411702101.png)

忽略树的其余部分，因为这些区块已经有足够信息参与计算

![image.png](https://img.learnblockchain.cn/2020/02/05_/879948198.png)

递归重新计算根的值，若与链上的根的值相等，则 data0 属于默克尔树一部分

![image.png](https://img.learnblockchain.cn/2020/02/05_/444953333.png)

先计算 data0 哈希，放于标记为 0 的区块中

![image.png](https://img.learnblockchain.cn/2020/02/05_/27049276.png)

将 data0 的哈希结合标记为 1 的区块值计算，结果放入 4

![image.png](https://img.learnblockchain.cn/2020/02/05_/123970407.png)

最终结合 4 和 5 算出根的值

![image.png](https://img.learnblockchain.cn/2020/02/05_/378038341.png)

比较两者结果即可做出判断

关于默克尔树的其他内容，请阅读[原文](https://blog.iden3.io/merkle-trees-visual-introduction.html)。

---

![.png](https://img.learnblockchain.cn/attachments/2020/02/d2T8Y0qW5e393ac13bc4d.png!/scale/40)

## 关于我

![.png](https://img.learnblockchain.cn/attachments/2020/02/eUDAQMsr5e393ac45720f.png!/scale/20)

原文链接

[iden3.io 的 blog](Blog 最近发表了一篇关于默克尔树的图解文章，相当不错，特摘取了文章的图解部分。

默克尔树规范