Consensus algorithm is a hotspot of distributed system research in recent years, and also a core element of blockchain technology. How to understand the importance and evaluation system of consensus algorithms? How to recognize the current mainstream consensus algorithm and the development behind it? What are the trends and obstacles in the development of consensus algorithms?

 

Consensus Algorithm

The consensus algorithm mainly aims to solve the issue of achieving consistent results for a certain state among multiple nodes in a distributed system. In the distributed system, transactions are processed by multiple service nodes and the data state of multiple copies in needs to keep consistent.

However, due to the unreliability and instability of nodes communication and even the malicious response from forged node information, the data state may be inconsistent among the nodes. Through the consensus algorithm, multiple unreliable individual nodes can be built into a reliable distributed system to achieve data state consistency and improve system reliability.

The blockchain system itself is a very large-scale distributed system. However, it is significantly different from the traditional one. Being based on a decentralized peer-to-peer network, the blockchain system has no central authority in the whole system. It’s the consensus algorithm that reaches the agreement on the order of transaction processing among the dispersed nodes. That’s the most important role played by the consensus algorithm in the blockchain system.

In addition, unlike the enterprise distributed systems, the consensus algorithm in the blockchain system also undertakes some functions of incentive model and governance model, including which workers to be granted with incentives in each block, the settlement and allocation of all transaction fees, the switch of network consensus cycle, etc.

Based on different fault tolerance capabilities, that is, considering the case when the node fails to respond and judging whether the node will forge information for malicious response, the consensus algorithm can be classified into two types: the CFT (Crash Fault Tolerance) and BFT (Byzantine Fault Tolerance).

• The CFT only guarantees the reliability of the entire distributed system when a node suffers from a shutdown. When the node in the system violates the consensus protocol (such as being hacked, the data is maliciously tampered, etc.), the reliability of the distributed system cannot be guaranteed. Therefore, the CFT is mainly applied in the closed distributed system of the enterprises. The popular CFTs mainly include the Paxos and the derived Raft consensus algorithm.
• For the distributed system adopting the BFT, once any type of error occurs in the node of the system, so long as the number of nodes is less than a certain ratio, the reliability of the entire system can still be guaranteed. Therefore, in the open distributed system, such as blockchain network, the BFT consensus algorithm must be adopted.

Before the development of blockchain network, the BFT is mainly the PBFT consensus algorithm. At present, some alliance chains still adopt the PBFT consensus algorithm. Due to the openness of public chains, any nodes can participate in and withdraw from the network at any time with the possibility of malicious intentions. The rapid development of public chains in the past two years has also promoted the big progress of the BFT consensus algorithm.

In addition, because the consensus algorithm is based on the underlying network model, from the perspective of the network synchronization model, the consensus algorithm can be divided into three types, namely, synchronous consensus algorithm, semi-synchronous consensus algorithm and asynchronous consensus algorithm.

The synchronization consensus algorithm demands any message in the network to reach all the consensus nodes within a known limited time. Therefore, it is mainly used in a network environment of limited scale, such as most of the alliance chains.

The asynchronous consensus algorithm has no restrictions on the delay of message in the network. Messages can be sent to other consensus nodes without time limit. Due to the FLP Impossibility, the asynchronous consensus algorithm cannot guarantee the final consensus, so there is almost no efficient all-asynchronous consensus algorithm, even the Bitcoin POW algorithm is based on the synchronous network to ensure consistency and based on asynchronous networks to ensure availability.

The semi-synchronous consensus algorithm makes a trade-off between synchronous consensus algorithm and asynchronous consensus algorithm and demands the relationship between the probability and time to reach all consensus nodes after a certain time in the network should be known. The mainstream blockchain consensus algorithms are based on the semi-synchronous network model, that is, the semi-synchronous consensus algorithm.

 

The  Evaluation System of Consensus Algorithm

The evaluation on the merits of blockchain consensus algorithm can be done from the following four aspects: fault tolerance performance, finality performance, scalability (message complexity) and network model performance.

Fault Tolerance Performance: Refers to the fault tolerance of the consensus algorithm. For example, Raft can only support node fault errors. In the blockchain, especially the public chain, since there’s benefit rivalry among nodes in a decentralized network, the consensus algorithm must support the fault tolerance of the malicious nodes, so the consensus algorithm of the blockchain must adopt the BFT algorithm.

Finality Performance: It refers to the time required by the blockchain network to complete the final consistency of a candidate block, which is a very important parameter for user-oriented DApp application.

Scalability: It refers to the correlation between the number of blockchain network nodes and the performance of consensus algorithm. Take the PBFT algorithm as an example, as the number of nodes increases, the number of messages conveyed in the network needs to be increased in a squared ratio, so the PBFT algorithm cannot support large-scale network due to its natural characteristics.

The network model performance of the consensus algorithm has a great influence on its fault tolerance performance and finality performance. Under the large-scale network of blockchain, the synchronous consensus algorithm demands all nodes to respond to messages from other nodes within a specified time. Otherwise, it will be considered as a faulty node. So, it is greatly affected by network fluctuations, resulting in reduced fault-tolerant performance. Due to the FLP Impossibility, the asynchronous consensus algorithm cannot ensure a definitive final performance, so the mainstream blockchain consensus algorithm now is based on the semi-synchronous model.

 

Current Mainstream Consensus Algorithms

In the early stages of blockchain development, mainstream blockchain networks were based on POW consensus algorithm, including Bitcoin, Ethereum, Litecoin and Zcash. Due to the waste of mining resources in POW, the research on consensus algorithm based on POS has been developed rapidly since 2017. In 2018, various public chains based on POS consensus algorithm were launched consecutively.

The current mainstream consensus algorithms can be classified by the following standards:

Classified based on mining methods:

• POW: All nodes participate in consensus by solving a computation problem (such as hash problem), including Bitcoin, Ethereum and Litecoin
• POS: All nodes participate in the consensus by pledge tokens, including: Ethereum-PoS, Tendermint, Algorand, EOS DPoS, DFINITY and VBFT

Classified based on finality:

• GHOST：PoW，Ethereum-PoS
• BFT：Tendermint，EOS DPoS，Algorand，DFINITY，VBFT

Classified based on node selection:

• Participated by all nodes: PoW, Ethereum PoS, Tendermint
• Participated by randomly selected nodes: Algorand, Dfinity, VBFT

According to the aforesaid classifications, we can see the evolution process of current blockchain consensus algorithm in the direction of performance, expandability and decentralization.

When Bitcoin blockchain technology was created, the PoW consensus algorithm was also created to implement the decentralized consensus algorithm by calculating the hash problem and the longest chain. As the size of Bitcoin network and the delay of subsequent blocks keep increasing, the rule based on the longest chain results in many pseudo-forks, the hash in the network and the performance of POW consensus algorithm have been greatly wasted.

For the problem of pseudo-fork, the blockchain community proposed to extend the POW consensus algorithm through DAG, such as PHANTOM and Conflux. However, for the waste of hashrate in POW, the blockchain community has turned to the consensus algorithm based on POS.

Ethereum also intends to gradually reduce POW incentives until it’s finally cancelled to complete the switch into the POS consensus algorithm. Meanwhile, most of the emerging blockchain platforms have also adopted the POS consensus algorithm, the most famous one is the EOS DPoS consensus algorithm.

At the same time, with more and more blockchain applications, the expandability has also been increasingly prominent. Professor Micali, the winner of Turing Award, proposed the Algorand algorithm and the way of participating in consensus by randomly selecting some nodes based on VRF. The way based on BFT can greatly reduce the message complexity of the consensus algorithm and realize the expandability of consensus algorithm while ensuring the security of decentralization.

On this basis, the consensus algorithms such as VBFT have included the governance mechanism based on POS to solve the sampling trap problem resulting from random node selection and ensure the expandability of algorithm while realizing the excellent finality performance.

The hybrid consensus algorithm is also worthy of being introduced. Due to the limitation of single consensus algorithm itself, such as the slow speed of POW consensus. The blockchain researchers have tried to combine the two or more consensus algorithms for complementary advantages. In general, the hybrid consensus algorithms include PoW+PoS, PoW+BFT and PoS+BFT. It’s easy to find out that the new generation of consensus algorithms, such as Algorand, DFINITY, BUMO BU Firework and Ontology VBFT, all belong to the hybrid consensus algorithms.

 

Trend of Consensus Algorithm Development

Generally speaking, the mainstream consensus algorithms are gradually developing from POW to POS to realize the expandability of algorithm by VRF random node selection. Even the Ethereum’s “Serenity” version is also based on the POS consensus algorithm to realize the VRF random node selection in beacon chain. Moreover, the Avalanche consensus algorithm also adopts the way of random node selection to realize the expandability of the blockchain consensus algorithm.

With further community researches on blockchain consensus algorithm, the technical community has found that the upper limit of performance achievable in Internet-scale network depends not only on the performance parameters of consensus algorithm, but also on the physical upper limits such as the time delay for message delivery in the network of such a scale. Therefore, the research team of mainstream blockchain has focused the performance extension of blockchain network on the directions such as sharding technology, state channel and layer 2 network.