Blockchain - Consensus Algorithms

Lesson: 7
Topic: Blockchain
Author: Ashley Rosilier

The fundamental trust mechanism in blockchain is the consensus algorithm. This defines the process by which data is validated and agreed upon by the majority of nodes in the system. In a permissionless system, using a consensus algorithm allows separate, anonymous nodes who don’t know or trust eachother to be assured that only good data is being added to the shared, distributed ledger. Consensus is slightly different in a permissioned system, where there is an established level of trust between known entities.

Proof of Work (PoW)

Bitcoin introduced the first consensus alogirthm used for permissionless blockchain: Proof of Work. The idea behind this mechanism is that notes can prove themslves as trustworthy by contributing a large amount of compute power to the system.

In PoW, a mathematical puzzle is used to prove the validity of the data. The chosen puzzle typically has these characteristics:

• Computationally intensive - this has the effect of both slowing down the creation of new blocks as well as deterring rogue actors from inserting bad data into the system
• Easily verifiable - while the creation of new blocks should be costly, the validation of the block should be efficient so that new data can quickly be validated and propogated throughout the blockchain

The hash problem described a previous lesson meets both of these two characteristics. Moreover, the protocol is able to increase or decrease the difficulty of the PoW puzzle by adjusting the target value for the final hash. This is done in order to adjust or nodes (and therefore computational power) being added to or removed from the system and maintain a consistent pace of block creation and validation.

Network nodes, called “miners,” will compete against each other to see who can solve the puzzle first, which is referred to as “mining.” Once a miner is able to solve the puzzle by generating the target hash, it is rewarded with currency and then broadcasts the block to all other nodes in the network. The peer nodes then validate the block and add it to their own copies of the distributed ledger.

The figure below from [11] illustrates the process of the PoW consensus mechanism.

It is possible for two nodes to solve the puzzle at exactly the same time and thereby broadcast two valid blocks simultaneously. Each blockchain system has its own protocol for resolving this conflict, and one of the blocks will emerge as the winner with the competing block becoming orphaned.

PoW systems do have some drawbacks. First is the fact that the mining process is slow and expensive in terms of energy and carbon footprint. Some miners have grouped together to form mining pools in order to increase hashing power and have a higher chance of winning the mining reward. The effect of these pools is that the consensus process becomes less decentralized and it becomes more feasible that a single pool could gain control of 51% percent of the network, opening the door to fraudulent transactions.

Proof of Stake (PoS)

Proof of Stake consensus was developed to provide an alternative to PoW, which is by design extremely inefficient and consumes a large amount of energy. In PoS systems, nodes prove trustworthiness by putting up “stake” in the form of currency, similar to a security deposit, with the assumpion being that dishonest nodes will not put their own currency at risk. There is no longer a need for huge computing power since there is no race to solve the hashing puzzle.

For consensus in PoS systems, a node is chosen to be the “validator” based on a pseudorandom algorithm that incorporates each node’s overall stake in the system as one factor. The validator then has the opportuniy to “forge” or “mint” the next block by validating that all of the contained transactions are valid. After this validation, the block is signed and broadcasted to all other nodes on the network and the validator receives a currency reward. If the validator is found to forge a block with fraudulent data, however, it is penalized by losing the currency that was put up as stake. As long as the amount of stake is higher than the potential transaction fee rewards, nodes can be trusted in a PoS system.

The primary advantage for PoS is that block creation and validations is much faster and less energy-expensive than in PoW. Of course there are drawbacks as well. One potential problem is that the validator selection can favor only the richest nodes, causing the system to become less decentralized, so various algorithms have been proposed to deal with that issue. In addition, PoS does not have as long of a track record as PoW ,so it has not yet been proven to be as effective at securing the blockchain.

A related, emerging consensus algorithm is Delegated Proof of Stake (DPoS), which is essentially a democratic version of PoS. In this case nodes elect a fixed number of delegates, also known as “witnesses,” to perform block validation. The number of votes allocated to each node is based on its stake in the overall system. Because the number of validators is much smaller, this type of system operates more quickly. Dishonest validators are voted out and no longer participate in validation.

Practical Byzantine Fault Tolerance (PBFT)

The need for a consensus algorithms is somewhat different in permissioned systems because only a limited number of nodes carry a complete copy of the block chain. Consensus is not used in order to establish trust between the nodes, but simply to validate and propogate new blocks. The Practical Byzantine Fault Tolerance (PBFT) algorithm is designed for permissioned systems but can handle byzantine faults – that is the system can recover even if some portion of nodes are either dishonest or malfunctioning.

In PBFT, there are multiple rounds of voting where the nodes in the system reach consensus about adding a new block to the chain. One node is selected as the leader to prepare and broadcast the block to the network. All other peer nodes calculate a block hash and broadcast the result. Each node then observes the hashes it receives from peer nodes, and if 2/3 are in agreement, the candidate block is added to its copy of the blockchain. Using this type of algorithm, a system of n nodes can tolerate f failing nodes as long as n > (3f + 1).

The PBFT algoirthm has high throughput and low latency, however the need to repeatedly broadcast blocks and votes to all peers is costly and limits the scalability of the system.

Crash Fault Tolerance (CFT)

Whereas Byzantine Fault Tolerant systems can robustly recover from both faulty and dishonest nodes, a more simplistic type of system ensures only Crash Fault Tolerance. A CFT system can recover if one of the nodes stops working, but does not protect agaainst malicious behavior. This level of fault tolerance might be completely adequate in a permissioned blockchain network where all nodes are fully trusted. In this case, the consensus algorithm used to propogate blocks onto the chain can be vastly simpler with higher throughput and performance.

Other

The previous sections reviewed some of the most common approaches to consensus algorithms for distributed ledgers, but there are many other algorithms under research and development today. Some of these are Proof of Activity, Proof of Burn, Proof of Elapsed Time, Proof of Luck, Proof of Capacity and Proof of Service.

References

[1] Honar Pajooh H, Rashid M, Alam F, Demidenko S. Hyperledger Fabric Blockchain for Securing the Edge Internet of Things. Sensors (Basel, Switzerland). 2021 Jan;21(2). DOI: 10.3390/s21020359.

[6] M. S. Ali, M. Vecchio, M. Pincheira, K. Dolui, F. Antonelli and M. H. Rehmani, “Applications of Blockchains in the Internet of Things: A Comprehensive Survey,” in IEEE Communications Surveys & Tutorials, vol. 21, no. 2, pp. 1676-1717, Secondquarter 2019, doi: 10.1109/COMST.2018.2886932.

[11] Li, X.; Jiang, P.; Chen, T.; Luo, X.; Wen, Q. A survey on the security of blockchain systems. Future Gener. Comput. Syst. 2020, 107, 841–853. https://doi.org/10.1016/j.future.2017.08.020

[12] Zheng, Z.; Xie, S.; Dai, H.N.; Chen, X.; Wang, H. Blockchain challenges and opportunities: A survey. Int. J. Web Grid Serv. 2018, 14, 352–375. https://doi.org/10.1504/IJWGS.2018.095647

[13] C. Cachin and M. Vukolić, “Blockchain consensus protocols in the wild (keynote talk)”, Proc. LIPIcs-Leibniz Int. Proc. Informat., vol. 91, 2017.