 # Analysis of Giskard Consensus Protocol

Translated from: https://mp.weixin.qq.com/s/LHCPK7Afn6tmUGRSYx1Wzg

In the previous article, we have briefly analysed the weighted proof of stake protocol based on verifiable computing, Giskard, which was invented by PlatON.

## Basic Rule Definition

In order to easier analyse the safety and liveness of the Giskard consensus protocol, we define a couple of basic rules here.

### Rule of K-Chain

When the following condition is met for a chain:

B(0)<-C(0)<-…<-B(k-1)<-C(k-1)

We define it as K-Chain, B stands for Block, C stands for B’s prepare QC. When the chain reaches 3-Chain, eg. B0<-C0<-B1<-C1<-B2<-C2, B0 reach the commit state.

### Rule of Lock-Block

When node A prepareQC 2 times after receiving block n, block n is defined as Lock-Block(a). So that, when Lock-Block(a)=B0, B0 reaches 2-Chain, eg. B0<-C0<-B1<-C1

### Rule of Unlock-Block

Given Lock-Block(a) is n, when sub-block n+1 of n prepareQC 2 times, then Lock-Block(a) is n+1. So that, when Lock-Block(a)=B0, B0 reaches 2-Chain, eg. B0<-C0<-B1<-C1-B2, when B0 Unlock-Block, B0 reaches 3-Chain, eg. B0<-C0<-B1<-C1<-B2<-C2.

### Rule of Previous-Block

Pattern like Block(B)<-prepareQC(B)<-Block(B’), we define Block(B) as *Block(B’)’*s Previous-Block, so that Previous-Block(B’) = Block(B).
Based on the rule of Lock-Block and the rule of Previous-Block, we can see:
In node a, chain shape is B<-C<-B’<-C’<-B’’,Previous-Block(B’’) > Lock-Block(a)

### Rule of Commit

When a node receives 3 times of prepareQC after receiving block n, then block n is committed. So that, when B0 was committed, B0 reaches 3-Chain, eg. B0<-C0<-B1<-C1<-B2<-C2.

## Proof of Safety

1. Two blocks in the same View with the same height can not both receive enough votes
Proof: Given nodes number is N=3f+1, f is the max number of Byzantine nodes, the minimal votes required is 2f+1. Because 2 nodes both need 2f+1 votes, so that the minimal number of total votes is 2(2f+1)=N+f+1, we can see that at least f+1 votes to these two blocks, which contradict the assumption of Byzantine nodes.

2. For 3-Chain B0<-C0<-B1<-C1<-B2<-C2, ViewNumber(B2) ≥ ViewNumber(B0). When Block(B) exists and ViewNumber(B) > ViewNumber(B2), then Previous_Block(B)>B0
Proof: Normal honest nodes (nodes voted for block B2 and B) can view B0<-C0<-B1<-C1<-B2<-C2, which means the minimum of Lock-Block is Lock-Block(B0). Because ViewNumber(B) > ViewNumber(B2), base on the confirmation rules of ViewChange, the first block of ViewNumber(B) is greater or equal to B1, then Previous_Block(B) > B0

3. Given Lock-Block(n)=B in node n, Lock-Block(m)=B’ in node m, if Number(B) = Number(B’), then Hash(B) = Hash(B’)
Proof: Regarding the rule of Lock-Block above, there are 2 scenarios of Lock-Block.
The first scenario is when two QC in the same view, base on the first proof of safety we can tell B’ and B can’t receive enough votes at the same time.
The second scenario is when B’ and B are in different Views, have both received prepareQC(B) and prepareQC(B’). Given ViewNumber(B’) > ViewNumber(B), so base on the 2nd proof of safety, Previous_Block(B’) > B, which contradicts the assumption.

4. There won’t be 2 same heights block’s with different block hash be both committed during the commit stage.
Proof: Base on the third proof of safety, if Number(B)=Number(B’), B and B’’ can’t both be Lock-Block at the same time. Therefore, Commit(B) and Commit(B’) won’t be both committed.

## Proof of Liveness

Given the maxim network delay between node is T, the execution block is S

1. Time window won’t always less than time(prepareQC) * 2
Proof: By adjust the actual window size base on the situation of the network, it can guarantee at least 2 times of QC in the time window, therefore the minimal time window is 2S + 4T

2. ViewNumber can reach an agreement and increase
Proof: It at least needs T for ViewChange to reach an agreement, base on the first proof of liveness, it can guarantee that ViewChange will reach an agreement, therefore ViewNumber can switch to increase.

3. Lock-Block heights will always increase
Proof: Given ViewNumber is n, n+1, base on the second proof of safety, it can guarantee the first Previous-Block block of ViewNumber(n + 1) is greater or equal to Lock-Block(View(n)), and base on the first proof of liveness, at least the lock heights’ relationship between two View can be acquired by two prepareQC, Lock-Block(View(n+1))≥Lock-Block(View(n))+1

## Analysis of the Communication Complexity

• PBFT: Mesh network topology, it’s using the two-stage voting protocol, the message will get locked once it reaches the prepared state. It has the standalone process of view switching. The communication complexity of a normal process is O(n2), the communication complexity of view switching is O(n3).
• Tendermint: Mesh network topology, it’s using the two-stage voting protocol, the message will get locked once it reaches the prepared state. The view switching process and normal process are merged, communication complexity is O(n2).
• Hotstuff: Star network topology, it’s using the three-stage voting protocol, the message will get locked once it reaches the pre-commit state. The view switching process and normal process are merged, communication complexity is O(n).
• Giskard: Mesh network topology, it’s using the three-stage voting protocol, the message will get locked once it reaches the pre-commit state. It has a self-adapting view switching process, communication complexity is O(n2)