Consensus

Consensus is the backbone of a blockchain, as it provides the decentralization of control through an optional process known as mining. The choice of the consensus algorithm to utilize is governed by the type of blockchain in use; that is, not all consensus mechanisms are suitable for all types of blockchains. For example, in public permissionless blockchains, it would make sense to use PoW instead of mechanisms that are more suitable for permissioned blockchains, such as Proof of Authority (PoA) or traditional Byzantine fault-tolerant consensus mechanisms. Therefore, it is essential to choose an appropriate consensus algorithm for a particular blockchain project.

Consensus is a process of achieving agreement between distrusting nodes on the final state of data. To achieve consensus, different algorithms are used. It is easy to reach an agreement between two nodes (in client-server systems, for example), but when multiple nodes are participating in a distributed system and they need to agree on a single value, it becomes quite a challenge to achieve consensus. This process of attaining agreement on a common state or value among multiple nodes despite the failure of some nodes is known as distributed consensus.

Consensus mechanism

A consensus mechanism is a set of steps that are taken by most or all nodes in a blockchain to agree on a proposed state or value. For more than three decades, this concept has been researched by computer scientists in industry and academia. With the advent of blockchain and Bitcoin, consensus mechanisms have come into the limelight again and gained considerable popularity.

There are various requirements for a consensus mechanism. The following describes these requirements:

• Agreement: All honest nodes decide on the same value.
• Integrity: This is a requirement that no node can make the decision more than once in a single consensus cycle.
• Validity: The value agreed upon by all honest nodes must be the same as the initial value proposed by at least one honest node.
• Fault tolerant: The consensus algorithm should be able to run correctly in the presence of faulty or malicious nodes (Byzantine nodes).
• Termination: All honest nodes terminate the execution of the consensus process and eventually reach a decision.

Having seen these general requirements, we'll now look at the different types of consensus mechanisms.

Types of consensus mechanisms

All consensus mechanisms are developed to deal with faults in a distributed system and to allow distributed systems to reach a final state of agreement. There are two general categories of consensus mechanisms. These categories deal with all types of faults (fail-stop types or arbitrary). These common types of consensus mechanisms are as follows:

• Proof-based consensus mechanisms: This arrangement requires nodes to compete in a leader-election lottery, and the node that wins proposes the final value. The algorithm works on the principle of providing proof of some work and the possession of some authority or tokens to win the right of proposing the next block. For example, the PoW mechanism used in Bitcoin falls into this category, where a miner who solves the computational puzzle as proof of computational effort expended wins the right to add the next block to the blockchain.
• Traditional fault tolerance-based: With no compute-intensive operations, such as partial hash inversion (as in Bitcoin PoW), this type of consensus mechanism relies on a simple scheme of nodes that publish and verify signed messages in a number of phases. Eventually, when a certain number of messages are received over a period of rounds (phases), then an agreement is reached.

To achieve fault tolerance, replication is used. This is a standard and widely used method to achieve fault tolerance. In general, there are two types of faults that a node can experience:

• Fail-stop faults: This type of fault occurs when a node merely has crashed. Fail-stop faults are the easier ones to deal with of the two fault types. Paxos or the RAFT protocol, introduced earlier in this chapter, are normally used to deal with this type of fault. These faults are simpler to deal with.
• Byzantine faults: The second type of fault is one where the faulty node exhibits malicious or inconsistent behavior arbitrarily. This type is difficult to handle since it can create confusion due to misleading information. This can be a result of an attack by adversaries, a software bug, or data corruption. SMR protocols such as Practical Byzantine Fault Tolerance (PBFT) was developed to address this second type of faults.

Many other implementations of consensus protocols have been proposed in traditional distributed systems. Paxos is the most famous of these protocols. It was introduced by Leslie Lamport in 1989. With Paxos, nodes are assigned various roles such as Proposer, Acceptor, and Learner. Nodes or processes are named replicas, and consensus is achieved in the presence of faulty nodes by an agreement among a majority of nodes.

An alternative to Paxos is RAFT, which works by assigning any of three states; that is, Follower, Candidate, or Leader to the nodes. A Leader is elected after a Candidate node receives enough votes, and all changes then have to go through the Leader. The Leader commits the proposed changes once replication on the majority of the follower nodes is completed.

We will briefly touch on some aspects of consensus in blockchain now, but more detail on the theory of consensus mechanisms from a distributed system point of view and also from the blockchain perspective will be presented in Chapter 5, Consensus Algorithms.

Consensus in blockchain

Consensus is a distributed computing concept that has been used in blockchain in order to provide a means of agreeing to a single version of the truth by all peers on the blockchain network. This concept was previously discussed in the distributed systems section of this chapter. In this section, we will address consensus in the context of blockchain technology. Some concepts presented following are still relevant to the distributed systems theory, but they are explained from a blockchain perspective.

Roughly, the following describes the two main categories of consensus mechanisms:

1. Proof-based, leader-election lottery-based, or the Nakamoto consensus whereby a leader is elected at random (using an algorithm) and proposes a final value. This category is also referred to as the fully decentralized or permissionless type of consensus mechanism. This type is well used in the Bitcoin and Ethereum blockchain in the form of a PoW mechanism.
2. Byzantine fault tolerance (BFT)-based is a more traditional approach based on rounds of votes. This class of consensus is also known as the consortium or permissioned type of consensus mechanism.

BFT-based consensus mechanisms perform well when there are a limited number of nodes, but they do not scale well. On the other hand, leader-election lottery-based (PoW) consensus mechanisms scale very well but perform very slowly. As there is significant research being conducted in this area, new types of consensus mechanisms are also emerging, such as the semi-decentralized type, which is used in the Ripple network. The Ripple network will be discussed in detail in this book's online content pages, here: https://static.packt-cdn.com/downloads/Altcoins_Ethereum_Projects_and_More_Bonus_Content.pdf. There are also various other proposals out there, which are trying to find the right balance between scalability and performance. Some notable projects include PBFT, Hybrid BFT, BlockDAG, Tezos, Stellar, and GHOST.

The consensus algorithms available today, or that are being researched in the context of blockchain, are presented as follows. The following is not an exhaustive list, but it includes all notable algorithms:

• Proof of Work (PoW): This type of consensus mechanism relies on proof that adequate computational resources have been spent before proposing a value for acceptance by the network. This scheme is used in Bitcoin, Litecoin, and other cryptocurrency blockchains. Currently, it is the only algorithm that has proven to be astonishingly successful against any collusion attacks on a blockchain network, such as the Sybil attack. The Sybil attack will be discussed in Chapter 6, Introducing Bitcoin.
• Proof of Stake (PoS): This algorithm works on the idea that a node or user has an adequate stake in the system; that is, the user has invested enough in the system so that any malicious attempt by that user would outweigh the benefits of performing such an attack on the network. This idea was first introduced by Peercoin, and it is going to be used in the Ethereum blockchain version called Serenity. Another important concept in PoS is coin age, which is a criterion derived from the amount of time and number of coins that have not been spent. In this model, the chances of proposing and signing the next block increase with the coin age.
• Delegated Proof of Stake (DPoS): This is an innovation over standard PoS, whereby each node that has a stake in the system can delegate the validation of a transaction to other nodes by voting. It is used in the BitShares blockchain.
• Proof of Elapsed Time (PoET): Introduced by Intel in 2016, PoET uses a Trusted Execution Environment (TEE) to provide randomness and safety in the leader-election process via a guaranteed wait time. It requires the Intel SGX (Software Guard Extensions) processor to provide the security guarantee for it to be secure. This concept is discussed in more detail in Chapter 17, Hyperledger, in the context of the Intel Sawtooth Lake blockchain project.
• Proof of Deposit (PoD): In this case, nodes that wish to participate in the network have to make a security deposit before they can mine and propose blocks. This mechanism is used in the Tendermint blockchain.
• Proof of Importance (PoI): This idea is significant and different from PoS. PoI not only relies on how large a stake a user has in the system, but it also monitors the usage and movement of tokens by the user in order to establish a level of trust and importance. It is used in the NEM coin blockchain. More information about this coin is available from NEM's website (https://nem.io).
• Federated consensus or federated Byzantine consensus: This mechanism is used in the stellar consensus protocol. Nodes in this protocol retain a group of publicly-trusted peers and propagate only those transactions that have been validated by the majority of trusted nodes.
• Reputation-based mechanisms: As the name suggests, a leader is elected by the reputation it has built over time on the network. It is based on the votes of other members.
• Practical Byzantine Fault Tolerance (PBFT): This mechanism achieves SMR, which provides tolerance against Byzantine nodes. Various other protocols, including PBFT, PAXOS, RAFT, and Federated Byzantine Agreement (FBA), are also being used or have been proposed for use in many different implementations of distributed systems and blockchains.
• Proof of Activity (PoA): This scheme is a combination of PoS and PoW, which ensures that a stakeholder is selected in a pseudorandom but uniform fashion. This is a comparatively more energy-efficient mechanism as compared to PoW. It utilizes a new concept called "Follow the Satoshi." In this scheme, PoW and PoS are combined together to achieve consensus and a good level of security. This scheme is more energy efficient as PoW is used only in the first stage of the mechanism; after the first stage, it switches to PoS, which consumes negligible energy. We will discuss these ideas further in Chapter 7, Bitcoin Network and Payments, where protocols are reviewed in the context of advanced Bitcoin protocols.
• Proof of Capacity (PoC): This scheme uses hard disk space as a resource to mine the blocks. This is different from PoW, where CPU resources are used. In PoC, hard disk space is utilized for mining and, as such, is also known as hard drive mining. This concept was first introduced in the BurstCoin cryptocurrency.
• Proof of Storage: This scheme allows for the outsourcing of storage capacity. This scheme is based on the concept that a particular piece of data is probably stored by a node, which serves as a means to participate in the consensus mechanism. Several variations of this scheme have been proposed, such as Proof of Replication, Proof of Data Possession, Proof of Space, and Proof of Space-time.
• Proof of Authority (PoA): This scheme utilizes the identity of the participants called validators as a stake on the network. Validators are known and have the authority to propose new blocks. Validators propose the new blocks and validate them as per blockchain rules. Commonly used PoA algorithms are Clique and Aura.

Some prominent protocols in blockchain will be discussed in detail in Chapter 5, Consensus Algorithms. In this chapter, a light introduction is presented only.

Remember, earlier in this chapter we said that distributed systems are difficult to build and a distributed system cannot have consistency, availability, and partition tolerance at the same time. This is a proven result; however, in blockchain, it seems that this theorem is somehow violated. In the next section, we will introduce the CAP theorem formally and discuss why blockchain appears to achieve all three properties simultaneously.