第 4 讲：哈希函数——三种抗性与它们的区别

你想向别人证明"我早在上周就猜到了今天的比分"，但又不想提前把答案告诉他。

办法是：上周你把答案写在纸上，装进信封封好交给他；今天当着他的面拆开。

哈希函数就是这个信封的数字版——而且它比信封更好：你不用把信封交给任何人保管，只需要报出一串数字。

密码学在区块链里用得其实很少——只有四样：哈希、Merkle 树、签名、承诺。这个单元从零讲起，不假设任何背景。先从最基础也用得最多的一个开始。

一、哈希函数是什么

H : {0,1}*  →  {0,1}ⁿ
    任意长度      固定 n 位

SHA-256 的 n = 256。无论你输入 1 个字节还是 10 GB，输出都是 32 字节。

它必须满足两条基本要求：

确定性：同样的输入永远给出同样的输出
高效：计算很快（这既是优点也是缺点——第 15 讲会看到 PoW 反过来利用了这一点）

雪崩效应

一个好的哈希函数，输入改一个比特，输出应该有大约一半的比特发生变化：

SHA-256("hello") = 2cf24dba5fb0a30e26e83b2ac5b9e29e1b161e5c1fa7425e73043362938b9824
SHA-256("hellp") = fdd7585e08c4e2afd71dcabdb4636c89d557a3f42db9e2040c8bbd1708aa4ce7
                   ⚠️ 只改了最后一个字母（o → p）

两个输出的 256 个比特中，有 131 个不同 —— 约 51%

⭐ 雪崩效应是"不可预测"的具象表现：你无法通过微调输入来"接近"某个目标输出。第 15 讲的工作量证明完全建立在这一点上——除了一个一个试，没有别的办法。

二、三种抗性

这三条经常被混为一谈，但它们是不同强度的三个性质，而且区块链的不同场景依赖的是不同的那一条。

① 抗原像性（Preimage Resistance）

给定 h，找出任意一个 m 使得 H(m) = h 在计算上不可行。

俗称"单向性"。这是"哈希不可逆"这句话的准确含义。

已知：h = 2cf24dba...
求：  m = ?
⟹ 只能穷举，期望 2ⁿ 次

② 抗第二原像性（Second Preimage Resistance）

给定一个特定的 m₁，找出 m₂ ≠ m₁ 使得 H(m₂) = H(m₁) 在计算上不可行。

已知：m₁ = "Alice 转账 10 元给 Bob"
求：  m₂ = 任何其他内容，但哈希值相同
⟹ 期望 2ⁿ 次

③ 抗碰撞性（Collision Resistance）

找出任意一对 m₁ ≠ m₂ 使得 H(m₁) = H(m₂) 在计算上不可行。

⚠️ 注意这里的差别：攻击者可以自由选择两个消息，不需要匹配某个给定的目标。这个自由度让攻击大幅变容易——下一节会看到，只需要 2^(n/2) 次。

三者的关系

抗碰撞  ⟹  抗第二原像        （强的推出弱的）
抗碰撞  ⟹̸  抗原像            ⚠️ 不成立！

第二条常被误认为成立，但有一个简单的反例：

构造 H'(m):
    若 m 的第一个比特是 0 ⟹ 返回 0 ‖ m 的剩余部分（直接暴露！）
    否则                  ⟹ 返回 1 ‖ H(m)

⟹ H' 仍然抗碰撞（因为 H 抗碰撞，两个分支的输出前缀不同不会互撞）
⟹ 但 H' 完全不抗原像（一半的输入直接从输出读出来）

⭐ 所以"抗碰撞"和"单向"是两件独立的事，一个函数可以有其一而无其二。实践中我们要求密码学哈希三条全部满足。

哪个场景依赖哪一条

场景	依赖的性质	为什么
区块哈希链接（第 9 讲）	抗第二原像	攻击者要替换一个已有的区块
Merkle 树（第 5 讲）	抗碰撞	攻击者可以构造两棵树，自由选择两边
承诺方案（第 8 讲）	抗碰撞 + 隐藏性	承诺者自己就是攻击者，两个值都由他选
地址派生（第 6 讲）	抗原像	从地址反推公钥必须不可行
工作量证明（第 15 讲）	不可预测性	需要的是"只能穷举"

凡是"攻击者能同时选择两个输入"的场景，都必须按抗碰撞的标准来衡量安全性——而它只有一半的比特数。

三、生日攻击：为什么 256 位只有 128 位安全

这是密码学里最反直觉、也最重要的一个结论。

生日悖论

一个房间里要有多少人，才能让"存在两人同一天生日"的概率超过 50%？

直觉答案是 183（365 的一半）。正确答案是 23。

原因在于：我们要找的不是"有人和某个特定的人同生日"，而是"任意两人同生日"。23 个人有 C(23,2) = 253 对，每对同生日的概率是 1/365：

无碰撞概率 ≈ (1 − 1/365)^253 ≈ 0.4995
⟹ 有碰撞概率 ≈ 50.05%

推广到哈希

对 n 位输出（共 2ⁿ 种可能），找到一对碰撞需要的尝试次数是：

约 √(2ⁿ) = 2^(n/2)

⭐ 于是每种攻击的实际成本是：

攻击类型	成本	SHA-256 的实际安全级别
找原像	`2ⁿ`	256 位
找第二原像	`2ⁿ`	256 位
找碰撞	`2^(n/2)`	128 位

⚠️ 一个 256 位的哈希只提供 128 位的碰撞安全性。 这就是为什么密码学哈希的输出位数看起来"过分长"——它必须按最弱的那条来设计。

这也解释了历史：

MD5   （128 位）→ 碰撞安全只有 64 位  → 2004 年被攻破，如今笔记本几秒钟出碰撞
SHA-1 （160 位）→ 碰撞安全只有 80 位  → 2017 年 Google "SHAttered" 给出实际碰撞
SHA-256（256 位）→ 碰撞安全 128 位     → 目前无已知有效攻击

⚠️ 注意 MD5 和 SHA-1 被攻破的是抗碰撞性，抗原像性至今仍然成立。 所以"MD5 被破解了"这句话经常被误解——你的 MD5 密码哈希被破，靠的是彩虹表和弱口令，不是 MD5 的碰撞攻击。

四、长度扩展攻击与双 SHA-256

Merkle–Damgård 结构

SHA-1、SHA-2（含 SHA-256）都用这个结构处理任意长输入：

消息切成固定大小的块，逐块压缩，前一块的输出是后一块的输入

IV ──▶[压缩]──▶[压缩]──▶[压缩]──▶ 输出
        ↑        ↑        ↑
       块1      块2   块3(含填充)

⚠️ 问题在于：最终输出就是最后一个压缩函数的完整内部状态。

攻击

假设服务器用 H(secret ‖ message) 作为消息认证码，攻击者知道 message 和这个哈希值，但不知道 secret：

攻击者拿到：  tag = H(secret ‖ "amount=10")
              且知道 secret 的长度

攻击者可以计算出：
              H(secret ‖ "amount=10" ‖ padding ‖ "&amount=10000")

⚠️ 全程不需要知道 secret 是什么！

因为 tag 就是内部状态，攻击者只要从这个状态继续压缩新数据即可。

三种应对

① 双重哈希：SHA-256(SHA-256(m))        ← 比特币的选择
   外层的输入是固定 32 字节，无法被扩展

② HMAC：HMAC(k, m) = H(k⊕opad ‖ H(k⊕ipad ‖ m))
   标准做法，TLS 等协议使用

③ 换结构：SHA-3 / Keccak 使用海绵（sponge）结构
   ⭐ 内部状态比输出长，输出只是状态的一部分 ⟹ 原理上免疫

⭐ 比特币几乎所有地方都用 SHA-256d（双重 SHA-256）：区块哈希、交易 ID、Merkle 树、PoW 谜题。中本聪没有解释原因，普遍认为是出于对长度扩展的保守防御。

五、Keccak-256 不是 SHA3-256

这是一个真实会让人踩坑的细节。

以太坊在 2015 年上线时，采用了 Keccak 算法。但 NIST 在 2015 年标准化 SHA-3 时修改了填充规则（在填充中加入了域分隔位），而以太坊没有跟进。结果：

以太坊的 keccak256("")  = c5d2460186f7233c927e7db2dcc703c0e500b653ca82273b7bfad8045d85a470
标准的  SHA3-256("")    = a7ffc6f8bf1ed76651c14756a061d662f580ff4de43b49fa82d80a4b80f8434a
                          ⚠️ 完全不同

⚠️ 所以在 Go 里用 golang.org/x/crypto/sha3 的 sha3.New256() 算出来的值，和 Solidity 的 keccak256() 对不上。 必须用 sha3.NewLegacyKeccak256()。

这个坑每年都有人踩，症状是"我在链下算的签名哈希和链上验不过"。

六、Go 代码

package main

import (
	"crypto/sha256"
	"encoding/hex"
	"fmt"

	"golang.org/x/crypto/sha3"
)

// SHA256d 是比特币使用的双重 SHA-256。
func SHA256d(data []byte) [32]byte {
	first := sha256.Sum256(data)
	return sha256.Sum256(first[:])
}

// Keccak256 是以太坊使用的哈希，⚠️ 注意必须用 NewLegacyKeccak256，
// 而不是 sha3.New256()——后者是 NIST 标准 SHA3-256，填充规则不同。
func Keccak256(data []byte) []byte {
	h := sha3.NewLegacyKeccak256()
	h.Write(data)
	return h.Sum(nil)
}

// countDiffBits 统计两个等长字节切片有多少比特不同，用于观察雪崩效应。
func countDiffBits(a, b []byte) int {
	n := 0
	for i := range a {
		x := a[i] ^ b[i]
		for x != 0 {
			n += int(x & 1)
			x >>= 1
		}
	}
	return n
}

func main() {
	h1 := sha256.Sum256([]byte("hello"))
	h2 := sha256.Sum256([]byte("hellp"))

	fmt.Println("SHA-256(hello) =", hex.EncodeToString(h1[:]))
	fmt.Println("SHA-256(hellp) =", hex.EncodeToString(h2[:]))
	fmt.Printf("不同比特数：%d / 256\n", countDiffBits(h1[:], h2[:])) // 131 / 256

	d := SHA256d([]byte("hello"))
	fmt.Println("SHA-256d       =", hex.EncodeToString(d[:]))
	fmt.Println("Keccak-256     =", hex.EncodeToString(Keccak256([]byte(""))))
	// c5d2460186f7233c927e7db2dcc703c0e500b653ca82273b7bfad8045d85a470
}

七、哈希在区块链里的四种用途

这四种用途分别依赖不同的性质，值得分开记：

① 指针 —— 把"引用"变成"承诺"

普通指针存的是地址，哈希指针存的是内容的哈希：

普通链表：  [数据|→]  →  [数据|→]  →  [数据|nil]
哈希链：    [数据|H(前一块)] ← 改动任何一块，后面所有哈希全部失效

⭐ 这就是"区块链"这个名字的来源，第 9 讲展开。它依赖抗第二原像性。

② 承诺 —— 先锁定，后揭示

我先公布 c = H(x ‖ r)      ← 承诺（r 是随机数）
稍后公布 x 和 r            ← 揭示
你验证 H(x ‖ r) == c

⭐ 抗碰撞性保证我不能事后改主意（无法找到另一对 (x', r') 撞上同一个 c）。第 8 讲会讲为什么必须加随机数 r。

③ 谜题 —— 工作量证明

找 nonce 使得 H(区块头 ‖ nonce) < 目标值

由于雪崩效应，除了穷举没有捷径。这让"计算"变成了可验证的稀缺资源（第 15 讲）。

④ 派生 —— 压缩标识符

比特币地址 = Base58Check(RIPEMD160(SHA256(公钥)))
以太坊地址 = Keccak256(公钥)[12:]         ← 取后 20 字节

把 33/65 字节的公钥压成 20 字节，同时在公钥公开之前提供一层额外保护（第 6 讲）。

八、本讲小结

哈希 = 任意长输入 → 固定长输出，确定 + 高效 + 雪崩。⭐ 雪崩效应是"只能穷举"的基础，PoW 完全依赖它。
三种抗性强度不同：抗原像（给 h 找 m）、抗第二原像（给定 m₁ 找 m₂）、抗碰撞（自由找一对）。
⚠️ 抗碰撞 ⟹ 抗第二原像，但抗碰撞 ⟹̸ 抗原像——可以构造出抗碰撞却完全不单向的函数。
生日攻击：n 位输出只有 n/2 位的碰撞安全性。 找碰撞只需 2^(n/2) 次，因为攻击者能自由选两边。SHA-256 的碰撞安全是 128 位，不是 256 位。
MD5 和 SHA-1 被攻破的是抗碰撞性，抗原像性至今成立。 “MD5 被破解"常被误解。
凡是攻击者能同时选择两个输入的场景（Merkle 树、承诺），都必须按抗碰撞标准衡量，安全性减半。
长度扩展攻击源于 Merkle–Damgård 结构：输出就是完整内部状态，攻击者可以在不知道密钥的情况下续写。应对有三：双重哈希（比特币）、HMAC、换成海绵结构（SHA-3）。
以太坊的 keccak256 ≠ 标准 SHA3-256，填充规则不同，输出完全不同。Go 里必须用 sha3.NewLegacyKeccak256()。
四种用途各依赖不同性质：哈希指针（抗第二原像）、承诺（抗碰撞）、PoW 谜题（不可预测）、地址派生（抗原像）。

思考题

用自己的话说清楚抗第二原像和抗碰撞的区别，并解释为什么后者的攻击成本低得多。
验证第二节那个反例：为什么 H' 仍然抗碰撞，却完全不抗原像？
一个 128 位输出的哈希，找碰撞需要约多少次尝试？如果每秒能算 10¹² 次，需要多久？
为什么区块链接只需要抗第二原像，而 Merkle 树需要抗碰撞？请给出一个"攻击者自由选择两边"的具体场景。
服务器用 H(secret ‖ msg) 做认证。写出长度扩展攻击的完整步骤，说明攻击者需要知道哪些信息。
为什么 SHA-3 的海绵结构天然免疫长度扩展攻击？（提示：想想输出和内部状态的长度关系）
你在 Go 里算出的哈希和 Solidity 的 keccak256() 对不上，列出三个可能的原因并说明怎么逐一排查。
比特币地址用了 RIPEMD160(SHA256(pubkey)) 两层哈希。这样做的碰撞安全性是多少位？为什么不直接用 SHA-256 截断？

一、哈希函数是什么#

雪崩效应#

二、三种抗性#

① 抗原像性（Preimage Resistance）#

② 抗第二原像性（Second Preimage Resistance）#

③ 抗碰撞性（Collision Resistance）#

三者的关系#

哪个场景依赖哪一条#

三、生日攻击：为什么 256 位只有 128 位安全#

生日悖论#

推广到哈希#

四、长度扩展攻击与双 SHA-256#

Merkle–Damgård 结构#

攻击#

三种应对#

五、Keccak-256 不是 SHA3-256#

六、Go 代码#

七、哈希在区块链里的四种用途#

① 指针 —— 把"引用"变成"承诺"#

② 承诺 —— 先锁定，后揭示#

③ 谜题 —— 工作量证明#

④ 派生 —— 压缩标识符#

八、本讲小结#

思考题#