4 CBFT分析
4.1 基本规则定义
为方便对CBFT的安全性和活跃性进行分析 ，我们定义CBFT的几条基本规则。
4.1.1 K-Chain 规则
对于一条链，满足以下条件：
B(0)<-C(0)<-…<-B(k-1)<-C(k-1)
我们将其定义为K-Chain, 其中B为Block, C为B的prepareQC。我们可以看到当达到3-Chain时如： B0<-C0<-B1<-C1<-B2<-C2 , B0达到Commit状态。
4.1.2 Lock-Block规则
节点a中, 当区块n收到区块n之后的2次prepareQC，则区块n定义为Lock-Block(a)。可以观察到，当Lock-Block(a) = B0时，B0达到2-Chain, 如 B0<-C0<-B1<-C1 。
4.1.3 Unlock-Block规则
假设Lock-Block(a)为n，当n的子区块n+1达到2次prepareQC,则Lock-Block(a)为n+1。可以观察到，当Lock-Block(a) = B0时，B0达到2-Chain， 如B0<-C0<-B1<-C1-B2,当B0 Unlock-Block时，B0达到3-Chain，如 B0<-C0<-B1<-C1<-B2<-C2 。
4.1.4 Previous-Block规则
形如 Block(B)<-prepareQC(B)<-Block(B’)，我们将Block(B)定义为Block(B’)的Previous-Block， 则可表示为Previous-Block(B’) = Block(B)。
由Lock-Block与Previous-Block规则可知:
在节点a中，形如B<-C<-B’<-C’<-B’’ , Previous-Block(B’’) > Lock-Block(a)
4.1.5 Commit 规则
当区块n, 收到区块n之后的3次prepareQC，则区块n被Commit。可以观察到，当B0被Commit时，B0达到3-Chain，如B0<-C0<-B1<-C1<-B2<-C2。
4.2 安全性（safety）证明
1） 不存在同一个View中有两个相同高度区块都能收到足够多投票
证明： 假设N=3f+1为节点总数，f为拜占庭节点最大数量，那么当收到2f+1投票为足够多投票。因两个区块都收到至少2f+1,投票总量至少为 2(2f+1) = N+f+1, 可以看到至少有f+1对两个区块投了票，与f个拜占庭节点假设矛盾。
2） 对于3-Chain来说，B0<-C0<-B1<-C1<-B2<-C2, ViewNumber(B2) >= ViewNumber(B0)。那么存在Block(B)，当ViewNumber(B) > ViewNumber(B2)，则Previous_Block(B) > B0。
证明： 对于正常诚实节点（给区块B2，B投过票）来说， 那么节点至少可以看到B0<-C0<-B1<-C1<-B2, 也就是Lock-Block最小为Lock-Block(B0)。因为ViewNumber(B) > ViewNumber(B2)，则根据ViewChange确认规则，ViewNumber(B)的第一个区块不小于B1，则Previous_Block(B) > B0
3） 假设节点n的Lock-Block(n) = B，节点m的Lock-Block(m) = B’，如果Number(B) = Number(B’), 则Hash(B) = Hash(B’)
证明： 由上面Lock-Block规则可知，存在2种Lock-Block场景，第一种情况两个QC在同一View内，则由1可知不存在B’和B同时收到足够多投票。第二种情况，出现B与B’分属不同View，且都收到prepareQC(B), prepareQC(B’)。假设ViewNumber(B’) > ViewNumber(B), 那么根据结论2，Previous_Block(B’) > B，与假设矛盾。
4） 在Commit阶段不会有两个相同高度不同块Hash被Commit
证明： 由3可知，如果Number(B) = Number(B’),不存在B，B’‘同时被Lock-Block。则可推不存在Commit(B),Commit(B’)都被提交。
4.3 活跃性（liveness）证明
假设节点间网络最大延时为T，执行区块为S
1） 不存在时间窗口永远小于time(prepareQC)*2时间
证明： 根据实际网络状况，合理调整实际窗口大小，可以保证时间窗口内至少达成2次QC，则时间窗口至少为 2 S+4 T
2） ViewNumber可以达成一致，并且递增
证明： ViewChange达成一致最少需要T，由结论1可以保证ViewChange可以达成一致，为那么ViewNumber可以进行递增切换
3） Lock-Block高度永远递增
证明： 假设ViewNumber为n, n+1, 由安全证明（2），可以保证ViewNumber(n+1)的第一个区块Previous-Block至少为Lock-Block(View(n))，又由于活证明（1), 至少有两次prepareQC，可以得到两个View锁定高度的关系，Lock-Block(View(n+1)) >= Lock-Block(View(n))+1
4.4 通信复杂度分析
- PBFT: 网状网络拓扑，采用二阶段投票协议，消息达到prepared状态即锁定，有单独的视图切换流程，正常流程通信复杂度为$O(n^2)$，视图切换流程通信复杂度为$O(n^3)$。
- Tendermint: 网状网络拓扑，采用二阶段投票协议， 消息达到prepared状态即锁定，视图切换流程和正常流程合并，通信复杂度为$O(n^2)$。
- Hotstuff 星状网络拓扑，采用三阶段投票协议，消息达到pre-commited状态即锁定，视图切换流程和正常流程合并， 通信复杂度为$O(n)$。
- CBFT: 网状网络拓扑，采用三阶段投票协议， 消息达到pre-commited状态即锁定, 自适配视图切换流程， 通信复杂度为$O(n^2)$。