"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 (or soccer as it is known in other countries) in a park with my friends. We didn't have a referee (a centralised authority) to officiate our games or tell us how many points were scored. We all knew what the score was at any given time, and if we wanted to change it, we had to have a very good reason to persuade the other players. Also, we were all familiar with the game's rules to some extent, and all of the players agreed to follow them. If a foul was called, we would quickly decide whether to call the foul or let the game continue, achieving constant consensus among all of us. These two are examples of how a consensus problem is solved in our daily 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. On 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. However for this to be successful, consensus algorithms need to address Byzantine Fault Tolerance (BFT), and thus a solution to the Byzantine Generals’ problem for blockchains is needed (I will explain BFT later on).
Different consensus algorithms have been proposed/developed to address Byzantine Generals' problem and a few of them are shown in the diagram below. 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) 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. This also means the network is safe as long as more than 50% of the work being put in by the miners is honest otherwise you could potentially have a 51% attack situation. This is one of the reason why PoW is used since it requires 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) 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.
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.
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.
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. Also 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.
These 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): 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.
The subsequent posts in the series will look into Blockchain use cases, then Testing, and finally AWS Blockchain.
Thanks for reading!
If you enjoyed this article feel free to share on social media 🙂
Github repo: hseera