区块链笔记——PBFT

PBFT是实用拜占庭容错的简称，是解决拜占庭将军问题的一种方案。比起最开始的BFT算法，PBFT额外要求网络封闭，即节点数目确定并提前互通，但将复杂度从指数级降低到多项式级，使得BFT系列算法真正具有可行性。

与POW、POS等大家耳熟能详的共识不同，BFT系列的共识不需要“Proof”，亦即不需要节点投入算力或其他资源来确权，因此不需要代币激励便可完成共识。缺点是原始的BFT效率太低，只能存在于理论而无法应用。而改进的PBFT虽然效率大大提高，却对节点数量和状态提出了要求，导致合格的记帐节点太少，并且也只能维持在少数，过多的节点会拖慢网络速度。因此PBFT更多是用在联盟链和私链上。公链也有应用，例如NEO，便是采用了PBFT算法。

拜占庭将军问题的实质是在恶劣的通讯环境中，如何使各参与方达成一致意见。POW和POS等共识要求参与方投入成本，争夺唯一的发言权。在某一段时间内只有唯一的发言人，自然只会有一个意见，从而达成共识。PBFT采取不同的思路，要求各参与方相互发送及验证彼此的信息，最终采用多数原则达成共识。

PBFT能够以一种低成本的方式实现节点间共识，其理念其实相当贴近我们的生活习惯。例如在老师布置作业后，同学们总要互相问问确认一下，才放心地把今天的作业记到本子上。当然实现上还有很多细节，保证各节点的平等关系。在节点数目不多的时候，节点之间实现相互通信的成本并不高，节点之间可以快速发送确认。但节点数目增长却会带来整体性能的下降。PBFT可以容忍的坏节点数量不多于总数的三分之一，如果节点损坏率比较固定，提高总节点数量虽然能使系统获得更好的冗余，却会大大增加通讯量，造成效率下降。加上PBFT没有激励机制，其适合联盟链和私链场景。作为公链不可避免地节点数量太少，分布过分集中，例如NEO只有七个节点。

PBFT要求坏节点数量f<=(n-1)/3，这里n是总节点数。只要f满足这个条件，共识总是可以达成。为什么f要满足这个条件？简单来说，假设网络中存在恶意节点联盟，其控制了数量为f的节点，这些节点可以故意发布错误的信息。此时网络中正常节点数量为n-f个。将这n-f个节点分为两部分，各自包含一部分节点。对于任一部分正常节点来说，只要恶意节点数f大于自身节点数，同时大于剩余的正常节点数，这部分正常节点便会与恶意节点联盟达成共识。此时只要恶意节点联盟先后向两部分正常节点发送不同的共识信息，便可造成网络分叉。因此要保证网络运行，对于每一部分正常节点来说，网络中恶意节点数量不能同时大于自身节点数和网络剩余正常节点数。代入计算便得到f<=(n-1)/3。