🧩 一、Merkle Tree 是什么？为什么要验证它？

想象你有一个名单，比如：

["Alice", "Bob", "Charlie", "Dave"]

你想让别人验证：“我（比如 Alice）是不是在这个名单里？”，但不想把整个名单都放在区块链上（太贵！）。

于是你用一种数据结构 —— ​​Merkle Tree（默克尔树）​​，把所有名字（或它们的哈希）组织成一棵树，最终得到一个唯一的“总照片”叫 ​​Merkle Root（根哈希）​​，你把这个根哈希存在区块链上。

别人（比如 Alice）给你：

• 她自己的名字的哈希（leaf）

• 从她到根路径上的一些“邻居哈希”（proof）

• 一组“怎么拼”的规则（proofFlags，或者按顺序）

• 你就能用这些信息，​​在链上计算出根哈希，看是否和你存证的一样​​，如果一样，说明她在名单里 ✅

---

🏗️ 二、这个库（MerkleProof.sol）是干嘛的？

这是一个 ​​工具库（Library）​​，提供了一系列函数，用来：

• 验证 ​​单个数据​​ 是否属于某个 Merkle Tree

• 验证 ​​多个数据（批量）​​ 是否同属于某个 Merkle Tree

• 支持 ​​不同存储方式（memory / calldata）​​

• 支持 ​​默认 Keccak256 哈希 或 自定义哈希函数​​

它封装了所有和 Merkle Proof（默克尔证明）验证相关的核心逻辑，让开发者可以很方便地集成到自己的 DApp / 合约中。

---

📦 三、文件结构 & 导入说明

// SPDX-License-Identifier: MIT
pragma solidity ^0.8.20;import {Hashes} from "./Hashes.sol";

• 使用 ​​Solidity 0.8.20​​

• 引入了一个工具库 Hashes.sol，它提供了一个关键函数：

  commutativeKeccak256(a, b)→ 这是一个 ​​可交换顺序的 Keccak256 哈希函数​​，即 hash(a,b) == hash(b,a)，这在构建 Merkle Tree 时非常有用，因为父子节点的左右顺序有时不重要。

---

❗ 四、自定义错误

error MerkleProofInvalidMultiproof();

• 当你传入的 ​​证明数据（proof）和叶子数据（leaves）不匹配​​（数量不对，结构不合理）时，就会报这个错，防止无效验证。

---

✅ 五、核心功能分类

这个库主要提供两类验证：

1. ​​单个数据验证（verify / processProof）​​

2. ​​多个数据同时验证（multiProofVerify / processMultiProof）​​

并且每种都支持：

• ​​普通版本（memory 存储）​​

• ​​高效版本（calldata 存储，省 gas）​​

• ​​默认 Keccak256 哈希​​

• ​​自定义哈希函数​​

我们逐一来看 👇

---

🟢 1. 单个数据验证（memory版）

🔹 函数：verify(proof, root, leaf)

 /*** @dev 验证单个叶子是否属于默克尔树* @param proof 证明路径数组，包含从叶子到根的所有兄弟哈希* @param root 默克尔树的根哈希* @param leaf 待验证的叶子哈希* @return 如果验证成功返回true，否则返回false* * 示例：* 假设默克尔树有4个叶子：A、B、C、D* 验证C是否在树中：* bytes32[] memory proof = [D的哈希, (A+B)的哈希];* bool isValid = MerkleProof.verify(proof, rootHash, hash(C));*/function verify(bytes32[] memory proof, bytes32 root, bytes32 leaf) internal pure returns (bool) {// 处理证明并与根哈希比较return processProof(proof, leaf) == root;}

• ​​作用​​：验证一个 leaf（比如你的地址哈希）是否属于某个 Merkle Tree（通过 root 和 proof）

• ​​参数​​：

  • proof: 从该叶子到根路径上的 “兄弟节点哈希” 数组

  • root: Merkle Tree 的根哈希（存在链上的那个）

  • leaf: 你要验证的叶子哈希（比如 keccak256(你的地址)）

• ​​返回​​：true/false，是否验证通过

🔍 ​​它是怎么做的？​​

• 调用了 processProof(proof, leaf)，这个函数会：

  • 从你的叶子开始

  • 依次和 proof 里的“兄弟哈希”做哈希组合（一层一层往上爬）

  • 最终得到一个哈希，就是这棵树的根

• 然后判断这个计算出来的根，是否等于传入的 root，一样就 ✅

🔹 函数：processProof(proof, leaf)

/*** @dev 处理证明路径，从叶子计算出根哈希* * 【实际区块链场景】：* 比如你参与了一个 Token 空投，项目方用 Merkle Tree 管理所有空投用户，* 你拿到：* - 你的叶子：你的钱包地址的哈希（比如 0x1111...）* - 一个证明路径（proof）：包含你从叶子到根过程中，每一层的“隔壁节点哈希”（兄弟节点）* - 你调用这个函数，传入你的叶子 + 证明路径，它就会帮你算出整棵树的根哈希* - 然后你拿这个根去和项目方存在链上的根对比，如果一样，你就能领空投啦！✅* * @param proof 证明路径数组*    这是一个数组，里面装的是你在从叶子到根的过程中，每一层需要用到的“兄弟节点哈希”*    比如：[0x2222..., 0x3333..., 0x4444...]，它们是你路径上的“邻居”* * @param leaf 待验证的叶子哈希*    这是你自己的数据哈希，比如你的钱包地址经过 keccak256 后的值：0x1111...* * @return 计算得到的根哈希*    最终拼出来的 Merkle 树的根，用来和链上存证的根做对比*/function processProof(bytes32[] memory proof, bytes32 leaf) internal pure returns (bytes32) {// 🌱 初始化：我们从叶子节点开始，这就是你自己的数据哈希bytes32 computedHash = leaf;// 比如：computedHash = 0x1111111111111111111111111111111111111111（你的地址哈希）// 🔁 遍历证明路径中的每一个兄弟节点哈希，逐步向上计算父节点哈希for (uint256 i = 0; i < proof.length; i++) {// 🧩 每次循环，你都会拿到一个“兄弟节点哈希”：proof[i]// 比如第1次循环：proof[0] = 0x2222...，第2次：proof[1] = 0x3333...，依此类推// 🔐 使用一个“可交换的哈希函数”来合并：computedHash（你的节点）和 proof[i]（兄弟节点）// 这里调用了 Hashes.commutativeKeccak256(...)，它本质上就是 keccak256(abi.encodePacked(a, b))// 但“可交换”意味着你先传 a 还是 b 都没关系，结果是一样的（keccak 本身是可交换的，只要顺序一致）computedHash = Hashes.commutativeKeccak256(computedHash, proof[i]);// 【例子】：// 第1次循环：computedHash = keccak256(0x1111..., 0x2222...) → 假设结果是 0x1234...// 第2次循环：computedHash = keccak256(0x1234..., 0x3333...) → 假设结果是 0x5678...// 第3次循环：computedHash = keccak256(0x5678..., 0x4444...) → 假设最终根是 0xAAAA...}// 🎯 最终返回：经过所有证明路径节点合并后，得到的根哈希return computedHash;// 比如最终返回：0xAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA（Merkle 树的根）}

• 内部实现：就是不断地把你的 leaf 和 proof 里的哈希两两组合（用commutativeKeccak256），最终返回根哈希

---

🟢 2. 单个数据验证（memory版，带自定义哈希函数）

/*** @dev 带自定义哈希函数的单个叶子验证* @param proof 证明路径数组* @param root 默克尔树的根哈希* @param leaf 待验证的叶子哈希* @param hasher 自定义哈希函数* @return 验证结果* * 示例：* 使用SHA256作为哈希函数（需提前实现）* bool isValid = MerkleProof.verify(proof, rootHash, hash(C), sha256Hash);*/function verify(bytes32[] memory proof,bytes32 root,bytes32 leaf,function(bytes32, bytes32) view returns (bytes32) hasher) internal view returns (bool) {return processProof(proof, leaf, hasher) == root;}

这个功能是基于之前提到的：

​​1. 单个数据验证（memory版）​​

的 ​​升级版​​，区别在于：

• 之前用的哈希函数是 ​