Alaya共识方案详解（二）：BFT协议的优化

通信复杂度问题
PBFT是基于三阶段投票即可达成共识的协议。prepare和commit阶段中，都需要每个节点广播自己的prepare或commit消息，因此通信复杂度是O(n²）。
view change过程中，需要所有的副本节点发现主节点time out，每个副本节点会广播view change消息，所有副本节点对view change达成共识后，新的主节点会把这个消息广播出去宣布view change。由于view change消息是P2P广播，且每个view change消息中都包含达到prepared状态的请求，因此view change的验证复杂度是O(n³）。
高达O(n³）的复杂度无疑给PBFT的共识效率带来了严重的影响，极大地制约了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%容错等方面仍有局限。
之后一些公链项目基于这种思想，采用EC-Schnorr多签算法提高PBFT过程中prepare和commit阶段的消息传递效率。
2. 通信机制优化
PBFT使用多对多(all-to-all)的消息模式，因此需要O(n）的通信复杂度。
SBFT(Scale optimized PBFT)[5]提出了一个使用收集器(collector)的线性通信模式。这种模式下不再将消息发给每一个副本节点，而是发给收集器，然后再由收集器广播给所有副本节点，同时通过使用门限签名(threshold signatures)可以将消息长度从线性降低到常数，从而总的开销降低到O(n）。
Tendermint[6]使用gossip通信机制，乐观情况下可以将通信复杂度降低到O(n log n）。
3. view-change流程优化
所有的BFT协议都通过view-change来更换主节点。PBFT，SBFT等协议具有独立的view-change流程，当主节点出问题后才触发。而在Tendermint、HostStuff[7]等协议中没有显示的view-change流程，view-change流程合入正常流程中，因此提高了view-change的效率，将view-change的通信复杂度降低。
Tendermint将roundchange(和viewchange类似)合入正常流程中，因此roundchange和正常的区块消息commit流程一样，不像PBFT一样有单独的viewchange流程，因此通信复杂度也就降为O(n²）。
HotStuff参考Tendermint，也将视图切换流程和正常流程进行合并，即不再有单独的视图切换流程。通过引入二阶段投票锁定区块，并采用leader节点集合BLS聚合签名的方式，将视图切换的通信复杂度降低到了O(n）。
4. 链式BFT
传统BFT需要对每个区块进行两轮共识，O(n）的通信复杂度可以让区块达到prepareQC，但是必须要O(n²）的通信复杂度才能让区块达到commitQC。
Hotstuff将传统BFT的两轮的同步BFT改为三轮的链式BFT，没有明确的prepare，commit共识阶段，每个区块只需要进行一轮QC，后一个区块的prepare阶段为前一个区块的pre-commit阶段，后一个区块的pre-commit阶段为前一个区块的commit阶段。每次出块的时候都只需要O(n）的通信复杂度，通过两轮的O(n）通信复杂度，达到了之前O(n²）的效果。
5. 流水线（Pipelining）和并行处理（Concurrency）
PBFT、Tendermint等协议具有即时确定(Instant Finality)的特性，几乎不可能出现分叉。在PBFT中，每个区块被确认后才能出下一个区块，Tendermint还提出区块锁定的概念，进一步确保了区块的即时确定性，即在某个round阶段，节点对区块消息投了pre-commit票，则在下一个round中，该节点也只能给该区块消息投pre-commit票，除非收到新proposer的针对某个区块消息的解锁证明。
这类BFT共识协议本质上是一个同步系统，将区块的生产和确认紧密耦合，一个区块确认后才能生产下一个区块，需要在块与块间等待最大的可能网络延迟，共识效率受到很大的限制。
HotStuff的Pipelining方法将区块的生产和确认分离，每个区块的最终确认需要后两个区块达到QC，也就意味着上一个区块没有完全确认（需要满足Three-Chain）的情况下可以生产下一个区块。这种方式实际上还是一个半同步系统，每个区块的产生还是需要等上一个区块达到QC。
EOS[8]的BFT-DPoS共识协议可认为是一种完全并行的Pipelining方案：每个区块生产后立即全网广播，区块生产者一边等待0.5秒生产下一个区块，一边接收其他见证人对于上一个区块的确认结果，使用BFT协议达成共识，新区块的生产和旧区块确认的接收同时进行，这极大地优化了出块效率。
（未完待续）
参考
[4] E. Kokoris-Kogias, P. Jovanovic, N. Gailly, I. Khoffi, L. Gasser, and B. Ford, “Enhancing Bitcoin Security and Performance with Strong Consistency via Collective Signing,” 2016.
[5] Guy Golan Gueta, Ittai Abraham, Shelly Grossman, Dahlia Malkhi, Benny Pinkas, Michael K. Reiter, Dragos-Adrian Seredinschi, Orr Tamir, Alin Tomescu，“a Scalable and Decentralized Trust Infrastructure”，2018.
[6] C. Unchained, “Tendermint Explained — Bringing BFT-based PoS to the Public Blockchain Domain.” [Online]. Available: https://blog.cosmos.network/tendermint-explained-bringing-bft-based-pos-to-the-public-blockchain-domain-f22e274a0fdb.
[7] M. Yin, D. Malkhi, M. K. Reiterand, G. G. Gueta, and I. Abraham, “HotStuff: BFT consensus in the lens of blockchain,” 2019.
[8] “EOS.IO Technical White Paper v2.” [Online]. Available: https://github.com/EOSIO/Documentation/blob/master/TechnicalWhitePaper.md.