?? 一、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版）??

的 ??升級版??，區別在于：

• 之前用的哈希函數是 ?