如何在 Solidity 中实现 Merkle 树

Merkle 树是一种二叉树，可以高效、安全地验证大型数据结构的内容。这棵树的概念是由美国密码学家拉尔夫·默克尔（Ralph Merkle）于 1982 年提出并申请专利。

对于任何数量的输入数据，散列的长度保持不变。叶顶点包含来自数据块的哈希值，而内部顶点包含来自两个子顶点中的值相加的哈希值。反过来，根顶点包含整个数据集的哈希。

理论

最初，存在一组彼此不以任何方式相关的数据。对于每个数据块（在交易区块链的上下文中），我们需要计算该块的哈希值。数据块的数量应该是2^N ，因为在构建树时，先前的块在每次迭代时都会成对散列。然后将一对哈希值组合在一起，并根据它们创建一个新的哈希值。只要每个级别都有东西要分组，散列就会继续，当只剩下一对可以从中获得根散列（默克尔根）时，散列就会停止。

H(1-2) = keccak256(H(1) + H(2))

H(3-4) = keccak256(H(3) + H(4))

H(5-6) = keccak256(H(5) + H(6))

H(7-8) = keccak256(H(7) + H(8))

H(1-2-3-4) = keccak256(H(1-2) + H(3-4))

H(5-6-7-8) = keccak256(H(5-6) + H(7-8))

H(1-2-3-4-5-6-7-8) = keccak256(H(1-2-3-4) + H(5-6-7-8))

一旦我们有了根，我们就可以验证数据。如果根哈希与原始哈希匹配，则一切正常，数据有效。还可以有效地检查树结构中是否存在某些数据。

假设我们要检查H2哈希值是否存在于树中。证明将是一组数据： H1 、 H3-4 、 H5-6-7-8 。借助这些哈希值，我们可以重建根哈希值：

H(1-2-3-4-5-6-7-8) = keccak256(keccak256(keccak256(H(1) + H(2)) + H(3-4)) + H(5-6-7-8))

然后我们将生成的哈希值与原始哈希值进行比较。如果它们匹配，则意味着哈希H2存在于树中。

实践

现在让我们看看如何在 Solidity 中实现 Merkle 树和数据验证。

为简单起见，我们将把交易数组以及哈希数组直接写入区块链。由于我们将使用内置的keccak256函数，该函数返回 32 字节的哈希值，因此哈希数组的数据类型将为bytes32 。该数组还将具有动态长度。一般来说，哈希数组的长度不会与交易数组的长度相同，因为它将保存生成的哈希。我们可以提前计算长度，但为了代码简化，我们不会。如果您愿意，您可以将每个数组public并读取交易的哈希值。

我们将在构造函数中生成hashes 。第一步是计算循环中包含transactions区块的哈希值。然后，在树的每一层，散列的数量减少 2 倍。由于我们将散列存储在散列数组中，因此索引偏移量必须单独存储。内循环中的迭代器增加 2，因为我们在计算和添加哈希值时将采用几个元素。这次在abi.encodePacked中，我们将添加 2 个哈希值，每个哈希值将正确设置索引：对于左侧元素 – 当前移位偏移的值 + 当前树级别的索引，对于右侧元素 – 相同+ 1。

因此，我们已经构建了树，但兴趣在于验证数据。为此，我们编写一个validateTransaction函数，该函数接受事务及其索引。不幸的是，Solidity 没有数组的find方法，因此只传递交易索引会更容易。

首先，我们计算交易的哈希值并创建一个证明数组。我们根据交易数组的长度找到证明的数量，并设置proofsIndexes的长度。之后，在树的每一层，我们根据索引找到必要的元素，采用右侧或左侧的元素，同时记住hashes中的偏移量。然后我们遍历证明索引数组，检查索引的奇偶性，并根据元素在对中的左侧还是右侧计算哈希值。最后，我们将结果哈希与根哈希进行比较并返回结果。

应用

默克尔树在区块链中有多种应用。

• 交易存储：例如，在比特币中，交易块仅存储其交易的merkle_root。这减少了块的大小和网络上的负载。积累一定数量的交易后，可以删除旧交易以节省空间，但块本身保持不变，因为它们只存储树的根。
• 挖矿：比特币区块由两部分组成——区块头和交易列表。为了避免每次都重新计算交易哈希值，它们被排列在 Merkle 树中，之后对块头而不是整个块进行哈希处理，并获取随机数。当区块发送到其他节点时，会计算交易列表的根，如果与标头中的根不匹配，则该区块被拒绝。
• 验证：验证的本质是审计，而无需下载整个区块链。该过程大大简化，并且还允许在不泄露数据信息的情况下确认数据的存在，这对于验证敏感信息非常有用。

概括

如果没有 Merkle 树，区块链就会变得太麻烦，而 Merkle 证明可以经济有效地验证数据的真实性。

默克尔树在区块链（例如比特币、以太坊）中被积极使用，以有效地存储交易，但这并不是唯一的应用。例如，在FTX交易所崩溃后，许多交易所实施了利用Merkle树的储备证明机制。