本文共 4090 字，大约阅读时间需要 13 分钟。

PlatON的并行拜占庭容错共识协议(CBFT)

分布式网络模型

分布式系统的网络模型主要分为三类：

同步网络模型：节点发出的消息在确定时间内会到达目标节点。

异步网络模型：节点发出的消息不确定是否会到达目标节点。

部分同步网络模型：节点发出的消息可能会有延迟，但最终会到达目标节点。

根据FLP不可能原理，在异步网络模型下，共识算法无法同时满足安全性和活性。因此，BFT类共识协议通常基于部分同步网络模型。

BFT共识协议

BFT(Bayantine Fault Tolerance)协议是一种能够在存在恶意节点的情况下确保分布式系统的安全性和活性的共识算法。Lamport的经典论文指出，节点总数大于3f时，恶意节点最大为f，诚实节点可以达成一致的正确结果。

PBFT共识协议

PBFT(Practical Byzantine Fault Tolerance)是现实世界中首批能够同时处理第一类和第二类错误的BFT协议。它基于部分同步模型，将算法复杂度从节点数的指数级降低到节点数的平方级，使得BFT共识协议在实际系统应用中变得可行。

PBFT共识协议包括以下三个阶段：

Pre-prepare：主节点向副本节点广播预准备消息。

Prepare：副本节点向其他节点报告已知的消息，收集足够多的prepare消息后进入prepared状态。

Commit：收集足够多的commit消息后进入committed状态，完成区块确认。

视图切换是PBFT的关键设计，当主节点失效或副本节点认为主节点有问题时，会触发视图切换。视图切换请求需要经过多数节点确认后才能生效。

通信复杂度问题

PBFT的通信复杂度较高：

• Prepare和Commit阶段需要O(n²)的通信复杂度。
• 视图切换阶段需要O(n³)的通信复杂度。

高通信复杂度严重制约了PBFT的可扩展性。

BFT协议优化

为了降低BFT共识协议的通信复杂度，研究者提出了多种优化方法：

聚合签名：通过聚合签名减少消息长度，降低通信复杂度。

通信机制优化：使用收集器和门限签名，减少消息传递开销。

视图切换流程优化：将视图切换合并到正常流程中，降低通信复杂度。

Tendermint和HotStuff等协议在此基础上进一步优化，将视图切换流程与正常共识流程合并，通信复杂度降低至O(n²)。

链式BFT

HotStuff提出了链式BFT，将传统BFT的两轮共识改为三轮链式共识。每个区块只需进行一轮QC，后一个区块的pre-commit阶段为前一个区块的commit阶段。这种方式提高了出块效率。

EOS的BFT-DPOS共识协议采用并行确认机制，允许多个区块同时进行共识，进一步提高出块速度。

CBFT共识协议

为了进一步提高共识效率，PlatON提出了CBFT(Concurrent Byzantine Fault Tolerance)共识协议。CBFT基于部分同步网状通信模型，在同一视图窗口内可以连续提出多个区块，下一个区块的产生不需要等待上一个区块确认。

CBFT概述

CBFT共识协议的核心改进包括：

多区块提议：在一个视图窗口内可以连续提议多个区块。

并行处理：验证人可以在接收上一个区块投票的同时，进行下一个区块的交易。

自适配视图切换机制：在一个视图窗口内接收到足够多的prepare票后，自动切换视图，无需单独的视图切换流程。

CBFT相关术语

• 提议人(Proposer)：负责出块的节点。
• 时间窗口(T)：提议人只能在自己的时间窗口内出块。
• 节点总数(N)：共识节点总数。
• 拜占庭节点最大数量(f)：节点总数大于3f时，恶意节点最大为f。
• 足够多赞成票：至少收到N-f张赞成票。
• 验证人(Validator)：共识节点中非提议人节点。
• 视图(View)：当前提议人的时间窗口可以产生区块的时间范围。
• 区块重组：允许部分区块被重组，前提是满足一定条件。

BLS签名

BLS(Boneh-Lynn-Shacham)聚合签名是一种高效的聚合签名方案，广泛应用于区块链项目。BLS签名可以将多个签名简化为一个聚合签名，显著降低通信复杂度。

CBFT协议流程

CBFT共识协议包括以下流程：

正常流程：提议人在进入新的视图后，连续产生多个区块并广播prepare消息。

prepare投票：验证人对提议区块进行prepare投票，使用BLS签名聚合成prepareQC。

视图切换流程：在时间窗口超时时，节点发送viewchange消息，新的提议人收集足够多的viewchange票后，开始新的共识流程。

区块确认

CBFT采用pipelining方式进行区块确认，只需要两种消息类型：prepare消息和viewchange消息。每个消息的签名均采用聚合签名方式验证。

区块重组

区块重组规则如下：

• Pre-Commit状态的区块：不能被重组。
• Prepare状态的区块：可以被重组。

验证人替换机制

CBFT共识协议每250个区块（一个Epoch）更新验证人集合。新验证人通过VRF随机选出，确保网络连接或区块不同步等原因无法参与共识的节点不会被选上。

容错恢复机制

CBFT提供容错恢复机制，通过持久化内存和本地数据库记录共识状态和消息，系统崩溃或掉电重启后可以快速恢复共识状态。

区块同步机制

CBFT共识协议基于PlatON-P2P的区块同步机制，新加入节点通过快速同步或全同步更新至主网高度。共识节点通过心跳机制保持块高一致，区块落后时主动减少通信量。

CBFT分析

基本规则定义

K-Chain规则：区块链满足B0<-C0<-B1<-C1<-B2<-C2，B0达到Commit状态。

Lock-Block规则：区块n收到区块n之后的2次prepareQC后，区块n定义为Lock-Block。

Unlock-Block规则：当Lock-Block(a)=n，区块n+1达到2次prepareQC后，Lock-Block(a)更新为n+1。

Previous-Block规则：区块B的Previous-Block为B’，满足B<-prepareQC<-B’。

Commit规则：区块n收到区块n之后的3次prepareQC后，区块n被Commit。

安全性证明

同一个视图中不存在两个相同高度区块都能收到足够多投票。

对于3-Chain来说，B0<-C0<-B1<-C1<-B2<-C2，ViewNumber(B2) >= ViewNumber(B0)。

Lock-Block高度永远递增。

对于同一个ViewNumber，数块B和B’的Hash相同。

活性证明

时间窗口不会永远小于prepareQC的两倍。

ViewNumber可以达成一致，并且递增。

Lock-Block高度永远递增。

通信复杂度分析

• PBFT：O(n²)的通信复杂度。
• Tendermint：O(n²)的通信复杂度。
• Hotstuff：O(n)的通信复杂度。
• CBFT：O(n²)的通信复杂度。

回顾与总结

本文讨论了BFT类共识协议的优化方法，提出了CBFT共识协议。CBFT在保证安全性和活性的前提下，大幅降低了通信复杂度，提高了区块出块确认速度，满足区块链高效共识需求。

参考文献

[1] Fischer, M. J., Lynch, N. A., & Paterson, M. S. (1985). Impossibility of distributed consensus with one faulty process. J. ACM. [2] Lamport, L., Shostak, R., & Pease, M. (1982). The Byzantine Generals Problem. ACM Transactions on Programming Languages and Systems. [3] Castro, M., & Liskov, B. (1999). Practical byzantine fault tolerance. In OSDI. [4] Kokoris-Kogias, E., Jovanovic, P., Gailly, N., Khoffi, I., Gasser, L., & Ford, B. (2016). Enhancing Bitcoin Security and Performance with Strong Consistency via Collective Signing. [5] TEAM T Z. Zilliqa TechnicalWhitepaper. Zilliqa. [6] Gueta, G. G., Abraham, I., Grossman, S., Malkhi, D., Pinkas, B., Reiter, M. K., ... & Tomescu, A. (2018). Scalable and Decentralized Trust Infrastructure. [7] Unchained. (n.d.). Tendermint Explained — Bringing BFT-based PoS to the Public Blockchain Domain. [8] Yin, M., Malkhi, D., Reiter, M. K., Gueta, G. G., & Abraham, I. (2019). HotStuff: BFT consensus in the lens of blockchain. [9] EOS.IO Technical White Paper v2. EOS.IO. [10] Boneh, D., Drijvers, M., & Neven, G. (2018). BLS Multi-Signatures With Public-Key Aggregation.