【从0学习Solidity】36. 默克尔树 Merkle Tree

在这里插入图片描述

博主简介：不写代码没饭吃，一名全栈领域的创作者，专注于研究互联网产品的解决方案和技术。熟悉云原生、微服务架构，分享一些项目实战经验以及前沿技术的见解。
关注我们的主页，探索全栈开发，期待与您一起在移动开发的世界中，不断进步和创造！
本文收录于不写代码没饭吃的学习汇报系列，大家有兴趣的可以看一看。
欢迎访问我们的微信公众号：不写代码没饭吃，获取更多精彩内容、实用技巧、行业资讯等。您关注的是我们前进的动力！

这一讲，我将介绍Merkle Tree，以及如何利用Merkle Tree发放NFT白名单。

`Merkle Tree`

Merkle Tree，也叫默克尔树或哈希树，是区块链的底层加密技术，被比特币和以太坊区块链广泛采用。Merkle Tree是一种自下而上构建的加密树，每个叶子是对应数据的哈希，而每个非叶子为它的2个子节点的哈希。

Merkle Tree允许对大型数据结构的内容进行有效和安全的验证（Merkle Proof）。对于有N个叶子结点的Merkle Tree，在已知root根值的情况下，验证某个数据是否有效（属于Merkle Tree叶子结点）只需要log(N)个数据（也叫proof），非常高效。如果数据有误，或者给的proof错误，则无法还原出root根植。
下面的例子中，叶子L1的Merkle proof为Hash 0-1和Hash 1：知道这两个值，就能验证L1的值是不是在Merkle Tree的叶子中。为什么呢？
因为通过叶子L1我们就可以算出Hash 0-0，我们又知道了Hash 0-1，那么Hash 0-0和Hash 0-1就可以联合算出Hash 0，然后我们又知道Hash 1，Hash 0和Hash 1就可以联合算出Top Hash，也就是root节点的hash。

生成`Merkle Tree`

我们可以利用网页或者Javascript库merkletreejs来生成Merkle Tree。

这里我们用网页来生成4个地址作为叶子结点的Merkle Tree。叶子结点输入：

    ["0x5B38Da6a701c568545dCfcB03FcB875f56beddC4", "0xAb8483F64d9C6d1EcF9b849Ae677dD3315835cb2","0x4B20993Bc481177ec7E8f571ceCaE8A9e22C02db","0x78731D3Ca6b7E34aC0F824c42a7cC18A495cabaB"]

在菜单里选上Keccak-256, hashLeaves和sortPairs选项，然后点击Compute，Merkle Tree就生成好了。Merkle Tree展开为：

└─ 根: eeefd63003e0e702cb41cd0043015a6e26ddb38073cc6ffeb0ba3e808ba8c097├─ 9d997719c0a5b5f6db9b8ac69a988be57cf324cb9fffd51dc2c37544bb520d65│  ├─ 叶子0：5931b4ed56ace4c46b68524cb5bcbf4195f1bbaacbe5228fbd090546c88dd229│  └─ 叶子1：999bf57501565dbd2fdcea36efa2b9aef8340a8901e3459f4a4c926275d36cdb└─ 4726e4102af77216b09ccd94f40daa10531c87c4d60bba7f3b3faf5ff9f19b3c├─ 叶子2：04a10bfd00977f54cc3450c9b25c9b3a502a089eba0097ba35fc33c4ea5fcb54└─ 叶子3：dfbe3e504ac4e35541bebad4d0e7574668e16fefa26cd4172f93e18b59ce9486

`Merkle Proof`验证

通过网站，我们可以得到地址0的proof如下，即图2中蓝色结点的哈希值：

["0x999bf57501565dbd2fdcea36efa2b9aef8340a8901e3459f4a4c926275d36cdb","0x4726e4102af77216b09ccd94f40daa10531c87c4d60bba7f3b3faf5ff9f19b3c"
]

我们利用MerkleProof库来验证：

library MerkleProof {/*** @dev 当通过`proof`和`leaf`重建出的`root`与给定的`root`相等时，返回`true`，数据有效。* 在重建时，叶子节点对和元素对都是排序过的。*/function verify(bytes32[] memory proof,bytes32 root,bytes32 leaf) internal pure returns (bool) {return processProof(proof, leaf) == root;}/*** @dev Returns 通过Merkle树用`leaf`和`proof`计算出`root`. 当重建出的`root`和给定的`root`相同时，`proof`才是有效的。* 在重建时，叶子节点对和元素对都是排序过的。*/function processProof(bytes32[] memory proof, bytes32 leaf) internal pure returns (bytes32) {bytes32 computedHash = leaf;for (uint256 i = 0; i < proof.length; i++) {computedHash = _hashPair(computedHash, proof[i]);}return computedHash;}// Sorted Pair Hashfunction _hashPair(bytes32 a, bytes32 b) private pure returns (bytes32) {return a < b ? keccak256(abi.encodePacked(a, b)) : keccak256(abi.encodePacked(b, a));}
}

MerkleProof库有三个函数：

verify()函数：利用proof数来验证leaf是否属于根为root的Merkle Tree中，如果是，则返回true。它调用了processProof()函数。
processProof()函数：利用proof和leaf依次计算出Merkle Tree的root。它调用了_hashPair()函数。
_hashPair()函数：用keccak256()函数计算非根节点对应的两个子节点的哈希（排序后）。

我们将地址0，root和对应的proof输入到verify()函数，将返回ture。因为地址0在根为root的Merkle Tree中，且proof正确。如果改变了其中任意一个值，都将返回false。

利用`Merkle Tree`发放`NFT`白名单

一份拥有800个地址的白名单，更新一次所需的gas fee很容易超过1个ETH。而由于Merkle Tree验证时，leaf和proof可以存在后端，链上仅需存储一个root的值，非常节省gas，项目方经常用它来发放白名单。很多ERC721标准的NFT和ERC20标准代币的白名单/空投都是利用Merkle Tree发出的，比如optimism的空投。

这里，我们介绍如何利用MerkleTree合约来发放NFT白名单：

contract MerkleTree is ERC721 {bytes32 immutable public root; // Merkle树的根mapping(address => bool) public mintedAddress;   // 记录已经mint的地址// 构造函数，初始化NFT合集的名称、代号、Merkle树的根constructor(string memory name, string memory symbol, bytes32 merkleroot)ERC721(name, symbol){root = merkleroot;}// 利用Merkle树验证地址并完成mintfunction mint(address account, uint256 tokenId, bytes32[] calldata proof)external{require(_verify(_leaf(account), proof), "Invalid merkle proof"); // Merkle检验通过require(!mintedAddress[account], "Already minted!"); // 地址没有mint过_mint(account, tokenId); // mintmintedAddress[account] = true; // 记录mint过的地址}// 计算Merkle树叶子的哈希值function _leaf(address account)internal pure returns (bytes32){return keccak256(abi.encodePacked(account));}// Merkle树验证，调用MerkleProof库的verify()函数function _verify(bytes32 leaf, bytes32[] memory proof)internal view returns (bool){return MerkleProof.verify(proof, root, leaf);}
}

MerkleTree合约继承了ERC721标准，并利用了MerkleProof库。

状态变量

合约中共有两个状态变量：

root存储了Merkle Tree的根，部署合约的时候赋值。
mintedAddress是一个mapping，记录了已经mint过的地址，某地址mint成功后进行赋值。

函数

合约中共有4个函数：

构造函数：初始化NFT的名称和代号，还有Merkle Tree的root。
mint()函数：利用白名单铸造NFT。参数为白名单地址account，铸造的tokenId，和proof。首先验证address是否在白名单中，验证通过则把序号为tokenId的NFT铸造给该地址，并将它记录到mintedAddress。此过程中调用了_leaf()和_verify()函数。
_leaf()函数：计算了Merkle Tree的叶子地址的哈希。
_verify()函数：调用了MerkleProof库的verify()函数，进行Merkle Tree验证。

`remix`验证

我们使用上面例子的4个地址作为白名单并生成Merkle Tree。我们部署MerkleTree合约，3个参数分别为：

name = "WTF MerkleTree"
symbol = "WTF"
merkleroot = 0xeeefd63003e0e702cb41cd0043015a6e26ddb38073cc6ffeb0ba3e808ba8c097

接下来运行mint函数给地址0铸造NFT，3个参数分别为：

account = 0x5B38Da6a701c568545dCfcB03FcB875f56beddC4
tokenId = 0
proof = [   "0x999bf57501565dbd2fdcea36efa2b9aef8340a8901e3459f4a4c926275d36cdb",   "0x4726e4102af77216b09ccd94f40daa10531c87c4d60bba7f3b3faf5ff9f19b3c" ]