共识算法系列：PBFT算法关键点综述、优缺点总结

本文参考：

Byzantine fault tolerance
Practical Byzantine Fault Tolerance
区块链核心技术：拜占庭共识算法之PBFT
美图技术团队：raft和pbft算法
pbft算法理解

---

我们之前讨论过的Raft和Paxos，都是非常高效的算法，他们只支持CFT（Crash fault tolerance），只允许系统内节点宕机（crash），并不考虑系统内有作恶节点。

但是对于开放区块链系统（公有链）来说，任何节点都可以加入这个网络中，那么就必须要考虑作恶节点的问题。对于这个问题Lamport老爷子走就在他的论文中提出：

拜占庭将军问题（Byzantine Generals Problem），是由Leslie Lamport在其同名论文中提出的分布式对等网络通信容错问题。在分布式计算中，不同的计算机通过通讯交换信息达成共识而按照同一套协作策略行动。但有时候，系统中的成员计算机可能出错而发送错误的信息，用于传递信息的通讯网络也可能导致信息损坏，使得网络中不同的成员关于全体协作的策略得出不同结论，从而破坏系统一致性。拜占庭将军问题被认为是容错性问题中最难的问题类型之一。

BFT从上世纪80年代开始被研究，目前已经是一个被研究得比较透彻的理论，具体实现都已经有现成的算法。其中，PBFT是当中最著名的算法，PBFT是Practical Byzantine Fault Tolerance的缩写，意为实用拜占庭容错算法。该算法是Miguel Castro和Barbara Liskov在1999年提出来的，解决了原始拜占庭容错算法效率不高的问题，将算法复杂度由指数级降低到多项式级，使得拜占庭容错算法在实际系统应用中变得可行。

---

简介

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

网络上很多关于PBFT的文章都是抄来抄去，甚至有很多概念上的错误，所以最好还是推荐读PBFT的原文Practical Byzantine Fault Tolerance同时在这里推荐两篇我觉得写的比较好的文章：

区块链核心技术：拜占庭共识算法之PBFT
美图技术团队：raft和pbft算法

为了保证pbft算法的正确性，节点总数量n和作恶节点数量f必须满足n > 3f。至于原因，我们接着往下看。

The resiliency of our algorithm is optimal: 3f + 1 is the minimum number of replicas that allow an asynchronous system to provide the safety and liveness properties when up to f replicas are faulty (see [2] for a proof). This many replicas are needed because it must be possible to proceed after communicating with n - f replicas, since f replicas might be faulty and not responding. However, it is possible that the f replicas that did not respond are not faulty and, therefore, f of those that responded might be faulty. Even so, there must still be enough responses that those from non-faulty replicas outnumber those from faulty ones, i.e., n - 2f > f. Thereforen n > 3f.

对于原文的理解：假设作恶节点数量为f（注意：作恶节点可能不发送任何消息，也可能发送错误消息），那么为了保证一致性达成，系统内节点数量必须大于3。为什么呢？原文的意思是：因为我们知道有f个作恶节点，所以我们必须在n-f个状态复制机的沟通内，就要做出决定（为什么呢？因为我们在设计异步通信算法的时候，我们不知道那f个节点是恶意节点还是故障节点，这f个节点可以不发送消息，也可以发送错误的消息，所以在设计阈值的时候，我们要保证必须在n-f个状态复制机的沟通内，就要做出决定，因为如果阈值设置为需要n-f+1个消息，那么如果这f个作恶节点全部不回应，那这个系统根本无法运作下去）。

在n-f个状态复制机的沟通内，就要做出决定。而且我们无法预测这f个作恶节点做了什么（错误消息/不发送），所以我们并不知道，这n-f个里面有几个是作恶节点，我们必须保证正常的节点大于作恶节点数。所以有 n-f-f > f，从而得出了n > 3f。

这里顺便提供⽹上看到的⼀个证明，但原理也是一样的：

• Liveness要求，Q <= n-f; (Q是要进行选举的法定⼈数，系统要能保证正常跑着，不中断，法定 人数不能多于可以进行选举的人数n-f)。

• Safy要求，根据quorum intersection property: 2Q-n > f，(2个不同的提议情况如何达成一致，只 要有分别支持两个提议的人有交叉，而且交叉的是⼀个non-faulty节点，就能达成一致，这是2Q-n > 0的情况，PBFT容忍f个faulty节点，所以需要有f个non-faulty的交叉) n+f < 2Q <= 2(n - f) => f < n/3 => n > 3f。最⼩n为3f+1。

---

算法分析

为了避遍内容重复，关于PBFT的算法细节，推荐大家这三篇文章，可根据需求服用。（当然还是看原论文最好）

Practical Byzantine Fault Tolerance（原论文）
区块链核心技术：拜占庭共识算法之PBFT
美图技术团队：raft和pbft算法

我们直接来总结PBFT算法当中的一些要点：

prepare和commit阶段为何都要2f+1个节点反馈确认?（这2f+1并不一定是相同的）

对于prepare和commit来说，节点需要在2f+1个状态复制机的沟通内就要做出决定，这是刚好可以保证一致性的，考虑最坏的情况：我们假设收到的有f个是正常节点发过来的，也有f个是恶意节点发过来的，那么，第2f+1个只可能是正常节点发过来的。（因为我们限制了最多只有f个恶意节点）由此可知，“大多数”正常的节点还是可以让系统工作下去的。所以2f+1这个参数和n>3f+1的要求是逻辑自洽的。

还有网上的另一个证明，但是其实也是一个意思：

某副本收到f+1个相同的反馈确认，如果这f+1个反馈中包含faulty节点发过来的消息，是不能作数的，因为faulty节点是墙头草，给副本i发送的消息和副本j发送的消息不一致(类⽐一下一个汉奸跟游击队说⾃己是爱国的，跟⻤子说⾃己是忠⼼的)。必须要2f+1个相同的反馈确认才能保证f+1个non-faulty节点正常，这时候即便f个faulty节点给不同⼈发不同消息也没关系，f+1个non-faulty节点已经形成了统一战线，他们在⼈数上已经多于那些墙头草了，可以达成⼀致了。

因此，如果顺利的话，一个节点收到1个pre-prepare消息和2f个和prepare消息进入commit阶段，2f+1个commit消息后可以reply给client，client收到f+1个回复就可以确认提交成功。

client为何只需要f+1个相同的回复就可确认？

之前我们说，prepare和commit阶段为何都要2f+1个节点反馈，才能确认。client只需要f+1个相同的reply就可以了呢？我们还是来考虑最坏的情况，我们假设这f+1个相同的reply中，有f个都是恶意节点。

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

如果primary是恶意节点呢？

对于一致性，我们可以这么看：如果prepared(m，v，n，i)为真，那么prepared(m’，v，n，j)一定是错误的，因为对于同一个提案我们不可能有两种结果，从而保证整个系统的一致性。

假设primary节点是恶意的，那么意味着在replicas节点中⾄多有f-1个恶意的节点，prepared(m，v，n，i)为真，则证明有f+1个善意节点达成了了⼀致，prepared(m’，v，n，j)为真，意味着另外f+1个善意节点达成了一致，因为系统中只有2f+1个善意节点，因此最少有⼀个善意节点发送了两个冲突的prepare消息，这是不可能的。所以prepared(m，v，n，i)为真，那么prepared(m’，v，n，j)是错误的。

总结

特征/优点：

• 通信复杂度O(n^2)

• 首次提出在异步网络环境下使用状态机副本复制协议，该算法可以工作在异步环境中，并且通过优化在早期算法的基础上把响应性能提升了一个数量级以上。作者使用这个算法实现了拜占庭容错的网络文件系统（NFS），性能测试证明了该系统仅比无副本复制的标准NFS慢了3%。

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

• 适用于permissioned systems (联盟链/私有链)，能容纳故障节点，也能容纳作恶节点。要求所有节点数量至少为3f+1（f为作恶/故障不回应节点的数量），这样才能保证在异步系统中提供安全性和活性。

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

• 仅仅适用于permissioned systems (联盟链/私有链)。

• 通信复杂度过高，可拓展性比较低，一般的系统在达到100左右的节点个数时，性能下降非常快。

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

</article