# 什么是Merkle Tree?

By [Webi_Tree](https://paragraph.com/@webi-tree) · 2022-11-17

---

**1\. Merkle Tree结构概念**

Merkle Tree (又称默克尔树, 哈希树）是一种典型的二叉树结构，由一个根节点、一组中间节点和一组叶节点组成。Merkle Tree最早由 Merkle Ralf 在 1980 年提出，曾广泛用于文件系统和 P2P 系统中。

**2\. Merkle Tree的主要特点为：**

·        最下面的叶节点包含存储数据或其哈希值；

·        非叶子节点（包括中间节点和根节点）都是它的两个孩子节点内容的哈希值。

进一步地，默克尔树可以推广到多叉树的情形，此时非叶子节点的内容为它所有的孩子节点的内容的哈希值。

默克尔树逐层记录哈希值的特点，让它具有了一些独特的性质。例如，底层数据的任何变动，都会传递到其父节点，一层层沿着路径一直到树根。这意味树根的值实际上代表了对底层所有数据的“数字摘要”。

**3\. Merkle Tree的典型应用场景包括如下几种。**

**3.1 证明某个集合中存在或不存在某个元素**

通过构建集合的默克尔树，并提供该元素各级兄弟节点中的 Hash 值，可以不暴露集合完整内容而证明某元素存在。

另外，对于可以进行排序的集合，可以将不存在元素的位置用空值代替，以此构建稀疏默克尔树（Sparse Merkle Tree）。该结构可以证明某个集合中不包括指定元素。

**3.2 快速比较大量数据**

对每组数据排序后构建默克尔树结构。当两个默克尔树根相同时，则意味着所代表的两组数据必然相同。否则，必然不同。

由于 Hash 计算的过程可以十分快速，预处理可以在短时间内完成。利用默克尔树结构能带来巨大的比较性能优势。

**3.3 快速定位修改**

以下图为例，基于数据 D0……D3 构造默克尔树，如果 D1 中数据被修改，会影响到 N1，N4 和 Root。

**4\. Merkle Tree与零知识证明**

如何向他人证明拥有某个数据 D0 而不暴露其它信息？挑战者提供随机数据 D1，D2 和 D3，或由证明人生成（需要加入特定信息避免被人复用证明过程）。

证明人构造如图所示的默克尔树，公布 N1，N5，Root。验证者自行计算 Root 值，验证是否跟提供值一致，即可很容易检测 D0 存在。整个过程中验证者无法获知与 D0 相关的额外信息。

 **5.Merkle Tree与储备证明**

Merkle Tree储备证明， PoR（Proof of Reserves，储备证明）是由第三方进行的独立审计，审计员将对所有的账户余额进行匿名快照，并将其聚合至 Merkle Tree 中，并获得 Merkle Root：一种在创建快照时产生的唯一的标识这些余额的数据组合。

然后，审计员收集由 Kraken 生成的数字签名，这些签名通过可公开验证的余额来证明对链上地址的所有权。

最后，审计师比较并验证这些余额是否超过或匹配 Merkle Tree 中显示的客户账户余额，来确定交易所是否持有足额的准备金。

Merkle Tree 的底层数据为每个账户持有的资产数据生成的 Hash，之后 Merkle Tree 再通过两个 Hash 生成一个新的 Hash，以此类推，最终的 Hash 代表着交易所所拥有的资产总额，该数字应该大于或至少等于所有用户持有的资产。

该方案能够被接受的最大原因在于每个用户的资产数据都被包含其中，如果交易所想要篡改该过程中任何一个数据，都会对最终数据产生极大的影响（产生影响的原因来自于生成 Hash 的算法特性）。

  

Merkle tree储备金方案能够在一定程度上证明在进行审计时，交易所拥有足以兑付所有用户资产的能力。

但也存在一定的缺陷。使用过Merkle tree进行资产储备证明的潜在的问题有：

1.树根的更新频率问题。CEX每秒有大量的交易，每一笔交易就去更新树根这个不现实。大概率你看到的树根不会是最新的，也即了解的情况不是最新的。更新频率是保障这套系统有效性的一个关键参数。

2.前端欺诈问题。用户基本是打开交易所的前端页面对自己在不在树上进行验证，这个页面可以返回假的结果，可能需要一些第三方的开源软件解决这个信任问题。

3.第三方审计的信用问题。传统金融中暴雷的很多公司也是经过层层审计的，有审计并不意味着万无一失。

4.吹哨人可用性问题。即使某个用户发现树根有假，他是否能意识到自己应该做什么，是否能有效地证明自己说的是对的，并传播这一事实？

例如无法证明私钥是独家拥有的、审计时的资产是否为临时借入、如何证明以将交易所资金（相当于所有者权益）与用户资产（相当于交易所负债）进行了隔离以及审计本身的审慎性等。

---

*Originally published on [Webi_Tree](https://paragraph.com/@webi-tree/merkle-tree)*