Consensus Algorithms: A Comprehensive View
As we know, the Blockchain is a ledger of transactions shared between participants of a network. There’s no central authority to validate transactions and tell which ones are valid and which ones aren’t. So, how do we ensure the participants of the network are honest? How does everyone in the network agree on a single universal “truth” about the ledger they are updating?
Blockchain systems are not based on honesty or trust of the participants; they are trustless systems. The only way for Blockchain to ensure the security of the network is through setting rules to enforce each participant to do the right thing. The rules can include investing or staking money and time to make it impossible for the participant to even think about doing something malicious. These rules are called consensus rules. Their objective is to provide incentives to everyone, so they participate in the network most efficiently. This is part of the magic of Blockchain and trustless systems.
The Byzantine Generals Problem (BGP)
The Byzantine Generals Problem is a fictitious problem illustrating the difficulties faced by a network of individuals in reaching consensus.
The BGP is as follows:
The great Byzantine empire is trying to conquer a city which is resisting with force. The generals of the Byzantine empire surround the town, each with their own army. Because the defence of the city is so strong if only one of the generals and his army attacks, they will be defeated. And, all the other generals won’t stand a chance afterwards. They need all of the armies to fight together to win the battle.
The only way that the generals will win is to attack with all their armies at the same time. For this, they have to communicate, and they are doing it through messengers which are not reliable. If a general sends out a message to attack, the other generals might receive the order to attack or the message could get intercepted and they could receive a request to retreat. The problem of the generals is that they need to reach consensus on when to attack and need to do so relying on a trustless system of messengers. Sound familiar?
The consensus algorithms solve the problem derived from the BGP.
Byzantine Fault Tolerance
Byzantine Fault Tolerance (BFT) refers to a system that tolerates the class of failures that belong to the BGP. If we translate this to the context of the story, there exists a system which tolerates one or more of the generals being traitors, and even when receiving the right message to attack, they may retreat.
A consensus that tolerates this sort of fault is called a BFT consensus system. It can still work and perform as expected even when some of the parties are not following the consensus rules.
A BFT is one of the most challenging problems to deal with even outside of the context of blockchain. BFT has been needed in very high availability and in security systems where failure is a threat to human lives, such as aeroplane engine systems or nuclear power plants.
Why we Need a Consensus Algorithm
The concept of Blockchain technology is not new. We had distributed systems, cryptography and network communications way before Bitcoin appeared, but the “glue” that sticks everything together and makes it work amazingly well is the consensus algorithms.
Satoshi Nakamoto proposed rules enforcing all nodes of a distributed network to agree on a single truth with absolute certainty. It added elements of game theory to avoid unethical participants of the system adding false transactions and blocks, by providing the correct incentives and penalising dishonest participants.
Without a consensus algorithm in Blockchain, we couldn’t agree which transactions and blocks need adding to the blockchain.
A miner is a node of the network in charge of creating blocks and adding them to the blockchain. Every miner would add different blocks and transactions to the blockchain, making it a separate blockchain to the others. Each node would have a different blockchain with different transactions on their database. Hence it wouldn’t be a single truth.
Bitcoin’s Proof of Work
Proof of work (PoW) was the first blockchain consensus algorithm. Satoshi Nakamoto proposed it in the original Bitcoin whitepaper.
In a PoW blockchain, the miners are the ones that need to do the heavy load in the network.
In summary, what miners do in PoW is:
- Pick transactions to include in a block from the Mempool (the place all transactions wait for inclusion in blocks)
- Create a block candidate with the picked transactions and hash them (apply a “one way” cryptographic function to all transactions in block) to get the “Merkle root.”
- Pick the “block header” from the last block of the blockchain
- Spend a considerable amount of computational power trying to hash the previous block header and a random number called “nonce” to get a result that is less than a predefined number (target). This means the miner needs to try random “nonce” values every time until it finds a result that is less than the predefined target
- If the miner is the first in the network to find a “nonce”, it adds it to the block and transmits the block to all its peers
- Peers in the network can quickly validate that the nonce is correct. If it’s right, they add the block to their local copies of the blockchain extending the selected blockchain
- If more than one miner finds the nonce and starts spreading the block throughout the network, the block that has the longest chain added is the most trustworthy one, and the miners will pick that one
- The whole process starts again once the winning block has been spread out
The main advantage of this consensus algorithm is that we know it works. Bitcoin has been around for nearly ten years and has never had an issue regarding consensus.
The Bitcoin network has continuously been under attack and is proven to be reliable. Nevertheless, it’s starting to be considered a legacy technology because of the amount of electricity it needs, and now other more “efficient” alternatives exist.
There are a few risks on a PoW blockchain, and the 51% attack is one of the most important to consider. A 51% means that if a miner or group of miners have more than 50% of the hashing power of the network (more computational power than the rest of all the miners), it can potentially re-write the blockchain, meaning they could double-spend transactions already settled in the blockchain.
Let’s use an example to illustrate it better:
Sarah is a miner of the Bitcoin blockchain, and for some reason, she was able to get 51% of the computational power of the network. Now she can send a transaction “X” to the network. This transaction is validated and added to the block number 100, for example. After block 100, two more blocks are added to the network, so we are on block 102.
At the same time, Sarah wants to double-spend the transaction “X”, meaning she wants to send the same amount of BTC to another address. She will need to go back to block 99, create another block with transaction “X” and send it to another address. Then, find the PoW “nonce” for that block, add it to the blockchain, and find the PoW “nonce” for the following two blocks, add them and then create another block to extend the block 102 to have the longest chain. Sarah needs to do this before any other miner continues to block 102, so she will need to mine a minimum of 4 blocks in less than 10 minutes (average block time creation). All of this effort to double-spend one transaction.
The amount of power (computational and electrical) for this to be accomplished makes it a complete waste of time. We also need to consider the bigger and stronger the network is, the more competitiveness between miners. This raises the difficulty level of the PoW algorithm, meaning it’s more challenging to attack with such magnitude. Therefore, it’s highly unlikely that in a network such as Bitcoin, this attack could ever be accomplished. Although it’s worth mentioning that in smaller systems, with fewer participants and less hashing power overall, this sort of attack is possible.
Ethereum’s Consensus Algorithms
Ethereum’s current consensus algorithm is called Ethash, and it’s a PoW algorithm. Ethash was initially designed to avoid centralisation.
A lot of miners in PoW use ASIC hardware (Application Specific Integrated Circuits) to gain more power and advantage over standard GPU (graphic processing unit). This leads to a more centralised network with only a few miners having enough resources to invest in ASIC hardware. Therefore, they control the majority of the hashing power.
The Ethash maths problems were explicitly designed to be very hard to resolve with ASIC (ASIC resistant), meaning that it would potentially be fairer for miners with fewer resources as it would not make a huge difference to mine with either ASIC hardware or GPU.
Another important aspect is that Ethereum always expressed its plans to move to a Proof of Stake (PoS) algorithm, making it even harder to invest in specific mining hardware that no longer will be suitable once the consensus rules change. Unless, of course, other coins exist for ASICs to mine with Ethash. In recent years, we saw an increase in ASIC hardware for Ethash as Ethereum Classic doesn’t have plans to move to PoS and more altcoins are using Ethash.
Casper: Proof of Stake
Casper is the proposed name for Ethereum’s new PoS consensus algorithm. At the time of writing, it’s still in development with deployment planned in the first quarter of 2020. Read more about Ethereum plans here.
As mentioned in a previous blog about PoS consensus, anyone in the network holding a specific amount of the network currency (in this case, ETH) can become a validator (miner). The way it works is the validators take turns proposing and voting on the next valid block. Each validator vote has a “weight” that depends on the size of their deposit (stake). If a validator acts in an unethical way and proposes a block that includes double-spending, for example, and the majority of validators reject this block, the unethical validator loses his or her stake. Vice versa is also true; validators receive rewards of ETH if the other validators accept the block they propose. So there are negative and positive incentives ensuring validators do the right thing.
Nevertheless, some of the critics of PoS say that it can lead to a centralised plutocracy as a few wealthy individuals would be able to gather the amount of Eth necessary to stake.
Another criticism is the so-called “Nothing at stake algorithm”, which is related to the fact that it’s in the best self-interest of all the miners to continue mining chains that have forked. This means that if two miners extend the blockchain with two different blocks at the same time, on different blocks, a fork occurs. Because there’s no real cost of mining, miners could mine both chains to avoid picking the incorrect chain on the fork and not profit from it. This can lead to a potential double-spend attack.
Other Consensus Algorithms
PoW and PoS are the most popular consensus algorithms. Why? Mainly because they're used, or planned to be used, on the blockchains that are currently most popular: Bitcoin and Ethereum. However, there are many variations of these consensus algorithms, and many others with quite different approaches.
Another popular consensus algorithm is the “Delegated Proof of Stake” (DPoS). A DPoS consensus has validators that are elected by token holders. For example, EOS is the most popular blockchain implementing DPoS. In EOS, there are 21 block validators elected by token holders. Validators are shuffled periodically and given an order to deliver their blocks. There are time slots in which validators need to publish a block. If validators continually fail to provide blocks or publish invalid blocks, stakers vote them out and replace them.
As you can see, consensus rules differ and have variations depending on the focus and requirements of the system. For example, speed, governability, security, decentralisation, anonymity, etc. Other less common consensus algorithms are; Proof of Authority (PoA), Proof of Weight (PoWeight), Byzantine Fault Tolerance (BFT), Proof of Reputation (PoR), and many more.
Consensus algorithms are part of the “magic” of blockchain technology. Without them, the blockchain networks would never reach a consensus of a single truth. Hence, never add the value they provide. Most importantly, PoW, besides all the criticism, is the most secure proven consensus algorithm working for more than ten years. PoS is very near, but yet to be proven.
The current state of most consensus algorithms is on ‘experimental mode’. As they're relatively new protocols, they need testing over time and in different circumstances. Nevertheless, the future for these protocols looks promising with the continued development of use cases for blockchain technology.
About the author:
A software developer by profession, and a traveller by heart, Juan Nuvreni has lived and travelled in many countries. Once he recognized the power of Bitcoin and Blockchain technology there was no way back. Driven by the potential to create a fairer world through technology, he is now on a mission to educate and spread the word of Blockchain.
The above references an opinion and is for informational purposes only. Do not take this as personalised financial advice or investment advice. The views expressed by the author do not necessarily represent the opinion of BitPrime.
Last updated: 13/12/2019