BFT协议技术分析与修订

拜占庭容错协议

第一部分：拜占庭容错的理论基础

第 1 节：分布式系统中的共识问题导论

在分布式计算领域，一个核心挑战在于如何使一组独立的、通过网络互连的计算节点达成一致。对于任何依赖于多个组件协作的系统而言，达成共识的能力并非一项可选功能，而是其可靠运行的基础性要求。当系统组件可能发生故障时，这一挑战变得尤为严峻。故障的形式多种多样，从简单的组件宕机到最复杂的任意、恶意行为。拜占庭容错（Byzantine Fault Tolerance, BFT）协议正是为应对这其中最险恶的一类故障而设计的。

1.1 分布式一致性的挑战

分布式系统的核心在于，其各个独立的组件（节点）必须就一个单一、一致的状态或值达成共识，才能确保系统的正确运行。然而，通信信道的不可靠性以及节点潜在的故障行为，使得达成这种一致性变得异常复杂 1。在一个集中式系统中，通常存在一个权威的中心节点负责协调决策和分发信息，从而绕开了共识问题。然而，分布式系统因其去中心化的特性，没有任何一个节点可以被完全信任，系统必须依赖于一个所有节点共同执行的协议来达成最终的一致性 1。这种去中心化的架构虽然带来了更高的弹性和可扩展性，但也引入了达成可靠共识的根本性难题。

1.2 故障谱系

在分布式系统中，故障并非单一形态，而是存在一个从简单到复杂的谱系。对故障模型的准确分类，直接决定了所需解决方案的复杂性和成本。

宕机故障（Crash Faults）：这是最简单的一种故障模型。在此模型中，发生故障的节点会直接停止运行（即“失效-停止”）。这类故障相对容易处理，因为系统只需处理节点的无响应，而无需担心其发送错误信息 1。

遗漏故障（Omission Faults）：此模型下的故障节点会间歇性地无法发送或接收消息。节点可能因为网络分区、缓冲区溢出或其他瞬时问题而遗漏部分通信，但其发送的消息内容本身是正确的 1。

拜占庭故障（Byzantine Faults）：这是最严重、最难以处理的故障类型。一个处于拜占庭故障状态的节点可以表现出任意的、甚至是恶意的行为。它不仅可以发送错误或随机的数据，还可以向系统的不同部分发送相互矛盾的信息，从而主动破坏共识过程 1。这种行为可能是由软件缺陷、硬件瞬时故障、操作员错误或恶意攻击引起的 1。

1.3 拜占庭容错的必要性

在那些信任无法集中化的系统中，例如去中心化金融网络、关键基础设施控制系统以及航空航天应用，仅仅假设节点只会发生宕机故障是远远不够的。在这些环境中，一个节点的故障可能是非确定性的，甚至是具有对抗性的。拜占庭容错（BFT）因此成为构建能够抵御软件漏洞、恶意攻击和其他不可预测故障模式的弹性系统的必要条件 1。

从容忍宕机故障（Crash Fault Tolerance, CFT）到实现拜占庭容错（BFT）的跨越，代表了系统设计理念上的一次重大飞跃。CFT 协议（如 Paxos）通常需要 2f+1 个副本以容忍 f 个宕机故障节点，而 BFT 协议则需要至少 3f+1 个副本以容忍 f 个拜占庭故障节点 1。这种资源需求的增加并非简单的数量叠加，而是反映了 BFT 所要解决的问题在本质上的更高复杂性。选择 BFT 架构，意味着系统设计者有意识地接受了更高的硬件成本、更复杂的协议逻辑和潜在的性能开销，以换取对更险恶威胁模型的防御能力。因此，BFT 并非对 CFT 的增量改进，而是针对一个根本上更为困难的问题所提出的解决方案。

第 2 节：系统模型与假设

为确保后续分析的严谨性，本节明确定义协议运行的系统模型与核心假设。任何容错协议的正确性都高度依赖于其所处的环境模型，脱离该模型讨论协议属性是无意义的。

2.1 同步性假设

分布式系统的同步性是决定共识问题可解性的关键因素。

同步模型（Synchronous Model）：系统中存在一个已知的、固定的消息传输延迟上限 Δ 和处理器相对速度上限 Φ 4。在此模型下，可以通过设置超时来可靠地判断一个节点是否发生故障。

异步模型（Asynchronous Model）：消息传输延迟和处理器速度没有确定的上限 4。这是对互联网等真实世界网络最保守的建模，但也带来了最强的理论限制。

部分同步模型（Partial Synchrony Model）：该模型是介于同步与异步之间的实用模型，由 Dwork、Lynch 和 Stockmeyer 提出，旨在规避纯异步模型的理论不可能性 4。它有两种主要形式：一种是假设延迟上限
Δ 和速度上限 Φ 存在但未知；另一种是假设这些上限已知，但只在某个未知的全局稳定时间（Global Stabilization Time, GST）之后才开始生效 4。本文后续分析的实用 BFT 协议（如 pBFT）均基于部分同步模型，该模型足以保证协议的活性。

2.2 信道与故障模型

信道属性：假设任意两个非故障节点之间的通信信道是可靠的，即一个由非故障节点发送给另一个非故障节点的消息最终会被送达 6。同时，信道是经过认证的，接收方可以验证消息发送方的身份，这通常通过消息认证码（MACs）或数字签名实现 1。

故障域：本文主要关注节点故障。假设系统中总共有 n 个副本节点，其中最多有 f 个节点可能是拜占庭式的，即它们可以表现出任意行为。客户端也可能存在拜占庭行为，协议必须能够抵御来自恶意客户端的攻击（如重放攻击）8。通信链路本身不被视为独立的故障单元，链路的故障（如消息丢失或延迟）被归因于异步网络模型或节点故障。

2.3 安全性与活性定义

安全性（Safety）：协议永远不会做出错误的决定。具体而言，（1）一致性（Agreement）：所有非故障副本以相同的顺序提交请求；（2）有效性（Validity）：如果一个请求由非故障客户端发出，它最终会被所有非故障副本执行。安全性必须在任何网络条件下（包括完全异步的时期）都得到保证。

活性（Liveness）：协议最终能够向前推进并做出决定。具体而言，非故障客户端发出的请求最终会被执行。在部分同步模型下，活性仅被要求在系统进入稳定期后（即 GST 之后）得到保证 4。

2.4 密钥管理

协议的安全性依赖于密码学工具，这要求一个可信的密钥基础设施。

信任根：假设存在一个公钥基础设施（PKI）或一个带外机制，用于安全地分发和验证节点的公钥或共享的对称密钥。

密钥轮换：在系统的长期运行中，密钥可能需要轮换。特别是在发生视图更换等关键事件后，可能需要更新群组密钥以排除被怀疑泄露的节点，确保前向保密性。

第 3 节：拜占庭将军问题与基础不可能性结论

所有拜占庭容错协议的理论基石，源于 Leslie Lamport、Robert Shostak 和 Marshall Pease 在 1982 年发表的里程碑式论文《The Byzantine Generals Problem》9。该论文通过一个生动的寓言，形式化地定义了在存在“叛徒”的情况下达成共识的难题。

3.1 寓言的阐述与形式化

论文描绘了这样一个场景：几支拜占庭军队的师团正包围着一座敌城，每个师团由各自的将军指挥。将军们只能通过信使相互通信，以便协同制定一个统一的作战计划——是“进攻”还是“撤退”9。问题的复杂性在于，将军中可能存在一个或多个叛徒，他们会试图通过发送欺骗性信息来迷惑忠诚的将军 7。

为了从寓言过渡到严格的计算机科学问题，论文提出了任何有效解决方案都必须满足的两个交互一致性条件（Interactive Consistency Conditions）：

IC1 (一致性, Agreement)：所有忠诚的副官（即正常运行的节点）必须遵循相同的命令（即就同一个值达成一致）9。

IC2 (有效性, Validity)：如果指挥官（即发送信息的源节点）是忠诚的，那么每个忠诚的副官都必须遵循他所发出的命令（即如果源节点是正常的，那么最终达成一致的值必须是源节点所提出的值）9。

3.2 基础不可能性结论

该论文最重要的理论贡献之一，是证明了一个关于此问题的局限性，即“不可能性结论”。研究表明，如果将军们只能通过“口头消息”（Oral Messages，即消息内容可被发送者任意伪造）进行通信，那么当将军总数 n 不大于叛徒总数 f 的三倍时（即 n≤3f），没有任何解决方案能够容忍 f 个叛徒 9。这一结论通常被表述为，在一个允许拜占庭故障的系统中，要达成共识，总节点数

n 必须满足 n≥3f+1 2。

然而，这一结论的适用范围受限于系统的同步性假设。在1985年，Fischer、Lynch和Paterson发表了著名的“FLP不可能性”定理，证明了在纯异步系统中，即使只有一个进程可能发生最良性的宕机故障，也不存在任何一个确定性的分布式算法可以在有限时间内解决共识问题 6。FLP 定理揭示了一个根本性的困境：在异步环境中，无法区分一个进程是宕机了还是仅仅经历了极端的网络延迟 12。这一结果意味着，任何声称能在异步网络中保证活性的 BFT 协议，都必须引入额外的假设，例如随机性、故障检测器或最终的网络同步，从而将系统模型从纯异步转变为部分同步。

紧随其后，Dwork、Lynch和Stockmeyer在1988年的论文中正式提出了部分同步模型，并证明了在该模型下，共识问题是可解的 4。他们的工作为FLP不可能性提供了一条出路，并为像 pBFT 这样的实用算法奠定了坚实的理论基础。这些算法的活性保证，正是建立在网络最终会稳定（即进入GST后）的假设之上。

3.3 解决方案的路径：不可伪造的消息

Lamport 等人的论文还探讨了另一种通信模型：“不可伪造的书面消息”（Unforgeable Written Messages），这在现代计算中与使用公钥密码学实现的数字签名机制高度相似 2。当使用这种消息时，叛徒无法伪造忠诚将军的签名，其谎言会被轻易揭穿，从而使得拜占庭将军问题对于任意数量的将军和叛徒都是可解的 7。这两种消息模型——“口头”与“书面”——的区分，深刻地预示了现代 BFT 协议设计的两种核心策略：一种是依赖多轮消息交换和法定人数投票来交叉验证信息（对应口头消息模型），另一种是严重依赖数字签名等密码学工具来验证每一条消息的真实性（对应书面消息模型）。

第二部分：BFT 系统的原理与架构

第 4 节：构建弹性架构：拜占庭容错（BFT）的原理

将拜占庭将军问题的理论转化为能够在现实世界中抵御恶意行为的工程实践，需要一套稳健的架构原则。这些原则共同构成了拜占庭容错系统的基础，确保了即使在部分组件行为不可预测的情况下，系统整体仍能保持一致和可用。

在深入探讨这些原则之前，必须首先给出安全性和活性的可检验定义，这是评估任何 BFT 协议正确性的基石。

安全性（Safety）的形式化定义：对于任意两个由非故障副本提交的请求，如果它们的序列号相同，那么它们必须是完全相同的请求。这一性质也被称为“不产生相互矛盾的提交”。其保证源于法定人数交集（Quorum Intersection）属性：任何两个用于做出提交决定的法定集合（Quorum），其交集必须至少包含一个诚实的副本。在一个拥有 n=3f+1 个副本的系统中，一个安全的法定人数大小为 2f+1。任意两个大小为 2f+1 的集合，其交集大小至少为 (2f+1)+(2f+1)−(3f+1)=f+1。由于系统中最多只有 f 个拜占庭节点，这个大小为 f+1 的交集中必然包含至少一个诚实节点。这个诚实节点的存在，如同一个不变式，将阻止系统对同一个序列号提交两个相互矛盾的决定。

活性（Liveness）的形式化定义：在部分同步模型下，从全局稳定时间（GST）开始，对于任何由非故障客户端提交的请求，所有非故障副本最终都会在有限时间内提交该请求。这确保了在网络条件恢复正常后，协议必然能够向前推进。

4.1 状态机复制（SMR）与确定性要求

状态机复制（State Machine Replication, SMR）是实现容错的核心技术范式 1。其基本思想是将服务抽象为一个确定性的状态机，并将其复制到多个独立节点上。BFT 协议的核心任务就是确保所有正常运行的副本节点以完全相同的顺序执行完全相同的操作序列 1。

然而，要保证状态机在不同副本上的一致性，必须严格保证其确定性。这意味着对于任何给定的状态和输入，状态转移函数必须产生完全相同的输出和新状态。在工程实践中，必须系统性地剔除所有潜在的非确定性来源：

时间与随机数：不能直接使用本地系统时钟或标准随机数生成器。应使用协议内部生成的逻辑时间戳，或基于共识协商的随机种子。

浮点运算：不同硬件架构可能导致浮点运算结果的微小差异，应避免在状态转移逻辑中使用浮点数，或采用确定性的软浮点库。

系统调用与外部输入：对外部世界的依赖（如文件系统、网络I/O）必须被序列化和确定化。一种常见的做法是对所有外部输入进行哈希快照，并将该哈希值作为共识过程的一部分，确保所有副本基于完全相同的输入视图进行计算。

多线程与内存：并发执行可能引入不确定性。必须确保状态机逻辑的执行是单线程的，或使用确定性的并发控制机制。

状态转移函数的签名可以形式化为 Snew​,O=F(Sold​,I)，其中 S 是状态， I 是输入， O 是输出。判等准则要求对于相同的 Sold​ 和 I，所有诚实副本计算出的 Snew​ 和 O 必须逐位相等。

4.2 n≥3f+1 副本要求的再校准

在部分同步或最终同步模型下，为容忍 f 个拜占庭副本需 n≥3f+1；纯异步下确定性活性受 FLP 不可能性限制 6。因此，任何声称能在异步网络（如互联网）中运行并保证活性的 BFT 协议，都隐式或显式地依赖于超时机制和网络最终会恢复稳定的假设，这实质上是采用了部分同步模型 4。

n≥3f+1 这个要求正是为了在部分同步模型下同时满足安全性和活性。

安全性保证：如前所述，大小为 2f+1 的法定人数确保了任意两个法定人数集合的交集中至少有一个诚实节点，从而防止了决策冲突。

活性保证：活性面临的最大威胁是出现一个恶意的领导者，它可能不发送任何消息，或者与网络分区合谋，将诚实节点分割成无法达成多数的小团体。当总节点数为 3f+1 时，即使有 f 个节点是恶意的，仍然剩下 2f+1 个诚实节点。这个数量的诚实节点本身就足以形成一个安全的法定人数，从而可以投票罢免不作为的恶意领导者，选举出新的领导者，并继续推动共识进程 1。如果总数仅为
3f，那么 f 个恶意节点可以将剩下的 2f 个诚实节点分割成两个各含 f 个节点的组，此时任何一组都无法形成 2f+1 的法定人数，系统将陷入停滞。

4.3 基于法定人数的投票

基于法定人数（Quorum-based）的投票是 BFT 协议中决策制定的核心机制。一个决策只有在获得了一个法定人数的节点同意后，才被认为是有效的 1。法定人数的大小（通常为

2f+1）及其交集属性，是维护系统状态单一历史、防止分叉的关键数学保障。

4.4 密码学机制

密码学工具是 Lamport 论文中“不可伪造的书面消息”的现代实践，为协议提供了可验证的通信环境 1。

认证（Authentication）：通过数字签名或消息认证码（MACs），确保消息来源的真实性。

完整性（Integrity）：通过哈希函数，确保消息在传输过程中未被篡改。

不可否认性（Non-repudiation）：主要通过数字签名实现，为识别和惩罚恶意行为提供了不可辩驳的证据，是实现问责制的基础 1。

第 5 节：一种实际实现：实用拜占庭容错（pBFT）算法

直到1999年，Miguel Castro 和 Barbara Liskov 发表了名为“实用拜占庭容错”（Practical Byzantine Fault Tolerance, pBFT）的论文，才首次展示了一个能够在部分同步网络（如互联网）中高效运行的 BFT 算法，为 BFT 技术的实际应用铺平了道路 8。

5.1 概述与角色

pBFT 旨在提供一个低开销的拜占庭容错状态机复制方案 8。协议定义了清晰的角色：在某个

视图（View） v 中，有一个副本被指定为主节点（Primary），负责对请求定序；其余节点为副本/备份节点（Replicas/Backups），负责验证和投票 1。

5.2 正常情况下的操作：三阶段协议

在没有主节点故障的正常情况下，处理一个客户端请求遵循一个严谨的三阶段协议。每个阶段都有明确的接受/拒绝谓词。

预准备（Pre-prepare）阶段：

动作：主节点接收到客户端请求 m 后，为其分配一个序列号 n，并向所有备份节点广播一个 <<PRE-PREPARE, v, n, d>, m> 消息，其中 d 是 m 的摘要 1。

接受谓词：备份节点 i 接受该消息，当且仅当：

消息签名/MAC 有效。

视图号 v 与 i 的当前视图号匹配。

i 尚未在视图 v 中接受过序列号为 n 但摘要不为 d 的 pre-prepare 消息。

序列号 n 在可接受的区间内（即在日志的水线 h 和 H 之间）。

核心作用：为请求定序并分发。

准备（Prepare）阶段：

动作：接受 pre-prepare 消息后，每个备份节点向所有其他节点广播一个 <PREPARE, v, n, d, i> 消息 1。

接受谓词：节点 j 接受来自 i 的 prepare 消息，当且仅当：

消息签名/MAC 有效。

视图号 v 与 j 的当前视图号匹配。

序列号 n 在可接受的区间内。

核心作用：在副本之间就请求的顺序达成一致，以抵抗恶意主节点的模棱两可攻击。

状态推进：当一个节点（包括主节点）收集到来自 2f 个不同副本的、与其 pre-prepare 消息内容相匹配的 prepare 消息后（加上自身，共 2f+1 个），该节点进入“已准备就绪”（prepared）状态。这证明了网络中至少有一个法定人数就该请求的定序达成了一致 1。

提交（Commit）阶段：

动作：当一个节点进入“已准备就绪”状态后，它会向所有其他节点广播一个 <COMMIT, v, n, i> 消息 1。

接受谓词：节点 j 接受来自 i 的 commit 消息，当且仅当谓词与 prepare 阶段类似。

核心作用：确认一个请求已被足够多的节点所接受，可以安全地执行。

状态推进：当一个节点收集到来自 2f+1 个不同节点的、内容相匹配的 commit 消息后，该节点进入“已提交”（committed）状态。此时，该节点可以安全地执行该请求，并确信所有其他诚实节点最终也会执行该请求 1。

5.3 客户端确认

节点在执行完请求后，会向客户端发送一个回复消息。客户端会等待收集到来自 f+1 个不同节点的相同回复。为防止重放攻击，客户端必须验证这些回复：它们必须来自不同的副本，并且携带单调递增的视图号与唯一的请求序列标识（例如，客户端发起的请求中包含的时间戳或随机数）1。

5.4 故障处理：视图更换协议

为保证系统的活性，pBFT 设计了视图更换协议以应对主节点故障 1。

触发：副本通过超时机制怀疑主节点故障。

提议：怀疑主节点故障的副本向所有其他副本广播一个 view-change 消息，提议切换到下一个视图 v+1。

选举：在新视图 v+1 中，新的主节点（通常是编号为 (v+1)modn 的副本）负责协调。它必须等待并收集到来自 2f 条有效的 view-change 消息作为证据 18。
view-change 消息的最小字段集应包括：提议的新视图号 v+1、发送方已知的最新稳定检查点 s 的证明、以及在 s 之后所有已达到 prepared 状态的请求 P 的证明集合。

确认：新主节点验证这些证据后，广播一条 new-view 消息。该消息必须包含收集到的 2f 条 view-change 消息作为视图更换有效的证明，并根据这些证据确定在新视图中需要重新提议的请求集合，以确保在旧视图中已达成共识的请求不会丢失 18。

5.5 性能优化与工程约束

检查点（Checkpoints）：为防止协议消息的日志无限增长，pBFT 引入了检查点机制。副本仅在收到来自 2f+1 个不同副本、相同序列号与状态摘要的 checkpoint 消息时，标记该检查点为“稳定”，并丢弃更早的日志 1。

密钥与认证机制的工程约束：

混合加密：pBFT 的一个关键优化是正常情况下使用计算开销较低的对称加密消息认证码（MACs），仅在视图更换等低频但需要不可否认证据的异常路径中使用计算开销较高的公钥数字签名 1。

运维成本：使用 MAC 需要为每对副本维护一个共享对称密钥，这导致了 O(n2) 的密钥对规模，给密钥分发和轮换带来了显著的运维成本。

密钥轮换与吊销：在视图更换后，如果某个节点被怀疑密钥泄露，系统必须有机制轮换群组密钥并吊销失效密钥，以维持前向保密性。

权衡：在异常路径（如视图更换）中使用签名，虽然会影响性能，但其提供的不可抵赖证据对于事后审计和问责至关重要。这是一个在性能和可审计性之间的重要权衡。

第 6 节：现代 BFT 协议与性能对比

自 pBFT 问世以来，BFT 领域的研究催生了协议的“寒武纪大爆发”。HotStuff、SBFT 和 BFT-SMaRt 等协议在性能、通信复杂度和活性保证等方面进行了各种权衡和创新。

6.1 BFT 协议对比分析

下表对比了四种代表性的 BFT 协议，数据来源均为其原始学术论文或技术报告。

表 1：现代 BFT 协议对比

6.2 关键创新与权衡

BFT-SMaRt：作为 pBFT 的一个高度优化和模块化的开源实现，BFT-SMaRt 解决了原始 pBFT 实现的一些局限性，如支持动态成员变更和为多核架构优化 20。它展示了在不改变核心
O(n2) 通信模式的情况下，通过工程优化所能达到的性能极限 24。IBM 的 Hyperledger Fabric BFT 排序服务就是基于 BFT-SMaRt 构建的 25。

HotStuff：该协议是为区块链场景设计的，其核心创新在于通过引入一个额外的通信阶段（形成三阶段协议），实现了线性的视图更换和响应性（responsiveness）21。虽然正常情况下的延迟增加到 3 个 RTT，但其“链式”结构天然支持流水线操作，显著提高了吞吐量。其线性的通信复杂度和领导者切换开销是其能够扩展到更大规模节点网络的关键 29。

SBFT：SBFT 通过引入收集器（collectors）和阈值签名来将 pBFT 的二次方通信复杂度降低到线性 22。它还设计了一个
乐观快速路径，在网络状况良好且无故障时，可以实现更低的延迟。SBFT 的设计目标是支持数百个副本的大规模、地理分布式部署 30。

这些现代协议的演进清晰地揭示了一个核心设计趋势：为了突破 pBFT 的可扩展性瓶颈，后续协议愿意接受略微增加的正常路径延迟（如 HotStuff）或引入新的架构组件（如 SBFT 的收集器），以换取通信复杂度和领导者切换开销的根本性降低（从 O(n2) 到 O(n)）。这使得 BFT 技术能够应用于更大规模的联盟链和分布式信任基础设施。

第三部分：在安全关键系统中的应用

第 7 节：故障管理策略：屏蔽与问责

面对系统中可能出现的故障，主要有两种应对策略：故障屏蔽和故障问责，它们服务于不同的系统目标函数。

故障屏蔽（Fault Masking）：这是经典 BFT 协议（如 pBFT）采用的主要策略。其目标函数是最大化服务可用性。通过部署足够多的冗余副本（n≥3f+1），正常节点的“投票”能够压倒并“屏蔽”掉少数故障节点的错误输出，从而完全隐藏故障的影响，使系统能够持续提供正确的服务，仿佛故障从未发生过 1。

故障问责（Accountability）：这是一种替代或补充策略，其目标函数是提供可审计的追溯性。它不承诺服务在故障发生时一定不中断，而是保证一旦发生违反安全规则的行为，系统能够产生不可否认的证据来准确识别出哪个节点是故障节点 1。问责路径要求对关键消息携带签名或可验证的 MAC 证据，形成可审计的事件链条。当证据门槛（例如，一个节点对同一序列号签署了两个不同的摘要）满足时，系统执行隔离与重构。这种方法在资源受限或可以容忍短暂服务中断的场景中更具成本效益，并且可以作为一种补充机制，增强采用故障屏蔽的系统的长期稳定性。

第 8 节：案例研究：航空航天系统中的容错架构

将拜占庭容错的抽象理论应用于现实世界中风险最高的领域——航空航天，可以最深刻地揭示其工程价值。NASA 在其数十年的发展历程中，为应对极端环境下的计算可靠性挑战，开发了一系列先进的容错架构。这些架构的设计理念与 BFT 原则遥相呼应，甚至直接催生了拜占庭问题的形式化。

8.1 SIFT 架构：拜占庭共识的起源

拜占庭将军问题的提出并非纯粹的理论游戏，而是源于一个具体的工程项目——由 NASA 资助、SRI 国际研究所在 20 世纪 70 年代开发的 SIFT（Software Implemented Fault Tolerance，软件实现容错）计算机系统 1。

架构设计：SIFT 系统的核心思想是，容错主要通过软件层面实现。关键的飞行控制任务被复制成多个实例，在不同的商用现成（COTS）处理器上独立、松散同步地执行 1。

容错机制：每个任务迭代完成后，需要使用该任务输出的其他任务会通过软件执行“多数投票”（majority voting）来决定正确的结果 1。这种机制能够处理时序与数值上的不一致，从而容忍任意故障，而不仅仅是失效-停止（fail-stop）故障。

开创性：SIFT 项目的开创性在于，它证明了包括处理拜占庭式不一致行为在内的复杂容错功能，可以主要通过软件编程来实现，而无需依赖于高度定制化的容错硬件 1。这种将容错逻辑从硬件中解耦出来的思想，为后来更通用的 BFT 协议的发展奠定了概念基础。

8.2 航天飞机中的冗余管理与投票

航天飞机的航空电子系统是容错工程史上的一个典范，其设计目标是达到“故障-操作/故障-安全”（Fail-Operational/Fail-Safe）标准 1。

架构设计：核心是一个由五台相同的 IBM AP-101 计算机组成的集群。在关键阶段，其中四台计算机会组成一个冗余集，以“锁步”（lock-step）同步的方式运行完全相同的主航空电子软件系统（PASS）1。第五台计算机则独立运行一套由不同团队开发的
备份飞行系统（BFS）37。

异构软件基线：PASS 和 BFS 构成了“异构软件基线”。这种在相同硬件上运行不同软件的设计，其明确目的是**降低共因失效（common-mode failure）**的风险。如果 PASS 软件中存在一个未被发现的致命缺陷，在特定输入下可能导致所有四台主计算机同时失效。在这种情况下，BFS 作为一套独立的软件实现，极不可能包含相同的缺陷，从而为机组人员提供了最后的安全保障 38。

多级投票/仲裁：该系统通过四重冗余提供了强大的故障检测和屏蔽能力。投票不仅在软件层面进行（比较计算机的输出指令），还在硬件层面实现（例如，作动器内部的机械或液压装置进行“力整合”），构成了典型的多级投票架构 1。

8.3 X-38 飞行器中的拜占庭弹性设计

X-38 乘员返回飞行器的航天电子系统是一个明确应用了拜占庭弹性设计的案例 1。

硬件/软件协同设计：系统的核心是硬件**网络元件（NE）和软件容错系统软件（FtSS）**的协同工作。NE 是一种专用的硬件仲裁器，负责管理冗余计算机之间的数据交换和投票 1。

两轮输入交换：为了处理来自非同步传感器的数据输入（即“不同症状”问题），系统采用了一种两轮交换协议。在第一轮，每个计算机将其从传感器获得的数据通过 NE 广播给所有其他计算机。在第二轮，所有计算机再次广播它们在第一轮收到的所有数据。这个过程与可靠广播或交互一致性算法的目标完全对应：通过两轮交换，所有正常的计算机都能获得一个关于所有输入数据的一致视图，从而有效解决了拜占庭节点可能向不同计算机提供不同输入值的问题 1。

拜占庭性质的边界：NE 和 FtSS 在飞行关键计算机（FCP）的接口层面满足了拜占庭性质，确保了核心计算单元之间的一致性。然而，这种弹性并非贯穿整个系统。由于成本和重量的限制，在 I/O 处理器之外的数据流可能仍然容易受到拜占庭错误的影响。这是一个典型的工程权衡，即在系统的核心部分实现强大的拜占庭容错，而在外围接口则采用较低级别的容错 39。

第 9 节：结论：迈向可认证的 BFT 实施

从理论的诞生到在云计算和航空航天等关键领域的应用，拜占庭容错技术已经证明了其在构建高可靠、高安全系统中的核心价值。现代 BFT 协议通过创新的设计，显著提升了性能和可扩展性，使其在企业级应用中变得愈发可行。然而，在航空电子等安全关键系统中部署 BFT，不仅需要技术上的可行性，更需要满足严格的行业合规性与认证要求。

将 BFT 协议的实施与 DO-178C（机载系统和设备审定的软件考虑）、ARP4754A（民用飞机和系统开发指南）和 ARP4761（民用机载系统和设备安全性评估过程指南）等航空航天标准进行映射，是其走向实际应用的关键一步。

需求可追踪性：BFT 协议的安全性和活性属性（如法定人数交集不变式、视图更换的活性保证）可以被视为顶层安全需求。在认证过程中，必须能够将这些形式化的协议属性，向下追踪到软件架构、代码实现乃至测试用例，形成一条完整的证据链。

形式化规格与覆盖：使用 TLA+ 或 Coq 等形式化方法对 BFT 协议进行建模和验证，可以为认证提供最高级别的保证。形式化规约可以精确定义协议的状态机、不变量和时序属性，而模型检查或定理证明可以系统性地覆盖所有可能的执行路径，包括那些在传统测试中难以触发的复杂故障场景。

FMEA/FTA 切入点：BFT 的故障模型（容忍 f 个任意故障）为系统级的安全性评估，如失效模式与影响分析（FMEA）和故障树分析（FTA），提供了清晰的切入点。分析可以集中于违反该模型的场景（如超过 f 个节点故障、密码学假设被攻破、或确定性状态机实现中的缺陷），并评估其对系统整体安全性的影响。

一个“可认证的 BFT 实施”的最小证据包应至少包含：一份协议的形式化规格、一份关于安全性和活性属性的机器可检查证明、一份将规格映射到软件高级需求的追踪矩阵、以及一套覆盖了所有协议状态转换和异常路径的结构化测试用例。通过构建这样的证据包，BFT 技术将不仅是理论上稳健的，更是工程上可信、合规的，从而为其在下一代安全关键系统中的应用奠定坚实基础。

参考文献

Fischer, M. J., Lynch, N. A., & Paterson, M. S. (1985). Impossibility of Distributed Consensus with One Faulty Process. Journal of the ACM (JACM), 32(2), 374–382. 6

Dwork, C., Lynch, N., & Stockmeyer, L. (1988). Consensus in the Presence of Partial Synchrony. Journal of the ACM (JACM), 35(2), 288–323. 4

Lamport, L., Shostak, R., & Pease, M. (1982). The Byzantine Generals Problem. ACM Transactions on Programming Languages and Systems (TOPLAS), 4(3), 382–401. 9

Castro, M., & Liskov, B. (1999). Practical Byzantine Fault Tolerance. In Proceedings of the Third Symposium on Operating Systems Design and Implementation (OSDI '99) (pp. 173–186). USENIX Association. 16

Castro, M. (2001). Practical Byzantine Fault Tolerance (PhD thesis). Massachusetts Institute of Technology. 8

Bessani, A., Sousa, J., & Alchieri, E. A. (2014). State Machine Replication for the Masses with BFT-SMaRt. In 2014 44th Annual IEEE/IFIP International Conference on Dependable Systems and Networks (DSN) (pp. 355-362). 20

Yin, M., Malkhi, D., Reiter, M. K., Gueta, G. G., & Abraham, I. (2019). HotStuff: BFT Consensus in the Lens of Blockchain. In Proceedings of the 2019 ACM Symposium on Principles of Distributed Computing (PODC). 21

Gueta, G. G., Abraham, I., Grossman, S., Malkhi, D., Pinkas, B., Reiter, M., Seredinschi, D. A., Tamir, O., & Tomescu, A. (2019). SBFT: A Scalable and Decentralized Trust Infrastructure. In Proceedings of the 49th Annual IEEE/IFIP International Conference on Dependable Systems and Networks (DSN). 22

Sousa, J., Bessani, A., & Vukolic, M. (2018). A Byzantine Fault-Tolerant Ordering Service for the Hyperledger Fabric Blockchain Platform. In Proceedings of the 48th Annual IEEE/IFIP International Conference on Dependable Systems and Networks (DSN). 25

Wensley, J. H., Lamport, L., Goldberg, J., Green, M. W., Levitt, K. N., Melliar-Smith, P. M., Shostak, R. E., & Weinstock, C. B. (1978). SIFT: Design and analysis of a fault-tolerant computer for aircraft control. Proceedings of the IEEE, 66(10), 1240–1255. 34

NASA. (1990). Space Shuttle Avionics System. NASA SP-504. 27

NASA. (2010). The X-38 Spacecraft Fault-Tolerant Avionics System. NASA/TM-2010-216431. 1

附录

附录 A：符号表

附录 B：pBFT 消息字段与伪代码

消息格式（最小字段集）

PRE-PREPARE: <"PRE-PREPARE", view: v, sequence: n, digest: d, message: m>

PREPARE: <"PREPARE", view: v, sequence: n, digest: d, replica_id: i>

COMMIT: <"COMMIT", view: v, sequence: n, replica_id: i>

VIEW-CHANGE: <"VIEW-CHANGE", new_view: v+1, last_stable_checkpoint: s, proof_set_C, prepared_set_P, replica_id: i>

NEW-VIEW: <"NEW-VIEW", new_view: v+1, view_change_proofs: V, re-proposal_set: O>

伪代码：备份节点处理 Pre-prepare 消息

Function HandlePrePrepare(message msg):
// 验证消息
IF NOT (VerifySignature(msg) AND
msg.view == self.current_view AND
msg.sequence >= self.low_water_mark AND
msg.sequence <= self.high_water_mark AND
NOT HasAcceptedPrePrepare(msg.view, msg.sequence, msg.digest)):
RETURN // 拒绝消息

// 记录消息
AddPrePrepareToLog(msg)

// 广播 Prepare 消息
prepare_msg = CreatePrepare(self.current_view, msg.sequence, msg.digest)
Broadcast(prepare_msg)

附录 C：图示

图 1：pBFT 三阶段协议消息序列图

Code snippet

sequenceDiagram
participant Client
participant Primary
participant Replica1
participant Replica2
participant Replica3

Client->>Primary: Request (m)
Primary->>Replica1: <<PRE-PREPARE, v, n, d(m)>>
Primary->>Replica2: <<PRE-PREPARE, v, n, d(m)>>
Primary->>Replica3: <<PRE-PREPARE, v, n, d(m)>>

Note over Replica1,Replica3: --- Pre-prepare Phase ---

Replica1-->>Primary: <PREPARE, v, n, d>
Replica1-->>Replica2: <PREPARE, v, n, d>
Replica1-->>Replica3: <PREPARE, v, n, d>
Replica2-->>Primary: <PREPARE, v, n, d>
Replica2-->>Replica1: <PREPARE, v, n, d>
Replica2-->>Replica3: <PREPARE, v, n, d>
Replica3-->>Primary: <PREPARE, v, n, d>
Replica3-->>Replica1: <PREPARE, v, n, d>
Replica3-->>Replica2: <PREPARE, v, n, d>

Note over Replica1,Replica3: --- Prepare Phase (Quorum of 2f+1 reached) ---

Replica1-->>Primary: <COMMIT, v, n>
Replica1-->>Replica2: <COMMIT, v, n>
Replica1-->>Replica3: <COMMIT, v, n>
Replica2-->>Primary: <COMMIT, v, n>
Replica2-->>Replica1: <COMMIT, v, n>
Replica2-->>Replica3: <COMMIT, v, n>
Replica3-->>Primary: <COMMIT, v, n>
Replica3-->>Replica1: <COMMIT, v, n>
Replica3-->>Replica2: <COMMIT, v, n>

Note over Replica1,Replica3: --- Commit Phase (Quorum of 2f+1 reached) ---

Replica1->>Client: Reply
Replica2->>Client: Reply
Replica3->>Client: Reply

Note over Client,Replica3: Client waits for f+1 matching replies

图 2：法定人数交集示意图 (n=4, f=1, Q=3)

Code snippet

graph TD
subgraph System (n=4)
R1(Replica 1)
R2(Replica 2)
R3(Replica 3)
R4(Replica 4 - Byzantine)
end

subgraph Quorum_A (size=3)
R1
R2
R4
end

subgraph Quorum_B (size=3)
R2
R3
R4
end

subgraph Intersection (size=2)
R2
R4
end

Quorum_A -- Intersects with --> Quorum_B
Intersection -- Contains at least one honest node (R2) --> Guarantees_Safety(Safety Guaranteed)

图 3：航天飞机航电冗余结构图

Code snippet

graph TD
subgraph "Avionics System"
direction LR
subgraph "Primary Redundant Set (PASS)"
GPC1(GPC 1)
GPC2(GPC 2)
GPC3(GPC 3)
GPC4(GPC 4)
end
subgraph "Backup System (BFS)"
GPC5(GPC 5)
end
subgraph "Voting & Arbitration"
Voter(Software & Hardware Voting)
end
subgraph "Actuators"
Actuators(Control Surfaces)
end
end
Sensors --> GPC1
Sensors --> GPC2
Sensors --> GPC3
Sensors --> GPC4
Sensors --> GPC5

GPC1 -- Lock-step Execution --> Voter
GPC2 -- Lock-step Execution --> Voter
GPC3 -- Lock-step Execution --> Voter
GPC4 -- Lock-step Execution --> Voter

Crew(Crew Manual Switch) --> GPC5
GPC5 -- Independent Execution --> Voter

Voter --> Actuators

Works cited

拜占庭容错协议及其在安全关键系统中的应用技术分析.docx

What Is the Byzantine Generals Problem? - River Financial, accessed September 29, 2025,

practical Byzantine Fault Tolerance(pBFT) - GeeksforGeeks, accessed September 29, 2025,

Consensus in the Presence of Partial Synchrony - Research, accessed September 29, 2025,

Consensus in the Presence of Partial Synchrony | Request PDF - ResearchGate, accessed September 29, 2025,

Impossibility of Distributed Consensus with One Fault Process. - DTIC, accessed September 29, 2025,

The Byzantine Generals Problem, accessed September 29, 2025,

Practical Byzantine Fault Tolerance - Microsoft, accessed September 29, 2025,

The Byzantine Generals Problem - LESLIE LAMPORT, ROBERT SHOSTAK, and MARSHALL PEASE - SRI International, accessed September 29, 2025,

Untitled - Microsoft, accessed September 29, 2025,

The impossibility result of Fischer, Lynch, and Paterson and its proof, accessed September 29, 2025,

Impossibility of Distributed Consensus with One Faulty Process - Lawrence Kesteloot, accessed September 29, 2025,

Consensus in the Presence of Partial Synchrony - Cynthia Dwork, Nancy Ann Lynch, Massachusetts Institute of Technology. Laboratory for Computer Science, L. Stockmeyer - Google Books, accessed September 29, 2025,

CONSENSUS IN THE PRESENCE OF PARTIAL SYNCHRONY (Preliminary Version) - Research, accessed September 29, 2025,

Network Bandwidth Variation-Adapted State Transfer for Geo-Replicated State Machines and its Application to Dynamic Replica Replacement - arXiv, accessed September 29, 2025,

Practical Byzantine Fault Tolerance | USENIX, accessed September 29, 2025,

Practical Byzantine Fault Tolerance - USENIX, accessed September 29, 2025,

Practical Byzantine Fault Tolerance - Programming Methodology Group, accessed September 29, 2025,

Practical Byzantine Fault Tolerance., accessed September 29, 2025,

State machine replication for the masses with BFT-SMART - ULisboa Research Portal, accessed September 29, 2025,

HotStuff: BFT Consensus in the Lens of Blockchain - Metadata, accessed September 29, 2025,

(PDF) SBFT: a Scalable and Decentralized Trust Infrastructure (2018) | Guy Golan Gueta | 255 Citations - SciSpace, accessed September 29, 2025,

‪Alysson Bessani‬ - ‪Google Scholar‬, accessed September 29, 2025,

State Machine Replication for the Masses with BFT-SMART, accessed September 29, 2025,

A byzantine Fault-Tolerant ordering service for the hyperledger fabric blockchain platform - University of Lisbon - ULisboa Research Portal, accessed September 29, 2025,

A Byzantine Fault-Tolerant Ordering Service for the Hyperledger Fabric Blockchain Platform, accessed September 29, 2025,

A byzantine fault-tolerant ordering service for the hyperledger fabric blockchain platform, accessed September 29, 2025,

HotStuff: BFT Consensus in the Lens of Blockchain - Semantic Scholar, accessed September 29, 2025,

HotStuff: BFT Consensus in the Lens of Blockchain, accessed September 29, 2025,

SBFT: a Scalable and Decentralized Trust Infrastructure - arXiv, accessed September 29, 2025,

SBFT: A Scalable and Decentralized Trust Infrastructure - People @EECS, accessed September 29, 2025,

Cyber Security and IT Infrastructure Protection, accessed September 29, 2025,

The Fault Detection Problem - Max Planck Institute for Software ..., accessed September 29, 2025,

SIFT - Design and analysis of a fault-tolerant computer for aircraft control - NASA Technical Reports Server (NTRS), accessed September 29, 2025,

SIFT: Design and Analysis of a Fault-Tolerant ... - Leslie Lamport, accessed September 29, 2025,

A History of Research in Fault Tolerant Computing at SRI International, accessed September 29, 2025,

The Space Shuttle Primary Computer System - klabs.org, accessed September 29, 2025,

The Legacy of Space Shuttle Flight Software, accessed September 29, 2025,

The X-38 Spacecraft Fault-Tolerant Avionics System :'~~::, accessed September 29, 2025,

Practical Byzantine Fault Tolerance - Microsoft Research, accessed September 29, 2025,

SBFT: A Scalable and Decentralized Trust Infrastructure - Bar-Ilan University, accessed September 29, 2025,

The Proof of the SIFT Implementation - NASA Technical Reports Server (NTRS), accessed September 29, 2025,