🧩 一、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）不匹配（数量不对，结构不合理）时，就会报这个错，防止无效验证。

✅ 五、核心功能分类

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

单个数据验证（verify / processProof）
多个数据同时验证（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;}

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