The Byzantine General's problem is a war scenario in which several battalions of the Byzantine Army led by different generals must collectively agree to a strategy but don't have a reliable, trustworthy way of ensuring that the other generals will all act according to the plan. If all of the generals collectively attack, they will have an advantage over the enemy and the attack will likely succeed. However, if only some of the generals attack and others retreat, the attackers will likely be defeated.
There are many things that can go wrong in this situation. For example, the messengers sent between generals might be intercepted by the enemy, or they might only reach some of the generals but not all of them. They might also relay the wrong message accidentally, forge an incorrect message maliciously, or be told the wrong message by a malicious general who wants to deceive the other generals.
This problem is relevant to decentralized computer systems because they have multiple independent actors who must achieve a consensus on a single state for the system. Reaching this consensus is difficult due to a number of possible failures, called Byzantine failures. For example:
- Hardware components could crash or break
- The network can become congested
- Nodes can get disconnected from the network for various reasons
- Requests can be processed incorrectly
- Local states can be corrupted
- Nodes can produce incorrect or inconsistent outputs
- One or more nodes might attempt a malicious attack
These potential problems are analogous to all of the ways that the generals in the Byzantine Army might fail to coordinate and collectively carry out a strategy.
A measure of how well a system is designed to tolerate or prevent these various Byzantine failures is known as the system's Byzantine fault tolerance.
This property is particularly important when a decentralized network is permissionless, meaning that anybody can participate in the network. For example, anybody can mine Bitcoin from anywhere in the world as long as they have the right equipment and an internet connection, and each of the possible Byzantine failures can occur arbitrarily or intentionally for any of the participating nodes.
Several solutions are used in tandem in order to give Bitcoin a high degree of Byzantine fault tolerance:
- Public-key cryptography is used for unforgeable digital signatures.
- All Bitcoin transactions are broadcasted atomically, meaning that all of the participants in the network receive them at the same time.
- Proof-of-work is used as a disincentive for nodes to attempt malicious attacks.
In terms of the original problems faced by the Byzantine Generals in their war scenario, each of the three solutions employed in Bitcoin serve different roles. Using public-key cryptography is analogous to ensuring that messengers won't forge or miscommunicate messages between the generals. Atomic broadcasting is analogous to ensuring that all of the generals receive the same message at the same time. And proof-of-work ensures that any general who tries to maliciously deceive the other generals will pay a heavy price for doing so.
Byzantine General's Problem
February 23, 2018
The Byzantine Generals Problem - An Intro To Blockchain
August 8th, 2016
The Byzantine Generals Problem - Microsoft Research
Leslie Lamport, Robert Shostak, Mashall Pease
The Byzantine Generals' Problem - All Things Ledger - Medium