硬核丨如何改进 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.