2023 年 4 月 6 日

了解默克尔树

Merkle 树方法的优点和缺点。

在本文中，我将探索默克尔树。

介绍

默克尔树在比特币区块链中找到了最流行的用例。它们是树状数据结构，其中每个节点都是其子节点的**加密哈希。**Merkle 根位于树的顶部，代表整个数据集。

Merkle 树是一种抗碰撞哈希函数，用𝖬𝖧𝖳表示，它接受 n 个输入 (x1,x2,……,xn) 并输出 Merkle 根哈希 h=𝖬𝖧𝖳(x1,x2,……,xn)。

Merkle 树用于存储和验证交易。交易首先被单独散列，然后成对分组，然后再次散列以创建新节点。重复这一过程，直到只剩下一个节点，即 Merkle 根。

验证者具有根节点哈希 H，并且可以给它一个 xi 以及相关的 Merkle 证明，证明 xi 是用于计算 h 的第 i 个输入。

创建默克尔树

让我们首先以输入数组 A = (x1, x2, x3, x4, x5, x6, x7, x8) 为例。它有 8 个元素。如果我们必须从中创建默克尔树，则过程如下。

• 获取输入对并将其传递给抗冲突的加密哈希函数。

• 获取其输出并递归，直到达到一个值。

• 该值成为根节点。

如果哈希函数 H 在计算上难以处理（在算法上不可能在这一生中找到打破碰撞抵抗的解决方案！），则该哈希函数 H 是抗碰撞的，对手可以使用相同的哈希找到两个不同的输入 x 和 x′（即， H(x)=H(x′))。

默克尔树验证

从数学上来说，默克尔哈希树可以表示如下：

Merkle root = MHT(x1, x2, … , x8)
= h(
h(
h( h(x1), h(x2) ), h( h(x3), h(x4) ) ),
h(
h( h(x5), h(x6) ), h( h(x7), h(x8) )
)
)

这再次向我们展示了默克尔树的递归性。

现在，假设给定一个输入 x*，并询问它是否属于用于创建 Merkle 树的数组。

我们可以使用 Merkle 哈希树的一部分并填充下图中的空白来获得 Merkle 根节点。现在，如果 Merkle 根节点与原始 Merkle 根节点匹配，那么我们可以绝对肯定地说 x* 属于数组中的第 5 个位置。

默克尔树的优点

使用 Merkle 树对于区块链来说有几个优点。首先，它允许有效的交易验证。节点可以验证代表整个数据集的 Merkle 根，而不是单独验证每个交易。

其次，它允许紧凑地存储交易。Merkle 树只存储 Merkle 根，而不是将所有交易存储在一个区块中，该区块要小得多。

最后，默克尔树允许节点的快速同步。当新节点加入网络时，它仅请求 Merkle 根而不是整个数据集，从而实现更快、更高效的同步。

默克尔树的缺点

虽然默克尔树为区块链技术提供了多种好处，但仍有一些潜在问题需要考虑。

一个问题是碰撞攻击的可能性，即两组不同的数据产生相同的 Merkle 根。这可能会导致恶意行为者在不被发现的情况下篡改数据。

另一个问题是潜在的 51% 攻击，其中单个实体或团体控制了网络的大部分计算能力。在这种情况下，攻击者可能会修改 Merkle 树中的交易及其相应的哈希值，然后网络可以将其视为有效。

值得注意的是，虽然这些问题存在，但它们并不一定会使 Merkle 树失效。正确的实施和安全措施可以帮助减轻这些风险并确保区块链的完整性。

结论

除了区块链之外，默克尔树还可以用于检测从恶意渠道下载的任何文件的恶意或意外修改。

虽然默克尔树是区块链技术中广泛使用且有效的存储和验证数据的方法，但也有一些替代方法。

其中一种方法是使用稀疏 Merkle 树，它与常规 Merkle 树类似，但仅存储树的非空叶子。在某些情况下，这可以减少存储需求并提高效率。

具有 n 个叶子的 Merkle 树具有 O(log2 n) 大小的证明。在大型树中，发送证明可以主导带宽消耗。向量承诺 (VC) 是 Merkle 树的潜在替代方案，具有恒定大小的证明。

Space and Time作为一个去中心化的数据仓库，也受到了Merkle树等各种方法的启发。但是Proof of SQL有自己的实现，用来解决去中心化的问题。我们的证明团队一直致力于创建一种可持续的方法，该方法改进了 Merkle 树并使用 zk-SNARK 的各种方法。我们很快就会写更多相关内容。

最终，区块链系统数据结构的选择将取决于网络的具体需求和要求。对于许多区块链应用程序来说，默克尔树仍然是一个流行且有效的选择，但在某些情况下其他选项可能更合适。