The Byzantine Generals Problem - Simple Explanation

--- by D. Petkovski ---

The Byzantine generals problem is a distributed computing problem introduced in 1982, in a paper of the same name.

In this post, I’ll give a simplified summary of a formulation of the problem. Then, I’ll explain how the Bitcoin blockchain and its use of Proof of Work solves it in practice.

Table of Contents

The Byzantine Generals Problem: Summary

If I can summarize the Byzantine generals problem in a simple sentence, it’d sound like this:

How can we guarantee that multiple geographically distributed entities can reach consensus?

It sounds simple, but the complexity of the problem arises once we stop relying on assumptions that every participant is honest.

Planning an Attack

Let’s say that the Byzantine army is planning an attack on a fortress. The fortress is surrounded by multiple battalions, each lead by a general.

If all battalions launch a coordinated attack, we can guarantee a victory.

However, if a single battalion doesn’t participate, the army will suffer a defeat.

For the sake of simplicity, let’s focus on just two generals trying to coordinate the attack, General A and General B.

The goal is to reach consensus whether to attack tonight or not.

Possible Scenarios

General A is ready to attack and sends a messenger to inform General B.

Here are a few of the scenarios that can happen after General A sends the message:

The messenger is captured on the way and the message never reaches General B. General A will never know if General B got the message or not.
The message is delivered and General B sends a confirmation. The messenger is captured on the way back and the confirmation never reaches General A.
If the messenger is captured in any direction, a fake message can be delivered to General A, making him appear by himself.
At any moment in time, the enemy can send a fake message to General B, making him appear by himself.
This also raises the question of how any of the generals can be sure that the message they received hasn’t been tampered with.
One of the generals cooperates with the enemy and tries to lure the other one to appear alone.

These are just handful of scenarios from the top of my head, but we see how complex it can be to guarantee a consensus of parties that aren’t close to each other. Now extend the same thing to a larger network of participants – hundreds or thousands of armies.

You can already see the analogy of the actual problem – a group of components having to agree on the state of the system, while information can get intercepted, lost, or forged during transmission.

How Bitcoin solves the Byzantine generals problem?

Bitcoin implements a Proof-of-Work consensus mechanism.

In PoW systems, each “miner” has a financial incentive to be the fastest one to guess the solution to a certain problem.

This solution is hard to find, but easy to verify.

In a way, this is similar to a Sudoku puzzle – it might take someone 10 minutes to solve one, but just a few seconds to verify that a solution is correct. Once a miner broadcasts his solution, the rest of the network can easily verify it.

All confirmed transactions are part of blocks in a distributed ledger and every miner in the Bitcoin network must agree with its state.

The Distributed Ledger

When a new unverified transaction appears, it may originate from an honest or a dishonest participant.

A transaction that’s not genuine might mean an attempt of sending money that’s not in possession, an attempt to magically add money to a certain address, etc.

Here comes the interesting part.

A transaction will end up in the distributed ledger only if the majority of the network agrees with its authenticity. This means that if a bad actor tries to include a fake transaction, the rest of the network will disagree and disregard it.

Once there’s a consensus of which transactions are valid, every node updates their copy of the ledger.

This update is permanent.

Every next action will be based on the current state of the distributed ledger.

This guarantees that as long as at least 51% of the miners are honest, all transactions will be genuine.

Here’s a visual representation of why modifying the blockchain by a minority of dishonest miners is ~~impossible~~ highly improbable:

Remember that the mining process is not only time intensive, but also energy intensive – see Bitcoin’s hashrate.

In other words: an attempt to cheat this system is a waste of money. The game theory of Bitcoin makes sure that only honest actors are rewarded.

What Does This Mean For Us?

To understand the Bitcoin revolution, one has to understand the greatness of what we described so far.

Solving the Byzantine Generals Problem in the context of money means that, for the first time in human history, we can reach consensus without having to trust a central authority. There is no VISA/PayPal/banks between the transactions.

On top of that, and also for the first time in history, we have a borderless, easy-to-use, and extremely efficient monetary system that allows everyone to participate.

This is the value of the Bitcoin network.

Not the billions of $USD in market cap – that’s just a consequence.

If you want an introduction to Bitcoin without technical jargon and price speculation, check out my free series: Bitcoin for Beginners.

Author

D. Petkovski

📓 The Author Husband & Father
Software Engineer StrengthCentric
Bitcoin Hodler DeFi Veteran
🌍 Everything Enthusiast 🔥 Optimist

Revolutionizing ideas. Simplifying complexity. Sharing knowledge.