浅析白名单校验原理

ETH 上的GAS 不是欢乐豆

这篇文章来在于一个群中的一次关于一个项目的大讨论。

一个NFT项目 mint 的成本异常的高。售价是 0.01 但是实际上mint 的 gas 在 [email protected]的情况下。 网络并不繁忙。

项目的合约地址在下面

https://etherscan.io/address/0x99a8e1cc829d6b33dc37851466c360e08757a0ae

在 MonkeyPoly.sol 的69~76段。可以看到一个白名单校验的函数。这里存在着一个循环结构。我们知道ETH上的计算是需要gas的,所以这里的一个对白名单列表的遍历。就是调用高gas的元凶。

function isWhitelisted(address _user) public view returns (bool) {
    for (uint i = 0; i < whitelistedAddresses.length; i++) {
      if (whitelistedAddresses[i] == _user) {
        return true;
      }
    }
    return false;
  }

而在另一段代码里面我们看到了写入白名单的地方

function whitelistUsers(address[] calldata _users) public onlyOwner {
    delete whitelistedAddresses;
    whitelistedAddresses = _users;
  }

这里项目方直接把地址列表给导入了进去,通过传参的方式。十分的生猛。

这里的gas 消耗,可以参考下文,记录了每个evm操作符消耗的 gas 情况。对上面的来进行一个估算。

以太坊的存储成本_跨链技术践行者-CSDN博客

evm-opcode-gas-costs/opcode-gas-costs_EIP-150_revision-1e18248_2017-04-12.csv at master · djrtwo/evm-opcode-gas-costs

所以在这里,项目方付出了巨大的存储成本。 用户付出了巨大的gas 成本。矿工窃喜。

https://etherscan.io/address/0x99a8e1cc829d6b33dc37851466c360e08757a0ae

具体的mint 成本,可以在这里里面看到,很多都是 out of gas 导致交易被 Reverted了. 真的ETH 就是欢乐豆了呗。

优雅的做法

合约里的实现

在一般项目的白名单机制中普遍使用默克尔树来实现。

简单讲计算所有白名单钱包地址得到默克尔树的Root hash。

在合约中只需要存储Root hash值,在调用mint函数时页面上的JS代码基于钱包地址生成proof路径(地址的上级父节点hash),合约就可以校验该地址是否属于白名单。

这里使用 https://etherscan.io/address/0x6fd053bff10512d743fa36c859e49351a4920df6#code

这个项目的代码为例子。选取部分的nft预售的代码,内容如下,可见这里对于预售的调用做了 merkleProof 的判断。来验证是否是白名单用户。比那个 循环实现要好上太多。

// 预售代码
function mintNFTDuringPresale(
        uint256 _numOfTokens,
        bytes32[] memory _proof
    ) 
        public 
        payable
    {
        require(isActive, 'Sale is not active');
        require(isPresaleActive, 'Whitelist is not active');
        require(verify(_proof, bytes32(uint256(uint160(msg.sender)))), "Not whitelisted");
        // ...

verify 的函数实现代码如下

// Verify MerkleProof
    function verify(bytes32[] memory proof, bytes32 leaf) public view returns (bool) {
        bytes32 computedHash = leaf;

        for (uint256 i = 0; i < proof.length; i++) {
            bytes32 proofElement = proof[i];
            
            if (computedHash <= proofElement) {
                // Hash(current computed hash + current element of the proof)
                computedHash = sha256(abi.encodePacked(computedHash, proofElement));
            } else {
                // Hash(current element of the proof + current computed hash)
                computedHash = sha256(abi.encodePacked(proofElement, computedHash));
            }
        }

        // Check if the computed hash (root) is equal to the provided root
        return computedHash == root;
    }

Dapp 中的实现

前面提到,在使用默克尔树进行验证 的情况下,在合约中只需要保存一个 默克尔根。由用户在前端提供 proof 来证明自己在 默克尔树中。默克尔树这一个结构是比较熟悉的了。下面给出简单的结构。数据在 最终的block中,进行hash 之后得到叶子,叶子再进行hash 之后得到父节点,最终得到一个 Root hash。位于树上叶节点正上方的每个父节点最多只能培养两个叶节点。如果存在奇数个叶节点,则父节点将培育一个叶节点。

当白名单的地址是恒定且已知的话,就可以使用 merkle tree 的结构来把数据构造出来。下面给出引用的代码片段,下面是 使用 merkletreejskeccak256 来实现的 默克尔树的构建。

最终的运行结果如下图

Merkle Tree 的独创性点在于它不需要任何原始数据来验证节点是否存在于树中。只需要知道直接相邻叶节点哈希(如果有的话)和直接在叶节点上方的相邻父节点哈希。所以这一段称之为 默克尔路径。

所以,我们会最终得到一个类似这样的 默克尔路径。

Merkle Proof for Address 0x7b6217492d5B7088A8b7adE75364F289Caa1A0Fe
[
	'Oxd7a3faaaa893aa663f894f29aae4851e028b4ffa394e825816b5cb3b163b20ce'
	'0x6dcecbf773ecd9d6a2dffe343430bdb01d2d1efcc872e072201ffcd0133adeb0'
	'0x3cc09b3073afe3acf80dc067d2b5b4672dc055430f1cf45bf155e6eeb36ec010'
]

回到上面的合约的校验代码,如果如果我提供的 proof 可以通过校验,那么我就可以证明我是存在这个原始列表中。交易不会被require 终止。

小结

到这里可以看到,使用默克尔树的方法在 EVM 上的实现,比使用循环来进行地址校验的方式优雅太多,只需要简单的几次hash 操作就可以完成校验,而且项目方更新白名单也可以简单的通过修改默克尔树的方式来实现。

更具体的实现细节可以看这篇 medium

Using Merkle Trees for NFT Whitelists

另一个问题

对于已知白名单的项目我们可以直接使用 默克尔书的方式来进行验证。但是像是 stopdao 这种项目。对于每一个参与OS 的人都可以获得空投。项目方不可能或者说很难获得全部的交互过的用户地址。怎么处理呢。

见到来说,这一类 我称之为 土DAO的原理是:后端私钥签名,合约公钥验证。当然这种方式的问题也先提出来:项目方有私钥在手,可以随随便便的签。所以理论上是无限量增发的。

我们可以使用 SOS 的代码来进行分析。在Claim函数中我们可以看到最后一个 require

function claim(uint256 amountV, bytes32 r, bytes32 s) external {
        uint256 amount = uint248(amountV);
        uint8 v = uint8(amountV >> 248);
        uint256 total = _totalSupply + amount;
        require(total <= MAX_SUPPLY, "OpenDAO: Exceed max supply");
        require(minted(msg.sender) == 0, "OpenDAO: Claimed");
				// 这里得到提交的数据指纹
        bytes32 digest = keccak256(abi.encodePacked("\\x19Ethereum Signed Message:\\n32", 
            ECDSA.toTypedDataHash(_domainSeparatorV4(),
                keccak256(abi.encode(MINT_CALL_HASH_TYPE, msg.sender, amount))
        )));
        // 这里对后端签出来的数据来进行验证,看看签名者是不是 cSinger 也就是项目作者。
        require(ecrecover(digest, v, r, s) == cSigner, "OpenDAO: Invalid signer");
        _totalSupply = total;
        _mint(msg.sender, amount);
    }

两行关键代码已经写在上面了,可以看到在这种方式是依靠 项目方在后端来进行的签名来实现对Claim数量的确定。问题就是没有公开性。依赖项目方来进行签名。

总结

这篇文章,通过一个失败的例子来简单讲了一下 现在常用的白名单验证方式。后面拓展一下 土DAO 的白名单原理。有不正确的地方也欢迎大家指出。共同学习进步

留下点什么吧