What is the Byzantine General’s Problem and how does it relate to consensus mechanisms?

The puzzle that inspired Bitcoin

The Byzantine General’s Problem is a puzzle meant to describe the difficulty in achieving consensus between multiple, separated parties, and was first proposed by Leslie Lamport, Robert Shostak and Marshall Pease in their 1982 paper, “The Byzantine General’s Problem”. It was famously solved by Satoshi Nakamoto with his Proof of Work system and is the basis to how Bitcoin works. As we approach the 10 year anniversary of Bitcoin’s Genesis Block, first established on January 3rd, 2009, we propose to look back at Santoshi’s solution.

The problem goes like this:

Imagine there are four generals all attacking a single city. There is one at the East, one at the West, one at the North, and one at the South. If each general attacks at the same time, then the attack will be successful and the city will fall. If each general attacks at a different time, the attack will be unsuccessful. Because the generals are separated by great distances, they must communicate by sending each other messengers with notes that explain when to attack. Can each general agree on the same time to attack and be perfectly confident that the other generals received the correct time as well?

Here are a few things to keep in mind:

Each general will send out a time to attack, but he needs a confirmation that his message was received. Otherwise, the message may have been intercepted or lost. If a general attacked the city without confirmation, he might be attacking alone.
Each general needs to know that the sent message wasn’t altered with an incorrect time. This could have been done by a traitor general or by a spy that intercepted the message in transit. A general receiving an altered message may attack alone.

How does Bitcoin address this problem?

Bitcoin’s ‘Proof of Work’ consensus mechanism presented the first practical solution to this problem. Here is Bitcoin’s solution communicated in the form of the Byzantine General’s Problem.

Imagine one of the generals creates a message saying ‘attack at midnight’. It is sent and the other general(s) receive the message. If they simply send a confirmation message back, then it can be intercepted or changed by a traitor. Instead, the general receives the message ‘attack at midnight’ and creates a puzzle to deter traitors from changing the message. He sends an encrypted message to the other generals saying something like this:

the new attack time = the previous attack time (midnight) + [maths problem]

He sends the message and the generals compute the maths problem to find the new attack time. If each calculation can be completed in 10 minutes, then each general knows when to expect a new attack time. Once a new attack time is calculated, the general who solved it creates and sends a new message with the previous attack time as an input to calculate the new attack time again. If any of the other generals were still working on the previous attack time when they receive a new message (after 10 minutes), they start working on the new one because its proof-of-work chain is longer. The latest message is always the most updated attack time, so the generals will eventually come to an agreement on the attack time even if messages are intercepted, changed, or lost. (Read more about Bitcoin’s Proof of Work).

Here are two reasons why this is a solution:

Even if a few messages were stolen or altered, the generals will eventually receive an updated and accurate message. They would know this to be the most recent and valid message because it would have the longest proof-of-work chain.
Even if a traitor intercepted and changed the new attack time, a general could reason that it was false because the input for the previous attack time would be wrong or the maths problem would be wrong.

For Bitcoin, the generals are actually Bitcoin miners and nodes. They send messages to each other in order to update the state of the blockchain. A correct blockchain, or attack time, is never fully reached; instead it’s continually being updated.

Why is this not a theoretically perfect solution?

In practice, Bitcoin solves the Byzantine General’s Problem. It would be incredibly difficult for an attacker to ever successfully alter the Bitcoin network. In fact, it’s so difficult that Bitcoin is considered a solution.

However, in theory, Bitcoin is not a perfect solution. An attacker could continually send incorrect, but valid messages every 10 minutes to a general (this would be called a 51% attack). Proof of work gets more difficult as time passes though, so creating valid messages for a long period would take a huge amount of resources and is practically infeasible. Today, there are many consensus mechanisms, many cryptocurrencies, and many new technologies, inspired by this single puzzle.