The Byzantine Generals’ Problem

As I’ve written about recently, gauging the detail with which to explain Bitcoin to a newcomer is a skill in itself – and I make no claims to be an expert at doing so. However, for those who question why the blockchain’s such a big deal, I find the Byzantine General’s Problem sometimes helps. So – mainly for my own benefit as I continue to try to simplify this explanation – here’s how I’ve found myself explaining it recently. It’s not for everyone but it may be useful to someone. If you understand Bitcoin in detail, please forgive the slight simplification in parts.

Why is the blockchain so important?

We now have a technology that provides us with a permanent and complete record of every transaction that’s ever taken place. Despite the fact that there is no one gatekeeper controlling how transactions are recorded, the record represents the truth and can’t be fiddled with after the fact. That by itself is pretty amazing.

How can you be certain?

In short, because it solves the Byzantine Generals’ Problem. This is an old computer science problem that was thought to be unsolvable before Bitcoin.

OK – what’s the Byzantine Generals’ Problem?

Picture the scene. A castle in the Middle Ages is under siege. There’s 300 baddies in a Castle surrounded by five armies of 100 men each who’ve set up camp in the surrounding hills. Each army is commanded by a General.

500 men v 300 men. The result is surely a foregone conclusion. 500 attackers will easily overpower the 300 men inside the Castle. However, if they don’t all attack simultaneously, there’s a very real risk that the attackers will be outnumbered, the attack will be repelled and they’ll go on to lose the battle.

So how can the Generals all agree on the same time to attack the Castle? These days, you’d simply need a quick conference call and the Generals could all agree to attack at 9pm. But back in the Byzantine Age, things were a little more complicated:-

1. The “9pm attack” message could only be passed on by a rider on horseback. He has to ride around visiting each General in turn to confirm.
2. Any General may be a traitor and in league with the baddies in the Castle.

What happened before Bitcoin (and the blockchain)?

General 1 decides to attack at 9pm. He sends his rider out with the message (“9pm attack”) to deliver it to General 2. Upon arrival, General 2 reads the message, notes the time of the attack and signs the message to also say “9pm attack”. He sends the rider on to share the message with General 3.

But – there’s a problem. General 3 is a traitor. He wants to the attack to fail. So when he gets the message, he rips it up and replaces it with a new message that says “8pm attack”.

The rider continues unaware. General 4 now receives a message saying “8pm attack”. He notes the time, signs the message to say “8pm attack” and sends this on to General 5.

Now the message has gone around everyone. But we have a problem. The dishonest General has disrupted the result. We now we have two generals (4 and 5) with 200 men attacking the Castle at 8pm. Expecting the others to join them, they instead get outnumbered and overpowered by the 300 defenders. The victorious baddies now stream out of the Castle and join forces with the treacherous General 3. Suddenly the two remaining Generals (1 and 2) have only 200 men and find themselves fighting 400 men.

Result: the (dishonest) baddies win.

What happened after Bitcoin (and the blockchain)?

General 1 wants to send the same message (“attack at 9pm”). But this time, there are two new rules he must abide by:-

1. He must spend 10 minutes preparing any new message for it to be valid; and
2. He must include the history of every previous message in every new message.

So let’s see what happens this time. As before, General 1 sends the message (“9pm attack”) with the rider on horseback. This time, however, it’s different for General 2 because he knows two things for certain:

1. The message must have taken 10 minutes to prepare; and
2. There are no previous messages – so it must be the truth*

(*or, more accurately, even if General 1 is a traitor and put in the wrong time, it doesn’t matter – if the majority of Generals followed this suggestion and went with a 9pm attack time, they’ll still be outnumber those in the Castle and win the battle)

Ok, so now it’s time for General 2 to send a message. As required, he spends 10 minutes preparing the new message and he embeds General 1’s message into his own. The rider then sets off with this message (now in fact, it’s two messages ‘chained’ together as the second has the first embedded within it).

Now it gets to General 3. Remember, he’s the traitor. What does he do? Last time, he changed the message to “8pm attack” so that Generals 4 and 5 would attack early and get overpowered. But all of sudden, now he can’t. Why? Because under the new rules, he has only 10 minutes to prepare a message for General 4. He has two options:

1. Cheat by changing the message to “8pm attack” – but to do this, he needs to (a) spend 10 minutes creating his message,  and then (b) spend an EXTRA 2 x 10 minutes working to create replacement “8pm attack” messages from Generals 1 and 2 to embed these into his message – and, what’s more, (c) carry out that 30 minutes of work within the next 10 minutes to avoid the other Generals knowing that he’s a traitor; or
2. Admit defeat and prepare the “9pm attack” message  during that 10 minutes.

You’ve lost me…

Every General has got no more than 10 minutes to provide the next General with something that would take more than 10 minutes to fake if they were trying to be dishonest. If they can’t deliver it within 10 minutes, everyone knows they’re dishonest and ignores them, rendering their attempts to mislead others useless.

Which means…

In Bitcoin, the network of computers comes to an agreement every ten minutes about which transactions are valid and adds these to the record.

The 10 minutes work in this example is known as Proof of Work. This work is hard (time-consuming) to do, but it’s easy for others to check whether or not it’s been done, making it valuable. An example of proof of work might be if someone asked you to write down all the numbers from 1 to 1000 by hand. Someone can easily scan the piece of paper to check that you’ve done the work – but for them to replicate the work, they’d have to actually sit down and spend all that time writing those numbers again themselves.

The result is that we now have a technological invention which means that, for the first time, it is possible for a distributed network of individuals (thousands of computers situated around the globe, instead of just five Generals around one Castle) to reach agreement (‘consensus’) about every transaction that takes place, to record those details and to make those records mathematically impossible to forge.

Whilst the most common use of the blockchain at present relates to the bitcoins that everything thinks of (or not) as currency, this is in no way the full story. Once you start to consider how the blockchain structure itself can be used to record any number of other transactions, documents, accounting records, shares or indeed any other transaction that could prove to be far too risky to entrust to a centralised organisation, you realise how great it is for all of us that those Byzantine Generals can now finally agree on their plans for the evening.

It’s simply the start.