← COMP5565 全部讲次
L02a-3 · 第 2 周

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」写成一张标签挂在最上面,省两层格子。

分到只剩一封信的格子,就不再往下分了,把剩下的门牌号写在信封上直接放进去。每个格子贴着一张封条,封条上写着格子里所有东西的指纹;最顶上那张总封条,就代表整面架子。

某天只有一封信的内容变了,就只换从这封信到顶上那一路的封条,别的格子原封不动。

类比在哪里失效:

  1. 分拣架每一格固定有 16 个口,对应 0 到 f,不是按字母表分。
  2. 封条是哈希,下层一变上层必变,这是数学保证,不靠邮局员工自觉。
  3. 新区块的树会直接指向上一块没变的节点,现实里的分拣架没法同时属于两天。

从零讲起

1. 先补一块:前缀树(补充)

它解决什么问题

要按 key 查值,又不想一个个比对。前缀树把 key 拆成字符,一层走一个字符,走到底就找到了。开头相同的 key 共用前面那段路,不用重复存。

从哪来(补充)

PATRICIA 这个词出自 Donald R. Morrison 1968 年的论文,指一种把只有一条出路的单链路径压缩起来的前缀树,今天常叫 radix tree。以太坊 MPT 里的扩展节点做的就是这种压缩。

出处:Wikipedia: Radix tree

直觉

像查字典:先翻到 t 开头的那一部分,再找 te,再找 ten。to、tea、ten 都在 t 那一部分,开头这一步大家共用。

一步一步看

目标:沿前缀树从根走到 ten,看共用前缀的 key 怎样共享路径,查找步数只看 key 的长度。

  1. 根节点下按第一个字母分两支:t 和 i。

  2. t 下面再按第二个字母分:o 走到 to,e 走到 te。

  3. te 下面按第三个字母分:a 是 tea,n 是 ten。

  4. 查 ten 就是沿 t → e → n 走三步,跟表里有多少个词无关。

    前缀树示意:根下分 t 和 i 两支;t 下有 to 和 te,te 下有 tea 和 ten;i 下有 in,再到 inn;青绿高亮从根经 t、te 到 ten 的查找路径,说明一个字母走一格

怎么判断

查找要走几步,看 key 有几个字符,不看树里一共有多少 key。共用开头的 key,在树里分叉之前走的是同一段路。

常见误解

以为前缀树和 Merkle 树是一回事

前缀树管「按 key 找到位置」,Merkle 树管「用一个哈希代表所有数据」。MPT 把两样合在一起:结构按前缀树分叉,每个节点又像 Merkle 树一样算哈希。

试一下

往上面那棵树里加一个词 tee,要新建几个节点?

1 个。t → e 这段已经有了,只要在 te 下面加一条 e 边,挂一个 tee 节点。

2. MPT 的三类节点和 prefix

它解决什么问题

地址有 40 个十六进制字符,一个字符一层的话树太深。MPT 用扩展节点把公共前缀压成一层,用叶子节点把剩下的尾巴一次存完,只在真正分叉的地方放分支节点。每个节点都算哈希,根的哈希就代表整张表。

直觉

三类节点各管一件事。扩展节点说「这一段大家都一样,直接跳过」;分支节点说「下一个字符是几就走第几号口」;叶子节点说「后面只剩你一个了,剩下的门牌号和余额都在这」。

一步一步看

目标:把四个简化地址放进 MPT,看扩展、分支、叶子三类节点各出现在哪,prefix 又标了什么。

  1. 课件把地址简化成 7 个十六进制字符,四个账户都以 a7 开头,所以根是扩展节点 a7。
  2. 根下面是分支节点,有 16 个槽(0 到 f)。按第三个字符选槽:Alice 走槽 1,Charlie 走槽 f,Bob 和 Dorothy 都走槽 7。
  3. 槽 1 和槽 f 下面都只剩一个账户,直接挂叶子,叶子里存剩下的 key-end 和余额。
  4. 槽 7 下面的两个账户又共享 d3,于是再接一个扩展节点 d3 和一个分支节点,两人分别走槽 3 和槽 9。
Merkle Patricia Trie 的分层结构:根部是 Extension 节点 a7,往下进 Branch 节点走第 7 号槽,再经 Extension 节点 d3、Branch 节点第 9 号槽,最后落到 key-end 为 7、value 为 0.12 ETH 的 Leaf 节点;图右侧还列着 prefix 取值 0、1、2、3 的含义和简化版世界状态表
图片来源:COMP5565 Lecture2.pdf, p.32
  1. 每个扩展节点和叶子节点开头都有一个 prefix,同时说明节点类型和 nibble 个数的奇偶。
prefix 节点类型 nibble 个数
0 扩展 偶数
1□ 扩展 奇数(□ 是补上的那一位)
2 叶子 偶数
3□ 叶子 奇数
  1. 整棵树的根节点过一次 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。

  1. 转账前的树:四个账户挂在扩展 a7 下的分支上。

    MPT 状态更新第 1 帧:根是扩展节点 a7,下接分支;槽 1 叶 1355 是 45 ETH,槽 7 接扩展 d3 再接分支,其下槽 3 叶 7 是 1 WEI、槽 9 叶 7 是 Dorothy 的 0.12 ETH,槽 f 是 Charlie 的叶 9365、1.1 ETH;底部说明完整地址等于扩展前缀加槽号加 key-end

  2. Dorothy 的余额变成 0.11 ETH。她的叶子变了,往上 d3 下的分支、扩展 d3、根分支、根扩展,整条路的哈希都要重算。

    MPT 状态更新第 2 帧:Dorothy 的叶子余额从 0.12 ETH 改成 0.11 ETH,从这片叶子经分支、扩展 d3、根分支到根扩展 a7 的整条路径用青绿高亮,没被碰到的三片叶子哈希不变

  3. Emily 的地址 a7ff377 和 Charlie 的 a7f9365 共享 a7f。原来槽 f 上 Charlie 的叶子裂开,换成一个新分支:槽 9 挂 Charlie,key-end 缩成 365;槽 f 挂 Emily,key-end 是 377。

    MPT 状态更新第 3 帧:根分支的槽 f 原来挂着 Charlie 的叶子,现在改成指向一个新分支,新分支的槽 9 挂 Charlie 的叶 365、1.1 ETH,槽 f 挂 Emily 的叶 377、0.01 ETH,新分支和 Emily 用青绿高亮

  4. 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 是执行前的状态。

必背

  1. State Root = 所有账户构成的树(跨区块累积的状态快照);Transaction Root = 本区块内所有交易构成的树(一次性)
  2. stateRoot 是所有交易执行完之后的状态根,由根节点过一次 keccak256 得到
  3. MPT 三类节点:Extension(压公共前缀)/ Branch(16 槽按 nibble 选路)/ Leaf(key-end + value)
  4. prefix 编码 = 节点类型 + nibble 奇偶:0 偶扩展、1□ 奇扩展、2 偶叶子、3□ 奇叶子;存在的理由是奇数个 nibble 无法字节对齐
  5. 沿路径把 shared nibbles + branch 槽号 + key-end 拼起来 = 完整的 key
  6. 状态更新时只重写从被改叶子到根的路径,其余子树跨区块共享;新 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,再找它们的公共前缀。

解答
  1. 四个 key 都以 a7 开头,所以根是扩展节点,共享前缀 a7,2 个 nibble 偶数,prefix 0。
  2. 分支节点按下一个 nibble 选槽:a711355 走槽 1,剩下 1355 直接成叶子,4 个 nibble 偶数,prefix 2。
  3. a7f9365 走槽 f,剩下 9365 成叶子,prefix 2。
  4. a77d337 和 a77d397 都走槽 7,又共享 d3,于是先接一个扩展节点 d3(prefix 0),再接一个分支节点。
  5. 这个分支里 a77d337 走槽 3、a77d397 走槽 9,各剩一个 nibble 7 成叶子,1 个 nibble 奇数,prefix 3□。
  6. 整棵树的根节点过一次 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 直接沿用的?

  1. 先定位问号:那个叶子在扩展 d3 下面分支节点的槽 9,也就是 Dorothy 的位置。
  2. 填 key-end:Dorothy 的 key 是 a77d397,路径 a7 → 槽 7 → d3 → 槽 9,剩下的就是 7。
  3. 填 value:0.12 − 0.01 = 0.11 ETH。所以两个问号是 key-end 7、value 0.11 ETH。
  4. 插入 Emily:a7ff377 和 Charlie 的 a7f9365 共享前缀 a7f。#654 里根分支的槽 f 直接挂着 Charlie 的叶子(key-end 9365)。
  5. 原叶子裂开:槽 f 改成指向一个新的分支节点。新分支的槽 9 挂 Charlie,key-end 缩短为 365,1.1 ETH;槽 f 挂 Emily,key-end 377,0.01 ETH。
  6. 沿用的节点:Alice 的叶子和 Bob 的叶子没变,#655 的树直接用长箭头指回 #654 的这些节点。被重写的只有 Dorothy 的叶子、Charlie 和 Emily 那一支,以及它们通往根的路径。
  7. 为什么 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□;④ 重写范围只到这一支和根。

  1. 根扩展 a7 之后,Frank 的下一个 nibble 是 1,走根分支的槽 1,和 Alice 同一个槽。
  2. 原来槽 1 直接挂着 Alice 的叶子(key-end 1355)。现在槽 1 改成指向一个新的分支节点。
  3. 新分支按下一个 nibble 选槽:Alice 剩 1355,走槽 1,key-end 缩短为 355;Frank 剩 3377,走槽 3,key-end 为 377。
  4. 355 和 377 都是 3 个 nibble,奇数加叶子,prefix 都是 3□。
  5. 要重写的是新分支、两个新叶子、根分支(槽 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。

下一讲 →
L02a-4 L02a-4 Gas 与 EIP-1559:一笔交易的手续费怎么算、钱去了哪

个人整理的学习笔记,不是官方材料;数字与结论以课件和讲师为准。