paint-brush
如何在 Solidity 中实现 Merkle 树经过@iamshvetsov
171,540 讀數
171,540 讀數

如何在 Solidity 中实现 Merkle 树

经过 Daniel Shvetsov5m2023/10/23
Read on Terminal Reader

太長; 讀書

如果没有 Merkle 树,区块链就会变得太麻烦,而 Merkle 证明可以经济有效地验证数据的真实性。 默克尔树在区块链(例如比特币、以太坊)中被积极使用,以有效地存储交易,但这并不是唯一的应用。例如,在FTX交易所崩溃后,许多交易所实施了利用Merkle树的储备证明机制。
featured image - 如何在 Solidity 中实现 Merkle 树
Daniel Shvetsov HackerNoon profile picture


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))


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


TX2 的样张


假设我们要检查H2哈希值是否存在于树中。证明将是一组数据: H1H3-4H5-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树的储备证明机制。