Byzantine Generals Problem

Hypothesized by Leslie Lamport in 1982, the Byzantine Generals Problem outlines the challenge the nodes in a distributed system face in coming to consensus on the current state of the network.

The Byzantine Army has surrounded a city and is poised to attack. To successfully attack the generals commanding the army must be able to coordinate their movements. The challenge is at any given moment its possible a general has been compromised by the enemy.

So how can the generals coordinate their movements without knowing if any of their fellow generals have been compromised? The problem is solvable when 2/3 of the generals are provably loyal ensuring no single general can compromise two honest ones. 

Distributed systems face a similar problem achieving consensus since its difficult to prove which messages the system is receiving are valid and which ones are not. Distributed systems able to overcome this challenge and gain consensus amongst nodes are described as Byzantine Fault Tolerant. 

Historically, open, permissionless distributed systems have had a hard time scaling while achieving Byzantine Fault Tolerance

One of Satoshi Nakamoto’s notable contributions to the space was solving this problem with the Proof-of-Work consensus mechanism introduced in the Bitcoin white paper.  Which included block rewards incentivizing miners to reach consensus around the current state of the Bitcoin network. 

Also, making it prohibitively expensive to attack the network and reverse the transaction history that has already been agreed upon by the network’s nodes once consensus has been reached.

Further Reading Byzantine Generals Problem

The Byzantine Generals Problem – Leslie Lamport Original White Paper