Cryptographic Primitives and Data Structures for Blockchain Systems

区块链系统的安全性建立在一系列密码学原语和数据结构之上。这些基础组件不仅提供了必要的安全保证，还决定了系统的效率、可扩展性和功能性。本章将深入探讨这些核心构建块，从底层密码学原语到高层数据结构，为理解后续章节中的高级协议奠定坚实基础。我们将首先审视哈希函数的严格安全定义及其在区块链中的关键作用，随后分析数字签名方案从传统椭圆曲线到现代聚合签名的演进。在此基础上，我们将形式化区块链作为仅追加数据结构的本质，并分析其不变性保证。最后，我们将探讨零知识证明系统如何作为隐私与可扩展性的基石，重新定义区块链的可能性边界。 throughout this chapter, we maintain a rigorous, formal perspective, emphasizing precise security definitions, provable guarantees, and the practical engineering trade-offs inherent in real-world deployments.

Cryptographic Hash Functions: The Bedrock of Blockchain Integrity

哈希函数是将任意长度输入映射为固定长度输出的基本密码学工具。在区块链中，它们充当着数字指纹的角色，确保数据完整性、建立区块间的链接，并在共识机制中发挥核心作用。一个密码学哈希函数 $H: \{0,1\}^* \rightarrow \{0,1\}^n$ 必须满足三个核心安全属性：原像抗性（preimage resistance）、第二原像抗性（second-preimage resistance）和碰撞抗性（collision resistance）。形式上，对于原像抗性，给定任意哈希值 $y$，计算任意输入 $x$ 使得 $H(x) = y$ 在计算上不可行，即 $\Pr[\text{FindPreimage}(H, y)] \leq \epsilon$ 对于可忽略的 $\epsilon$。第二原像抗性要求，给定特定输入 $x_1$，找到另一个不同输入 $x_2 \neq x_1$ 使得 $H(x_1) = H(x_2)$ 在计算上不可行。碰撞抗性则是最强的属性，要求找到任意一对不同输入 $(x_1, x_2)$ 使得 $H(x_1) = H(x_2)$ 在计算上不可行。值得注意的是，碰撞抗性蕴含第二原像抗性，但反之不成立；然而，对于输出长度 $n$ 的哈希函数，生日悖论表明碰撞可在约 $2^{n/2}$ 次查询内找到，因此现代哈希函数必须提供至少 256 位输出以抵御暴力碰撞攻击。

在区块链的初始设计中，比特币采用 SHA-256 作为其核心哈希函数，用于工作量证明（PoW）和交易标识。SHA-256 属于 SHA-2 家族，基于 Davies-Meyer 结构的 Merkle-Damgård 构造。尽管 SHA-256 至今仍被认为是安全的，但 Merkle-Damgård 构造固有的长度扩展攻击漏洞（例如，已知 $H(k \| m)$ 可计算 $H(k \| m \| m')$ 而不知 $k$）促使了更现代设计的发展。SHA-3 家族（基于 Keccak 算法）通过海绵构造（sponge construction）规避了此漏洞，提供了与 SHA-2 不同的安全假设。Keccak 的参数化设计允许灵活的输出长度和吸收/ squeezing 速率，其内部置换 $f$ 由五步迭代（$\theta, \rho, \pi, \chi, \iota$）构成，提供了对差分和线性密码分析的强抵抗力。以太坊 1.0 最初也采用 Keccak-256（而非标准 SHA-3），体现了工程实践中对算法细微差别的考量。

BLAKE3 代表了哈希函数设计的最新进展，通过引入树哈希模式（tree hash mode）和优化的压缩函数，在保持与 BLAKE2 相当安全性的同时，实现了显著的并行性能提升。BLAKE3 的压缩函数基于 HAIFA 结构，并采用 7 轮 ChaCha20 核心，支持增量更新和密钥化操作（即作为伪随机函数 PRF）。其树模式允许输入被分割为子树，各子树可独立并行哈希，最后通过根节点合并，这使得 BLAKE3 在大规模数据哈希（如区块链状态快照）中展现出卓越的吞吐量。下表对比了主流哈希函数的关键特性：

| 函数 | 输出长度 | 构造 | 主要优势 | 典型区块链应用 | |------|----------|------|----------|----------------| | SHA-256 | 256 bits | Merkle-Damgård | 广泛部署、硬件加速 | 比特币、比特币现金 | | Keccak-256 | 256 bits | Sponge | 无长度扩展漏洞、标准化 | 以太坊 1.0 | | BLAKE3 | 256 bits | Tree + HAIFA | 极致并行、增量哈希 | 新兴链（如 Algorand 实验性） |

在区块链工程中，哈希函数的性能直接影响共识效率与交易处理速度。例如，在 PoW 机制中，矿工需反复计算双 SHA-256 哈希以寻找低于目标的 nonce，因此硬件优化（如 ASIC）针对特定哈希函数设计。此外，哈希函数用于生成交易标识（txid）和区块头哈希，后者通过包含前一区块哈希而实现链式链接，形成不可篡改的账本。任何对历史区块的修改都会导致其哈希值改变，进而破坏后续所有区块的链接，这构成了区块链不变性（immutability）的密码学基础。然而，这种保证依赖于“诚实多数”假设：若攻击者控制超过 50% 的算力，理论上可发起 51% 攻击重写链历史，但代价随链长度指数增长，因为需要重新计算所有后续区块的工作量证明。

Digital Signature Schemes: Authenticity and Non-Repudiation

数字签名方案为区块链交易提供了不可否认的认证，确保只有私钥持有者能授权资金转移，同时允许任何人用公钥验证签名有效性。一个签名方案由三元组 $(\mathsf{KeyGen}, \mathsf{Sign}, \mathsf{Verify})$ 组成，需满足存在性不可伪造性（existential unforgeability） under 适应性选择消息攻击（EUF-CMA）。形式上，对于任何概率多项式时间（PPT）攻击者 $\mathcal{A}$，在获得对任意消息 $m_i$ 的签名 $\sigma_i = \mathsf{Sign}(sk, m_i)$ 的 oracle 访问后，成功伪造一条新消息 $m^* \notin \{m_i\}$ 的有效签名 $\sigma^*$ 的概率可忽略。

椭圆曲线数字签名算法（ECDSA） 是比特币和早期区块链的默认选择。它基于椭圆曲线离散对数问题（ECDLP）的困难性，在曲线 $y^2 = x^3 + ax + b$ 上定义。签名生成涉及生成随机数 $k$，计算点 $(x_1, y_1) = k \cdot G$，其中 $G$ 为基点，然后 $r = x_1 \mod n$，$s = k^{-1}(H(m) + r \cdot sk) \mod n$，其中 $sk$ 为私钥，$H$ 为哈希函数。验证时，计算 $u_1 = H(m) \cdot s^{-1} \mod n$，$u_2 = r \cdot s^{-1} \mod n$，点 $(x_1, y_1) = u_1 \cdot G + u_2 \cdot Q$，其中 $Q = sk \cdot G$ 为公钥，最后验证 $r \equiv x_1 \mod n$。ECDSA 的随机数 $k$ 必须严格保密且不可预测；历史上，因 $k$ 重复或偏斜导致的私钥泄露事件（如 PlayStation 3 漏洞、Satoshi Dice 漏洞）凸显了其实现风险。此外，ECDSA 签名是非线性的，难以直接聚合多个签名，这限制了其在需要高吞吐量场景（如跨链交易）的效率。

Schnorr 签名 提供了更优的代数结构和安全性。其核心方程为 $s = k + e \cdot sk \mod n$，其中 $e = H(R \| m)$，$R = k \cdot G$。验证通过检查 $s \cdot G = R + e \cdot Q$。Schnorr 签名的线性性质使其天然支持签名聚合：多个签名可合并为单一组签名，验证复杂度仅与公钥数量成线性关系，而非签名数量。例如，对于 $n$ 个签名者，聚合签名大小为单个 Schnorr 签名（64 字节），验证需 $n+1$ 次标量乘法，而非 $n$ 次独立验证。比特币通过 Taproot 升级（BIP 340/341/342）引入了 Schnorr 签名，实现了更高效的_multisig_ 交易、脚本路径花费和协作式交易（如 CoinJoin）。Schnorr 的安全性可归约到离散对数问题，且对随机数失败更具鲁棒性（可通过 deterministic $k$ 避免）。

BLS 签名（Boneh-Lynn-Shacham）基于双线性配对（bilinear pairing），在椭圆曲线群 $G_1$ 和 $G_2$ 上定义，映射到目标群 $G_T$。签名 $\sigma = H(m)^{sk}$，其中 $sk \in \mathbb{Z}_p$，验证通过检查 $e(\sigma, g) = e(H(m), g^{sk})$，其中 $g$ 为 $G_2$ 的生成元，$g^{sk}$ 为公钥。BLS 签名的核心优势是简单聚合：给定签名 $\sigma_i = H(m_i)^{sk_i}$ 和公钥 $g^{sk_i}$，聚合签名 $\sigma = \prod_i \sigma_i$ 可通过 $e(\sigma, g) = \prod_i e(H(m_i), g^{sk_i})$ 验证，无论签名者数量多少，验证仅需一次配对运算。这使其在需要大量签名者（如权益证明（PoS）共识中的验证者委员会）的场景中极具价值。以太坊 2.0 采用 BLS 签名聚合验证者签名，将每 slot 的验证开销从 $O(N)$ 降低到 $O(1)$，显著提升了可扩展性。然而，BLS 依赖于配对友好曲线（如 BLS12-381），其安全性基于更复杂的假设（如 $e$-BDH），且签名生成涉及配对运算，通常比 ECDSA/Schnorr 慢。

下表总结了三大签名方案的关键工程权衡：

| 特性 | ECDSA | Schnorr | BLS | |------|-------|---------|-----| | 安全假设 | ECDLP | DLP / ROS | BDH + 配对 | | 签名大小 | 64-72 字节 | 64 字节 | 48 字节 | | 验证成本 | 1-2 次标量乘法 | 1 次标量乘法 + 1 次加法 | 1 次配对运算 | | 聚合类型 | 复杂（需交互） | 简单（线性） | 极简（乘积） | | 随机数依赖 | 是（风险高） | 可确定化 | 否 | | 典型应用 | 比特币 Legacy | 比特币 Taproot, Litecoin | 以太坊 2.0, Zcash |

在区块链工程实践中，签名方案的选择直接影响交易费用、隐私性和网络吞吐量。例如，比特币的 SegWit 升级通过分离签名数据，降低了交易字节数，但未改变底层 ECDSA。Taproot 通过引入 Schnorr，使复杂智能合约交易与普通转账在链上 indistinguishable，提升了隐私并降低了费用。在 PoS 链中，BLS 聚合是处理数千验证者签名的唯一可行方案；然而，其配对运算的复杂性要求高度优化的库（如 blst）和特定的曲线选择以平衡安全与性能。

Merkle Tree Constructions: From Authentication to State Representation

Merkle 树（哈希树）是一种二叉树结构，其中每个叶节点为数据块的哈希，每个内部节点为其子节点哈希的哈希。根节点哈希（Merkle root）作为整个数据集的紧凑指纹，使得验证特定数据成员关系（membership proof）仅需 $O(\log n)$ 个哈希值（Merkle proof），而非传输全部数据。这种默克尔化（Merkelization）是轻客户端（light client）和简化支付验证（SPV）的核心，允许节点仅存储区块头（80 字节）而验证交易存在性，无需下载完整区块链。

标准二叉 Merkle 树假设叶节点数量为 2 的幂，通过重复哈希相邻节点对构建。为处理奇数节点，通常采用双哈希（double hashing）策略：节点哈希为 $H(H(\text{left}) \| H(\text{right}))$，其中 $\|$ 表示拼接。这防止了长度扩展攻击，并确保即使子节点哈希长度可变，内部节点哈希仍固定长度。在比特币中，交易默克尔树用于生成区块头中的默克尔根，轻客户端可通过提供交易索引和中间哈希值来验证交易是否包含在区块中。然而，标准 Merkle 树不支持动态更新：插入或删除叶节点需重建整树，成本为 $O(n)$，这在需要频繁更新的场景（如账户状态树）中不可接受。

稀疏 Merkle 树（Sparse Merkle Tree, SMT） 通过将键空间（key space）固定为 $2^{256}$（基于 256 位哈希），使得每个可能键对应一个叶节点，初始值为零哈希。更新时，仅需修改从叶节点到根的路径上的节点，复杂度 $O(\log n)$，且默克尔根变化可证明特定键值对的更新。SMT 的关键创新是空分支压缩：由于绝大多数键不存在，其子树可表示为单一哈希值，无需显式存储。这使 SMT 成为理想的状态树结构，其中仅活跃账户需要存储。以太坊 1.0 采用改良的 Patricia Merkle Trie（基于 Radix 树和 Merkle 化），键为地址（160 位），值为账户状态（余额、nonce、存储根等）。Patricia 树通过路径压缩减少节点数，但证明大小可达数百字节，且验证需复杂状态转换逻辑。

Verkle 树（Vector Commitment Tree）是 SMT 的现代演进，旨在降低证明大小和验证成本。它结合向量承诺（vector commitment）方案与二叉树结构，使用多项式承诺（如 KZG 承诺）替代传统哈希。在 Verkle 树中，每个内部节点代表一个多项式承诺，其子节点为承诺的求值。验证默克尔证明时，验证者仅需一次多项式求值验证，而非多次哈希计算。这显著减小了证明大小（从约 200 字节降至约 30 字节）并加速验证，特别有利于状态同步和 rollup 证明。以太坊的 Verkle Tree 计划（EIP-2929 及后续）旨在用 Verkle 树替换当前状态树，以支持更小的状态 witnesses 和更快的同步。Verkle 树的代价是更复杂的实现和基于离散对数假设的信任（与 KZG 相关），但其在可扩展性方面的收益已被广泛认可。

下图对比了三种树结构在证明大小和更新复杂度上的差异：

```mermaid graph LR A[数据集合] --> B[标准 Merkle 树] A --> C[稀疏 Merkle 树] A --> D[Verkle 树]

B --> E[证明大小: O(log n) 哈希] B --> F[更新: O(n) 重建]

C --> G[证明大小: O(log n) 哈希] C --> H[更新: O(log n) 路径更新]

D --> I[证明大小: O(log n) 但常数小] D --> J[更新: O(log n) 多项式承诺]

style B fill:#f9f,stroke:#333 style C fill:#bbf,stroke:#333 style D fill:#bfb,stroke:#333 ```

在区块链工程中，Merkle 树的选择直接影响客户端的资源需求和网络的去中心化程度。全节点需存储完整状态树，而轻客户端依赖 Merkle 证明验证。随着状态增长（如以太坊状态已达数百 GB），传统树结构的证明大小和验证时间成为瓶颈。Verkle 树通过密码学压缩，有望将状态 witnesses 从数百 kB 降至数十 kB，使移动端和嵌入式设备运行轻客户端成为可能。此外，Merkle 树的变体如 Merkle Mountain Ranges（用于文件版本控制）和 Incremental Merkle Tree（用于 Zcash 的注记）展示了其在特定场景的适应性。

Blockchain as an Append-Only Data Structure: Formalization and Immutability

从数据结构视角，区块链可形式化为一个仅追加的链表，其中每个区块包含一批交易、前驱区块哈希、时间戳和随机数（nonce）。定义区块 $B_i = (t_i, h_{i-1}, \text{ts}_i, n_i)$，其中 $t_i$ 为交易集合，$h_{i-1} = H(B_{i-1})$ 为前一区块哈希，则链 $C = (B_1, B_2, \dots, B_k)$ 满足 $h_i = H(B_i)$ 且 $h_i$ 包含于 $B_{i+1}$。这种链式哈希链接（hash chain）创造了密码学链式绑定（cryptographic chaining）：修改任意历史区块 $B_j$ 将导致 $h_j$ 改变，进而使 $B_{j+1}$ 中的 $h_j$ 不匹配，破坏链的连续性，需重新计算所有后续区块的哈希（包括工作量证明）。因此，在假设哈希函数抗碰撞的前提下，区块链提供了弱不变性（weak immutability）：历史记录可验证但并非绝对不可变；在足够算力下仍可重写，但成本随链长度增加。

不变性保证依赖于共识规则与密码学原语的结合。在 PoW 链中，最长链规则（以累计工作量最大为准）定义了“有效链”。攻击者若想篡改历史交易，需创建一条从篡改点开始的分叉链，并使其工作量超过诚实链。若攻击者算力为 $\alpha$，诚实网络为 $1-\alpha$，则攻击者追上诚实链的概率随落后区块数 $z$ 指数下降，由 Satoshi 定理 给出：$\Pr[\text{Catch-up}] \leq \begin{cases} 1 & \alpha \leq 0.5 \\ (