The Byzantine Generals Problem

Quick Byte:

The Byzantine Generals Problem describes the problem of keeping a decentralized and distributed network in sync and running without issues given an environment where communication can be imperfect. It is a crucial concept in Bitcoin as blockchain technology is, by its nature, a decentralized and distributed network.

The Byzantine Generals Allegory

Imagine that you are a general of the Byzantine Empire at the height of its power in 555 AD. You have been tasked by the Emperor with capturing a heavily fortified castle situated on a hill. The castle’s defenses are formidable, and your army alone is not enough to capture it. Thankfully, there are other Byzantine generals in the area who each lead their own armies. You do some quick calculations and conclude that the only way to overwhelm the castle’s defenses is if all the generals lead their armies to attack the castle simultaneously. However, if only one of the generals attacks too early, or too late, or perhaps not at all, the attack will fail.

To help coordinate this attack, you decide to send a letter to each of the other generals with detailed instructions on exactly when to attack and from which direction they should approach the castle from.

There is however, a small issue. The castle’s defenders have sent out ambush squads to try to intercept couriers sending letters between the generals. Even if a courier doesn’t get ambushed, there’s always the chance they could get lost, or the letter could fall into mud and become illegible, or some other issue can happen. To make sure the generals receive your letter, you include in your letter that the receiving general send you back a confirmation letter confirming that they received your letter.

You think about this plan for a moment and realize there is another problem. How would the general who sent the confirmation letter know for sure that you received the letter? For them to know for sure would require you to send them back a confirmation that you received their confirmation. But then the problem reverts back to the beginning, since you would have no way of knowing if they received your confirmation without them sending you back yet another confirmation. You think about this issue for a long time but could not come up with a solution.

Distributed Networks

The Byzantine Generals Problem describes the problem of keeping a decentralized and distributed network in sync and running without issues given an environment where communication can be imperfect. Imagine that instead of Byzantine Generals, the participants were nodes of a distributed network, and the messages sent back and forth between the “generals” were crucial data or code that a node needs to run. In a distributed network, where components may fail and there is imperfect information on whether a component has failed, this is called a Byzantine Fault. 

This concept is especially important to blockchains, since blockchains are a form of a distributed network. Due to the lack of a central authority, a decentralized blockchain requires a way to recover from a Byzantine Fault where a node or large group of nodes go down simultaneously, malfunction, or become out of sync with one another. All crypto projects must find a way to deal with the Byzantine Generals Problem. Bitcoin handles the Byzantine Generals Problem using a set of conditions known as Nakamoto Consensus.

Nakamoto Consensus

Named after the mysterious founder of Bitcoin, Satoshi Nakamoto, the keys to Nakamoto Consensus comes in 2 parts:

1. Proof of Work
2. Longest Chain Wins

Proof of Work is the method employed by Bitcoin to confirm blocks to the blockchain. In Proof of Work, participants who are trying to confirm the next block to the blockchain are required to find the answer (and also be the first one to do so) to a mathematical problem called a cryptographic hashing function. Finding the answer to this problem requires an immense number of calculations, which in turn necessitate a similarly large amount of electricity to be expended. It is called Proof of Work, because the computer (also known as a “miner”) who finds the answer to the cryptographic hashing function has demonstrated that they have done the extraordinarily large number of calculations, otherwise there would be no other way for them to get the answer. This solves the Byzantine Generals Problem as it gets the whole network to agree, in a decentralized way, which block is next. The next block is the block who has the Proof of Work solved. 

The second part to Nakamoto Consensus involves what to do if the nodes on the network get out of sync with each other. 

Pretend that you’re in Iceland, a country that is rather geographically isolated from the rest of the world, being located in the middle of the Atlantic Ocean. Further pretend that for whatever reason, the entire country of Iceland gets cut off from the internet or any other form of communication with the rest of the world temporarily. However, within this downtime, bitcoin transactions are still happening all over the world as well as within Iceland. 

Pretend now that internet access is restored. Given that Iceland was cut off from the world, and there was no way for the Icelandic Bitcoin nodes to communicate with nodes from the rest of the world, there will inevitably now be two Bitcoin blockchains, the Icelandic one, and a different one for the rest of the world. So, which version is the “correct” Bitcoin blockchain? 

In comes Longest Chain Wins. As the name suggests, the longest blockchain is the correct blockchain. If both blockchains are equally as long, then there will indeed be two blockchains until one inevitably prevails as the longest chain. Another way to put it, Longest Chain Wins states that “the chain with the most amount of work put into it is the correct chain”. For Bitcoin, a longer chain means that more work was done on that chain, since more electricity had to be expended to construct that chain. Going back to the hypothetical Iceland example, it is highly unlikely that during the outage the Icelandic bitcoin miners were able to confirm more blocks than the rest of the world. Therefore, it is likely that the Icelandic chain would be shorter than the chain made by the rest of the world. Therefore, the Icelandic chain would be abandoned and the network will agree that the chain formed by the rest of world is the "correct" chain.

Note that this system is scalable even if there are multiple pockets of outages. Instead of Iceland versus the rest of world, what if it was North America versus Asia versus Europe? The answer is the same, we still rely on the longest chain.

By using Nakamoto Consensus, Bitcoin is able to overcome the Byzantine Generals Problem.