拜占庭容错共识（PBFT）

一、拜占庭容错共识

1. 什么是PBFT

共识机制堪称区块链的核心。我们知道，EOS、Hyperledger（之前0.x是，现在2.x已经不是。现在是Raft共识： Raft共识可以处理集群中部分节点的崩溃故障，但不能处理恶意节点行为，因此通常用于节点身份已知的环境中，例如许可制区块链 Hyperledger Fabric 就使用了基于Raft共识的排序服务。）等著名的项目，都采用了BFT（拜占庭容错）共识机制，那么，BFT到底是什么?

什么是 pBFT？
Practical Byzantine Fault Tolerance ，实用拜占庭容错。

什么是 BFT？
Byzantine Fault Tolerance ，拜占庭容错。

区块链中最重要的便是共识算法，比特币使用的是POS（Proof of Work，工作量证明），以太币使用的是POS（Proof of Stake，股权证明）使得算理便的不怎么重要了，而今POS的变体DPOS（Delegated Proof of Stake，股份授权证明）进一步削减算力的浪费，同时也加强了区块链的安全性。
不过，对于不需要货币体系的许可链或者私有链而言，绝对信任的节点，以及高效的需求上述共识算法并不能够提供，因此对于这样的区块链，传统的一致性算法成为首选，RAFT。

拜占庭将军的问题是什么？

简单地说，是一种少数服从多数的问题。拜占庭罗马帝国的每块封地都驻扎一支由将军统领的军队，将军与将军之间只能靠信差传递消息。在战争时期，拜占庭军队只有占据人数优势情况下，才能夺取目标的胜利。但在军队内有可能存有叛徒，当敌军与之联合起来大于忠诚将军数量时，进攻就会失败。

pBFT 算法的提出主要是为了解决拜占庭将军问题。

pBFT 原理

POS、PBFT共识算法的介绍
参考URL: https://mathpretty.com/9602.html
pBFT 原理
参考URL: https://zhuanlan.zhihu.com/p/71075569

基于拜占庭将军问题，PBFT算法一致性的确保主要分为这三个阶段：预准备（pre-prepare）、准备(prepare)和确认(commit)。流程如下图所示：

我们首先解释一下上面各个符号表达的意思：

• C表示客户端；
• 0，1，2，3表示4个节点；
• 0在这里为主节点，1，2，3为从节点；（注意，这里其他节点也可以作为主节点，若0发生错误只能由服务器监测。如果服务器在一段时间内不能完成客户端的请求，则会触发视图更换协议，将其他节点换为主节点）
• 3为故障节点；

下面我们结合上图，详细说一下PBFT的步骤：

1. Request：请求端C发送请求到主节点，这里是0节点；
2. Pre-Prepare：节点0收到C的请求后进行广播，扩散至123；
3. Prepare：123节点收到后记录并再次广播，1->023，2->013，3因为宕机无法广播；（这一步是为了防止主节点给不同从节点发送不同的请求）
4. Commit：0123节点在Prepare阶段，若收到超过一定数量（2F，实际使用中，F为可以容忍的拜占庭节点个数）的相同请求，则进入Commit阶段，广播Commit请求；
5. Reply：0123节点在Commit阶段，若其中有一个收到超过一定数量（2F+1）的相同请求，则对C进行反馈；

根据上述流程，在 N ≥ 3F + 1 的情況下一致性是可能解決，N为总计算机数，F为有问题的计算机总数。

一个例子：
下面我们来举一个PBFT（实用拜占庭容错算法）的例子来进行说明。

我们假设N=4，F=1，即有四个节点，其中有一个节点是坏的，我们还使用上面的图，即节点3为故障节点。

1. 请求端C发送请求到0节点，假设这里请求内容为“1”；
2. 节点0收到C的请求后进行广播，将请求内容“1”扩散至节点123；
3. 节点1、2、3收到后内容“1”后，再次广播，节点1->023，节点2->013，节点3因为宕机无法 广播；
4. 节点0，1，2会在上一阶段分别收到三个请求内容“1”，均超过了2个，于是节点0、1、2会分别广播请求内容“1”；
5. 此时如果一个节点（0，1，2中任意一个）收到3即（2+1）条commit消息，即对C进行反馈。

一个问题说明 — 为什么至少需要N=3F+1个节点
我们在上面讲到，当网络中有F台有问题的计算机时，至少需要3F+1台计算机才能保证一致性问题的解决，我们在这里讨论一下原因。

我们可以考虑：由于有F个节点为故障或被攻击的节点，故我们只能从N-F个节点中进行判断。但是由于异步传输，故当收到N-F个消息后，并不能确定后面是否有新的消息。（有可能是目前收到的N-F个节点的消息中存在被攻击的节点发来的消息，而好的节点的消息由于异步传输还没有被收到。）

我们考虑最坏的情况，即剩下F个都是好的节点，收到的中有F个被攻击的节点，故我们需要使得收到的中好节点的数量N-2F大于被攻击节点的数量F，于是有N-2F>F，即N>3F，所以N的最小整数为N=3F+1。

2. 与最传统的PoW共识机制相比，PBFT优势和劣势

1、效率高

PBFT要求所有节点之间的两两通信，因此这种通信机制要求节点数量不能太多，通常是几十个，在这种模式下，节点达成一致的速度更快，延时更低。

2、吞吐量高

节点数量的控制，使PBFT网络不用像大型PoW网络那样，受限于处理能力最低的节点；因此带来全网吞吐量的大幅提升。

3、节能
无须使用工作量证明的耗电模式，因此更加节能环保。

所谓有得必有失，相对而言，PBFT又有以下劣势：

1、可扩展性及去中心化程度较弱

由于节点数量的限制，因此可扩展性较弱；同时节点需要选举、或者许可，不像PoW节点那样可以自由加入，去中心化程度较弱。

2、容错性较低

PoW网络的容错性是50%，也就是须防范51%攻击；而PBFT容错性只有三分之一，也就是34%的恶意节点即可发起攻击。

表 共识算法对比 来源：中国信息通信研究院，2018 年8 月

总结：
pBFT 的优点
高效，由于各个节点达成共识是在同一时刻决定的首先，所以pBFT 无需等待确认。
节能，因为pBFT 是无需挖矿的，所以pBFT 不用耗能。

pBFT 的缺点：
中心化，由于要保证各个节点间的频繁的通信，所以节点数不能太多。
门槛高，由于pBFT 不能防止女巫攻击，也就无法防御一个恶意用户用多个账户来进行共识的造假行为，所以需要审核加入节点。

所以pBFT 比较适合需审批的联盟链，不太适合做无条件加入的公链。

3. BFT共识开发库

区块链主流共识算法的15个开源实现
参考URL: https://zhuanlan.zhihu.com/p/99403520

Tendermint

BFT共识算法可以应对分布式系统中的拜占庭故障（Byzantine failures），也就是可以在集群中部分节点存在恶意行为时依然保证整个系统的正常工作。

Tendermint Core 是一个拜占庭容错的中间件，可以安全的将任何语言开发的状态机复制到集群中的其他机器上。Tendermint Core已经被用于Cosmos、币安链等多种公链环境中。

Tendermint Core的协议详情可以参考这里，开发教程访问这里：tendermint开发详解(http://xc.hubwiz.com/course/5bdec63ac02e6b6a59171df3?affid=csdn7878)。

开发语言：Go
下载地址：https://github.com/tendermint/tendermint

Tendermint Core是一种拜占庭容错（BFT）共识引擎，可以抵御双重攻击，并且能够容忍网络中一组高达1/3的拜占庭角色。Tendermint应用程序区块链接口（ABCI）平台是一个适用于区块链应用程序开发人员的工具包。该工具包与任何编程语言兼容，允许对仅运行业务逻辑的去中心化应用程序进行更高级别的开发，而无需在共识层上进行更低级别的修补。Ethermint等平台建立在Tendermint ABCI平台之上。

另一个建立在Tendermint ABCI之上的项目是Cosmos Network，它被设计为“区块链互联网”。Cosmos设想了一个可互操作的多链网络，它提供了在独立区块链（称为区域）之间无信任地交换加密资产的方法，通过称为Cosmos Hub的主集线器链。为了使区块链开发人员尽可能轻松，Cosmos还附带了一个名为Cosmos-SDK的工具包，使开发人员可以使用即插即用模块轻松创建自定义区块链。

BFT-SMaRt

BFT-SMaRt是一个拜占庭容错的状态机复制实现，采用Java开发，目前由里斯本大学的LsSIGE研究组负责维护。BFT-SMaRt要求JRE 1.8+。

BFT-SMaRt是最知名的Java版BFT实现，京东的区块链就是采用这个库解决共识问题。

开发语言：Java
下载地址：https://github.com/bft-smart/library

BABBLE

Babble是用于分布式应用的拜占庭共识平台，它可以让一组计算机表现的如同单一计算机。Babble它使用P2P网络和BFT共识算法来保证一组彼此互联的计算机可以同样的顺序处理同样的命令，也就是通常说的状态机复制。Babble可以让整个系统安全的应对部分节点的故障或恶意行为。

Babble主要采用Go语言开发，但是其设计目标是可以集成进任何语言开发的应用，如上图所示。

开发语言：Go
下载地址：https://github.com/mosaicnetworks/babble

Concord-BFT

concord-bft是vmware开源的一个通用的状态机复制库，可以应对集群中的恶意行为（拜占庭故障）。 concord-bft被设计用于分部署数据仓库复制的核心构建模块，特别适合作为许可制区块链系统的基础。

concord-bft的实现基于这片论文中的算法：SBFT: a Scalable Decentralized Trust Infrastructure for Blockchains。

开发语言：Python
下载地址：https://github.com/vmware/concord-bft

HBBFT

HBBFT是论文Honey Badger of BFT Protocols提出的蜜獾BFT共识算法的Rust实现。HBBFT要求Rust 1.36+以及cargo

蜜獾（Honey Badger）共识算法可以让分布式异步环境中的节点交易达成一致，该算法不需要主导节点，可以应对恶意节点的攻击，适合于去中心化数据库和区块链应用。

开发语言：Rust
下载地址：https://github.com/poanetwork/hbbft

libbft

libbft是一个轻量级的拜占庭容错库，用于neo区块链，采用C++开发，由neo研究院维护，计划移植到Python、go等多种语言。

开发语言：C++
下载地址：https://github.com/NeoResearch/libbft

二、参考

什么是 pBFT
参考URL: https://zhuanlan.zhihu.com/p/71075569
从0到1搞懂拜占庭容错共识机制
参考URL: https://www.jianshu.com/p/6420eb1661a0?from=groupmessage
区块链共识算法 PBFT（拜占庭容错）、PAXOS、RAFT简述
参考URL: https://www.cnblogs.com/yuluoxingkong/p/13542788.html
对PBFT算法的理解
参考URL: https://www.cnblogs.com/gexin/p/10242161.html
实用拜占庭容错系统（PBFT）共识算法
参考URL: https://blog.csdn.net/JonasErosonAtsea/article/details/109236413
[比较全面，推荐]参考URL: https://github.com/xipfs/IPFS-Internals/blob/master/ebook/13.0.md
区块链主流共识算法的15个开源实现
参考URL: https://zhuanlan.zhihu.com/p/99403520