作者：王永革教授，著名华裔密码学家，北卡罗来纳大学夏洛特分校 (UNC, Charlotte) 计算机系终身教授，德国海德堡大学获得博士学位，Sperax首席科学家。
共识协议的设计一直是一个很具有挑战性的课题。图灵奖获得者 Lamport 在 1989 年用古希腊帕克西岛 (Paxos) 上的一群业余立法议员制定法律的过程描述了他所设计的可用于分布式计算的 Paxos 共识协议。Lamport 将他的文章投给了 ACM TOCS。也许这个杂志的编辑没领会到该文章的重要性，所以一直没同意发表。直到 Paxos 共识协议被学术界广泛讨论并被工业界广泛应用，该杂志才在 1998 年发表了该文章：
Lamport, Leslie. The part-time parliament. ACM Transactions on Computer Systems (TOCS) 16.2 (1998): 133-169.
Lamport 自我调侃说这是他的所有文章中等待发表时间第二长的一篇文章。到目前为止，Paxos 共识协议几乎被使用于所有的分布式系统。比如 Google 的 Bigtable 使用 Chubby lock service 系统来保证各个节点数据的一致性。而 Chubby lock service 就是基于 Paxos 协议的。此外，微软，IBM，亚马逊的云服务系统都用 Paxos 协议为其提供系统的一致性。粗略来讲，Paxos 协议由一系列 ROUND 组成。ROUND 由 0 开始直到共识达成。每个 ROUND 分以下四步：
1. 主节点生成一个序列号，向所有节点广播。希望大家参与该序列号的活动
2. 每个节点发给主节点以下信息：他所参与投过票的序列号和他投过的票
3. 主节点在收到第二步的大部分回复后，选取一个不会违反 SAFETY 的数值 v。把这个值 v 广播给所有的节点
4. 每个节点在收到主节点第三步的值 v 后，投票给 v 并向所有节点广播他的投票
由于 Paxos 协议比较难于实现，斯坦福的研究者在 2014 年提出了模块化的易于实现的 Paxos 协议，并将其命名为 Raft 协议。Paxos/Raft 协议是在比较温和的威胁模型里工作的。换句话说，该协议只对异步网络里的非拜占庭错误具有鲁棒性。在非拜占庭威胁模型里，出错的节点只能犯被动性的错误（比如停止工作）而不能展开具有主动进攻性的攻击。具有 n 个节点的系统最多能容忍的非拜占庭错误节点数是（n-1）/2。Paxos/Raft 协议达到了这个最大的容错节点数。
因为 Paxos/Raft 协议对拜占庭错误不具有鲁棒性，他们是无法在开放的网络系统（比如区块链系统）里使用的。拜占庭错误是具有主动攻击性的错误，比如：说谎，伪造消息，合谋攻击，或者展开具有选择性的 DoS 攻击。我们在之前的文章中已经提到，去中心化的区块链系统是基于开放的网络系统的，所以我们必须使用拜占庭威胁模型。
目前市场上的区块链里使用最多的拜占庭协议是图灵奖获得者 Barbara Liskov 和她的学生 Castro 设计的实用拜占庭容错系统 PBFT (practical BFT)。PBFT 被广泛使用于联盟链（比如 Hyperledger sawtooth 和趣链科技的 Hyperchain）和很多公链。PBFT 可以被看作是 Paxos 协议的拜占庭版本。其主要区别在于 PBFT 在 Paxos 协议中加入了一个验证步骤来防止拜占庭错误。在分析其安全性之前，我们先给出其协议的形式化描述。
在 PBFT 协议中，我们假定有 n=3t+1 个节点 P1, …, Pn。其中最多 t 个节点被攻击者所控制。PBFT 要求所有的节点共同维护一个状态并采取一致的行动。PBFT 协议是通过一系列的视图 (view) 来进行的。在每一个视图里，有一个节点被称为主节点 (leader)。PBFT 系统首先从视图 (v=0) 开始，然后通过视图更换协议进入视图 v=1, v=2, … 等等。只有在系统认为主节点不能正常工作时，才会启动视图更换协议进入下一个视图。我们假定所有的节点都知道每一个视图的主节点是谁。每当一个客户提交一个任务给当前视图的主节点后，PBFT 协议将进行三个阶段的通信：序号分配（pre-prepare），相互交互（prepare），和 序号确认（commit）。序号分配（pre-prepare）阶段对每个任务分配一个序列号，相互交互（prepare）和 序号确认（commit）阶段对所有的任务提供一个全局的排序。假定我们现在在视图 v，并且主节点是 Pi。那么整个协议的过程如下：
1. 客户端发送任务请求 m，激活主节点的服务操作。
2. 当主节点 Pi 接收任务请求 m 后，启动三阶段的协议：
a. 序号分配（pre-prepare）阶段：主节点选择一个唯一的序列号 seq 给任务请求 m。主节点然后向所有的节点广播以下消息
m,<PRE-PREPARE, v, seq, H(m)>，SIGNATURE
其中 H 是一个哈希函数。一个节点 Pj 接受以上的消息，如果以下的条件都满足
i. 数字签名 SIGNATURE 有效
ii. Pj 尚未接受另一个含有相同 v, seq 的另一任务请求
iii. 序列号 seq 在合理的范围内
b. 相互交互（prepare）阶段：如果节点 Pj 接受接受了主节点的广播消息，那么 Pj 进入相互交互（prepare）阶段并对所有的节点广播以下消息
<PREPARE, v, seq, H(m), Pj>，SIGNATURE
c. 序号确认（commit）阶段：对于节点 Pj 来说，一个数组<m, v, seq, Pj>是准备好了的当且仅当 Pj 收到了至少 2t 个有效的消息<PREPARE, v, seq, H(m), P>。当数组<m, v, seq, Pj>对 Pj 来说是准备好了后，Pj 对所有的节点广播以下确认消息：
<COMMIT, v, seq, H(m), Pj>，SIGNATURE
当一个节点收到 2t+1 个确认消息后，该节点将执行任务请求 m 中所包含的任务，并将结果直接发送给客户。
3. 客户端等待来自不同节点的回复，若有 t+1 个回复相同，则该回复即为运算的结果。
最近我们在如下文章中对 PBFT 的安全性进行了分析：
Yongge Wang. Byzantine Fault Tolerance in Partially Connected Asynchronous Networks
该文章的分析结论是 PBFT 共识协议在异步网络里是不安全的。我们在本文，简单的介绍我们设计的在异步网络里对 PBFT 协议的攻击办法。为了简化我们的描述，我们假定系统有 n=3+1=4 个节点 P1,P2, P3, P4。其中节点 P1 被攻击者控制。另外我们假定视图 v 的主节点是 P1。我们的攻击在视图 v 展开：
1. 在视图 v 的序号分配（pre-prepare）阶段，主节点 P1 把广播消息「m, <PRE-PREPARE, v, seq, H(m) >，SIGNATURE」发送给 P1,P2, P3。但是不发给 P4。
2. 在相互交互（prepare）阶段，P1 把广播消息「<PREPARE, v, seq, H(m), P1>，SIGNATURE」发送给 P1,P2, P3。但是不发给 P4。在相互交互（prepare）阶段，节点 P2, P3 会把广播消息「<PREPARE, v, seq, H(m), P2>，SIGNATURE」和「<PREPARE, v, seq, H(m), P3>，SIGNATURE」发给所有的节点。当然了，如果可能，攻击者也许会发起 DoS 攻击，让节点 P4 不会接受到节点 P2, P3 的广播消息（这个 DoS 攻击对我们的攻击来讲不是很重要）。到此时，数组<m, v, seq, Pj>对节点 P1,P2, P3 来说是准备好了。因为 P4 最多收到了两个相互交互消息，而我么最少需要 2+1=3 个消息来准备好一个数组，所以对 P4 来说，该数组并没有准备好。
3. 在序号确认（commit）阶段，P1 把广播消息「<COMMIT, v, seq, H(m), P1>，SIGNATURE」发送给 P1,P2。但是不发给 P4。在序号确认（commit）阶段，节点 P2, P3 会把广播消息「<COMMIT, v, seq, H(m), P2>，SIGNATURE」和「<PREPARE, v, seq, H(m), P3>，SIGNATURE」发给所有的节点。当然了，如果可能，攻击者也许会发起 DoS 攻击，让节点 P4 不会接受到节点 P2, P3 的广播消息（这个 DoS 攻击对我们的攻击来讲不是很重要）。到此时，节点 P1,P2 收到了 3 个对任务 m 的确认消息。节点 P3 和 P4 最多收到 2 个对任务 m 的确认消息。所以节点 P2 将执行任务请求 m 中所包含的任务，并将结果直接发送给客户。但是 P1,P3, P4 不会执行该任务。所以客户收不到足够的回复。
在实行了以上的攻击后，节点 P1 将不再回复任何视图 v 的任何消息。所以系统将启动视图更换协议进入下一个视图 v +1。在进入视图 v +1 后，诚实节点的 P2,P3, P4 的内部数据状态是不一样的。所以系统进入了不协调的状态。
在 PBFT 协议中，为了解决有些节点可能会收不到某些消息（比如我们以上攻击情景），PBFT 协议设计了 CHECKPOINT 状态更新过程。特别的，每执行 100 个任务后，每个节点 Pj 会广播其当前状态的消息给所有的节点：
<CHECKPOINT, seq, H(state), Pj>，SIGNATURE
如果一个节点 Pi 收到 2t+1 个如上的状态更新消息，并且其状态 state 的，那么节点 Pi 将用如上消息里的状态 state 替换自己的当前状态。在我们的如上攻击中，如果不诚实的节点 P1 不发布状态更新消息，那么 P2 发布的状态更新消息将不同于 P3 和 P4 发布的状态更新消息。因为我们至少需要 2+1=3 个相同的状态更新消息来更新一个节点的状态，P2 的状态是没法更新到 P3 和 P4 的状态的。所以系统将一直处于不协调状态。
在以后的视图里，不诚实的节点 P1 可以和诚实的节点 P3，P4 合作共同执行客户端的另一个任务请求。所以各个节点的状态将进入不可恢复的不协调状态。
在我们的前一篇文章里，我们提到，在基于 Internet 的区块链技术中，DoS 攻击是很容易展开的。由于 Internet 是一个异步网络，所以我们用以下模型来刻画其网络通信：
存在一个 Global Stabilization Time (GST)，在 GST 之前，任何消息可能丢失（比如 DoS 攻击），或被重新排序。在 GST 之后，网络变为同步网络。但是 GST 什么时候开始，没有人知道。
所以说，我们以上的攻击在异步网络的 GST 之前是可以展开的。那么如果一个区块链系统使用 PBFT 作为其共识协议，我们以上的攻击结果是什么样的？一般来说，在发起如上攻击收，该区块链系统首先会出现分叉，然后将进入死机状态（也就是说，区块链将没有任何新的区块可以生成）。特别的，加入在展开我们所描述的以上攻击之前，大家达成共识的区块链是：A→B→C→D。攻击者用以上的攻击方案，先让 P2 决定下一个区块是 E。也就是说在 P2 的记录里，当前区块链是：A→B→C→D→E。但是 P3，P4 所记录的当前区块链仍然是 A→B→C→D。然后攻击者 P1 让节点 P3，P4 决定下一个节点为 F。这样在 P3，P4 的记录里，当前区块链是：A→B→C→D→F。因为区块 E 不同于区块 F。区块链产生了分叉。由于下一个区块必须有当前区块链延伸出去。如果节点从现在开始不在参与任何活动，那么系统没发得到最小的投票数 2+1=3。所以没有新的区块可以生成。综合起来，我们在本文的分析结论是：PBFT 共识协议没法保证区块链系统的安全性（safety）和活性（liveness）需求。所以我们建议，不论是联盟链或公链，都不应该用 PBFT 做为其共识协议。
