什么是稀疏梅克尔树？

如果你最近关注以太坊研究社区，可能听说过稀疏 Merkle 树。它们听起来很复杂，但其实很简单。本文将确切解释稀疏 Merkle 树是什么、为什么它们很酷，以及它们目前的用途。

Merkle 树

首先，让我们快速回顾一下 Merkle 树。Merkle 树提供了一种方式来 加密承诺 一组数据。我们首先对数据集中每个数据进行 哈希 处理，然后继续哈希直到到达根节点。

结果看起来是这样的：

证明包含性

这棵树的根就是一个哈希——它并不告诉我们树的内容。我们可以使用一种叫做“Merkle 证明”的方法来显示某些内容实际上是这棵树的一部分。例如，让我们证明 A 是上面树的一部分。我们只需提供 A 的每个兄弟节点，重新计算树，并确保一切匹配即可。

我已经将兄弟节点用蓝色标出。有了 A、H(B) 和 H(H(C)+H(D))，我们就可以重新计算原始根哈希。这是一种高效的方式来证明 A 是这棵树的一部分，而不必提供整个树！

证明不包含性

所以我们可以很容易地证明某物 是 Merkle 树的一部分，但如果我们想证明某物 不是 树的一部分怎么办？不幸的是，标准的 Merkle 树没有提供良好的方法来做到这一点。我们可以揭示整个内容，但这样做在使用 Merkle 树的初衷上就有些悖论。

稀疏 Merkle树

这就是稀疏 Merkle 树派上用场的地方。稀疏 Merkle 树与标准 Merkle 树类似，不同之处在于，它包含的数据是索引的，每个数据点放置在对应于该数据点索引的叶子节点上。

假设我们有一棵有四个叶子的 Merkle 树。我们将用一些字母（A、D）填充这棵树以进行演示。字母 A 是字母表的第一个字母，所以我们应该将其放在第一个叶子节点。同样，我们可以将 D 放在第四个叶子节点。

那么第二和第三个叶子节点会发生什么呢？我们只需将它们留空。更准确地说，我们在放置字母的地方放一个特殊值（如 null）。

这棵树最终看起来是这样的：

证明包含性

就像在标准 Merkle 树中一样，我们可以使用 Merkle 证明来证明 A 是这棵树的一部分。这个证明看起来就像你的标准 Merkle 证明：

同样，我们只需要提供兄弟节点 H(null) 和 H(H(null)+H(D))，并检查是否与根匹配。

证明不包含性

这就是魔法发生的地方。如果我们想证明 C 不是 这棵 Merkle 树的一部分，会发生什么？这很简单！我们知道，如果 C 是树的一部分，它将位于第三个叶子节点。如果 C 不是树的一部分，那么第三个叶子节点一定是 null。

我们只需一个标准的 Merkle 证明来显示第三个叶子是 null！

这看起来就像一个标准的 Merkle 证明，唯一的不同是我们在证明叶子包含的是 null 而不是 C。

稀疏 Merkle 树最棒的地方在于它们实际上代表了键值存储，在 Merkle 树内部！

缺点

稀疏 Merkle 树非常酷，因为它们提供了 高效的不包含证明。然而，这也可能意味着它们会变得非常庞大。26 个字母并不算多，但通常我们讨论的是 2²⁵⁶ 个哈希！这实在是太多的索引，以至于我们无法手动生成一棵树。

幸运的是，有 一些技术 可以高效地生成 Merkle 树。这些技术的关键在于这些巨型稀疏 Merkle 树大多数是……稀疏的。H(null) 是一个常量值，H(H(null)) 也是，等等等等。树的大块可以被缓存！

用例

稀疏 Merkle 树已经在实际中用于一些很酷的区块链应用。

Plasma Cash 利用稀疏 Merkle 树来存储有关存入资产的信息。每个 Plasma Cash 资产都有一个唯一的 ID。每当资产被转移到新用户时，交易会被包含在该资产索引的稀疏 Merkle 树中！包含（或不包含！）的证明用于证明给定的交易历史是有效的。

稀疏 Merkle 树甚至可能会进入以太坊！以太坊研究人员正在 研究稀疏 Merkle 树 作为替代当前用于存储以太坊状态的 Merkle Patricia trie。

一如既往，欢迎反馈/评论/问题。如果你发现任何错别字，或者认为有必要澄清的地方，请告诉我！

• 原文链接： medium.com/@kelvinfichte...
• 登链社区 AI 助手，为大家转译优秀英文文章，如有翻译不通的地方，还请包涵～