Analysis of Giskard Consensus Protocol

PlatON Global Development & Technologies
#1

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

0_SBQeI0tEbppspFUm
0_SBQeI0tEbppspFUm800×340 44.9 KB

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)

For further discussion

If you want to discuss more about Giskard Consensus Protocol, join our community:

3 个赞