The Byzantine Generals’ Problem is an age-old game theory problem, where several Generals of the Byzantine army are preparing to attack an enemy city from all sides. They have surrounded the city, but they must collectively decide when to attack so the generals in charge of each regiment must coordinate together to attack on same time to overcome the defense from the enemy. If all generals attack at the same time they win, but if they attack at different times or one faulty general chooses not to fight, they lose. Each regiment has a messenger who is used as a communicator, but there is no way of knowing whether the messenger is a traitor or the message itself is intercepted by the enemy.
The only way to victory is that every generals are honest including the messenger and also there is a way to know that the message is not tampered by the enemy. The only solution to this problem is to send message or command to attack or retreat to the other generals on the other side. Each general collects the message from the messenger from each sides. But there is no way to trust the messenger because the message might have been tampered on the way by the enemy. So it would be wise for the generals usually to follow the majority of the message from different generals and send it back to the commander and execute it. Honest and coordinated attack could lead to victory but noone could ensure that every generals and their commanders are honest so even one traitor could lead to defeat.
This same problem followed in the computer science world, where decentralized parties face difficulty in arriving at a consensus without relying on a trusted central party. The problem of coordinating consensus among the participants in distributed systems was first identified by computer scientists in 1970s. In a distributed system, it may still be deemed reliable even if one or more components or nodes have failed. This leads to the concept of Byzantine Fault Tolerance in the distributed system. This provides a measure of the ability for a system to resist a certain amount of failure and still collaborate with other nodes to make the whole system work.
Byzantine Fault Tolerance
In the late 1990s, Barbara Liskozv and Miguel Castro developed a consensus algorithm for distributed networks called Practical Byzantine Falut Tolerance. However, when the number of nodes or participants on the network increased, the time taken to reach consensus increased exponentially. Byzantine Fault Tolerance(BFT) is the property of a system that is able to resist the failure derived from the Byzantine Generals’ Problem. BFT system is able to continue operating even if some of the nodes fail to communicate or act maliciously.
A breakthrough in addressing this Byzantine Generals’ Problem occured in 2008 when Satoshi Nakamoto published the Bitcoin whitepaper, which introduced the proof-of-work algorithm. The consensus algorithm used in Bitcoin is called Proof-of-work and is one of the most common implementations of consensus algorithm. While the bitcoin protocol defines the rules, the consensus algorithm determines how these rules will be followed. For instance, during the validation of the transactions.
The concept of proof work is older than Bitcoin. But Satoshi Nakamoto developed the modified version that enabled the creation of Bitcoin as a Byzantine Fault Tolerant System. Although Proof of Work is not 100% fault tolerant, it has proven to be one of the most secure implementation for blockchain networks and is considered by many as one of the most genius solutions to the Byzantine faults. Securing these systems is an ongoing effort, and the existing consensus algorithms are yet to overcome a few limitations. But the potential applications are certainly inspiring wide spread innovation beyond the Bitcoin blockchain. A few use-cases of Byzantine Fault Tolerant Systems include the Aviation, Space and Nuclear Power industries.
How Bitcoin solved this 5,000 year old Byzantine Generals’ Problem?
Bitcoin works as a decentralized digital ledger which is maintained by the distributed network of computers. It has allowed a trustless economic systems and the financial transaction could be executed without the need of any intermediaries. Bitcoin relies on a decentralized network of miners that collaborate to maintain the decentralized ledger of transactions. Each miner must be able to trust that transactions added to the ledger are true. These miners are the equivalent of the generals in Byzantine Generals’ Problem. And the ledger and transactions are the messages the miner shares. The proof-of-work algorithm makes miner agree that the transactions are valid before adding to the blockchain ledger. They validate those transactions using the historical information on the ledger to check that the necessary account balances are available. If any one of them find the tampered data, they have the power to reject that specific transaction. And if every honest nodes does that on their own, the faulty transaction is not accepted.
Once the honest transaction has been validated, they are recorded on the ledger permanently and is published throughout the network. This way the honest transaction can be trusted with its history of data. Once every miner has the copy of the same data, it can be verified as true and honest. Satoshi Nakamoto used the game theory to incentivize miners to act in such a way that is beneficial to the whole network.
Bitcoin network addresses the Byzantine Generals’ Problem such that there has never been 51% attack meaning there has never been a time that 51% of the miner has ever accepted the faulty transaction. This does not mean it is impossible to launch an attack on Bitcoin. Theoritically its possible, but the game theory suggest that it would be financially super profitable for the attacker to act honestly than to act maliciously and lose time, energy and money. As miners have to invest significant amounts of energy/money to participate in mining which is the way they receive BTC as the reward of their efforts. The false broadcaster will have wasted the work that was required for their attempt to spread the false message. This makes it too expensive for any “Byzantine General” in this case bitcoin node to lie. Because each node can verify all information independently, it makes Bitcoin a trustless system. That’s how Bitcoin solved the Byzantine Generals problem. What Satoshi did was a one-time discovery and cannot be reinvented.
Thank you for reading and see you on next one.