如果您最近跟随以太坊研究社区，那么您可能听说过稀疏的树木。它们听起来很复杂，但实际上很简单。本文将准确解释什么是稀疏的树木，为什么它们很酷以及它们当前使用的方法。
树
首先，让我们快速看一下树。树提供了一种加密保证数据集的方法。我们首先哈希数据集中的每个数据，然后继续哈希，直到达到根节点。
结果看起来像这样：
证明包容性
这棵树的根部是哈希 - 它没有告诉我们这棵树是什么。我们可以使用一种称为“证明”的方法来证明实际上是树的一部分。例如，让我们证明A是上面树的一部分。我们只需要提供a的每个兄弟姐妹节点，重新计算树，并确保一切都匹配。
我以蓝色标记了兄弟节点。使用a，h（b）和h（h（c）+h（d）），我们可以重新计算原始的根哈希。这是证明A是这棵树的一部分而无需提供整棵树的有效方法！
证明它不包括性
因此，我们可以轻松地证明某物是树的一部分，但是如果我们想证明某物不是树的一部分怎么办？不幸的是，标准树没有提供这样做的好方法。我们可以揭示整个过程，但是这样做对使用树木的原始意图有些自相矛盾。
稀疏的树
这是稀疏树木派上用场的地方。稀疏树类似于标准树，除了它包含索引数据，并且每个数据点都放在与该数据点索引相对应的叶子节点上。
假设我们有一棵树有四片叶子。我们将用一些字母（a，d）填充这棵树以进行演示。字母A是字母的第一个字母，因此我们应该将其放在第一个叶子节点上。同样，我们可以将D放在第四个叶节点上。
那么第二和第三叶节点会发生什么？我们只需要让他们空白。更确切地说，我们放置了放置字母的特殊价值（例如null）。
这棵树看起来像这样：
证明包容性
就像在标准树中一样，我们可以使用证明A是该树的一部分。此证明看起来像您的标准证明：
同样，我们只需要提供兄弟节点h（null）和h（h（null）+h（d）），然后检查它是否匹配根。
证明它不包括性
这是魔术发生的地方。如果我们想证明C不是这棵树的一部分，会发生什么？这很简单！我们知道，如果C是树的一部分，它将位于第三个叶子节点中。如果C不是树的一部分，则第三个叶节点必须为null。
我们只需要标准证明即可证明第三叶是无效的！
这看起来像是标准证明，唯一的区别是我们证明了叶子包含null而不是C。
关于稀疏树木的最好的事情是，它们实际上代表了树内的钥匙值存储！
缺点
稀疏的树非常酷，因为它们提供了有效的不包括的证据。但是，这也可能意味着它们会变得很大。 26个字母并不多，但是我们通常会讨论2²⁵⁶哈希！这是很多索引，我们无法手动生成树。
幸运的是，有些技术可以有效地跨越树木。这些技术的关键是，这些巨大的稀疏树木中的大多数都是……稀疏。 h（null）是一个恒定值，h（h（null））也是如此。可以缓存树的大块！
用例
稀疏的树木已经在实践中用于一些凉爽的区块链应用。
现金使用稀疏的树木存储有关存入资产的信息。每个现金资产都有一个独特的ID。每当将资产转移到新用户时，交易就包含在资产索引的稀疏树中！包括（或不包括！）的证明证明给定的交易历史记录有效。
稀疏的树木甚至可能进入以太坊！以太坊研究人员正在研究稀疏树木，以替代目前用于存储以太坊状态的Trie。
与往常一样，欢迎反馈/评论/问题。如果您找到任何错别字，或者认为有必要澄清，请告诉我！
