《以太坊账户模型与数据结构：探秘区块链世界的架构密码》

引言

在区块链技术的发展历程中，以太坊作为第二代区块链的代表，以其独特的账户模型和数据结构设计，为智能合约的运行和分布式应用的开发提供了强大的支持。与比特币的 UTXO 模型不同，以太坊采用基于账户的模型，通过账户地址和状态的映射，实现了对账户余额、交易次数、合约代码等信息的高效管理。为了满足区块链系统对数据完整性、高效存储和快速更新的需求，以太坊在数据结构的选择上进行了深入的探索和创新。本文将详细介绍以太坊账户模型、数据结构的选择与优化，以及 Modified Patricia Trie (MPT) 在以太坊中的应用，探讨其在状态树管理、区块头结构、存储与序列化、证明机制等方面的特点和优势。

一、以太坊账户模型

以太坊采用基于账户的模型，与比特币的 UTXO 模型不同。每个账户都有一个状态，包括：

地址（addr）：160 位（20 字节）的十六进制数，40位16进制数，唯一标识一个账户。

状态（state）：包括余额（Balance）、交易次数（Nonce）、合约代码（CodeHash）和存储根（StorageRoot）等。

账户分为两类：

外部账户（EOA）：由私钥控制，用于发送交易。

合约账户（CA）：由代码控制，用于执行智能合约。

二、数据结构的选择

为了高效管理账户状态，以太坊需要一种既能快速查找和更新，又能提供数据完整性证明的数据结构。

（一） 哈希表

优点：查找和更新效率高（O(1)）。

缺点：无法高效提供数据完整性证明（如余额证明）。

（二） Merkle Tree

优点：可以高效提供数据完整性证明。

缺点：
①不可变：每次更新需要重新构建整棵树，代价高。

②无序：如果不排序，树结构不唯一，导致根哈希不一致。

（三） Sorted Merkle Tree

Sorted Merkle Tree 的优缺点

优点：

①树结构唯一：由于键值对按顺序排列，生成的树结构唯一，不受插入顺序影响。

②支持高效的不存在性证明：由于键值对有序，可以通过二分查找快速证明某个键不存在。

③数据完整性验证：与普通 Merkle Tree 一样，Sorted Merkle Tree 支持高效的数据完整性验证。

④适用于稀疏数据集：当键值分布稀疏时，Sorted Merkle Tree 的路径压缩效果显著。

加粗样式
缺点：

①插入和更新效率低：每次插入或更新键值对时，需重新排序并重构树，时间复杂度较高。

②存储开销较大：由于需要维护排序，Sorted Merkle Tree 的存储开销比普通 Merkle Tree 更大。

③实现复杂度高：排序和路径压缩的实现增加了代码复杂度。

④不适合频繁更新的场景：由于插入和更新效率低，Sorted Merkle Tree 不适合键值对频繁变化的场景。

Sorted Merkle Tree 的应用场景

①区块链中的交易验证：用于验证交易是否包含在区块中，或证明某个交易不存在。

示例：
比特币中使用 Merkle Tree 验证交易存在性，Sorted Merkle Tree 可进一步支持不存在性证明。

②分布式数据库：用于高效验证数据的完整性和一致性。

示例：
IPFS 中使用 Merkle Tree 验证文件块的完整性。

③稀疏数据集管理：当键值分布稀疏时，Sorted Merkle Tree 的路径压缩效果显著。

示例：
以太坊中的账户地址分布稀疏，适合使用 Sorted Merkle Tree。

Sorted Merkle Tree 与普通 Merkle Tree 对比

（四） Patricia Tree（前缀树）

Trie（前缀树）

Trie（前缀树）是一种树形数据结构，用于高效存储和检索键值对。在以太坊中，Trie 被用于构建状态树（MPT），管理账户地址到账户状态的映射。

Trie 的优缺点

优点
①地址格式固定，查找效率高

②以太坊地址为 160 位（40 个十六进制数），长度固定。

③Branching Factor：每个节点有 17 个子节点（16 个十六进制数 + 1 个结束标识符）。

④查找效率：查找时间复杂度为 O(k)，其中 k 是键的长度（以太坊中 k=40）。

⑤无碰撞：不同地址映射到不同的分支，不会发生碰撞。

⑥唯一性：无论数据插入顺序如何，生成的 Trie 结构相同。

⑦更新操作的局部性：更新某个键的值时，只需修改相关分支，无需遍历整棵树。

⑧支持前缀压缩（Patricia Trie）：共享前缀的键值对合并存储，减少存储空间。

缺点
①存储浪费：一脉单传问题，某些分支可能只有一个子节点，导致存储空间浪费。

②查找效率受键长度影响：键越长，查找需要访问的节点越多。

③路径压缩的局限性：当键值分布稀疏时，路径压缩效果不明显。

Patricia Tree（前缀树）

Patricia Trie（Practical Algorithm to Retrieve Information Coded in Alphanumeric）是一种经过优化的 Trie 数据结构，通过路径压缩减少存储空间并提高查找效率。

Patricia Trie 的核心思想

①路径压缩：将共享相同前缀的键值对合并存储，减少冗余节点。

②树高度变浅：压缩后，树的层级减少，查找和更新效率提高。

③分叉处理：插入新键时，若与现有键无共享前缀，则生成新分支。

路径压缩的适用场景

①键值分布稀疏：当键值分布稀疏时，路径压缩效果显著。
比如：
misunderstanding
decentralization
disintermediation
下面这样的结构效率很低。

使用Patricia Trie之后：

②长键值：键值越长，路径压缩的收益越大，路径压缩显著减少存储空间。

③共享前缀较多：当键值之间存在较多共享前缀时，路径压缩效果明显。

Patricia Trie 的优缺点

优点
①存储空间优化：通过路径压缩减少冗余节点，节省存储空间。

②查找效率提高：树高度变浅，查找时间复杂度降低。

③支持高效更新：更新某个键的值时，只需修改相关分支。

缺点
①分叉开销：插入新键时，若与现有键无共享前缀，需生成新分支。

②实现复杂度较高：路径压缩和分叉处理增加了实现复杂度。

Patricia Trie 与普通 Trie 对比

三、以太坊的 Modified Patricia Trie (MPT)

以太坊结合 Merkle Tree 和 Patricia Tree 的优点，设计了 Modified Patricia Trie (MPT)，用于管理账户状态。

这个图中，右上角有四个账户，为了简单起见，账户地址比较短。假如只有7位地址，而不是40位。账户状态只有余额。
树中的节点分为三种：
extension node：如果树的部位出现了压缩就会有extension node。四个地址根节点都是a7，shared nibble（s）就是a7。nibble 是十六进制数的意思。
branch node：分支节点。有1、7、f。
leaf node：叶节点。

节点的连接不是通过指针，意思是比如7里面存的值是下一个节点的哈希值。普通指针存的是地址，不是哈希值。

以太坊中的结构是一个大的mpt，包含很多小的mpt。每一个合约账户的存储，都是一个小的mpt。
在这个图中，Nonce，balance变化了，Codehash没有变化，所以是指向原来的节点。Storage root 变了。存储树中的大部分节点也是没有改变，只有整数变量从29变为45，新建了分支。

所以系统中每个全节点需要维护的不是一棵 mpt 树，而是每次出现一个区块要新建一个mpt。只有少数变化了的节点需要新建分支。

那么为什么要保留历史状态；临时性的分叉，两个节点同时获得记账权，有一个获得记账权，另一个节点进行 roll back，回到前一个状态，再沿着链往后。如何进行回滚呢，需要历史状态。

（一） MPT 的特点

路径压缩：共享相同前缀的键值对合并存储，减少存储空间。

局部更新：更新账户状态时，只需修改相关分支，无需重构整棵树。

历史状态保留：每次更新生成新分支，旧状态保留，支持分叉和回滚。

防篡改：根哈希值写入区块头，确保数据完整性。

（二） MPT 的节点类型

MPT 包含三种节点：

Extension Node：
①存储共享前缀（shared nibble）。
②指向下一个节点。

Branch Node：

①存储 16 个子节点的哈希值（对应 16 进制数）。
②用于分支分叉。

Leaf Node：
①存储账户状态（如余额、Nonce 等）。

（三） MPT 的存储结构

键：账户地址（160 位十六进制数）。

值：账户状态（经过 RLP 编码的字节数组）。

节点连接：通过哈希指针（而非普通指针）连接节点，确保数据不可篡改。

四、 区块头与状态树

以太坊的区块头包含多个字段，其中与状态树相关的字段包括：
block header
parent hash ：前一个区块块头的哈希值。父区块哈希。
UncleHash：叔块
Coinbase：挖出矿的矿工地址
Root：状态树的根哈希值。以太坊三棵树有状态树，交易树和收据树。
TxHash：交易树的根哈希值。
ReceiptHash：收据树
Bloom： Blomm filter。提供了一种高效的查询，父合某种条件的交易的执行结果。
Difficulty：挖矿难度。
GasLimit：汽油费，类似于比特币中的交易费。
GasUsed：汽油费相关。
Time：区块的大致产生时间。
MixDigeszt：从Nonce随机数经过计算 算出的哈希值。
Nonce：挖矿猜的随机数，符合难度要求。

（一）区块结构

Header：指向区块头的指针。

Uncles：指向叔块的指针数组。

Transactions：区块中的交易列表。

external block，这个就是区块真正在往上发布的是这些信息。

五、状态树的存储与序列化

（一） 账户状态存储

状态树中存储的键值对（key, value）经过序列化(RLP)处理。

键：账户地址。

值：账户状态（包括余额、Nonce、CodeHash、StorageRoot 等）。

（二）序列化方法

以太坊使用 RLP（Recursive Length Prefix） 编码，将数据转换为字节数组。RLP 支持嵌套结构，适合存储复杂数据。

六、 证明机制

（一）交易存在性证明

通过Merkle Proof证明交易包含在区块中。

全节点提供从交易到 Merkle Tree 根节点的路径（包含路径上的哈希值）。

轻节点通过这些哈希值重新计算根哈希值，并与区块头中的 Merkle 根对比。

（二） 交易不存在性证明

需要排序的 Merkle Tree 来证明交易不在区块中。

通过证明交易不在 Merkle Tree 的某个分支中实现。

（三） 账户状态证明

通过 MPT 提供账户状态的 Merkle Proof。

证明账户状态的存在性或不存在性。

七、MPT 的实际应用

（一） 状态树的更新

每次新区块发布时，状态树中只有少数节点需要更新。

更新时生成新分支，旧状态保留，支持历史状态查询和回滚。

（二） 合约账户的存储

每个合约账户的存储也是一个 MPT。

合约状态的变化通过 MPT 的局部更新实现。

八、MPT 与比特币Merkle Tree对比

总结

以太坊通过采用基于账户的模型和 Modified Patricia Trie (MPT) 数据结构，实现了对账户状态的高效管理和数据完整性验证。MPT 结合了 Merkle Tree 和 Patricia Tree 的优点，通过路径压缩、局部更新和历史状态保留等特性，优化了存储空间利用和查找效率，同时支持分叉和回滚操作，确保了系统的灵活性和可靠性。在区块头与状态树的结合中，以太坊将状态树的根哈希值写入区块头，实现了数据的防篡改和快速验证。通过 RLP 序列化方法，以太坊将复杂的账户状态数据转换为字节数组，便于存储和传输。在证明机制方面，MPT 提供了交易存在性证明、交易不存在性证明和账户状态证明等功能，为轻节点验证和分布式系统中的数据一致性维护提供了有力支持。与比特币的 Merkle Tree 相比，以太坊的 MPT 在数据结构和功能上进行了进一步的优化和扩展，更好地适应了智能合约平台的需求。总之，以太坊的账户模型和数据结构设计为其生态系统的发展和应用提供了坚实的基础，为区块链技术的创新和进步做出了重要贡献。