什么是Merkle 树、Merkle 证明和 Merkle 树根

深入探讨 Merkle 树的数据结构以及 Merkle 证明如何验证数据的存在。回答以下问题：什么是 Merkle 树、Merkle 证明和 Merkle 根？

什么是 Merkle 树、Merkle 证明和 Merkle 根？了解它们是什么、如何工作以及如何将它们应用于你的项目中。

通过这篇文章的学习，你将理解 Merkle 树、Merkle 证明和 Merkle 根是什么，为什么需要它们，如何使用它们，以及如何将它们构建到你的项目中！让我们开始吧！

在开始之前，请确保你对以下内容有扎实的理解：

• 哈希函数的知识
• 精通 Solidity 智能合约

什么是 Merkle 树、Merkle 证明和 Merkle 根？

我们为什么需要 Merkle 树？

问题：我如何验证某些任意数据是否在一组数据中？例如，假设我们有一个俱乐部 VIP 名单，我们如何确定特定的名字是否在名单上？

我们难道不能简单地遍历（或手动搜索）数据列表来检查我们正在寻找的特定数据是否存在？

这将是一个挑战，尤其是当名字列表非常庞大时（想想成千上万）。现在，想象一下这是一个智能合约中的字符串数组。遍历这个数组的成本会随着名字数组的增加而变得极其高昂。在某些情况下，可能会出现服务拒绝，导致无法检查某个名字，因为 gás 不够。相反，我们使用 Merkle 树！

‍

Merkle 树是什么？

Merkle 树是一种数据结构，而 Merkle 证明则用于证明某些数据在该 Merkle 树中。它们是在1979年由 Ralph Merkle 发明的，他是一位计算机科学家、数学家，也是公钥密码学的创造者之一。

那么，Merkle 树实际是什么呢？

想象一棵树……但是是倒过来的。

叶子位于底部，根位于顶部。我们树中的每个叶子都是一条数据，树的分支和根通过将这些数据进行 哈希 得到。这就是 Merkle 树。通过这篇文章，你将理解下面这个图示：

Merkle 树示意图

‍

一个叶节点是某些哈希数据，例如 VIP 示例中的字符串 “Ciara”。相邻的叶节点会被哈希在一起以生成中间节点。相邻的中间节点会递归地哈希在一起直到产生一个单一的哈希。这个哈希被称为根哈希。

Merkle 证明用于证明某些特定数据在一组数据（在 Merkle 树中）中存在。这些数据可以是任何东西，例如俱乐部 VIP 的名字，我想证明我的名字在 VIP 名单上。

Merkle 树是一个 二叉树 ，其中每个叶节点表示某些数据的哈希，每个中间节点则是其两个子节点的哈希。最上方的节点称为 Merkle 根。

‍

Merkle 树如何工作？

让我们拆解如何创建一个 Merkle 树：

1. 每条数据（字符串 “Ciara”）被哈希以生成叶节点哈希（使用像 keccak256 这样的哈希算法）：某些文本
2. Hash 1 = Hash(Data 1)
3. Hash 2 = Hash(Data 2)
4. Hash 3 = Hash(Data 3)
5. Hash 4 = Hash(Data 4)

Hash 1 的图示。

1. 然后，相邻的叶节点被哈希在一起以生成中间节点：某些文本
2. Hash 1-2 = Hash(Hash 1, Hash 2)
3. Hash 3-4 = Hash(Hash 3, Hash 4)

Hash 1-2 的图示。

‍

1. 相邻的中间节点随后会被哈希在一起以生成根哈希（预期的根哈希）某些文本
2. Root Hash = Hash(Hash 1-2, Hash 3-4)

根哈希的图示。

‍

将所有这些结合在一起，我们可以将 Merkle 树可视化为：

完整 Merkle 树的图示。

‍

要证明某些数据存在于 Merkle 树中–证明 “Ciara” 是 VIP 俱乐部的一部分：

1. 提供者（在我们的示例中，将是一个试图进入俱乐部的人）提供：某些文本
2. 数据，例如，在我们的 VIP 示例中，他们的名字 “Ciara.”
3. 一个数组包含所需的其他中间节点，以重构树并计算根哈希。这被称为 Merkle 证明。

所以，为了证明名字 “Ciara” 在树中，他们必须提供一个数组 Proof = [Proof 1, Proof 2]

• 其中：某些文本
  • Proof 1 = Hash 2
  • Proof 2 = Hash 3-4。

2. 然后将数据的哈希与证明的第一个元素 Proof 1 进行哈希，然后将所得的哈希与第二个元素 Proof 2 进行哈希，以生成计算得到的根哈希。在我们的 VIP 示例中，某些文本
3. Hash(“Ciara”) 与第一个证明数组元素 Hash 2 进行哈希
4. 然后该结果与第二个证明元素 Hash 3-4 进行哈希，以生成预期根哈希
5. 计算出的根哈希与预期的根哈希进行比较，以检查名字是否在树中。在我们的 VIP 示例中，只有俱乐部所有者才能访问此预期根。

使用一个安全的哈希函数如 keccak256 使得创建哈希碰撞的可能性几乎是不可能的；找到两个不同输入集得到相同哈希的可能性是如此之低，以至于在实践中不会发生。这是因为在使用 keccak256 时，该数据的哈希对于不同的数据片段是唯一的。如果在 Merkle 证明中存在匹配的根哈希，则你知道该项一定是原始根哈希计算的一部分。

带注释的完整 Merkle 树的图示。

‍

让我们看看我们的 VIP 示例的 JSON。如下所示，你可以看到输入。这是 VIP 名单中名字的字符串。证明是重构树所需的两个中间节点；根是预期根哈希，叶是叶节点 - 输入数据的哈希，例如 keccak256(“Ciara”)。

[
   {
       "inputs": [
           "Ciara"
       ],
       "proof": [
           "0xfcedff7fd13c323a60b257d4553f350831c1694fd3a953ed9bb5af1abd127fb8",
           "0x7c1a4a44f893dd1de1745304d1b2a6413f937d10c458bdd45ede7c53b87e3a0e"
       ],
       "root": "0x6e10420ea854c1d5c4c2e7ecf3e1f79e6963f43f924a009f5bf6d45da592d1cf",
       "leaf": "0x7c03745f570a678cbf8956b39d092a3653cd96d15b52ee66f408571923aa69b8"
   },
   {
       "inputs": [
           "Sarah"
       ],
       "proof": [
           "0x7c03745f570a678cbf8956b39d092a3653cd96d15b52ee66f408571923aa69b8",
           "0x7c1a4a44f893dd1de1745304d1b2a6413f937d10c458bdd45ede7c53b87e3a0e"
       ],
       "root": "0x6e10420ea854c1d5c4c2e7ecf3e1f79e6963f43f924a009f5bf6d45da592d1cf",
       "leaf": "0xfcedff7fd13c323a60b257d4553f350831c1694fd3a953ed9bb5af1abd127fb8"
   },
   {
       "inputs": [
           "Bob"
       ],
       "proof": [
           "0xe060618ff524040946d843f7db0f20bc36d6823d1dd1adf0cefbbd8c4283eda1",
           "0x68247294d6ac7c96da06755b7e71415e1b46163839ab6a67b9f7cc896369f8f7"
       ],
       "root": "0x6e10420ea854c1d5c4c2e7ecf3e1f79e6963f43f924a009f5bf6d45da592d1cf",
       "leaf": "0xfa584e70da2cdafeba16aae05f550a31fac5d37ea2de2232d2fb02401b0527da"
   },
   {
       "inputs": [
           "Dylan"
       ],
       "proof": [
           "0xfa584e70da2cdafeba16aae05f550a31fac5d37ea2de2232d2fb02401b0527da",
           "0x68247294d6ac7c96da06755b7e71415e1b46163839ab6a67b9f7cc896369f8f7"
       ],
       "root": "0x6e10420ea854c1d5c4c2e7ecf3e1f79e6963f43f924a009f5bf6d45da592d1cf",
       "leaf": "0xe060618ff524040946d843f7db0f20bc36d6823d1dd1adf0cefbbd8c4283eda1"
   }
]

‍

在智能合约中使用 Merkle 树

要将 Merkle 树实现到智能合约中并验证某些任意数据是否在 Merkle 树中，我们可以使用 OpenZeppelin 的 MerkleProof.sol 智能合约。让我们看看它是如何工作的：

• verify 接受证明、Merkle 根以及我们想要验证的叶节点。通常情况下，根将存储在智能合约中，证明将离线计算并作为函数调用的参数传递。
• processProof 将迭代通过证明数组中的每个元素。
• 从叶节点开始，通过与证明中的下一个元素进行哈希更新计算哈希。某些文本
  1. 哈希将始终先处理较小的值。
  2. OpenZeppelin 使用 mstore 和 keccak256 操作码进行效率优化，而不是简单地使用 keccak256(abi.encodePacked(a, b))。
• 计算出的哈希将被返回，并与预期根进行比较，以确定提供的叶节点是否存在于 Merkle 树中。

function verify(bytes32[] memory proof, bytes32 root, bytes32 leaf) internal pure returns (bool) {
    return processProof(proof, leaf) == root;
}

function processProof(bytes32[] memory proof, bytes32 leaf) internal pure returns (bytes32) {
    bytes32 computedHash = leaf;
    for (uint256 i = 0; i < proof.length; i++) {
        computedHash = _hashPair(computedHash, proof[i]);
    }
    return computedHash;
}

function _hashPair(bytes32 a, bytes32 b) private pure returns (bytes32) {
    return a < b ? _efficientHash(a, b) : _efficientHash(b, a);
}

function _efficientHash(bytes32 a, bytes32 b) private pure returns (bytes32 value) {
    /// @solidity memory-safe-assembly
    assembly {
        mstore(0x00, a)
        mstore(0x20, b)
        value := keccak256(0x00, 0x40)
    }
}

‍

有关如何使用 OpenZeppelin 的 MerkleProof.sol 智能合约的示例，请查看 MinimalMerkle 示例仓库。

// SPDX-License-Identifier: MIT
pragma solidity ^0.8.24;

import {MerkleProof} from "@openzeppelin/contracts/utils/cryptography/MerkleProof.sol";

contract MinimalMerkle {
   bytes32 immutable public i_root;

   error MinimalMerkle__NotInClub();

   constructor(bytes32 _root) {
       i_root = _root;
   }

   function verifyIfInClub(string memory name, bytes32[] memory proof) public view returns (bool) {
       bytes32 leaf = keccak256(bytes.concat(keccak256(abi.encode(name))));

       if (!MerkleProof.verify(proof, i_root, leaf)) {
           revert MinimalMerkle__NotInClub();
       }

       return true;
   }
}

‍

生成 Merkle 树和第二原像攻击

可以使用两个主要库生成 Merkle 树：

• OpenZeppelin 的 JavaScript 库
• DMFXYZ 的 Murky Solidity 脚本

这两个库都将输入数据哈希两次，以防止所谓的第二原像（second preimage）攻击。

在第二原像攻击中，一个中间节点作为叶节点呈现，因此通过了检查，因为它在 Merkle 树中存在。

如果函数接受 62 字节的叶子作为输入，则此情况是可能的。这意味着攻击者可以将两个哈希合并的叶节点哈希作为输入（在哈希之前），这被称为中间节点的原像，而不是其哈希值。由于 Solidity 中的哈希长度为 32 字节，因此编码两个叶节点哈希的结果将是 64 字节。

通过不接受 64 字节长的叶节点数据和/或对叶节点使用与中间哈希不同的哈希函数，这种情况得到了缓解。这可以通过对数据进行两次哈希来实现，类似于使用不同的哈希函数。中间哈希则只通过哈希一次。当我们使用这两个脚本来生成 Merkle 树时，生成的 Merkle 树抵抗原像攻击，因为用于生成叶节点的数据已哈希两次。

有关更多信息，Rareskills 发布了一篇关于 第二原像攻击 的精彩文章。

‍

现实世界中的 Merkle 用例

空投

与使用地址的数组或映射相比，Merkle 树可以在空投智能合约中使用，以提高性能并减少 Claim的 Gas 成本。

Merkle 树用于高效空投，以安全且可验证的方式向大量接收者分发代币，而无需在链上存储整个接收者名单。在此过程中，合格接收者及其相应的代币分配被哈希以创建 Merkle 树中的叶节点。然后，根被发布在链上，作为空投智能合约的一部分。每个接收者可以通过提供离线计算的 Merkle 证明来索取他们的代币。

区块链

区块头包含有关区块本身的信息，并包含以下字段：

• 交易根： 交易树的 Merkle 根的 Keccak 哈希
• 收据根： 交易收据树的 Merkle 根的 Keccak 哈希 ‍
• 状态根： 状态（执行后）树的 Merkle 根的 Keccak 哈希

这些“根”起到 Merkle 根的作用。状态、交易和收据都是编码到 Merkle Patricia 树中，根包含在区块头中！

为了简化，你可以将一个 Merkle Patricia 树 视为与 Merkle 树相同，因为根哈希是依赖于子节点的，如果任何子节点发生变化，根哈希也会变化。

更多信息，请参阅这篇 noxx EVM 深入研究文章。

Rollup

Rollup是一种 Layer 2 扩展解决方案，旨在增加像以太坊这样的区块链网络的吞吐量。它将多个链下交易打包，并将批次的根哈希发布到主链。下面是 Merkle 树在Rollup中的使用方式：

• 批次根： 交易被捆绑并编码为使用 Merkle 树的单个根哈希。批次根包含批次中的所有交易。要证明交易是否包含在批次中，需要提供交易细节、批次根和证明包含路径的 Merkle 证明。
• 状态根： Rollup的前后状态变化（之前和新的批次状态）被表示为 Merkle 树，称为状态树，状态根提交在 layer 1 链上。

这些根随后被发布在 layer 1 链上，使用 Merkle 证明验证特定交易或状态，证明其在Rollup中的包含。

‍

总结

Merkle 树是一种数据结构，通过迭代地将相邻的任意数据片段哈希在一起，创建一个单一节点——称为 Merkle 根——其中包含关于树中所有子节点的信息。然后使用 Merkle 证明来证明是否某些任意数据存在于树中。

Merkle 树在高效的空投、存储区块链交易、收据和状态数据以及在Rollup中整合和证明批次和状态数据方面非常有用。

• 原文链接： cyfrin.io/blog/what-is-a...
• 登链社区 AI 助手，为大家转译优秀英文文章，如有翻译不通的地方，还请包涵～