The Byzantine Generals Problem
In a decentralized peer-to-peer system like a public blockchain, there needs to be consensus. The individual parts of the system need to agree on the history of the blockchain up until the present moment as well as on how to move forward since there is no central authority to assume responsibility over it.
That’s easier said than done. There is always a risk of misinformation or miscommunication between users, whether accidental or deliberate. The Byzantine Generals Problem is a way of explaining the problem of misalignment between users of a decentralized system and its solution, without which decentralized Distributed Ledger Technology, and several other types of computer networks would fail to function properly.
Take a public blockchain for example. To make it work, enough participants in the blockchain must agree on the history of validation and permanent registration of transactions on the blockchain ledger up until that point. If we could rely on everybody to be honest, there would be little or no problem — but we can’t. The temptation to register fraudulent transactions or illicitly reverse genuine transactions, while hanging onto their ill-gotten gains is simply too much for some users to resist.
Public blockchain protocols must deal with this issue autonomously. No single participant can step in and unilaterally declare transactions to be valid or invalid. That would make nonsense of the principle of decentralization. But to understand how a blockchain protocol can handle such a challenge, we first need to know more about the problem.
Let’s allow the Byzantine Generals step forward and tell us all about it. The Byzantine Generals Problem was given its name by Leslie Lamport, one of the three authors of a pivotal paper on the subject in 1982. He reasoned that ‘the best way to attract attention to a problem is to present it in terms of a story’, meaning the Byzantine Generals didn’t actually have a problem with achieving decentralized consensus — it’s just an effective way of helping people understand the problem.
Imagine a military operation in the East Roman Empire (aka Byzantium), more than 1,000 years ago. Several Byzantine generals and their armies are positioned around a rebel city. Each general and army is in a separate camp. Communication between the generals is only possible by messengers who must cross the open terrain from one camp to another.
For the generals and their armies to successfully attack the city or retreat safely from it, they must all act together. Failure to coordinate their actions by even one of the generals will mean that all the armies will be individually massacred by the forces of the rebel city. To act together and take over the rebel city, they must agree on when to attack and at what time — but here’s the catch:
- They could send messengers on horseback, but what if one is captured or killed before delivering the message?
- They’d need to reply to one another to confirm they’ve received and agree with the message, but this would entail sending another messenger on horseback who may also be captured or killed.
- What if a messenger is intercepted by the enemy and the message is changed in order to confuse the generals?
- How do any of the generals know that the messages they received are genuine?
- What if one or more of the generals are traitors and intentionally send the wrong message to other generals?
It’s a tough problem to crack, but one that Satoshi Nakamoto managed to solve through the Bitcoin blockchain.
Distributed systems with mechanisms to overcome this problem are said to have Byzantine Fault Tolerance or BFT. Bitcoin has BFT built into its protocol. Its proof of work consensus mechanism is designed to produce new blocks every 10 minutes, using the total available computing power in the Bitcoin network and rewarding the first node to mine the next valid block.
All the other Bitcoin nodes in the network can easily and individually check that a new block of transactions proposed by one of the nodes has been correctly mined. In this way they can then reach agreement on whether to add the new block to the existing blockchain.
And so, unlike the Byzantine generals who — rumour has it, are still stationed around the rebel city to this day — users of public blockchain systems can safely and securely run their operations.
Enjoyed this post? You’ll find plenty more like it on:
