Read the Giskard Consensus Protocol in one article

In this article, we will briefly introduce PPoS consensus and BFT theory, followed by a focus on Giskard.

The Giskard consensus protocol of PlatON consists of the probabilistic proof of stake PPoS (PlatON proof of stake) and the Giskard Byzantine Fault Tolerance protocol – Giskard BFT (Giskard Byzantine Fault Tolerance). Giskard BFT uses a BFT-like algorithm for block production and verification.

In this paper, we will briefly introduce PPoS consensus and BFT theory, and analyze the characteristics of PBFT algorithm and the problems of PBFT, and then focus on the evolutionary path of Giskard BFT borrowing from PBFT, Tendermint, Hotstuff and other consensus protocols.

The essence of blockchain technology cannot be separated from traditional distributed systems. Distributed consistency algorithm is a major problem of traditional distributed systems, after a long period of research and application, mature and secure algorithms such as paxos, raft, zab, etc. have been born.

Compared with traditional distributed systems, there is no centralized assumption in public blockchain, and any node can join and freely access all the data, so there will inevitably be malicious nodes in public chain. Therefore, the consensus mechanism in blockchain system needs to support not only CFT (Crash fault tolerance) but also BFT (Byzantine Fault Tolerance), which is a well-researched theory, and PBFT is the most famous implementation algorithm and is widely used in major BFT is a well-researched theory, and PBFT is the most famous implementation algorithm, which is widely used in major blockchain systems.

PlatON’s Giskard consensus protocol consists of a probabilistic proof of stake (PPoS) and a Giskard Byzantine Fault Tolerance (Giskard BFT) protocol. PPoS uses pledge, delegation, and random selection to select verification nodes to participate in consensus, and Giskard BFT uses a BFT-like algorithm for block production and verification.

PPOS – Verification Node Selection

Before introducing PPoS, let’s first popularize PoS, which currently can be divided into four categories of consensus schemes.

PoS Consensus Overview

Chain-Based

This is an early generation of PoS. pseudo-randomly selects verifiers for block production based on the number of tokens held. There is also a PoS+PoW scheme, which is generally PoW out of the block, and the verifier is selected for verification through PoS. Ether’s Casper 1.0 is also a hybrid PoS/PoW scheme, as an intermediate scheme for its conversion from PoW to PoS.

DPoS (Delegated Proof of Stake)

Delegated Proof of Stake. Each token holder can delegate rights to a partial representative who will participate in the production and verification of the block.

VRF (Verifiable Random Function)

Verifiable Random Function is used to verify the random selection of nodes. Currently, this scheme is used by Dfinity, Cardano and Algorand, among others.

BFT (Byzantine Fault Tolerance)

Byzantine Fault Tolerance. The verification node is selected and then the block is confirmed to complete consensus by running the BFT protocol through multiple rounds of voting. Currently Tendermint, Stellar, Ontology, Zilliqa, NEO, etc. are all using this type of consensus algorithm.

PlatON’s consensus scheme PPoS, which is often referred to as probabilistic proof of interest, is essentially a PoS consensus scheme that plots a binomial distribution cumulative distribution curve based on the nodes’ interests and randomly selects verification nodes using VRF.

The key core point of the PPoS solution is that the selection of the verifier is not only related to the size of the node’s equity, but also random, which means that the selected verifier node is not necessarily the node with the highest equity, and the node with lower equity also has a certain probability of being selected. PPoS is essentially a combination of PoS+VRF scheme.

A simple summary is that PPoS provides a scheme to select a number of verification nodes from a large number of participating nodes as fairly and randomly as possible.

BFT – Block Consensus

After the verification nodes are elected, the consensus protocol is run for block production and verification. The whole process requires the nodes to collaborate with each other to mutually confirm the blocks and reach a unanimous conclusion to reach block consensus.

As mentioned above, the consensus algorithm in blockchain needs to consider not only Crash nodes, but also Byzantine nodes. What is a Byzantine node? Let’s start with a story.

The Byzantine General Problem

The Byzantine Roman Empire was so vast that for defense purposes, each fief had an army led by a general, and each army was so far apart that the only way to send messages from general to general was by messenger.

In times of war, all generals in the Byzantine army had to agree on whether there was a chance of winning before attacking the enemy’s camp. However, there could be traitors and enemy spies in the army who could influence the decision of the generals to reach a unanimous consensus. The problem of how to reach a unanimous agreement among the remaining loyal generals when a general is known to be a traitor is the Byzantine General Problem.

What the Byzantine General Problem describes is that the good generals do not know whether the other generals are good or bad, but the purpose of all good generals is: to act in unison and move forward together. Therefore, they need to agree on strategy.

Seeing this, I believe you have a preliminary understanding of Byzantine nodes. Briefly, there are two types of errors in the blockchain system as follows.

The first type of error is node crash, network failure, packet loss, etc. This type of error is not malicious and is a non-Byzantine error.

The second type of error is that the node may be malicious and does not follow the protocol rules. For example, the verifier node can delay or reject messages in the network, the leader can propose invalid blocks or the node can send different messages to different peers. In the worst case, malicious nodes may collaborate with each other. These are collectively referred to as Byzantine errors.

For this problem to have a solution, it is also necessary to first introduce a concept – the distributed network model, which, according to the theory of distributed systems, is divided into three categories.

Synchronous network model: the messages sent by nodes will definitely reach the target node in a determined time

Asynchronous network model: the message sent by a node cannot be sure to reach the target node

Partially synchronous network model: the message sent by the node, although there is a delay, will eventually reach the target node

A very important prerequisite for solving the Byzantine General problem is that the communication channel must be reliable. If the channel is not guaranteed to be reliable, then the Byzantine problem is unsolvable. This is the FLP impossibility principle, i.e., under the assumption of the asynchronous network model, consensus algorithms cannot satisfy both safety and liveness, i.e., it is basically impossible or very difficult to reach agreement through communication on an unreliable communication link. As for what is safety and liveness, we will talk about them later.

In fact, the Byzantine generals problem was first proposed by Leslie Lamport in his 1982 paper “The Byzantine Generals Problem”, where he proved that loyal generals can agree on orders when the total number of generals is greater than 3f and the number of betrayers is f or less, i.e., 3f+1<=n. And Miguel Castro and Barbara Liskov first proposed the PBFT algorithm in their 1999 paper “Practical Byzantine Fault Tolerance”, which also satisfies 3f+1<=n for the number of fault tolerances.

BFT is a well-studied theory that tells us that the ultimate consistency can be achieved among non-Byzantine nodes based on the assumption of a partially synchronized network model with no more than one-third of faulty and misbehaving nodes.PBFT is the most famous implementation of this algorithm, meaning Practical Byzantine Fault Tolerance. Currently, most of the blockchain consensus algorithms are based on BFT implementations. giskard BFT is also evolved from PBFT.

Application of PBFT algorithm in blockchain consensus

PBFT algorithm is widely used in all kinds of blockchain consensus, which not only solves the Byzantine node problem that may occur in the consensus process, but also enables the system to always maintain two attributes: safety (security) and activeness (liveness).

Safety: The consensus system cannot produce incorrect results when two types of errors, Crash node and Byzantine node, occur. In blockchain, it means no double spending and forking.

Activation: The system has been able to continuously generate commits, which in a blockchain means that the consensus will continue without getting stuck. If the consensus of a blockchain system is not sustainable, then the system cannot respond to new transaction requests from clients, i.e., it does not satisfy liveness.

We directly take the application of PBFT algorithm in blockchain consensus as an example to summarize the core process of the algorithm.

Read the Giskard Consensus Protocol in one article

PBFT’s view switching process

The view-change process of PBFT is also divided into three phases.

view-change: each replica node (Replica) will send a view-change message to other nodes when it thinks the primary node (Primary) has a problem

view-change-ack: After receiving 2*f+1 view-change messages, each node elects the node with the smallest node number that is currently alive to be the new primary node and sends a view-change-ack message to that node

new-view: When the new master node receives 2*f+1 view-change-ack messages from other nodes, it broadcasts a new-view message to other nodes. Note: slave nodes do not initiate new-view events

Through the analysis of the consensus process, we believe that we can understand the view switching process very well, so we will not repeat it here. Next, we focus on the problems of PBFT algorithm, and Giskard BFT improvement optimization.

Problems of PBFT

Through a detailed analysis of the three stages of the PBFT consensus process, we can see that the message transmission overhead is large. The system involves n nodes to broadcast messages to n-1 other nodes when trying to reach a state consensus, so the algorithm communication complexity reaches O(n²), and the amount of communication to be exchanged is 1,000,000 for a number of nodes of 1000. some experiments show that the performance of the algorithm drops dramatically when the number of nodes exceeds 20.

In addition, in the process of electing the Leader in PBFT, it is possible that after multiple rounds of interaction, the elected Leader keeps running for a long time until the Leader node fails to initiate the view switching process. However, in the blockchain system, the viewview represents a consensus unit, and the consensus process consists of one view after another, with one identified proponent in each view leading the consensus protocol and generating blocks, and the remaining verifiers voting and signing on the blocks to reach consensus. Because nodes generate blocks with benefits (e.g., bookkeeping rights, block rewards, etc.), it is necessary to frequently change the nodes that produce blocks, i.e., it is necessary to frequently switch viewviews, which will inevitably lead to a huge consumption of network resources.

Giskard BFT consensus optimization

Therefore, we designed Giskard BFT based on the BFT protocol, combined with the characteristics of the blockchain, and mainly focused on the following points for protocol optimization.

view-change process optimization
All BFT protocols replace the master node by view-change. PBFT, SBFT and other protocols have a separate view-change process, which is triggered when the master node has a problem. In Tendermint, HotStuff and other protocols, there is no explicit view-change process, and the view-change process is integrated into the normal process, thus improving the efficiency of view-change and reducing the complexity of view-change communication.

Giskard BFT is also a view-based consensus protocol, to reduce the communication complexity, Giskard BFT also does not have an explicit view change process, but combines this process with the normal outgoing block process.Giskard BFT agrees that each proposing node generates 10 consecutive blocks in this view, and each block reaches QC ( Quorum Certificate, which means that the node receives 2*f+1 signatures for the block) status, then it automatically switches to the next view without the need for a separate view-change voting process.

The following figure shows the explicit ViewChange process, which can be seen to have no view-change-ack and new-view phases similar to those in PBFT, which are replaced by the subsequent prepareQC(n).

Read the Giskard Consensus Protocol in one article

Giskard BFT viewchange voting process

To summarize, two key points of view-change process optimization.

No explicit view change process is needed to reduce voting actions.

There is no view-change-ack and new-view phase, instead, the new view is “indirectly” confirmed by the subsequent prepareQC(n) in combination with blockchain features.

Applying BLS aggregated signatures

In order to further reduce the message communication volume, we use the aggregated signature technique. The industry’s dominant aggregated signature scheme is BLS aggregated signature, which is an extension of the BLS signature scheme.

In Giskard BFT, we aggregate multiple node signatures for block and view-change messages into a single signature, which can be simply understood as “compressing” a long section of signatures from multiple nodes into a single signature. This approach greatly reduces the communication volume and plays a significant role in improving the communication efficiency of the protocol.

Block production and verification parallelization

This optimization is a unique innovation of Giskard BFT. Parallelism here means: parallelization of block production and block validation.

As mentioned above, Giskard BFT is a consensus protocol based on viewview, where each proposing node produces 10 blocks consecutively within this view, and the parallel process is as follows.

The proposing node can propose multiple blocks consecutively within a view, and the next block is generated without waiting for the previous block to reach QC status.

The verifier can execute the transaction of the next block in parallel while receiving the vote of the previous block.

This approach greatly improves the block-out speed and also improves the consensus performance of the system.

Introducing the pipeline approach to block validation

In the traditional BFT-dominated blockchain system, the consensus of each block usually needs to go through explicit Pre-Commit and Commit phases before final confirmation.

Pre-Commit: When a node receives 2*f+1 Prepare votes, it broadcasts Pre-Commit, which can be regarded as a confirmation of the Prepare phase.

Commit: When 2*f+1 Pre-Commit votes are received, it indicates that all nodes agree on the specified message and commit to local disk.

Giskard BFT has only Prepare votes for each block, no explicit Pre-Commit and Commit phases, so how does the block reach the final confirmation?Giskard BFT can be seen as a Pipeline version of BFT, where each PrepareQC is a confirmation of a higher phase of the previous block.

Read the Giskard Consensus Protocol in one article

Giskard BFT’s block confirmation process

As shown in the diagram prepareQC(2) as the Pre-Commit stage of Block(1) prepareQC(3) as the Commit stage of Block(1) and the Pre-Commit stage of Block(2).

Simply put, it is “omitted” the Commit stage of PBFT, here the reader may have doubts: the previous article does not clearly give the conclusion that the message must pass three stages to reach consistency? In fact, Giskard BFT does not really have no Commit stage, but combines the characteristics of blockchain to indirectly confirm the QC status of the next block as the Commit of the previous block.

Giskard BFT combines the chain structure of blockchain and introduces the pipeline approach to block acknowledgement, which makes the protocol simple and beautiful, and can be well process-oriented operation, improving the performance of the protocol, in addition to leaving enough design space for the scalability of the protocol.

Conclusion

At present, PlatON test network, main network and Alaya network with Giskard consensus protocol have been running stably and efficiently for a long time, and its safety and liveness have been fully verified. The role of Giskard consensus in solving the over-centralized system, reducing the complexity of network communication, message complexity, improving consensus efficiency and the transaction processing performance of the whole blockchain is undoubted.

In the later versions of the protocol, we will continue to deepen the optimization: the selection of verifier not only adopts VRF, but also plans to further increase the randomness by combining verifiable secret sharing PVSS, BLS and other cryptographic algorithms; the introduction of group consensus again improves the scalability of the algorithm to efficiently support more verification nodes to join and increase the security and fault tolerance of the network.

Posted by:CoinYuppie,Reprinted with attribution to:https://coinyuppie.com/read-the-giskard-consensus-protocol-in-one-article/
Coinyuppie is an open information publishing platform, all information provided is not related to the views and positions of coinyuppie, and does not constitute any investment and financial advice. Users are expected to carefully screen and prevent risks.

Like (0)
Donate Buy me a coffee Buy me a coffee
Previous 2021-06-05 00:29
Next 2021-06-05 00:35

Related articles