很多时候，协议需要验证某项内容是否属于某个已知集合。天真地认为，可以将所有有效值作为 mapping 存储在链上。这种方法只需读取一个存储槽，因此在验证成员资格时效率很高。但是，在链上提交这类数据的成本会非常高，尤其是对于大型数据集。以空投为例，通常会有数千个符合条件的接收者。如果要在 mapping 中存储 1000 个地址，成本将高达 20M gas！
如果我们采取以下措施，就能改进传统方法，避免链上存储的大部分成本：
- 只在链上存储整个集合的哈希值，例如
keccak256(abi.encode([...SET_ITEMS]))。 - 当我们需要检查成员资格时，也要求调用者在调用中传递整个集合。
- 确保传入的集合哈希值与我们存储的哈希值相匹配。
- 对集合进行遍历，找到有问题的 item。
这种方法适用于小型数据集，但如果数据集变大，这种方法很快就会难以为继，因为它要求迭代次数与集合成线性增长。对于潜在的大型集合，我们需要一种扩展性更好的解决方案。
默克尔树是默克尔证明中测试的底层数据结构，许多区块链都以某种形式支撑着默克尔树。比特币将一个区块中的所有交易都浓缩在一棵默克尔树的唯一树根中，这一点非常有名。
简单来说，默克尔树是一种二叉树，其中每个叶子节点都保存了集合中一个数据的哈希值，每个非叶子节点则保存其两个子节点的哈希值。
与基于哈希值的解决方案一样，通过默克尔证明，我们仍将在链上存储一个哈希值来代表整个集合：默克尔树的根哈希值。我们还需要与我们的合约进行特定的交互，以传递额外的数据来证明某物属于该集合，但由于默克尔树的分层性质，这次我们不需要提供整个集合。
要证明某项内容属于默克尔树，我们只需推导出默克尔树的根，并检查它是否与我们存储的内容相匹配。我们接受相关 item，以及我们在寻找默克尔根时会遇到的任何树节点的相邻节点的哈希值。由于二叉树有 log2(N) 层，因此我们的证明只需对数复杂度。
举例说明，在前面提供的默克尔树中，我们可以通过推导根 (N0) 来证明 item2 属于默克尔树。为此，我们只需要 item2 以及 N1 和 N6 的哈希值：
特别是在智能合约中，默克尔证明通常用于集合上限过大或未知/无限的情况。
- 空投（默克尔空投）和限制性铸币厂经常使用默克尔根。UNI 空投是第一批高知名度的默克尔空投之一。
- OpenZeppelin 有一个方便的库，你只需将其导入到你的合约中，即可使用默克尔证明。
- Fractional V2 在其保险库中使用默克尔证明来限制可调用的函数。
虽然证明默克尔根的成本相对较低，但计算典型默克尔根（初始哈希值）的成本却不低，因为它必须遍历整棵树。因此，这种计算通常在链外完成，并传入智能合约中立即存储。这个过程显然意味着某种可信的设置。对于某些应用来说，这种集中化是一种可以接受的权衡。好的一面是，只要授权机构也共享整套数据，所提供的根哈希值就可以独立验证是否真实，因为任何人都可以使用它自己推导出根哈希值。
所提供的示例使用默克尔证明实现了空投（MerkleDrop）。使用每个接收者地址的哈希值 + 索赔金额构建一棵默克尔树，填充树叶。值得注意的是，这种特定的默克尔树实现实际上是一种"稀疏默克尔树"，它通过用 0 值代替真实哈希值来替换缺失（未使用）的子树，从而提高了普通默克尔树的空间复杂度。这样，我们就不必创建叶节点数量为 2 的次幂的树了。
此外，我们还提供了一个实用合约（MerkleDropHelper），它可以构建一棵默克尔树，并从中生成一个证明。通常这将作为一个链外库实现，但为了获得更好的阅读体验，我们在 Solidity 中提供了这个库。