How to Fork Algorand's Pure Proof-of-Stake Blockchain

Honest money sometimes lies.

I’ve always been skeptical of Proof-of-Stake. There’s a reason why it took the Ethereum development team 7 years to transition to PoS – there are a ton of issues with Proof-of-Stake that Proof-of-Work doesn’t have. That’s why I was fascinated when Turing Award winner Silvio Micali released Algorand, a blockchain that purports to be un-forkable and secure, despite being based on a pure proof-of-stake consensus protocol. More specifically, Algorand claims to solve what they call the “blockchain trilemma”, a fundamental tradeoff that states that a blockchain can only have at most two of three desirable properties: decentralization, scalability, and security.

I’ve been following Algorand development on and off for the past couple of years, but recently had an excuse to dive deep into the math behind the chain, and realized that Algorand actually has a fundamental decentralization-security tradeoff. I’m not the first person to notice this – Yongge Wang published a 2020 paper identifying the same issue – but, to my knowledge, there doesn’t seem to be a simple, easy to understand explanation on what the tradeoff actually is.

The best part about it, though? There’s barely any math involved. The Algorand whitepapers feature some devilishly complex and genuinely incredible cryptographic work done by some of the most talented folks in the field. The work they’ve done is truly groundbreaking, and nothing I’m saying here is out of an attempt to paint the Algorand team in a negative light. However, by re-examining some foundational assumptions about honesty and trust, we can identify a tradeoff between decentralization and security that arises from more realistic – and pessimistic – assumptions about human behavior.

A Brief Background on Proof-of-Work

Proof-of-work blockchains maintain consensus by forcing miners to spend computational resources to add information (blocks) to the chain. If there are two copies of the chain that are different, the longer copy is automatically assumed to be the correct one, because a greater cost (in terms of compute, and energy) was spent to create it. If there are two copies of the chain with the same length, eventually one of them will outgrow the other and become the “true chain”. This is because miners don’t have the computational power to mine effectively on both chains at once.

Essentially, Proof-of-Work prevents forking by making it very expensive to add blocks to any forks other than the correct one. The downside, though, is that this consumes a lot of energy. Like, an entire country’s worth of energy. So people tried to come up with a better way: Proof of Stake.

Proof-of-work, Proof-of-stake, and Forking

On September 14th, 2021, the Proof-of-Stake blockchain Solana imploded. According to the Solana dev team, a large influx of transactions caused the chain to fork, with multiple chains being valid simultaneously. In a Proof-of-Work protocol, this would be just fine – like we just described, we’d just wait until one of the chains eventually outgrew all of the others, and declare that chain as our “true chain”. However, Solana, a Proof-of-Stake chain, couldn’t do that, and the devs had to pull the entire blockchain offline. This is a fundamental issue with Proof-of-Stake chains: forking a Proof-of-Stake chain can result in catastrophic failure of the system.

The idea behind PoS is simple: what if, instead of requiring an attacker to get a ton of computing power to take over the chain, we make it so an attacker has to get a ton of cryptocurrency to take over? Each user is able to propose and verify new blocks with a probability proportional to the amount of coins they own. This makes it economically difficult to attack the chain, but also doesn’t waste a mid-sized country's worth of electricity guessing numbers.

There’s a problem, though: forks. A fork in a PoS blockchain can result in catastrophic failure due to something called the “Nothing-at-Stake problem”. In the case of a fork, validators don’t have to pick one chain and stick to it, like they do in a Proof-of-Work system. Because there’s no cost to mining, validators can simply validate all of the conflicting copies of a fork, gaining block validation rewards on both forks; this can result in double-spending and other major issues that can render the chain totally unusable.

Conventionally, there are two ways to avoid the Nothing at Stake problem. Some PoS chains use a system of punishment, called Bonded Proof-of-Stake, where validators have to lock up some of their stake to get votes; if those validators get caught misbehaving, the stake that they bonded gets destroyed. This is how Etherium currently operates.

Another option is to have individual users delegate their votes to a handful of elected entities who are selected to create blocks. Delegates are generally major coin holders themselves, and thus wouldn’t want to destroy the value of their investment by allowing the chain to fork. However, this results in a level of centralization; in EOS, there are only 21 validators, and their identities are known.

Why Algorand “Never Forks”

Algorand claims to build a chain that never forks. More specifically, the forking probability is 10⁻¹⁸; in essence, if there was one block per second since the big bang, the chain would have probably forked once. This is a very clever way to stop the Nothing at Stake problem – if the chain can’t fork, there aren’t multiple competing chains for validators to validate, and the network remains stable.

(Heads up for any actual crytpographers: the explanation that’s about to follow is heavily simplified!)

Algorand builds this “unforkable chain” through a handful of clever cryptographic techniques. The basic idea is this:

• You randomly select one user to propose the next block, with the likelihood of selection based on ownership of the cryptocurrency, Algos.

• Then, you randomly select 1000 users to vote on validating the next block, again with the likelihood of selection based on Algo ownership.

• A majority of those users need to validate that block using an “ephemeral” secret cryptographic key, which they immediately delete after validation. This prevents two blocks from both being verified simultaneously.

• Repeat!

One of the things that made Algorand unique when it was first described was its ability to select 1000 users in a decentralized way. They use a technique called cryptographic sortition, which is a fancy way of describing a fully decentralized lottery. This is done through a cryptographic primitive called a verifiable random function. A VRF is essentially a (pseudo-)random number generator, but unlike conventional PRNGs, it also generates a proof that the random output was generated correctly. Thus, to be selected to participate in the voting committee, a user simply needs to get a lucky draw from their VRF. The fact that it’s verifiable means that users can’t lie and pretend that they got lucky; this gives us a secure, verifiable set of 1000 validators.

How does this result in a 10⁻¹⁸ forking probability? Well, Algorand has one major assumption built into it. For this to work, ⅔ of all Algos, the chain’s currency, needs to be controlled by “honest money”, parties who always obey the rules of the Algorand protocol without fail. This is vast oversimplification, but the basic idea is that it would be very, very unlikely for a user with less than ⅓ control of the money supply to not only be selected to propose a block, but also be a majority of the verification committee. Plus, there are some additional Byzantine Agreement protocols that make it even harder for an attacker to wrest control of the network, which bring the fork probability down to that impressively low value.

However, there’s a catch. That “honest money” assumption implies that honest parties always follow all of the rules of the protocol, without fail, no matter the personal gain they could get by cheating. As a person who’s interacted with other humans in my life, this simply isn’t an accurate assumption to make.

The Nothing-at-Stake problem, which is the very problem that a non-forking PoS blockchain is meant to solve, is due to opportunistic validators who validate multiple forks of the same chain. If all users in a conventional PoS model were “honest” by Algorand’s definition, they would never validate multiple forks, as the protocol says not to. To create a more realistic security analysis for Algorand, we need to revise this assumption.

Now, PoS proponents often make the argument that PoS validators are not incentivised to let the chain fork, as they are, by definition, holders of the currency that the chain represents. As such, here’s the realistic, if aggressive, security model I propose: any validator will actively search for and accept any bribe worth more than their stake in the network. How does that work? Well, that brings us to the Algorand Key Bazaar.

Assume there’s a secret website out there. It’s an online auction house, but it’s for people to sell their old ephemeral keys from participating in the Algorand verification process. “Oh, but those keys are ephemeral!”, you protest. Notably, however, Algorand has no way to enforce ephemeral key deletion. Under our security model, every single person on the validation committee instead offers their ephemeral key on our key exchange, listing it for a single cent more than their current stake in the Algorand blockchain. In this situation, how secure is the chain?

Let’s make another assumption: the chain is maximally decentralized. By that, I mean that every single user has a single Algo in their wallet, and none of them act in validator pools. An attacker could take control of the leader and verification pool for 1001 Algos – which, today, is worth about $200. Once the attacker gathers the “ephemeral” keys for all of those nodes, he or she could simply create an arbitrary new block, and fork the chain. At that point, both chains could very well continue separately, allowing the attacker to perform a double-spending attack and cash out before people realize the chain was compromised. 

So What?

So, should we all cash out of Algorand and go running back to PoW chains? Absolutely not! We made some of our own assumptions here, some of which currently aren’t true in practice. This attack is only feasible if Algorand was highly, highly decentralized, such that each user could be bribed for a fairly small sum. In practice, this couldn’t be further from the case. Algorand themselves own 48% of all Algos, with many, many more owned by investors and others with significant stake in the protocol itself. You would have to offer Algorand over 2 billion dollars to bribe them to part with their ephemeral keys in this model, and even then I doubt they would do it.

However, this does show a tradeoff between decentralization and security in Algorand. The more decentralized a network is, the cheaper and easier a bribery attack becomes. This means that Algorand doesn’t truly solve the blockchain trilemma; any instance of the Algorand blockchain can be either highly decentralized or highly secure.

The cost of mounting this attack can also be increased by increasing the size of the verification committee, but that results in the scalability of the network decreasing; doubling the size of the verification committee doubles the cost of a bribing attack, but it also doubles the number of messages required for the verification committee to come to an agreement. Again, the trilemma between security, decentralization, and scalability remains.

Ultimately, blockchain technologies aren’t magic, and there’s never a free lunch. While Algorand has a ton of amazing cryptographers and engineers, all that math can’t beat human nature: in the real world, people like being bribed.