九思札记
教程›区块链›区块链技术›ch02›2.7 Merkle 树与 SPV 轻量验证

本页目录

区块链需要存储海量交易数据。以太坊一个全节点的状态大小超过 700 GB，比特币区块链历史数据超过 600 GB。如果每个用户都需要下载全部数据才能验证一笔交易，去中心化的门槛将变得极高。本节介绍 Merkle 树（哈希树） 的巧妙结构，以及它如何使轻客户端（SPV）仅用数 KB 数据就可验证特定交易的存在性。

2.7.1 问题：如何高效证明"某个数据在集合中"

假设一个区块包含 1000 笔交易，全节点需要存储所有交易的完整列表。当 Alice 问"我的交易 tx_237 是否被包含在这个区块中？"，传统方法是把 1000 笔交易全部发送给她，让她自己搜索。传输量 = 1000 × 平均交易大小（约 250 B）= 250 KB。

有没有更高效的方法？答案是：如果全节点只需证明"tx_237 的哈希在某个哈希值的集合中"，而 Alice 信任自己已经知道的那个"集合的简洁表示"，证明可以极短。

2.7.2 Merkle 树的结构

构建过程（自下而上）

假设 8 笔交易（N=8N=8，扩展为 2 的幂次）：

text
Level 3 (Root):            H_{0-7}
                          /       \
Level 2:           H_{0-3}         H_{4-7}
                   /    \          /    \
Level 1:      H_0-1   H_2-3   H_4-5   H_6-7
              /   \    /   \    /   \    /   \
Level 0:   tx0   tx1  tx2  tx3  tx4  tx5  tx6  tx7
           (叶节点，每个都是数据的哈希)

每个内部节点存储其两个子节点的双重哈希（防止长度扩展攻击）：

Hparent=H(Hleft∥Hright)H_{\text{parent}} = H(H_{\text{left}} \parallel H_{\text{right}})

在比特币中，H=double-SHA256(double-SHA256(left∥right))H = \text{double-SHA256}(\text{double-SHA256}(\text{left} \parallel \text{right}))。

关键性质：O(log⁡N)O(\log N) 的证明大小

要证明 tx3 在集合中，只需提供从 tx3 到根的一条路径上的兄弟节点哈希：

需要的兄弟节点为什么需要
Hash(tx2)与 Hash(tx3) 组合得 H_{2-3}
H_{0-1}与 H_{2-3} 组合得 H_{0-3}
H_{4-7}与 H_{0-3} 组合得 H_{0-7}（根）

证明大小：O(log⁡N)O(\log N) 个兄弟节点。对于 1000 笔交易，需要 log⁡21000≈10\log_2 1000 \approx 10 个哈希，每个 32 字节，总证明大小 ≈ 320 字节——比发送全部 250 KB 交易数据小了 800 倍。

typescript
/**
 * Merkle 树完整 TypeScript 实现
 */
class MerkleNode {
  constructor(
    public hash: Uint8Array,
    public left: MerkleNode | null = null,
    public right: MerkleNode | null = null,
    public txIndex: number = -1, // 叶节点对应的交易索引
  ) {}

  isLeaf(): boolean {
    return this.left === null && this.right === null;
  }
}

class MerkleTree {
  root: MerkleNode | null = null;
  private leaves: MerkleNode[] = [];

  constructor(txHashes: Uint8Array[]) {
    if (txHashes.length === 0) throw new Error('Cannot build tree with 0 leaves');
    
    // 如果叶节点数量不是 2 的幂次，重复最后一个直到对齐
    const padded = [...txHashes];
    while ((padded.length & (padded.length - 1)) !== 0) {
      padded.push(padded[padded.length - 1]);
    }
    
    // 构建叶节点
    this.leaves = padded.map((h, i) => new MerkleNode(h, null, null, i < txHashes.length ? i : -1));
    this.root = this._buildTree(this.leaves);
  }

  private _buildTree(nodes: MerkleNode[]): MerkleNode {
    if (nodes.length === 1) return nodes[0];
    
    const parents: MerkleNode[] = [];
    for (let i = 0; i < nodes.length; i += 2) {
      const left = nodes[i];
      const right = nodes[i + 1] || nodes[i]; // 奇数时复制最后一项
      const parentHash = this._hashPair(left.hash, right.hash);
      parents.push(new MerkleNode(parentHash, left, right));
    }
    return this._buildTree(parents);
  }

  private _hashPair(a: Uint8Array, b: Uint8Array): Uint8Array {
    // 比特币采用双重 SHA256：SHA256(SHA256(concat(a, b)))
    const concat = new Uint8Array(a.length + b.length);
    // 排序：较小的哈希在前（保证顺序确定性）
    if (this._compare(a, b) < 0) {
      concat.set(a, 0);
      concat.set(b, a.length);
    } else {
      concat.set(b, 0);
      concat.set(a, b.length);
    }
    // 简化：教学演示用 simple hash
    return simpleDoubleHash(concat);
  }

  private _compare(a: Uint8Array, b: Uint8Array): number {
    for (let i = 0; i < Math.min(a.length, b.length); i++) {
      if (a[i] < b[i]) return -1;
      if (a[i] > b[i]) return 1;
    }
    return a.length - b.length;
  }

  /**
   * 生成某个叶节点的 Merkle 证明
   * @param index 交易索引
   * @returns 从叶到根路径上的兄弟节点列表
   */
  getProof(index: number): Uint8Array[] {
    if (index < 0 || index >= this.leaves.length) throw new Error('Invalid index');
    
    const proof: Uint8Array[] = [];
    let currentIndex = index;
    let level = this.leaves;
    
    while (level.length > 1) {
      const isEven = currentIndex % 2 === 0;
      const siblingIndex = isEven ? currentIndex + 1 : currentIndex - 1;
      
      if (siblingIndex < level.length) {
        proof.push(level[siblingIndex].hash);
      }
      
      // 构建父层
      const parents: MerkleNode[] = [];
      for (let i = 0; i < level.length; i += 2) {
        const left = level[i];
        const right = level[i + 1] || level[i];
        const parentHash = this._hashPair(left.hash, right.hash);
        parents.push(new MerkleNode(parentHash, left, right));
      }
      
      level = parents;
      currentIndex = Math.floor(currentIndex / 2);
    }
    
    return proof;
  }

  getRoot(): Uint8Array | null {
    return this.root?.hash ?? null;
  }
}

/**
 * 简化的双重哈希（教学用）
 */
function simpleDoubleHash(data: Uint8Array): Uint8Array {
  const hash1 = new TextEncoder().encode(sha256(new TextDecoder().decode(data)));
  const hash2 = new TextEncoder().encode(sha256(new TextDecoder().decode(hash1)));
  return hash2.slice(0, 32);
}

// --- 完整流程验证 ---
console.log("=== Merkle 树验证 ===");
const txData = ["Alice->Bob: 1.0", "Bob->Charlie: 0.5", "Charlie->Dave: 0.3", "Dave->Eve: 0.2"];
const txHashes = txData.map(tx => {
  const hash = sha256(tx);
  const bytes = new Uint8Array(32);
  for (let i = 0; i < 32; i++) bytes[i] = parseInt(hash.slice(i * 2, i * 2 + 2), 16);
  return bytes;
});

const tree = new MerkleTree(txHashes);
console.log(`树根: ${Array.from(tree.getRoot()!).map(b => b.toString(16).padStart(2, '0')).slice(0, 8).join('')}...`);

// 为 tx[1] (Bob->Charlie) 生成证明
const proof = tree.getProof(1);
console.log(`\ntx[1] 的 Merkle 证明需要 ${proof.length} 个兄弟节点`);
proof.forEach((hash, i) => {
  console.log(`  层级 i+1兄弟:{i + 1} 兄弟:{Array.from(hash).map(b => b.toString(16).padStart(2, '0')).slice(0, 4).join('')}...`);
});

2.7.3 证明验证算法

轻客户端（已拥有根哈希 HrootH_{\text{root}}，来自区块头）：

text
输入：目标交易哈希 H(tx)，证明 [s1, s2, ..., s_logN]

当前 = H(tx)
对每个兄弟哈希 s_i（从叶到根的顺序）：
  if 当前在左子树: 当前 = H(当前 || s_i)
  else: 当前 = H(s_i || 当前)

返回 当前 == H_root
typescript
/**
 * 验证 Merkle 证明
 * @param targetHash 目标交易哈希
 * @param proof 兄弟节点列表（从叶到根）
 * @param root 预期的树根
 * @param index 交易在原始列表中的索引
 */
function verifyMerkleProof(
  targetHash: Uint8Array,
  proof: Uint8Array[],
  root: Uint8Array,
  index: number,
): boolean {
  let current = targetHash;
  let idx = index;
  
  for (const sibling of proof) {
    // 判断当前节点在左还是右
    if (idx % 2 === 0) {
      // 当前在左，兄弟在右
      current = simpleDoubleHash(concatBytes(current, sibling));
    } else {
      // 当前在右，兄弟在左
      current = simpleDoubleHash(concatBytes(sibling, current));
    }
    idx = Math.floor(idx / 2);
  }
  
  return arraysEqual(current, root);
}

function concatBytes(a: Uint8Array, b: Uint8Array): Uint8Array {
  const result = new Uint8Array(a.length + b.length);
  result.set(a, 0);
  result.set(b, a.length);
  return result;
}

function arraysEqual(a: Uint8Array, b: Uint8Array): boolean {
  if (a.length !== b.length) return false;
  for (let i = 0; i < a.length; i++) {
    if (a[i] !== b[i]) return false;
  }
  return true;
}

// --- 验证演示 ---
const isValid = verifyMerkleProof(txHashes[1], proof, tree.getRoot()!, 1);
console.log(`\n✅ tx[1] 证明有效: ${isValid}`);

// 尝试验证错误索引（应失败）
const fakeIndex = 2;
const fakeValid = verifyMerkleProof(txHashes[1], proof, tree.getRoot()!, fakeIndex);
console.log(`❌ 错误索引(fakeIndex)验证:{fakeIndex}) 验证:{fakeValid} (应为 false)`);

// 尝试验证篡改的数据（应失败）
const tamperedHash = new Uint8Array(txHashes[1]);
tamperedHash[0] ^= 1;
const tamperedValid = verifyMerkleProof(tamperedHash, proof, tree.getRoot()!, 1);
console.log(`❌ 篡改数据验证: ${tamperedValid} (应为 false)`);

2.7.4 Simplified Payment Verification (SPV)

核心思想

SPV 客户端不下载完整区块，只下载区块头（80 字节/块）。区块头包含：

  • 前一区块哈希
  • Merkle 根
  • 时间戳
  • 难度目标
  • Nonce
text
SPV 客户端存储的数据量:
- 完整节点: 600+ GB (比特币全部交易历史)
- SPV 客户端: 80 bytes × ~800,000 区块 ≈ 64 MB (仅区块头)
- 验证单笔交易: + 320 bytes (Merkle 证明)

SPV 验证流程

graph LR
    SPV[SPV 客户端<br/>存储: 64 MB 区块头] -- "请求\ntx237 证明" --> FN[全节点<br/>存储: 600 GB 完整链]
    FN -- "提供 320 B Merkle 证明" --> SPV
    SPV -- "验证: hash(tx237)+证明 == 区块头.Merkle根" --> OK{✅ 通过<br/>❌ 失败}
typescript
/**
 * SPV 简化验证（教学演示）
 */
class SPVClient {
  private blockHeaders: Array<{
    blockHash: Uint8Array;
    merkleRoot: Uint8Array;
    timestamp: number;
    // ... 其他字段
  }> = [];

  /**
   * 仅下载区块头（高度轻量）
   */
  addBlockHeader(header: { blockHash: Uint8Array; merkleRoot: Uint8Array; timestamp: number }): void {
    this.blockHeaders.push(header);
  }

  /**
   * 验证交易：需要全节点提供 Merkle 证明
   */
  verifyTransaction(
    txHash: Uint8Array,
    blockHeight: number,
    merkleProof: Uint8Array[],
    txIndex: number,
  ): boolean {
    if (blockHeight < 0 || blockHeight >= this.blockHeaders.length) {
      throw new Error('Unknown block');
    }
    const header = this.blockHeaders[blockHeight];
    return verifyMerkleProof(txHash, merkleProof, header.merkleRoot, txIndex);
  }
}

const spv = new SPVClient();
spv.addBlockHeader({
  blockHash: new Uint8Array(32), // 占位
  merkleRoot: tree.getRoot()!,
  timestamp: Date.now(),
});

const spvValid = spv.verifyTransaction(txHashes[1], 0, proof, 1);
console.log(`\n=== SPV 验证结果 ===`);
console.log(`SPV 验证 tx[1]: ${spvValid ? '✅ 交易确认包含在区块中' : '❌ 验证失败'}`);

SPV 的安全假设

SPV 客户端信任区块头（通过 PoW 验证）和全节点提供的 Merkle 证明。它不能验证：

  • 双花攻击（除非监听更多网络节点）
  • 共识规则的完全合规（依赖全节点诚实）
  • 当前余额（需追踪所有输入）

因此 SPV 适合验证特定交易是否被确认（如"我收到的付款是否已上链"），但不适合作为完整节点的替代。

2.7.5 Patricia Merkle Tree（以太坊的状态树）

比特币的 Merkle 树仅用于交易列表。以太坊使用更复杂的 Patricia Trie（前缀树 + 压缩） 和 Merkle Patricia Trie（MPT） 来存储：

  • 状态树（State Trie）：账户地址 → 账户状态（nonce, balance, codeHash, storageRoot）
  • 存储树（Storage Trie）：每个合约的局部键值存储
  • 交易树（Transaction Trie）：当前区块的交易
  • 收据树（Receipt Trie）：交易收据（gas 使用、日志等）

以太坊的 MPT 使用三种节点类型：

  1. 叶子节点（Leaf）：存储键值对的最终值
  2. 扩展节点（Extension）：压缩单一路径上的连续节点
  3. 分支节点（Branch）：最多 16 个子节点 + 1 个值槽
text
存储少量地址的 MPT 示例:

                    [ , , , , [_extension: , 
                   0xe7] , , , ,...]
                       |
             [branch: 0 → ac, 1 → 9b, ...]
             /                           \
    [leaf: {address1}]              [extension: 35]
                                       |
                            [branch: 0 → leaf2, ...]

这种结构允许以太坊轻客户端用类似 SPV 的方式验证"某个地址的余额是否为 XX"，通过提供从根到叶的路径证明。

核心认知

  1. Merkle 树将证明大小从 O(N)O(N) 降到 O(log⁡N)O(\log N)。 对于 4000 笔交易/区块的比特币，所需证明从 ≈ 1 MB 降到 ≈ 480 字节。
  1. 哈希箱结构天然防止篡改。 如果攻击者修改任何一笔交易，计算出的根哈希将完全不同，与区块头中的存储值不符。这就是 Merkle 树作为"密码学累加器"的价值。
  1. SPV 是信任与效率的权衡。 64 MB 的区块头存储 vs 600 GB 的完整链——代价是信任全节点提供的证明，以及无法独立检测双花。
  1. 以太坊的 MPT 是 Merkle 树的进化。 从有序列表的验证扩展到任意键值存储的验证，支撑了智能合约的复杂状态管理。

下一预告：2.8 将跳出具体实现，从系统对比角度审视所有密码学原语——哈希、签名、对称/非对称加密——在区块链中的角色分工，并总结常见工程错误。

返回 区块链 教程列表

评论

0

评论加载中…

发表评论

0/2000