第 5 讲：Merkle 树与包含证明

一、一个具体需求

你的手机钱包收到一笔转账。你想确认：这笔交易真的被打包进了第 900000 号区块吗？

最笨的办法是把整个区块下载下来，检查里面有没有你那笔。但一个比特币区块最大约 4 MB，一个以太坊区块也有百 KB 到 MB 级——而你只关心其中一笔。

有没有办法，只下载几百字节就能确信？

有。这就是 Merkle 树要解决的问题：

⭐ 给定一个「集合的摘要」，如何用远小于集合大小的证据，证明某个元素在这个集合里？

二、构造

打个比方

想象一场淘汰赛的对阵表。

一千个选手两两捉对，赢的进下一轮，最后剩一个冠军。现在有人问你：“第 387 号选手真的参加过这场比赛吗？”

你不需要把全部一千人的名单给他。你只需要给出这一条晋级路线上、每一轮的对手是谁——大约十个名字。他顺着这十场比赛一路推上去，如果最后推出的冠军和公布的冠军一致，那么第 387 号必定在这一千人里。

改动任何一个人，都会导致上面某一场的结果对不上，最后推出来的冠军就不一样了。

⭐ Ralph Merkle 1979 年的想法就是这个：两两哈希，一层层往上合并。 那个"冠军"是根哈希，那"十个对手"就是 Merkle 证明。

以 8 笔交易为例：

                        Root
                   ┌──────┴──────┐
                 H(AB)         H(CD)         ← 第 2 层
              ┌────┴────┐   ┌────┴────┐
            H(A)      H(B) H(C)     H(D)     ← 第 1 层
          ┌──┴──┐  ┌──┴──┐ ...
         h₀    h₁  h₂    h₃  h₄  h₅  h₆  h₇   ← 叶子 = 每笔交易的哈希
         │     │   │     │
        tx₀   tx₁ tx₂   tx₃ tx₄ tx₅ tx₆ tx₇

规则：

叶子节点：   leaf(i) = H(0x00 ‖ txᵢ)          ⚠️ 前缀的作用见第六节
内部节点：   node    = H(0x01 ‖ 左 ‖ 右)
根：         Root —— 只有 32 字节，放进区块头

⭐ 关键性质：改动任何一笔交易，它上面那条路径的所有哈希都会变，最终 Root 一定变。Root 是整个交易集合的一个 32 字节承诺。

三、包含证明

⭐ 这就是那条晋级路线：你只给出沿路每一轮的对手，不给整张对阵表。 下面看它具体有多小。

现在回到需求。要证明 tx₂ 在树里，需要给出什么？

                        Root
                   ┌──────┴──────┐
                 H(AB)         [H(CD)]  ← ③ 需要
              ┌────┴────┐
            [H(A)]    H(B)               ← ② 需要
                    ┌──┴──┐
                   h₂    [h₃]            ← ① 需要
                    │
                  tx₂  ← 要证明的交易

只需要三个哈希：h₃、H(A)、H(CD)——也就是从叶子到根这条路径上，每一层的兄弟节点。

验证过程：

① 自己算 h₂ = H(0x00 ‖ tx₂)
② 用 h₃ 合并：       H(B)  = H(0x01 ‖ h₂ ‖ h₃)          ← tx₂ 是左边，所以兄弟在右
③ 用 H(A) 合并：     H(AB) = H(0x01 ‖ H(A) ‖ H(B))      ← 这次自己在右
④ 用 H(CD) 合并：    Root' = H(0x01 ‖ H(AB) ‖ H(CD))
⑤ 检查 Root' == 区块头里的 Root

⚠️ 注意第 ②③ 步的方向不同——所以证明里除了兄弟哈希，还必须记录自己在左边还是右边。方向搞反是实现这个算法最常见的 bug。

大小

树高是 log₂ n，所以证明包含 log₂ n 个哈希：

交易数	证明大小
8	3 × 32 = 96 字节
1,024	10 × 32 = 320 字节
1,000,000	20 × 32 = 640 字节
10 亿	30 × 32 = 960 字节

⭐ 一百万笔交易，640 字节就能证明其中任意一笔的存在。 这就是轻客户端（第 13 讲）能在手机上运行的原因。

但要注意它证明了什么、没证明什么：

✅ 证明了：tx₂ 在这个 Root 所承诺的集合里
❌ 没证明：这个 Root 是"正确的链"上的
❌ 没证明：tx₂ 本身是合法的（签名有效、没有双花）

第 13 讲会讲轻客户端如何补上这两条，以及它必须付出的信任代价。

四、坑一：CVE-2012-2459

真实世界里，交易数很少正好是 2 的幂。奇数个节点怎么办？

比特币的做法是：复制最后一个。

3 个叶子： [h₀, h₁, h₂]
补齐成：   [h₀, h₁, h₂, h₂]   ← 把 h₂ 复制一份

这个决定引入了一个严重漏洞。观察下面两个区块：

区块 X 的交易列表： [A, B, C]
  第 0 层： h(A), h(B), h(C)  → 补齐 → h(A), h(B), h(C), h(C)
  第 1 层： H(h(A),h(B)),  H(h(C),h(C))
  Root_X = H( H(h(A),h(B)), H(h(C),h(C)) )

区块 Y 的交易列表： [A, B, C, C]   ← ⚠️ C 出现了两次
  第 0 层： h(A), h(B), h(C), h(C)   ← 已经是偶数，不用补
  第 1 层： H(h(A),h(B)),  H(h(C),h(C))
  Root_Y = H( H(h(A),h(B)), H(h(C),h(C)) )

⟹  Root_X == Root_Y   完全相同！

两个交易列表不同的区块，Merkle 根却一样。 而区块头里只有 Root，所以两个区块的区块哈希也完全相同。

攻击怎么进行

① 矿工挖出合法区块 X = [A, B, C]，广播
② 攻击者截获，构造 Y = [A, B, C, C]，转发给受害节点
③ 受害节点验证：
      区块头哈希 ✅（和 X 一样）
      Merkle 根 ✅（和 X 一样）
      交易内容 ❌ —— C 出现两次，这是双花，区块无效
④ 节点把"这个区块哈希"记入无效缓存
⑤ ⚠️ 真正的区块 X 到达时，节点一看哈希已在无效列表 → 直接丢弃
⟹ 该节点永久停在旧链上，与全网分叉

⭐ 这是一个「永久 DoS」：不需要算力，只需要转发一个变异区块，就能让一个全节点掉队。

修复

比特币 0.6.3 的修复很直接：计算 Merkle 根时，如果某一层出现了重复的相邻节点，直接判定区块无效。

⭐ 更根本的教训：Merkle 树的构造必须保证「树 → 根」是单射的。任何两个不同的叶子序列都必须给出不同的根。比特币的复制策略破坏了这一点。

更好的做法（多数现代系统采用）：在叶子哈希里编码总数，或者干脆不补齐，允许不平衡树。

五、坑二：第二原像攻击与域分隔

再看一个更微妙的问题。假设我们不加第二节里的 0x00 / 0x01 前缀：

leaf(i) = H(txᵢ)
node    = H(左 ‖ 右)

考虑一棵 4 叶子的树：

Root = H( H(h₀‖h₁) ‖ H(h₂‖h₃) )

现在攻击者宣称：这其实是一棵只有 2 个叶子的树，两个叶子分别是 (h₀‖h₁) 和 (h₂‖h₃) 这两串 64 字节数据：

攻击者的"树"： Root = H( leaf'₀ ‖ leaf'₁ )
    其中 leaf'₀ = h₀‖h₁ ，leaf'₁ = h₂‖h₃

验证者算：H( H(leaf'₀) ‖ H(leaf'₁) ) ...

这里的核心问题是：内部节点的值和叶子的值来自同一个哈希函数，无法区分。攻击者可以把一棵树的内部节点冒充成叶子，从而对同一个 Root 给出一个完全不同的"原像"。

修复：域分隔（domain separation）

leaf(x) = H(0x00 ‖ x)
node    = H(0x01 ‖ 左 ‖ 右)

⭐ 加一个字节的前缀，叶子哈希和内部节点哈希就落在两个不相交的空间里，冒充不可能发生。

这是 RFC 6962（Certificate Transparency）确立的标准做法，如今几乎所有新系统都遵循。⚠️ 比特币没有这么做——它靠"叶子必须是合法交易的序列化"这一额外约束来间接防御，但这是一个更脆弱的保证。

六、Go 实现

package merkle

import (
	"bytes"
	"crypto/sha256"
	"errors"
)

const (
	leafPrefix = 0x00 // ⚠️ 域分隔：防止内部节点被冒充成叶子
	nodePrefix = 0x01
)

func hashLeaf(data []byte) []byte {
	h := sha256.New()
	h.Write([]byte{leafPrefix})
	h.Write(data)
	return h.Sum(nil)
}

func hashNode(left, right []byte) []byte {
	h := sha256.New()
	h.Write([]byte{nodePrefix})
	h.Write(left)
	h.Write(right)
	return h.Sum(nil)
}

// Tree 保存每一层的节点，levels[0] 是叶子层。
type Tree struct {
	levels [][][]byte
}

// New 构建 Merkle 树。
// 奇数节点时不复制最后一个（那会导致 CVE-2012-2459），
// 而是把它原样提升到上一层。这样"叶子序列 → 根"仍然是单射的。
func New(items [][]byte) (*Tree, error) {
	if len(items) == 0 {
		return nil, errors.New("merkle: 空集合")
	}

	level := make([][]byte, len(items))
	for i, it := range items {
		level[i] = hashLeaf(it)
	}

	t := &Tree{levels: [][][]byte{level}}
	for len(level) > 1 {
		next := make([][]byte, 0, (len(level)+1)/2)
		for i := 0; i < len(level); i += 2 {
			if i+1 == len(level) {
				next = append(next, level[i]) // 落单的节点直接上提
			} else {
				next = append(next, hashNode(level[i], level[i+1]))
			}
		}
		t.levels = append(t.levels, next)
		level = next
	}
	return t, nil
}

func (t *Tree) Root() []byte { return t.levels[len(t.levels)-1][0] }

// Step 是证明路径上的一步：一个兄弟哈希，以及它在左还是在右。
type Step struct {
	Hash    []byte
	IsRight bool // true 表示兄弟在右边（即自己在左边）
}

// Proof 生成第 index 个元素的包含证明。
func (t *Tree) Proof(index int) ([]Step, error) {
	if index < 0 || index >= len(t.levels[0]) {
		return nil, errors.New("merkle: 下标越界")
	}
	var path []Step
	for lv := 0; lv < len(t.levels)-1; lv++ {
		level := t.levels[lv]
		if index%2 == 0 {
			if index+1 < len(level) { // 有右兄弟
				path = append(path, Step{Hash: level[index+1], IsRight: true})
			}
			// 落单节点被直接上提，这一层不产生证明步骤
		} else {
			path = append(path, Step{Hash: level[index-1], IsRight: false})
		}
		index /= 2
	}
	return path, nil
}

// Verify 在只知道 root 的情况下验证 item 属于集合。
// 验证方不需要任何其他数据——这正是轻客户端能工作的原因。
func Verify(root, item []byte, path []Step) bool {
	cur := hashLeaf(item)
	for _, s := range path {
		if s.IsRight {
			cur = hashNode(cur, s.Hash)
		} else {
			cur = hashNode(s.Hash, cur)
		}
	}
	return bytes.Equal(cur, root)
}

⚠️ 注意 Verify 的签名：它只需要 root、item 和 path。不需要树，不需要其他任何交易。 这个函数可以跑在手机上、跑在智能合约里——第七节的空投白名单用的就是它。

七、Merkle 树在区块链里出现在哪

位置	承诺了什么	用途
交易根（每个区块头）	本块所有交易	轻客户端验证"我的交易被打包了"
收据根（以太坊）	所有交易的执行结果与日志	验证"这个事件真的发生了"
状态根（以太坊）	全部账户与合约存储	用的是 Merkle Patricia Trie，第 12 讲
空投白名单	几万个地址	合约里只存 32 字节的根，用户领取时自带证明
数据可用性采样	一个大数据块的所有分片	第 29 讲

⭐ 空投白名单是最能体现价值的例子：如果把 10 万个地址直接写进合约，Gas 成本高到不可行；用 Merkle 根只需存 32 字节，每个用户领取时自己提供 17 个哈希的证明。成本从 O(n) 变成 O(1) 存储 + O(log n) 验证。

八、排序 Merkle 树与不存在性证明

标准 Merkle 树能证明"在里面"，不能证明"不在里面"——因为你无法穷举所有可能。

但如果把叶子按键排序，就可以：

排序后的叶子： ... , key=15 , key=42 , ...
                        ↑        ↑
要证明 key=30 不存在：
   给出相邻的两个叶子 15 和 42 各自的包含证明，
   并且它们在树中是相邻的。
   ⟹ 因为有序，15 和 42 之间不可能存在 30

⭐ 这个技巧叫区间证明（range proof）或不存在性证明。第 12 讲的 Merkle Patricia Trie 通过键的路径结构提供了同样的能力。

九、本讲小结

⭐ Merkle 树解决的问题：用远小于集合大小的证据，证明某元素属于一个由 32 字节摘要承诺的集合。
构造：叶子 = 数据哈希，内部节点 = 两个子节点的哈希，根放进区块头。改动任何叶子必然改变根。
⭐ 包含证明只需 log₂ n 个哈希。一百万笔交易 → 640 字节。这是轻客户端能跑在手机上的根本原因。
证明里必须记录左右方向，方向搞反是最常见的实现 bug。
它证明的是"在集合里"，不是"交易合法"，也不是"这条链是主链"。
CVE-2012-2459：比特币在奇数节点时复制最后一个，导致 [A,B,C] 和 [A,B,C,C] 的 Merkle 根相同 ⟹ 攻击者可让节点把合法区块永久标记为无效，造成永久 DoS。根本教训：「叶子序列 → 根」必须是单射。
缺少域分隔会导致第二原像攻击：内部节点可以被冒充成叶子。修复是给叶子和内部节点加不同的一字节前缀（RFC 6962）。
空投白名单是最典型的应用：合约只存 32 字节根，存储成本从 O(n) 降到 O(1)。
把叶子排序，就能证明"不存在"——给出相邻两个叶子即可。

思考题

一个区块有 5,000 笔交易，包含证明有多大？如果交易数翻 1000 倍，证明大小变成多少？
为什么证明里必须记录"兄弟在左还是在右"？举一个方向搞反导致验证通过的例子（或说明为什么不会）。
完整推演 CVE-2012-2459：给出 [A,B,C] 和 [A,B,C,C] 每一层的哈希，说明为什么根相同。
除了"检测重复相邻节点"，还有什么办法能修复这个漏洞？比较各自的代价。
域分隔攻击中，攻击者需要满足什么条件才能成功？为什么比特币实际上没有因此被攻击？
上面的 Go 实现中，落单节点被直接上提。请证明这个策略下"叶子序列 → 根"是单射的。
设计一个空投合约：10 万个地址，每人可领固定数量。写出合约需要存什么、用户提交什么、合约怎么防止重复领取。
排序 Merkle 树能证明不存在。如果攻击者控制了树的构造，他能伪造一个"不存在证明"吗？需要什么额外假设？

一、一个具体需求#

二、构造#

打个比方#

三、包含证明#

大小#

四、坑一：CVE-2012-2459#

攻击怎么进行#

修复#

五、坑二：第二原像攻击与域分隔#

修复：域分隔（domain separation）#

六、Go 实现#

七、Merkle 树在区块链里出现在哪#

八、排序 Merkle 树与不存在性证明#

九、本讲小结#

思考题#