深入剖析Solmate库 #12：MerkleProofLib.sol

一、概述

版本说明：[solmate]：main分支 [commit: 89365b8]，[forge-std]：v1.15.0

源码链接：https://github.com/RevelationOfTuring/solmate/blob/main/src/utils/MerkleProofLib.sol

MerkleProofLib 是 solmate 的工具库，提供 Gas 优化的 Merkle Proof 验证。整个库仅 1 个函数，使用纯 assembly 实现，零内存分配，仅利用 EVM scratch space 完成计算。

解决的核心问题：验证某个叶子节点是否属于一棵 Merkle Tree。典型应用场景是链上白名单（如 NFT mint、空投），合约只存储 32 字节的 root，用户提交 proof 证明自己在白名单中，无需链上存储完整名单。

Merkle Tree 原理：

Merkle Tree 结构（4 个叶子节点）：

              root
             /    \
          H(AB)   H(CD)
          / \      / \
         A   B    C   D    ← 叶子节点（数据的哈希）

构建过程（自底向上）：
  1. 叶子层：对每个数据项做 keccak256 得到 A, B, C, D
  2. 第一层：hash(A, B) → H(AB)，hash(C, D) → H(CD)
  3. 第二层：hash(H(AB), H(CD)) → root
  每一层两两配对哈希，最终收敛为唯一的 root

验证过程（验证 leaf=A 是否在树中）：
  proof = [B, H(CD)]（log2(N) 个兄弟节点）
  1. hash(A, B) → H(AB)
  2. hash(H(AB), H(CD)) → computedRoot
  3. computedRoot == root ? → 有效

为什么 Merkle Tree 适合链上验证？

1000 个地址的白名单：完整存储需要 32000 字节 + 遍历查找，Merkle Tree 只需 32 字节 + 10 次哈希（log2(1000) ≈ 10）。

二、适用场景

三、合约结构总览

MerkleProofLib (library)
│
└── Functions（1 个 internal pure 函数）
    └── verify(bytes32[] calldata proof, bytes32 root, bytes32 leaf) → bool

特点：无 Events、无 Constructor、无 Storage、无 Error——极简到只有一个函数。纯 assembly 实现，零 Solidity 层开销。

四、源码逐行解析

4.1 verify 函数

function verify(
    bytes32[] calldata proof,
    bytes32 root,
    bytes32 leaf
) internal pure returns (bool isValid)

作用：验证给定的 leaf 是否属于以 root 为根的 Merkle Tree。

参数：

proof 的排列顺序：

从底到顶——proof[0] 是最靠近叶子的兄弟，proof[length-1] 是最靠近 root 的兄弟。以 8 叶子的树验证 leaf=A 为例：

                    root
                   /    \
              H(ABCD)   H(EFGH)
              /    \      /    \
          H(AB)  H(CD) H(EF)  H(GH)
          / \    / \    / \    / \
         A   B  C   D  E   F  G   H

proof[0] = B        ← 第 1 层：A 的兄弟节点
proof[1] = H(CD)    ← 第 2 层：H(AB) 的兄弟节点
proof[2] = H(EFGH)  ← 第 3 层：H(ABCD) 的兄弟节点

验证计算过程（与 proof 下标一一对应）：
  第 1 轮：leaf = hash(A, proof[0])       = hash(A, B)              = H(AB)
  第 2 轮：leaf = hash(H(AB), proof[1])   = hash(H(AB), H(CD))      = H(ABCD)
  第 3 轮：leaf = hash(H(ABCD), proof[2]) = hash(H(ABCD), H(EFGH))  = root ✓

代码中循环从 proof.offset（即 proof[0]）开始顺序遍历，正好对应从底向上逐层计算。

设计决策 —— 为什么参数用 calldata 而非 memory？

calldata 数组在 assembly 中有两个属性：

• proof.offset：第一个元素（proof[0]）在 calldata 中的字节起始位置
• proof.length：元素个数

通过 calldataload(offset) 直接从 calldata 原地读取，无需先拷贝到 memory，省去了 calldatacopy 的 gas 开销。

4.2 Assembly 实现逐行解析

/// @solidity memory-safe-assembly
assembly {
    // 只有 proof 数组非空时才需要逐层计算
    if proof.length {
        // proof.length * 32 = 总字节数，shl(5, x) 等价于 x * 32
        // end = proof 数据在 calldata 中的结束偏移量
        let end := add(proof.offset, shl(5, proof.length))

        // offset 初始指向 proof[0] 在 calldata 中的位置
        let offset := proof.offset

        // 使用 for {} 1 {} 而非 for {} lt(offset, end) {}
        // 等价于 do-while 循环：外层 if proof.length 已保证至少一个元素，
        // 第一次迭代无条件执行，末尾 if iszero(lt(offset, end)) { break } 控制退出
        // 相当于 do { ... } while (offset < end)，省去首次进入循环的 lt 判断
        for {} 1 {} {
            // 决定 leaf 放在 scratch space 的哪个位置：
            // - 若 leaf > proof[i]：leafSlot = 32（leaf 放地址 0x20，proof[i] 放地址 0x00）
            // - 若 leaf <= proof[i]：leafSlot = 0（leaf 放地址 0x00，proof[i] 放地址 0x20）
            // 效果：较小值始终在前 32 字节，较大值在后 32 字节 → 排序后哈希
            let leafSlot := shl(5, gt(leaf, calldataload(offset)))

            // 将 leaf 写入 scratch space 的 leafSlot 位置（0x00 或 0x20）
            mstore(leafSlot, leaf)
            // 将 proof[i] 写入 leafSlot 的互补位置：
            // xor(0, 32) = 32，xor(32, 32) = 0 → leaf 放哪，proof[i] 就放另一个
            // 用 xor 一条指令实现二选一，避免 if/else 分支跳转，省 gas
            mstore(xor(leafSlot, 32), calldataload(offset))

            // 对 scratch space 0x00~0x3f 共 64 字节的内容做 keccak256 哈希
            // 结果覆写 leaf，作为下一层迭代的输入
            leaf := keccak256(0, 64)

            // offset 移动到下一个 proof 元素（+32 字节）
            offset := add(offset, 32)

            // 所有 proof 元素处理完毕（offset >= end）则退出循环
            if iszero(lt(offset, end)) { break }
        }
    }

    // proof 为空时：直接比较 leaf == root（单节点树）
    // proof 非空时：比较逐层哈希后的最终值 == root
    isValid := eq(leaf, root)
}

4.3 关键优化技巧

1. Scratch Space（零内存分配）

EVM 保留内存地址 0x00~0x3f（64 字节）作为临时计算空间（scratch space），不受 free memory pointer 管理。本库将两个待哈希的 bytes32 直接写入 scratch space，然后 keccak256(0, 64)，完全避免了 memory 分配和 free memory pointer 更新。

2. 排序后哈希（无需方向标记）

每次配对哈希时，将较小值放 0x00、较大值放 0x20，确保 hash(A, B) == hash(B, A)。

为什么这样做？Merkle Tree 验证时，proof 中的兄弟节点可能是左子节点也可能是右子节点。如果不排序，验证者必须知道每个 proof 元素的方向（左/右），proof 需要额外携带方向标记。排序后哈希消除了方向依赖，proof 只需要兄弟节点的值。

构建时也必须遵循同样的排序规则——这是一个约定，solmate、OpenZeppelin 的 MerkleTree.js、@openzeppelin/merkle-tree npm 包都遵循这个约定。

3. shl(5, gt(...)) 无分支排序

let leafSlot := shl(5, gt(leaf, calldataload(offset)))

gt 返回 0 或 1，shl(5, x) 即 x * 32，所以 leafSlot 只有 0 或 32 两个值。配合 xor(leafSlot, 32) 实现互补位置选择——全程无 if/else 分支跳转，纯算术运算。

4. for {} 1 {} do-while 循环

外层 if proof.length 已保证数组非空，第一次迭代无条件执行，末尾检查退出。相比 for {} lt(offset, end) {}，省去了首次进入循环时的一次 lt 比较。

4.4 完整验证示例

验证 leaf=A 是否在树中：
proof = [B, H(CD)]，root = R

              R (root)
             / \
          H(AB)  H(CD)
          / \
         A   B

初始：leaf = A

第 1 轮（offset → B）：
  假设 A < B → leafSlot = 0
  scratch: [A | B]
  leaf = keccak256(A, B) = H(AB)

第 2 轮（offset → H(CD)）：
  假设 H(AB) < H(CD) → leafSlot = 0
  scratch: [H(AB) | H(CD)]
  leaf = keccak256(H(AB), H(CD)) = computedRoot

最终：
  isValid = (computedRoot == R)

五、完整调用流程图

┌──────────────────────────────────────────────────────────┐
│                  verify 函数流程                          │
│                                                          │
│  输入：proof[], root, leaf                                │
│       │                                                  │
│       ▼                                                  │
│  proof.length == 0 ?                                     │
│       │                                                  │
│       ├── 是 ──> 跳过循环，直接比较 leaf == root            │
│       │                                                  │
│       ▼ 否                                               │
│  end = proof.offset + proof.length * 32                  │
│  offset = proof.offset                                   │
│       │                                                  │
│       ▼                                                  │
│  ┌─── do ────────────────────────────────────────┐       │
│  │ 读取 proof[i] = calldataload(offset)           │       │
│  │       │                                       │       │
│  │       ▼                                       │       │
│  │ leaf > proof[i] ?                             │       │
│  │   是 → scratch: [proof[i] | leaf]             │       │
│  │   否 → scratch: [leaf | proof[i]]             │       │
│  │       │                                       │       │
│  │       ▼                                       │       │
│  │ leaf = keccak256(0x00, 64)                    │       │
│  │ offset += 32                                  │       │
│  │       │                                       │       │
│  └─── while (offset < end) ──────────────────────┘       │
│       │                                                  │
│       ▼                                                  │
│  isValid = (leaf == root)                                │
│       │                                                  │
│       ▼                                                  │
│  返回 isValid                                             │
└──────────────────────────────────────────────────────────┘

六、设计思想

6.1 极简主义

• 不提供 processProof（返回计算出的 root）——只提供最常用的 verify
• 不提供 multiProofVerify——单叶子验证覆盖绝大多数场景
• 不提供 memory 版本——calldata 版本更省 gas，也是最常用的调用方式

6.2 Gas 极致优化

全程 assembly 实现，具体优化技巧见上方 4.3 关键优化技巧。

6.3 约定优于配置

• 硬编码 keccak256 作为哈希函数，不支持自定义哈希
• 硬编码排序后哈希，与主流 Merkle Tree 构建工具兼容
• 这些约定覆盖了 99% 的使用场景，不为罕见需求增加复杂度

七、安全注意事项

leaf 为什么需要取哈希？

verify 的 leaf 参数类型是 bytes32（32 字节），但业务数据几乎不可能刚好是 32 字节：

abi.encode(address, uint256)           → 64 字节（空投：地址 + 金额）
abi.encode(address, uint8, uint256)    → 96 字节（白名单：地址 + 等级 + 过期时间）
abi.encodePacked(address)              → 20 字节（NFT mint：仅地址）

做一次 keccak256 就把任意长度的业务数据统一成了 bytes32，才能传给 verify。

调用方的正确写法：

// ✓ 合约现场计算 leaf（用户无法伪造）
bytes32 leaf = keccak256(abi.encode(msg.sender, amount));
require(MerkleProofLib.verify(proof, root, leaf), "INVALID_PROOF");

// ✗ 危险：让用户直接传 leaf
function claim(bytes32[] calldata proof, bytes32 leaf) external {
    MerkleProofLib.verify(proof, root, leaf);
    // 攻击者可以传入中间节点的值作为 leaf
}

八、与 OpenZeppelin MerkleProof 对比

排序实现对比：

solmate（纯 assembly，无分支）：
  leafSlot = shl(5, gt(leaf, proof[i]))     // 0 或 32
  mstore(leafSlot, leaf)
  mstore(xor(leafSlot, 32), proof[i])       // 互补位置
  → 纯算术运算，无跳转

OpenZeppelin Hashes.sol（Solidity 三元运算符）：
  function commutativeKeccak256(bytes32 a, bytes32 b) internal pure returns (bytes32) {
      return a < b ? efficientKeccak256(a, b) : efficientKeccak256(b, a);
  }
  → Solidity 层三元运算符排序，编译后仍有条件跳转（JUMPI）
  → 且通过函数调用 efficientKeccak256，多一层 JUMP 开销

如何选择：

只需要单叶子 Merkle Proof 验证，追求最低 gas？
  → 选 solmate MerkleProofLib

需要 multiProof、自定义哈希、memory 版本？
  → 选 OpenZeppelin MerkleProof

九、实战：在业务合约中使用

// SPDX-License-Identifier: MIT
pragma solidity >=0.8.0;

import {MerkleProofLib} from "solmate/utils/MerkleProofLib.sol";

/*
 * @title MerkleAirdrop — 使用 MerkleProofLib 的空投合约
 * @notice 展示 Merkle Proof 验证的典型用法：白名单空投
 */
contract MerkleAirdrop {
    bytes32 public immutable merkleRoot;
    mapping(address => bool) public claimed;

    constructor(bytes32 _merkleRoot) {
        merkleRoot = _merkleRoot;
    }

    function claim(bytes32[] calldata proof, uint256 amount) external {
        // 防重放：每个地址只能领取一次
        require(!claimed[msg.sender], "ALREADY_CLAIMED");

        // 构造 leaf：对 (address, amount) 做哈希，将任意长度的业务数据统一为 bytes32
        // 合约现场用 msg.sender 计算，用户无法伪造 leaf 值
        bytes32 leaf = keccak256(abi.encode(msg.sender, amount));

        // Merkle Proof 验证
        require(MerkleProofLib.verify(proof, merkleRoot, leaf), "INVALID_PROOF");

        // 标记已领取
        claimed[msg.sender] = true;

        // 发放空投（示例用 ETH，实际可替换为 ERC20 transfer）
        (bool success, ) = msg.sender.call{value: amount}("");
        require(success, "TRANSFER_FAILED");
    }

    // 接收 ETH 用于空投资金
    receive() external payable {}
}

链下构建 Merkle Tree（JavaScript 示例）：

// 使用 @openzeppelin/merkle-tree 的 SimpleMerkleTree
// SimpleMerkleTree 不会自动做哈希，接受现成的 bytes32 直接构建树
// 与链上一次 keccak256 的方式保持一致
const { SimpleMerkleTree } = require("@openzeppelin/merkle-tree");
const { keccak256, AbiCoder } = require("ethers");
const coder = new AbiCoder();

// 链下自己做一次哈希，与链上 keccak256(abi.encode(...)) 对应
const leaves = [
    keccak256(coder.encode(["address", "uint256"], ["0xABCD...1234", "1000000000000000000"])),
    keccak256(coder.encode(["address", "uint256"], ["0xEFGH...5678", "2000000000000000000"])),
    keccak256(coder.encode(["address", "uint256"], ["0xIJKL...9012", "500000000000000000"])),
];

// 构建树（自动排序，不会再对 leaves 做哈希）
const tree = SimpleMerkleTree.of(leaves);

// 获取 root（部署合约时传入）
console.log("Root:", tree.root);

// 获取某个地址的 proof（用户调用 claim 时传入）
console.log("Proof:", tree.getProof(0));

注：如果用 StandardMerkleTree，它会自动对叶子做双重哈希， 链上也必须用 keccak256(bytes.concat(keccak256(abi.encode(...)))) 匹配。 这里选择 SimpleMerkleTree + 单次哈希，更简洁且合约现场算 leaf 已足够安全。

十、测试实战

Mock 合约：https://github.com/RevelationOfTuring/foundry-solmate/blob/main/src/utils/MockMerkleProofLib.sol

全部 Foundry 测试合约：https://github.com/RevelationOfTuring/foundry-solmate/blob/main/test/utils/MerkleProofLib.t.sol