PBFT共识算法的个人见解

前置知识

CFT与BFT的区别

• CFT&＃xff1a;节点出现故障( crash 或 fail-stop&＃xff09;&＃xff0c;即不响应但不会伪造信息的情况称为“非拜占庭错误”( non-byzantine fault)或“故障错误”( Crash
  Fault)&＃xff0c;处理非拜占庭错误的算法有&＃xff1a;paxos、raft和其变种&＃xff1b;
• BFT&＃xff1a;节点伪造信息恶意响应的情况称为“拜占庭错误”( Byzantine Fault)&＃xff0c;对应节点为拜占庭节点。处理拜占庭错误算法有&＃xff1a;pbft、hotstuff算法&＃xff1b;

同步、异步、部分同步概念

• 异步(asynchrony)&＃xff1a;系统中各个节点可能存在较大的时钟误差、消息传递时间是任意长的&＃xff0c;各节点对 消息的处理时间也可能是任意长的。
• 同步(synchrony)&＃xff1a;系统中各个节点的时钟误差存在上限、消息传递在一定时间内完成&＃xff0c;各节点完成处 理消息的时间是一定的。
• 部分同步(partial synchrony)&＃xff1a;在一个全局稳定时间&＃xff08;GST&＃xff09;之前&＃xff0c;系统可能处于异步状态&＃xff0c;GST之后&＃xff0c;会有一段同步的状态。

与公有链共识算法的区别

公有区块链不可能同时共识区块1和区块2&＃xff0c;但在pbft中&＃xff0c;交易1和交易2的共识是并行的。

• 在公有区块链中&＃xff0c;每一个区块串行进行共识&＃xff0c;共识的对象是区块&＃xff0c;区块包含一段时间收集的交易

• 在pbft中&＃xff0c;共识的对象是每一个交易(可以说在pbft中没有区块这个概念)&＃xff0c;交易共识的过程是并行&＃xff08;限定在高低水位,后续解释&＃xff09;

关于N>&＃61;3f&＃43;1

假设总共有N个节点&＃xff0c;其中有F个拜占庭节点&＃xff0c;拜占庭节点是可以不发送消息的&＃xff0c;所以为了保证活性&＃xff0c;主节点收到N-F个节点发送来的消息就要做出判断&＃xff0c;考虑极端情况&＃xff1a;N-F个消息中恰好有F个是拜占庭节点发来的&＃xff0c;因为网络存在延迟等原因&＃xff0c;诚实节点的消息可能会比拜占庭节点的消息更晚到达。此时N-F个消息中只有N-2F个是正确节点发送来的&＃xff0c;所以为了保证消息的正确性&＃xff0c;即需要诚实节点数量大于拜占庭节点F&＃xff0c;则有N-2F>F&＃xff0c;则至少需要保证N&＃61;3F&＃43;1。

具体流程

关于整个流程的具体流程讲解可以参考&＃xff1a;简书&＃xff0c;本文针对论文中的重点和难点进行提取。

重点提取

• pre-prepare阶段和prepare阶段确保所有正常节点对同一个视图中的请求排序达成一致&＃xff0c;prepare和commit两个阶段用来确保在不同的视图之间的请求也是严格排序的。

证明1&＃xff1a; 当节点收到了一个pre-prepare和对应的2f个prepare消息之后&＃xff0c;进入准备完毕阶段&＃xff0c;记作prepared(m, v, n, i).。假如有prepared(m,v,n,i)为真且prepared(m’,v,n,j)也为真&＃xff0c;那么可以由接受prepared的条件可以看出&＃xff0c;有f&＃43;1个好节点&＃xff08;包括他本身&＃xff09;发出了prepare消息接受m&＃xff0c;另有f&＃43;1个好节点发出了prepare接受m’,这样好节点为2f&＃43;2
但是N&＃61;3f&＃43;1,好节点只有N-f&＃61;2f&＃43;1个&＃xff0c;有矛盾。

证明2&＃xff1a;**某个好节点i达到committed-local说明其至少接收了2f&＃43;1个节点的commit消息&＃xff0c;所以至少有f&＃43;1个好节点的commit消息。好节点发送commit需要保证是已经进入prepared状态才行。这样就至少有f&＃43;1个好节点进入了prepared状态。如果发生视图转换的时候&＃xff0c;新的主节点需要收到2f个来自其他不同节点的view-change消息&＃xff08;加上自己就是2f&＃43;1个消息&＃xff09;。网络中总有3f&＃43;1个节点&＃xff0c;所以f&＃43;1个好节点肯定至少有一个会把已经prepared的消息发送到下一个视图中继续达成共识。

• 视图轮换

• pbft为什么需要三个阶段

如果一个节点达到了prepared状态&＃xff0c;就认为全网共识了是有问题的&＃xff0c;因为你收到凭证不代表其他人也受到足够的确认也生成凭证。想象一下&＃xff0c;如果就你生成凭证的情况下&＃xff0c;你认为全网已经共识了&＃xff0c;甚至返回用户结果。这时发生viewchange&＃xff0c;所有的交易都要被重放&＃xff0c;新的View从2f&＃43;1个回复中重新生成pre-prepare&＃xff0c;但是如果2f&＃43;1个回复中不包含你的消息&＃xff0c;那么你认为全网已经共识的交易就会凭空消失&＃xff0c;而此时你甚至已经返回用户结果了&＃xff0c;这是很有问题的。所以需要加多一个commit阶段&＃xff0c;commit阶段是让你知道别人也拿到这样的凭证的&＃xff08;因为一个节点达到了commited-local证明有f&＃43;1个好节点已经prepared&＃xff09;&＃xff0c;这样即使发生viewchange&＃xff0c;因为Quorum的性质&＃xff0c;保证你这个已经prepared凭证的消息&＃xff0c;一定会出现再重放名单中。
这也暗示了&＃xff0c;Viewchange会发生请求丢失的情况&＃xff0c;因为收集的2f&＃43;1个回复中只能保证那个commit阶段完成的prepare凭证消息能够重放。那些没完成commit阶段的prepare凭证消息可能会丢失&＃xff0c;没拿到prepare凭证的消息绝对会被丢失。这时就是可用性的问题了&＃xff0c;用户长时间没收到结果会重新发消息&＃xff08;因为消息丢失了&＃xff0c;只能这样&＃xff09;。同时&＃xff0c;因为丢失问题&＃xff0c;我们意识到中间有些序号是没有相应的消息的&＃xff0c;此时新主会填充为null消息。

优缺点总结

优势

• 首个实用的BFT容错算法&＃xff0c;使得复杂度从指数级降到多项式级 O(n2)&＃xff1b;
• 响应性&＃xff08;Responsiveness&＃xff09;&＃xff1a;在网络状况OK&＃xff0c;主节点不犯错&＃xff0c;拜占庭节点数量不超过f个时&＃xff0c; 在下一个视图一定是可以达成共识的&＃xff1b;

不足

• 通信复杂度 O(n2) &＃xff0c;可扩展性低&＃xff1b;
• 视图转换的复杂度 O(n3)&＃xff0c;要是连续视图转换复杂度 O(f* n3)&＃xff0c;视图转换复杂&＃xff0c;很“重”&＃xff1b;
• 视图转换期间只能接收viewchange、newview消息不能对外提供服务&＃xff1b;
• Safety和Liveness耦合&＃xff0c;都需要通过视图转换来保障&＃xff1b;
• 去重机制没有提&＃xff1b;

参考资料&＃xff1a;

https://www.jianshu.com/p/0bef4fb1662b
https://blog.csdn.net/jason_cuijiahui/article/details/79613633
https://blog.csdn.net/u011537073/article/details/53519074
源码&＃xff1a;https://github.com/Liukemeng/Fabric0.6-PBFT-Learning
原文&＃xff1a;https://pmg.csail.mit.edu/papers/osdi99.pdf