Giskard共识协议的分析

在上一篇内容中我们浅析了PlatON提出的基于可验证计算的加权权益证明共识方法Giskard。今天我们将解析Giskard共识协议的分析。

基本规则定义

为方便对Giskard共识协议的安全性和活跃进行分析 ，我们定义Giskard共识协议的几条基本规则。

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状态。

Lock-Block规则

节点a中， 当区块n收到区块n之后的2次prepareQC，则区块n定义为Lock-Block(a)。可以观察到，当Lock-Block(a)=B0时，B0达到2-Chain, 如B0<-C0<-B1<-C1。

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。

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)

Commit规则

当区块n，收到区块n之后的3次prepareQC，则区块n被Commit。可以观察到，当B0被Commit时，B0达到3-Chain，如B0<-C0<-B1<-C1<-B2<-C2。

安全性（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)，则Previous_Block(B)>B0。

证明：对于正常诚实节点（给区块B2，B投过票）来说， 那么节点至少可以看到B0<-C0<-B1<-C1<-b2,>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')都被提交。

活跃性（liveness）证明

假设节点间网络最大延时为T，执行区块为S

1. 不存在时间窗口永远小于time(prepareQC)*2时间

证明： 根据实际网络状况，合理调整实际窗口大小，可以保证时间窗口内至少达成2次QC，则时间窗口至少为2S+4T

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

通信复杂度分析

PBFT：网状网络拓扑，采用二阶段投票协议，消息达到prepared状态即锁定，有单独的视图切换流程，正常流程通信复杂度为，视图切换流程通信复杂度为。

Tendermint：网状网络拓扑，采用二阶段投票协议，消息达到prepared状态即锁定，视图切换流程和正常流程合并，通信复杂度为。

Hotstuff：星状网络拓扑，采用三阶段投票协议，消息达到pre-commited状态即锁定，视图切换流程和正常流程合并，通信复杂度为。

Giskard：网状网络拓扑，采用三阶段投票协议，消息达到pre-commited状态即锁定，自适配视图切换流程，通信复杂度为。