九思札记 · 探索区块链 · AI

以太坊的"世界状态"是一个巨大的键值数据库，存储数亿个账户的 balance、nonce、code 和 storage。这个数据结构必须满足三个苛刻条件：(1) 每次区块后能快速切换到新状态；(2) 轻客户端能验证任意账户的存在性；(3) 历史状态能被快速回滚。Patricia Merkle Trie（MPT）以优雅的方式同时解决了这三个问题。

7.3.1 Patricia Trie + Merkle Tree 的融合

MPT 是两个经典数据结构的叠加：

Patricia Trie（前缀树 / 压缩 Trie）：用共享前缀压缩键空间，确保树高仅与键长度成正比；
Merkle Tree：每个节点的哈希是其子节点的哈希函数，使根哈希成为整棵树的密码学摘要。

\text{MPT Node} \in \{\text{Null}, \text{Leaf}(\text{path}, \text{value}), \text{Extension}(\text{path}, \text{next}), \text{Branch}[16+1]\}

节点类型	子节点数	用途
`Null`	—	空路径
`Leaf`	0	键的终点，RLP 编码 = [encodedPath, value]
`Extension`	1	压缩一段公共前缀，指向 1 个子节点
`Branch`	16 + 1	16 分支对应 hex 字符 [0-f] + 1 个可选 value 字段

graph TD
    A[Root<br>H(H(B)=r1)] --> B[Branch<br>index 'a']
    B --> C[Leaf<br>encodedPath<b|d2c| → value<br>(Alice's account)]
    B --> D[Extension<br>path: <b|d...>] 
    D --> E[Branch<br>index '2']
    E --> F[Leaf<br>path <b|d2...|3| → value<br>(Bob's account)]
    style A fill:#ccebff
    style C fill:#e6f3ff
    style F fill:#e6f3ff

7.3.2 三棵树结构及其职责

一个以太坊区块的头部包含三棵树的根哈希：

状态树（State Trie）：stateRoot —— 当前所有账户状态的快照；
交易树（Tx Trie）：txRoot —— 当前区块内所有交易的 trie；
收据树（Receipt Trie）：receiptRoot —— 当前区块内所有交易收据的 trie。

\text{Block Header} = (\dots, \text{stateRoot}, \text{txRoot}, \text{receiptRoot}, \dots)

状态树的特殊性：状态树是全局跨块累积的——每个新区块基于上一区块的状态树做增量修改，而不是从 0 开始重建。未触及的账户路径直接复用前一状态的子树。

graph LR
    A[Block N<br>stateRoot = H(σ_N)] -->|增量更新| B[Block N+1<br>stateRoot = H(σ_N+1)]
    A --> C[txRoot = txs in N]
    B --> D[txRoot = txs in N+1]
    A -.-> E[未更改子树<br>直接复用]
    E -.-> B
    style E fill:#ffffcc

键编码方式：状态树的键不是原始地址，而是地址的 Keccak256 哈希的十六进制字符（64 个 hex 字符），然后按 4 比特半字节（nibble）逐层导航。这保证了树的均匀分布。

7.3.3 轻客户端验证：MPT 证明

轻客户端只保存区块头（约 500 字节/块），要验证"地址 0xabc... 的余额是多少"，只需向全节点请求该地址的 Merkle 证明路径。

路径证明大小： $O(\log_{16} N)$ 个节点，每个节点约 32-530 字节。对于 2 亿账户，树高约 $\log_{16}(2\times10^8) \approx 7$ 层，证明大小约 1-3KB。

// mpt-verify-sim.ts
// 纯内置：模拟简化的 MPT 路径验证

type MPTNode = 
  | { type: 'null' }
  | { type: 'branch'; children: (string | null)[]; value: string | null; hash: string }
  | { type: 'leaf'; path: string; value: string; hash: string }
  | { type: 'ext'; path: string; next: string; hash: string } // 指向下一个节点的哈希

// 简化的 Keccak 占位符
function keccak256(data: string): string {
  // 模拟：累加字符编码取 BigInt 后取模
  let h = 0n;
  for (const c of data) h = (h * 31n + BigInt(c.charCodeAt(0))) % (1n << 256n);
  return '0x' + h.toString(16).padStart(64, '0');
}

// RLP 编码占位符
function fakeRlpEncode(parts: string[]): string {
  return parts.map(p => p.length.toString(16).padStart(2, '0') + p).join('');
}

// 计算节点哈希
function nodeHash(node: MPTNode): string {
  if (node.type === 'null') return '0x' + '0'.repeat(64);
  if (node.type === 'branch') return keccak256(fakeRlpEncode([...node.children.filter(Boolean) as string[], ...(node.value ? [node.value] : [])]));
  if (node.type === 'leaf') return keccak256(fakeRlpEncode([node.path, node.value]));
  return keccak256(fakeRlpEncode([node.path, node.next]));
}

// 验证路径：给出一系列节点，从叶子向上哈希，最终比对 root
function verifyMPT(root: string, keyNibbles: number[], proof: MPTNode[], expectedValue: string): boolean {
  let currentHash = '';
  let currentNode: MPTNode | null = null;
  
  // 从 proof 尾部（叶子）开始，反向重建上一层哈希
  let idx = proof.length - 1;
  for (let depth = 0; depth < proof.length; depth++) {
    const node = proof[proof.length - 1 - depth];
    if (node.type === 'leaf') {
      if (node.value !== expectedValue) return false;
      currentHash = nodeHash(node);
    } else if (node.type === 'branch') {
      const childIdx = keyNibbles[depth];
      const child = node.children[childIdx];
      if (child === null) return false;
      // 验证当前哈希是否与分支节点的引用匹配
      if (depth > 0 && child !== currentHash) return false;
      currentHash = nodeHash(node);
    } else if (node.type === 'ext') {
      if (depth > 0 && node.next !== currentHash) return false;
      currentHash = nodeHash(node);
    }
  }
  return currentHash === root;
}

// 示例：构建简单的 2 层分支证明
const leaf: MPTNode = { type: 'leaf', path: 'b0', value: '1000', hash: '' };
const leafHash = nodeHash(leaf);
const branch: MPTNode = { type: 'branch', children: Array(16).fill(null) as any, value: null, hash: '' };
branch.children[11] = leafHash; // 'b' = 11
branch.hash = nodeHash(branch);

const root = branch.hash;
const proof: MPTNode[] = [branch, leaf];
const key = [11, 0]; // 'b0'

console.log('验证 Merkle 证明:', verifyMPT(root, key, proof, '1000'));
// 输出 true，验证了从 leaf → branch → root 的哈希链