以太坊作为领先的智能合约平台，其实现依赖于多种精心设计的数据结构和编码方案。深入理解这些底层机制对于区块链开发者和研究者至关重要。本文将系统解析以太坊的核心数据结构，涵盖基础概念、编码方案、区块交易结构以及具体实现细节。
基础数据结构
Patricia Trie：高效搜索的树结构
树结构是高效搜索的标准方法之一，其中最常见的是二叉搜索树。二叉搜索树可以构成前缀树（Prefix Tree），具有相同前缀的键会共享从根节点到叶节点的路径。
在前缀树中搜索键时，需要依次按顺序逐个检查字符，确认是否存在与当前字符匹配的子节点。如果存在，则向下遍历到该子节点，然后继续匹配下一个字符。
搜索树的主要缺点体现在遍历效率上。当处理具有长公共前缀的键时，必须遍历多个子节点，特定情况下树会退化为链表，使查找时间复杂度从 O(log n) 增加到 O(n)。
为解决这一问题，Fredkin 提出了 Trie Memory 结构。他将数据表示为表格形式，其中表的列代表节点，行代表分支。行数取决于分支数，列数相当于将数据表示为树时的深度。
Patricia Trie 对原始 Trie 结构进行了压缩优化，每个节点不仅存储路径信息，还记录了可以在匹配键时跳过的位数。在原始 Trie 中，键的公共前缀部分会通过多个节点表示，而在 Patricia Trie 中，这些公共路径会被压缩成一个单一节点，从而减少了不必要的节点存储。
Merkle Tree：密码学验证结构
Ralph Merkle 提出的 Merkle Tree 是一种用于快速验证数据集一致性的密码学数据结构。其核心特征是每个节点包含其子节点的哈希值，叶子节点则链接到编码数据集的实际值。
Merkle Tree 的核心价值在于允许各方在不交换完整数据集的情况下验证数据一致性。它为数据集提供了唯一的哈希标识，有效防止了恶意或无意的数据修改。参与者可以通过比对哈希值来验证数据的完整性和一致性。
在区块链这样的分布式无信任环境中，Merkle Tree 提供了理想的解决方案。它不仅提供了基于哈希的有效性证明，而且哈希值的小体积特性使其非常适合在互联网环境中传输。
Merkle Patricia Trie：融合与创新
Merkle Patricia Trie (MPT) 是融合并扩展了 Patricia Trie 的高效存储和 Merkle Tree 的防篡改验证特性的数据结构。该结构巧妙地将主键的公共路径组合在单一节点中，同时以 Merkle 证明的方式对每个节点进行哈希处理。
MPT 定义了三种类型的节点：
- 分支节点：包含17项，用于处理键分叉，前16项对应十六进制字符0-F，第17项用于存储值
- 扩展节点：包含2项，实现了路径压缩功能，当多个键共享公共前缀时，这部分前缀被存储在扩展节点中
- 叶节点：包含2项，标志着树中路径的终点，采用压缩方法存储键的公共后缀
👉 深入了解Merkle Patricia Trie的实现细节
数据结构编码
十六进制前缀编码（HP）
在 Merkle-Patricia Trie 中，存储的数据被编码为字节序列。叶节点和扩展节点使用 HP 编码函数进行处理，核心目的是将任意数量的半字节编码为二进制流。
HP编码的特点包括添加前缀半字节和长度调整。前缀半字节的倒数第二位用于区分叶节点和扩展节点，最低位表示编码数据长度的奇偶性。
递归长度前缀编码（RLP）
RLP 函数的核心功能是将输入的一组数组序列化为一个扁平的字节数组，本质是将所有子数组转换为一个长数组，在每个原始子数组的序列前添加其长度信息和一个位掩码。
RLP 根据数据类型和长度采用不同的编码策略，包括单字节值、短字符串、短数组、长字符串和长数组等不同情况的处理规则。
RLP 编码的优势在于其高效性和灵活性。与 JSON 等文本标记语言相比，RLP 仅需少量前缀字节就能表示复杂的数据结构，大大降低了存储和传输开销。
简单序列化编码（SSZ）
SSZ 是为以太坊 2.0 专门设计的序列化方法，解决了 RLP 编码存在的一些限制。SSZ 使用固定偏移量，使得在解码消息的个别部分时无需解码整个结构，这对共识客户端非常有用。
SSZ 定义了基本类型（无符号整数、字节、布尔值）和复合类型（向量、列表、容器、联合、位向量、位列表），并确保对合性和单射性两个重要属性。
区块与交易结构
区块结构演进
以太坊完成 The Merge 后，共识机制由工作量证明转变为权益证明，区块结构也相应发生了变化。PoW 区块中的大部分内容作为执行负载被添加进了 PoS 区块中，与共识层内容集成。
当前以太坊的区块结构包含 slot、proposer_index、parent_root、state_root 和 body 等字段。信标区块体包含多个操作字段和执行负载字段。
交易类型与发展
以太坊执行层规范定义了多种交易类型：
- 传统交易：最早的交易类型，使用固定的 gasPrice 计算交易费用
- 访问列表交易：引入 accessList 字段，允许预先声明交易将访问的账户和存储槽
- 动态费用交易：采用双层手续费模型，将 gasPrice 拆分为基础手续费和小费
- Blob 交易：专为 Layer 2 扩展解决方案设计，处理暂时存储大量数据的 Blob
每种交易类型都代表了以太坊协议的重要升级，从基础功能到经济模型和可扩展性都有了显著改进。
数据表示与存储
全局状态树
全局状态树是动态可变更的数据结构，用于记录区块链的最新状态。它维护了地址与账户之间的映射，树中的路径会链接到账户信息记录。
以太坊中包含两类账户：外部拥有账户和合约账户。两者在全局状态树中都是叶子节点，结构相同，但可通过某些字段的值来区分。
存储树管理
状态树通过账户的 storageRoot 字段引用智能合约数据，该字段是账户存储树的根哈希值。存储树通过智能合约字节码中的 SLOAD 和 SSTORE 指令直接进行修改。
存储树中的每一个键都是存储在叶节点中的一个 Slot 的索引。索引代表智能合约中的一个或多个全局变量，编译器在编译时确定每个变量的索引。
安全树机制
安全树是一种 Trie 的封装，指 Trie 中的键经过了哈希处理。以太坊在全局状态树和账户存储树中使用这种封装，目的是防止 DOS 攻击。
通过对键进行哈希处理，可以随机化其字符串表示形式，使分支的分布更加均匀，从而避免 Trie 退化为包含长路径且分支最少的结构。
常见问题
以太坊为什么选择 Merkle Patricia Trie 作为核心数据结构？
MPT 结合了 Patricia Trie 的高效存储和 Merkle Tree 的防篡改验证特性，既能高效组织数据，又能提供安全验证，非常适合区块链环境的需求。
RLP 编码与 SSZ 编码的主要区别是什么？
RLP 是自描述的，可以解码成结构化对象而无需预先了解对象形态；SSZ 必须事先知道反序列化的对象类型，但使用固定偏移量，支持部分解码，效率更高。
以太坊如何防止存储树上的 DOS 攻击？
通过对键进行哈希处理，随机化字符串表示形式，使分支分布更加均匀，避免攻击者构造特定负载使 Trie 退化为低效结构。
全局状态树与交易树的主要区别是什么？
全局状态树是动态的，随区块链状态变化而更新；交易树是静态的，一旦交易执行完毕，内容就不可更改，确保所有已执行交易被永久记录。
SSZ 编码如何支持 Merkle 化过程？
SSZ 专门设计为能够与 Merkle 协议集成，使用固定偏移量和确定性的序列化方式，使得在 Merkle 化过程中能够高效计算哈希和验证。
Blob 交易如何改善以太坊的可扩展性？
Blob 交易通过引入临时存储大量数据的机制，降低了 Layer 2 Rollup 方案的数据可用性成本，为以太坊的大规模应用提供了更好的支持。