一枚根哈希，如何证明一片森林？

下面的教学树使用 SHA-256 与显式域分离。叶子前加 0x00， 内部节点前加 0x01。这样做是为了把概念讲清，不代表执行层 MPT 采用同一套具体编码。

1. 规范化数据 先确定字符编码、整数宽度、字段次序与长度；“语义相同”不代表字节相同。
2. 生成叶子承诺 每条数据独立哈希。任何一位变化都通常会让叶子摘要出现完全不同的输出。
3. 按位置合并兄弟 左摘要在前、右摘要在后。父节点不保存原文，只承诺这两个子承诺及其顺序。
4. 递归直到只剩一枚根 根长度固定为 32 字节，与叶子是一百条还是一百万条无关。

为什么一次更新只重算一条路径？

Alice 的叶子变化后，它的兄弟 Bob 没变，右半棵树也没变。重算只发生在 L₀ → P₀₁ → Root 这条祖先链。对一棵有 n 个叶子的平衡二叉树， 树高约为 log₂(n)，所以单点更新只影响约 log₂(n) 个层级。

“持久化 Merkle Tree”还可以复用未改变的旧节点，因此同一数据库可保留多个历史根， 只为变更路径创建新节点。以太坊状态树的工程实现更复杂，但“未变子树可由旧哈希继续代表” 是理解状态根高效更新的重要直觉。

四个经常被省略、却会让根算错的细节

要证明 Alice 位于四叶树的第 0 号位置，验证者已经拿到了 Alice 的数据， 因此不需要再次发送 L₀；它只缺同层的 L₁ 与另一半子树的 P₂₃。

验证算法实际上只做三件事

node = hashLeaf(encodedValue)

for each (sibling, direction) in proof:
    if direction == "sibling_on_left":
        node = hashParent(sibling, node)
    else:
        node = hashParent(node, sibling)

accept if node == trustedRoot

左右方向不能省略。假设当前节点在父节点右边，拼接顺序必须是 sibling ∥ current；若当前节点在左边，则是 current ∥ sibling。 有些树可从固定索引逐位推导方向，因此证明格式不一定显式传一串“左/右”。

为什么证明是 O(log n)？

平衡二叉树每上升一层，覆盖的叶子数翻倍：1、2、4、8……覆盖 n 个叶子需要约 log₂(n) 层。单叶证明每层补一个兄弟摘要，所以证明哈希数量与树高相同。

一次证明多个叶子：不要机械拼接多份单证明

若要同时证明多个相近叶子，它们的路径常共享上层兄弟节点。Merkle multiproof 只提供恢复相关子树所需的最小辅助节点，能去掉重复哈希。以太坊共识规范专门定义了基于 generalized index 的多证明辅助索引算法。^[5]

说“以太坊把状态放在 Merkle Tree 里”作为入门直觉没有问题；进入协议层后，必须马上补上限定： 当前执行状态是 modified Merkle-Patricia Trie，共识对象则用 SSZ Merkleization。

执行状态里的“两层证明”

世界状态树的键是账户地址的 Keccak 摘要路径，叶子值是账户对象。合约账户对象中的 storageRoot 又承诺这个合约自己的存储 trie。因此证明某个存储槽通常要走两段： 先证明账户属于 stateRoot，再用账户中认证过的 storageRoot 证明槽值。 ^[2][6]

stateRoot、transactionsRoot、receiptsRoot 不要混用

三者都出现在执行区块头语境中，却承诺不同对象。节点重执行区块交易后，会检查新状态根、 交易根、收据根等承诺与区块头是否一致；任一不匹配都不能把该执行结果当作有效区块接受。 ^[3][4]

Ethereum Execution APIs 定义了 eth_getProof(address, storageKeys, block)。 你可以传入地址、要核对的 32 字节存储键列表，以及区块号、区块哈希或 latest / safe / finalized 等标签。^[6]

{
  "jsonrpc": "2.0",
  "id": 1,
  "method": "eth_getProof",
  "params": [
    "0xAbC…123",
    ["0x000…007"],
    "finalized"
  ]
}

离线验证的顺序

Merkle Proof 在应用层还做什么？

六题自测

三步练习

1. 01

   手画四叶树，任选一个叶子，写出验证者需要的两个兄弟摘要及左右拼接顺序。

2. 02

   打开区块浏览器的某个执行区块，分别找到 state root、transactions root 与 receipts root，并用一句话说明三者对象。

3. 03

   在测试环境调用 eth_getProof，保存实际 block hash，不只保存会移动的 latest 标签；尝试用 MPT 库离线验账户证明。

核心术语

Merkle Tree

叶子与内部节点通过哈希递归认证、最终归约为根承诺的数据结构家族。

Merkle root

整份数据及其规范结构的固定长度根承诺。

Merkle proof

目标值重建到根所需的兄弟节点、方向/位置与相关元数据。

Leaf

树的底层数据承诺；可为固定长度块或对编码数据的哈希。

Internal node

由一个或多个子节点按规则计算而成的中间承诺。

Domain separation

用不同前缀或域标识区分叶子、内部节点等结构角色。

Membership proof

证明某个值位于被根承诺的数据结构中的证明。

Non-membership proof

证明某个键或值不在承诺结构中的证明，需要结构支持缺失语义。

Multiproof

共享多条路径的公共节点，以更少辅助哈希同时认证多个目标。

MPT

Modified Merkle-Patricia Trie；当前以太坊执行状态使用的认证键值结构。

stateRoot

执行完区块后世界状态的根承诺，位于执行区块头/执行载荷头语境中。

storageRoot

单个账户存储 trie 的根，作为账户对象字段被世界状态树继续承诺。

SSZ

共识层 Simple Serialize；类型驱动序列化并支持二叉 Merkleization。

Generalized index

SSZ 二叉 Merkle 树的稳定节点编号；根为 1，节点 k 的子节点为 2k、2k+1。

Data availability

参与者能否获得重建、验证或执行所需数据；承诺完整性不能单独保证它。

UBT

Unified Binary Tree；EIP-7864 提议的未来执行状态树，当前仍为 Draft。

官方与标准原文

1. ethereum.org · Merkle Patricia Trie 当前执行状态 MPT 的总体定位、节点类型、路径压缩、RLP 与哈希引用。
2. ethereum.org · Ethereum Virtual Machine 世界状态作为 modified Merkle Patricia trie，以及合约 storage trie 与账户的关系。
3. ethereum.org · Blocks 执行载荷头中的 state_root、receipts_root、transactions_root 与节点重执行验证。
4. Ethereum Execution Specs · Blocks 当前执行规范中的区块字段与 stateRoot、transactionsRoot、receiptsRoot 承诺。
5. Ethereum Consensus Specs · Merkle proof formats generalized index、单证明与 multiproof 辅助索引的规范算法。
6. Ethereum Execution APIs · eth_getProof 账户地址、storage keys、block 参数与 Merkle proof RPC 的当前接口定义。
7. ethereum.org · Simple Serialize (SSZ) 32 字节 chunks、零值补齐、hash-tree-root、generalized indices 与证明直觉。
8. EIP-1186 · RPC-Method to get Merkle Proofs eth_getProof 的历史动机、账户/存储证明字段与不存在证明讨论；状态为 Stagnant，应结合当前 API 规范阅读。
9. ethereum.org · Merkle proofs for offline data integrity 链下数据完整性、链上保存根与合约验证证明的应用层教程。
10. EIP-7864 · Ethereum state using a unified binary tree Draft 提案：统一二叉状态树、证明大小与 ZK 友好性的动机；哈希函数尚未最终确定。
11. Ethereum Foundation · Protocol Priorities Update for 2026 把二叉树与无状态化列为长期状态扩展方向，短期重点仍含重定价与历史过期。
12. Ethereum Yellow Paper · Appendix D 执行层 modified Merkle Patricia tree 的形式化基础；阅读时需结合后续 EIP 与当前执行规范。