区块链之拜占庭容错算法——Practical Byzantine Fault Tolerance(PBFT)

实用拜占庭容错算法（PBFT）是由 Barbara Liskov 和 Miguel Castro 于 90 年代末提出的一种共识算法。原论文链接如下：

http://pmg.csail.mit.edu/papers/osdi99.pdf

pBFT 被设计为在异步（响应请求的时间没有上限）系统中高效运行。它针对低开销时间进行了优化。其目标是解决现有拜占庭容错解决方案中存在的许多问题。应用领域包括分布式计算和区块链。

PBFT在保证可用性和安全性（liveness & safety）的前提下，提供了(n-1)/3的容错性，意思就是如果系统内有n台机子，那么系统最多能容忍的作恶/故障节点为(n-1)/3个。（作恶节点可以不响应或者回应错误的信息）。

也就是说为了保证pbft算法的正确性，节点总数量n和作恶节点数量f必须满足n > 3f，如何证明呢？

我们在设计异步通信算法的时候，我们不知道那f个节点是恶意节点还是故障节点，这f个节点可以不发送消息，也可以发送错误的消息，所以在设计阈值的时候，我们要保证必须在n-f个状态复制机的沟通内，就要做出决定；而且我们并不知道，这n-f个里面有几个是作恶节点，我们必须保证正常的节点大于作恶节点数。所以有 n-f-f > f，从而得出了n > 3f。

一、拜占庭将军问题

Byzantine Generals' Problem 拜占庭将军问题在 1982 年微软研究院由 LESLEY LAMPORT、ROBERT SHOSTAK 和 MARSHALL PEASE 撰写的论文中得到了恰当的解释：

想象一下，拜占庭军队的几个分队在敌对城市外扎营，每个分队由各自的将军指挥。将军们只能通过信使互相通信。在观察了敌人之后，他们必须制定一个共同的行动计划。然而，一些将军可能是叛徒，试图阻止忠诚的将军们达成一致。将军们必须决定何时进攻城市，但他们需要大部分军队同时进攻。忠诚的将军们必须有一个算法来保证：

(a)所有忠诚的将军们制定相同的行动计划

(b)少数叛徒不能导致忠诚的将军们采纳一个糟糕的计划。

忠诚的将军们会按照算法所说的去做，但叛徒们可以随心所欲。算法必须保证条件(a)，无论叛徒们做什么。忠诚的将军们不仅要达成一致，而且要同意一个合理的计划。

如果网络中正确工作的节点能够就它们的值达成一致，那么就可以实现拜占庭容错。可以给缺失的消息指定一个默认投票值，也就是说，如果在一定时间限制内没有收到来自特定节点的消息，我们可以假设该消息是“有故障的”。此外，如果大多数节点响应了正确的值，我们还可以分配一个默认响应。莱斯利·兰伯特证明，如果我们有 3m+1 个正确工作的处理器，那么如果最多 m 个处理器有故障，就可以达成共识（对相同状态的一致意见）。

二、PBFT流程

PBFT是一种状态机副本复制算法，即服务作为状态机进行建模，状态机在分布式系统的不同节点进行副本复制。每个状态机的副本都保存了服务的状态，同时也实现了服务的操作。

所有的副本在一个被称为视图（View）的轮换过程中运作。在某个视图中，一个副本作为主节点（primary），其它的副本节点作为备份节点（backups）。视图是连续编号的整数。主节点由公式p = v mod |R|计算得到，v是视图编号，p是副本编号，|R|是副本集合的个数。当主节点失效的时候就需要启动视图轮换过程。

在启用 pBFT 的分布式系统中，节点按顺序排列，其中一个节点是主节点（或领导者节点），其他节点被称为次级节点（或备份节点）。请注意，系统中的任何符合条件的节点都可以通过从次级节点转变为主节点来成为主节点（通常情况下，在主节点故障时）。目标是所有诚实节点通过多数规则帮助达成关于系统状态的共识。一个实用的拜占庭容错系统可以在满足最大恶意节点数量不超过系统所有节点总数三分之一的前提下运行。随着节点数量的增加，系统安全性会提高。pBFT 共识轮次分为四个阶段（参考下图）：

1）客户端发送请求给主节点

2）主节点广播请求给其它节点，节点执行PBFT算法的三阶段（pre-prepare阶段( 预准备阶段),prepare阶段( 准备阶段)，commit 阶段(提交阶段)）共识流程。

3）节点处理完三阶段流程后，返回消息给客户端。

4）客户端收到来自 f+1 个节点的相同消息后，代表共识已经正确完成。

Request阶段：在每一个视图中会选择一个主节点（这里假设是0节点），客户端会发送请求给主节点。

Pre-prepare阶段：节点收到pre-prepare消息后，会有两种选择，一种是接受，一 种是不接受。拒绝的逻辑就是主节点不会发送两条具有相同的v和n，但d和m却不同的消息。其中v是视图编号，d是客户端消息摘要，m是消息内容，n主要用于对客户端的请求进行排序。

Prepare阶段：副节点同意请求后会向其它节点（包括主节点）发送prepare消息。同一时刻不是只有一个节点在进行这个过程，可能有n个节点也在进行这个过程。同一个节点既在发prepare，也在收到其他节点的prepare消息。在一定时间范围内，一个节点如果收到2f+1个不同节点的prepare消息，就代表prepare阶段已经完成。

Commit阶段：所有节点向其它节点广播commit消息，同理，这个过程可能是有n个节点也在进行的。因此可能会收到其它节点发过来的commit消息，当收到2f+1条commit消息后(包括该节点本身)，代表大多数节点已经进入commit阶段，这一阶段已经达成共识，于是节点就会执行请求，写入数据。

Reply阶段：客户端如果收到f+1个相同的REPLY消息，说明客户端发起的请求已经达成全网共识，否则客户端需要判断是否重新发送请求给主节点。

为什么prepare和commit阶段都需要收到2f+1呢？

为了保证一致性，考虑最坏的情况：我们假设收到的有f个是正常节点发过来的，也有f个是恶意节点发过来的，那么，第2f+1个只可能是正常节点发过来的。（因为我们限制了最多只有f个恶意节点）由此可知，“大多数”正常的节点还是可以让系统工作下去的。

为什么reply阶段都需要收到2f+1呢？

我们还是来考虑最坏的情况，我们假设这f+1个相同的reply中，有f个都是恶意节点。

所以至少有一个rely是正常节点发出来的，因为在prepare阶段，这个正常的节点已经可以保证prepared(m,v,n,i)为真，所以已经能代表大多数的意见，所以，client只需要f+1个相同的reply就能保证他拿到的是整个系统内“大多数正常节点“的意见，从而达到一致性。

三、PBFT算法的优缺点

（1）优点

A、PBFT算法具有高交易通量和吞吐量，高可用性，易于理解的优点。

B、解决了原始拜占庭容错(BFT)算法效率不高的问题，将算法复杂度由指数级降低到多项式级，使得拜占庭容错算法在实际系统应用中变得可行。

C、使用了加密技术来防止欺骗攻击和重播攻击，以及检测被破坏的消息。消息包含了公钥签名（其实就是RSA算法）、消息验证编码（MAC）和无碰撞哈希函数生成的消息摘要（message digest）。

（2）缺点

PBFT算法的缺点:

A、计算效率依赖于参与协议的节点数量，由于每个副本节点都需要和其它节点进行P2P的共识同步，因此随着节点的增多（100个左右时），性能会下降的很快，但在较少节点的情况下可以有不错的性能，并且分叉的几率很低，不适用于节点数量过大的区块链，扩展性差。t同事由于节点较少pBFT 机制容易受到 Sybil 攻击，即一个实体（一方）控制多个身份。

B、PBFT算法要求总节点数n>=3f+1(其中，f代表恶意节点数)。系统的失效节点数量不得超过全网节点的1/3，容错率相对较低。

C、PBFT在网络不稳定的情况下延迟很高。

四、PBFT算法的应用场景

PBFT算法的节点数量是固定的，节点身份提前确定，无法动态添加或删除，只能适用于节点数目固定的联盟链或私有链场景中。

PBFT在很多场景都有应用，在区块链场景中，一般适合于对强一致性有要求的私有链和联盟链场景，但如果能够结合DPOS节点代表选举规则，也可以应用于公有链，并且可以在一个不可信的网络里解决拜占庭容错问题。在Hyperledger Fabric项目中，共识模块被设计成可插拔的模块，支持像PBFT、Raft等共识算法。