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:
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
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 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
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.
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
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.
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)
For further discussion
If you want to discuss more about Giskard Consensus Protocol, join our community: