Solidity中的默尔克树终极指南

• 原文链接： https://soliditydeveloper.com/merkle-tree
• 译文出自：登链翻译计划
• 译者：翻译小组 校对：Tiny 熊
• 本文永久链接：learnblockchain.cn/article…

我们大多数人现在可能已经听说过Merkle树了。它们在区块链的世界里到处都被使用。

但是，你真的清楚地知道:

• 它们是如何工作的？
• 使用它们的最佳方式是什么？
• 默克尔(Merkle)树的未来是什么？

哈哈，这不是默克尔(Merkle)树

什么是默克尔树？

Ralph Merkle在1979年已经发明了默克尔树（Merkle Tree）。要理解的最重要的概念是Merkle树，这是一棵Merkle树：

在Merkle树的根部是根哈希。它是通过哈希所有的原始值作为叶子节点而创建的。现在，两个叶子的哈希值通过创建一个新的哈希值被组合在一起。我们一直这样做，直到我们有一棵只有一个根哈希值的树。

现在，一个Merkle证明是你向只知道根哈希值的人证明任何值实际上是这棵树的叶子之一。例如，你可以证明L3确实包含一个给定的值。人们需要做的就是提供Hash0，Hash1-1和L3块本身。现在对于证明验证，人们可以计算L3的哈希值，然后是Hash1，最后是Top Hash。然后我们可以将根哈希值与我们已知的根哈希值进行比较。对于Merkle证明的直观解释，请查看这个出色的视频解释。

正如你所看到的，对于一个成功的Merkle证明，你需要提供每个树级的所有兄弟节点，请记住这一点，因为我们可能会在本篇文章的后面改进这一点。

为什么这样就够了？因为当使用像 keccak256 这样的安全哈希函数时，实际上是不可能产生哈希碰撞的，这意味着几乎可以将无限的潜在输入空间减少到只有256位，两组不同的输入计算出相同的哈希值的可能性非常低，在实践中根本不会发生。现在，如果你在Merkle证明中匹配一个的根哈希值，你就知道这一项确实是原始根哈希值计算的一部分。

Solidity 中的Merkle证明

来自Openzeppelin合约的MerkleProof.sol是一个很好的入门方法。所以我们来看看他们是如何实现的。

verifyCalldata接收 bytes32数组形式proof（证明）、Merkle根哈希值及要验证的叶子。通常情况下，根是你存储在智能合约中的数据，proof（证明）是来自某人在链外创建的数据，以便向合约证明叶子是原始树的一部分。

而processProofCalldata将遍历 proof 数组中的每个元素：

1. 从叶子结点开始。

2. 然后在每一步中，通过与proof中的下一个元素哈希来更新的计算哈希.

   1. 将两个哈希值一起哈希，总是先取较小的值。
   2. Openzeppelin使用 keccak256操作码的汇编来实现更有效的哈希。或者可以使用Solidity：keccak256(abi.encodePacked(a, b))。

3. 返回计算出的哈希值。

最后回到verifyCalldata函数中，简单地验证计算的哈希值与预期的根哈希值相匹配。

function verifyCalldata(
    bytes32[] calldata proof,
    bytes32 root,
    bytes32 leaf
) internal pure returns (bool) {
    return processProofCalldata(proof, leaf) == root;
}

function processProofCalldata(
    bytes32[] calldata 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;
}

function _hashPair(bytes32 a, bytes32 b)
    private
    pure
    returns(bytes32)
{
    return a < b ? _efficientHash(a, b) : _efficientHash(b, a);
}

function _efficientHash(bytes32 a, bytes32 b)
    private
    pure
    returns (bytes32 value)
{
    assembly {
        mstore(0x00, a)
        mstore(0x20, b)
        value := keccak256(0x00, 0x40)
    }
}

比特币中的默克尔证明

在区块链世界中，Merkle证明可以追溯到最开始，在2008年发布的Bitcoin PDF中，用来证明交易的被包含。它详细介绍了一种机制，为没有下载完整区块链的轻客户验证交易状态，即简化支付验证（SPV：Simplified Payment Verification ）。

比特币轻客户端，与完整节点相比，只下载区块链的区块头。一个区块头相当小，只包含上一个区块根Hash、当前区块根Hash、时间戳、难度和nonce。这使得移动设备也能参与到网络中，而不需要大量的数据存储。

要弄清楚一笔交易是否包含在区块链中，只需向一个下载了区块链的完整节点索取Merkle证明。完整的节点可以寻找包含交易的区块，然后创建一个Merkle证明，验证这个特定的交易匹配轻客户端已知的区块根Hash。

很好，所以现在轻客户端可以自己验证交易，而无需下载完整的区块链。但是，像以太坊中的状态这样更复杂的东西呢？

以太坊中的默克尔证明

现在对于以太坊，我们还有智能合约状态。除了包含交易的Merkle证明外，还有第二个状态根哈希，可以证明一个账户在某个区块有特定的以太币余额。另外，也可以证明一个智能合约在某个区块有一个特定的状态。在以太坊中还有一个用于记录日志的第三个根哈希值。它可以证明一个特定的事件发生在那个区块。

我们将在后面看看如何在Merkle证明中使用这些特殊的以太坊根哈希值。当然，我们也可以创建自己的根哈希值并在我们的智能合约中使用它们。有很多方法可以做到这一点。让我们来探讨一些...

1. 高效的空投

Merkle树的一个常见使用场景是空投，因为Merkle证明允许我们非常有效地实现ERC20代币空投。使用上面提到的Openzeppelin MerkleProof库，其实现相当简单：

contract MerkleDistributor {
    address public immutable token;
    bytes32 public immutable merkleRoot;

    mapping(address => bool) public isClaimed;

    constructor(address token_, bytes32 merkleRoot_) {
        token = token_;
        merkleRoot = merkleRoot_;
    }

    function claim(
        address account,
        uint256 amount,
        bytes32[] calldata merkleProof
    ) external {
        require(!isClaimed[account], 'Already claimed.');

        bytes32 node = keccak256(
            abi.encodePacked(account, amount)
        );
        bool isValidProof = MerkleProof.verifyCalldata(
            merkleProof,
            merkleRoot,
            node
        );
        require(isValidProof, 'Invalid proof.');

        isClaimed[account] = true;
        require(
            IERC20(token).transfer(account, amount),
            'Transfer failed.'
        );
    }
}

A. 创建Merkle分发合约

让我们首先创建分发合约，它将持有所有的代币，或者允许铸造新的代币。

核心是 claim (申领)函数，它接收用户地址、金额和Merkle证明。Merkle 根最初是在部署合约时存储的。

在claim中，需要验证：

1. 原始Merkle树确实包含一个叶子，其值与账户地址和金额相匹配
2. 用户还没有认领代币。

第一部分正是使用Openzeppelin的MerkleProof.verifyCalldata进行Merkle证明验证。对于第二部分，我们只需将账户存储在一个映射到布尔值的 mapping 中。

但现在我们要如何创建这个原始Merkle树和所有的证明呢？这不是 Solidity 的一部分，而是发生在链外。接下来让我们来探讨一下。

B. 创建Merkle树和证明

我们可以使用 merkletreejs 来创建 Merkle 根的哈希值，以及获得单个证明。

const keccak256 = require("keccak256");
const { MerkleTree } = require("merkletreejs");
const Web3 = require("web3");

const web3 = new Web3();

let balances = [
  {
    addr: "0xb7e390864a90b7b923c9f9310c6f98aafe43f707",
    amount: web3.eth.abi.encodeParameter(
      "uint256",
      "10000000000000000000000000"
    ),
  },
  {
    addr: "0xea674fdde714fd979de3edf0f56aa9716b898ec8",
    amount: web3.eth.abi.encodeParameter(
      "uint256",
      "20000000000000000000000000"
    ),
  },
];

const leafNodes = balances.map((balance) =>
  keccak256(
    Buffer.concat([
      Buffer.from(balance.addr.replace("0x", ""), "hex"),
      Buffer.from(balance.amount.replace("0x", ""), "hex"),
    ])
  )
);

const merkleTree = new MerkleTree(leafNodes, keccak256, { sortPairs: true });

console.log("---------");
console.log("Merke Tree");
console.log("---------");
console.log(merkleTree.toString());
console.log("---------");
console.log("Merkle Root: " + merkleTree.getHexRoot());

console.log("Proof 1: " + merkleTree.getHexProof(leafNodes[0]));
console.log("Proof 2: " + merkleTree.getHexProof(leafNodes[1]));

1. 首先，我们必须对地址和参数进行编码， Web3.js可以帮助我们解决这个问题。
2. 然后我们可以使用keccak256来计算每个余额的地址和金额的哈希值。
3. 上一步的结果是我们的叶子节点，使用merkletreejs ，叶子作为输入， 创建一个新的Merkle树。
4. 我们可以使用merkleTree.toString()打印完整的树。
5. 或者我们可以打印单个证明或根哈希值。

---------
Merke Tree
---------
└─ 399f97e5a31d2[...]c9f3379ff72
   ├─ dd3f64a1b692[...]38dfdd8578
   └─ 15e70077678[...]e7944f27e36

---------
Merkle Root: 0x399f97e5[...]f37d0379ff72
Proof 1: 0x15e7001d277[...]79440b8f27e36
Proof 2: 0xdd3f64a1877[...]38df4b9dd8578

现在，原始根将被存储在合约中。所以你可以看到，像这样做一个空投是相当便宜的，只需部署一个小合约，并存储根的哈希值。

而且用户可以在链外单独创建他们的证明，并在他们需要的时候 claim 代币。

C. 改进Merkle 空投的Gas成本

我们可以通过将已经认领的代币的映射存储为位图来进一步改进这一机制。我以前解释过Solidity中的位图的概念。这个优化是来自Uniswap。

对于我们的空投，可以简单地将余额数组的索引添加到证明本身。然后，在存储申领的状态时，只需在 uint256 => uint256 映射中更新一个位。

mapping(uint256 => uint256) private claimedBitMap;

function isClaimed(uint256 index) public view returns (bool) {
    uint256 claimedWordIndex = index / 256;
    uint256 claimedBitIndex = index % 256;
    uint256 claimedWord = claimedBitMap[claimedWordIndex];
    uint256 mask = (1 << claimedBitIndex);
    return claimedWord & mask == mask;
}

function _setClaimed(uint256 index) private {
    uint256 claimedWordIndex = index / 256;
    uint256 claimedBitIndex = index % 256;
    claimedBitMap[claimedWordIndex] = claimedBitMap[claimedWordIndex] | (1 << claimedBitIndex);
}

function claim(uint256 index, address account, uint256 amount, bytes32[] calldata merkleProof) external {
    require(!isClaimed(index), 'MerkleDistributor: Drop already claimed.');
    [...]
    _setClaimed(index);
    [...]
}

2. 空投NFT

与空投ERC20代币的方式类似，我们可以使用Merkle证明来空投NFT。一个允许向一个地址空投多个NFT的简单实现如右图所示。

• 我们首先验证申领，就像空投 ERC20 一样。
• 然后我们为每一个应该被空投的金额铸造一个新的NFT。

这是一个不完整的例子，但想法应该是清楚的。也可以把它和之前的位图技巧结合起来，以节省更多的Gas：

function _mint(
    address to, 
    uint256 amount, 
    bytes32[] calldata merkleProof
) internal virtual {
    require(!minted[to] && _verifyClaim(to, amount, merkleProof));
    minted[to] = true;

    uint256 newId = currentId;
    balanceOf[to] += amount;

    for (uint256 i; i < amount; i++) {
        _ownerships[newId] = to;
        newId++;
    }

    currentId = newId;
}

function _verifyClaim(
    address who,
    uint256 amount,
    bytes32[] memory merkleProof
) internal view returns (bool) {
    bytes32 node = keccak256(
        abi.encodePacked(account, amount)
    );
    return MerkleProof.verify(merkleProof, MERKLE_ROOT, node);
}

4. 在合约内创建证明

我不确定直接在合约内创建证明的使用场景是什么，但这当然是可能的。你可以使用murky来实现这个。

创建一个新的Merkle合约，你对它调用getProof 就可以了!

现在，这会是一个怎样的使用场景呢？我不确定，请在评论中告诉我。

// Initialize
Merkle m = new Merkle();
// Toy Data
bytes32[] memory data = new bytes32[](4);
data[0] = bytes32("0x0");
data[1] = bytes32("0x1");
data[2] = bytes32("0x2");
data[3] = bytes32("0x3");
// Get Root, Proof, and Verify
bytes32 root = m.getRoot(data);
bytes32[] memory proof = m.getProof(data, 2); 

5. 证明以太坊智能合约状态

一个更高级和非常强大的使用场景是证明智能合约的状态! 有了这个，我们基本上可以向智能合约证明，任何智能合约在过去有一个特定的状态。这是非常强大的东西。

然而，它只对过去的256个块起作用，原因是EVM只能访问最后256个块的块根哈希值。而这个根哈希值将被需要用来验证证明。所以这允许证明大约过去一小时的状态。

要验证这样的证明就有点复杂了，需要了解：

• Merkle-Patricia-Tries：以太坊的状态树不只是一个普通的Merkle树，而是使用Merkle-Patricia-Tries。它允许在更新后快速计算新的树根，而无需重新计算整个树。主要的想法是，存储一个值的键被编码为从树上取下的 "路径"。
• RLP-Encoding：递归长度前缀(RLP)序列化是一种空间效率高的格式，用于编码以太坊中的数据。你不需要了解它的所有细节。因为幸运的是有一个Solidity RLP库你可以使用。

Merkle证明在Merkle-Patricia-Trie中的工作方式不同，但你可以在这里找到一个完整的Solidity例子。

证明智能合约的状态可以分解为证明单个智能合约的存储槽。结合RLP编码，下方代码。你可以在Solidity 文档中阅读关于存储槽的概念。

function extractSlotValueFromProof(
    bytes32 _slotHash,
    bytes32 _storageRootHash,
    RLPReader.RLPItem[] memory _proof
)
    internal pure returns (SlotValue memory)
{
    bytes memory valueRlpBytes = MerklePatriciaProofVerifier.extractProofValue(
        _storageRootHash,
        abi.encodePacked(_slotHash),
        _proof
    );

    SlotValue memory value;

    if (valueRlpBytes.length != 0) {
        value.exists = true;
        value.value = valueRlpBytes.toRlpItem().toUint();
    }

    return value;
}

而自EIP-1186以来，有一个RPC方法叫做eth_getProof，它有助于创建这样一个证明。

你可以在 这里找到完整的 Solidity 示例。

6. 乐观Rollup

乐观 Rollup（Optimistic Rollup）是建立在前面提到的状态证明之上的。我们已经在之前详细解释过，但这里的主要思想是：

• 将智能合约的状态表示为Merkle树

• 只在 乐观Rollup 链（Layer2）上运行所有交易

• 持续（乐观地）更新以太坊第1层的状态根部

• 乐观Rollup 的安全性低，但通过以太坊上的状态根，则可以实现欺诈证明

  • 当中继者提交恶意的状态根并被质疑时，他们会失去他们的抵押（bond）。

  • 欺诈证明相当昂贵，所以它们实际上并不意味着要经常做。

  • 运行有争议的整个交易，并提交任何需要的状态作为状态Merkle证明。

这就是扩容的来源，你只在第一层运行有争议的交易，并提交欺诈证明，这就带来了收益。不过运行一个欺诈证明的交易实际上比直接在第1层运行更昂贵。

因此，扩展的优势完全来自于你99.9%的交易不会在第1层运行这一事实。

未来 = Verkle Trees?

Merkle Trees的一个改进可能是Verkle Trees。它们是非常新的，还没有在以太坊中使用。它们背后的主要想法是极大地减少证明的大小。回顾一下，Merkle证明包括从根到叶每一级的所有兄弟节点。这可能是一个很大的数据，特别是对于宽的树。

Verkle树不要求你在证明中提供兄弟姐妹，而是利用多项式承诺。它们将允许你证明一些数据zi包含在一个列表[z0, z1, z2...]中。这里的列表当然是同一层次中所有兄弟姐妹的哈希值，我们所关心的是当前的哈希值确实是其中的一部分。将其与允许通过随机评估的多重验证的技术相结合，会得到更高效的Verkle Trees。

阅读Vitalik 关于Verkle Trees的文章了解更多细节。

以太坊有计划在第三个升级阶段将Merkle-Patricia-Tries升级到Verkle Trees，称为The Verge。

1. The Merge是权益证明。
2. The Surge是 分片。
3. The Verge是Verkle trees。
4. The Purge是指像状态过期和删除旧的历史。
5. The Splurge是所有其他有趣的东西。