L02a-3 状态树 MPT:所有账户怎么压成一个 stateRoot
从前缀树讲起,认识 Merkle Patricia Trie 的三类节点和 prefix 编码,沿路径拼出地址,再看一笔转账只重写哪一条路径。
一句话版
世界状态这张大表被组织成一棵按地址逐个字符分叉的哈希树,叫 Merkle Patricia Trie。树根的哈希就是区块头里的 stateRoot;改一个账户,只需重写从它到根的那一条路。
前一页 L02a-2 讲了账户里存什么。Merkle 树的基础在 C01b。下一页 L02a-4 讲每笔交易要付多少 gas。
先认识这几个词
| 词 | 全称 / 读法 | 一句人话 |
|---|---|---|
| 前缀树 | trie,读「tree」或「try」 | 按字符一层层分叉的树,开头相同的词共用一段路 |
| MPT | Merkle Patricia Trie | 以太坊的状态树:前缀树加上每个节点都算哈希 |
| nibble | 半字节 | 4 bit,也就是一个十六进制字符 |
| Extension | 扩展节点 | 把一段公共前缀压成一个节点 |
| Branch | 分支节点 | 16 个槽,按下一个 nibble 选路 |
| Leaf | 叶子节点 | 存地址剩下没走完的部分(key-end)和值 |
| stateRoot | 状态根 | 整棵状态树根节点的哈希,放进区块头 |
一个类比:按门牌号逐位分拣的信件架
邮局有一面分拣架。地址按字符一位一位分:第一位是 a 的放左边,第二位是 7 的再往下一格。所有地址都以 a7 开头,那就干脆把「a7」写成一张标签挂在最上面,省两层格子。
分到只剩一封信的格子,就不再往下分了,把剩下的门牌号写在信封上直接放进去。每个格子贴着一张封条,封条上写着格子里所有东西的指纹;最顶上那张总封条,就代表整面架子。
某天只有一封信的内容变了,就只换从这封信到顶上那一路的封条,别的格子原封不动。
类比在哪里失效:
- 分拣架每一格固定有 16 个口,对应 0 到 f,不是按字母表分。
- 封条是哈希,下层一变上层必变,这是数学保证,不靠邮局员工自觉。
- 新区块的树会直接指向上一块没变的节点,现实里的分拣架没法同时属于两天。
从零讲起
1. 先补一块:前缀树(补充)
它解决什么问题
要按 key 查值,又不想一个个比对。前缀树把 key 拆成字符,一层走一个字符,走到底就找到了。开头相同的 key 共用前面那段路,不用重复存。
从哪来(补充)
PATRICIA 这个词出自 Donald R. Morrison 1968 年的论文,指一种把只有一条出路的单链路径压缩起来的前缀树,今天常叫 radix tree。以太坊 MPT 里的扩展节点做的就是这种压缩。
直觉
像查字典:先翻到 t 开头的那一部分,再找 te,再找 ten。to、tea、ten 都在 t 那一部分,开头这一步大家共用。
一步一步看
目标:沿前缀树从根走到 ten,看共用前缀的 key 怎样共享路径,查找步数只看 key 的长度。
-
根节点下按第一个字母分两支:t 和 i。
-
t 下面再按第二个字母分:o 走到 to,e 走到 te。
-
te 下面按第三个字母分:a 是 tea,n 是 ten。
-
查 ten 就是沿 t → e → n 走三步,跟表里有多少个词无关。
怎么判断
查找要走几步,看 key 有几个字符,不看树里一共有多少 key。共用开头的 key,在树里分叉之前走的是同一段路。
常见误解
以为前缀树和 Merkle 树是一回事
前缀树管「按 key 找到位置」,Merkle 树管「用一个哈希代表所有数据」。MPT 把两样合在一起:结构按前缀树分叉,每个节点又像 Merkle 树一样算哈希。
试一下
往上面那棵树里加一个词 tee,要新建几个节点?
1 个。t → e 这段已经有了,只要在 te 下面加一条 e 边,挂一个 tee 节点。
2. MPT 的三类节点和 prefix
它解决什么问题
地址有 40 个十六进制字符,一个字符一层的话树太深。MPT 用扩展节点把公共前缀压成一层,用叶子节点把剩下的尾巴一次存完,只在真正分叉的地方放分支节点。每个节点都算哈希,根的哈希就代表整张表。
直觉
三类节点各管一件事。扩展节点说「这一段大家都一样,直接跳过」;分支节点说「下一个字符是几就走第几号口」;叶子节点说「后面只剩你一个了,剩下的门牌号和余额都在这」。
一步一步看
目标:把四个简化地址放进 MPT,看扩展、分支、叶子三类节点各出现在哪,prefix 又标了什么。
- 课件把地址简化成 7 个十六进制字符,四个账户都以
a7开头,所以根是扩展节点a7。 - 根下面是分支节点,有 16 个槽(0 到 f)。按第三个字符选槽:Alice 走槽 1,Charlie 走槽 f,Bob 和 Dorothy 都走槽 7。
- 槽 1 和槽 f 下面都只剩一个账户,直接挂叶子,叶子里存剩下的 key-end 和余额。
- 槽 7 下面的两个账户又共享
d3,于是再接一个扩展节点d3和一个分支节点,两人分别走槽 3 和槽 9。
- 每个扩展节点和叶子节点开头都有一个 prefix,同时说明节点类型和 nibble 个数的奇偶。
| prefix | 节点类型 | nibble 个数 |
|---|---|---|
0 |
扩展 | 偶数 |
1□ |
扩展 | 奇数(□ 是补上的那一位) |
2 |
叶子 | 偶数 |
3□ |
叶子 | 奇数 |
- 整棵树的根节点过一次 Keccak-256,就是区块头里的 stateRoot。
怎么判断
拼 key:把路上的扩展前缀、分支槽号、叶子的 key-end 按顺序连起来。判 prefix:先看是扩展还是叶子,再数 nibble 个数是奇是偶。
为什么要有 prefix:存储按字节走,一个 nibble 只有半个字节,奇数个 nibble 凑不成整字节,前面得补一位;补过之后要让读的人知道,就把类型和奇偶一起编进 prefix。
常见误解
以为 stateRoot 是区块执行之前的状态
stateRoot 是这个区块里全部交易执行完之后的状态根。根变了说明状态变了。
把 State Root 和 Transaction Root 混为一谈
State Root 是所有账户构成的树,描述「现在是什么样」,跨区块累积。Transaction Root 是本区块内所有交易构成的树,描述「这一块发生了什么」,每块一棵、互不相干。
试一下
一个叶子的 key-end 是 365,它的 prefix 是什么?
3□。叶子,3 个 nibble,奇数。
3. 状态更新:只重写一条路径
它解决什么问题
每个区块都要有自己的 stateRoot。如果每块都重建整棵树,存储会爆炸。MPT 让新区块只重写变了的那几个节点,其余节点直接指回上一块。
直觉
改了一片叶子,它的哈希变了;它的父节点里存着这个哈希,父节点也变了;一路往上到根。没被改到的分支,哈希一个都不变,可以原样拿来用。
一步一步看
目标:跟着 Dorothy 给 Emily 转账,看新区块只重写哪条路径、Charlie 的叶子怎样裂开、哪些节点直接复用。
下面三帧接着课件的例子:区块 #654 之后,Dorothy 给新账户 Emily 转 0.01 ETH。
-
转账前的树:四个账户挂在扩展
a7下的分支上。 -
Dorothy 的余额变成 0.11 ETH。她的叶子变了,往上
d3下的分支、扩展d3、根分支、根扩展,整条路的哈希都要重算。 -
Emily 的地址
a7ff377和 Charlie 的a7f9365共享a7f。原来槽 f 上 Charlie 的叶子裂开,换成一个新分支:槽 9 挂 Charlie,key-end 缩成365;槽 f 挂 Emily,key-end 是377。 -
Alice 和 Bob 的叶子一个字节都没变,新区块的树直接指回上一块的这两个节点。
怎么判断
问「哪些节点要重写」:从每个被改的叶子往上画到根,路上的全要重写;不在任何一条这种路上的节点原样沿用。问「新账户插进来会怎样」:看它和已有 key 共享多长前缀,共享到哪一层,那一层原来的叶子就要裂开。
常见误解
以为每个区块都要重建整棵状态树
只重写被改叶子到根的那条路径,其余子树跨区块共享。这是每块都能有独立 stateRoot 又不让存储爆炸的原因。
试一下
如果这一块只有 Alice 的余额变了,要重写几个节点?
3 个:Alice 的叶子、根分支、根扩展 a7。d3 那一支和 Charlie 的叶子都不动。
把它们串起来
前缀树负责「按地址找到位置」,Merkle 哈希负责「用一个根代表全部」,MPT 把两者合成一棵树。三类节点里,扩展压前缀、分支选路、叶子收尾;prefix 让读的人知道节点类型和有没有补位。
这样一来,区块头里只需要放一个 32 字节的 stateRoot。轻节点拿着区块头和一条从叶子到根的路径,就能核对某个账户此刻的状态,这正是 C01b 里 Merkle 证明的用法。状态变一点,树只改一条路,新旧区块共用其余节点。
推动状态变化的是交易,交易要付 gas,下一页讲这笔钱怎么算。
课件里的坑
- [过时内容] p.26 是合并之前的区块头,difficulty、mixHash、nonce、ommers 这些挖矿字段现在已经没有了;现在的区块头看 p.27,多了 Base fee,Miner 改叫 Fee recipient(p.26)
- [概念区分] stateRoot 的说明写的是「after all transactions are executed and finalisations applied」,是执行之后的状态(p.32)
- [考点提示] p.33 的两个问号是课堂练习,答案不在图上,要按路径自己推(p.33)
- [概念区分] State Root 和 Transaction Root 叶子的内容完全不同:前者是账户状态,后者是交易本身(p.29)
课后 10 分钟:考点复习
这 10 分钟怎么用:合上页面,先默写三类节点各存什么、prefix 四种取值;再沿 p.32 的树拼出四个地址;然后做 p.33 的两个问号和下面的变式题;最后回查两个最容易错的地方:以为每块重建整棵树、以为 stateRoot 是执行前的状态。
必背
- State Root = 所有账户构成的树(跨区块累积的状态快照);Transaction Root = 本区块内所有交易构成的树(一次性)
- stateRoot 是所有交易执行完之后的状态根,由根节点过一次 keccak256 得到
- MPT 三类节点:Extension(压公共前缀)/ Branch(16 槽按 nibble 选路)/ Leaf(key-end + value)
- prefix 编码 = 节点类型 + nibble 奇偶:0 偶扩展、1□ 奇扩展、2 偶叶子、3□ 奇叶子;存在的理由是奇数个 nibble 无法字节对齐
- 沿路径把 shared nibbles + branch 槽号 + key-end 拼起来 = 完整的 key
- 状态更新时只重写从被改叶子到根的路径,其余子树跨区块共享;新 key 与已有 key 共享更长前缀时,原叶子裂成分支加两个更短的叶子
课件例题
例 1(课件 p.32):沿 MPT 的路径拼出四个 key
题面:简化的世界状态有四个账户:a711355 45.0 ETH、a77d337 1.00 WEI、a7f9365 1.1 ETH、a77d397 0.12 ETH。图上根节点是扩展节点 a7,下面是一个分支节点。写出每个账户从根到叶子的路径,并说明每个节点的 prefix。
提示
先找四个 key 的公共前缀,那就是根扩展节点。接着按第三个字符分到分支的槽里;某个槽下如果还有两个 key,再找它们的公共前缀。
解答
- 四个 key 都以
a7开头,所以根是扩展节点,共享前缀a7,2 个 nibble 偶数,prefix0。 - 分支节点按下一个 nibble 选槽:
a711355走槽1,剩下1355直接成叶子,4 个 nibble 偶数,prefix2。 a7f9365走槽f,剩下9365成叶子,prefix2。a77d337和a77d397都走槽7,又共享d3,于是先接一个扩展节点d3(prefix0),再接一个分支节点。- 这个分支里
a77d337走槽3、a77d397走槽9,各剩一个 nibble7成叶子,1 个 nibble 奇数,prefix3□。 - 整棵树的根节点过一次 keccak256,就是区块头里的 stateRoot,而且是交易全部执行完之后的状态。
例 2(课件 p.33):课堂练习,Dorothy 给 Emily 转 0.01 ETH 后两个问号填什么
见下方完整例题。
完整例题
题面(课件 p.33):区块 #654 的 stateRoot 是 5fd136972a,账户为 Alice(a711355)45 ETH、Bob(a77d337)1 WEI、Charlie(a7f9365)1.1 ETH、Dorothy(a77d397)0.12 ETH。随后发生一笔交易:Dorothy 给 Emily 转 0.01 ETH,Emily 是新账户,key 为 a7ff377。区块 #655 的 stateRoot 变成 833bc229db。图上有一个叶子的 key-end 和 value 打着两个问号。(1)填出两个问号。(2)Emily 的新叶子挂在哪里?(3)#655 的树里哪些节点是从 #654 直接沿用的?
- 先定位问号:那个叶子在扩展
d3下面分支节点的槽9,也就是 Dorothy 的位置。 - 填 key-end:Dorothy 的 key 是
a77d397,路径a7→ 槽7→d3→ 槽9,剩下的就是7。 - 填 value:0.12 − 0.01 = 0.11 ETH。所以两个问号是 key-end
7、value0.11 ETH。 - 插入 Emily:
a7ff377和 Charlie 的a7f9365共享前缀a7f。#654 里根分支的槽f直接挂着 Charlie 的叶子(key-end9365)。 - 原叶子裂开:槽
f改成指向一个新的分支节点。新分支的槽9挂 Charlie,key-end 缩短为365,1.1 ETH;槽f挂 Emily,key-end377,0.01 ETH。 - 沿用的节点:Alice 的叶子和 Bob 的叶子没变,#655 的树直接用长箭头指回 #654 的这些节点。被重写的只有 Dorothy 的叶子、Charlie 和 Emily 那一支,以及它们通往根的路径。
- 为什么 stateRoot 变了:路径上的节点内容变了,哈希一路向上变,根自然不同,
5fd136972a变成833bc229db。
变式题(先自己做)
自编情境:接着上题的 #655 状态,再来一个新账户 Frank,key 为 a713377,收到 0.5 ETH。问:(1)Frank 的路径从根出发先走分支的哪个槽?(2)Alice 的叶子会发生什么变化?(3)新出现的叶子 prefix 各是什么?(4)哪些节点要重写?
提示
先把 Frank 的 key 和 Alice 的 a711355 逐个 nibble 对齐,找到第一个不同的位置。共享的前缀越长,原叶子要裂到越深。
判分点与答案(非官方评分标准)
判分点:① 两个 key 共享 a71,所以在槽 1 处分叉;② Alice 的叶子裂成新分支下的一个更短叶子;③ 叶子剩 3 个 nibble,奇数,prefix 是 3□;④ 重写范围只到这一支和根。
- 根扩展
a7之后,Frank 的下一个 nibble 是1,走根分支的槽1,和 Alice 同一个槽。 - 原来槽
1直接挂着 Alice 的叶子(key-end1355)。现在槽1改成指向一个新的分支节点。 - 新分支按下一个 nibble 选槽:Alice 剩
1355,走槽1,key-end 缩短为355;Frank 剩3377,走槽3,key-end 为377。 355和377都是 3 个 nibble,奇数加叶子,prefix 都是3□。- 要重写的是新分支、两个新叶子、根分支(槽
1的指针变了)和根扩展节点。Bob、Dorothy 所在的d3子树和 Charlie、Emily 所在的槽f子树原样沿用。
闪卡自测
1. State Root 和 Transaction Root 分别是哪棵树的根?哪个跨区块累积?
State Root 是所有账户构成的树,覆盖全链当前状态,跨区块累积;Transaction Root 是本区块内所有交易构成的树,每块各有一棵、互不相干。前者是状态快照,后者是操作清单(p.29)。
2. MPT 里 key-end 为 1355 的叶子 prefix 是 2,key-end 为 7 的却是 3□,为什么?
prefix 同时编码节点类型和 nibble 个数的奇偶:0 偶扩展、1□ 奇扩展、2 偶叶子、3□ 奇叶子。1355 是 4 个 nibble(偶)加叶子 → 2;7 是 1 个(奇)加叶子 → 3□。存在的理由是奇数个 nibble 无法按字节对齐,补一位后必须让读的人知道补过(p.32)。
3. 分支节点有几个槽?按什么选?
16 个槽(0 到 f)加一个 value 槽,按 key 的下一个 nibble 选(p.32)。
4. 把 stateRoot 放进区块头有什么好处?
一个 32 字节的哈希就能验证全网状态的完整性;节点同步时也可以只同步根和需要的分支,不必下载全部账户(p.30)。
5. 只看区块头里的 Transaction Root,能做什么?
拿区块头加一条 Merkle 证明,就能确认某笔交易确实在这个区块里,不必下载整棵交易树(p.34)。
6. 新账户插入时,原有叶子什么时候会裂开?
新 key 和某个已有叶子的 key 共享更长前缀时,那个叶子会裂成一个分支加两个更短的叶子(p.33)。
下一讲
状态怎么存讲完了,接下来看改状态要花多少钱:gas 怎么计、base fee 和小费各归谁、交易失败了钱还退不退。见 L02a-4。
个人整理的学习笔记,不是官方材料;数字与结论以课件和讲师为准。