默克尔树 Merkle

本章讲解默克尔树的原理和使用方法。

视频：Bilibili | Youtube

官网：binschool.app

推特：@BinSchool Discord：BinDAO 微信：bkra50

代码：github.com/binschoolapp/solidity

Merkle 树是一种树状的数据结构，它通过哈希值的层级连接来验证和管理大量数据块。它得名于其发明者 Ralph Merkle，广泛应用于密码学、分布式系统、区块链等领域。

在以太坊中所说的 Merkle 树，是将一组数据块按顺序组成树状结构，每个叶节点都是一个数据块的哈希值。

然后将相邻的叶子节点两两组合，对它们的哈希值进行计算得到它们的父节点，这个过程不断迭代直到根节点。

最终，根节点的哈希值就是这组数据块形成 Merkle 树的根哈希值。

上图中的 Merkle 树有 4 个数据块，分别是 L1、L2、L3、L4。

对这 4 个数据块分别进行 hash 运算，会得到它们对应的哈希值，分别是 Hash 0-0、Hash 0-1、Hash 0-2、Hash 0-3。

将 Hash 0-0、Hash 0-1 组合后，进行哈希运算，得到哈希值 Hash 0；同样地，可以得到 Hash 0-2、Hash 0-3 组合后的哈希值 Hash1。

最后，将 Hash 0 和 Hash 1 组合后，进行哈希运算，得到唯一的根哈希值 Top Hash，也就是根节点。

1. Merkle 树的用途

a) 数据完整性验证

通过比较根哈希值，可以验证数据块是否被篡改。只需比较根哈希值，而无需对整个数据进行比对。

b) 高效数据同步

在分布式系统中，Merkle 树能够快速验证不同节点间的数据同步情况，只需要传递少量哈希而不是完整的数据。

c) 加速数据检索

在某些系统中，Merkle 树可用于快速定位数据块的位置，加速数据的检索过程。

我们通过一个例子，来说明如何快速确定某个数据是否在 Merkle 树中，整个确认过程只需提交少量的数据。

如图所示：

对于有 N 个叶子结点的 Merkle 树，在已知根节点值的情况下，验证某个数据是否属于叶子结点，只需要 log(N) 个数据。

比如，要验证 L1 是否是 Merkle 树的数据块，我们只需要提交图中蓝色的 3 个节点的数据就能确定。

验证过程如下：

第一步：计算 L1 的哈希值，也就是 hash(L1)，得到结果为 Hash 0-0。

第二步：将 Hash 0-0 与相邻的 Hash 0-1 连接，计算其哈希值，也就是 hash((Hash 0-0) + (Hash 0-1))，得到结果 Hash 0。

第三步：将 Hash 0 与相邻的 Hash 1 连接，计算其哈希值，也就是 hash((Hash 0) + (Hash 1))，得到计算结果 Top Hash。

第四步：将 Top Hash 与已知的根节点值进行对比，如果两者相等，那么 L1 就是已知根节点值所代表的 Merkle 树的数据块，否则就不是。

所以，整个验证过程中，只需要 4 个数据：L1、Hash 0-1、Hash 1 和已知的根节点值。其中的 Hash 0-1、Hash 1 这些中间节点的数据称为 proof。

这个验证方法就是利用了哈希函数的特性之一：哈希函数将数据映射为唯一的哈希值，只要构成的数据发生微小变化，哈希值就会截然不同。而且，哈希函数是单向不可逆的，无法从哈希值倒推得到原始数据。所以，没有人能够伪造 leaf 和 proof 数据使之得出已知的根节点值。

只要能提供 leaf 数据(L1)和 proof 数据(Hash 0-1、Hash 1)，经过计算，与已知的根节点值进行对比，就能确定它是否包含在 Merkle 树中，无需遍历整棵树的数据。

这种验证方式，在包含大量数据块的场景下非常有效。比如，我们在进行 NFT 空投时，要验证某个地址是否在白名单中，而这个白名单中含有成千上万个地址。

2. Merkle 树验证合约

MerkleProof 库合约提供了一个 verify 函数，它有 3 个参数，分别是 proof、root 和 leaf，其中的 proof 就是指中间节点的哈希值，root 为根节点的哈希值，leaf 为叶子节点的哈希值。

verify 函数用于验证 leaf 是否存在于根哈希值为 root 的 Merkle 树上，提供的证据为 proof。

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

library MerkleProof {
    /**
     * @dev 通过`proof`和`leaf`计算出一个`root`，
     * 它与参数中给定的`root`进行比较，相等则返回`true`，否则为`false`。
     * @param proof 中间节点的哈希值
     * @param root 根节点的哈希值
     * @param leaf 叶子节点的哈希值
     */
    function verify(
        bytes32[] memory proof,
        bytes32 root,
        bytes32 leaf
    ) internal pure returns (bool) {
        return processProof(proof, leaf) == root;
    }

    /**
     * @dev 通过`proof`和`leaf`计算`root`
     * @param proof 中间节点的哈希值
     * @param leaf 叶子节点的哈希值
     */
    function processProof(
        bytes32[] memory proof, 
        bytes32 leaf
    ) internal pure returns (bytes32) {
        bytes32 computedHash = leaf;
        // 逐层计算相邻两个节点组合后的哈希值，最终得到`root`
        for (uint256 i = 0; i < proof.length; i++) {
            computedHash = _hashPair(computedHash, proof[i]);
        }
        return computedHash;
    }

    /**
     * @dev 对两个节点按大小进行排序，并计算组合后的哈希值
     * @param a b 相邻的两个节点
     */
    function _hashPair(
         bytes32 a,
         bytes32 b
     ) private pure returns (bytes32) {
        return a < b ? 
            keccak256(abi.encodePacked(a, b)) : 
            keccak256(abi.encodePacked(b, a));
    }
}

我们再编写一个用于对特定的以太坊地址进行验证的测试合约，它使用了库合约 MerkleProof ：

contract MerkleVerify {
    /**
    * @dev 验证某个地址在特定的 Merkle 上
    * @param proof 作为证据的节点哈希值
    * @param root 根节点的哈希值
    * @param account 进行验证的账户地址
    */
    function verify(
        bytes32[] memory proof,
        bytes32 root,
        address account
    ) external pure returns(bool) {
        // 计算 account 的哈希值
        bytes32 leaf = keccak256(abi.encodePacked(account));
        // 使用库合约函数 verify 判定是否位于 Merkle 树中
        return MerkleProof.verify(proof, root, leaf);
    }
}

这个测试合约的目的，就是通过传入已知的证据 proof 和根节点哈希值，对某个以太坊地址 account 进行校验，判断它是否在根节点哈希值所代表的 Merkle 树中。

校验的时候，首先对这个以太坊地址 account 进行哈希操作，获得其哈希值，然后再调用 MerkleProof 库合约的 verify 函数进行判定。

3. 制作 Merkle 树

我们虽然已经有了校验合约 MerkleVerify ，那么在校验函数 verify 中，如何获得 proof、root 的值呢？

我使用开源的 merkletree.js 专门开发了一个制作 Merkle 树的工具，能够非常简单的获得所有的数据。

工具地址为 https://binschool.app/tool/merkle/，打开链接后，界面如下：

我们在 Leaves 处输入 4 个地址，它们是 Merkle 树的叶子节点的原始数据。

它的下方的是哈希算法和配置项，使用默认值就可以了。

最后，点击 Compute 计算出根节点哈希值 root 和中间节点哈希值 proof。

我们可得到这棵 Merkle 树的根节点哈希值 root：

还得到了所有地址的中间节点哈希值 proof，我们可以通过选择框来选择 4 个地址之一。

目前图中显示的是第一个地址的 proof：

在这棵 Merkle 树中，只有上面的 4 个叶子节点的地址，才能通过计算得到根节点哈希值 0xeeef... ，其它的任何地址都无法构建出这个根节点哈希值，换句话说，也就是其它的任何地址都不能通过验证。

4. 部署和测试

我们可以把上面的库合约 MerkleProof 和校验合约 MerkleVerify 合并为一个文件，复制到 Remix 里进行编译，然后部署到区块链上。

我们在 verify 函数中，分别输入 proof、root 和第一个地址 0x5931...，然后点击 call 调用函数，结果值为 true。

如果输入其它地址，或者其它的 proof，得到的结果值是 false。

5. Merkle 树验证 NFT 白名单

openzepplin 合约库中有 MerkleProof 合约，我们可以直接引入使用。

比如，我们在 NFT 项目中，使用 Merkle 树来验证白名单用户，只有白名单用户有资格铸造 NFT。

假如这个白名单用户的数量很大，比如有 1000 个。如果我们使用 mapping 来存储用户白名单的话，那么这个 mapping 需要有 1000 条记录，需要耗费的 gas 费高达 1 ETH 以上，代价非常昂贵。

如果我们使用 Merkle 树来验证白名单用户的话，那么耗费 gas 费用只需要很少一点。

操作流程如下：

1）项目方将所有白名单用户的地址，作为叶子节点数据，构造一棵 Merkle 树，最终会得到一个根节点哈希值 root。

2）项目方得到了根节点哈希值 root 后，将其保存到合约中。

3）项目方将每个白名单地址对应的 proof 交给用户。

4）用户只要出具自己的账户地址和 proof ，就能够进行验证。

5）验证通过后，使用 ERC721 合约的 mint 函数铸造 NFT。

带有白名单的 ERC721 合约代码如下：

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

import "@openzeppelin/contracts/token/ERC721/ERC721.sol";
import "@openzeppelin/contracts/utils/cryptography/MerkleProof.sol";

contract MerkleNFT is ERC721 {
    // 根节点哈希值
    bytes32 public root;
    // 最新铸造的 NFT 的 Id
    uint256 public tokenId;

    // 构造函数，设置根节点哈希值
    constructor(bytes32 _root) ERC721("Merkle NFT", "MNFT") {
        root = _root;
    }

    // 铸造 NFT
    function mint(bytes32[] calldata proof) external {
        // 计算当前调用者地址的哈希值
        bytes32 leaf = keccak256(abi.encodePacked(msg.sender));
        // 校验当前调用者地址是否在白名单中
        require(MerkleProof.verify(proof, root, leaf), "not in the whitelist");
        // 为自己铸造一个 NFT
        _mint(msg.sender, ++tokenId);
    }
}

这个合约在部署的时候，需要设置事先计算得到的根节点哈希值。

BinSchool -