第 12 讲：Merkle Patricia Trie 与状态根

一、需求变了

第 5 讲的 Merkle 树承诺的是一个固定的列表（一个区块里的交易）。现在要承诺的东西不一样：

状态 = 地址 → 账户 的映射
     ⚠️ 它是可变的：每个区块都会修改其中一小部分
     它很大：以太坊有数亿个账户和存储槽

打个比方

第 5 讲那棵 Merkle 树像给一份印好的名单做骑缝章：名单定死了，你只需要证明某一行在里面。

现在的需求变了：这份名单每天都要改几百行，而且有几亿行。你不可能每改几行就重新装订整本、重新盖章。

你需要的是一种活页夹：能按姓名直接翻到某一页、能证明"某人不在这本里"、而且改几页之后只有那几页所在的分支需要重新盖章，其余部分原封不动。

⭐ 下面四条要求，就是把这个"活页夹"说准确：

需求	为什么
① 规范性（canonical）	同一组键值对必须给出同一个根，与插入顺序无关。否则两个诚实节点算出不同的根，共识直接崩溃
② 按键查找 + 存在性证明	轻客户端要问"地址 X 的余额是多少"
③ 不存在性证明	要能证明"地址 Y 根本没有账户"
④ 增量更新	一个区块只改几百个账户，不能重算整棵树

⚠️ 这四条里，第 ① 条最不起眼，也最要命。

“同一组数据必须给出同一个根"听起来像废话——可一旦不成立，后果不是"效率低”，是两个都诚实、都没出错的节点算出不同的根，然后互相认为对方在作恶。共识不是被攻破的，是被一个实现细节自己拆掉的。

这也是为什么下面的结构看起来比"一棵树"复杂得多：大部分复杂度不是为了快，是为了让结果唯一。

为什么普通 Merkle 树不行

❌ 规范性：Merkle 树的根取决于叶子的顺序。
   要让它规范，就得规定"按键排序"。
   ⚠️ 但排序数组的插入是 O(n)——每加一个新账户要移动大量元素。

❌ 按键查找：Merkle 树是数组的承诺，不是映射的承诺。
   给定一个键，你不知道它在第几个位置。

❌ 不存在性证明：需要给出"相邻的两个叶子"（第 5 讲第八节），
   这依赖排序，回到第一个问题。

⭐ 回到那个活页夹：下面这套结构看起来复杂，但它每一处复杂度都对应上面四条里的一条——能按键翻页（②）、能证明某页不存在（③）、改几页只重盖那几页的章（④），而且不管谁来装订、装出来都一模一样（①）。

二、Trie：从"数组"到"路径"

Trie（前缀树） 的思路完全不同：不存位置，按键的内容走路径。

存 "do"、"dog"、"dad" 三个键：

              (根)
             /    \
            d      ...
           / \
          o   a
         /|    \
      (do) g    d
           |     \
         (dog)  (dad)

⭐ 关键性质：树的形状只由键的集合决定，与插入顺序完全无关。 需求 ① 自动满足——这正是 Trie 相对 Merkle 树的根本优势。

需求 ②③④ 也顺带解决了：

② 查找 = 按键的字符逐个往下走
③ 不存在 = 走到某处发现没有对应的分支
④ 更新一个键 = ⭐ 只需重算它那条路径上的节点

Patricia：路径压缩

朴素 Trie 有大量"只有一个孩子"的节点，浪费空间：

压缩前：  d → o → g → (值)      三个节点
压缩后：  "dog" → (值)          一个节点

Patricia trie = 带路径压缩的 Trie。 把单链压成一个节点，存下整段路径。

Merkle 化

最后一步：把节点之间的指针换成子节点内容的哈希（第 4 讲第七节的"哈希指针"）。

⟹ 根哈希承诺了整棵树的全部内容
⟹ 任何一处改动都会传导到根
⟹ ⭐ Merkle Patricia Trie

三、以太坊 MPT 的三种节点

以太坊把键按 4 位（nibble，半字节） 拆开，所以每个分支有 16 路。

① 叶子节点     [ 编码后的剩余路径, 值 ]
② 扩展节点     [ 编码后的共享路径, 子节点的哈希 ]      ← 路径压缩的产物
③ 分支节点     [ v₀, v₁, ..., v₁₅, 值 ]                ← 17 项
                 └─ 16 个子节点哈希 ─┘   └ 键在此终止时的值

⚠️ 分支节点的第 17 项容易被忽略：它用于一个键恰好是另一个键的前缀的情况（比如同时存在 do 和 dog）。

HP 编码：怎么区分叶子和扩展

叶子和扩展节点都是 [路径, 内容] 两项，序列化后长得一样。而且 nibble 数可能是奇数，无法直接按字节存。HP（Hex Prefix）编码用一个前缀 nibble 同时解决这两个问题：

前缀 nibble：
    0  → 扩展节点，路径长度为偶数（后面补一个 0 nibble 对齐）
    1  → 扩展节点，路径长度为奇数
    2  → 叶子节点，路径长度为偶数（补 0）
    3  → 叶子节点，路径长度为奇数

⭐ 最低位表示奇偶，次低位表示是不是叶子

一个具体例子

存三个键值对（用十六进制表示键）：
    a711355 → 45
    a77d337 → 1
    a7f9365 → 2

                    扩展节点  共享前缀 "a7"
                          │
                    ┌─────┴─────┐
                    │  分支节点  │       第 3 个 nibble 分叉
                    └─┬───┬───┬─┘
              nibble=1 │  7│  f│
                       │   │   └──── 叶子 "9365" → 2
                       │   └──────── 叶子 "d337" → 1
                       └──────────── 叶子 "1355" → 45

⭐ 只有 5 个节点就表达了三个键。而根哈希承诺了全部内容。

四、以太坊里的四棵树

树	键	值	根存在哪
世界状态树	`keccak256(地址)`	RLP 编码的账户	区块头 `stateRoot`
账户存储树	`keccak256(槽号)`	槽的值	账户的 `storageRoot`
交易树	`RLP(索引)`	交易	区块头 `transactionsRoot`
收据树	`RLP(索引)`	收据	区块头 `receiptsRoot`

⭐ 注意状态树是"树中有树"：世界状态树的每个叶子是一个账户，而账户里的 storageRoot 又是另一棵树的根。

为什么键要先哈希

这一点常被忽略，但很关键。世界状态树的键是 keccak256(地址)，不是地址本身。原因是防 DoS：

如果直接用地址做键：
   攻击者可以暴力搜索出一大批具有超长公共前缀的地址
   （比如全都以 0x0000000000 开头）
   ⟹ ⚠️ 这些账户会在树里形成一条极深的路径
   ⟹ 访问它们的开销变成 O(深度)，而攻击者可以把深度做得很大
   ⟹ 用固定的 Gas 价格换取了不成比例的计算量

先哈希之后：
   键在 256 位空间里均匀分布，深度期望是 O(log₁₆ N)
   攻击者要构造长公共前缀，就得先找哈希碰撞——不可行

以太坊源码里这种树叫 secure trie，就是这个意思。

⚠️ 代价是丧失了局部性：相邻的地址在树里的位置完全无关。这是第六节那个性能问题的根源。

五、状态根能做什么

有了 stateRoot，一个只有区块头的轻客户端可以：

问："地址 0xabc... 在第 N 块时的余额是多少？"
答：值 + 一条从根到叶子的路径（各节点的兄弟哈希）

⭐ 验证者自己沿路径重算哈希，对上 stateRoot 即可确信答案正确。
   完全不需要信任回答者。

不存在性证明同样自然：

沿路径走到某个分支节点，发现对应的 nibble 位置是空的
⟹ ⭐ 这条路径本身就证明了该键不存在

⭐ 对比第 9 讲：比特币没有状态根，所以做不到这件事。 比特币轻客户端只能验证"某笔交易在某块里"，无法验证"某地址现在有多少钱"。

六、代价：写放大与随机磁盘访问

⚠️ 活页夹不是免费的。改一页要重盖沿途每一层的章——这就是写放大；而"按姓名翻页"意味着你在磁盘上到处跳，这就是随机访问。下面把这两笔代价算出来。

MPT 很优雅，但在工程上它是以太坊全节点最大的性能瓶颈。

写放大

账户数量 N ≈ 数亿
树的深度 ≈ log₁₆(N) ≈ 7–8 层

⟹ 修改一个账户余额，要重写路径上 7–8 个节点
⟹ ⭐ 而每个被重写的节点，哈希都变了，父节点也要跟着重写

一个区块可能修改几百到上千个账户，于是每个区块产生数千次节点写入。

随机访问

第四节说过，键是哈希，所以：

⚠️ 逻辑上相邻的账户，在树里、在磁盘上的位置毫无关系
⟹ 每次状态访问都是一次随机 I/O
⟹ 这就是为什么以太坊全节点强烈推荐 NVMe SSD，机械硬盘根本跑不动

状态膨胀

状态只增不减（第 3 讲）：
   每个新账户、每个新的非零存储槽，都要永久保存在所有全节点上
   ⚠️ 而写入它的人只付了一次性的 Gas

⭐ 这是一个典型的"成本外部化"问题：写入者付一次费用，全网所有节点承担永久成本。缓解方向有三：

① Gas 退款：清空存储槽可以退 Gas（⚠️ 曾被滥用做"Gas 代币"，EIP-3529 已大幅削减）
② 状态过期 / 租金：长期不用的状态被归档，需要时提供证明来"复活"
③ 无状态客户端：干脆不存状态，靠交易自带证明（第 13 讲）

七、Go 实现（简化版）

package mpt

import (
	"bytes"

	"golang.org/x/crypto/sha3"
)

// 节点类型。真实的以太坊 MPT 还要处理 RLP 编码和小节点内联，这里省略。
type node interface{ hash() []byte }

type leafNode struct {
	path  []byte // nibble 序列
	value []byte
}

type extNode struct {
	path  []byte // 共享的 nibble 前缀
	child node
}

type branchNode struct {
	children [16]node
	value    []byte // ⚠️ 键在此终止时的值（例如同时存在 "do" 和 "dog"）
}

func keccak(parts ...[]byte) []byte {
	h := sha3.NewLegacyKeccak256()
	for _, p := range parts {
		h.Write(p)
	}
	return h.Sum(nil)
}

func (n *leafNode) hash() []byte {
	return keccak([]byte{0x02}, hpEncode(n.path, true), n.value)
}

func (n *extNode) hash() []byte {
	return keccak([]byte{0x01}, hpEncode(n.path, false), n.child.hash())
}

func (n *branchNode) hash() []byte {
	parts := [][]byte{{0x00}}
	for _, c := range n.children {
		if c == nil {
			parts = append(parts, make([]byte, 32)) // 空位用全零占位
		} else {
			parts = append(parts, c.hash())
		}
	}
	return keccak(append(parts, n.value)...)
}

// hpEncode 实现 Hex Prefix 编码：
// 前缀 nibble 的最低位表示路径长度奇偶，次低位表示是否叶子。
func hpEncode(path []byte, isLeaf bool) []byte {
	var flag byte
	if isLeaf {
		flag = 2
	}
	var nibbles []byte
	if len(path)%2 == 1 {
		nibbles = append([]byte{flag | 1}, path...) // 奇数：前缀直接跟路径
	} else {
		nibbles = append([]byte{flag, 0}, path...) // 偶数：补一个 0 对齐
	}
	// 两个 nibble 打包成一个字节
	out := make([]byte, len(nibbles)/2)
	for i := range out {
		out[i] = nibbles[2*i]<<4 | nibbles[2*i+1]
	}
	return out
}

// keyToNibbles 把字节键拆成 nibble 序列。
// 以太坊传入的 key 是 keccak256(地址)，不是地址本身——见第四节。
func keyToNibbles(key []byte) []byte {
	out := make([]byte, 0, len(key)*2)
	for _, b := range key {
		out = append(out, b>>4, b&0x0f)
	}
	return out
}

// Get 沿路径查找。返回值和是否存在。
// 走到空位就是不存在性证明的依据。
func Get(n node, path []byte) ([]byte, bool) {
	for {
		switch t := n.(type) {
		case nil:
			return nil, false // 路径走空 ⟹ 键不存在
		case *leafNode:
			if bytes.Equal(t.path, path) {
				return t.value, true
			}
			return nil, false
		case *extNode:
			if len(path) < len(t.path) || !bytes.Equal(path[:len(t.path)], t.path) {
				return nil, false
			}
			n, path = t.child, path[len(t.path):]
		case *branchNode:
			if len(path) == 0 {
				return t.value, t.value != nil
			}
			n, path = t.children[path[0]], path[1:]
		}
	}
}

八、本讲小结

承诺一个可变映射需要四条：规范性、按键查找、不存在性证明、增量更新。⚠️ 普通 Merkle 树四条都不满足。
⭐ Trie 的形状只由键集合决定，与插入顺序无关——规范性自动满足，这是它相对 Merkle 树的根本优势。
Patricia = 路径压缩，把单链节点压成一个；Merkle 化 = 指针换成子节点哈希。
以太坊 MPT 有三种节点：叶子、扩展、17 项的分支。分支的第 17 项用于"一个键是另一个键前缀"的情况。
HP 编码用一个前缀 nibble 同时表达"是不是叶子"和"路径长度奇偶"。
状态树是树中有树：世界状态树的叶子是账户，账户的 storageRoot 又是一棵树的根。
键必须先哈希，否则攻击者可以构造长公共前缀的地址把树做深，用固定 Gas 换取不成比例的计算量。代价是完全丧失局部性。
有了状态根，轻客户端能验证"某地址在某高度的余额"，且不必信任回答者。比特币做不到这件事。
写放大：改一个账户要重写路径上 7–8 个节点，一个区块产生数千次节点写入。
随机磁盘访问是以太坊全节点最大的瓶颈——因为键是哈希，逻辑相邻的账户在磁盘上毫无关联。这是必须用 NVMe 的直接原因。
状态膨胀是成本外部化：写入者付一次 Gas，全网节点承担永久存储。三条缓解路径：Gas 退款、状态过期/租金、无状态客户端。

思考题

为什么"根与插入顺序无关"对共识是必需的？如果不满足会发生什么？
给出三个键 cafe、cab、dog，画出压缩后的 MPT 结构，标出每个节点的类型。
分支节点为什么需要第 17 项？举一个必须用到它的具体例子。
HP 编码里，路径 [1,2,3]（奇数长度）的叶子节点编码成什么字节序列？路径 [1,2,3,4] 呢？
如果以太坊直接用地址而不是 keccak256(地址) 做键，写出一个具体的 DoS 攻击方案，并估算攻击者需要做多少工作。
键哈希化带来了均匀分布，代价是局部性丧失。为什么这会让磁盘 I/O 变成瓶颈？如果按地址排序存储会怎样？
一个区块修改了 500 个账户。估算需要重写多少个 trie 节点。如果树深从 8 变成 10，写入量增加多少？
状态膨胀是"成本外部化"。设计一个状态租金方案，说明它怎么收费、谁付费、以及数据被归档后用户怎么恢复。
为什么"清空存储槽退 Gas"会被滥用成 Gas 代币？EIP-3529 削减退款额度后，这个套利还成立吗？

一、需求变了#

打个比方#

为什么普通 Merkle 树不行#

二、Trie：从"数组"到"路径"#

Patricia：路径压缩#

Merkle 化#

三、以太坊 MPT 的三种节点#

HP 编码：怎么区分叶子和扩展#

一个具体例子#

四、以太坊里的四棵树#

为什么键要先哈希#

五、状态根能做什么#

六、代价：写放大与随机磁盘访问#

写放大#

随机访问#

状态膨胀#

七、Go 实现（简化版）#

八、本讲小结#

思考题#