密码学基石：哈希、签名与Merkle世界树

第 1 章 密码学基石：哈希、签名与 Merkle 世界树

去中心化账本的"魔法"并不依赖任何可信机构，而只依赖数学。比特币白皮书开篇即点明：所谓"不可否认的历史"，本质上是把每一笔交易压成一段不可逆的指纹，再把这些指纹通过树形结构聚合成一个全网唯一的根。任何对历史的篡改都会使根值变化，任何人都可以零成本地验证这一变化。本章沿三条主轴拆解这个机制——哈希函数提供数据完整性的"原子"，椭圆曲线签名提供身份与意图的"墨水"，Merkle 树及其变体则提供聚合与可验证性的"骨架"。三条主轴合在一起，构成一切链上协议的密码学底座。

1.1 密码学哈希函数：从 SHA-2 到 Keccak-256

1.1.1 三性质的形式化定义

哈希函数 $H: \{0,1\}^* \to \{0,1\}^n$ 在区块链语境下必须满足三项性质，按强度递增排列：

抗原像性（Pre-image Resistance）：给定 $y \in \{0,1\}^n$，在多项式时间内找到任意 $x$ 使得 $H(x)=y$ 不可行。即对任意概率多项式时间敌手 $\mathcal{A}$， $$\Pr_{x \leftarrow \{0,1\}^*}[\mathcal{A}(H(x)) = x] \le \mathsf{negl}(\lambda)$$ 其中 $\lambda$ 是安全参数。这保证攻击者无法"反推"出产生某个摘要的原始交易。

抗第二原像性（Second Pre-image Resistance）：给定 $x_1$，找到 $x_2 \neq x_1$ 使得 $H(x_1)=H(x_2)$ 不可行。形式化地： $$\Pr_{x_1 \leftarrow \{0,1\}^*}[\mathcal{A}(x_1) = x_2 \land x_2 \neq x_1 \land H(x_1)=H(x_2)] \le \mathsf{negl}(\lambda)$$ 这是区块链抗篡改的核心——一旦区块哈希被广播，攻击者无法在不重算工作量的情况下找到第二份产生相同摘要的区块。

抗碰撞性（Collision Resistance）：找到任意 $(x_1, x_2)$ 满足 $x_1 \neq x_2 \land H(x_1)=H(x_2)$ 不可行。 $$\Pr[\mathcal{A}() = (x_1, x_2) \land x_1 \neq x_2 \land H(x_1)=H(x_2)] \le \mathsf{negl}(\lambda)$$ 注意抗碰撞性严格强于抗第二原像性——攻击者可以自由选择两个输入碰撞比固定一个输入找碰撞要容易得多。生日攻击给出 $O(2^{n/2})$ 的下界，这也是为何所有主流区块链选择 $n \ge 256$ 位摘要（相当于 128 位安全级别）。

1.1.2 SHA-256 的内部结构

SHA-256 由 NIST 于 2001 年标准化，遵循 Merkle–Damgård 迭代结构：先将消息填充至 512 位的整数倍，然后由 64 轮压缩函数 $C$ 迭代处理： $$H_i = C(H_{i-1}, M_i), \quad H_0 = \text{IV}$$ 其中初始向量 IV 是 8 个 32 位常量，最终摘要为 $H_k$。

每轮的核心是一个工作在 8 个 32 位工作变量 $(a,b,c,d,e,f,g,h)$ 上的"加法-异或-旋转"型布尔函数： $$T_1 = h + \Sigma_1(e) + \text{Ch}(e,f,g) + K_t + W_t$$ $$T_2 = \Sigma_0(a) + \text{Maj}(a,b,c)$$ $$\{h,g,f,e,d,c,b,a\} \leftarrow \{g,f,e,d+T_1,c,b,a,T_1+T_2\}$$ 其中 $\text{Ch}(x,y,z) = (x \land y) \oplus (\lnot x \land z)$，$\text{Maj}(x,y,z) = (x \land y) \oplus (x \land z) \oplus (y \land z)$ 是两个经典 S 盒。这种 ARX（Add-Rotate-XOR）构造在 x86 指令集上有极佳的常量时间实现，代价是易受长度扩展攻击——给定 $H(m)$ 与 $\lvert m \rvert$，攻击者无需知道 $m$ 即可计算 $H(m \Vert \text{pad})$。

1.1.3 Keccak-256 与海绵构造

以太坊选用 Keccak-256（SHA-3 标准化前的原始版本）而非 SHA-256，关键差异在于 Keccak 采用海绵（Sponge）构造而非 Merkle–Damgård：

```text 吸收阶段：state = 0; for each block: state = f(state ⊕ block); rate = state[0:r] 挤压阶段：output = state[0:r]; while need more: state = f(state); output += state[0:r] ```

海绵构造对长度扩展攻击天然免疫，因为输出不暴露中间状态。Keccak-256 取速率 $r=1088$、容量 $c=512$，提供 256 位输出，安全级别 128 位。它的核心置换 $\chi\rho\pi\theta$ 由 5 步可逆操作构成，运行在 $5 \times 5 \times 64$ 的三维状态上。这种结构虽然比 SHA-2 慢约 30%，但与以太坊 EVM 的 256 位栈字长对齐良好，且为 ZK 电路友好——这是后文 Rollup 章节会回扣的一个伏笔。

1.1.4 比特币的双 SHA-256 与以太坊的 Keccak-256

比特币对区块头做两次 SHA-256：$\text{hash} = \text{SHA256}(\text{SHA256}(\text{header}))$。双哈希的设计动机有两点：(1) 防御长度扩展攻击，SHA-256 内部 Merkle–Damgård 结构有此隐患；(2) 在 ASIC 设计年代，挡住对单次 SHA-256 的定制化优化，为公平挖矿留出余地。以太坊则在 RLP 编码后直接调用 Keccak-256，并且为提升抗 ASIC 能力，最初规划 Ethash 与 Keccak-256 组合的哈希函数族。

值得指出，Keccak-256 与 NIST 标准化后的 SHA3-256 输出长度虽然相同，但填充规则不同：以太坊在 EIP 中明确使用 padding byte 0x06，NIST SHA-3 使用 0x06 后跟一个终止字节 0x80。这种细微差别是工程上常见的"踩坑点"，在跨链桥审计中曾多次出现。

1.2 椭圆曲线签名：从 ECDSA 到 Schnorr

1.2.1 secp256k1 曲线参数

比特币和以太坊都默认使用同一条曲线 secp256k1，它定义在素域 $\mathbb{F}_p$ 上： $$y^2 = x^3 + 7 \pmod p$$ 其中 $p = 2^{256} - 2^{32} - 977$，曲线阶 $n$ 略小于 $p$。这条曲线属于 Koblitz 家族，特殊形式使模 $p$ 运算中的乘法可优化为多项式乘法，少量参数如表 1 所示（文中以代码块形式给出关键常量的二进制表达）：

```python SECP256K1_P = 0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEFFFFFC2F SECP256K1_N = 0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEBAAEDCE6AF48A03BBFD25E8CD0364141 SECP256K1_Gx = 0x79BE667EF9DCBBAC55A06295CE870B07029BFCDB2DCE28D959F2815B16F81798 SECP256K1_Gy = 0x483ADA7726A3C4655DA4FBFC0E1108A8FD17B448A68554199C47D08FFB10D4B8 ```

注意 $a=0$、$b=7$ 的极简形式——这并非偶然。NIST 曲线（如 P-256）选择 $a,b$ 以利于侧信道免疫，但对 $p$ 的特殊结构没有额外约束；secp256k1 反其道而行，$p$ 被选为接近 $2^{256}$ 的"近 Mersenne 素数"，可显著加速模约减。这种取舍意味着 secp256k1 在恒定时间实现上需要更多工程注意（避免基于分支的标量泄漏），但换来的是验证性能优势。

1.2.2 ECDSA 签名算法

ECDSA 的核心思想是把"签名"转化为对消息哈希与私钥乘积的离散对数证明。对私钥 $d \in [1, n-1]$，公钥 $Q = dG$，签名 $(r, s)$ 生成流程为：

1. 选取临时随机数 $k \in [1, n-1]$，计算 $(x_1, y_1) = kG$； 2. 令 $r = x_1 \bmod n$，若 $r = 0$ 重选 $k$； 3. 计算 $s = k^{-1}(z + rd) \bmod n$，其中 $z$ 是消息哈希的截断（按曲线阶长度取左位）； 4. 输出签名 $(r, s)$。

验证流程：检查 $u_1 = zs^{-1} \bmod n$、$u_2 = rs^{-1} \bmod n$，计算 $(x_1, y_1) = u_1 G + u_2 Q$，要求 $r \equiv x_1 \pmod n$。

1.2.3 ECDSA 的可塑性与比特币的 BIP-62

ECDSA 签名有一个微妙的"可塑性（malleability）"：若 $(r, s)$ 是合法签名，则 $(r, -s \bmod n)$ 也是合法签名，因为验证时 $u_2$ 的符号会翻转。攻击者无需知道私钥即可"修改"交易签名而不改变交易语义。这在比特币早期导致严重后果——交易 $T_1$ 的输入引用 $T_2$ 的 txid，但 $T_2$ 的签名被修改后其 txid 改变，$T_1$ 的输入引用悬空，整个交易链断裂。SegWit 升级通过把签名从交易体移到见证区（witness）解决了此问题，但根本修复需要把签名格式变为"严格"形式。BIP-340 Schnorr 正是这一思路的延伸。

1.2.4 BIP-340 Schnorr 签名

Schnorr 签名在数学上与 ECDSA 同构于离散对数困难性假设，但拥有 ECDSA 不具备的关键性质：线性。给定私钥 $d_1, d_2$ 与对应公钥 $Q_1 = d_1 G, Q_2 = d_2 G$，聚合公钥 $Q = Q_1 + Q_2$ 对应聚合私钥 $d = d_1 + d_2$，且对同一消息 $m$ 的两个签名 $(R_1, s_1)$、$(R_2, s_2)$ 满足： $$s_1 + s_2 = k_1 + k_2 + (d_1 + d_2) H(R_1+R_2 \Vert Q_1+Q_2 \Vert m)$$ 直接聚合为聚合签名 $(R_1+R_2, s_1+s_2)$。这是 MuSig 等密钥聚合协议的代数基础。

BIP-340 在 secp256k1 上定义的 Schnorr 形式要点：

• $x$ 坐标作为挑战：$e = H(R \Vert Q \Vert m) \bmod n$，避免 ECDSA 中恢复 $y$ 符号所需的额外判断；
• 签名 $(R, s)$ 长度固定 64 字节；
• 强制 $R$ 的 $y$ 坐标为偶数（"lift-X"），消除可塑性；
• 不使用 $k$ 的哈希链，仅要求 $k$ 来自诚实随机源并加上额外熵。

Taproot 升级（2021）后，比特币 P2TR 地址即使用 BIP-340 Schnorr。线性聚合带来隐私增强：多签交易看起来与单签交易在链上完全相同，仅暴露聚合公钥。这是后续 MuSig2、跨链原子交换、FROST 门限签名等技术的根基。

1.2.5 RSA 与 ECDSA 的工程对比

从签名长度看，2048 位 RSA 签名是 256 字节，ECDSA 在 256 位曲线上是 64 字节（r,s 各 32 字节），Schnorr 也是 64 字节。从验证时间看，RSA 验证只需一次模幂（约 $O(\log^3 N)$），而 ECDSA 需要点乘（约 $O(n)$），实际中 secp256k1 签名验证约为 RSA-2048 的 5–10 倍慢。但 ECDSA 优势在于密钥长度短 8 倍，存储与传输开销显著降低，这正是区块链选择它的根本原因——链上每一字节都对应经济成本。

1.3 Merkle 树与向量承诺：从 SPV 到 Verkle Tree

1.3.1 二叉 Merkle 树与包含性证明

给定 $n$ 个数据块 $D_1, \dots, D_n$（通常 $n$ 是 2 的幂，否则填充），Merkle 树自底向上递归构造： $$\text{node}_{i,j} = H(\text{node}_{i,j \cdot 2} \Vert \text{node}_{i, j \cdot 2+1})$$ 其中 $\text{node}_{0,j} = H(D_j)$。根节点 $\text{root} = \text{node}_{\log n, 1}$ 是全部数据的指纹。

要证明 $D_k$ 包含在根中，验证者只需要 $\log_2 n$ 个兄弟节点路径（认证路径），从叶子向上逐步哈希恢复出根，与本地计算的根比对即可。这带来 $O(\log n)$ 的证明复杂度——比特币区块含约 3000 笔交易时，SPV 证明仅需 12 个哈希，约 384 字节。

不可伪造性证明：若存在伪造证明 $(\pi_1, \dots, \pi_{\log n})$ 使攻击者声称的 $D_k'$ 通过验证，则必存在某层节点 $v_i \neq v_i'$ 但 $H(v_i \Vert \pi_i) = H(v_i' \Vert \pi_i)$，这违反 $H$ 的抗碰撞性。在 random oracle 模型下，伪造概率 $\le q^2/2^n$，其中 $q$ 是查询次数。

1.3.2 从交易到 Merkle 根的聚合路径

下面这张图描述了一笔交易从原始字节序列到最终被纳入区块头的完整哈希聚合路径，并说明 SPV 轻客户端如何仅凭兄弟节点路径确认该交易存在于链上。

```mermaid flowchart TD A["Tx: 原始交易字节序列"] --> B["H_0 = DSHA256(Tx)"] B --> C["Merkle 叶子层 (Layer 0)"] C --> D["H_1 = H(H_0 || H_sibling_0)"] D --> E["Layer 1 节点"] E --> F["H_2 = H(H_1 || H_sibling_1)"] F --> G["Layer 2 节点"] G --> H["H_3 = H(H_2 || H_sibling_2)"] H --> I["Layer 3 节点"] I --> J["H_root = Merkle Root"] J --> K["写入区块头"] K --> L["SPV 客户端: 提供 sibling_0, sibling_1, sibling_2"] L --> M["本地重算 H_root 并与区块头比对"] ```

读者可留意其中两条数据流：区块构造者从下往上计算根（自底向上），SPV 客户端则从叶子的兄弟节点出发按相同规则重算根（验证方向是单向的）。任何对原始交易的篡改都会改变 $H_0$，进而破坏 $H_{\text{root}}$，验证者立即发现差异。

1.3.3 Merkle Patricia Trie：以太坊状态存储

比特币的 UTXO 集合用普通哈希表管理即可，但以太坊的账户模型要求按地址路径快速查询余额、合约代码、存储槽，这正是 Merkle Patricia Trie（MPT）解决的问题。MPT 是 Patricia Trie 与 Merkle 树的结合：

• **Patricia Trie 部分**：将键编码为 nibble（4 位）序列，沿树向下每 nibble 走一步，遇到无分支路径时压缩为"扩展节点"；
• **Merkle 部分**：每个节点存哈希指针，根哈希进入区块头，任何状态变更都使根变化。

以太坊采用十六进制前缀（Hex-Prefix, HP）编码区分扩展节点与分支节点，并通过三种节点类型完成路径压缩：

```text Branch Node: 16 个子项 + value，共 17 个槽 Extension Node: [hex-prefix nibbles, key suffix, child hash] Leaf Node: [hex-prefix nibbles, key suffix, value] ```

MPT 的优势在于：证明大小与键长对数成正比（而非与全树大小对数成正比），且支持高效的"插入"操作（每次仅修改 $O(\log n)$ 个节点）。代价是证明验证需要路径上所有节点完整数据，证明体积相对较大——这是 Verkle Tree 试图改进的核心点。

1.3.4 Verkle Tree：向量承诺的下一代

Verkle Tree 由 John Kuszmaul 在 2018 年提出，2021 年由 Vitalik Buterin 引入以太坊路线图（EIP-6800）。其关键思想是用 KZG 多项式承诺（Kate-Zaverucha-Goldreich）替代哈希：

对每个节点 $v$，构造一个多项式 $f_v(X)$，使 $f_v(i) = $ 第 $i$ 个子节点的承诺。父节点的承诺 $C_{\text{parent}} = \text{com}(f_{\text{parent}})$。要证明"父节点第 $i$ 个子节点的值是 $y$"，只需提供一个证明 $\pi$，使得验证者能检查： $$e(C_{\text{parent}}, g_2) = e(\pi, g_2^{\alpha - i}) \cdot e(\text{com}(y), g_2)$$ 其中 $e$ 是配对（pairing），$\alpha$ 是可信设置中的"陷门"。这种向量承诺的优点是证明大小恒定（$O(1)$ 个群元素），不随树宽度变化；缺点是依赖椭圆曲线配对（不在 secp256k1 上而在 BLS12-381 上）与一次可信设置