How to Agree: Different Types of Consensus for Blockchain

There are many more types of consensus than Proof of Work and Proof of Stake. Here we introduce the most important alternatives.

In the simplest of terms, a blockchain is data that is processed and recorded by a group of computers, who work together to ensure the authenticity and security of these data transactions.

But how can we ensure that these transactions are, in fact, verified and secure? Blockchains are, by nature, decentralised and distributed, meaning that there is no central authority to exercise governance over the system. To ensure that protocol rules are being followed and prevent any unethical behaviour, blockchains apply various algorithms to achieve what’s known as consensus between trustless entities.

Quick Definition of Consensus

Consensus can be defined as the agreement of a group of agents on their common states via local interaction. 

In the context of blockchain, consensus is a procedure in which the peers of a Blockchain network reach agreement about the present state of the data in the network. It’s these consensus algorithms that establish reliability and trust in Blockchain systems.

While consensus is fairly easy to achieve in centralised networks where one governing authority is trusted to validate transactions and safeguard records, it is far less straightforward in the case of decentralised systems.

Consensus in Blockchain

Blockchain works by adding blocks of data and the essence of consensus is to ensure that every block that is added to the chain is the one and only version of the truth that’s agreed upon by all the nodes in the system. It is a key feature of the decentralised nature of blockchain. 

The base rules for consensus in blockchain include:

• The objective of coming to an agreement
• Collaboration, cooperation, and equal rights to every node/peer, and 
• Mandatory participation of each node in the process

There are many different approaches to reaching consensus on decentralised systems. Here we look at different ways to agree and form consensus.

Nakamoto Consensus

The mother of all blockchain consensus, the Nakamoto consensus protocol was devised by Satoshi Nakamoto in 2009 as a new means of verifying the authenticity of a blockchain network and preventing double-spending. It is a Byzantine fault tolerant consensus algorithm that works in conjunction with Proof of Work (PoW) to govern the Bitcoin blockchain.

Byzantine fault tolerance (BFT) is a condition where a distributed system can remain fault-tolerant in the presence of malicious actors and network imperfection. 

While PoW refers to the cryptographic mechanism whereby miners compete against one another to solve extremely complex (and expensive) computational puzzles in order to earn the right to validate a new block and earn a ‘block reward’. This monetary reward incentivises miners to follow the rules and stay honest, while the participation costs serve as an economic disincentive for them to attack the Bitcoin network, further securing the blockchain. 

Through the combination of BFT and PoW, Nakamoto sought to circumnavigate some of BFT’s inherent issues with scalability, while deterring bad actors. By creating a standard measurement for the blockchain’s validity — in this case, the amount of computational resources (or ‘hashing power’) spent on it — Nakamoto opened a new direction for solving the Byzantine Generals Problem in a permissionless setup; one that would lead to the emergence of many new consensus algorithms, including Proof of Stake (PoS), Proof of Authority (PoA), Proof of Reputation (PoR), and Proof of Importance (PoI).

Proof of X

The idea behind this proof of something (PoX) consensus is to use some scarce resources X where malicious attackers cannot get X easily. In doing so, the system can remain safe in a decentralised and permissionless manner. Here’s how it usually works.

In order to gain the privilege of validating transactions and mining new coins, nodes on a PoX network must provide evidence that they have successfully fulfilled X criteria. Oftentimes, this process involves some sort of sacrifice. For example, computational power and effort in PoW, and staked coins in PoS. In different ways, these serve as incentives for miners to stay honest.

In general, PoX belongs to the class of Nakamoto consensus. Nakamoto consensus normally takes the following design choices:

• Byzantine fault tolerant – networks are able to continue operating even if some nodes fail or act maliciously
• Synchronous – messages are delivered within a fixed time
• Probabilistic – nodes agree on the probability of the value being correct
• Leader-based – leaders are elected to validate transactions

And hence can achieve the following properties:

• Peers can join and leave whenever they want
• Focuses on liveness (i.e. one peer can always produce new blocks) at the cost of safety (i.e. decision taken can be reverted)
• Self-sustaining – peers are incentivised to maintain the network

There are too many PoX protocols to introduce them all. Interested readers can read our beginner’s guide to consensus mechanisms for a summary of the most well-known PoX consensuses today.

Classical consensus

Classical consensus, on the other hand, reaches consensus through voting. These protocols confirm transactions faster than the types of Nakamoto consensus discussed above as the consensus network size is fixed and progress can be made as soon as the required votes are seen. 

Here are some important examples of classical consensus:

Practical Byzantine Fault Tolerance (pBFT)

Introduced in the late 90s by Barbara Liskov and Miguel Castro, practical Byzantine fault tolerance (pBFT) aims to solve many of the problems associated with the aforementioned Byzantine fault tolerance (BFT) solutions.

pBFT uses a three-phase state machine and a block election to select the leader. The three phases of pBFT are known as pre-prepare, prepare, and commit. Where In the usual case, consensus is achieved by exchanging messages among nodes that brings a progressive transition to their local state. Otherwise, in the case of node failure, a ‘view-change’ will be triggered, leading to a re-selection of the leader in a round-robin manner. pBFT is able to handle less than ⅓ of Byzantine faults, this can be seen as 3f+1= Total nodes where f=amount of Byzantine faults.

However, it comes with some disadvantages:

• Weak leadership – nodes can reject requests from the leader and propose re-election, but it requires authority services for the leader selection.
• Byzantine fault tolerance – 33% of the nodes can be malicious.
• Low network scalability – due to the high communication overhead and latency of multiple message rounds, scaling up the number of nodes would also increase the system’s complexity quadratically.
• Transaction throughput – up to 50,000 tx per second with a confirmation time of 1 second.
• Use case – consortium blockchain with a limited authorised validator.

Delegated Byzantine Fault Tolerance (dBFT)

Delegated Byzantine fault tolerance (dBFT) was proposed by the NEO project in 2014. In contrast to pBFT which requires authority services to select the leader, dBFT’s voting system allows for large-scale participation, in a similar way to Delegated Proof of Stake (DPoS).

The overall consensus procedure is very similar to pBFT, where it differs is in how the votes are counted.. In dBFT, the weight of the vote is proportional to the number of tokens that the participants held at the time of voting. Participants can delegate their tokens (votes) to trusted representatives. This enhances the performance, but also means it could become more centralised over time due to this extra layer of representation. A con to this method is that delegates who are elected are no longer allowed to be anonymous. Delegates on the NEO blockchain work under real identities.

Federated Byzantine Agreement (FBA)

The federated Byzantine agreement (FBA) is an algorithm that supports open membership, allowing validators to join the network freely. It is notable for its high throughput, scalability, and low transaction costs. 

FBA can be considered a permissionless BFT. However, a transaction is required to be signed by a specific group of signers. In an FBA system validators are able to choose which other validators they trust and from there they form what is known as a quorum slice. In a system with many validators there may be multiple quorum slices and with multiple quorum slices there becomes overlap with some nodes being trusted in multiple slices. These overlaps come together to form the overarching quorum. Which is used as the method to come to a consensus in FBA. Notable projects that use FBA are Ripple(XRP) and Stellar(XLM).

Some advantages to FBA are:

• Low barrier to entry as membership is open as long as can be trusted and join a quorum slice.
• Anyone can join and leave at any time with the system still being able to function.

Raft

Developed by Diego Ongaro and John Ousterhout in 2014, Raft is based on the Paxos protocol and was designed to be easier to comprehend and implement. Compared to many other consensus algorithms, Raft has a stronger dependency on the leader. Nodes will trust the leader once randomised timers elect it, and it will be re-elected only if the current leader fails. 

This improved things considerably:

• Strong leadership – nodes would not reject requests from the leader, no re-election until the leader is unavailable.
• Crash fault-tolerant – 49% of the nodes can crash or become unavailable.
• High network scalability – The complexity of this consensus algorithm is linearly proportional to the number of nodes.

Examples:

Leaderless Consensus

The last type of consensus we will introduce is a new emerging direction – leaderless consensus.

As covered earlier, consensus means the agreement of a group of agents on their common states via local interaction. 

In a leaderless consensus problem, no virtual leader is needed, while in a leader-following consensus problem, a virtual leader that specifies the objective for the whole group is required. More specifically, consensus with a static virtual leader is called a consensus regulation problem, and consensus with a dynamic virtual leader is called a consensus tracking problem.

Examples of leaderless consensus projects include Avalanche, IOTA, and NKN. We will introduce Avalanche and IOTA here at a high level.

Avalanche

The Avalanche whitepaper was released anonymously in mid-May 2018 by a team identifying themselves only as Team Rocket. Later, AVA Labs was founded to develop the token Avalanche (AVA), and it is believed that a group of computer scientists from Cornell University (Emin Gün Sirer, Kevin Sekniqi, Ted Yin) are closely associated with the project.

Team Rocket called the consensus protocol a “novel metastable consensus protocol family for cryptocurrencies” and described it as “a new family of leaderless Byzantine fault tolerance protocols, built on a metastable mechanism”.

Avalanche makes use of repeated random subsampling for voting to reach a consensus. Each node needs to sample a certain number of neighbours to verify their states to see if it aligns with the majority. If not, they will change their states following the majority. The process will repeat again and again, so eventually, the whole network will come up with a ubiquitous conclusion in the long run.

Avalanche claimed its consensus mechanism could reach 1,300 tps with 4 seconds latency.

According to the team, Avalanche’s mainnet is expected to be released in September 2020.

IOTA

IOTA was founded in 2015 by David Sonstebo, Sergey Ivancheglo, Dominik Schiener, and Dr. Serguei Popov. IOTA is among the earliest coins to propose using a directed acyclic graph (DAG) as the underlying data structure for a distributed ledger technology (DLT) instead of blockchain.

The current version of IOTA is using a protocol called Tangle. The Tangle has the following properties that are different from that of bitcoin:

• It uses a DAG-based data structure to form the transaction graph instead of grouping transactions into chained blocks.
• It removes the role of miners and requires the user to verify two previous (unconfirmed) transactions if they intend to send new transactions to the network.
• Consensus/voting is based on local information and doesn’t require interaction with the whole network. Instead, it is achieved via a weighted random walk process called Monte-Carlo Markov Chain (MCMC)
• However, the whitepaper didn’t specify clearly how consensus can be reached in a distributed environment. Hence, the network relies on a centralised ‘coordinator’ until today, which the crypto community has widely criticised.

Recently, the IOTA Foundation has stated their roadmap called ‘Coordicide’ to revamp the protocol and remove the coordinator. Two consensuses were proposed: the fast probabilistic consensus (FPC) and the cellular consensus (CC). Both solutions belong to the class of leaderless consensus. 

Consensus and Scaling the Blockchain

And there you have it, an overview of the most commonly used consensus mechanisms. Like all parts that keep a blockchain moving, we can see a distinct evolution here as well, from the original concept to faster and nimbler versions helping to scale blockchains for faster speeds and larger networks. If you want to learn more about the basic functions of blockchain, also check out our articles on sidechains and how they help build much more than just a payment system on the chain.