以太坊的核心功能，就是维护一个从“地址 (Address)”到其对应“状态 (State)”的、持续更新的、全球共享的巨大映射（Mapping）关系。这个宏大的、在某一瞬间的完整映射，就被称为以太坊的世界状态 (World State)。而我们之前讨论的状态树（State Trie），正是实现这个映射的技术手段。

以太坊的地址和状态

以太坊地址是一个独一无二的标识符，它代表了网络上的一个“位置”或“目的地”。所有可以接收资产或信息的实体，都拥有一个地址。一个以太坊地址是一个以0x开头的、由40个十六进制字符（数字0-9和字母a-f）组成的字符串。 例如：0x742d35Cc6634C0532925a3b844Bc454e4438f44e实际上这个地址也是由一个公钥进行一定的哈希算法得到的。

而以太坊所述的状态，具体指账户的状态，根据上节所述的不同的账户，EOA与合约账户往往状态不太一样。

一个外部拥有账户的状态，主要由两项数据构成：

• nonce: 一个计数器，记录了“这个地址已经发送过多少笔交易”。每成功发送一笔交易，nonce就加1。它的核心作用是防止交易重放。
• balance: 该地址当前拥有的ETH余额，以最小单位Wei（1 ETH = 10^18 Wei）来记录。

一个智能合约账户的状态，由四项数据构成：

• nonce: 它的nonce比较特殊，只在这个合约要创建另一个新合约时才会增加。
• balance: 和EOA一样，代表这个合约自身持有的ETH余额。是的，合约可以像人一样持有ETH。
• codeHash: 代码哈希。这是指向该合约程序代码的“指-纹”。这段代码在合约部署时被确定，是不可更改的。它定义了合约的所有行为逻辑。
• storageRoot: 存储根。这是指向该合约内部私有数据库的“指-纹”。这个存储空间是合约的“记忆芯片”，用来记录各种需要持久化的数据。例如：
  • 一个ERC-20代币合约，会在这里记录每个地址拥有多少该代币。
  • 一个NFT合约，会在这里记录每一个NFT（Token ID）目前归哪个地址所有。
  • 一个DeFi借贷协议，会在这里记录每个用户的存款和借款金额。

以太坊的“世界状态”就是一个巨大的、包含数亿条目的列表，每一条都是：

Address (地址) -> State (状态数据: nonce, balance, codeHash, storageRoot)

而状态树 (State Trie) 这个数据结构，就负责将这些键值对（Address -> State）组织起来，并计算出一个唯一的、32字节的状态根 (stateRoot)，记录在每个区块头中，从而以极高的效率和安全性来维护和验证这个庞大的映射系统。

在这里，状态树和BTC中的交易树最大的区别就是，状态树比BTC中的树远远大的多，因此BTC中每个区块最多也只有4000个交易，而同样时间内ETH只是数以亿计的状态中改变了4000个，因此BTC可以通过某个矿工的工作量证明最终决断交易的有效性，因为BTC只记录交易历史，而交易历史是无状态的。

但一个以太坊区块执行后，会导致数百万个账户中的任意数量发生变化（余额增减、合约内部数据改变等）。这个“世界状态”即所有账户当前状态的完整快照的数据量是极其庞大的（TB级别）。把整棵状态树（这个TB级别的文件）打包并发布到网络上是完全不可行的，带宽和处理时间都无法承受。

因此，以太坊必须找到一种方法，既能证明状态发生了正确的改变，又不需要传输海量的数据。明白了这一点，我们再接下来进行讨论。

状态数据结构的讨论

哈希表

哈希表（Hash Table / Hash Map）拥有O(1)的平均查找速度，确实是实现键值对快速查找的完美选择。在需要查找某个地址对应的状态时，哈希表是有优势的。但是使用哈希表会存在如下的问题：

问题一：无法高效地达成全网共识 (Inability to Reach Consensus)

这是最根本的问题。以太坊网络有成千上万个节点，分布在全球各地。在每个区块处理完一批交易后，所有节点都必须确保它们的世界状态完全一致。

• 如果用哈希表：
  • 两个节点该如何比较它们的哈希表是否一模一样？难道要把数百万个账户的数据全部传输一遍进行对比吗？这在带宽和时间上是完全不可行的。
  • 哈希表本身没有一个内置机制，可以生成一个代表其所有内容的、独一无二的、简短的“指纹”。也就是BTC中使用默克尔树的原因。我们必须有一个验证机制。

问题二：无法提供轻客户端所需的“默克尔证明” (Inability to Provide Merkle Proofs)

以太坊网络不仅有存储所有数据的全节点，还有只下载区块头的轻节点（例如手机钱包）。轻节点也需要一种方法来独立验证某个账户的状态，而不能仅仅“相信”全节点告诉它的信息。

• 如果用哈希表：
  • 一个轻节点想知道“我的余额是多少？”。它向一个全节点询问。
  • 全节点回复说“你的余额是10 ETH”。轻节点该如何相信这个答案？它无法验证。为了证明这个信息的真实性，全节点可能需要把整个哈希表或者很大一部分数据都发给轻节点，这违背了轻节点的初衷。

问题三：数据结构的确定性问题 (Issues with Determinism)

为了让所有节点计算出完全相同的根哈希，数据结构本身必须是完全确定性的。

• 如果用哈希表：
  • 不同的编程语言（Go, Rust, Python）对哈希表的内部实现是不同的，尤其是在处理哈希碰撞和内存布局时。
  • 即使两张哈希表记录完全相同的数据，它们在内存中的字节表示也可能不同。对它们进行哈希运算，很可能会得到不同的结果。

将哈希表组织成一个默克尔树

将哈希表进行“默克尔化”（Merkle-ize），工作方式如下：

1. 将哈希表中的所有键值对（地址 -> 状态）取出来。
2. 将这些键值对按照键（地址）进行确定性的排序（例如，按字母或数字顺序）。
3. 基于这个排好序的列表，自下而上地构建一棵标准的默克尔树，最终得到一个唯一的默克尔根。

这个结构确实解决了共识验证和轻客户端证明的问题。只要有了这个根，我们就能验证整个数据集。但是对于以太坊，这个方案存在严重的更新效率 (Update Efficiency)问题。

以太坊的世界状态不是一成不变的，它在每个区块中都会发生数千次改变。我们需要一个能够高效地反映这些改变的数据结构。

• 场景：假设只有一个账户的余额发生了变化。
  • 在“默克尔化哈希表”方案中：
    1. 首先，哈希表中的对应值被更新。
    2. 但为了计算出新的默克尔根，我们不能只更新树上的一条路径。因为这棵树是基于所有元素排序后构建的。
    3. 我们必须重新取出所有数百万个账户的数据，对它们重新排序，然后自下而上地完全重建一棵全新的默克尔树。
    4. 这个操作的计算成本是极其高昂的（大约是O(N)或O(N log N)级别，N是账户总数）。如果每个区块都这样做，整个网络的效率将无法想象地低下。

注：这里注意的是，我们必须在ETH中进行这样的排序，因此在前面说过，使用BTC那样的共识机制，是不可能的。所以想要所有的节点都达成共识，必须有一个排序的规则。而BTC因为是靠最后的矿工判断这个共识的，所以BTC中的默克尔树实际上不需要进行排序。

一个标准的默克尔树

将所有数据项（在这里是所有账户的状态）排成一个有序的列表，然后在这个列表上构建二叉树。在这棵树里，一个数据的位置是由它在列表中的“次序”或“索引”决定的（例如，“第500万个账户”）。树的路径和账户的地址本身没有直接关系。

这样的方案实际上会在更新上更差。

问题一：查找和证明效率低下

假如查找地址 0x742d... 的余额。

• 在标准默克尔树中：
  1. 不能直接用地址 0x742d... 来遍历树，因为树的结构和地址无关。
  2. 我们必须先在一个概念上的、包含所有数百万个账户的**“全局有序列表”中，通过二分查找等方法，找到地址 0x742d... 位于第几个位置**。这是一个 O(log N) 的操作。
  3. 知道了它是“第N个”元素后，我们才能在默克尔树中找到对应的路径，并生成默克尔证明。
• 这是一个间接的、两步走的过程，效率更低，也更复杂。

问题二：更新效率低下

以太坊的状态是频繁变动的。我们再来看那个“只有一个账户余额变化”的场景。

• 在标准默克尔树中：
  • 当一个账户的状态更新后，它在那个“全局有序列表”中的位置没有变，所以它在树上的位置也没变。更新它自己到树根的路径（O(log N)）看起来是高效的。
  • 但问题出在新增账户时。假设我们要添加一个新账户，它的地址按排序规则，应该插在整个列表的中间。
  • 这会导致列表中所有在它后面的元素，其“索引”都加了1。这意味着它们在默克尔树中的位置都发生了变化，导致树的一大半都需要被重新计算和构建。这在计算上是不可接受的。

排序默克尔树

一个普通的排序默克尔树，无法同时高效地满足区块链状态机的三大核心需求：查找（Read）、更新（Write）、和证明（Prove）。尤其是在“更新”这一环，它的效率很差，这使得它在实践中完全不可行。

场景：一笔交易发生，只改变了Alice账户的余额。

1. 查找 (Read)
   • 为了找到Alice的状态，我们不能直接用她的地址0x123...来导航。我们必须先在一个包含数亿个账户的、概念上的“全局有序列表”中，通过二分查找等方法，找到Alice的地址排在第几个。
   • 这是一个间接、效率较低的查找过程。
2. 更新 (Write)
   • 我们更新了Alice账户的状态（她的余额减少了）。
   • 为了计算出代表整个新世界状态的新默克尔根，我们必须：
     1. 取出所有数亿个账户的数据。
     2. 将它们重新排序（虽然只是一个值变了，但为了保证确定性，流程上需要这样做）。
     3. 然后从零开始，自下而上地完全重建一棵全新的默克尔树。
   • 这是一个 O(N) 级别的操作（N是账户总数）。为了一个账户的微小变动，而去重新计算和构建整个宇宙的状态，这个代价是无法承受的。
3. 证明 (Prove)
   • 默克尔证明机制本身是有效的。但为了生成一个证明，我们仍然需要先经过第一步那个间接、低效的查找过程来定位数据。

核心缺陷：更新成本过高。它就像一本每次修改一个字，就需要把整本书全部重新打印和装订一遍的百科全书。

前缀树(Trie)

前缀树的路径本身就代表了被存储的字符串，而节点本身不存储字符，只表明连接关系。理解Trie最直观的方式就是想象一个我们每天都在用的功能：

• 搜索框的自动补全：当您在Google搜索框里输入 “th”，它会立刻提示 “the”, “thanks”, “this” 等。您继续输入变成 “tha”，提示就变成了 “thanks”, “that”。Trie正是实现这种功能背后最高效的数据结构。
• 字典目录：一本英文字典，所有的单词都按字母顺序排列。所有以 "c" 开头的单词都在一个大章节里，其中所有以 "ca" 开头的又在一个小节里。Trie就是这种组织方式的程序化实现。

我们来构建一个包含以下单词的Trie："tea", "ted", "ten", "in", "inn"

1. 从一个空的根节点开始。
2. 插入 "tea":
   • 从根节点开始，创建一个指向 t 的分支，再从 t 创建指向 e 的分支，最后从 e 创建指向 a 的分支。
   • 为了表示"tea"是一个完整的单词，我们在节点 a 上打一个“结束标记”（比如把它涂成蓝色）。
3. 插入 "ted":
   • 从根节点开始，路径 t -> e 已经存在了，我们共享并复用这个前缀。
   • 只需要从节点 e 创建一个新的指向 d 的分支。
   • 在节点 d 上打上“结束标记”。
4. 插入 "ten":
   • 同样，复用 t -> e 的路径，然后从节点 e 创建一个新的指向 n 的分支，并标记 n。
5. 插入 "in":
   • 从根节点创建一条全新的路径 i -> n，并标记 n。
6. 插入 "inn":
   • 复用 i -> n 的路径。注意，此时的 n 节点本身已经是一个结束标记（代表单词 "in"）。
   • 我们从这个 n 节点再创建一个指向 n 的新分支，并标记这个新的 n 节点。

Trie的优缺点

优点：

1. 极速的前缀查找：查找一个长度为 k 的字符串或前缀，时间复杂度是 O(k)。查找速度与Trie中存储了多少个单词无关，只与你要查的字符串长度有关。这是它比哈希表等结构在特定场景下更优越的地方。
2. 空间效率高（对于共享前缀）：如果大量字符串拥有共同的前缀（例如字典里的单词、IP地址、以太坊地址），Trie通过共享这些前缀路径，可以节省大量存储空间。
3. 天然有序：可以很方便地按字母顺序遍历所有存储的字符串。

缺点：

1. 空间消耗大（对于无共享前缀）：如果字符串之间没有太多公共前缀，Trie可能会比哈希表占用更多的空间，因为每个节点都需要维护一个指向所有可能下一个字符的指针数组/哈希表。
2. 对长字符串不友好：树的深度由最长的字符串决定。

在以太坊中，其就使用一种经过优化的、默克尔化的Trie（Merkle Patricia Trie）来存储其世界状态。其中因为前文说过以太坊地址是40个16进制的数，那么对应的branching factor就是17。

帕特里夏树（Patricia Trie）

核心思想：合并“不分叉的公路”

让我们回到Trie数据结构的“公路网”比喻：

• 标准Trie：就像一个“本地公交系统”，它必须在**每一站（每个字符）**都停一下。即使从A站到D站中间的B、C两站没有任何岔路，公交车也必须按顺序停靠A -> B -> C -> D。
• Patricia Trie：则像这个系统的“快速直达快线”。它会观察路网，如果发现从A到D的路径 A -> B -> C -> D 是一条笔直的、没有任何其他岔路的“高速公路”，它就会直接开通一条从A直达D的快线。这条快线的路牌上会写着“此路段代表BCD”。

通过这种方式，Patricia Trie 消除了那些只有一个子节点的中间节点，将一长串没有分叉的路径压缩成一步。Patricia Trie的压缩效果好坏，直接取决于它所存储的键（Key）集合的自身特性。

总的来说，当键（Key）集合满足以下两个主要特征时，Patricia Trie的压缩效果会非常好：

1. 存在大量的、长短不一的公共前缀 (Long and Varied Common Prefixes)

这是最核心、最重要的一个因素。

• 什么是公共前缀？ 比如 “apple”、“apply”、“application” 都共享公共前缀 “appl”。
• 为什么这很重要？ Patricia Trie的核心就是共享这些前缀路径。如果大量的键都从同样的前缀开始，这些共享的路径就可以被高度压缩，从而节省大量节点和空间。

压缩效果好的例子：

• 英文字典：大量的单词有共同的词根和前缀，例如 re-, pre-, trans- 等。存储一本字典时，压缩效果会极好。
• IP地址：同一个子网内的IP地址，其前缀部分是完全相同的。例如 192.168.1.1 到 192.168.1.254。
• 以太坊地址：虽然以太坊地址看起来是随机的，但在海量数据中，总会出现大量地址共享前面几个、甚至十几个字符的情况。每个这样的共享都能带来一次压缩机会。

压缩效果差的例子：

• 如果我们要存储一组键："apple", "banana", "cherry", "durian"。
• 这些键的第一个字母就完全不同，它们之间没有任何公共前缀可以共享。
• 在这种情况下，Patricia Trie会退化成一个非常简单的结构，从根节点直接分出四个不同的分支，几乎没有任何压缩效果可言。

2. 键的分布比较稀疏，形成“长链”

这个特性与第一点紧密相关，它指的是在树的很多地方，都存在长长的、没有分叉的路径。

• 什么是“长链”？ 想象一下，树中有一条路径，代表了前缀 “application”，而在这个前缀之后，只有一个单词 "s" 存在，形成了 "applications"。从 “application” 到 "applications" 的这个 “s” 节点就是一个单孩子节点。如果后面还有 "ship" 等，就会形成更长的链。
• 为什么这很重要？ Patricia Trie的设计正是为了消除这些单孩子节点链。一条链越长，它能被压缩得越厉害，节省的空间就越多。标准Trie需要为这条链上的每个字符都创建一个节点，而Patricia Trie只需要一个节点（或者说一条边）就能代表整条链。

Patricia Trie的优势

1. 节省大量空间 (Space Efficiency)：这是它最主要的优点。通过消除冗余的中间节点，显著减少了内存占用，特别是当键（key）很长且前缀高度共享时。
2. 提升查找速度 (Faster Traversal)：因为树的深度变浅，需要遍历的节点数量减少，这意味着更少的指针跳转和更好的CPU缓存利用率，从而让查找、插入和删除操作更快。

默克尔·帕特里夏·树（Merkle Patricia Trie, MPT）

MPT是一种将三个核心计算机科学概念（Trie、Patricia、Merkle）融合在一起的、高度优化的、复合型树状数据结构。

1. Trie (字典树/前缀树)：这是它的基本骨架。一个Trie的核心特性是用路径来代表键（Key）。在以太坊中，这个“键”就是账户地址。
2. Patricia (帕特里夏树/紧凑前缀树)：这是对Trie的压缩优化。它将Trie中那些没有分叉的、长长的单链路径（例如a->b->c）压缩成一步，从而极大地节省了存储空间并提升了遍历速度。当键（如以太坊地址）很长且分布稀疏时，这个优化至关重要。
3. Merkle (默克尔化)：这是赋予这棵树密码学安全和可验证性的灵魂。它规定树上任何一个节点的值都是其子节点内容的哈希。这个过程从叶子节点（账户状态）开始，逐层向上哈希，最终汇聚成一个代表整棵树所有数据快照的、唯一的根哈希（Root Hash）。

因此，MPT是一个经过压缩优化的、用账户地址作为路径、并通过逐层哈希来保证数据完整性和可验证性的、用于存储键值对的树状数据结构。其核心特性如下：

• 确定性 (Deterministic)：对于任何给定的键值对集合，无论以何种顺序插入，最终生成的根哈希永远是唯一的、完全相同的。
• 高效的局部更新：当只有少数账户状态改变时，只需更新树中与这些账户相关的路径上的节点即可（一个O(log N)的操作），绝大部分树结构保持不变。
• 唯一的根哈希：无论树中数据多么庞大（数亿个账户），所有数据都可以被一个唯一的、32字节的根哈希所代表。
• 密码学可验证性：可以生成简短的“默克尔证明（Merkle Proof）”，向任何人（特别是轻客户端）证明某个特定的键值对确实存在于这棵由特定根哈希所代表的树中，而无需展示整棵树。

MPT解决了这三个问题：

• 解决了全网共识的效率问题：节点之间无需传输和比较TB级别的完整状态数据，只需比较那个32字节的stateRoot，就能高效地就整个复杂的世界状态达成共识。
• 解决了轻客户端的验证问题：使得手机钱包等轻客户端能够在不下载全部数据的情况下，安全、独立地验证自己账户的状态信息（如余额），实现了“不信任但可验证”。
• 解决了状态更新的效率问题：完美契合了区块链需要每隔十几秒就对庞大状态集进行频繁局部更新的核心场景，避免了每次更新都要重建整个数据库的灾难性开销。

Merkle Patricia Trie的最终目的，是以一种密码学安全、可验证、且对更新操作极其高效的方式，来存储和管理以太坊作为一个“世界计算机”的全局共享内存——即世界状态。

它在以太坊中被用于三棵主要的树，分别对区块的不同方面进行承诺和验证：

• 状态树 (State Trie)：最重要的一棵，其根哈希（stateRoot）被记录在每个区块头，代表了所有账户的状态。
• 交易树 (Transaction Trie)：每个区块独立构建，其根哈希（transactionsRoot）代表了该区块内所有交易的集合。
• 收据树 (Receipts Trie)：每个区块独立构建，其根哈希（receiptsRoot）代表了所有交易执行后产生的“收据”（如Gas消耗、事件日志等）。

在以太坊的实际应用中，MPT主要能证明以下两类事情：

1. 证明“包含关系”（Inclusion Proof）

这是最常见的用途。它可以证明某个数据确实存在于状态中。

• 对于状态树（State Trie）：
  • 证明一个账户的存在及其状态：
    • “能证明，在stateRoot为0xabc...的这个世界状态里，地址0x123...的余额确实是10 ETH，并且nonce是5。”
  • 证明一个合约账户的存储：
    • “能证明，在stateRoot为0xabc...的这个世界状态里，USDT合约的存储中，记录着地址0x123...的代币余额是1000 USDT。”
• 对于交易树（Transaction Trie）：
  • 证明一笔交易确实被打包了：
    • “我能证明，这笔哈希为0xdef...的交易，确实包含在transactionsRoot为0x456...的那个区块里。”

2. 证明“非包含关系”（Non-inclusion Proof）

这一点稍微复杂一些，但同样强大。MPT也能证明某个数据确实不存在于状态中。

• 如何做到？ 证明过程是通过展示在树中，当您沿着目标键的路径去查找时，最终会走到一个空节点，或者会走到一个路径与您的目标键不完全匹配的叶子节点。
• 实际应用：
  • 证明一个账户不存在：
    • “能证明，在stateRoot为0xabc...的这个世界状态里，不存在地址为0x789...的账户。”（例如，可以证明某个地址从未被使用过）。

ETH中的MPT

以太坊使用的是一个经过高度定制和改良的默克尔·帕特里夏·树，而不是一个理论上的原生MPT。虽然它完全遵循了默克尔（Merkle）和帕特里夏（Patricia）的核心思想，但在具体的实现层面，为了适应区块链的特殊需求，它引入了几个关键的、独有的设计。

1. 明确定义了三种节点类型 (Three Specific Node Types)

为了高效地实现压缩和分支，以太坊的MPT将所有节点明确地分为三种：

• 叶节点 (Leaf Node)：
  • 代表一条路径的终点。
  • 它包含两部分数据：一部分是路径的剩余部分（经过特殊编码），另一部分是最终的值（Value），例如一个账户的RLP编码状态。
• 扩展节点 (Extension Node)：
  • 这是帕特里夏压缩思想的直接体现。它代表了一段没有分叉的、被压缩的路径。
  • 它也包含两部分数据：被压缩的路径部分，以及一个指向下一个节点的哈希指针。
• 分支节点 (Branch Node)：
  • 代表一个“岔路口”，路径在这里发生分歧。
  • 它是一个拥有17个槽位的数组。
    • 前16个槽位分别对应十六进制字符0到f。如果地址的下一位是a，就走第a个槽位指向的路径。
    • 第17个槽位用来存储一个值（Value）。这用于处理一个单词正好在分叉点结束的情况（例如，同时存在"car"和"cat"，分支节点ca就可以在第17个槽位存储"car"的值，同时在t槽位有一个指向后续节点的指针）。

2. 独特的十六进制前缀编码 (Hex-Prefix Encoding)

• 问题：当看到一段路径时，我们如何区分这是一个代表路径终点的“叶节点”，还是一个代表路径中间部分的“扩展节点”？例如，路径...abc是代表一个键abc的终点，还是代表一个更长的键abcdef的一部分？
• 解决方案：以太坊在对路径进行编码时，在路径的第一个“半字节”（nibble）中加入了一个特殊的标记。这个标记同时编码了两个信息：
  1. 奇偶性：路径的剩余长度是奇数还是偶数。
  2. 节点类型：这是一个叶节点（路径终点）还是一个扩展节点（路径中间点）。
• 作用：这种编码方式确保了任何一个键值对集合，只能被唯一的一种MPT结构所表示，消除了所有可能的歧义，保证了哈希结果的绝对确定性。

3. 键（Key）和值（Value）的特定格式

• 键的哈希处理：在以太坊的状态树中，用作“键”的不是原始的地址（20字节），而是这个地址经过Keccak-256哈希运算后得到的结果（32字节）。这样做可以保证键的长度统一，并且使得键在树中的分布更加均匀，提高了树的平衡性和效率。
• 值的RLP编码：存储在叶节点或分支节点中的“值”（例如账户状态），不是以明文或JSON格式存储的，而是使用以太坊独有的RLP（Recursive Length Prefix，递归长度前缀）编码方案进行序列化。RLP是一种能将任意复杂的嵌套数据结构，高效地编码成字节数组的方案。

![[Pasted image 20250629155602.png]]

当一个新区块发布时，其对应的新的状态树（State Trie），不是从零开始重新构建的，而是在上一个区块的状态树的基础上进行修改和更新得到的。由于MPT的特性，即使修改操作效率极高。它不会触动整棵树，而只会创建从被修改的叶子节点到树根的那几条路径上的新节点。树中其他数百万个未受影响的分支，在新的状态树中会直接复用旧树的节点哈希。

![[Pasted image 20250629160650.png]]

MPT的修改机制

当N+1个区块进行发布后，第N个区块的状态树不会被“完全替换”，它在某种程度上依然“存在”于全节点的历史记录中。但是，“如何存在”以及“能存在多久”，则取决于节点的运行模式。

核心机制：“写时复制” (Copy-on-Write) 与数据共享

首先，以太坊节点在处理新区块时，采用的是一种极其高效的、类似于版本控制系统Git的“写时复制”策略，而不是“删除旧的，写入新的”。

1. 起点：节点拥有代表第N个区块状态的stateRoot_N。这个根哈希是指向数据库中存储的MPT节点的入口。
2. 更新过程：当处理第N+1个区块的交易时，假设只有一个账户A的状态改变了。
   • 节点会找到账户A在树中的叶子节点，并创建一个新的叶子节点来代表A的新状态。
   • 然后，它会创建新的父节点来指向这个新叶子，并继续向上创建新的父节点，直到树根，最终形成一个新的stateRoot_N+1。
   • 关键在于：在这个过程中，整棵树中除了从账户A到树根的那一条路径之外的所有其他节点（代表了数亿未变动的账户），都没有被触动。
3. 数据共享：新的状态树（以stateRoot_N+1为入口）和旧的状态树（以stateRoot_N为入口）共享了绝大部分完全相同的、未发生改变的节点数据。它们就像是同一个Git代码库的两个不同的Commit，共享了大量未修改的文件。stateRoot_N和stateRoot_N+1只是进入这个庞大节点数据库的两个不同的“指针”或“入口点”。

所以，从物理存储上说，旧的状态树并没有被删除或替换，因为它的绝大部分组件正被新的状态树所引用。

不同的节点配置

至于“第N个区块的状态树还存在于历史记录中吗？” 这就取决于节点是如何配置的。

1. 全节点 (Full Node) - 默认运行模式

• 主要目的：高效地验证新区块，并维护好当前以及最近的世界状态，以应对潜在的链重组（Reorgs）。
• 状态修剪 (State Pruning)：为了节省巨大的磁盘空间，一个默认的全节点会执行状态修剪。这意味着，它会定期删除那些“过时的”、不再被最近区块所需要的旧的状态树节点数据。通常，一个全节点可能只保留最近的128个或更多的区块状态。
• 结果：在一个标准的（经过修剪的）全节点上，您可以验证整个链的历史，但您无法查询很久以前某个区块的确切状态。例如，您无法查询“在第1,000,000个区块高度时，Alice的账户余额是多少？”。因为组成那个历史状态的、独有的MPT节点数据可能已经被“修剪”掉了。它拥有完整的区块历史，但没有完整的状态历史。

2. 归档节点 (Archive Node)

• 主要目的：成为一个完整的区块链历史图书馆，保存每一个区块高度下的每一个账户的完整状态。
• 无状态修剪：归档节点在运行时会禁用状态修剪功能。它会把自创世区块以来的、每一个历史状态版本所需要的所有MPT节点都永久保存在数据库里。
• 结果：在一个归档节点上，您可以随时查询任何历史区块高度下的任何状态。您只要提供那个历史区块的stateRoot，归档节点就能从它庞大的数据库中，重构出当时完整的状态树并回答您的查询。
• 代价：巨大的存储成本。归档节点的存储需求是极其庞大的（目前需要超过16TB的高速SSD），并且同步时间极长。通常只有像Etherscan这样的区块浏览器、Infura/Alchemy这样的基础设施服务商才会运行归档节点。

目的

节点保留最近一部分（例如128个）区块的状态，而不是只保留最新的那一个，最主要、最核心的原因是为了安全、高效地处理“链重组”（Reorganization / Reorg）。

• 就像BTC一样，在一个全球分布式的网络中，由于网络延迟，可能会有两个验证者在世界的不同角落，几乎在同一时间都发布了一个有效的、新的区块。
• 这会导致区块链产生一个短暂的“分叉”。网络中的一部分节点先看到了A区块，另一部分先看到了B区块。特别是在ETH中，因为出块时间快，所以这种情况更普遍。
• 经过一段时间，当更多的验证者在其中一条链（比如A链）上继续构建新的区块后，根据“最重链”原则，全网会逐渐统一共识，承认A链是“正统”的，而B链则被抛弃。
• 如果节点一开始不幸地跟随了那条最终被抛弃的B链，那么当它发现A链成为更“重”的链时，它就必须放弃B链，切换到A链上来。这个过程就叫“链重组”。

那么：

• 假设这个分叉有5个区块深。您的节点需要放弃它本地的最近5个区块。
• 这不仅仅是删除区块那么简单，它还必须撤销（回滚）这5个区块里所有交易所带来的状态改变。
• 要想将状态从第N个区块回滚到第N-1个区块，节点必须拥有第N-1个区块结束时的完整状态树（由stateRoot_N-1所指向）。
• 如果节点在处理完第N个区块后，立即删除了第N-1个区块的状态树，那么当需要回滚时，它将无据可查，无法执行这个操作。

对比来说，BTC作为无状态的模型，UTXO记账模型远比以太坊的账户模型简单，其交易的“可逆性”也更强。比特币节点的“状态”，本质上就是它维护的当前全局未花费交易输出（UTXO）的集合。当比特币节点需要回滚一个区块（比如第N号区块）时，它的操作非常机械和简单：

1. 遍历要被抛弃的那个区块N里的每一笔交易。
2. 处理交易的“输入”：交易的输入部分告诉了我们“哪些旧的UTXO在这笔交易中被花掉了”。节点会把这些UTXO重新加回到自己的全局UTXO集合中，让它们恢复到“未花费”状态。
3. 处理交易的“输出”：交易的输出部分告诉了我们“哪些新的UTXO在这笔交易中被创造了出来”。节点会从自己的全局UTXO集合中删除这些新创造的UTXO。

完成这两步加减法后，节点的UTXO集合就自动恢复到了第N-1个区块结束时的状态。但是ETH中的智能合约不一定能进行自动的反向操作。

ETH块头结构

在2022年“合并（The Merge）”升级，以太坊从工作量证明（PoW）转向权益证明（PoS）后，一些字段的含义发生了变化。当前PoS机制下以太坊区块头的完整结构最重要的是三个根。

• 状态根 (stateRoot)
  • 代表在执行完这个区块的所有交易之后，整个以太坊世界状态的MPT的根哈希。
  • 这是以太坊作为“世界计算机”的核心。它为整个网络提供了一个关于所有账户状态的、可高效验证的、唯一的快照。共识主要就是围绕这个stateRoot的正确性来建立的。
• 交易根 (transactionsRoot)
  • 代表包含在这个区块内的所有交易**所组成的MPT的根哈希。
  • 高效地证明某笔特定的交易确实存在于这个区块中。轻客户端可以用它来验证自己的交易是否被打包。
• 收据根 (receiptsRoot)
  • 代表这个区块内所有交易执行后生成的“收据”所组成的MPT的根哈希。每笔交易的收据包含了诸如消耗的Gas量、产生的事件日志（Logs）等信息。
  • 高效地证明某笔交易确实产生了某个特定的结果或事件，而无需重新执行整个交易来验证。

下面是块头中所有字段的详细列表：

RLP (Recursive Length Prefix)

RLP将结构化的数据（例如一个包含多个字段的区块，或者一个嵌套的列表）转换成一个明确的、无歧-义的字节序列，以便在网络中进行可靠的存储和传输。

RLP的规则非常简单，它只处理两种类型的数据：

1. 字符串（String）：一串字节数据。
2. 列表（List）：一个包含了其他（可以是字符串或列表）数据项的集合。

它的编码规则大致如下（简化版）：

• 对于单个字符串：
  • 如果只有一个字节且在0x00到0x7f之间，编码就是它本身。
  • 如果是0到55字节长的字符串，编码是 0x80 + 长度，后面跟着字符串本身。例如，"dog"会被编码成 [0x83, 'd', 'o', 'g']。
  • 如果是更长的字符串，前缀会更复杂，用多个字节来描述长度。
• 对于一个列表：
  • 如果列表内容的总长度是0到55字节，编码是 0xc0 + 列表总长度，后面跟着列表中每一项被RLP编码后拼接起来的结果。
  • 如果是更长的列表，前缀同样会更复杂。

递归的关键就在于，当编码一个列表时，列表里的每一个成员都必须是已经被RLP编码过的。这就是它如何处理 ['cat', ['dog', 'mouse']] 这种嵌套结构的。在以太坊中，几乎所有需要被哈希、签名或在网络上传输的结构化数据，都预先经过了RLP编码。例如：

• 交易 (Transactions)：一笔交易的所有字段（nonce, gasPrice, to, value, data等）会被组合成一个列表，然后用RLP编码成一串字节数据，最后再对这串数据进行哈希和签名。
• 区块 (Blocks)：整个区块本身就是一个列表，包含了区块头和交易列表，这两部分也都是经过RLP编码的。
• 状态树节点 (MPT Nodes)：我们之前讨论的叶节点、分支节点和扩展节点，在数据库中存储时，它们的内容也是被RLP编码成字节串的。

ETH不使用JSON或XML这样更常见的格式，原因是为了保证：

• 绝对的确定性 (Determinism)
  • 对于任何给定的数据结构，其RLP编码的结果永远是一模一样的，一个字节都不会差。这对于区块链至关重要，因为所有节点都必须对哈希值达成共识。像JSON这样的格式，因为键的顺序或空格等问题，是非确定性的。
• 简洁性与效率 (Simplicity & Efficiency)
  • RLP的规则集非常小，实现起来非常简单，这减少了不同语言开发的客户端（如Geth用Go语言，Besu用Java）之间出现兼容性问题的风险。
  • 它的编码结果也相对紧凑，节省了存储空间和网络带宽。
• 通用性 (Generality)
  • 它可以对任意复杂的、由字节数组和列表组成的数据结构进行编码，这足以满足以太坊内部所有数据结构的需求。