罗罗编程学习记录 全栈面试题库
本页导航 展开查看

15.1.1 区块链结构与 Merkle 树

所属:全栈开发面试题库 / 15 Web3 与区块链 / 15.1 区块链基础与密码学

本节要解决的问题

很多人能背出"区块头指向前一个区块头",但一到细节就露馅:区块头到底有几个字段、各自多大;Merkle 树证明一笔交易存在时要给轻节点几个哈希;以太坊为什么不用比特币那种二叉 Merkle 树,而要搞出 Merkle Patricia Trie(MPT)。本节解决四个具体问题:一是把区块头、交易列表、状态根这三层结构讲清,让你能在白板上画出区块字节布局;二是分清比特币 Merkle 树与以太坊 MPT 的设计动机差异(无状态 vs 有状态、静态列表 vs 键值集合);三是讲清状态根、交易根、收据根三个根各自证明什么,为什么三棵树都要挂在区块头上;四是解释轻节点怎么只用几个哈希就验证"某笔交易在区块里"以及"某个账户在某高度的余额",这是 SPV 与无状态客户端的理论基础。

学习目标

学完本节,你应当能够:

  • 写出以太坊区块头的核心字段(parentHash、ommersHash、stateRoot、transactionsRoot、receiptsRoot、number、timestamp、difficulty/gasLimit/gasUsed、baseFeePerGas 等)并说明各自用途。
  • 用 4 笔交易手算一次 Merkle 根,并画出 SPV 验证所需的哈希路径。
  • 说清 MPT 的分支节点、扩展节点、叶节点三种结构,以及为什么它比普通哈希表更适合作为状态数据库的索引。
  • 区分"交易存在性证明"与"状态正确性证明",并解释为什么后者需要 MPT 而不是普通 Merkle 树。

先修与前置

知识地图

区块 (Block)
├── 区块头 (Header)
│   ├── parentHash        : 父区块头的 Keccak-256
│   ├── ommersHash       : 叔块列表的哈希(PoW 时代保留)
│   ├── stateRoot        : 执行完本块所有交易后的状态 MPT 根
│   ├── transactionsRoot : 本块交易列表的 MPT 根
│   ├── receiptsRoot     : 本块收据(含日志)的 MPT 根
│   ├── number / gasLimit / gasUsed / timestamp
│   └── baseFeePerGas    : EIP-1559 引入
├── 叔块列表 (ommers)      : 仅 PoW 时代有效
└── 交易列表 (transactions): RLP 编码数组

MPT 三棵树:
  stateTrie   : address → Account{nonce, balance, storageRoot, codeHash}
  storageTrie : address 内部的 key → value
  txTrie      : txIndex → Transaction(静态列表按序)
  receiptTrie : txIndex → Receipt{status, cumulativeGasUsed, logsBloom, logs}

核心术语

  • 区块头(Block Header):约 500 字节左右的元数据块,是区块链真正"链接"的对象;交易列表本身不参与父哈希。
  • 哈希指针(Hash Pointer):既指向数据位置又携带数据哈希的引用,篡改任意历史字节都会导致后续所有哈希失效。
  • Merkle 根(Merkle Root):对叶子列表逐层两两哈希得到的根哈希,可用来证明某个元素在列表中。
  • Merkle Patricia Trie(MPT):以太坊使用的一种带压缩前缀的 Merkle 三叉树,键为任意长度十六进制串,值任意。
  • RLP(Recursive Length Prefix):以太坊的二进制编码格式,用于序列化交易、区块、账户对象。
  • 状态根(State Root):执行完区块所有交易后,全局状态树的根哈希;客户端之间用它就状态达成一致。
  • 收据(Receipt):每笔交易执行后的结果(状态码、累计 Gas、日志),交易成功与否不能只看交易本身。
  • SPV(Simplified Payment Verification):轻节点不下载全区块,只验证区块头 + Merkle 证明。

覆盖范围

  • 区块头字段布局与三个根的职责
  • 比特币二叉 Merkle 树结构、空洞(duplicate node)处理与 SPV 证明
  • 以太坊 MPT 的分支/扩展/叶节点、hex-prefix 编码与节点哈希
  • 状态树、存储树、交易树、收据树的索引方式
  • 区块重组与状态回滚对 MPT 历史键的要求

高频题速览

编号 题目 难度 频率
15.1.1-001 一个区块由哪几部分组成?区块头有哪些核心字段? 基础 ★★★★★
15.1.1-002 什么是哈希指针?为什么区块链用哈希链接而不是普通指针? 基础 ★★★★
15.1.1-003 普通 Merkle 树怎么证明一笔交易在区块里? 基础 ★★★★★
15.1.1-004 比特币 Merkle 树与以太坊 MPT 有什么本质区别? 进阶 ★★★★
15.1.1-005 stateRoot、transactionsRoot、receiptsRoot 三个根各自证明什么? 进阶 ★★★★
15.1.1-006 MPT 的分支、扩展、叶节点怎么协同工作? 进阶 ★★★★
15.1.1-007 SPV 轻节点怎么不下载全区块就验证一笔交易? 进阶 ★★★
15.1.1-008 MPT 为什么能支持任意键的插入、删除与读取? 高级 ★★★
15.1.1-009 区块重组时状态怎么回滚?为什么需要历史键与快照? 高级 ★★★
15.1.1-010 为什么要做无状态客户端(stateless client)与见证数据? 高级 ★★★

15.1.1-001 一个区块由哪几部分组成?区块头有哪些核心字段?

一句话结论

一个区块由区块头(Header)、叔块列表(ommers,PoW 时代保留字段)和交易列表三部分组成;区块头才是链真正链接的对象,其核心字段包括父哈希、三个 Merkle 根(状态/交易/收据)、块高、时间戳、Gas 上限与用量、基础费用等,约数百字节。

概念解释

  • 区块头:约 500 字节,是节点间同步与共识的最小单位。
  • 交易列表:RLP 编码的数组,体积远大于头部(主网常见 100–约 1.5 MB 量级,随 EIP-4844 与 blob 扩展变化)。
  • 叔块(ommer/uncle):PoW 时代让差一点胜出的矿工也能分到奖励,合并后已无实际意义,但字段仍在头部。
  • 三个根:分别对状态、交易、收据三棵树取根,使轻节点只信任头部即可验证任意子项。

原理流程

  1. 矿工/提议者收集交易,按规则排序后执行。
  2. 执行后得到新状态、每笔交易的收据,分别写入三棵 MPT。
  3. 把三棵树的根、父块哈希、本块元数据(高度、时间戳、Gas)RLP 编码成区块头。
  4. 对区块头做共识运算(PoW 解谜题 / PoS 签名),广播整个区块。
  5. 验证者收到后先验头部共识,再独立执行交易并比较 stateRoot 是否一致。

代码或图示

以太坊区块头字段(合并后常见字段,按 RLP 顺序):
  parentHash      H32   父区块头 Keccak-256
  ommersHash      H32   叔块列表 Keccak-256(合并后通常为空列表哈希)
  beneficiary     H20   区块奖励接收者(PoW 时代的矿工)
  stateRoot       H32   全局状态 MPT 根
  transactionsRoot H32  交易树 MPT 根
  receiptsRoot    H32   收据树 MPT 根
  logsBloom       H256  本块所有日志 bloom 过滤器
  difficulty      U256  PoW 难度(合并后固定为 0 或终端难度)
  number          U256  块高
  gasLimit        U256
  gasUsed         U256
  timestamp       U256
  extraData       0-32B
  mixHash         H32   PoW 工作量证明(合并后为随机数)
  nonce           H64   PoW 随机数(合并后为 0)
  baseFeePerGas   U256  EIP-1559 引入(伦敦硬分叉)

常见误区

  • 误区:区块 = 一堆交易;正解:链上链接的是区块头,交易只是头部挂载的数据体。
  • 误区:stateRoot 包含所有交易;正解:stateRoot 是"执行完这些交易后的状态",不包含交易本身,交易由 transactionsRoot 单独证明。
  • 误区:叔块现在还在用;正解:合并后叔块机制已废弃,字段只是历史兼容。

追问

  • 为什么区块头不直接包含交易列表哈希?答:因为以太坊用 MPT 而不是简单列表哈希,transactionsRoot 本身就是交易列表的 Merkle 根,已经承担了"列表完整且未被替换"的证明。机制上任何一笔交易被替换,transactionsRoot 都会变,节点拒绝。边界在于:MPT 树按交易序号索引,重排交易顺序不会改变根,所以排序合法性要靠执行结果与共识规则保证。延伸:这也是 MEV 与交易排序问题的根源。
  • 节点收到新区块先验什么?答:先验头部共识(签名/PoW)与父链连续性,再验 Gas 与时间戳,最后才执行交易。机制上头部验证便宜(几百字节),执行昂贵(可能要跑几千笔交易),顺序颠倒会被 DoS。边界在于:如果父块不在本地,要先回溯同步父块,这是同步算法的入口。延伸:轻节点只做到头部验证就停了。
  • logsBloom 为什么放在头部?答:它是本块所有日志 topic/地址的 2048 位 bloom 过滤器,让轻客户端不用下载收据就能粗筛"这块是否有我关心的事件"。机制上每个日志把地址和 topic 各取 3 个哈希位置 1。边界在于 bloom 有假阳性,命中后仍要下载收据确认。延伸:这也是事件索引服务(The Graph 类)必须全节点扫块的原因。

15.1.1-002 什么是哈希指针?为什么区块链用哈希链接而不是普通指针?

一句话结论

哈希指针 = 指向数据的位置引用 + 数据本身的密码学哈希;区块链用它把区块按"前一个区块头哈希"串起来,篡改任意历史字节会让从该处起的所有后续哈希全部失配,从而形成不可由单节点单方修改的链式结构。

概念解释

  • 普通指针:只给地址,内容被改了指针不感知。
  • 哈希指针:内容一旦变化,哈希就变化,链接自动断裂。
  • 密码学哈希:单向、抗碰撞、抗原像,任意改动 avalanche 到完全不同的哈希。
  • 链式结构:每个块的 parentHash 指向前一块头,篡改旧块会引发连锁失配。

原理流程

  1. 节点计算某个历史区块头 H 的 Keccak-256,记为 h。
  2. 下一个区块的 parentHash 字段填入 h。
  3. 任何人修改 H 的哪怕 1 字节,重算得到 h' ≠ h,后续所有块的 parentHash 全部不匹配。
  4. 攻击者要让篡改生效,必须从被改块起重新计算之后所有区块,并且在 PoW/PoS 网络上比诚实链更快。
  5. 网络越长、共识越分散,重写历史的代价越高,这就是区块链不可篡改性的来源。

代码或图示

普通链表:
  [块A] --next--> [块B] --next--> [块C]
  修改块A数据 → 链接不变 → 没人知道

哈希链:
  hash(A) = H_A
  B.parentHash = H_A ; hash(B) = H_B
  C.parentHash = H_B ; hash(C) = H_C

  改 A 任意字节 → H_A' ≠ H_A
  → B.parentHash 不匹配
  → 必须重算 B、C 及之后所有块
  → 在 PoW 上意味着重做之后所有工作量

常见误区

  • 误区:区块链"加密"所以内容看不见;正解:链上数据是公开的,哈希只保证未被篡改,不保密。
  • 误区:改了创世块就能改世界;正解:创世块被所有客户端硬编码在源码里,改它等于分叉出另一条链。
  • 误区:哈希指针和普通指针一样有内存地址;正解:它指向的是"被全网多数节点承认的那个区块",不是某个磁盘位置。

追问

  • 为什么哈希要选密码学哈希而不是 CRC?答:因为需要抗碰撞——攻击者不能造出两个不同块有相同哈希,也不能给定哈希反推内容。机制上 Keccak/SHA-256 的 avalanche 与海绵结构让这类反演在计算上不可行。边界在于:量子计算对 Grover 算法可把哈希强度平方级降低,256 位仍大致安全到 128 位强度。延伸:这也是后量子签名迁移的动因。
  • 长链为什么一定比短链可信?答:在 Nakamoto 共识下,更长的链意味着累积了更多算力/质押,单点撒谎成本更高。机制上节点总是选择累计难度最大的那条链。边界在于:这只在"攻击者控制多数资源不经济"时成立;51% 攻击就是反例。延伸:PoS 下这个逻辑改成"累计质押罚没风险最大"。
  • 区块头哈希和区块哈希是一回事吗?答:在以太坊里区块哈希就是 Keccak-256(RLP(区块头)),不包含交易体。机制上交易体的完整性由 transactionsRoot 单独证明。边界在于:比特币的双哈希(SHA256d)与以太坊 Keccak-256 不同,跨链桥与索引服务容易在这里搞错。延伸:解析外部数据时必须区分"块哈希"与"交易哈希"。

15.1.1-003 普通 Merkle 树怎么证明一笔交易在区块里?

一句话结论

把所有交易两两分组、对每对哈希再哈希、逐层向上直到根;证明某笔交易存在时,轻节点只需拿到该交易自身哈希加上从叶子到根路径上的兄弟哈希(约 log2(n) 个),与已知的区块头中 Merkle 根比对即可。

概念解释

  • 叶子:每笔交易的哈希。
  • 内部节点:两个子节点哈希的拼接再哈希。
  • Merkle 路径:从叶子到根的兄弟哈希列表。
  • 空洞(odd node):叶子数为奇数时,最后一个叶子自己复制一份参与下一层,避免引入特殊分支。

原理流程

  1. 对 n 笔交易分别取哈希,得到叶子层 L0..L(n-1)。
  2. 两两一组:H(L0,L1)、H(L2,L3)…;奇数个则最后一个自拼。
  3. 对下一层重复,直到只剩一个根。
  4. 要验证交易 Tx_i:节点已有区块头中的根 R,拿到叶子 H(Tx_i) 与路径上兄弟哈希。
  5. 逐层向上组合哈希,最终得到 R',与 R 比较。

代码或图示

4 笔交易的 Merkle 树:
         Root
        /    \
      h(AB)  h(CD)
      / \    / \
     A   B  C   D

证明 C 在树中:
  已知 Root
  提供:H(C)、H(D)、h(AB)
  验算:
    h(CD) = H(H(C) || H(D))
    Root' = H(h(AB) || h(CD))
  Root' == Root 则 C 确实在树中,位置在第三

8 笔交易时,每个证明只需 3 个兄弟哈希(log2(8)=3),
而不是下载全部 8 笔交易。

常见误区

  • 误区:Merkle 证明能证明交易"合法";正解:它只证明"这笔交易在区块里",交易是否签名有效、是否有钱花,要靠脚本/状态证明。
  • 误区:每笔交易的证明大小一样;正解:证明大小为 O(log n),区块越大证明略长,但相对区块体可忽略。
  • 误区:Merkle 树能证明交易"没被改过";正解:它能证明"在已知根的这棵树里",根本身由区块头锚定。

追问

  • 比特币为什么要对叶子做双哈希?答:为了避免第二层扩展(second-preimage)攻击——攻击者用 Merkle 内部节点伪装成叶子构造另一个合法树。机制上叶子哈希 = SHA256d(Tx),内部节点 = SHA256d(left||right),两者输入结构不同。边界在于这种防御不是密码学完备的,现代实现更倾向用域分隔(domain separation)。延伸:以太坊 MPT 用前缀区分节点类型,本质也是域分隔。
  • 轻节点验证交易后怎么知道"钱真的花到了我地址"?答:它只能确认交易在某块里,至于金额、输出地址必须由交易本身的字段给出,节点本地解析交易。机制上 SPV 假设"包含在最长链上的交易最终不会被双花"。边界在于:SPV 不能确认未花费输出(UTXO Set),所以才会被日蚀攻击与费米欺诈(fee scam)欺骗。延伸:比特币简化支付验证原本就是为轻钱包设计。
  • 为什么不直接把所有交易哈希都塞区块头?答:区块头要小(几百字节),否则带宽与签名成本会爆炸。机制上 O(log n) 证明把"证明任意一笔"的成本从 O(n) 降到对数级。边界在于:n 极大时(如 100 万笔)路径也要约 20 个哈希,仍可接受。延伸:这也是数据可用性采样(DAS)的基本思想。

15.1.1-004 比特币 Merkle 树与以太坊 MPT 有什么本质区别?

一句话结论

比特币 Merkle 树是静态、有序、只挂交易列表的二叉树,适合"证明某元素在已知列表里";以太坊 MPT 是带前缀压缩的可迭代键值树,键可以是任意字节串(地址、存储槽、交易序号),既支持列表证明也支持任意键的状态证明,并且插入/删除时能复用大部分节点。

概念解释

  • 静态列表:叶子在构建时一次性确定,之后不再变。
  • 键值树:键是任意字符串,可插入、删除、修改任意位置。
  • 前缀压缩:相邻共享前缀的节点合并为扩展节点,避免每层一个字节的浪费。
  • 域分隔:通过节点结构区分分支/扩展/叶,避免混淆。

原理流程

  1. 比特币场景:树只在打包区块时构建一次,叶子 = 交易哈希,证明 = 兄弟路径。
  2. 以太坊场景:状态是全局键值集合(地址 → 账户),需要随时新增、修改、删除条目。
  3. 若用普通二叉哈希表,每次改一个键都要沿路径重建所有节点,且公共前缀大量重复。
  4. MPT 用十六进制串为键、分支节点(16 路 + 1 个值)、扩展节点(共享前缀)、叶节点(剩余前缀 + 值)组织。
  5. 改一个键只需沿路径重建节点,未受影响分支共享不变。

代码或图示

MPT 节点类型:
  branch  : [v0..v15, value]   16 个分支 + 可选本节点值
  extend  : [shared_nibbles, hash_to_next]
  leaf    : [remaining_nibbles, value]

例:键 0x123ABC 与 0x123DEF
  root --extend "123"--> branch
                          /       \
                    leaf "AB"   leaf "DE"

常见误区

  • 误区:MPT 是二叉树;正解:它是 16 叉(按十六进制 nibble)的 Merkle 树,每层沿 nibble 走。
  • 误区:MPT 每改一个键整棵树都变;正解:只重建从叶子到根的路径,其他分支节点哈希共享。
  • 误区:MPT 与普通数据库无关;正解:MPT 节点就是 LevelDB/RocksDB 里的一条记录,键 = 节点哈希,值 = RLP 节点内容。

追问

  • 为什么按 nibble(4 位)而不是按字节分叉?答:因为地址与存储键是 32 字节,按字节会产生 256 路分支,节点过大;nibble 让分支节点固定 16+1 项,且前缀压缩有效。机制上扩展节点只存公共十六进制前缀。边界在于:路径深(64 个 nibble)意味着每次写入要改 64 个节点,这是 MPT 的主要开销之一。延伸:这也是 Verkle 树(向量承诺)想替代 MPT 的动因。
  • MPT 怎么删除一个键?答:沿路径找到叶节点,删除后若父分支只剩一个孩子,把它与扩展节点合并压缩;若分支节点空,则继续向上合并。机制上删除后还要清理不再被引用的旧节点。边界在于:并发回滚与重组时旧节点不能立即删除,要保留到最终性后。延伸:这是状态数据库要做垃圾回收的原因。
  • 收据树为什么不直接复用交易树?答:交易树按 txIndex 索引交易本身,收据树按 txIndex 索引执行结果,两者结构相同但内容不同,必须各自有根。机制上一笔交易可能成功(status=1)或失败(status=0),失败时交易本身仍被打包但状态不变。边界在于:只有 receiptsRoot 才能证明"事件日志"真的被发出,前端靠它索引。延伸:logsBloom 是 receiptsRoot 的粗筛加速层。

15.1.1-005 stateRoot、transactionsRoot、receiptsRoot 三个根各自证明什么?

一句话结论

transactionsRoot 证明"这个块打包了哪些交易、按什么顺序";stateRoot 证明"执行完这些交易后,全局所有账户的余额/nonce/存储/代码是这个集合";receiptsRoot 证明"每笔交易执行后的状态码、累计 Gas、日志"。三者都挂在区块头上,缺一就无法独立验证。

概念解释

  • transactionsRoot:对按序交易列表建树,锚定"交易列表未被替换"。
  • stateRoot:对全局状态(地址 → 账户)建树,是节点间一致性的核心。
  • receiptsRoot:对每笔交易的执行结果建树,包含日志与状态码。
  • logsBloom:块级 bloom,加速事件检索。

原理流程

  1. 提议者按规则收集交易,建立 txTrie(键 = 序号,值 = 交易)。
  2. 按序执行每笔交易,更新全局状态树与收据树。
  3. 把三棵树根写进区块头。
  4. 验证者独立重放所有交易,重算三棵根,与头部比较。
  5. 任意不一致即拒绝该块。

代码或图示

验证一个区块:
  已知 header.stateRoot、header.transactionsRoot、header.receiptsRoot

  1. 验证 RLP 解码后的交易列表哈希 = transactionsRoot
  2. 从 parent.stateRoot 开始,按序执行交易
     - 每笔成功:改账户 nonce/balance/storage 与合约存储
     - 记录 cumulativeGasUsed、status、logs
  3. 执行完得到 newStateRoot 与 newReceiptsRoot
  4. 比较 newStateRoot == header.stateRoot
       newReceiptsRoot == header.receiptsRoot
  三者全等 → 区块合法

常见误区

  • 误区:stateRoot 包含交易;正解:stateRoot 是交易执行后的结果,不包含交易本身。
  • 误区:失败的交易不占 Gas;正解:失败交易仍消耗 Gas,且收据 status=0,receiptsRoot 仍包含它。
  • 误区: receiptsRoot 是可选的;正解:没有它就无法证明事件日志真实发生过,前端索引会失效。

追问

  • 为什么不能只看 transactionsRoot 就认为链正确?答:因为同样的交易列表,执行结果可以被恶意构造者跑出不同状态。机制上节点必须独立执行才能确认 stateRoot 是诚实的。边界在于:轻节点不执行交易,所以它们只信"被最终性确认的块",不自己重算。延伸:ZK Rollup 用有效性证明代替全节点重放。
  • 账户在状态树里具体长什么样?答:RLP 编码的 [nonce, balance, storageRoot, codeHash]。机制上 storageRoot 是该合约自己的子树,codeHash 是合约字节码的 Keccak。边界在于:EOA(外部账户)codeHash 为空哈希、storageRoot 为空。延伸:这就是为什么合约部署时要把字节码写进数据库并在账户里登记哈希。
  • 三个根都用同一棵 MPT 还是三棵独立树?答:三棵独立树。机制上 txTrie 与 receiptTrie 每块新建,stateTrie 是跨块累积的全局树。边界在于:stateTrie 的节点长期保留(直到重组/修剪),txTrie 与 receiptTrie 节点块后即可被 GC。延伸:这也是归档节点与全节点磁盘差异的来源。

15.1.1-006 MPT 的分支、扩展、叶节点怎么协同工作?

一句话结论

MPT 用三种节点组织键值:分支节点是 16 路 + 1 值的岔路口;扩展节点压缩一段公共 nibble 前缀并指向后续节点;叶节点携带剩余 nibble 与最终值。读取/写入沿键的 nibble 序列走,遇到分支继续、遇到扩展跳过共享前缀、遇到叶命中或失配。

概念解释

  • nibble:4 位,一个十六进制数字。
  • 分支节点:17 项数组(16 分支 + 1 value)。
  • 扩展节点:长度 2 的数组 [shared_prefix, next_hash],用于压缩。
  • 叶节点:长度 2 的数组 [remaining_suffix, value]。
  • hex-prefix(HP)编码:用首 nibble 的高低位标记"节点类型(叶/扩展)+ 是否偶数长度"。

原理流程

  1. 从根开始,把键转成 nibble 序列。
  2. 遇分支:取第一个 nibble,索引到对应孩子。
  3. 遇扩展:比较剩余 nibble 是否以扩展共享前缀开头,是则跳过该前缀并继续下一个节点,否则键不存在。
  4. 遇叶:比较剩余 nibble 是否等于叶的 suffix,相等则返回 value,不等则未命中。
  5. 写入时沿路重建节点;若新增孩子让扩展节点变成分支,或删除让分支退化为只剩一个孩子,做节点合并/分裂。

代码或图示

例:插入 0x12345 → A, 0x12399 → B, 0x14 → C

       root
        |
     extend "1"
        |
      branch
       /   \
     "2"    "4" -- leaf "" -> C
      |
   extend "3"
      |
    branch
     /   \
   "4"   "9"
    |     |
 leaf     leaf
 (A)     (B)

HP 编码示例:
  偶数长度扩展 "123" -> [0, 0x12, 0x3]
  奇数长度叶  "4"    -> [1, 0x4, value...]

常见误区

  • 误区:扩展节点存的是完整键;正解:它只存公共前缀,值在叶节点。
  • 误区:分支节点最多 16 个孩子;正解:是 16 个 nibble 分支 + 1 个可选 value,共 17 项。
  • 误区:MPT 每次写入都要新建所有节点;正解:只新建路径上的节点,其他分支哈希复用。

追问

  • 为什么需要 hex-prefix 编码?答:为了在不带额外类型标签的情况下,从 RLP 字节串本身区分"这是叶节点还是扩展节点、suffix 长度是奇数还是偶数"。机制上把奇偶性编码进首 nibble 的高/低位。边界在于这是以太坊特有的编码约定,跨语言实现最容易在这里出错。延伸:这也是为什么不同客户端对同一区块算出的根必须完全一致。
  • 一个空状态的根是什么?答:RLP 编码空字符串的 Keccak-256,即众所周知的空哈希。机制上创世块之后所有账户都从空树派生。边界在于:不同链(如测试网)若创世状态不同,stateRoot 不同,不能混用。延伸:跨链消息验证必须知道对方创世根。
  • MPT 为什么不直接用普通 B+ 树?答:因为区块链需要"内容寻址"——节点的键就是它自身内容的哈希,这种结构天然支持"对任意历史根的快照做证明"。机制上 B+ 树的内部节点键是排序值,不能直接当哈希。边界在于:内容寻址导致每次写入都要重新计算路径节点哈希,CPU 开销大。延伸:这也是 Verkle 树与状态过期(stateless)研究的出发点。

15.1.1-007 SPV 轻节点怎么不下载全区块就验证一笔交易?

一句话结论

SPV 轻节点只下载区块头(约数百字节),从对方网络拿到"该交易在某块中的 Merkle 路径 + 交易本身",自己用本地已知的最长链头部哈希验证根,从而确认交易被打包;它不验证交易合法性、不维护 UTXO/状态集,把安全性假设为"诚实多数会拒绝包含无效交易的块"。

概念解释

  • 区块头同步:轻节点只 headsync,不下载交易体。
  • Merkle 证明:交易哈希 + log2(n) 个兄弟哈希。
  • 简化支付验证:只验证"交易被某已知块包含",不验证"这笔交易是否双花"。
  • 日蚀攻击:轻节点的危险,攻击者把它隔离到自己构造的假链上。

原理流程

  1. 轻节点与多个全节点建立连接,同步区块头到最新。
  2. 用户发起"我是否收到了某笔地址的付款"查询。
  3. 某个全节点返回交易本身 + 从交易到块根的 Merkle 路径。
  4. 轻节点重算根,与本地该高度的区块头比较。
  5. 若块在足够深的位置(如比特币 6 块确认),认为付款不可逆。

代码或图示

SPV 验证流程:
  本地已存 header[N].merkleRoot = R

  对方返回:
    tx = <原始交易字节>
    proof = [h_sibling_i, h_sibling_i+1, ...]
    blockHeight = N

  本地计算:
    leaf = H(tx)
    cur  = leaf
    for each sibling in proof:
        cur = H(min(cur,sib) || max(cur,sib))
    assert cur == R
    assert header[N].height 在最长链足够深

常见误区

  • 误区:SPV 能防双花;正解:SPV 只能确认交易被打包,无法确认输入没有被另一笔交易花掉,这是全节点的事。
  • 误区:轻钱包用 SPV 就够安全;正解:现代轻钱包通常连接自己的服务节点或用 Neutrino 类轻节点,SPV 原始模型已被多个攻击绕过。
  • 误区:SPV 不需要区块头;正解:没有区块头,就没有可信的根,Merkle 证明毫无意义。

追问

  • SPV 为什么容易被日蚀?答:因为轻节点主动选择全节点连接,攻击者可以用大量假节点包围它,让它只看到伪造的链。机制上节点发现与 peer 表可被女巫化。边界在于:长时段、多源连接能缓解,但不能根除。延伸:比特币 Neutrino 与以太坊轻客户端用"随机采样 + 密码学验证"改进。
  • 以太坊为什么没有传统意义的 SPV?答:因为以太坊是账户模型,交易的有效性依赖当前状态,而不是 UTXO 集合;轻节点要验证"某个账户余额是多少"必须用状态 MPT 证明。机制上这就是 Merkle Patricia 的状态证明,比比特币 SPV 更通用但更大。边界在于:状态证明要给从账户到 stateRoot 的路径,约 200-1000 字节。延伸:这是 15.2 章节轻客户端与同步的话题。
  • 6 个确认是什么原理?答:在 PoW 下,已包含交易的块被重组的概率随确认数指数衰减;6 个确认是工程经验值,让攻击者重写的成本超过收益。机制上每次后续块都要重做工作量。边界在于:这不是密码学绝对最终性,只是概率安全;大额交易仍需更多确认或等待最终性。延伸:PoS 合并后以太坊有真正的_slot 最终性概念。

15.1.1-008 MPT 为什么能支持任意键的插入、删除与读取?

一句话结论

MPT 的键是任意长度 nibble 序列,三种节点结构天然支持"在任意键位置分叉、合并、删除":读取沿键走节点、插入在缺失处挂叶节点、删除后通过合并扩展/分支保持树紧凑;所有节点内容寻址,改一个键只重建路径。

概念解释

  • 内容寻址:节点 key = H(RLP(node)),值 = RLP(node)。
  • 路径重建:插入/删除时从叶子到根重建节点,其他分支共享。
  • 节点合并:分支退化为单孩子时与扩展节点合并。
  • 分裂:扩展节点的前缀不再共享时拆成扩展 + 分支。

原理流程

  1. 读取:从根开始按 nibble 序列走,扩展跳前缀、分支按 nibble 索引、叶节点比对 suffix。
  2. 插入:走到缺失位置(要么叶节点前缀冲突,要么分支缺孩子)。
  3. 叶冲突时新建一个分支节点,把旧叶与新叶挂到对应 nibble 下,必要时加扩展。
  4. 删除:找到叶节点删除,向上把空分支合并为扩展或直接移除。
  5. 每一步产生的新节点都以其哈希为键写入底层 KV 存储。

代码或图示

插入 0xAB → X,再插入 0xAC → Y:

  初始: root --leaf "AB" -> X

  插入 0xAC:
    root
     |
  extend "A"
     |
   branch
    /   \
  "B"   "C"
   |     |
  leaf   leaf
   X     Y

删除 Y:
  branch 只剩 "B" → 合并回 extend "AB" -> leaf X

常见误区

  • 误区:MPT 是二叉搜索树;正解:它是按 nibble 走的 16 路 trie,不依赖比较键大小。
  • 误区:删除一个键后旧节点立即被清除;正解:重组与历史证明期间要保留,由 GC 异步清理。
  • 误区:MPT 写入是原地更新;正解:它是不可变树,每次写入产生新路径节点,旧节点保留直到被引用计数清除。

追问

  • 为什么 MPT 写入放大严重?答:因为账户键是 64 个 nibble,每次写入要从叶到根新建约 10-20 个节点(公共路径上的扩展/分支)。机制上每个节点 RLP 编码后哈希一次,写一次底层 KV。边界在于:这是以太坊主网 TPS 受限的核心原因之一。延伸:Verkle 用向量承诺把路径证明从几百字节压到几百字节,并减少节点数。
  • 底层 KV 存什么?答:键是 Keccak-256(RLP(node)),值是 RLP(node);根节点哈希另外存为"当前头的 stateRoot"。机制上这就是 LevelDB/RocksDB 的一张表。边界在于:重组时旧根仍被引用,不能立即删;这就是"历史键"与"快照"机制。延伸:客户端会定期生成快照加速新节点同步。
  • 如何证明"某地址余额是 X"?答:从账户节点沿分支/扩展节点走到根,提供路径上所有节点的 RLP,验证者用这些节点重算 stateRoot。机制上账户节点本身包含 [nonce, balance, storageRoot, codeHash]。边界在于:这个证明只在"该 stateRoot 被某已知块头锚定"时才有意义。延伸:这是无状态客户端与 Verkle 的核心交互格式。

15.1.1-009 区块重组时状态怎么回滚?为什么需要历史键与快照?

一句话结论

当链切换到另一条分叉时,节点要把本块从状态树"撤销":把每个账户、每个存储槽恢复到父块状态,旧 MPT 节点不能立刻删除,要保留到重组不再发生;这就是为什么数据库要存历史键、为什么归档节点能回答任意历史高度的余额。

概念解释

  • 重组(reorg):本以为主链的块被另一分支取代。
  • 状态回滚:逆序执行本块交易,恢复账户与存储。
  • 历史键:旧状态节点以旧根哈希为键保留,用于回滚与历史查询。
  • 快照:周期性的状态树扁平导出,加速回滚与新节点同步。

原理流程

  1. 节点在块 N 上,已知本地状态根 = root_N。
  2. 收到分叉链 N',其累计难度/最终性更高。
  3. 找到共同祖先 A,逆序撤销 N、N-1…A+1 的所有交易。
  4. 撤销时直接从历史键里取出每个账户在 A 时的值写回。
  5. 然后正向执行新链上 A+1' … N' 的交易。
  6. 长期不再被引用的旧节点由 GC 异步清理。

代码或图示

状态回滚伪代码:
  for block in reverse(chain[ancestor+1 .. current]):
    for tx in reverse(block.transactions):
      account = tx.from
      state[account] = oldStateSnapshot[tx.hash][account]
      for slot in tx.touchedSlots:
        storage[account][slot] = oldStateSnapshot[tx.hash][slot]

  数据库设计:
  key = keccak(node_rlp)  value = node_rlp   -- 状态节点,多版本共存
  key = "h" + blockNumber value = blockHash  -- 高度到哈希
  key = "s" + blockHash   value = stateRoot  -- 块到状态根

常见误区

  • 误区:回滚是重跑交易反向;正解:实际是用执行时记录的"前值快照"直接覆盖,不需要反向计算。
  • 误区:旧节点用完即删;正解:可能再次重组回来,必须保留到最终性窗口之后。
  • 误区:归档节点和全节点代码不同;正解:区别只在"是否启用状态修剪",归档节点不删历史键。

追问

  • 为什么合并后重组大幅减少?答:PoS 下有两个 epoch 后的最终性(约 12.8 分钟),最终性块不能回滚。机制上验证者对检查点投票,超过 2/3 投票即最终。边界在于:最终性之前的区块仍可能重组(深度通常 1-32 槽)。延伸:这是 15.2.4 最终性话题。
  • 全节点为什么磁盘越涨越大?答:虽然会修剪老状态节点,但块数据、收据、日志仍在累积,且修剪本身需要保留近期状态。机制上 geth 默认 full 模式保留最近 128 个块的状态,并做每周快照。边界在于:归档节点不修剪,主网状态已达数百 GB 量级,随时间继续增长。延伸:这是状态增长问题与 Verkle 的动机。
  • 状态快照为什么能加速同步?答:因为从创世块重放要执行所有历史交易;而快照直接 dump 某高度的所有账户(键值对),节点加载后只从该高度继续。机制上快照文件是按地址排序的账户列表,可并行下载。边界在于:快照本身要由某个可信节点提供,信任假设回到轻客户端问题。延伸:这是 snap sync 的核心。

15.1.1-010 为什么要做无状态客户端(stateless client)与见证数据?

一句话结论

MPT 全状态太大,新节点同步慢、磁盘大;无状态客户端不再本地保存全状态,而是提议者在打包时附带"本块涉及账户与存储的 MPT 证明"(witness),其他节点仅凭区块 + witness 就能验证执行结果,不需要本地状态。

概念解释

  • 状态爆炸:主网状态随合约与用户增长,磁盘与同步门槛高。
  • 见证数据(witness):执行本块所需的所有账户与存储槽的 MPT 路径。
  • 无状态执行:节点不维护状态,只根据 witness 验证状态转换。
  • Verkle:用向量承诺替换 MPT,把 witness 压到几百字节。

原理流程

  1. 提议者本地有状态,执行交易得到新状态。
  2. 对本块触达的每个账户、每个存储槽生成 MPT 路径证明。
  3. 把 witness 附在块上广播。
  4. 验证者不持有状态,仅用 witness 重放交易,比较新 stateRoot。
  5. 磁盘与同步成本从"全状态"降到"按块 witness"。

代码或图示

有状态节点:
  本地 KV: 全量 ~数百 GB 状态节点
  收到块 → 查本地状态 → 执行 → 写新状态

无状态节点:
  本地 KV: 仅块头、块体(轻量)
  收到块 + witness:
    witness = { address → (account_node, path_nodes),
                slot     → (value_node, path_nodes) }
  用 witness 重放 → 比较 stateRoot
  不保存任何账户

常见误区

  • 误区:无状态节点不验证区块;正解:它仍独立重放交易,只是用 witness 代替本地查询。
  • 误区:witness 很小;正解:当前 MPT 下 witness 可能比块体还大,这是 Verkle 要解决的问题。
  • 误区:无状态意味着没有隐私;正解:witness 是公开数据,隐私仍由隐私技术解决。

追问

  • 为什么需要 Verkle?答:MPT 的见证大小随触达账户数线性增长(每个账户约 1-2 KB),而 Verkle 用向量承诺(多项式 KZG 类)把多个证明聚合成几百字节。机制上一个证明同时覆盖多个键。边界在于:Verkle 仍处于研究与测试网阶段,主网迁移尚未完成。延伸:这是以太坊路线图的核心议题之一。
  • 提议者为什么要附 witness?答:因为只有提议者本地有完整状态,它是唯一能便宜生成证明的人。机制上验证者不能凭空拿到状态。边界在于:这要求提议者至少跑一次全节点,或者与状态提供者合作。延伸:这也是 PBS(提议者/构建者分离)的天然接口。
  • 无状态会让轻钱包更安全吗?答:会,因为普通节点不再需要信任某个全节点说"你余额是多少",而是直接用 witness 自证。机制上钱包收到 witness 即可验证,不需要自己跑全节点。边界在于:witness 的获取仍需要某个网络服务,且需要块头同步。延伸:这与 15.2 轻客户端话题相连。

动手练习

练习 1:手算 Merkle 根与 SPV 证明

  • 任务:用 4 笔交易哈希(任意 Keccak-256)构造 Merkle 树,画出根;然后为其中第 3 笔写出验证路径。
  • 验收标准:
    1. 画出完整树图,标注每一层哈希。
    2. 写出验证第 3 笔时所需的兄弟哈希列表。
    3. 说明 8 笔交易时证明需要几个兄弟哈希。

练习 2:用代码观察 MPT 节点

  • 任务:在本地用任意以太坊客户端(如 go-ethereum 或 pyethereum)的 MPT 实现,插入 3 个键值对,遍历打印节点类型(branch/extend/leaf)与路径。
  • 验收标准:
    1. 能区分三种节点并解释何时出现。
    2. 修改一个键后,比较新旧根哈希,指出哪些节点复用、哪些新建。
    3. 删除一个键,观察节点合并过程。

自检清单

  • [ ] 能否在白板上画出以太坊区块头的 12 个核心字段及其字节含义?
  • [ ] 能否解释为什么链链接的是区块头而不是区块体?
  • [ ] 能否手算 4 个叶子的 Merkle 根并写出一个叶子的证明路径?
  • [ ] 能否说清 MPT 三种节点的结构与 HP 编码的作用?
  • [ ] 能否区分 stateRoot、transactionsRoot、receiptsRoot 各自证明什么?
  • [ ] 能否解释 SPV 能做什么、不能做什么?
  • [ ] 能否描述区块重组时状态回滚的机制与历史键的作用?
  • [ ] 能否说清无状态客户端与 Verkle 想解决的问题?

延伸阅读

  • Bitcoin Core 源码 src/consensus/merkle.cpp:二叉 Merkle 树与空洞处理。
  • Yellow Paper(以太坊黄皮书)第 4 章关于区块头与 MPT 定义。
  • EIP-1559:baseFeePerGas 字段引入的背景。
  • EIP-4762 / Verkle 相关研究文档:用向量承诺替换 MPT 的路线图。
  • 以太坊客户端实现文档(go-ethereum trie/、reth trie/):MPT 与快照同步。

待整理清单

  • [ ] 补充 EIP-4844 blob 字段对区块头的扩展
  • [ ] 补充 Verkle 与 KZG 承诺的入门推导
  • [ ] 补充不同客户端(geth / reth / nethermind)状态数据库布局差异