Byzantine Generals Problem

Imagine army units surrounding a city. They must attack together or retreat together; splitting their actions could be disastrous. A commander sends orders, but someone may betray the others and give them different accounts. How can reliable participants make sure they ultimately act alike? This is not an account of an actual battle. It is a thought experiment about computers that need consistent records. Several servers, computers running a shared service, might, for example, need to agree on whether a payment has already been processed. Receiving an answer is not enough: those answers must support a common decision. [1] [9]

Leslie Lamport, Robert Shostak and Marshall Pease presented the familiar formulation in July 1982, following their 1980 work on agreement in the presence of faults. A traitor represents a component whose behavior we can no longer predict. A computer need not simply stop. It may answer one neighbor correctly and another incorrectly, omit messages or claim to have seen something different. An attack or a software fault could cause this. A Byzantine fault describes what other participants observe, not the device's intentions. BFT, short for Byzantine Fault Tolerance, means the ability to withstand such behavior under stated conditions. [1] [2]

The original problem sets two requirements. IC1 says that all reliable subordinates must accept the same order. IC2 adds that, if the commander is reliable, they must accept the commander's actual order. Without the second requirement, an apparent solution would be to always retreat, even when that ignores a reliable commander. Computer systems distinguish safety, which rules out conflicting outcomes, from liveness, which means being able to reach an outcome at all. Further rules determine which outcomes are valid. A consistent record does not, by itself, prove that an input statement was true in the outside world. [1] [9]

Call the commander A and the subordinates B and C. C receives an attack order from A, but B says the commander ordered a retreat. Is B lying, or did the commander give each a different order? Without a signature that can be verified after forwarding, C may be unable to distinguish these situations. B can face the same uncertainty. Always obeying the commander lets a dishonest A split them; always ignoring the commander violates the requirement for an honest one. In this three-participant problem with one possible traitor, no procedure without signatures always succeeds. The obstacle is missing distinguishable information, not slow computers. [1] [9]

In the classical model without signatures, tolerating m possible traitors requires at least n ≥ 3m+1 participants: four for one traitor. Here n is the total number of participants, and m is the largest number of traitors the system must tolerate. That does not mean adding a vote and taking a majority once. The OM(m) procedure repeatedly relays what participants heard and evaluates messages according to common rules; its base case OM(0) takes the commander's value or an agreed default. The model assumes known participants, direct connections, correct delivery of sent messages, knowledge of the immediate sender and the ability to detect a missing message. So 'without signatures' does not mean 'without any authentication of origin'. Without these assumptions, the number four guarantees nothing. [1] [9]

With a verifiable Digital Signature, B can give C evidence of what the commander actually signed. A program creates this signature using a private key, a secret numerical value. Others check it with the corresponding public key, without needing to know the private one. A traitor cannot silently alter a reliable participant's order or imitate that participant's signature. The signed-message algorithm circulates signed values and applies a shared selection rule. This model removes the honest-majority requirement above, but still assumes unforgeable signatures, delivery and appropriately timed rounds. Dolev and Strong's 1983 work further studies the required number of rounds. Even a valid signature does not guarantee truthful content or timely delivery, nor does it prove that the private key has not been stolen. It establishes the origin of a particular message, not the sender's general trustworthiness. [1] [3]

When a server does not reply, others cannot tell whether it has stopped or merely has a very slow connection. The FLP result, published in 1985 by Michael Fischer, Nancy Lynch and Michael Paterson, makes this uncertainty precise. A process here means a running program. A deterministic procedure takes the same next step from the same state and input; it does not choose that step at random. In a fully asynchronous system with no known upper bound on delay, a deterministic procedure cannot guarantee agreement will finish in every admissible execution if even one process may crash. This holds even with reliable delivery whose delay is unbounded. It does not mean agreement never happens. Practical systems add timing assumptions, a suitable failure detector or randomness. During a network partition, waiting may be safer than confirming incompatible outcomes. [4] [13] [8]

In 1999 Miguel Castro and Barbara Liskov described Practical Byzantine Fault Tolerance, or PBFT, for a service running on several known replicas. These replicas are copies of the service running on different servers and continually processing the same requests. They are not stored backup files. Its basic configuration n = 3f+1 tolerates f faulty replicas. With four servers, one may be Byzantine; two groups of three overlap in at least two servers, at least one of which must be reliable. Such a required set of approvals is called a quorum. Intersection alone is insufficient: phase rules and leader changes matter too. More precisely, the prepared state requires the request, a pre-prepare message and 2f matching prepare messages from different replicas other than the primary. Local confirmation additionally requires 2f+1 commit messages, possibly including the replica's own. Authentication, sequence numbers and checkpoints address forgery, replay and unbounded log growth. Safety does not rely on timing bounds, but continued progress needs additional conditions on delays. [5] [10] [11] [12]

Bitcoin does not have a predetermined, closed list of servers. If every newly created account got one vote, an attacker could manufacture a majority: this is a Sybil Attack. Proof of Work instead ties block production to computational work. A block is a batch of transactions added to the shared history. A Full Node, a computer running software that independently checks the rules, first rejects invalid blocks and then follows the valid branch with the greatest accumulated work. Bitcoin does not run OM or PBFT; temporary forks are part of its operation. Given a sufficient honest share of computing power and suitable communication conditions, further confirmations reduce the risk of history being rewritten, but do not create absolute irreversibility. Bitcoin Backbone research examines these conditions: agreement between histories, chain growth and the share of blocks honest participants can produce. [6] [7]

When told that a network reaches consensus, look for concrete answers: who may participate, what can the attacker control, how long can messages take, and when might a decision change? Even Proof of Work does not remove every problem. An Eclipse Attack isolates a node from honest peers, censorship leaves transactions out, and Selfish Mining involves withholding mined blocks. Software faults and the possibility of rewriting part of the history with sufficient attacking power also remain. Yet even majority computing power cannot make a correctly functioning Full Node accept a block that violates its rules. The generals' story is useful because it teaches us to examine the conditions for agreement rather than trust a technology's name. [6] [7] [8]