Merkle Patricia Trie 简介

介绍

以太坊依赖于密码学数据结构来高效地存储和验证其状态。其中一种结构是 Merkle Patricia Trie (MPT)，它为以太坊的状态管理提供支持。在更深入地探索这个工具之后，很明显，MPT 是一种复杂的数据结构——远比简单的 Merkle 树复杂。这就是我们觉得创建这篇文章很重要的原因：让 MPT 更容易理解。在这里，我们将解释什么是 MPT，以太坊如何使用它以及它的证明如何工作。在即将发布的文章中，我们将解释如何对 MPT 进行算术化，以便生成证明，表明我们验证了元素是否在树中，或者树是否已成功更新。

在下面的内容中，我们仅假设你对 Merkle 树 和密码学哈希函数有基本的了解。

Merkle 树快速回顾

Merkle 树是一种二叉树，其中：

• 叶子节点 包含数据的哈希值。
• 非叶子节点 包含其子节点连接后的哈希值。
• 根哈希 充当所有叶子节点数据的密码学指纹。换句话说，它是一个短的、固定大小的摘要（哈希值），可以唯一地标识大量数据——就像一个唯一的签名。

Merkle 树用于 数据完整性证明：你可以通过提供 Merkle 路径（从叶子节点到根节点的一系列哈希值）有效地证明一条数据属于树的叶子节点。

什么是 Trie？

Trie（检索树的缩写，也称为前缀树）是一种类似树的数据结构，用于高效地存储和检索键值对，尤其是在键是字符串或序列时。

trie 的每个级别表示键中的一个字符，从根到叶的路径对应于整个键。键之间的共享前缀仅存储一次，这使得 trie 对于具有公共前缀的数据集非常节省空间。

让我们看一个玩具示例，以便更容易理解。假设我们要存储以下键值对：

我们的玩具 trie 看起来像这样：

要查找键 "cake" 的值：

1. 从根开始。
2. 按照与键的字符对应的节点：c -> a -> k -> e。
3. 在最后一个节点 e 检索值 "sweet"。

什么是 Merkle Patricia Trie？

以太坊使用一种专门的 trie 形式，称为 Modified Merkle Patricia Trie (MPT)。该名称结合了三个核心思想：

• Trie: 用于按共享前缀组织键。
• Merkle: 每个节点都被哈希，形成一个 Merkle 结构，可以对整个数据集进行密码学验证。
• Patricia: Practical Algorithm to Retrieve Information Coded in Alphanumeric 的缩写——trie 的一种变体，可压缩节点具有单个子节点的路径（也称为 radix 或 compact trie）。

MPT 在以太坊中如何使用？

以太坊使用多个 MPT，但我们将仅关注其中一个，即 State Trie，并将其用作解释它们如何工作的示例。

在 State Trie 中，每个帐户的状态都存储为一个键值对，其中：

• 键 是帐户地址的 Keccak-256 哈希值。
• 值 是帐户，它是四项数组的 RLP 编码：[nonce, balance, storageRoot, codeHash]。

为了达成共识，当出现一个包含交易集的新区块时，每个以太坊节点都需要执行所有这些交易并验证所有节点的结果状态是否相同。但是，比较每个帐户的计算成本非常高，因此它们使用 MPT 代替。以太坊所有帐户的状态都存储在一个名为 State Trie 的 Merkle trie 中，该 trie 在每次交易执行后都会不断更新。为了达成共识，节点只需比较 StateRoot（State Trie 的根）。如果两个节点具有相同的 StateRoot，则它们的状态匹配。

不可变性：MPT 的巨大优势

以太坊需要能够轻松地恢复到以前的状态：当节点对下一个区块存在分歧时，需要进行区块链分叉。这是可能的，因为 trie 保留了旧状态，而不是直接删除或修改它。trie 是持久的和可版本化的，而不是可变的就地结构。

当状态发生变化时（例如，帐户余额更新），trie 会为已更改的路径创建新节点，而 trie 的其余部分（未更改的部分）会被重用。因此，可以通过它们的根访问以前的 trie 版本。每个区块都在其标头中存储一个状态根，并且该根唯一地标识了当时整个以太坊的状态。因此，如果以太坊需要回滚，它只需使用先前区块的状态根即可。由于旧节点从未被删除，因此 trie 可以有效地重建旧状态。这意味着以太坊只需切换回较早的根哈希即可恢复旧状态。

MPT 结构

让我们解释一下 State Trie 是如何构建的。正如我们上面所说，这个 trie 的键由地址的哈希值组成，表示为十六进制字符串。正如我们在玩具示例中展示的那样，trie 的每个节点将存储十六进制字符串的一个字符，也就是单个 nibble （四位数据）。

MPT 中有三种类型的节点：

1. 分支节点（Branch Node）

   • 它存储一个 17 项数组。
   • 前 16 项表示键前缀可以是的每个十六进制数字之一。如果键前缀是数字 $i$，那么在索引 $i$ 处，你将找到指向继续键路径的下一个节点的指针。
   • 最后一项可以在键在此处结束的情况下分配一个值。

   • 例子：

     [0x, 0x, child_hash, 0x, 0x, other_child_hash, 0x, 0x, 0x, 0x, 0x, 0x, 0x, 0x, 0x, 0x, value]

     在这里，"0x" 表示未使用的槽，即没有子节点的数字。

2. 扩展节点（Extension Node）
   • 它是压缩共享键前缀的优化结果。
   • 它存储一个包含共享键前缀和指向下一个节点的指针的两项数组。
   • 例子：[shared_prefix, child_hash]
3. 叶子节点（Leaf Node）
   • 它存储一个包含剩余键片段及其关联值的两项数组，结束路径。
   • 例子：[key_remaining, value]

这三种类型的节点都存储一个以 RLP 编码的单个数组。指向某个节点的指针始终是存储该 RLP 字符串数据的哈希值。根可以是任何类型，但通常，由于我们有很多数据，因此根是一个分支节点。

节点和奇偶校验标志

当逐个 nibble（或逐个字符）遍历键路径时，我们最终可能会得到一个需要存储奇数个 nibble 的叶子节点或扩展节点。但是由于所有数据都存储在字节中，这会产生一个问题。例如，如果我们想存储 nibble 1，我们将不得不将其保存为 01，但我们将无法判断它来自两个 nibble 01，还是来自单个 nibble 1。为了指示我们是存储偶数个还是奇数个 nibble —— 以及我们正在处理的节点类型（叶子或扩展）——部分路径以以下标志作为前缀。

示例：逐步构建 MPT

理解 MPT 的最佳方法是查看完整的示例。让我们模拟一个真实的 State Trie。假设我们有五个帐户的数据，这些帐户转换为以下键值对：

正如我们前面提到的，键应该是帐户地址的哈希值。由于以太坊使用 Keccak-256，因此键应该是 32 字节长（或 64 个十六进制字符）。但是，对于此示例，我们将使用短得多的键，以便生成的 trie 不会太大且更易于理解。以太坊还使用优化，例如内联小节点，为了清楚起见，我们将在本示例中跳过这些优化。

现在我们准备好构建 MPT：

1. 从一个空的 MPT 开始，并添加第一个键值对：(0x616b6c64, 0x01)。因为它只是一个