What is the Byzantine General’s Problem and how does it relate to consensus mechanisms?
Satoshi Nakamoto solved the The Byzantine General’s Problem when he created Bitcoin’s Proof of Work. But is it a perfect solution?
Satoshi Nakamoto solved the The Byzantine General’s Problem when he created Bitcoin’s Proof of Work. But is it a perfect solution?
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:
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:
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.
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.
—
Joe Delistraty
Technology Researcher
Good security is essential if you are running any cryptocurrency or blockchain system. We can discuss your security needs, or perform a security audit of your existing systems. Get in touch.
Get secure