在这篇文章中，我们将介绍区块链实现中常见的一种数据结构：Merkle-Patricia树， 学习其索引机制并了解以太坊是如何利用Merkle-Patricia树来实现交易的实时审计。
试想一下，如果我们能捕捉到每家银行和整个金融基础设施中每笔金融交易的当前状态。 这将是我们整个金融基础设施的历史。因此，在任何时间点，我们都会看到整个画面随着时间的推移， 并会看到所有交易的确切时间和参与者。如果我们愿意，我们也可以匿名交易数据。
这将是一个我们可以随时进行审计，并即时记录当前状态的世界，还可以获取每个以前状态的快照。 这样，审计师就能看到一切，并随着时间的推移而前后移动。我描述的是以太坊，它使用Merkle-Patricia树 创建一个完整的世界模型的所有交易。
1、Merkle-Patricia树
使用 Merkle 树，我们创建一个哈希树，根哈希提供树内数据的整体一致性。它的核心优点是，我们 可以通过分析子树轻松检查数据是否在树内。
Merkle-Patricia-Tree 使用密钥（通常定义为字符串）来存储关联数组来增强这一功能。Patricia 是检索以字母数字编码的信息的一种实用算法。
在Merkle-Patricia树中，节点与密钥关联，这被定义为三元数字树。这与 Merkle 树不同，因为每个节点 的实际密钥不存储，但它在树中的位置用于定义密钥。给定节点下方的节点的定义与该节点上的字符串的前缀 相同，然后树根是一个空字符串。
让我们举一个索引五个单词的例子：flower，flows，far，pitching和pitches。我们现在可以画一棵树来 索引这些字符串：
如果用户输入”f”，我们会进入到第二级，然后进入”low”，然后进入第三级。最后，进入’s’，我们移动到 第四级。我们可以看到，数据现在已排序并关联，树中的位置定义了数据元素与之关联的key。
2、Merkle-Patricia树在以太坊中的应用
在以太坊区块链中，我们使用修改后的Merkle-Patricia树（如黄皮书所定义的）来创建包含所有交易的 trie。 通过这种方式，我们可以生成所有交易的完整世界视图。
在我们处理交易 ID 时，每个键都有 X 个16进制字符。然后，trie 中的每个节点都可以有 16 个可能的子节点。 三元树的最大深度为 X。
然后，每个节点可以是一个扩展，一个分支或一片叶子。叶子是终点，将包含交易价值。在图表中，我们看到 根哈希是所有交易的哈希。然后，我们有一个扩展来定义顶层节点，在那里我们可以看到有四个交易，它们由 “a711355”、”a77d337”、”a7f9365”和”a77397”的键定义。交易金额分别为 45.0 ETH、1.00 WEI、1.1 ETH 和 0.12 ETH。
然后，我们可以按照树找到交易。我们从”a7…”的键值开始（根：扩展节点）。然后我们有一个叶节点在 “a7…1355”（其中”1355”是键的结尾部分）。这里的交易值为 45.0 ETH。我们有另一个叶节点与”a7….9365” （其中”9365”是键的末尾部分），交易值为 1.1 ETH。
接下来，我们将扩展至”a7d3”。最后，我们到达最后两个交易与叶节点（”a7d33.。7”和”a7d39.。7”），交易 金额分别为1.00 WEI和0.12 ETH。
下面我们列出了世界排名前2，500位的网站，并利用Radix Trie（又名Patricia）实现：
3、结论
我们金融体系的完整世界模式。不久的将来，我们需要采用这些方法，无论是在每家银行内部还是在我们完整 的金融基础设施内，并创建一个新的系统，在任何时间点完全可审计，并且我们可以看到每一笔交易。这将是 一个更值得信赖的金融世界。我们刚才的挑战是使这个世界对所有人开放和透明，但尊重隐私和同意。
通过零知识验证和同构加密，我们正在达到这个水平，以太坊只是新世界正在创造的一个例子。区块链和DLT 将是人类有史以来最伟大的机器，而我们刚刚开始这段旅程。
忘记加密货币，想想交易，你就有了我们新的数字世界。
原文链接：Instant Auditing? Meet The Merkle-Patricia-Tree
汇智网翻译整理，转载请标明出处