Solidity 合约分析：2. Merkle Proof
介绍
你好，我是 Pluveto。我发现多数 Solidity 的教程都是从语法开始讲起，但是我觉得这样不够直观，而且很消耗耐心。这是一个系列文章，我会在这个系列里分析一些简单的 Solidity 合约。在例子中学习。
希望你能学到东西，让我们开始吧！
代码
来自：Merkle Tree | Solidity by Example | 0.8.20
1// SPDX-License-Identifier: MIT
2pragma solidity ^0.8.20;
3
4contract MerkleProof {
5 function verify(
6 bytes32[] memory proof,
7 bytes32 root,
8 bytes32 leaf,
9 uint index
10 ) public pure returns (bool) {
11 bytes32 hash = leaf;
12
13 for (uint i = 0; i < proof.length; i++) {
14 bytes32 proofElement = proof[i];
15
16 if (index % 2 == 0) {
17 hash = keccak256(abi.encodePacked(hash, proofElement));
18 } else {
19 hash = keccak256(abi.encodePacked(proofElement, hash));
20 }
21
22 index = index / 2;
23 }
24
25 return hash == root;
26 }
27}
28
29contract TestMerkleProof is MerkleProof {
30 bytes32[] public hashes;
31
32 constructor() {
33 string[4] memory transactions = [
34 "alice -> bob",
35 "bob -> dave",
36 "carol -> alice",
37 "dave -> bob"
38 ];
39
40 for (uint i = 0; i < transactions.length; i++) {
41 hashes.push(keccak256(abi.encodePacked(transactions[i])));
42 }
43
44 uint n = transactions.length;
45 uint offset = 0;
46
47 while (n > 0) {
48 for (uint i = 0; i < n - 1; i += 2) {
49 hashes.push(
50 keccak256(
51 abi.encodePacked(hashes[offset + i], hashes[offset + i + 1])
52 )
53 );
54 }
55 offset += n;
56 n = n / 2;
57 }
58 }
59
60 function getRoot() public view returns (bytes32) {
61 return hashes[hashes.length - 1];
62 }
63
64 /* verify
65 3rd leaf
66 0xdca3326ad7e8121bf9cf9c12333e6b2271abe823ec9edfe42f813b1e768fa57b
67
68 root
69 0xcc086fcc038189b4641db2cc4f1de3bb132aefbd65d510d817591550937818c7
70
71 index
72 2
73
74 proof
75 0x8da9e1c820f9dbd1589fd6585872bc1063588625729e7ab0797cfc63a00bd950
76 0x995788ffc103b987ad50f5e5707fd094419eb12d9552cc423bd0cd86a3861433
77 */
78}
解释
我们这次看到了两个合约，一个是 MerkleProof，另一个是 TestMerkleProof。TestMerkleProof 继承了 MerkleProof。
当一个合约使用 is 继承另一个合约时，具有以下特征：
-
子合约获得并且能调用父合约中的所有公开函数、变量、事件
-
子合约可以对父合约中的函数和变量进行重写
-
子合约可以添加新的状态变量、函数等
-
部署子合约实际上就是部署一个继承了父合约定义和代码的合约
这里的 MerkleProof 合约实现了一个简单的 Merkle 树验证逻辑：
- verify 函数可以验证一个叶子节点是否在 Merkle 树的根节点下面。
-
参数 proof 是每个节点的兄弟节点哈希值组成的数组。
-
leaf 是需要验证的叶子节点哈希。
-
index 是叶子节点在整个叶子节点列表中的索引。
-
根据索引计算遍历顺序，利用兄弟节点哈希值进行哈希，最终得到的 hash 与根节点 root 进行比较。
-
具体算法：
-
初始化 hash 为 leaf
-
遍历 proof 数组中的每个兄弟节点哈希值
-
根据 index 奇偶决定哈希顺序（左儿子还是右儿子）
-
每次哈希后 index 右移一位
-
遍历结束后 hash 是否等于根节点 root, 就是验证结果
您可以参考鄙人的文章 Merkle Tree 及其算法的设计与实现 我的文章里使用异或来避开哈希顺序的问题。
所以这个合约实现了一个简单的 Merkle 树验证逻辑。通过提供叶子节点、索引、证明和根节点，可以验证这个叶子节点是否在这个 Merkle 树下。
其中用到了
-
keccak256：Solidity 的哈希函数，用于计算哈希值。
-
abi.encodePacked：Solidity 的编码函数，用于将多个值编码为一个值。
abi.encodePacked 是 Solidity 中用于打包参数到二进制编码格式的内置函数之一。它的工作原理如下:
-
abi.encodePacked 接收一个或多个参数,可以是不同类型的。
-
它会将这些参数按照类型从低地址到高地址打包成紧密排列的二进制编码格式。
-
与 abi.encode 不同,它不会在开头添加类型信息长度字。
-
这使得打包结果可以再紧凑,但也意味着解码时需要知道参数的数量和类型。
-
参数会按照内存中变量的顺序从左到右进行打包。
-
数值类型如 uint、int 会保留对齐,字符串会保留长度字。
-
结构体会将其成员依次打包。
举个例子:
1abi.encodePacked(uint256(1), bool(true), bytes("abc"))
会得到这个字节序列:
101 00 00 00 00 00 00 00 01 61 62 63
其中:
-
第一个uint256(1)为 01 00 00 00 00 00 00 00
-
第二个bool(true) 为 01
-
第三个bytes3 为 61 62 63
所以abi.encodePacked可以实现参数的最紧凑打包,但实际操作需要了解其内部机制。它通常用于需要极为高效的合约中,如 Merkle树实现。
接下来的 TestMerkleProof 合约用于测试 MerkleProof 合约的功能。
-
首先初始化了四个字符串，每个字符串代表一个交易。
-
然后计算了每个交易的哈希值，放入了一个数组中。
-
接下来是一个循环，用于计算 Merkle 树的根节点。
-
每次循环都会计算出一个新的哈希值，放入数组中。
-
每次循环都会将交易数量除以 2，直到交易数量为 0。
-
每次循环都会将偏移量 offset 加上交易数量，直到交易数量为 0。
-
这样就能够计算出 Merkle 树的根节点。
-
最后生成的 hashes 数组类似这样：
| offset | 交易数量 | 哈希值 |
|---|---|---|
| 0 | 1 | hash(transactions[0]) |
| 1 | 1 | hash(transactions[1]) |
| 2 | 1 | hash(transactions[2]) |
| 3 | 1 | hash(transactions[3]) |
| 4 | 2 | hash(hash(transactions[0]) + hash(transactions[1])) |
| 6 | 2 | hash(hash(transactions[2]) + hash(transactions[3])) |
| 7 | 4 | hash(hash(hash(transactions[0]) + hash(transactions[1])) + hash(hash(transactions[2]) + hash(transactions[3]))) |