{"content":{"title":"Solidity中的默尔克树终极指南","body":"> * 原文链接： https://soliditydeveloper.com/merkle-tree\r\n> * 译文出自：[登链翻译计划](https://github.com/lbc-team/Pioneer)\r\n> * 译者：[翻译小组](https://learnblockchain.cn/people/412)  校对：[Tiny 熊](https://learnblockchain.cn/people/15)\r\n> * 本文永久链接：[learnblockchain.cn/article…](https://learnblockchain.cn/article/5297)\r\n\r\n\r\n\r\n\r\n\r\n\r\n我们大多数人现在可能已经听说过Merkle树了。它们在区块链的世界里到处都被使用。\r\n\r\n但是，你真的清楚地知道:\r\n\r\n- 它们是如何工作的？\r\n- 使用它们的最佳方式是什么？\r\n- 默克尔(Merkle)树的未来是什么？\r\n\r\n![默克尔树](https://img.learnblockchain.cn/2023/01/12/merkel-tree.jpg)\r\n\r\n> 哈哈，这不是默克尔(Merkle)树\r\n\r\n\r\n\r\n## 什么是默克尔树？\r\n\r\n[Ralph Merkle](https://en.wikipedia.org/wiki/Ralph_Merkle)在1979年已经发明了默克尔树（Merkle Tree）。要理解的最重要的概念是Merkle树，这是一棵Merkle树：\r\n\r\n![Merkle树](https://img.learnblockchain.cn/2023/01/12/merkle-tree.png)\r\n\r\n在**Merkle树**的根部是根哈希。它是通过哈希所有的原始值作为叶子节点而创建的。现在，两个叶子的哈希值通过创建一个新的哈希值被组合在一起。我们一直这样做，直到我们有一棵只有一个根哈希值的树。\r\n\r\n现在，一个**Merkle证明**是你向**只知道根哈希值的人证明**任何值实际上是这棵树的叶子之一。例如，你可以证明L3确实包含一个给定的值。人们需要做的就是提供Hash0，Hash1-1和L3块本身。现在对于证明验证，人们可以计算L3的哈希值，然后是Hash1，最后是Top Hash。然后我们可以将根哈希值与我们已知的根哈希值进行比较。对于Merkle证明的直观解释，请查看[这个出色的视频解释](https://www.youtube.com/watch?v=2kPFSoknlUU)。\r\n\r\n正如你所看到的，对于一个成功的Merkle证明，你需要提供**每个树级的所有兄弟节点**，请记住这一点，因为我们可能会在本篇文章的后面改进这一点。\r\n\r\n为什么这样就够了？因为当使用像 `keccak256` 这样的安全哈希函数时，实际上是不可能产生哈希碰撞的，这意味着几乎可以将无限的潜在输入空间减少到只有256位，两组不同的输入计算出相同的哈希值的可能性非常低，在实践中根本不会发生。现在，如果你在Merkle证明中匹配一个的根哈希值，你就知道这一项确实是原始根哈希值计算的一部分。\r\n\r\n\r\n\r\n## Solidity 中的Merkle证明\r\n\r\n来自Openzeppelin合约的[MerkleProof.sol](https://github.com/OpenZeppelin/openzeppelin-contracts/blob/master/contracts/utils/cryptography/MerkleProof.sol)是一个很好的入门方法。所以我们来看看他们是如何实现的。\r\n\r\n`verifyCalldata`接收 bytes32数组形式`proof`（证明）、Merkle根哈希值及要验证的叶子。通常情况下，**根是你存储在智能合约中的数据**，`proof`（证明）是来自某人在链外创建的数据，以便向合约证明叶子是原始树的一部分。\r\n\r\n而`processProofCalldata`将遍历 `proof` 数组中的每个元素：\r\n\r\n1. 从叶子结点开始。\r\n2. 然后在每一步中，通过与`proof`中的下一个元素哈希来更新的计算哈希.\r\n   1. 将两个哈希值一起哈希，总是先取较小的值。\r\n   2. Openzeppelin使用 `keccak256 `操作码的汇编来实现更有效的哈希。或者可以使用Solidity：`keccak256(abi.encodePacked(a, b))`。\r\n\r\n3. 返回计算出的哈希值。\r\n\r\n\r\n\r\n最后回到`verifyCalldata`函数中，简单地**验证**计算的哈希值与预期的根哈希值相匹配。\r\n\r\n```solidity\r\nfunction verifyCalldata(\r\n    bytes32[] calldata proof,\r\n    bytes32 root,\r\n    bytes32 leaf\r\n) internal pure returns (bool) {\r\n    return processProofCalldata(proof, leaf) == root;\r\n}\r\n\r\nfunction processProofCalldata(\r\n    bytes32[] calldata proof,\r\n    bytes32 leaf,\r\n) internal pure returns (bytes32) {\r\n    bytes32 computedHash = leaf;\r\n    for (uint256 i = 0; i < proof.length; i++) {\r\n        computedHash = _hashPair(computedHash, proof[i]);\r\n    }\r\n    return computedHash;\r\n}\r\n\r\nfunction _hashPair(bytes32 a, bytes32 b)\r\n    private\r\n    pure\r\n    returns(bytes32)\r\n{\r\n    return a < b ? _efficientHash(a, b) : _efficientHash(b, a);\r\n}\r\n\r\nfunction _efficientHash(bytes32 a, bytes32 b)\r\n    private\r\n    pure\r\n    returns (bytes32 value)\r\n{\r\n    assembly {\r\n        mstore(0x00, a)\r\n        mstore(0x20, b)\r\n        value := keccak256(0x00, 0x40)\r\n    }\r\n}\r\n```\r\n\r\n\r\n\r\n## 比特币中的默克尔证明\r\n\r\n在区块链世界中，Merkle证明可以追溯到最开始，在2008年发布的[Bitcoin PDF](https://bitcoin.org/bitcoin.pdf)中，用来证明交易的被包含。它详细介绍了一种机制，为没有下载完整区块链的轻客户验证交易状态，即简化支付验证（SPV：Simplified Payment Verification ）。\r\n\r\n比特币轻客户端，与完整节点相比，只下载区块链的区块头。一个区块头相当小，只包含上一个区块根Hash、当前区块根Hash、时间戳、难度和nonce。这使得移动设备也能参与到网络中，而不需要大量的数据存储。\r\n\r\n要弄清楚一笔交易是否包含在区块链中，只需向一个下载了区块链的完整节点索取Merkle证明。完整的节点可以寻找包含交易的区块，然后创建一个Merkle证明，验证这个特定的交易匹配轻客户端已知的区块根Hash。\r\n\r\n很好，所以现在轻客户端可以自己验证交易，而无需下载完整的区块链。但是，像以太坊中的状态这样更复杂的东西呢？\r\n\r\n![Merkle Tree Meme](https://img.learnblockchain.cn/2023/01/12/merkle-trees-meme.jpeg)\r\n\r\n\r\n\r\n## 以太坊中的默克尔证明\r\n\r\n\r\n现在对于以太坊，我们还有智能合约状态。除了包含交易的Merkle证明外，还有第二个状态根哈希，可以证明一个账户在某个区块有特定的以太币余额。另外，也可以证明一个智能合约在某个区块有一个特定的状态。在以太坊中还有一个用于记录日志的第三个根哈希值。它可以证明一个特定的事件发生在那个区块。\r\n\r\n我们将在后面看看如何在Merkle证明中使用这些特殊的以太坊根哈希值。当然，我们也可以创建自己的根哈希值并在我们的智能合约中使用它们。有很多方法可以做到这一点。让我们来探讨一些...\r\n\r\n\r\n\r\n### 1. 高效的空投\r\n\r\n![Airdrop Meme](https://img.learnblockchain.cn/2023/01/12/free-airdrop-meme.jpeg)\r\n\r\nMerkle树的一个常见使用场景是空投，因为Merkle证明允许我们非常有效地实现**ERC20代币空投**。使用上面提到的Openzeppelin MerkleProof库，其实现相当简单：\r\n\r\n```solidity\r\ncontract MerkleDistributor {\r\n    address public immutable token;\r\n    bytes32 public immutable merkleRoot;\r\n\r\n    mapping(address => bool) public isClaimed;\r\n\r\n    constructor(address token_, bytes32 merkleRoot_) {\r\n        token = token_;\r\n        merkleRoot = merkleRoot_;\r\n    }\r\n\r\n    function claim(\r\n        address account,\r\n        uint256 amount,\r\n        bytes32[] calldata merkleProof\r\n    ) external {\r\n        require(!isClaimed[account], 'Already claimed.');\r\n\r\n        bytes32 node = keccak256(\r\n            abi.encodePacked(account, amount)\r\n        );\r\n        bool isValidProof = MerkleProof.verifyCalldata(\r\n            merkleProof,\r\n            merkleRoot,\r\n            node\r\n        );\r\n        require(isValidProof, 'Invalid proof.');\r\n\r\n        isClaimed[account] = true;\r\n        require(\r\n            IERC20(token).transfer(account, amount),\r\n            'Transfer failed.'\r\n        );\r\n    }\r\n}\r\n```\r\n\r\n\r\n\r\n#### A. 创建Merkle分发合约\r\n\r\n让我们首先创建分发合约，它将持有所有的代币，或者允许铸造新的代币。\r\n\r\n核心是 `claim` (申领)函数，它接收用户地址、金额和Merkle证明。Merkle 根最初是在部署合约时存储的。\r\n\r\n在`claim`中，需要验证：\r\n\r\n1. 原始Merkle树确实包含一个叶子，其值与账户地址和金额相匹配\r\n2. 用户还没有认领代币。\r\n\r\n\r\n\r\n第一部分正是使用Openzeppelin的`MerkleProof.verifyCalldata`进行Merkle证明验证。对于第二部分，我们只需将账户存储在一个映射到布尔值的 mapping 中。\r\n\r\n但现在我们要如何创建这个原始Merkle树和所有的证明呢？这不是 Solidity 的一部分，而是发生在链外。接下来让我们来探讨一下。\r\n\r\n\r\n\r\n#### B. 创建Merkle树和证明\r\n\r\n我们可以使用 [merkletreejs](https://github.com/miguelmota/merkletreejs) 来创建 Merkle 根的哈希值，以及获得单个证明。\r\n```javascript\r\nconst keccak256 = require(\"keccak256\");\r\nconst { MerkleTree } = require(\"merkletreejs\");\r\nconst Web3 = require(\"web3\");\r\n\r\nconst web3 = new Web3();\r\n\r\nlet balances = [\r\n  {\r\n    addr: \"0xb7e390864a90b7b923c9f9310c6f98aafe43f707\",\r\n    amount: web3.eth.abi.encodeParameter(\r\n      \"uint256\",\r\n      \"10000000000000000000000000\"\r\n    ),\r\n  },\r\n  {\r\n    addr: \"0xea674fdde714fd979de3edf0f56aa9716b898ec8\",\r\n    amount: web3.eth.abi.encodeParameter(\r\n      \"uint256\",\r\n      \"20000000000000000000000000\"\r\n    ),\r\n  },\r\n];\r\n\r\nconst leafNodes = balances.map((balance) =>\r\n  keccak256(\r\n    Buffer.concat([\r\n      Buffer.from(balance.addr.replace(\"0x\", \"\"), \"hex\"),\r\n      Buffer.from(balance.amount.replace(\"0x\", \"\"), \"hex\"),\r\n    ])\r\n  )\r\n);\r\n\r\nconst merkleTree = new MerkleTree(leafNodes, keccak256, { sortPairs: true });\r\n\r\nconsole.log(\"---------\");\r\nconsole.log(\"Merke Tree\");\r\nconsole.log(\"---------\");\r\nconsole.log(merkleTree.toString());\r\nconsole.log(\"---------\");\r\nconsole.log(\"Merkle Root: \" + merkleTree.getHexRoot());\r\n\r\nconsole.log(\"Proof 1: \" + merkleTree.getHexProof(leafNodes[0]));\r\nconsole.log(\"Proof 2: \" + merkleTree.getHexProof(leafNodes[1]));\r\n```\r\n\r\n1. 首先，我们必须对地址和参数进行编码， [Web3.js](https://github.com/web3/web3.js)可以帮助我们解决这个问题。\r\n2. 然后我们可以使用[keccak256](https://github.com/miguelmota/keccak256)来计算每个余额的地址和金额的哈希值。\r\n3. 上一步的结果是我们的叶子节点，使用merkletreejs ，叶子作为输入， 创建一个新的Merkle树。\r\n4. 我们可以使用`merkleTree.toString()`打印完整的树。\r\n5. 或者我们可以打印单个证明或根哈希值。\r\n\r\n```bash\r\n---------\r\nMerke Tree\r\n---------\r\n└─ 399f97e5a31d2[...]c9f3379ff72\r\n   ├─ dd3f64a1b692[...]38dfdd8578\r\n   └─ 15e70077678[...]e7944f27e36\r\n\r\n---------\r\nMerkle Root: 0x399f97e5[...]f37d0379ff72\r\nProof 1: 0x15e7001d277[...]79440b8f27e36\r\nProof 2: 0xdd3f64a1877[...]38df4b9dd8578\r\n```\r\n\r\n现在，原始根将被存储在合约中。所以你可以看到，像这样做一个空投是相当便宜的，只需部署一个小合约，并存储根的哈希值。\r\n\r\n而且用户可以在链外单独创建他们的证明，并在他们需要的时候 claim 代币。\r\n\r\n\r\n\r\n#### C. 改进Merkle 空投的Gas成本\r\n\r\n我们可以通过将**已经认领的代币的映射存储为位图**来进一步改进这一机制。我以前解释过[Solidity中的位图](https://soliditydeveloper.com/bitmaps)的概念。这个优化是[来自Uniswap](https://github.com/Uniswap/merkle-distributor/blob/master/contracts/MerkleDistributor.sol)。\r\n\r\n对于我们的空投，可以简单地[将余额数组的索引](https://github.com/Uniswap/merkle-distributor/blob/c3255bfa2b684594ecd562cacd7664b0f18330bf/src/balance-tree.ts#L8-L10)添加到证明本身。然后，在存储申领的状态时，只需在 uint256 => uint256 映射中更新一个位。\r\n\r\n```solidity\r\nmapping(uint256 => uint256) private claimedBitMap;\r\n\r\nfunction isClaimed(uint256 index) public view returns (bool) {\r\n    uint256 claimedWordIndex = index / 256;\r\n    uint256 claimedBitIndex = index % 256;\r\n    uint256 claimedWord = claimedBitMap[claimedWordIndex];\r\n    uint256 mask = (1 << claimedBitIndex);\r\n    return claimedWord & mask == mask;\r\n}\r\n\r\nfunction _setClaimed(uint256 index) private {\r\n    uint256 claimedWordIndex = index / 256;\r\n    uint256 claimedBitIndex = index % 256;\r\n    claimedBitMap[claimedWordIndex] = claimedBitMap[claimedWordIndex] | (1 << claimedBitIndex);\r\n}\r\n\r\nfunction claim(uint256 index, address account, uint256 amount, bytes32[] calldata merkleProof) external {\r\n    require(!isClaimed(index), 'MerkleDistributor: Drop already claimed.');\r\n    [...]\r\n    _setClaimed(index);\r\n    [...]\r\n}\r\n```\r\n\r\n![NFT Meme](https://img.learnblockchain.cn/2023/01/12/nft-meme.jpeg)\r\n\r\n\r\n\r\n### 2. 空投NFT\r\n\r\n与空投ERC20代币的方式类似，我们可以使用Merkle证明来**空投NFT**。一个允许向一个地址空投多个NFT的简单实现如右图所示。\r\n\r\n- 我们首先验证申领，就像空投 ERC20 一样。\r\n- 然后我们为每一个应该被空投的金额铸造一个新的NFT。\r\n\r\n\r\n\r\n这是一个不完整的例子，但想法应该是清楚的。也可以把它和之前的位图技巧结合起来，以节省更多的Gas：\r\n\r\n```solidity\r\nfunction _mint(\r\n    address to, \r\n    uint256 amount, \r\n    bytes32[] calldata merkleProof\r\n) internal virtual {\r\n    require(!minted[to] && _verifyClaim(to, amount, merkleProof));\r\n    minted[to] = true;\r\n\r\n    uint256 newId = currentId;\r\n    balanceOf[to] += amount;\r\n\r\n    for (uint256 i; i < amount; i++) {\r\n        _ownerships[newId] = to;\r\n        newId++;\r\n    }\r\n\r\n    currentId = newId;\r\n}\r\n\r\nfunction _verifyClaim(\r\n    address who,\r\n    uint256 amount,\r\n    bytes32[] memory merkleProof\r\n) internal view returns (bool) {\r\n    bytes32 node = keccak256(\r\n        abi.encodePacked(account, amount)\r\n    );\r\n    return MerkleProof.verify(merkleProof, MERKLE_ROOT, node);\r\n}\r\n```\r\n\r\n\r\n\r\n### 4. 在合约内创建证明\r\n\r\n我不确定直接在合约内创建证明的使用场景是什么，但这当然是可能的。你可以使用[murky](https://github.com/dmfxyz/murky)来实现这个。\r\n\r\n创建一个新的Merkle合约，你对它调用`getProof` 就可以了!\r\n\r\n现在，这会是一个怎样的使用场景呢？我不确定，请在评论中告诉我。\r\n\r\n```solidity\r\n// Initialize\r\nMerkle m = new Merkle();\r\n// Toy Data\r\nbytes32[] memory data = new bytes32[](4);\r\ndata[0] = bytes32(\"0x0\");\r\ndata[1] = bytes32(\"0x1\");\r\ndata[2] = bytes32(\"0x2\");\r\ndata[3] = bytes32(\"0x3\");\r\n// Get Root, Proof, and Verify\r\nbytes32 root = m.getRoot(data);\r\nbytes32[] memory proof = m.getProof(data, 2); \r\n```\r\n\r\n\r\n\r\n### 5. 证明以太坊智能合约状态\r\n\r\n一个更高级和非常强大的使用场景是证明智能合约的状态! 有了这个，我们基本上可以向智能合约证明，任何智能合约在过去有一个特定的状态。这是非常强大的东西。\r\n\r\n\r\n然而，它只对**过去的256个块**起作用，原因是EVM只能访问最后256个块的块根哈希值。而这个根哈希值将被需要用来验证证明。所以这允许证明大约**过去一小时**的状态。\r\n\r\n要验证这样的证明就有点复杂了，需要了解：\r\n\r\n- [Merkle-Patricia-Tries](https://ethereum.org/en/developers/docs/data-structures-and-encoding/patricia-merkle-trie/)：以太坊的状态树不只是一个普通的Merkle树，而是使用Merkle-Patricia-Tries。它允许在更新后快速计算新的树根，而无需重新计算整个树。主要的想法是，存储一个值的键被编码为从树上取下的 \"路径\"。\r\n- [RLP-Encoding](https://ethereum.org/en/developers/docs/data-structures-and-encoding/rlp/)：递归长度前缀(RLP)序列化是一种空间效率高的格式，用于编码以太坊中的数据。你不需要了解它的所有细节。因为幸运的是有一个[Solidity RLP库](https://github.com/hamdiallam/Solidity-RLP)你可以使用。\r\n\r\nMerkle证明在Merkle-Patricia-Trie中的工作方式不同，但你可以在[这里](https://github.com/lidofinance/curve-merkle-oracle/blob/main/contracts/MerklePatriciaProofVerifier.sol)找到一个完整的Solidity例子。\r\n\r\n证明智能合约的状态可以分解为证明单个智能合约的存储槽。结合RLP编码，下方代码。你可以在[Solidity 文档](https://learnblockchain.cn/docs/solidity/internals/layout_in_storage.html)中阅读关于存储槽的概念。\r\n\r\n```solidity\r\nfunction extractSlotValueFromProof(\r\n    bytes32 _slotHash,\r\n    bytes32 _storageRootHash,\r\n    RLPReader.RLPItem[] memory _proof\r\n)\r\n    internal pure returns (SlotValue memory)\r\n{\r\n    bytes memory valueRlpBytes = MerklePatriciaProofVerifier.extractProofValue(\r\n        _storageRootHash,\r\n        abi.encodePacked(_slotHash),\r\n        _proof\r\n    );\r\n\r\n    SlotValue memory value;\r\n\r\n    if (valueRlpBytes.length != 0) {\r\n        value.exists = true;\r\n        value.value = valueRlpBytes.toRlpItem().toUint();\r\n    }\r\n\r\n    return value;\r\n}\r\n```\r\n\r\n而自[EIP-1186](https://eips.ethereum.org/EIPS/eip-1186)以来，有一个RPC方法叫做`eth_getProof`，它有助于创建这样一个证明。\r\n\r\n你可以在 [这里](https://github.com/lidofinance/curve-merkle-oracle/blob/main/contracts/StateProofVerifier.sol)找到完整的 Solidity 示例。\r\n\r\n\r\n\r\n\r\n\r\n### 6. 乐观Rollup\r\n\r\n乐观 Rollup（Optimistic Rollup）是建立在前面提到的状态证明之上的。我们已经[在之前详细解释过](https://soliditydeveloper.com/optimism)，但这里的主要思想是：\r\n\r\n- 将智能合约的状态表示为Merkle树\r\n\r\n- 只在 乐观Rollup 链（Layer2）上运行所有交易\r\n\r\n- 持续（乐观地）更新以太坊第1层的状态根部\r\n\r\n- 乐观Rollup 的安全性低，但通过以太坊上的状态根，则可以实现欺诈证明\r\n  - 当中继者提交恶意的状态根并被质疑时，他们会失去他们的抵押（bond）。\r\n\r\n  - 欺诈证明相当昂贵，所以它们实际上并不意味着要经常做。\r\n\r\n  - 运行有争议的整个交易，并提交任何需要的状态作为**状态Merkle证明**。\r\n\r\n\r\n \r\n\r\n这就是扩容的来源，你只在第一层运行有争议的交易，并提交欺诈证明，这就带来了收益。不过运行一个欺诈证明的交易实际上比直接在第1层运行更昂贵。\r\n\r\n因此，扩展的优势完全来自于你99.9%的交易不会在第1层运行这一事实。\r\n\r\n![光明的未来备忘录](https://img.learnblockchain.cn/2023/01/12/bright-future-meme.jpg)\r\n\r\n\r\n\r\n## 未来 = Verkle Trees?\r\n\r\nMerkle Trees的一个改进可能是Verkle Trees。它们是非常新的，还没有在以太坊中使用。它们背后的主要想法是极大地减少证明的大小。回顾一下，Merkle证明包括从根到叶每一级的所有兄弟节点。这可能是一个很大的数据，特别是对于宽的树。\r\n\r\nVerkle树不要求你在证明中提供兄弟姐妹，而是利用**多项式承诺**。它们将允许你证明一些数据zi包含在一个列表[z0, z1, z2...]中。这里的列表当然是同一层次中所有兄弟姐妹的哈希值，我们所关心的是当前的哈希值确实是其中的一部分。将其与允许[通过随机评估的多重验证](https://dankradfeist.de/ethereum/2021/06/18/pcs-multiproofs.html)的技术相结合，会得到更高效的Verkle Trees。\r\n\r\n阅读Vitalik [关于Verkle Trees的文章](https://vitalik.ca/general/2021/06/18/verkle.html)了解更多细节。\r\n\r\n以太坊有计划在第三个升级阶段将Merkle-Patricia-Tries升级到Verkle Trees，称为`The Verge`。\r\n\r\n1. The Merge是权益证明。\r\n2. The Surge是[ 分片](https://vitalik.ca/general/2021/04/07/sharding.html)。\r\n3. **The Verge**是[Verkle trees](https://vitalik.ca/general/2021/06/18/verkle.html)。\r\n4. The Purge是指像状态过期和删除旧的历史。\r\n5. The Splurge是所有其他有趣的东西。\r\n\r\n![结束的备忘录](https://img.learnblockchain.cn/2023/01/12/the-end.meme.jpg)"},"author":{"user":"https://learnblockchain.cn/people/412","address":null},"history":"QmPWDu58x5LgUnEKrmShTecVGwZvW8xHQZfQQP8E1aqjgj","timestamp":1673830492,"version":1}