拜占庭容错

拜占庭容错研究的是当某些进程可能任意失败（包括发送冲突或恶意消息）时如何达成一致。

Definition

拜占庭故障是指组件规范的任意偏差，包括恶意行为；拜占庭容错是指分布式协议在存在有限数量的此类故障参与者的情况下，仍能满足其正确性条件的能力。

Scope

本主题涵盖了拜占庭将军问题及其建立的严格弹性界限（至少需要3f+1个进程，或签名消息，才能容忍f个任意故障），同步口头和签名消息一致性算法，以及实用的异步拜占庭容错协议，例如PBFT及其后代。它是许可区块链和高完整性复制服务信任模型的基础。

Core questions

• 需要多少个正确进程才能容忍给定数量的任意故障？
• 数字签名如何改变拜占庭一致性的弹性界限？
• 如何使拜占庭一致性足够高效以用于实际的异步系统？

Key theories

拜占庭将军界限

在未经认证（口头）消息的情况下，当且仅当超过三分之二的进程是正确的（n > 3f）时，拜占庭一致性问题才可解决；带有不可伪造签名的认证消息放宽了这一要求。

实用拜占庭容错复制

PBFT表明，拜占庭一致性可以在部分同步系统中使用状态机复制（state-machine replication）运行，采用主节点和三阶段协议，在容忍高达三分之一的故障副本的同时实现实用性能。

同步一致性算法

在同步模型中，递归口头消息和签名消息算法在f+1轮中达成一致，说明了容忍任意故障的轮次复杂性成本。

Clinical relevance

拜占庭容错是系统抵御崩溃、入侵或恶意行为的基础，这些系统包括许可区块链、高保障复制服务以及航空电子和航空航天控制，在这些领域中不能排除任意组件故障的可能性。

History

Pease、Shostak和Lamport于1980年确立了一致性界限，并于1982年将其戏剧化为拜占庭将军问题；近二十年来，拜占庭一致性被认为在实践中成本过高，直到Castro和Liskov于1999年提出的PBFT展示了高效的异步拜占庭复制，才使该领域得以复兴，并随后为区块链共识提供了信息。

Key figures

• Leslie Lamport
• Robert Shostak
• Marshall Pease
• Miguel Castro
• Barbara Liskov

Seminal works

• lamport1982byz
• castro1999
• pease1980

Frequently asked questions

为什么容忍f个拜占庭故障需要3f+1个进程？

正确进程必须达成多数决策，即使f个故障进程撒谎，另外f个进程可能缓慢或无法访问；只有当正确进程的数量是故障进程数量的三倍以上时，正确多数才能始终压倒故障和滞后参与者的组合。