译文出自：登链翻译计划[1] 译者：翻译小组[2] 校对：Tiny 熊[3]
简介
在我们今天所知道和喜爱的区块链出现之前，默克尔树一直是密码学和计算机科学领域的一个方面。如今，我们开始慢慢看到它们在链上更频繁地被用于数据验证的目的。在这篇文章中，我将解释 Merkle Trees 如何在 NFT（ERC-721）背景下实现代币白名单的目的，它们是如何提供保证只能由预定参与者认领代币。
什么是 Merkle 树？
默克尔树是一种树状结构，树上的每个节点都由一个值表示，这个值是一些加密哈希函数的结果。哈希函数是单向的，从一个输入产生一个输出很容易，但从一个输出确定一个输入在计算上是不可行的。默克尔树有 3 种类型的节点，如下所示：
- 叶子节点 - 叶子节点位于树的最底部，它们的值是原始数据根据指定的哈希函数进行哈希的结果。一棵树上有多少个叶子节点，就有多少个需要哈希的原始数据。例如，如果有 7 个数据需要被哈希，就会有 7 个叶子节点。
- 父节点 - 父节点可以位于树的不同层次，这取决于整个树的大小，父节点总是位于叶节点之上。父节点的值是由它下面的节点的哈希值决定的，通常从左到右开始。由于不同的输入总是会产生不同的哈希值，不考虑哈希值的碰撞，节点哈希值的连接顺序很重要。值得一提的是，根据树的大小，父节点可以 Hash 其他父节点。
- 根节点 - 根节点位于树的顶端，由位于它下面的两个父节点的哈希值连接而成，同样从左到右开始。任何默克尔树上都只有一个根节点，根节点拥有根哈希值。
我知道这是一个需要消化的信息，所以请参考下面的图表（图 1），以便更好地了解这些树的结构。
图 1. 默克尔树结构
上下文背景
如前所述，在 NFT（ERC-721）的背景下使用 Merkle 树，如果为选定的参与者群体保留一定数量的代币，这其实就是一个白名单。Merkle 树必须是预先计算的，在这种情况下，可以让一个叶子节点代表我们白名单中的一个钱包地址。
让我们想象一下，你的项目已经确定了一个白名单策略，为选定的钱包地址保留了任意数量的代币，这些地址可能是通过竞争、抽奖或其他系统的方式选择。这些白名单上的地址可以在某个时间点（通常在公共铸币之前）能申领获得为他们保留的代币。当然，还可以出于各种其他的原因，这些可能涉及到避免高额的 Gas 费，奖励创造力，鼓励早期参与，社区参与等等。
由于这些地址是已知的，而且是不变的，我们可以使用这些信息来创建一个 Merkle 树。我们可以使用merkletreejs[4]和keccak256[5] JavaScript 库来进行实现。
注：为了简单起见，将只使用 7 个钱包地址，以保持树的大小精简。
JavaScript 实现
要做的第一件事是衍生出我们的叶子节点。如果你还记得，在一棵树上位于叶子节点正上方的每个父节点，最多只能 Hash 两个叶子节点。如果叶子节点的数量不均匀，父节点将处理一个叶子节点。每个叶子节点应该是某种形式的 Hash 数据，所以在这个例子中，让我们使用keccak256库来哈希白名单上的所有地址（图 2）。我们使用这种特定的哈希算法，因为它将在以后的 Solidity 智能合约中使用。
图 2. 衍生出叶子节点和默克尔树对象
对白名单上的所有地址进行了哈希，从而获得了我们的叶子节点，现在就可以创建 Merkle 树对象。我们使用merkletreejs库，通过调用new MerkleTree()函数，将叶子节点作为第一个参数，哈希算法作为第二个参数，{ sortPairs: true }选项作为最后一个参数。最后一个参数是可选的，但我在试图在这个例子不使用它时遇到了很大困难。
图 3. Merkle 树的可视化和根哈希。
现在已经得出了一个完整的 Merkle 树，可以通过调用 Merkle 树对象的getRoot()方法（图 3）来获得根哈希值。记住，Merkle 树的根哈希值是树上根节点正下方的两个前面的父节点的哈希值。在本例中，0xf352...和0x3cc0...。使用toString()方法在控制台打印 Merkle 树，为我们提供了一个很好的可视化的树的结构。
Merkle 树的巧妙之处在于，它不需要任何关于原始数据块的知识来验证一个节点是否属于我们的树。如果我们试图验证一个叶子节点属于我们的树，只需要知道直接相邻的叶子节点哈希值(如果有的话)，以及叶子节点正上方相邻的父节点哈希值就可以了。对于这个工作原理的简短解释，我建议查看 Tara Vancil 的这个视频[6]。这个信息被称为proof，将被 Solidity 智能合约使用，以验证调用者是否属于白名单。
网站实现
现在我们有了 Merkle 树对象和它的根哈希值，我们准备开始考虑如何让白名单用户申领他们的代币时向智能合约提供 Merkle 证明。我们需要做的是在项目网站上实现一些 JavaScript，在铸币页面上请求外部 API。这个 API 将接收连接的钱包地址，因为它是我们最初用来生成叶子节点的，并返回指定的证明。
在服务器端，你会收到地址，使用keccak256进行哈希，并使用 Merkle Tree 对象上的getHexProof()方法检索证明。下图（图 4）显示了你可能从这个 API 调用中返回的例子。
图 4. 对应地址的 Merkle 证明。编辑：0x7b 地址可以忽略，这是我的一个打印错误。
前端在收到这个证明之后，并将其作为参数与参与者的交易一起发送到合约，我们现在可以开始研究如何在智能合约中验证它。
智能合约的实现
注：本文展示的智能合约例子是用最小的代码量构建的，以展示一个概念证明。它绝不是一个你应该如何编写铸币功能的例子。
为了验证所提供的证明，需要做的第一件事是导入OpenZeppelin MerkleProof.sol contract[7](第 6 行，图 5)，这将使我们能够在智能合约代码中使用MerkleProof.verify()函数。接下来需要做的是定义根 Merkle 哈希值。如果智能合约在白名单确定之前已经被部署到以太坊主网上，那么可以假设有一些setter函数可以用来在以后的时间点更新这个值。在这个例子中，我对根 Merkle 哈希值进行了硬编码，以便在部署时被设置(第 12 行，图 5)。
图 5. 智能合约代码
接下来，我们需要验证该证明。证明是一个bytes32类型的值数组。技术上来说，它们是string类型的，但无论如何，Solidity 都会正确解释。先生成的目标叶子节点（第 25 行，图 5），如果你记得，这是一个白名单地址的keccak256哈希。在这个例子中，通过哈希msg.sender的值来生成目标叶节点。记住，这个值是不可改变的，不能被恶意改变。
由于只有白名单地址被用来生成我们的叶子节点，我们可以假设，如果一个非白名单地址试图使用有效或无效的证明来调用这个函数，生成的目标叶子节点将根本不存在于我们的 Merkle 树上，验证将失败。这个实现的最后一步只是调用MerkleProof.verify()函数，将提供的证明作为第一个参数，将根 Merkle 哈希作为第二个参数，将目标叶节点作为最后一个参数。如果这个函数返回 "false"，require 语句将失败，交易将被简单地回退，否则，该函数将继续执行，执行铸造代币逻辑。
临别赠言
我们已经学会了如何使用默克尔树实现白名单，这是一个相对简单明了的方法，展示了在 NFT 项目中使用白名单生成默克尔树，实现只有白名单中的指定地址才能申领代币。我知道还有其他的解决方案，但在我研究过的方案中，我认为迄今为止最吸引人的方案。
本翻译由 Duet Protocol[8] 赞助支持。
原文：https://medium.com/@ItsCuzzo/using-merkle-trees-for-nft-whitelists-523b58ada3f9
参考资料
[1]
登链翻译计划: https://github.com/lbc-team/Pioneer
[2]
翻译小组: https://learnblockchain.cn/people/412
[3]
Tiny 熊: https://learnblockchain.cn/people/15
[4]
merkletreejs: https://www.npmjs.com/package/merkletreejs
[5]
keccak256: https://www.npmjs.com/package/keccak256
[6]
这个视频: https://www.youtube.com/watch?v=YIc6MNfv5iQ
[7]
OpenZeppelin MerkleProof.sol contract: https://github.com/OpenZeppelin/openzeppelin-contracts/blob/master/contracts/utils/cryptography/MerkleProof.sol
[8]
Duet Protocol: https://duet.finance/?utm_souce=learnblockchain
