Byzantine General's Problem

Introduction

The Byzantine Generals Problem, formalized by Leslie Lamport in 1982, is a situation faced by computers in a distributed system trying to come to consensus. It’s described abstractly as a group of generals commanding a Byzantine army who have surrounded a city they plan to attack. The problem is any one of the generals could be compromised and the goal is to coordinate battle plans. Without knowing who could be compromised it becomes difficult to come to consensus around battle plans. This problem was shown to be solvable only if more than two-thirds of the generals are known to be loyal such that no single general can compromise two honest ones.

This is the same problem facing distributed systems in an adversarial environment since it is difficult to tell which messages being received are honest and which are not. If a distributed system can come to consensus, then it is known to be Byzantine Fault Tolerant. This is difficult to achieve in practice and most systems do not scale well, especially in open, permissionless systems.

Pseudonymous author Satoshi Nakamoto was the first to solve this problem in an asynchronous environment by utilizing a Proof-of-Work sybil resistance mechanism with block rewards as incentive to probabilistically ensure consensus is reached. While technically possible to attack network it becomes prohibitively expensive to reverse transactions after a certain amount of time.

Suggested Reading

The Byzantine General's Problem - Leslie Lamport

Practical Byzantine Fault Tolerance - Miguel Castro and Barbara Liskov

If there is anything you'd like to add or change, you can tweet your feedback at @messari_crypto or email [email protected]

Let us know what you loved about the report, what may be missing, or share any other feedback by filling out this short form. All responses are subject to our Privacy Policy and Terms of Service.