第一章 区块链的形式化定义与分布式系统基础 / Chapter 1 Formal Definition of Blockchain and Distributed Systems Foundations

第一章 区块链的形式化定义与分布式系统基础

Chapter 1 Formal Definition of Blockchain and Distributed Systems Foundations

一个根本性的问题贯穿本章：在分布式系统理论的形式化框架下，"区块链"应当被如何精确定义？它与传统复制状态机协议的根本区别是什么？为了回答这一问题，我们必须在最严格的数学抽象中展开讨论——不诉诸营销话语，不依赖隐喻，而仅从状态、一致性、对抗性（adversariality）这几个可以写出形式化定义的概念出发。本章以 FLP 不可能性结果与 CAP 定理为序章，回顾拜占庭容错模型下达成一致性的必要条件；继而将区块链抽象为"在对抗性网络条件下提供概率性或确定性一致性的去中心化复制状态机"（Decentralized Replicated State Machine, DRSM），并讨论其与传统 RSM 的本质差异。

---

1.1 分布式系统基础模型与不可能性结果

1.1.1 系统模型的三要素

在讨论一致性之前，必须先固定所讨论的分布式系统的故障模型（Failure Model）、网络模型（Network Model）与对手模型（Adversary Model）。这三者构成了所有可证明结论的边界条件。

故障模型刻画的是进程可能偏离其规范行为的方式。常见的有三类：

• **崩溃故障**（Crash Fault）：进程停止响应，不再发送任何消息，但停止前发送的消息遵守协议。
• **遗漏故障**（Omission Fault）：进程可能丢失部分消息。
• **拜占庭故障**（Byzantine Fault，简称 BF）：进程可能任意偏离协议，包括发送矛盾消息、伪造消息或不响应。Lamport、Shostak 与 Pease 在 1982 年的开创性论文中将此问题形式化为"拜占庭将军问题"（Byzantine Generals Problem）。

网络模型刻画消息投递的时序保证：

• **同步网络**（Synchronous）：消息投递有已知上界 $\Delta$，处理时间有已知上界。
• **异步网络**（Asynchronous）：消息投递时延无上界，处理时延无上界。
• **部分同步网络**（Partially Synchronous）：Dwork、Lynch 与 Stockmeyer 在 1988 年提出的模型，包含两种变体。其一是 **GST 模型**：存在一个未知的全局稳定时间（Global Stabilization Time, GST）$\mathsf{GST}$，在此之后网络变为同步；其二是 **有限漂移模型**：时钟漂移与消息时延有上界但这些上界未知。

对手模型刻画对手对协议执行的控制能力。在区块链语境下，对手可分为：

• **静态对手**（Static Adversary）：在协议开始前确定腐化的节点集合。
• **自适应对手**（Adaptive Adversary）：可在线决定腐化哪些节点。
• **移动对手**（Mobile Adversary）：可在协议执行过程中"移动"其腐化能力。

1.1.2 FLP 不可能性

1985 年，Fischer、Lynch 与 Paterson 证明了分布式系统理论中最深刻的不可能性结果之一：在一个异步网络中，即便仅有一个进程发生崩溃故障，也不存在一个确定性的协议能够保证所有非故障进程在有限时间内就二元值达成一致。该结论的正式陈述如下。

> 定理 1.1（FLP 不可能性） 假设网络为异步且可靠（即消息最终必达，但无时延上界），且至少有一个进程可能发生崩溃故障。则不存在任何确定性协议 $\Pi$ 能够在所有执行中保证： > 1. 一致性（Agreement）：所有非故障进程决定（decide）相同的值。 > 2. 有效性（Validity）：所决定的值由某个进程的输入提出。 > 3. 终止性（Termination）：每个非故障进程在有限步内做出决定。

其证明的核心在于：异步系统中的"不确定性"——由于消息时延无上界，进程无法区分"消息尚未到达"与"发送方已崩溃"这两种情况——使得任何配置（configuration）都至少存在一个导致协议无法在有限步内终止的"逃离"路径。形式上，通过对配置图（configuration graph）构造一棵无限的二义性树（bivalence tree），FLP 证明任一确定性协议都存在无限执行而不终止。

FLP 定理并非宣告分布式一致性的死刑，它实际划定了可行的边界：

• 引入**随机性**（randomness）可绕过 FLP，如 Ben-Or 协议以概率 1 在有限期望时间内达成一致。
• 引入**部分同步**假设可绕过 FLP，如 PBFT 在 GST 之后保证终止。
• 引入**崩溃-恢复**与**同步器**（synchronizer）也可在弱化模型下构造一致性。

1.1.3 CAP 定理

2000 年，Eric Brewer 在 PODC 会议上提出猜想，2002 年由 Gilbert 与 Lynch 给出证明的 CAP 定理，刻画了分布式数据存储系统在网络分区（network partition）下的固有取舍。

> 定理 1.2（CAP 定理） 任何分布式数据存储系统在发生网络分区时，不可能同时满足以下三个性质： > 1. 一致性（Consistency, C）：所有节点在同一时刻看到相同的数据。 > 2. 可用性（Availability, A）：每个对非故障节点的请求都能在有限时间内收到响应。 > 3. 分区容忍性（Partition tolerance, P）：系统在任意网络分区下仍能继续提供服务。

由于现代网络环境中分区不可避免（P 必选），系统设计者必须在 C 与 A 之间做出取舍。这一取舍在区块链设计中反复出现：以 Bitcoin 为代表的 Nakamoto 共识牺牲强一致性以换取可用性（即 AP 倾向），而以 DiemBFT 为代表的 PBFT 系协议则倾向一致性优先（即 CP 倾向）。

1.1.4 拜占庭将军问题与容错阈值

拜占庭将军问题可被抽象为：$n$ 个将军中任意 $m$ 个可能叛变，需要就"进攻"或"撤退"达成一致。Lamport 等人证明，在使用口头消息（oral message）的同步模型下，当 $n \geq 3m + 1$ 时存在协议 $\Pi$ 可解决该问题；在使用签名消息（signed message）时，阈值可放松至 $n \geq m + 1$。这一阈值在区块链协议设计中反复出现：PBFT 要求 $n \geq 3f + 1$ 才能容忍 $f$ 个拜占庭节点；Tendermint 沿用此条件；而在 Nakamoto 共识（PoW）中，对应的概率性阈值是算力占比不超过 50%。

形式化地，定义一个共识协议 $\Pi$ 的安全阈值（safety threshold）为：在该参数下，协议的安全性（即不出现分叉）在所有对手策略下均成立。相应地，活性阈值（liveness threshold）为：在该参数下，协议的活性在所有对手策略下均成立。对 BFT 系协议而言，二者通常相同，均为 $f < n/3$。对 PoW 系协议，安全阈值为算力 $\alpha < 0.5$，活性阈值亦为 $\alpha < 0.5$（但当 $\alpha \in (0.33, 0.5)$ 时需考虑自私挖矿等具体策略）。

---

1.2 复制状态机与原子广播的形式化等价

1.2.1 复制状态机模型

复制状态机（Replicated State Machine, RSM）是分布式系统中最具影响力的一致性模型之一。其核心思想是：维护 $n$ 个副本（replica），每个副本从相同的初始状态 $\sigma_0$ 出发，对相同的有序操作序列（operation sequence）依次执行确定性状态转移函数 $\delta: \Sigma \times O \to \Sigma$，从而达到相同的状态 $\sigma_t$。

形式化地，一个 RSM 系统 $\mathcal{R} = (n, \sigma_0, \delta, \mathcal{O})$，其中：

• $n$：副本数
• $\sigma_0$：初始状态，$\sigma_0 \in \Sigma$
• $\delta$：状态转移函数，$\delta(\sigma, o) = \sigma'$
• $\mathcal{O}$：操作集合

执行模型为：客户端向 RSM 提交操作；RSM 通过一致性协议（consensus protocol）对操作的全局顺序达成一致；各副本按此顺序依次应用 $\delta$；最后向客户端返回响应。其正确性条件为：

• **状态一致性**：对任意两个非故障副本 $i, j$，在任意时刻 $|\sigma_i - \sigma_j|_d = 0$（即状态距离为零）。
• **线性化语义**（Linearizability）：操作的外部观察等价于某个串行执行。

1.2.2 原子广播

原子广播（Atomic Broadcast, ABCAST）是另一种等价的一致性抽象。Cristian、Aghili、B Strong 与 Dolev 等人在 1990 年代的工作中证明：在一个可以解决一致性问题的协议 $\Pi$ 的基础上，原子广播与一致性问题是等价的。

原子广播协议 $\mathcal{A}$ 满足以下三个性质：

• **有效性**（Validity）：如果一个正确的进程广播消息 $m$，那么它最终会传递（deliver）$m$。
• **一致序**（Total Order）：所有正确进程以相同顺序传递所有消息。
• **完整性**（Integrity）：每条消息最多被传递一次，且仅由其发送者广播。

> 定理 1.3（RSM-ABCAST 等价） 任何实现原子广播的协议都可以在常数额外开销下实现 RSM；反之，任何实现 RSM 的协议都可以在常数额外开销下实现原子广播。

该等价性的关键在于：RSM 中的"决定操作顺序"步骤，正是 ABCAST 中"一致序"性质的体现。给定原子广播，客户端将操作作为消息广播，所有副本按一致序接收并应用 $\delta$ 即可；给定 RSM，将 RSM 的"提交-决定-应用"循环中的状态值替换为消息内容即可。

1.2.3 传统 RSM 的中心化排序器

在传统 RSM 实现（如 Paxos、Multi-Paxos、Raft）中，决定操作全局顺序的角色由单一领导者（single leader）或主从配置（primary-backup configuration）承担。Raft 将其形式化为"Leader election + Log replication"两阶段：领导者从客户端接收操作提议，将其附加到日志中并向其他副本复制，多数派（majority）确认后提交并应用。

这种"中心化排序器"设计在数据中心等可信环境中工作良好，但在公链场景下面临根本性挑战：

• **单点信任**：客户端必须信任领导者不会审查（censor）其交易。
• **领导者选择**：在对抗性环境中，谁能担任领导者本身是一个需要共识的问题——产生循环依赖。
• **女巫攻击**（Sybil Attack）：在开放网络中，敌手可以创建任意数量的伪身份，使得"多数派"概念失效。

下图刻画了传统 RSM 的标准执行流，并凸显出区块链相对于传统 RSM 的"无中心排序器"特征。

```mermaid flowchart LR C[Client Request] --> S[Centralized Sequencer / Leader] S --> O[Order Assignment] O --> D1[Replica 1: Apply delta] O --> D2[Replica 2: Apply delta] O --> Dn[Replica N: Apply delta] D1 --> R1[Response 1] D2 --> R2[Response 2] Dn --> Rn[Response N]

C -.->|Blockchain: trustless| X[No central sequencer] X --> B[Distributed Ordering via Consensus] B --> D1 B --> D2 B --> Dn ```

> 图 1.1 传统 RSM（实线路径）与区块链 DRSM（虚线路径）的执行流对比。RSM 依赖中心化排序器；区块链 DRSM 通过分布式共识实现去中心化排序。

---

1.3 区块链作为对抗性去中心化复制状态机

1.3.1 形式化定义

基于前述模型，我们现在给出区块链的形式化定义。

> 定义 1.1（区块链协议） 一个区块链协议 $\mathcal{B}$ 是一个元组 $(\mathcal{N}, \sigma_0, \delta, \mathcal{O}, \Pi_{\text{order}}, \mathcal{A})$，其中： > - $\mathcal{N}$：网络节点集合，$|\mathcal{N}| = n$，无预设信任关系。 > - $\sigma_0$：创世状态（genesis state），公开且可验证。 > - $\delta$：确定性状态转移函数，$\delta(\sigma, B) = \sigma'$，其中 $B$ 为一个新区块。 > - $\mathcal{O}$：交易/操作集合。 > - $\Pi_{\text{order}}$：去中心化排序协议，输出全局一致的区块序列 $(B_1, B_2, \ldots)$。 > - $\mathcal{A}$：对手模型与容错参数。 > > $\mathcal{B}$ 在对手 $\mathcal{A}$ 控制不超过 $\tau$ 比例的资源的条件下满足： > 1. 共识性（Agreement）：所有诚实节点在 $\sigma$ 上达成一致。 > 2. 有效性（Validity）：由诚实节点产生的有效操作最终被包含在状态中。 > 3. 不可伪造性（Unforgeability）：不存在有效操作被错误地归因于未签署该操作的节点。 > 4. 抗审查性（Censorship Resistance）：对手无法持续将诚实操作排除在状态之外。

这一形式化的关键点在于 $\Pi_{\text{order}}$。在传统 RSM 中，这是一个中心化或受信任的协议；在区块链中，它必须是：

• **去中心化**（Decentralized）：无单一可信第三方。
• **抗合谋**（Collusion-Resistant）：在不超过容错阈值时，任意子集均无法破坏一致序。
• **开放参与**（Permissionless，对 PoW/PoS 系而言）：任何满足资源条件的节点均可参与。

1.3.2 区块作为排序单位

在区块链中，$\Pi_{\text{order}}$ 的输出不是单一操作的顺序，而是区块（block）的顺序。每个区块 $B_i = (h_{i-1}, \mathsf{tx\_root}_i, \mathsf{nonce}_i, \sigma_i^{\text{header}})$ 包含前驱区块哈希、交易树根、用于 PoW 的随机数等头部字段，以及一组有序交易列表 $(o_1, o_2, \ldots, o_k)$。

这一抽象引入了与传统 RSM 的关键区别：操作粒度从单条交易扩展为交易批次（transaction batch）。其后果是：

• **状态转移的非原子性**：同一区块中的交易在应用 $\delta$ 时需定义先后顺序。Bitcoin 使用交易在区块中的拓扑序；Ethereum 维护一个**交易池**（mempool），同一区块内交易可被任意排序，只要最终结果一致。
• **可验证性的累积**：每个区块通过哈希链结构 $\mathsf{hash}(B_i) = H(h_{i-1}, \mathsf{tx\_root}_i, \ldots)$ 累积了从创世以来的全部状态历史。

1.3.3 哈希链结构与不可篡改性

将区块视为 Merkle 树（或更一般的 authenticated data structure），可形式化其不可篡改性（immutability）：

> 定理 1.4（哈希链安全性） 假设哈希函数 $H: \{0,1\}^* \to \{0,1\}^\lambda$ 抗第二原像性（second-preimage resistance）。则篡改区块 $B_k$（$k < i$）需重新计算 $H(B_k), H(B_{k+1}), \ldots, H(B_{i-1})$，其计算成本为 $\Omega(2^\lambda)$。

这一定理是"区块链不可篡改"说法的严格基础。值得注意的是，其安全性假设是密码学假设（抗碰撞性或抗第二原像性），而非协议假设——这与安全性来自共识的 RSM 形成对照。

---

1.4 安全性、活性与最终性的形式化刻画

1.4.1 安全性与活性

Lamport 在 1977 年提出的安全性-活性二分法（Safety-Liveness Dichotomy）是理解分布式协议正确性的基础框架：

• **安全性**（Safety）："坏事不会发生"。协议不产生违反不变式（invariant）的状态。
• **活性**（Liveness）："好事终将发生"。协议最终会到达期望状态。

在区块链语境下：

> 定义 1.2（区块链安全性） 区块链协议 $\mathcal{B}$ 满足安全性，若对任意两个诚实节点 $i, j$ 在任意时刻的本地视图 $\mathsf{View}_i, \mathsf{View}_j$，有 $\mathsf{LastCommonPrefix}(\mathsf{View}_i, \mathsf{View}_j) \geq \ell(k)$，其中 $\ell(k)$ 为安全前缀深度函数，$k$ 为确认后的区块数。 > > 直观上：诚实节点不会接受相互冲突的交易。

> 定义 1.3（区块链活性） 区块链协议 $\mathcal{B}$ 满足活性，若对任意由诚实节点在时间 $t$ 提交的有效交易 $\mathsf{t