What is a Byzantine Generals Problem?
The Byzantine Generals Problem (BGP) is a term used in computer science and describes a situation where a number of dispersed parties need to coordinate a strategy to avoid failure. At the same time, some of those involved are corrupt and cannot be trusted.
The Byzantine Generals Problem is ideal to discuss consensus on the blockchain as, in a distributed network, all nodes need to make consensus, something that can be achieved through hashing, computing work and communication between the nodes/generals.
While the situation is fictitious, historically, the Byzantine Empire (330 AD to 1453 AD) was Eastern and Southern Europe, and its capital was Constantinople, which is now modern Istanbul, in Turkey.
First introduced in 1982 in a paper by Leslie Lamport, Robert Shostak and Marshall Pease, the problem is described as follows:
“Reliable computer systems must handle malfunctioning components that give conflicting information to different parts of the system. This situation can be expressed abstractly in terms of a group of generals of the Byzantine army camped with their troops around an enemy city. Communicating only by messenger, the generals must agree upon a common battle plan. However, one or more of them may be traitors who will try to confuse the others. The problem is to find an algorithm to ensure that the loyal generals will reach an agreement. It is shown that using only oral messages, this problem is solvable if and only if more than two-thirds of the generals are loyal; so a single traitor can confound two loyal generals. With unforgeable written messages, the problem is solvable for any number of generals and possible traitors. Applications of the solutions to reliable computer systems are then discussed.”
The example is mainly manufactured and refers to a situation where various generals and their armies have surrounded a castle, but they are unable to trust each other to attack or retreat. The problem presented by the different generals is that the situation will result in failure, unless they are able to trust the opposing armies and work together to achieve their goal, to conquer the castle. What stops them from succeeding is their lack of trust.
Blockchain as a solution
When it comes to cryptocurrencies, the Byzantine Generals Problem is timely, as it brings up the issue of trust to which the blockchain offers a viable solution.
Initially, the solution to the problem was developed by the entity known as Satoshi Nakamoto, who invented the bitcoin blockchain. Each army represents a node, messages are transactions and the enemy is the actual person who wants to change the blockchain.
The blockchain provides verification and a record of all the information from many computers, while, at the same time, none of the computers have more control over it or can be trusted as the utlimate source of reliable information.
According to “Duality: An excerpt,” allegedly written by Nakamoto, the Generals Problem can thus be solved with the bitcoin blockchain which operates on a Proof-of-Work consensus algorithm. The proof of work (PoW) used for both bitcoin and Ethereum, is the answer to a complex mathematical problem. With PoW, a majority agreement is reached without the need of a central authority, as miners compete to discover the solution to the next block, with the correct answer broadcast and verified by other miners. PoW is not without its problems, as proponents of Proof of Stake point out.