Foundations of Distributed Ledger Technology Part 2: How to reach consensus
DLT Foundations
5th August 2024
Part 1 explains what DLT is: It is a way for computers to reach consensus. The way they reach consensus is through a consensus algorithm. The algorithm used depends on the ledger in question. This part describes the most common consensus algorithms today and briefly mentions some others.
DL Consensus algorithm
Disclaimer: Not all information that follows is researched in-depth. You can look up the research papers or my sources yourself if you want to know more. Some technical details stated here could therefore be incorrect. I just want to bring an general overview of the different kinds of algorithms that have been invented so far.
PoW = Proof-of-Work Algorithms
Bitcoin was invented in 2008 and it is the first DL ever invented. It uses a PoW based algorithm. The core concept is, figuratively speaking, a community of computers that add blocks containing transactions on top of each other, in the order they "raise their hand". That is where the concept of “Blockchain Technology” comes from, and is being used interchangeably with DLT. However, there are other ways of building a DL without using blocks. In this regard, the blockchain is the ledger itself. The computers involved in creating blocks and validating blocks are called Validators.
Problems starts occurring when two computers occasionally raises their hand at the same time. That will result in the chain splits into a fork, and we don't know the order of all transactions anymore.
To solve that problem, the validators will start adding blocks to the whichever chain they think is the longest. After a while, they will eventually come to an agreement on which is the longest chain and everyone will start adding to that chain, and destroy the other shorter chain. The transactions that was on the shorter chain will be put back into the pool of unconfirmed transactions. But wait! What if it forks faster than the validators have time to reach consensus? That will eventually crash the whole blockchain!
To mitigate that problem, all computers have to solve a math puzzle before they add their block on top of the chain, deliberately slowing the network down. The incentive to do so, is that every time some validator manage to solve a math puzzle, it gets rewarded with a few bitcoins, and is allowed to put their block on the chain. That is the concept behind bitcoing “mining”.
This system worked well for the first 10 years of Bitcoin. But now, only mining rigs have enough computing capacity to participate in the blockchain. As a result, Bitcoin transactions have become slow, expensive and consumes a lot of energy. And worse yet; it risks becoming centralized if mining rigs starts moving to a geographic region where they have cheaper energy. But at least it is secure, because the vast amount of energy needed to overcome the blockchain consensus, deters most of the bad actors.
Update: With the introduction of the lightning network, speed and transaction costs have been reduced dramatically for bitcoin transactions. However, the lightning network is a layer 2 blockchain solution, so the events in the lightning network still needs to be recorded to the underlying mainnet.
PoS = Proof-of-Stake Algorithm
In 2022 Ethereums blockchain switched to a Proof-of-Stake algorithm. This is one of the more popular consensus algorithms today.
A Proof-of-Stake (PoS) based blockchain uses staked cryptocurrency to secure itself. In Ethereums case, every validator node must have “locked up” a security deposit consisting of minimum 32 ETH on the network, in order to participate in the blockchain validation. The more collateral you stake, the more likely you will be validating new blocks, thus earn more rewards. Validator nodes vote on the authenticity of a new block of transactions, thus communally ensuring new blocks are valid before permanently adding them to the blockchain. By using the ETH as collateral, it naturally compels the nodes to behave properly, and helps to keep the network secure. Otherwise they might loose everything they staked (referred to as “Slashing”) if they vote for the wrong outcome.
For an attacker to take control of the consensus algorithm, allegedly he needs to be in control of at least 51% of the total amount of the native token. Although I’ve heard arguments that no consensus algorithm can handle if more than a third of the validators are malicious.
Note: PoS have also been referred to as an Economy based algorithm.
PoH = Proof of History Algorithm
Proof of History (PoH) can be seen as an improvement for other algorithms. One problem with PoW and PoS is that the validators are missing a common timestamp, because they could be synchronizing with different NTP server. That is why new blocks can risk being forked, and voting is needed to restore the chain. PoH integrates a common measurement of time called the Verifiable Delay Function (VDF). All validators set their timestamps relative to the VDF. That siginificantly reduces the risk of forking.
Solana runs PoH in conjunction with PoS algorithm.
PoA = Proof-of-Agreement
Proof-of-Agreement (PoA) is an improvement to the PoW algorithm. Invented by Stellar, PoA nodes are helping each other to solve the math puzzles by forming groups of validators called “Quorum Sets”. When one of the nodes solve a math puzzle, they first need to agree within the quorum set. Then each node within the quorum set needs to ask another quorum set to verify, before reaching consensus.
This speeds things up a bit. But to me it still looks like it has the same underlying issues with PoW algorithms; that they eventually won’t scale well, and risk forking.
Leader Based Algorithm
Another common problem with the previous examples are that they are relatively slow, because they have to wait for validation. A Bitcoin transaction can take hours to complete. Transactions over the Ethereum blockchain can take minutes. Leader based algorithms are intended to speed things up.
A leader based algorithm is the opposite of a voting algorithm (see appendix). Instead of having to vote every time a new transaction is being presented to the validators, they just send everything to the supreme leader that decides which order the blocks should be placed in. It might not be the fairest, but it’s very effective.
The followers send all their blocks with timestamps towards the leader. If there are multiple blocks with the same timestamp, the leader decides the order.
Two main problems with this approach:
The leader has to be a quite powerful machine to be able to handle all the incoming transactions.
The second is that it is vulnerable to DDoS attacks.
DDoS Attack
A Distributed Denial-of-Service attack is when a group of devices, which usually contains hacked cameras, printers, routers and other unprotected devices, all at the same time sends requests to one single machine, with the intent of overloading the system and make it crash. There is no bullet proof solution for this attack, and with the dawn of IoT = Internet of Things, the situation is most likely going to get worse, before it gets better.
With a blockchain that have one leader that manages most things, that makes it a single point of failure. When a botnet (a group of hacked devices) all target the leader. The leader will crash, and the network can’t reach consensus anymore.
Follow the leader
Of course, it is always possible to elect a new leader when the old one has fallen. But what if one participating validator is malicious? It could then steer the botnet to attack the next leader, then re-election occur, new leader again, and then that one gets targeted next. It won’t stop until the attack stops.
Note: Solana combines aspects of Proof-of-Stake, Proof-of-History and Leader Algorithms. It is one of the fastest and most cost-efficient blockchains in the market, but may not be the most stable.
Update: In Solanas defence: The leader changes after every time consensus about a transaction has been reached. It is because Solana is using a pBFT based consenus algorithm (Practical BFT). It is still possible to follow the leader, because the leader is changed on a round-robin basis, and future leaders can be calculated in advance. However, it requires a quite sophisticated and intense DDoS attack to overburden every upcoming leader, but in theory it could happen.
Virtual Voting Algorithm
It seemed like it was impossible to have an algorithm that was fast, inexpensive and secure at the same time; you always had do sacrifice at least one of them.
In 2016 Leemon Baird invented the Hashgraph consensus algorithm. It claims to have solved this problem.
The Swirlds Hashgraph Consensus algorithm combines the fast gossip protocol and the strong proven mathematical security from the old voting algorithms (see appendix), but with a twist: It skips the voting.
It is referred to as Virtual Voting because there is no vote ever cast. It is not necessary because all participating nodes already know what the outcome will be. This method is the only algorithm so far that is Asynchronous Byzantine Fault Tolerant. Asynchronous BFT means that there is no leader involved that can be targeted; all nodes/validators are equal.
Hashgraphs are also lightning fast because events get put on the ledger in almost the same instant they are received by the nodes. That’s because there are very few messages required to reach consensus.
Note: I’m going to write about Hashgraph and it’s virtual voting algorithm in more detail in it’s own post.
Hashgraph = Blockchain?
Is a hashgraph the same as a blockchain? People seem to use those words interchangeably and I don’t think the terms have been clearly defined yet. In my view, they are both distributed ledgers, but a hashgraph doesn’t deal with blocks of transactions. It sends the transactions, aka events, directly onto the ledger. In my opinion, calling it a blockchain is technically incorrect, but I could be wrong in this regard.
Hashgraph seems almost to good to be true. Unfortunately its biggest weakpoint is that is is currently a Permissioned ledger. A concept that will be covered in part 3. They will become permissionless in the future. But until then, it might cause some skepticism in the blockchain community.
“The public ledger is stored on the mainnet, a network comprised of consensus and mirror nodes. While currently permissioned and run by the Hedera Governing Council, consensus nodes will be permissionless – able to be run by anyone – in the future.”
Conclusion
There is still a lot more to say about DLs, and there are probably many more variations of the above algorithms that I’m unaware of at this time. But I would never finish this post if I would go through each one of them in detail, and this post is long enough. We truly live in the time of the browser war of blockchain technologies right now. And It’s going to be interesting to see if Bitcoin eventually will be Netscaped.
Part 3 will talk more about different components and use-cases for Blockchains, aka Distributed Ledgers.
Appendix
Special Mention
Thank you Mike Maloney for a very simple and comprehensive explanation of Bitcoin and Hashgraph. Your series, Hidden Secrets of Money, is a must watch for everyone. It was a great starting point for this research.
Thank you Sjur, for some last minute input on various DLs that were worth looking up.
Honorary mention: Voting Algorithms
The Paxos algorithm, also called Part-Time Parliament, was invented by Leslie Lamport in 1989. Computers are voting on “Yes” and “No” questions regarding incoming requests. When a majority of computers have voted for one certain outcome, that is what the consensus will be.
It has some mechanisms to break a tie, for example a Paxos system can elect a leader to solve disputes. It is a very complex protocol, but you can read about some of the details in a simplified version here.
Although voting algorithms were quite complicated, they were mathematically proven to be BFT = Byzantine Fault Tolerant. In other words, they were very secure. But they were very slow and didn't scale well, so they were never implemented for any DL.
Some other consensus mechanisms out there
Here is
Sources
Paxos Algorithm
https://medium.com/distributed-knowledge/paxos-consensus-for-beginners-1b8519d3360fHedera on Youtube: CESC2017 - Leemon Baird - Hashgraph Security and Attack Resilience
Etheruem PoS:
https://www.ledger.com/academy/ethereum-proof-of-stake-pos-explainedSolana:
Investopedia on Solana: https://www.investopedia.com/solana-5210472
Blockchain101 on Solana: https://101blockchains.com/proof-of-history/Stellar’s Consensus Protocol:
https://stellar.org/learn/stellar-consensus-protocol