Types of Blockchain Consensus Algorithms

“A fundamental problem in distributed computing and multi-agent systems is to achieve overall system reliability in the presence of a number of faulty processes. This often requires processes to agree on some data value that is needed during computation”.

 

For safety reason and others, modern day cars come with various sensors, just look at Tesla which has 12 ultrasonic sensors providing it with 360 degree vision. Depending on the precision, there might be some variation in reading from these sensors and Auto pilot need to agree on when to apply brakes.

 

Similarly as a child, I used to play football (Soccer as they call in other countries) with my friends in a park. We didn’t have referee (centralized authority) to officiate our games or tell us what the score was. Each of us knew what the score was at any one time and we better have a very good reason to convince other players, if we wanted to change the score. Also we all knew the rules of the game to some extend but never the less we had some rules and all the players agreed to abide by them. If a foul was made, we would quickly make a decision to either act upon the foul or let the game continue and thereby constantly achieving a consensus between all of us. These two are example of a consensus problem being solved in our every day lives.

 

Blockchain is a new way of organizing data, it stores every change that has occurred and finally it arranges data in blocks. Blockchain only provides a very flexible and secure way of arranging data. Own it’s own it does not provide any sort of decentralization. Once you combine blockchain with a consensus algorithm, it then allows you for a successful operation of a fully or partially decentralized system. The Consensus algorithms address Byzantine Fault Tolerance (BFT), a solution to the Byzantine Generals’ problem for blockchains (I will explain BFT later on) in order to have a decentralized system.

 

The diagram below shows different consensus algorithms that have been implemented with blockchain. In this article I will only explain the most common consensus algorithms as it is a book on it’s own, if I have to explain all of them plus others not in the diagram.

Proof of Work (PoW)

Proof of Work (PoW) is currently the most common, one of the most robust consensus algorithm for blockchain technology and it is also the first blockchain consensus algorithm. It was devised by Satoshi Nakamoto for the use in the Bitcoin blockchain.

 

In PoW, Miners have to solve mathematically complex puzzles to produce block of transactions and get rewarded. After solving the puzzle, the result is then forwarded to other miners and verified by them before block is accepted on to the blockchain.

 

Mining requires highly specialized computer hardware to run the complicated algorithms. These specialized computers consume large amount of power. PoW runs on the concept of the “longest chain.” If most of the the miners are working on the same chain, that one will grow fastest and longest and therefore will be trustworth. The network is safe as long as more than 50% of the work being put in by the miners is honest. PoW addresses this by requiring a lot of computational power and lot of time to solve these puzzles, which in turn means high cost to run the infrastructure.

 

The 51% attack in a PoW blockchain is a situation whereby an organization is able to control majority of the network mining power. This will allow them to monopolize generation of new blocks and receiving rewards while preventing others from completing blocks. There is an app called crypto51.app, that tracks the cost of performing hourly 51 percent attacks on PoW based cryptocurrencies.

Proof of Stake (PoS)

Proof of Stake (PoS) is another category of consensus algorithm whereby a user can mine or validate block transactions depending on the user’s wealth, also defined as ‘stake’. Forgers is name given to the users who validate and create new blocks in the system. In PoW blocks are mined but in PoS, blocks are said to be ‘forged’ or ‘minted’.

 

From an algorithmic perspective, there are mainly two major types of PoS: chain-based PoS and BFT- style PoS. In chain-based PoS, the creator of a new block is chosen in a pseudo-random way where as in BFT-styple PoS validators are randomly assigned the right to propose block, however consensus is formed through a multi-round process where ever validator votes for a chain.

 

Some of the cryptocurrencies such as Ethereum are moving away from PoW to PoS because of the following reasons:

  1. Energy Efficiency – With PoS consensus you don’t need to use large amount of electricity in order to secure blockchain.
  2.  Security – Attackers must put their wealth on the line in order to attempt a 51% attack. If the attacker is the majority share holder on the network, then it will not be in his best interest to attach the network.
  3. Decentralization – In PoW network system, large mining-pools can work collectively to control over 51% of the network, leading to a very real threat of centralization. The reward in PoW system tends to go up exponentially compared to linear increase in reward for PoS based systems.

 

There is also a theoretical problem that may be encountered in PoS system called the “NOTHING AT STAKE” problem. This problem could happen if blockchain is forked. Basically validators don’t lose anything from behaving badly, you lose nothing by signing each and every fork, your incentive is to sign everywhere because it doesn’t cost you anything. Where as it will cost the validator a huge computational power (electricity cost), if they ever try to do that in PoW network.

Delegated Proof of stake (DPoS)

The Delegated Proof of Stake is the brain-child of Daniel Larimer, and is actually very different from PoS. DPoS, leverages the power of the stakeholders by voting for delegates who on their behalf validate transactions for the next block and in turn receive the reward. There are generally between 21–100 elected delegates in a DPoS system. If delegate does not behave or perform well, the stakeholders can vote them out and replace them with a better one. Therefore the major difference between PoS and DPoS is that PoS is a direct democratic and DPoS is representative democratic.

Proof of Authority (PoA)

In Proof of Authority consensus algorithm, it assigns a set of trusted nodes to process transactions and build new blocks. These new blocks need to be signed by the majority of the authorities. POA has a high throughput and is mainly optimized for private network.

Byzantine Fault Tolerance (BFT)

In distributed computing there is a classic problem of a system that must tolerate failure of one or more of its components and is usually explained with Byzantine generals. Famously described in 1982 by Lamport, Shostak and Pease, a city is surrounded by Byzantine army which is split into groups and each group is commanded by a general. Generals must decide in unison whether to attack or not. There is an added complexity that there might be one or more generals who are traitors and might try to prevent loyal generals from reaching an agreement of whether to attack or not. Generals are separated by distance and can only communicate via a messenger. Therefore generals need to have an algorithm that guarantees:

  1. All loyal generals decide upon the same plan of action.
  2. A small number of traitors can not cause the loyal generals to adopt a bad plan.

The generals are equivalent of nodes in a decentralized blockchain network, communicating and receiving information to the others via the blockchain network but unable to always trust it at a face value as they don’t know if any of those nodes have been compromised.

  1. Practical Byzantine Fault Tolerance (PBFT): The nodes collecting transactions, select a leader for their next block. Leader orders the transactions and broadcasts the list. Each node validates the transactions and broadcasts the calculated hash of the new block and. Once 2/3 of the nodes have the same hash, the new block is published. Currently in use by Zilliqa and HyperLedger.
  2. Federated Byzantine Agreement (FBA):FBA is another class of solutions to the Byzantine generals problem used by currencies like Stellar and Ripple. In FBA systems, each node does not have to be known and verified ahead of time, membership is open and control is decentralized. Nodes can choose whom they thrust and system wide quorums emerge from decisions made by individual nodes

Beginner’s Guide to Blockchain Technology – Part II

This is part II of the series and it will focus on concept called hashing.  I will use same metaphor as previous article to explain hashing. If we go back to our example of train, coupler is a mechanism used to connect carriages and engine of the train, as shown in the image below.

 

The coupler come in different shapes and sizes.Buffer & chain, Link & pin and Bell-and-hook are few example of couplers. Just like coupler for train, similar concept is used in Blockchain to connect blocks. The Blocks in Blockchain are linked to its immediate predecessor using hash. The first block in the Blockchain is called “Genesis” block or Block 0 and its link lies out in the system. The below diagram is a simplified version of how Bitcoin Blockchain looks like and generally Blockchains follow same pattern.

 

At this point you might be wondering, what is hashing and how is it useful in the whole Blockchain ecosystem. Worry not, I will try to explain it.

 

Hashing is a simply process of taking a variable length input and creating a fixed size output, which is sometimes also called as Digest. Just like different types of couplers for train, there are also different types of hash functions. Example are Murmur hash, CityHash, SHA256, xxHash and SHA-3.

 

Blockchain mainly uses cryptographic hash functions such as SHA256 and Keccak-256. Example of Blockchains using these functions are Bitcoin and Ethereum, respectively.

 

 

The main reasons for using cryptographic hash functions for Blockchain lies in its properties, which are:

  • Deterministic – each time you parse same input through the hash function, you will get same hash value.
  • Efficiency – for any given input, the hash function should be capable of returning the hash value quickly else the system is simply not efficient.
  • Pre-image resistance – given a hash value, it should be difficult to find its input value. It is not impossible to determine the original input from its hash function.
  • Collision resistance – two different inputs to a hash function cannot have same hash value.
  • Slight change to input – making a small change to the input will change the hash value completely. For example, just changing the first letter of the Iron Maiden song “The Trooper” to “the Trooper” using SHA256 hash function changes the hash value completely.

 

Input Digest
The Trooper DB934DFF3B19B23DD77EA52DDE8A0DBB8654F1902827CA8D6633D939B8B7C29A
the Trooper E414332ED44FB59942899C6AF443CC89CF392BD112964BAFA7E5C3E2CB4A3D39

 

Just to cap this article off, let’s say a malicious attacker changes a data in block 1 of the Blockchain. Because of the properties of cryptographic hash functions, any slight change made in block 1 will change the hash value stored in block 2 and this will result in changes in block 3 and so on and so forth. Therefore it will become very hard for the malicious attacker to compute an alternate chain from Block 1 which will catch-up with and overtake the one true chain.

 

More to follow.