title | tags | |||||
---|---|---|---|---|---|---|
36. 默克尔树 |
|
我最近在重新学 Solidity,巩固一下细节,也写一个“WTF Solidity极简入门”,供小白们使用(编程大佬可以另找教程),每周更新 1-3 讲。
所有代码和教程开源在 github: github.com/AmazingAng/WTF-Solidity
这一讲,我将介绍Merkle Tree
,以及如何利用Merkle Tree
发放NFT
白名单。
Merkle Tree
,也叫默克尔树或哈希树,是区块链的底层加密技术,被比特币和以太坊区块链广泛采用。Merkle Tree
是一种自下而上构建的加密树,每个叶子是对应数据的哈希,而每个非叶子为它的2
个子节点的哈希。
Merkle Tree
允许对大型数据结构的内容进行有效和安全的验证(Merkle Proof
)。对于有N
个叶子结点的Merkle Tree
,在已知root
根值的情况下,验证某个数据是否有效(属于Merkle Tree
叶子结点)只需要ceil(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。
我们可以利用网页或者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
通过网站,我们可以得到地址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 Hash
function _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
的Hash
,root
和对应的proof
输入到verify()
函数,将返回true
。因为地址0
的Hash
在根为root
的Merkle Tree
中,且proof
正确。如果改变了其中任意一个值,都将返回false
。
一份拥有800个地址的白名单,更新一次所需的gas fee很容易超过1个ETH。而由于Merkle Tree
验证时,leaf
和proof
可以存在后端,链上仅需存储一个root
的值,非常节省gas
,项目方经常用它来发放白名单。很多ERC721
标准的NFT
和ERC20
标准代币的白名单/空投都是利用Merkle Tree
发出的,比如optimism
的空投。
这里,我们介绍如何利用MerkleTree
合约来发放NFT
白名单: