Byzantine Generals Problem: Definition & How It Was Solved For Monetary Networks (2024)

Strap in as we embark on a thrilling journey into the complex and captivating world of the Byzantine Generals Problem! OK… so maybe not thrilling, but it’s at least mildly interesting. While sounding simple at first, it quickly devolves into a riddle wrapped in an enigma, tucked inside a computer science paradox.

What Is The Byzantine Generals Problem?

The Byzantine Generals Problem is a fundamental issue that arises when you have multiple parties that are communicating and must reach consensus despite potential systems failures, deception or betrayal. The text book analogy that’s used to illustrate this problem involves the Byzantine army invading a city.

How do you make sure that multiple entities, which are separated by distance, are in absolute full agreement before an action is taken?

Mike Maloney

The Byzantine army, along with the Byzantine navy, was the main armed forces for the Eastern roman army between 395-1453. Now, imagine that this group of armed men are attacking an enemy city and have totally surrounded the cities walls.

To make things super simple, there’s just one General and two Lieutenants. They lead three separate armies of men around the perimeter and need to communicate with each other in order to pull off a successful attack on the city.

Our problem is, how do they communicate with each other and all agree on a course of action? This agreement is called consensus.

Deception In The Ranks

Like many intractable problems it seems simple on the surface. The general just needs to send messengers to the two Lieutenants that says “attack at noon” and the problems solved! But what if one of the Lieutenants is a traitor?

As you can see, our traitorous Lieutenant receives the correct “attack” message, but then reports to the other loyal Lieutenant that they actually received “hold”. This creates confusion and when noon comes, only the Generals men actually attack resulting in a lost battle.

But it gets worse.

What if the messenger is a traitor? What if no one is a traitor, but the person writing down the message mistakenly hears the wrong thing? What if the General themselves is the traitor as opposed to the two other loyal Lieutenants?

This is essentially the simplest setup possible, just three heads and two different messages, and already you can see things are escalating into something quite complex! If we’re talking about ten or a hundred generals and dozens of different potential military plans of attack or retreat the problem can become intractable.

The Modern Day Byzantine Generals Problem

Obviously there aren’t many Roman era armies around today – damn shame that really – so why is this even a thing that you should care about? Well some of the sharper ones out there might have noticed that our diagram of the General and Lieutenants above is quite similar to that of the Bitcoin Network.

Here we see many nodes, all communicating with each other and needing to make sure that they all agree on the current state of the network. It’s also possible that any number of those Bitcoin Nodes could be run by malicious people, infected with malware or just be broken somehow and sending out the wrong message.

Maybe the current state of the network is at block height 123, but because Bob screwed up their Bitcoin Core bitcoin.conf file it’s saying the block height is 1234. The network, whilst being made up of tens of thousands of decentralized nodes and without any central bank or head server needs to know what messages are true and what are false.

It needs to achieve consensus without trusting any specific node and only using the information that the node itself has. That is not an easy task! It’s also not easy to do with minimal and cheap hardware. To achieve this, it needs to have what’s called Byzantine Fault Tolerance or BFT.

What Is Byzantine Fault Tolerance?

Byzantine Fault Tolerance (BFT) is a mechanism that allows our system to sustain functionality amidst failures or attacks. These faults cause different messages to be sent to different observers – a phenomenon known as a Byzantine failure or Byzantine faults.

BFT algorithms and protocols are designed to reduce the effects of these failures and guarantee the integrity and consistency of the system, even when dealing with arbitrary data that’s coming from malicious or just plain broken nodes.

In short, our Bitcoin node needs to be able to receive both the “attack” and “hold” messages and figure out on its own what the real consensus of the network is. BFT isn’t something that’s just needed for the Bitcoin network either, having this tolerance to faults in a monetary system is just as useful as having it in military units during a coordinated attack.

The “nodes” can also be inside the same computer system too, for example a single plane computer might have dozens of sensors that report messages to it. Having proper BFT allows for one or more of the sensors to break or get hacked and have the plane not crash. This is the case for any mission critical system like nuclear power plants or rockets.

Byzantine Faults In Decentralized Systems

Decentralized networks like Bitcoin have a much harder time dealing with Byzantine faults as there’s no central authority to trust. Satoshi Nakamoto explicitly didn’t want any trusted central authorities or even trusted third parties involved in the network as they are security holes.

All Bitcoin nodes have equal say in the network, are located all around the world and can be controlled by anyone, even those that are Bitcoin’s biggest enemies. Compared to even a complex plane, this sprawling network of extremely diverse computer systems was a problem that stumped computer science researchers for decades.

Until 2008 when Satoshi dropped the Bitcoin Whitepaper titled Bitcoin: A Peer-to-Peer Electronic Cash System.

How Satoshi Solved The Byzantine Generals Problem

Over the years there have been many research papers written and many exceedingly smart people try and solve this problem. It should also be noted that Satoshi wasn’t the first to solve the Byzantine Generals Problem, but they did do it for a monetary network and in a brand new way.

Even way back in the 1980’s there were multiple solutions to dealing with Byzantine faults including Draper’s FTMP, Honeywell’s MMFCS and SRI’s SIFT architectures. Dozens more were built and deployed throughout the 90’s and 2000’s in everything from planes to submarines.

Blockchain & Bitcoin Proof-Of-Work (PoW)

To solve for Byzantine faults, Satoshi designed the Bitcoin network to work in parallel to generate the Bitcoin Blockchain via its Proof-of-Work consensus algorithm.

The PoW algorithm not only solves Byzantine failures, but also contributes a number of other critical things to the network in what is an amazingly elegant overall solution that requires no centralized systems or traditional financial system.

A blockchain is a distributed database, also referred to as a distributed ledger, that’s shared between many nodes on a network. They are most commonly used in cryptocurrency networks, but they have been used for other things too. The data that’s stored in a blockchain is immutable, meaning that it can never be changed.

Blockchain technology is the key to solving the Byzantine Generals Problem in the Bitcoin network as it establishes a trustworthy database for all nodes on the network. This database allows each node to verify all data, right back to the Genesis block, ensuring there’s no data manipulation or bad actors trying to insert or generate arbitrary data.

How Bitcoin Provides Practical Byzantine Fault Tolerance

If a node receives a correct network message from an honest actor, then receives an incorrect message from another bad actor, it can use that information to figure out what the correct state of the network is. How?

It simply agrees with whichever Blockchain is the longest, provided it obeys all the other rules of the network.

For example, if Bob mines 2 new blocks while at the same time Alice mines 1 new block, our node will receive these 3 new blocks and have to decide which chain to accept as the truth. This decision making process must also match what all other nodes decide too.

As Bob’s chain is longer (2 blocks added vs 1), our node will update its system’s state to say that Bob’s chain is the main bitcoin blockchain while discarding Alice’s. Alice’s block is what’s called an orphan block.

Another way that Byzantine failures are avoided is by using cryptographic security in the form of hashing and public and Private Keys. This prevents data tampering and allows nodes to verify transactions and their owners, making bitcoin virtually impervious to fraudulent information or the Double Spending Problem.

The end result is an immutable, distributed database that both old and brand new bitcoin nodes can fully verify the full transaction histories on. All run on a super cheap and sexy looking Umbrel Node.

The Future Of Byzantine Fault Tolerance And Distributed Systems

While it hasn’t been easy to achieve Byzantine fault tolerance for distributed computing systems like Bitcoin, the future is bright. Secure communication channels like End-to-End Encryption (E2E) combined with this new PoW consensus algorithm has shown the world how completely decentralized and leaderless networks can be secure and possible.

Now if someone wants to build a reliable computer system in such a way that it’s resilient to Byzantine failures, they can. At its heart a blockchain is just a database that’s copied onto all the nodes in the network, all around the world. This makes it much less efficient and slower than having one, central database. But. It has the benefit of making it decentralized and immutable.

Many companies have tried to use blockchain technology for other applications like voting systems or storing medical data and some have shown promise. However it’s still too early to tell whether there are other solid use cases for blockchains beyond Bitcoin.

FAQ