通信复杂性问题

PBFT是一个可以在三阶段投票的基础上达成共识的协议。在准备和提交阶段，每个节点都需要广播其o (n)准备或提交消息，因此通信复杂度为O(n)。

在视图更改过程中，所有副本节点都需要发现主节点的超时，每个副本节点都会广播一条视图更改消息。在所有副本节点就视图更改达成一致后，新的主节点将广播此消息以宣布视图更改。视图改变的验证复杂度为o (n)，因为视图改变消息是P2P广播，并且每个视图改变消息包含到达准备状态的请求。

复杂度高达O (n)无疑严重影响了PBFT的O(n)共识效率，极大制约了PBFT的可扩展性。

BFT协议的优化

因此，如何降低O(n)到O (N)的通信复杂度，提高共识效率，是BFT共识协议在区块链场景下面临的挑战。BFT共识效率有以下几类优化方法：

1.聚合签名

E.Kokoris-Kogias等人提出了在共识机制中使用聚合签名的方法。文中提到的ByzCoin[4]用数字签名代替了PBFT使用的MAC，将通信时延从O (n)降低到O(n)，进一步用聚合签名将通信复杂度降低到O(log n)。但是，ByzCoin在主节点的邪恶行为或者33%的容错方面还是有局限性的。

然后，基于这一思想，一些公共链项目在PBFT的准备和提交阶段采用了EC-Schnorr多符号算法来提高消息传输效率。

2.通信机制优化

PBFT采用全对全消息模式，因此需要O(n)个通信复杂度。

SBFT(规模优化的PBFT)[5]提出了一种使用收集器的线性通信模式。在这种模式下，消息不会发送到每个副本节点，而是发送到收集器，然后由收集器广播到所有副本节点。同时，通过使用阈值签名，消息长度可以从线性减少到常数，从而总开销可以减少到O(n)。

嫩薄荷[6]采用八卦沟通机制，在乐观的情况下可以将沟通复杂度降低到O(n log n)。

3.视图变更流程优化

所有BFT协议都使用视图改变来替换主节点。PBFT、SBFT和其他协议都有独立的视图改变过程，当主节点出现问题时就会触发这些过程。将嫩薄荷、HostStuff[7]等协议中没有显示的视图变化过程集成到正常过程中，提高了视图变化的效率，降低了视图变化的通信复杂度。

Tendermint mint将roundchange(类似于viewchange)集成到正常流程中，因此roundchange与正常的block消息提交流程一样，不像PBFT那样有单独的viewchange流程，因此通信复杂性降低到o (n)。

参照嫩度薄荷，HotStuff也是把视图切换过程和正常过程结合起来，也就是没有单独的视图切换过程。通过引入两阶段投票锁块和采用领导节点集的BLS聚合签名，视图切换的通信复杂度降低到0(n)。

4.连锁BFT

传统的BFT每个街区都需要两轮共识。o (n)的通信复杂度可以使块到达预备质量控制，但是必须是O(n)才能使块到达准备质量控制。

Hotstuff把传统的BFT从两轮同步BFT变成了三轮连锁BFT。准备和提交没有明确的共识阶段，每个区块只需要一轮QC。后一个块的准备阶段是前一个块的预提交阶段，后一个块的预提交阶段是前一个块的提交阶段。每次生成一个块只需要o (n)个通信复杂度，通过两轮O(n)个通信复杂度达到之前的O(n)个效果。

5.流水线和并发

PBFT、嫩薄荷等协议具有即时终结性的特点，几乎不可能有分歧。在PBFT，只有在每个区块都得到确认后，才能发布下一个区块。嫩薄荷还提出了块锁的概念，进一步保证了块的即时确定性。也就是说，在某一轮阶段，节点为块消息投票预提交，并且在下一轮中，节点只能为块消息投票预提交，除非它从新的提议者接收到块消息的解锁证书。

这种BFT共识协议本质上是一个同步系统，它紧密地耦合了块的产生和确认。确认一个区块后，才能生产下一个区块。需要等待最大可能的块间网络延迟，共识效率大大受限。

HotStuff的流水线方法将块的产生和确认分开，每个块的最终确认需要后两个块达到QC，这意味着如果前一个块没有完全确认(需要三链)，就可以产生下一个块。其实这种方法还是半同步系统，每个块的生成还是需要等上一个块到达QC。

EOS[8]的BFT-DPoS共识协议可以看作是一个完全并行的流水线方案：每一个块在产生后立即在整个网络上广播，块生产者在等待0.5秒产生下一个块的同时，接收到其他见证人对前一个块的确认结果。利用BFT协议达成共识，新块的产生和旧块确认的接收同时进行，极大地优化了块输出效率。

(待续)

参考

[4] E. Kokoris-Kogias，P. Jovanovic，N. Gailly，I. Khoffi，L. Gasser和B. Ford，“通过集体签名增强比特币安全性和强一致性性能”，2016年。

[5]盖伊戈兰葛雷塔、伊塔亚伯拉罕、谢利格罗斯曼、达丽娅马尔基、本尼平卡斯、迈克尔k赖特、德拉戈斯-阿德里安塞丁斯基、奥尔塔米尔、阿林托梅斯库，《可扩展和分散的信托基础设施》，2018年。

[6] C .未被束缚，“嫩薄荷解释——将基于BFT的位置引入公共区块链领域。”[在线]。available : https://blog . cosmos . network/嫩薄荷-explained-bring-bft-based-pos-to-public-区块链-domain-f22e274a0fdb。

[7]尹，马尔基，赖特兰德，亚伯拉罕，“区块链视角下的BFT共识”，2019年。

[8]“EOS。IO技术白皮书v2。”[在线]。available : https://github.com/EOSIO/Documentation/blob/master/Technological WheSe . MD。