“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:
- Energy Efficiency – With PoS consensus you don’t need to use large amount of electricity in order to secure blockchain.
- 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.
- 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:
- All loyal generals decide upon the same plan of action.
- 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.
- 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.
- 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