什么是 pBFT算法 - 区块链前沿 - BitMere

什么是 pBFT？
Practical Byzantine Fault Tolerance ，实用拜占庭容错。
什么是 BFT？
Byzantine Fault Tolerance ，拜占庭将军问题。
拜占庭将军的问题是什么？
简单地说，是一种少数服从多数的问题。拜占庭罗马帝国的每块封地都驻扎一支由将军统领的军队，将军与将军之间只能靠信差传递消息。在战争时期，拜占庭军队只有占据人数优势情况下，才能夺取目标的胜利。但在军队内有可能存有叛徒，当敌军与之联合起来大于忠诚将军数量时，进攻就会失败。
pBFT 算法的提出主要是为了解决拜占庭将军问题。
要解决这个问题的前提是通信必须是可靠的，如果通信不可靠则问题无解。而拜占庭将军问题中通过通信不可靠而试图达成一致的结果几乎不可能或者非常困难。所以要在通信可靠的前提下来解决此问题。也就是在系统上有一些恶意组件不断发送错误信息的情况下让系统依旧正常运行的能力。
pBFT 原理
在系统中有一个节点会被当做主节点，而其他节点都是子节点。系统内的所有节点都会相互通信，最终目标是大家能以少数服从多数的原则达成数据的共识。
达成共识的过程
第一步，客户端发一个请求给主节点去执行某个操作；
第二步，主节点通信给各个子节点；
第三步，所有节点通过算法并把结果返回给客户端；
第四步，当客户端「收到结果」后，过程结束；
第四步中收到结果时的最大容错节点数
假设 n 是总节点数，f 为有问题的节点，问题包括两种，一种是故障节点 f，一种是作恶节点 f。故障节点收到通信后不会返回结果，作恶节点收到通信后会返回错误的结果。在统计返回节点数时，有问题的节点 f 会被排除在外，所以只要正确通信数大于作恶节点数 f 即可保证本次通信正常，即 f + 1 个正确节点，也就是说总节点数n 包括 f + 1 个正确节点，f 个作恶节点和 f 个故障节点，即 3f + 1 = n，因此pBFT算法支持的最大容错节点数是 f = （n-1）/3，也就是超过 1/3 的节点数即可。

第三步中的pBFT算法
其中
C代表客户端，0，1，2，3 代表节点的编号，
打叉的3代表故障节点或者是问题节点，这里表现为故障节点。
0 是主节点。
算法的核心三个阶段分别是
pre-prepare预准备，由于主节点不会发布两条内容不同的通信，则如果收到节点编号相同而内容不同的通信，子节点会选择拒绝请求。
prepare 准备，由于同时有n个节点接受请求进行通信，所以在一定时间范围内，如果收到超过 2f 个不同节点的 prepare 消息，就代表 prepare 阶段已经完成。
commit提交，和prepare同理，当收到 2f+1 个 commit 消息后（包括自己），代表大多数节点已经进入 commit 阶段，这一阶段已经达成共识，于是节点就会执行请求，写入数据。
有关其他技术
checkpoint 、stable checkpoint和高低水位
checkpoint，是当前节点处理的最新请求序号。比如一个节点正在共识的一个请求编号是1，那么对于这个节点，它的 checkpoint 就是1。
stable checkpoint，是已经共识完成的最大请求序号。也就是 f + 1个节点请求编号是10 ，那么stable checkpoint就是10。
stable checkpoint为的是减少内存占用。当稳定是stable checkpoint是10 ，那么代表 10 号之前的记录已经共识过的了，可以删掉了。
stable checkpoint 可以设置一个范围，即水位，他的最小值叫下水位，最大值就高水位，他们的差 L 可以自定义。为了减少各个节点之间最大请求序号的差。假设水位是 50 ~ 100，当 a 节点到达100后，会等待 b 节点到达接近 100 时，自动更新水位范围，比如变成 100 ~ 150。这样节点就可以基本同步重新进行操作了。
更换主节点
当主节点出现故障，就会触发 ViewChange + 1 事件viewchange 会有三个阶段，分别是
view-change ，从节点认为主节点有问题时，会向其它节点发送 view-change 消息，当前存活的节点编号最小的节点将成为新的主节点。
view-change-ack ，新的主节点收到 2f 个 view-change 消息，则证明 view-change有效，并广播new-view 消息。
new-view ，新主节点会继续执行上个视图未处理完的请求，其它节点验证 new-view 消息通过后，就会处理执行pbft 过程并进入ViewChange + 1。
pBFT 的优点
高效，由于各个节点达成共识是在同一时刻决定的首先，所以pBFT 无需等待确认。
节能，因为 pBFT 是无需挖矿的，所以pBFT 不用耗能。
pBFT 的缺点
中心化，由于要保证各个节点间的频繁的通信，所以节点数不能太多。
门槛高，由于pBFT 不能防止女巫攻击，也就无法防御一个恶意用户用多个账户来进行共识的造假行为，所以需要审核加入节点。
所以 pBFT 比较适合需审批的联盟链，不太适合做无条件加入的公链。