硬核丨如何改进 BFT 共识算法?

通信复杂度问题

PBFT是基于三阶段投票即可达成共识的协议。prepare和commit阶段中，都需要每个节点广播自己的prepare或commit消息，因此通信复杂度是。

view change过程中，需要所有的副本节点发现主节点time out，每个副本节点会广播view change消息，所有副本节点对view change达成共识后，新的主节点会把这个消息广播出去宣布view change。由于view change消息是P2P广播，且每个view change消息中都包含达到prepared状态的请求，因此view change的验证复杂度是。

高达的复杂度无疑给PBFT的共识效率带来了严重的影响，极大地制约了PBFT的可扩展性。

BFT协议的优化

那么如何把的通信复杂度降到，提高共识效率，是BFT共识协议在区块链场景中面临的挑战。针对BFT共识效率的优化方法，共有以下几类：

1. 聚合签名

E.Kokoris-Kogias等在其论文中提出了在共识机制中使用聚合签名的方法。论文中提到的ByzCoin[4]以数字签名方式替代原有PBFT使用的MAC将通信延迟从降低至，使用聚合签名方式将通信复杂度进一步降低至。但ByzCoin在主节点作恶或33%容错等方面仍有局限。

之后一些公链项目基于这种思想，采用EC-Schnorr多签算法提高PBFT过程中prepare和commit阶段的消息传递效率。

2. 通信机制优化

PBFT使用多对多(all-to-all)的消息模式，因此需要的通信复杂度。

SBFT(Scale optimized PBFT)[5]提出了一个使用收集器(collector)的线性通信模式。这种模式下不再将消息发给每一个副本节点，而是发给收集器，然后再由收集器广播给所有副本节点，同时通过使用门限签名(threshold signatures)可以将消息长度从线性降低到常数，从而总的开销降低到。

Tendermint[6]使用gossip通信机制，乐观情况下可以将通信复杂度降低到。

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流程，因此通信复杂度也就降为。

HotStuff参考Tendermint，也将视图切换流程和正常流程进行合并，即不再有单独的视图切换流程。通过引入二阶段投票锁定区块，并采用leader节点集合BLS聚合签名的方式，将视图切换的通信复杂度降低到了。

4. 链式BFT

传统BFT需要对每个区块进行两轮共识，的通信复杂度可以让区块达到prepareQC，但是必须要的通信复杂度才能让区块达到commitQC。

Hotstuff将传统BFT的两轮的同步BFT改为三轮的链式BFT，没有明确的prepare，commit共识阶段，每个区块只需要进行一轮QC，后一个区块的prepare阶段为前一个区块的pre-commit阶段，后一个区块的pre-commit阶段为前一个区块的commit阶段。每次出块的时候都只需要的通信复杂度，通过两轮的通信复杂度，达到了之前的效果。

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.

作者：加密谷Live；来自链得得内容开放平台“得得号”，本文仅代表作者观点，不代表链得得官方立场凡“得得号”文章，原创性和内容的真实性由投稿人保证，如果稿件因抄袭、作假等行为导致的法律后果，由投稿人本人负责得得号平台发布文章，如有侵权、违规及其他不当言论内容，请广大读者监督，一经证实，平台会立即下线。如遇文章内容问题，请发送至邮箱：linggeqi@chaindd.com