默克尔帕特里夏树

默克尔·帕特里夏·特里树（Merkle Patricia Trie，MPT）是以太坊区块链中使用的一种关键数据结构，它结合了默克尔树和帕特里夏树的特点。其主要目的是为网络中大量的交易和收据提供一个可靠的数据存储系统。

与比特币不同，默克尔·帕特里夏·特里树是专为以太坊设计的，满足了该网络的需求。凭借其高效的数据管理功能，它非常适合以太坊的去中心化和以智能合约为中心的环境，是该平台独特且至关重要的组成部分。

什么是默克尔·帕特里夏·特里树？

对于“以太坊的关键数据结构是什么？”这个问题，只有一个答案：默克尔·帕特里夏·特里树。以太坊使用了一种结合了帕特里夏树和默克尔树优势的数据结构。默克尔·帕特里夏·特里树在以太坊区块头中用于表示特定数据。

我们已经介绍过帕特里夏树和默克尔树。简而言之，默克尔树利用哈希表示来加速搜索过程并节省存储空间，因此在区块链网络管理中起着至关重要的作用。相比之下，帕特里夏树这种数据结构存储（键，值）对，类似于一棵树。帕特里夏树的压缩方法减少了区块链中所需的存储量。

与默克尔树类似，以太坊树中的每个节点都由其哈希值标识。根哈希充当其所代表的整个数据集的数字签名。任何键值的更改也会影响默克尔根。以太坊密钥的十六进制表示中有 16 个可用字符，分别是 0 到 9 和 A 到 F。

默克尔·帕特里夏·特里树有四种不同类型的节点：

• 空节点（Null）：用一个空字符串表示一个不存在的节点。
• 分支节点（Branch）：一个最多连接 16 个不同子节点的节点，对应 16 个十六进制字符。它也有一个值字段。
• 叶子节点（Leaf）：一个“终端节点”，包含一个值和密钥的最后部分。
• 扩展节点（Extension）：一个“快捷方式”节点，根据共享的前缀存储密钥的一部分，并链接到下一个节点。

为什么以太坊使用默克尔·帕特里夏·特里树？

通常，数据分为两类：

1. 持久
   
   • 交易发生后，记录被永久封存。
   • 这意味着一旦在区块的交易树中找到一笔交易，你可以重复地沿着相同的路径得到相同的结果。
2. 临时
   
   • 而在以太坊中，账户状态是不断变化的！（例如，用户与合约交互、收到一些以太币等）
   • nonce、余额、storageRoot 和 codeHash

将临时数据（如以太坊账户、余额、nonce等）和永久数据（如已挖出的交易）分开存储是合理的。再次强调，默克尔树非常适合持久性数据。而以太坊有大量的临时数据，这使得 MPT 非常适合它。

与交易历史不同，以太坊的账户状态需要定期更新。不仅账户余额和 nonce 经常被修改，新的账户和密钥也经常被添加和从存储中移除。

为什么使用默克尔·帕特里夏·特里树？

我们已经展示了默克尔·帕特里夏·特里树是如何结合默克尔树和帕特里夏树的优点的。现在，让我们来看看默克尔·帕特里夏·特里树提供的一些优势。

当发生账户余额、nonce 等更新时，状态树能够快速重新计算根哈希。所有数据都决定了根值。它与更新发布的顺序无关。因此，即使更新以不同的顺序进行，最终的树也不会改变。

借助哈希，可以轻松检测数据修改。任何对等方试图修改数据的行为都会导致根哈希的改变，从而向其他对等方发出更改警报。

• 可以轻松查询，而无需重新计算整个树。
• 验证一笔交易是否属于一个区块？请求交易树。
• 想验证一个账户的合法性？请求状态树。
• 想知道你的账户余额？请求收据树。

轻量级客户端（处理和存储能力较低的设备），如移动应用程序，可以使用此功能进行数据验证。

树被存储在数据库中。因此，我们无需在区块链上存储所有数据，就能证明大部分数据是准确的。此外，它还降低了区块链的存储开销。

默克尔树 vs 默克尔-帕特里夏树

既然我们已经了解了默克尔树和帕特里夏树，让我们来看看它们的一些关键区别。

• 默克尔·帕特里夏·特里树的根独立于数据的时间顺序。然而，由于我们将相邻节点配对并获取哈希值，默克尔树的根依赖于数据的顺序。
• 由于基于前缀的压缩方法，默克尔·帕特里夏·特里树的大小比典型的默克尔树要小。
• 默克尔·帕特里夏·特里树比默克尔树更快，但实现起来更复杂。