一、引入：为什么白名单实现推荐使用Merkle Tree？
1、现在智能合约白名单的实现主要有两种方式：
-
数组存储白名单地址，当使用时候，遍历数组判断地址是否在数组中；
-
如果白名单量大，那消耗的Gas将非常惊人！
-
MerkleTree实现；
-
大大节省Gas，合约中只需要存储一个树根Root；
二、默克尔树Merkle Tree简介
1、什么是默克尔树？
默克尔树（Merkle tree）是一种数据结构，以它的提出者默克尔命名，根据默克尔树的性质也可以叫哈希树，是一种典型的二叉树。
默克尔树有3中类型的节点：根节点、父节点(非叶子节点)、叶子节点
默克尔树有两个重要的特点：
-
叶子节点包含的是相关数据的哈希值（而不是相关数据本身），这也是它叫哈希树的原因，因为它的所有节点都是存储的哈希值；
-
非叶节点的内容是子节点的哈希值的哈希。具体如下图所示：
2、默克尔树的构建过程：
-
上图中的 TA 就是原始的数据，将数据经过 hash 后，得到哈希值 HA，HA 作为整棵树的叶子节点。其余的节点如 HB，HC 等，用同样的方式得到；
-
每两个子节点的哈希值再进行哈希得到其父节点的哈希值，如 HAB = hash(HA，HB) ，以此类推得到 HABCDEFGH（也被叫做这个区块的数字指纹）；
—— 如果叶子节点是奇数（也就是最下面的那一排 T 节点为奇数），则需要复制最后一个 T 节点，这样所有叶子节点总数为偶数了；
—— 在交易作用的区块链中，默克尔树的作用在于快速归纳和校验区块数据的完整性，同时也支持“简化支付验证协议”（spv）。
3、默克尔树的验证原理：
我们还是拿上面的图片举例，假设我要检查 H 节点是否在这棵树中，那么我们需要 TH，HG，HEF，HABCD，HABCDEFGH，这些节点的哈希值：
然后将 TH通过 hash 函数转换成 HH，接着按照相似的流程 hash(HG, HH)，hash(HGH, HEF), …，最终我们只需要比较这一次 hash 的 HABCDEFGH 和区块头中存储的 HABCDEFGH 是否一致即可。
—— 可以看到为了验证某个节点，我们并不需要构建整棵默克尔树即可完成期望的操作。
三、默克尔树在智能合约白名单中的经典应用（使用Hardhat）
1、初始化一个 hardhat 项目：
npm init --yes npm install --save-dev hardhat
2、初始化 hardhat 项目：
npx hardhat init
3、安装openzeppelin/keccak256/merkletreejs：
npm install @openzeppelin/contracts keccak256 merkletreejs
4、全局安装 hardhat-toolbox 工具包：
参考：https://hardhat.org/hardhat-runner/plugins/nomicfoundation-hardhat-toolbox
npm install --save-dev @nomicfoundation/hardhat-toolbox # 但是如果我们使用的是旧版本的npm，还需要安装其他hardhat依赖： npm install --save-dev @nomicfoundation/hardhat-toolbox @nomicfoundation/hardhat-network-helpers @nomicfoundation/hardhat-chai-matchers @nomiclabs/hardhat-ethers @nomiclabs/hardhat-etherscan chai ethers hardhat-gas-reporter solidity-coverage @typechain/hardhat typechain @typechain/ethers-v5 @ethersproject/abi @ethersproject/providers
5、在 hardhat.config.js 配置文件中添加hardhat-toolbox全局配置：
/** @type import('hardhat/config').HardhatUserConfig */
// 因为hardhat框架全局都需要使用hardhat-toolbox，所以在这里引入
require("@nomicfoundation/hardhat-toolbox");
module.exports = {
solidity: "0.8.18"
};
6、在 /contracts 目录下创建一个白名单的合约 Whitelist.sol：
// SPDX-License-Identifier: MIT
pragma solidity ^0.8.4;
import "@openzeppelin/contracts/utils/cryptography/MerkleProof.sol";
contract Whitelist {
bytes32 public merkleRoot;
constructor(bytes32 _merkleRoot) {
merkleRoot = _merkleRoot;
}
// 接收
function checkInWhitelist(bytes32[] calldata proof, uint64 maxAllowanceToMint) view public returns (bool) {
bytes32 leaf = keccak256(abi.encode(msg.sender, maxAllowanceToMint));
bool verified = MerkleProof.verify(proof, merkleRoot, leaf);
return verified;
}
}
7、在 /test 目录下，创建一个测试文件 WhitelistTest.js：
const { expect } = require("chai");
const { ethers } = require("hardhat");
const keccak256 = require("keccak256");
const { MerkleTree } = require("merkletreejs");
// 对地址+最大可Mint数据进行encode编码
function encodeLeaf(address, spots) {
// 这里使用encode，则sol合约中也必须使用abi.encode()
return ethers.utils.defaultAbiCoder.encode(
["address", "uint64"],
[address, spots]
);
}
describe("测试Merkle Tree白名单实现是否可行", function () {
it("如果调用地址在白名单中，且数量等于指定数量，则通过检验", async function () {
// 生成一批地址
const [owner, addr1, addr2, addr3, addr4] = await ethers.getSigners();
// 编码地址 + 最大可Mint数量
const list = [
encodeLeaf(owner.address, 2),
encodeLeaf(addr1.address, 2),
encodeLeaf(addr2.address, 2),
encodeLeaf(addr3.address, 2),
encodeLeaf(addr4.address, 2)
];
console.log("编码后的原数据为:", list)
const merkleTree = new MerkleTree(list, keccak256, {
hashLeaves: true,
sortPairs: true,
});
// 计算MerkleTree树根
const root = merkleTree.getHexRoot();
console.log("默克尔树为：", merkleTree.toString());
console.log("MerkleTree树根为：", root);
// 部署合约
const whitelist = await ethers.getContractFactory("Whitelist");
const WhitelistContract = await whitelist.deploy(root);
await WhitelistContract.deployed();
console.log("合约部署成功，部署地址为：", WhitelistContract.address);
// 通过keccak256得到msgSender所在的叶子节点，并获得验证所需的proof
const leaf = keccak256(list[0]);
const proof = merkleTree.getHexProof(leaf);
console.log("msdSender验证所需的proof证明为：", proof)
// 场景1：msgSender : 1 => 期望false
let verified = await WhitelistContract.checkInWhitelist(proof, 1);
console.log("场景1合约返回结果：", verified);
expect(verified).to.equal(false);
// 场景2：msgSender : 2 => 期望true
verified = await WhitelistContract.checkInWhitelist(proof, 2);
console.log("场景2合约返回结果：", verified);
expect(verified).to.equal(true);
// 场景3：msgSender : 3 => 期望false
verified = await WhitelistContract.checkInWhitelist(proof, 3);
console.log("场景3合约返回结果：", verified);
expect(verified).to.equal(false);
});
});
8、运行测试用例（本次将失败）——此处有坑
npx hardhat test
原因：ethers版本过高，第六版不支持ethers.providers.JsonRpcProvider()用法；
解决办法：在package.json中将ethers的版本降到5.4，然后重新： npm install
9、重新运行测试用例：
PS E:\Study-Code\blockchain\WhiteList> npx hardhat test 测试Merkle Tree白名单实现是否可行 编码后的原数据为: [ '0x000000000000000000000000f39fd6e51aad88f6f4ce6ab8827279cfffb922660000000000000000000000000000000000000000000000000000000000000002', '0x00000000000000000000000070997970c51812dc3a010c7d01b50e0d17dc79c80000000000000000000000000000000000000000000000000000000000000002', '0x0000000000000000000000003c44cdddb6a900fa2b585dd299e03d12fa4293bc0000000000000000000000000000000000000000000000000000000000000002', '0x00000000000000000000000090f79bf6eb2c4f870365e785982e1f101e93b9060000000000000000000000000000000000000000000000000000000000000002', '0x00000000000000000000000015d34aaf54267db7d7c367839aaf71a00a2c6a650000000000000000000000000000000000000000000000000000000000000002' ] 默克尔树为： └─ 3da10f52b61d3229c1849e581e7fc99f52253ea91a72bf39f47e40d521ea4ecd ├─ 392526380863aaa55c6b43a4d5f2610ffc88c9489b3e6f66f25229958367f85b │ ├─ 632857fc45795b05ef446a31b8c68c337da8d48fdc1ad84b4fb1b1ca4987ba5a │ │ ├─ bc40fbf4394cd00f78fae9763b0c2c71b21ea442c42fdadc5b720537240ebac1 │ │ └─ 6ffab96d4009ce38df68f4dc04583568617773212ffc44bef9feaece2962b766 │ └─ 4d599dffc2a93b068ea6425cf6b498ba69604b38f9ebbe824b4a51f29014d932 │ ├─ bd19ff506d92b45639170e62f1a12073921a4358c3ccd05d4584519f78d65103 │ └─ 290d67fa5d3e085921a73833359e3fc1da9587bf1de51d1b061255196c35a4dd └─ fcb66c6776d19d0057746fbecdb07c5b544b6a4d7fcfb04e96a88007dd36b3d2 └─ fcb66c6776d19d0057746fbecdb07c5b544b6a4d7fcfb04e96a88007dd36b3d2 └─ fcb66c6776d19d0057746fbecdb07c5b544b6a4d7fcfb04e96a88007dd36b3d2 MerkleTree树根为： 0x3da10f52b61d3229c1849e581e7fc99f52253ea91a72bf39f47e40d521ea4ecd 合约部署成功，部署地址为： 0x5FbDB2315678afecb367f032d93F642f64180aa3 msdSender验证所需的proof证明为： [ '0x6ffab96d4009ce38df68f4dc04583568617773212ffc44bef9feaece2962b766', '0x4d599dffc2a93b068ea6425cf6b498ba69604b38f9ebbe824b4a51f29014d932', '0xfcb66c6776d19d0057746fbecdb07c5b544b6a4d7fcfb04e96a88007dd36b3d2' ] 场景1合约返回结果： false 场景2合约返回结果： true 场景3合约返回结果： false ✔ 如果调用地址在白名单中，且数量等于指定数量，则通过检验 (1060ms) 1 passing (1s)
测试通过！
补充一、思考：默克尔树实现白名单的功能还可以借助后端服务实现
因为我们一般不会把整个原数据数放在前端代码中，所以在使用过程中，很难去获取到MerkleTree并得到当前地址的proof，所以我们可以将这些地址维护在数据库或缓存中：
-
前端让用户授权钱包，获得当前钱包地址；
-
调用后端接口，后端可以直接判断当前地址是否是白名单，如果不是，直接提示用户，不用去链上验证；
-
如果当前用户后端验证后是白名单，那么则生成对应的proof返回给前端；
-
前端调用合约的接口进行Mint操作，在Mint方法中会调用白名单验证的逻辑！
这么写的好处是，可以很方便的控制项目的报名单！
