Understanding Algorand — The blockchain which claims to solve the trilemma
Core concepts of the blockchain started by Silvio Micali, Turing Award Winner and MIT Professor
Blockchains today are far from perfect. Bitcoin was first released over 10 years ago, but it still suffers from low throughput and high transaction fees. Ethereum has been pushing updates for years now, but are barely doing better than Bitcoin in terms of scalability. This problem occurs due to what is known as the blockchain trilemma.
In this article, I will cover what the blockchain trilemma is, what Algorand is, and how they are attempting to solve it in a high level manner. This article assumes some basic knowledge of blockchains and terminology associated with them.
The Blockchain Trilemma… What is it?
A trilemma is a situation where there are three options, but at most only two of them are possible at the same time. In the case of the blockchain trilemma, the three options are:
If the trilemma holds, there are no good situations with just two options being true.
Without decentralization, we essentially remain in the same system that already exists today: exclusive and secretive. This includes projects which have a small number of ‘delegates’ — that’s not true decentralization.
Without security, transactions can disappear into thin air. You could’ve received money from somebody and given them a product or service, but a while later you realize you never actually got the money in the first place.
Lastly, without scalability, the network would be slow and prone to getting clogged (remember what happened with Ethereum when CryptoKitties boomed?). This is not favourable as we want to build a global instant network.
What is a blockchain supposed to do?
A blockchain essentially has two needs:
- Making it tamper proof and traceable. This is done by one-way hashing techniques and including the hash of the last block within the latest block. Pretty much all blockchains out there do this and are not very different in this case.
- Generating new blocks. How do you choose which block gets appended to the chain? This is the tricky one, different blockchains use different consensus algorithms to determine this.
Solving the trilemma comes down to developing a consensus algorithm which can do all those three things simultaneously.
Popular Consensus Algorithms and their Flaws
Proof of Work (PoW)
PoW is infamously known due to Satoshi Nakamoto using it as the consensus algorithm for Bitcoin. At the time of writing, Ethereum is also (still) using PoW. While the algorithm has proven to be somewhat reliable, as it’s been running Bitcoin for over 10 years now, it has a fair share of problems.
- Not Scalable: In PoW, the ‘miners’ are required to solve a very complex cryptographic puzzle on their machines. The first to do so in the world gets the right to append a new block to the chain. This process is expensive as solving the puzzle requires a lot of computational power and takes a lot of electricity. Everyone beside the winning miner essentially loses money as well because they just spent time trying to solve a puzzle but didn’t win.
- De facto centralized: While PoW itself is not a centralized consensus mechanism, due to how costly it is, over time Bitcoin mining has become de facto centralized. Mining in today’s world utilizes racks and racks of specialized hardware using tons of electricity. Mining on a personal computer or laptop is completely worthless, and probabilistically you’re almost guaranteed to lose money. With the huge amount of investment required to turn profits, Bitcoin’s blockchain is majorly controlled by only three mining pools.
- Vulnerable to 51% attack: If the major miners of a PoW chain collude, or a single malicious actor somehow is able to control 51% of the mining hashrate of the network, they can agree to ‘fake blocks’ and control the entire chain by themselves. It doesn’t matter if the other 49% doesn’t agree with their decisions, as the majority consensus holds true. This makes the de-facto centralization point very scary.
- Forks and slow finality: When 2 or more miners solve the puzzle close to each other, the chain branches because the network now sees multiple candidates for the next block due to latency in spreading this information. This branching is known as forking, and forks can exist for a while and even continue to elongate by addition of new blocks. Eventually though, all but one of the forks will disappear. This causes uncertainty and delay for transactions, as you can’t be fully sure that your transaction actually went through or not. For Bitcoin, people recommend waiting for 6 blocks to be sure your transaction is final, as the chance of it being on a fork chain after 6 blocks have been appended is extremely low. But, this can take about an hour, and that’s not good.
Delegated Proof of Stake (DPoS)
In DPoS, the community empowers a set of users called ‘delegates’ to choose the next block. This algorithm is used in EOS. This also has several criticisms and vulnerabilities:
- DPoS is essentially centralized straight off the bat. A fixed small number of delegates who choose which block gets appended next to the chain is nothing when you want the network to be running for millions of users. Relying on chosen delegates for a long time is very risky.
- Can be stalled. Since there’s only a limited number of nodes which do all the hard work, attackers can identify them and halt the network from functioning at all e.g. by DDoS’ing the delegate nodes.
Bonded Proof of Stake (BPoS)
BPoS allows users of the network, as many are willing, to put some money on the table in a ‘bond’ they cannot touch. This gives them some power on the network, and these users validate and add new blocks to the chain. The idea is that if they act maliciously, they lose their bonded money. This has a very clear flaws:
- The average user of the network doesn’t have enough disposable money to put in a bond. It is much easier for malicious actors to put huge amounts of money in their stake which would allow them to control the blockchain completely. They can afford to lose a few million dollars if the returns are in billions or trillions.
Algorand’s Pure Proof of Stake (PPoS)
Algorand’s solution to these problems is their PPoS algorithm. PPoS doesn’t require users to stake any money in a bond, just requires them to have it in the first place. This doesn’t try to keep the users honest through a fear of imposing fines, but rather it makes “cheating by a minority of the money impossible, and cheating by a majority of the money stupid”. This algorithm is secure when most of the money is in honest hands.
Implementing Pure Proof of Stake
At a high level, Algorand constructs a new block in two phases:
- In Phase 1, a single token is randomly selected, and the owner of that token is selected to propose the next block.
- In Phase 2, a few thousand tokens are selected randomly from all tokens in the network. The owners of these tokens are selected to form a phase 2 committee which then validate and approve the block proposed in phase 1. Since tokens are selected randomly and not owners, some members may be chosen k > 1 times and have k votes in the committee.
How is this secure?
The answer to this question is a somewhat philosophical one. The core assumption is that in any society, there is a minority of bad actors. Maybe 1%, maybe 2%. If one is in a particularly dangerous society, maybe even 10% or 20% . But, in no society would there be a majority of bad actors as the society wouldn’t exist otherwise.
Think of the Algorand network as a society. Let’s assume the worst case scenario and consider 20% of the tokens on the network belong to malicious actors. Then, 1/5 times, the token chosen for Phase 1 will be owned by a bad actor. Let’s say they tell some users about the block being X while they tell other users about the block being Y, trying to cause disagreement in the society.
The number of tokens on the Algorand network is a very big number, close to 2²⁵⁶ (It varies slightly depending on the total voting stake). The probability of a token being selected to vote on a block is ~2990/2²⁵⁶. Hence, the committee which votes on the blocks has size approximated by a Poisson distribution with mean 2990. The threshold for reaching consensus is 2267 votes. Since the adversary holds 20% of the stake, the expected number of votes going to bad actors are roughly 2990/5 = 598 (the actual number is based on a Poisson distribution), and the expected number of honest voters is roughly 2990 * (4/5) = 2239.
The adversary would win if they are able to get more than the threshold amount of votes for two different values, thereby partitioning the chain and causing disagreement on the network.
As an example, let us examine what happens in the average case where the number of honest votes are exactly the expectation 2239. For the adversary to win, they would need [(2 * 2267)-2239]/2 votes to win — or 1147.5 votes. Since number of votes are integers, they need ≥ 1148 votes to win. The expected value of the votes going to the adversary however, as described above, is 598. Calculating the probability of getting ≥ 1148 votes in a Poisson distribution with E(X) = 598 is roughly (5 / 10⁸⁷) which is very, very small. You can find the calculation here.
The most intriguing question of this algorithm though is yet to be answered. Who chooses this committee?
How users are selected to be part of the committee
If I told you, the committee is chosen by Algorand (the company) themselves, that would be a highly centralized solution and hold the trilemma.
If I told you, the users discuss among themselves until they decide who the members are, that’s a super slow system as how do you determine you trust someone else, and may never lead to a selection.
This is where the fun part comes in. The committee members choose themselves. But, not like “I choose myself for this round, and next round, and next round…”. To belong to the committee, the nodes run a cryptographically verifiable ‘lottery’ over all their accounts, and if any of their coins win the lottery, they are selected to be part of the committee. This lottery is run in isolation with no communication with other nodes on the network. Since it’s cryptographically verifiable, nobody can alter their chances to win the lottery either. No matter how much computation power you have, you cannot alter your chances of being selected.
When a user runs the lottery, there are two possible scenarios:
- None of their tokens win the lottery, in which case their opinion about the block is ignored.
- Some k ≥ 1 tokens win the lottery, in which case the user gets a ‘winning ticket’ (a short cryptographic proof) to prove they won the lottery. Then, they propagate this ticket along with their opinion about the block to the rest of the network.
Revisiting the Trilemma
Assume a powerful malicious adversary would like to corrupt the committee members and influence their votes about the next block. Let’s even assume they could do this if they knew who the committee members were.
That’s where the caveat comes in, they don’t know who the committee members are. Since the lottery is run in isolation, only the members alone know if they’re selected or not until the time they propagate their proof and opinion about the block to the rest of the network.
Once they do propagate their opinion, other nodes know who the committee members are, but at this point it’s too late to corrupt them. They’ve already said what they had to say, and their opinion is already being broadcasted to the network. There is no guarantee when they will be a committee member again. Thus, the malicious adversary can’t do anything now to silence them.
So essentially, Algorand is secure because firstly, the adversary doesn’t know who the committee members are. And when they do find out, it’s too late to corrupt them.
Additionally, since nobody knows who the committee members are initially, they cannot attack their nodes using methods like DDoS either.
It takes only a microsecond for any user to run the ‘lottery’, no matter how many tokens they have. Also, since all lotteries are run independently of each other, nodes don’t need to wait for other nodes to finish doing something first. This can happen concurrently across all nodes.
Once selected, the members propagate a single short message to the rest of the network. So no matter how many users are on the network, only a few thousand messages need to be propagated across the network. This is highly scalable.
There are not a few users deciding on what the next block will be. Nor is there a fixed committee which makes this decision every time. The committee is chosen randomly and securely, and doesn’t require much computational power at all. This allows everyone on the network to have a chance of being in the committee and voting on the next block.
Bonus: Essentially Non-Forkable
In Algorand, only one block at a time can have the required threshold of committee votes. Accordingly, all transactions are final as soon as they get added to a block. Once a block appears, you can count on it to be there forever and transactions are thus instantly final.