Merkle Trees是区块链技术的一个基本概念。它们是一种特殊的二叉树，用于编码大块信息。Merkle Trees的酷之处在于，它们是自下而上“构建”的，允许您验证树中是否存在某些值，而无需遍历树的每个元素。这可能非常有用。

什么是默克尔树（Merkle Trees）？

Merkle树是一种散列树，其中每个叶子节点都标有数据块的加密散列，每个非叶节点都标有其子节点标签的加密散列。大多数哈希树实现是二进制的（每个节点有两个子节点），但它们也可以有更多的子节点。

典型的默克尔树看起来像这样：

默克尔树（Merkle Trees）

让我解释一下发生了什么。树的所有叶子节点，即没有其他子节点的节点，都包含您想要编码的数据散列。请注意，您要在树中编码的值始终只是叶子节点的一部分。由于它是一棵二叉树，每个非叶节点都有两个子节点。当您从叶子节点向上移动时，父节点将拥有叶子节点的组合散列的散列，以此类。

当您继续这样做时，最终您将进入单个顶级节点，称为Merkle Tree Root，这将发挥非常重要的作用。

⚒️简单的例子

假设我们有4笔交易：“交易A”、B、C和D。它们都在同一个区块中执行。这些交易中的每笔都会被散列。让我们分别将这些散列称为“哈希A”、“B、C和D”。

以下是这些交易的默克尔树（Merkle Tree）：

哈希C和哈希D

使用Merkle Root验证有效性

当这些交易被汇总到块中时，块头将包含Merkle Root，Hash ABCD。所有矿工都有迄今为止所有交易的副本，因此也拥有所有交易的哈希值。任何矿工都可以按需重建Merkle树，这意味着每个矿工都可以独立地针对同一组交易得出相同的Merkle根。

这允许任何矿工验证欺诈交易。假设有人试图引入虚假交易而不是交易D，让我们称这个为交易E。由于此交易E与交易D不同，所以哈希值也会不同。交易E的哈希值是Hash E。C和E的哈希是Hash CE，它与Hash CD不同。当Hash AB和CE一起哈希时，您将获得Hash ABCE。由于Hash ABCE与Hash ABCD不同，我们可以得出结论：交易E是欺诈性的。

欺诈证明

矿工可以在自己的区块中重新计算默克尔根（Merkle Root），并尝试将该版本发布到区块链上，但由于其他每个矿工都有不同的默克尔根（Merkle Root），因此欺诈性矿工很容易被拒绝。

哈希函数（Hash Function）

哈希函数（Hash Function）是单向的，可用于将交易A哈希为哈希A。一旦哈希后，哈希A不能转换为交易A；哈希是不可逆的。

每个区块链使用不同的散列函数，但具有相同的共同属性。

1）确定性

通过哈希函数，相同的输入总是具有相同的输出。

2）计算效率

计算输入值的哈希函数速度很快。

3）无法逆向工程

给定一个生成的哈希值，几乎不可能确定输入。即哈希函数是单向函数。例如：给定y，很难找到一个h(x) = y的x值。

4）抗碰撞性

两个不同的输入永远不会产生相同的输出。

区块链中Merkle Trees的好处

Merkle Trees允许快速验证数据完整性。

与整组交易事务相比，所消耗的磁盘空间非常少。出于这个原因，Merkle Root包含在区块头中。

如果您有两组相同的交易，则使用Merkle Tree验证它们是否相同比一次单独验证交易更快。只需通过了解Merkle Root就可以验证区块是否未被修改。

使用场景

Merkle Trees不仅仅用于区块链应用程序。使用Merkle Trees的一些流行应用程序是：

IPFS

Git

AWS DynamoDB和Apache Cassandra等分布式数据库也是使用Merkle树来控制差异

验证Merkle Trees中的存在性

那么，我们如何实际验证一些数据是默克尔树（Merkle Trees）的一部分呢？

您不希望验证器在Merkle Tree的每个叶子节点上循环，因为它可能相当大，那么我们如何才能以更有效的方式做到这一点呢？

假设Verifier只有Merkle Root r，即树的顶级父节点。作为证明者（Prover），您想向验证者（Verifier）证明默克树中存在一些值K。

为此，您可以生成Merkle Proof。让我们试着用默克尔树的例子来了解默克尔证明是什么。

默克尔证明

主要想法如下：如果您可以给验证者（Verifier）K的值，以及树中的所有相关节点哈希在一起以建立r哈希，则验证者（Verifier）可以将计算的根值与他们已经拥有的r进行比较。如果它们是相同的哈希值，这必然意味着K实际上存在于Merkle Tree中，因为您不可能用不同的输入数据生成相同的Merkle Root哈希值。

在上图中，让我们考虑必须向验证者（Verifier）提供什么信息，这些信息将积极向验证者（Verifier）证明K是默克尔树的一部分。

K本身的值（因此验证者（Verifier）可以自行计算H（K））H（L），所以验证者（Verifier）可以计算H（KL）H（IJ），以便验证者（Verifier）可以计算H（IJKL）H（MNOP），以便验证者（Verifier）可以计算H（IJKLMNOP）H（ABCDEFGH），以便验证者（Verifier）可以计算H（ABCDEFGHIJKLMNOP）

再次强调，重要的是要记住，只有一个给定的节点组合可以生成这个唯一的根r，因为Merkle树是一个抗碰撞的哈希函数，这意味着它是一个哈希函数，给定两个输入，几乎不可能产生相同的输出。

对于我们给定的示例，我们只需要提供以下节点，就可以证明H[K]确实存在于我们的节点中：

此时，如果H（ABCDEFGHIJKLMNOP）的计算值与验证者先前已知的值r匹配，则K一定存在于默克尔树中，否则哈希值将不相同。

这比循环遍历整个默克尔树上要高效得多，因为对于具有n个元素的树，您只需提供大约log（n）元素作为证明的一部分（一个对于树的每个“级别”）。这意味着如果您有大量数据，Merkle Trees比存储数组或映射更有效率。

智能合约中的用例

由于验证者（Verifier）不需要存储整个Merkle Tree来验证某些东西是否是它的一部分，因此Merkle Trees实际上对某些事情非常有用。

试想一下，我们创建一个白名单dApp，将用户地址存储在映射中。虽然这种方法有效，但在智能合约存储中存储数据是迄今为止在天然气方面最昂贵的事情。那么如果你必须存储1000个地址呢？10,000或100,000又如何？

在这一点上，直接使用智能合约存储是不可行的，并且很容易花费数百万美元将人们列入白名单。另一方面，您可以建立一个Merkle Tree，并将Merkle Root值存储在合约中（一个微不足道的 bytes32值）。在这种情况下，合约就是希望使用白名单位置来铸造NFT的用户成为证明他们确实是白名单的一部分的证明者（Provers）。