Merkle树——验证NFT白名单

在我们今天所知道和喜爱的区块链出现之前，默克尔树一直是密码学和计算机科学领域的一个方面。如今，我们开始慢慢看到它们在链上更频繁地被用于数据验证的目的。

1. 什么是默克尔树？

默克尔树是一种树状结构，树上的每个节点都由一个值表示，这个值是一些加密哈希函数的结果。哈希函数是单向的，从一个输入产生一个输出很容易，但从一个输出确定一个输入在计算上是不可行的。默克尔树有3种类型的节点，如下所示：

1. 叶子节点 - 叶子节点位于树的最底部，它们的值是原始数据的哈希值。一棵树上有多少个叶子节点，就有多少个需要哈希的原始数据。例如，如果有7个数据需要被哈希，就会有7个叶子节点。
2. 父节点 - 父节点可以位于树的不同层次，这取决于整个树的大小，父节点总是位于叶节点之上。父节点的值是由它下面的节点的哈希值决定的，通常从左到右开始。由于不同的输入总是会产生不同的哈希值，不考虑哈希值的碰撞，节点哈希值的连接顺序很重要。
3. 根节点 - 根节点位于树的顶端，由位于它下面的两个父节点的哈希值连接而成，同样从左到右开始。任何默克尔树上都只有一个根节点，根节点拥有根哈希值。

2. 默克尔树结构

简化它

3. 为什么需要默克尔树？

3.1 背景

在NFT（ERC-721）的背景下使用Merkle树，白名单为选定的参与者群体保留一定数量的代币。

白名单地址将会预先计算成Merkle对象。

在这种情况下，可以让一个叶子节点代表我们白名单中的一个钱包地址的哈希值。

3.2 痛点

前面提到过哈希函数是单向的——从一个输入产生一个输出很容易，但从一个输出确定一个输入在计算上是不可行的，并且连接顺序也将决定结果。

Example:

hash（hash1,hash2） != hash(hash2,hash1)

在NFT白名单实例中，将会使用哈希值进行数据安全验证。

因此在这种情况下，直系验证是非常困难的，需要非常大的计算量和资源。

传统验证

验证根哈希值是否相同，这看似很简单，但问题就在于，当你去验证一个地址时，到底将该地址哈希与哪个叶子哈希值进行替换并验证？这是很难计算得知的。

根哈希验证的另一个难点（了解即可）

3.3 如何解决——取得默克尔证明

Merkle树妙处在于它根本不需要与根哈希，父哈希等等进行等量校对。

如果试图验证一个叶子节点属于我们的树，只需要知道直接相邻的叶子节点哈希值(如果有的话)，以及叶子节点正上方相邻的父节点哈希值就可以了。

如果这个Merkle树有四层，五层甚至一百层，那么返回的哈希值数量将会相应增长！

4. 实战

实战将会带你实例化默克尔树对象以及取得默克尔树验证！

4.1 JavaScript实现

安装

npm i -D merkletreejs keccak256

merkletree.js

const {MerkleTree} = require('merkletreejs')

const keccak256 = require('keccak256')


let whitelistAddresses = [
    "0x262bCDeEf90181676BDC0a247A1954666F8a2815",
    "0x262bCDeEf90181676BDC0a247A1954666F8a2816",
    "0x262bCDeEf90181676BDC0a247A1954666F8a2817",
    "0x262bCDeEf90181676BDC0a247A1954666F8a2818",
    "0x262bCDeEf90181676BDC0a247A1954666F8a2819",
    "0x262bCDeEf90181676BDC0a247A1954666F8a2820",
    "0x262bCDeEf90181676BDC0a247A1954666F8a2821"       
]

//buffer化叶子结点
const leafNodes = whitelistAddresses.map(addr => keccak256(addr))

//实例化默克尔树
const merkleTree = new MerkleTree(leafNodes,keccak256,{sortPairs:true});

//获取根哈希值
const rootHash = merkleTree.getRoot();

console.log('Whitelist Merkle Tree\n',merkleTree.toString())

//定义你所需要验证的地址
const claimingAddress = leafNodes[0]

//取得默克尔树证明
const hexProof = merkleTree.getHexProof(claimingAddress)


console.log(`Merkle Proof for Address is\n`,hexProof)


//当你传入一个错误的白名单地址时
const errAddress = keccak256('0x98D9897e0F0389158978B384E6ecF3cf93153876');

//取得默克尔证明
const hexProof1 = merkleTree.getHexProof(errAddress)

//将会得到空数组！
console.log(`Merkle Proof for error Address is\n`,hexProof1)

测试结果

由于该默克尔树是由七个叶子节点组成的，所以这是一个三层结构的树，因此默克尔证明将会取得三个哈希值作为凭证。当树结构为五层，六层… 默克尔证明的哈希值数量会对应增加！

4.2 智能合约实现

Merkletree.sol

// SPDX-License-Identifier: SEE LICENSE IN LICENSE
pragma solidity ^0.8.0;


//导入默克尔树智能合约
import "https://github.com/OpenZeppelin/openzeppelin-contracts/blob/master/contracts/utils/cryptography/MerkleProof.sol";

contract Merkletree{

    //该根哈希值需要你用到刚刚js生成的merkle树的根哈希（记得加上0x）
    bytes32 public merkleRoot = 0x3a6036ef5f6da50ea7f3dc72c7c83c1e6d5be6cded8ad495fb4b0bb870f1c093;
    
    //记录白名单是否被使用过
    mapping(address => bool) public whitelistClaimed;

    //使用白名单函数
    function whitelistMint(bytes32[] calldata _merkleProof) public{
        //要求白名单没有被使用过
        require(!whitelistClaimed[msg.sender],"Address has already claimed");
        //初始化叶子哈希
        bytes32 leaf = keccak256(abi.encodePacked(msg.sender));
        //将叶子哈希传入merkle树验证，查看是否是白名单
        require(MerkleProof.verify(_merkleProof, merkleRoot , leaf),"Invalid proof");
        //是白名单，记录该白名单使用过
        whitelistClaimed[msg.sender] = true;
    }
}

5. 总结

Merkle树是区块链中非常重要的数据结构，它的应用极大地减小了哈希安全验证的难度，提高了合约安全程度，减少了被攻击成功的可能性。

感谢阅读！

Blog by Science_jun