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 KChain
When the following condition is met for a chain:
B(0)<C(0)<…<B(k1)<C(k1)
We define it as KChain, B stands for Block, C stands for B’s prepare QC. When the chain reaches 3Chain, eg. B0<C0<B1<C1<B2<C2, B0 reach the commit state.
Rule of LockBlock
When node A prepareQC 2 times after receiving block n, block n is defined as LockBlock(a). So that, when LockBlock(a)=B0, B0 reaches 2Chain, eg. B0<C0<B1<C1
Rule of UnlockBlock
Given LockBlock(a) is n, when subblock n+1 of n prepareQC 2 times, then LockBlock(a) is n+1. So that, when LockBlock(a)=B0, B0 reaches 2Chain, eg. B0<C0<B1<C1B2, when B0 UnlockBlock, B0 reaches 3Chain, eg. B0<C0<B1<C1<B2<C2.
Rule of PreviousBlock
Pattern like Block(B)<prepareQC(B)<Block(B’), we define Block(B) as *Block(B’)’*s PreviousBlock, so that PreviousBlock(B’) = Block(B).
Based on the rule of LockBlock and the rule of PreviousBlock, we can see:
In node a, chain shape is B<C<B’<C’<B’’,PreviousBlock(B’’) > LockBlock(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 3Chain, eg. B0<C0<B1<C1<B2<C2.
Proof of Safety

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. 
For 3Chain 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 LockBlock is LockBlock(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 
Given LockBlock(n)=B in node n, LockBlock(m)=B’ in node m, if Number(B) = Number(B’), then Hash(B) = Hash(B’)
Proof: Regarding the rule of LockBlock above, there are 2 scenarios of LockBlock.
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. 
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 LockBlock 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

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 
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. 
LockBlock heights will always increase
Proof: Given ViewNumber is n, n+1, base on the second proof of safety, it can guarantee the first PreviousBlock block of ViewNumber(n + 1) is greater or equal to LockBlock(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, LockBlock(View(n+1))≥LockBlock(View(n))+1
Analysis of the Communication Complexity
 PBFT: Mesh network topology, it’s using the twostage 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(n^{2}), the communication complexity of view switching is O(n^{3}).
 Tendermint: Mesh network topology, it’s using the twostage 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(n^{2}).
 Hotstuff: Star network topology, it’s using the threestage voting protocol, the message will get locked once it reaches the precommit state. The view switching process and normal process are merged, communication complexity is O(n).
 Giskard: Mesh network topology, it’s using the threestage voting protocol, the message will get locked once it reaches the precommit state. It has a selfadapting view switching process, communication complexity is O(n^{2})
For further discussion
If you want to discuss more about Giskard Consensus Protocol, join our community:
 Discord: https://discord.gg/JUmWFSVU
 Telegram: https://t.me/PlatONNetworkCN
 Twitter: https://twitter.com/PlatON_Network