3.1 为什么设计CBFT
前面的内容中，我们分析了BFT共识协议的问题，以及几种主流的优化BFT共识协议，这些BFT共识协议在降低通信复杂度和出块效率方面都取得了不错的研究成果，但仍存在一些改进空间。
- PBFT 较之于之前的 BFT 算法虽更实用，但因受制于O(n^(3))的视图切换开销，在扩展性方面存在很大的问题。
- Tendermint将round change和正常流程合并，简化了视图切换逻辑，将视图切换的通信复杂度降低为$O(n^2)$，但需要等待一个比较大的网络时延来保证活跃性。同时 Tendermint 仍然是串行出块和确认，一个区块的投票需要等上一个区块 commit 完成才能开始。
- EOS的BFT-DPOS 共识协议中，区块生产者可以连续产生若干区块，同时区块采用并行确认，提高了出块速度。使用 BFT 协议确认出块，但仅适用于强同步的通信模型。
- HotStuff 创新地提出了基于leader节点的、三阶段提交的 BFT 共识协议，吸收了 Tendermint 的优点，将viewchange 和正常流程合并，并将 viewchange 的通信复杂度降至线性。同时通过简化消息类型，可以 pipeline 的方式确认区块。但引入了新的投票阶段也会增加通信复杂度，同时一个视图窗口只确认一个区块，这无疑需要耗费较多的通信复杂度在视图切换上。此外，基于Leader节点收集投票的星状拓扑结构，比较适合于 Libra 这种网络环境良好的联盟链，在弱网环境中比较容易受单点故障影响，造成较大的 leader 节点切换开销。
因此，我们提出了 CBFT 共识协议，在以上共识协议的基础上进行进一步的优化，可以极大地降低通信复杂度 ，并且提高出块效率。
3.2 CBFT概述
CBFT基于部分同步网状通信模型，提出了一个三阶段共识的并行拜占庭容错协议。网状的通信模型更适合公网的弱网环境，在PlatON上已经使用了该协议作为共识算法。
CBFT 的正常流程和 Hotstuff 类似，分为 prepare，pre-comit，commit 和 decide几个阶段。但 CBFT 还作了关键的改进：在一个视图窗口内可以连续提议多个区块，下一个区块的产生不用等上一个区块达到QC；而且各个节点可以在接收上一个区块投票的同时，并行执行下个区块的交易，以 pipeline 的方式对区块进行投票确认， 从而极大提高了出块速度。
CBFT 有自适配的视图切换机制：在一个视图窗口内，节点接收到足够多的区块以及赞成票（超过2/3的节点投票，也就是 QC）时，会自动进行窗口切换，切换到下一个窗口，无需进行 viewchange 投票。除此之外，节点才会启动 viewchange 流程，并且在 viewchange 阶段引入了和 Hotstuff 一样的二阶段锁定投票规则，同时使用 BLS 聚合签名，可以在$O(n^2)$的通信复杂度内完成视图窗口切换。
根据上面的讨论，CBFT 只在正常流程之外才会进行 viewchange，因此相比 HotStuff 会有更少的视图切换开销。
接下来先给出 CBFT 共识中涉及的相关概念及其含义说明，便于之后对 CBFT 进行详细介绍。
3.2.1 CBFT相关术语
- 提议人(Proposer)： CBFT共识中负责出块的节点
- T： 时间窗口，每个提议人只能在自己的时间窗口进行出块
- N： 共识节点总数
- f： 拜占庭节点最大数量
- 足够多赞成票： 表示为至少收到N-f张赞成票
- 验证人(Validator)： 共识节点中非提议人节点
- 视图(View)： 当前提议人的时间窗口可以产生区块的时间范围
- ViewNumber： 每个时间窗口的序号，随着时间窗口递增
- HighestQCBlock： 本地最高的N-f PrepareVote区块
- ProposalIndex： 提议人的索引号
- ValidatorIndex： 验证人的索引号
- PrepareBlock： 提议的区块消息，主要包含区块（Block)，提议人索引号
- PrepareVote： 验证人对提议区块的Prepare投票，每个验证人需要执行区块后才发送PrepareVote。主要包含ViewNumber, 区块hash, 区块高度，验证人索引号(ValidatorIndex)
- ViewChange： 当时间窗口超时，提议人的区块没有都收集到N-f PrepareVote，则会向下一个提议人发送ViewChange。ViewChange包含 提议人索引号（ValidatorIndex），最高确认区块(HighestQCBlock)
- 锁(Lock)： 对指定块高进行锁定
- Timeout： 超时（时间窗口到期可以看作提议人的超时时间）
- 法定： 最大被允许
- 同一个View： 两个View的ViewNumber相等，可以成为同一个View
3.2.2 BLS签名
目前业界采用的聚合签名方案主要是BLS聚合签名。BLS聚合签名是在BLS签名方案基础上的扩展方案。Boneh-Lynn-Shacham（BLS）签名方案是Dan Boneh，Ben Lynn, Hovav Shacham[10]于2001年提出的。BLS签名目前在许多区块链项目如Dfifinity、fifilecoin、 Libra中都得到了运用。 BLS聚合签名可以把多个签名简化为1个聚合签名，对于提高BFT共识协议中的通信效率至关重要。
值得注意的是，BLS聚合签名的方法是有漏洞的。一种称为rogue public key的攻击可以使得攻击者有机会在获得其他签名者的公钥和标准BLS签名信息之后，能够操纵聚合签名的输出结果。
对这个攻击的一种最直接的防御措施是，参与BLS聚合签名的人都需要先证明各自确实掌握了BLS私钥信息，并事先注册。这一过程可以通过使用一种简单高效的零知识证明技术(Schnorr非交互式零知识证明协议)完成。参与者在进行聚合签名之前，需要给出零知识证明，证明其持有公钥信息的同时，确实掌握了该公钥对应的私钥信息。
3.3 CBFT协议流程
3.3.1 正常流程
图3 CBFT正常流程 1. 提议人在成功进入到新的 View 后，会连续产生多个区块，将消息PrepareBlock广播给验证人。
- 逐个验证区块：验证人校验签名和时间窗口，执行区块，成功后产生PrepareVote<ViewNumber,BlockHash, BlockNumber>。当PrepareVote对应的父区块收集到N-f个PrepareVote时，使用BLS 将N-f 个PrepareVote的个体签名聚合成一个聚合签名，并将当前PrepareVote进行广播。我们将N-f个PrepareVote 简化为prepareQC(quorum certificate) 。
- 当节点在当前view内最后一个区块收到prepareQC，则会进入新的view开始下一轮投票。
为了更安全的投票，投票必须符合以下规则：
- 区块执行后才能进行投票
- 诚实的节点只能对当前View提议的区块进行投票
- 诚实的节点当View超时后不能再进行投票，也不接收当前View的投票
- 在同一个View内，相同高度的两个区块只能投其中一个
- 当对Block(n+1)进行投票时，Block(n)需达到prepareQC
3.3.2 ViewChange流程
图4 时间窗口出块完成时切换窗口 图5 时间窗口出块未完成但过期时切换窗口
图6 viewchange投票流程 假设每个时间窗口最多允许产生n个区块，viewchange 流程如下：
- 如果在时间窗口内，收到第n块的prepareQC，则更新本地view+1，进入新的正常流程，这种情况下如果是新提议人达成n的QC，则开始广播第一个区块，如图4所示，高度为BlockNumber(n)+1 ，并会携带n 区块的prepareQC。 2. 如果时间窗口过期，节点首先会拒绝对当前提议人的区块产生新的投票，同时没有收到第n块的prepareQC，则发送ViewChange<ViewNumber, HighestQCBlock>消息，如图5所示。 3. 下一个时间窗口的提议人收到 N-f 个ViewChange 消息（我们将N-f 个ViewChange 消息简称为 viewchangeQC )之后，使用BLS签名聚合成一个QC签名，然后更新本地ViewNumber+1，由于采用两轮投票锁定区块的规则，新提议人可以简单地从收到的 N-f 个viewchange 消息中选择 HighestQCBlock，将新的区块序号定为 HighestQCBlock+1，如图6所示，然后广播第一个区块给各验证人节点，并携带HighestQCBlock的QC签名和viewchange的QC签名。 4. 各验证人节点会根据收到的 HighestQCBlock+1 序号开始新一轮共识。
3.3.3 区块确认
3.3.3.1 Pipelining流程
在传统BFT(PBFT, Tendermint)中，每个区块通常都需要经历明确的Pre-Commit 和 Commit阶段才最终确认：
- Pre-Commit： 当节点收到N-f个Prepare投票时会广播Pre-Commit, Pre-Commit 可以看作对Prepare阶段的确认。
- Commit： 当收到N-f个Pre-Commit投票时，表明所有节点对指定消息达成一致，提交到本地磁盘。
根据上面的介绍，CBFT中也有类似的 Prepare 和 ViewChange 两个阶段，每个区块只有Prepare投票，没有明确的Pre-Commit 和 Commit阶段，那么如何达到区块的确认呢？CBFT可看作Pipeline版本的 BFT，每个prepareQC 都是对前面区块更高阶段的确认。
图7 CBFT确认流程 如图7所示prepareQC(2)作为Block(1)的Pre-Commit阶段，prepareQC(3)作为Block(1)的Commit阶段，Block(2)的Pre-Commit阶段。
因此在CBFT中，只有两种消息类型：prepare消息和view-change消息，每个消息的QC均采用聚合签名方式验证。
3.3.3.2 区块重组
假设每个view允许产生n个区块，当前view V_i 时间窗口超时，view切换到$V_{i+1}$，此时$V_i$产生的区块只有部分得到QC，部分区块会进行重组，重组规则如下：
- Pre-Commit状态的区块被锁定，不能被重组，即如果当前节点在高度h上有Pre-Commit状态的区块，当前节点不能在高度h产生新的区块，也不能在高度h对其他区块投票
- Prepare状态的区块可以被重组，即如果当前节点在高度h上有Prepare状态的区块，当前节点可以在高度h产生新的区块，或者在高度h对其他区块投票（只允许对更高viewnumber的区块投票）
3.4 验证人替换机制
CBFT共识中，每250个区块（称为一个 Epoch）就会更新验证人集合，更新规则如下：
- 新验证人可能由于网络连接或区块不同步等原因不能参与共识，因此我们每次替换不超过8个节点，如果候选验证人不足8个，替换的数量为候选验证人的总数。
- 使用VRF从候选验证人中随机选出新验证人。
3.5 容错恢复（WAL）机制
CBFT 共识提供了容错恢复机制，也就是 WAL 模块。该模块不属于严格意义上的预写日志系统，但是借鉴了相关思想，在验证人共识过程中将还未落链区块的共识状态和当前View的共识消息从内存分别持久化到本地数据库和本地文件。在系统 crash 或者机器掉电重启之后通过磁盘日志数据迅速恢复共识状态。
这里简要介绍一下主要的原理：
- 区块、viewChange 在各验证人间达成共识需要经历验证、投票等阶段，某个区块最终落链前与该区块相关的共识状态、消息都记录在内存中。节点重启也只是需要恢复这部分还未落链区块的内存数据，因此 checkpoint 恢复点也就是当前 blockchain 的 currentBlock
- 链式投票可得，每一区块的投票都是对前一区块的确认，达到第三级即达到达到区块的 Commit 阶段，因此 3-chain 区块的 prepareQC 状态在共识中至关重要，必须保证在重启后恢复，这部分数据存储至 db
- 共识消息只保留最近一轮 view 相关的，这部分数据存储至文件
3.6 区块同步机制
由于 CBFT 共识的异步并行性，导致最新的区块存储在内存中，并且区块高度有3种高度：最高逻辑区块高度、最高确认区块高度和写入磁盘区块高度，并且三种高度依次递减。因此 CBFT 中的区块同步机制也在已有的ETH-P2P的基础上作了适配，调整了区块高度的获取方式。 这里概要介绍区块同步机制如下：
- 新加入节点通过ETH-P2P 利用快速同步或全同步更新至主网高度
- 共识节点利用CBFT-P2P的心跳机制与其它节点保持块高一致
- 共识节点区块落后时，会主动减少通信量，全力处理区块同步
- 同步机制使用BLS签名来减少网络同步消息量