Skip to content
Financial Context Wiki

Byzantine Generals Problem: Agreement Under Conflicting Messages

The Byzantine Generals Problem asks how honest participants can agree when faulty participants may send conflicting information. Analyze the agreement task, channel and authentication assumptions, fault bound, lower bound, algorithm, and deployment separately.

Updated

Educational protocol analysis only. Solving one Byzantine agreement model does not prove that a deployed network is safe, live, correctly implemented, decentralized, final, or secure for assets.

Direct answer

The Byzantine Generals Problem asks how nonfaulty participants that communicate by messages can reach a consistent decision when some participants may behave arbitrarily, including sending different claims to different recipients. The military story is an analogy for interactive consistency in distributed systems, not a historical event and not one specific blockchain consensus algorithm.

In the commanding-general formulation, IC1 requires all loyal lieutenants to obey the same order, while IC2 requires every loyal lieutenant to obey the commander’s order when the commander is loyal. Agreement alone is insufficient: a rule that always chooses RETREAT would agree but would violate the loyal commander’s valid ATTACK order.

For the paper’s “oral messages” model with at most m traitors, a solution exists only when n>3m, equivalently for integer participants n>=3m+1. This model assumes messages sent by loyal participants are delivered correctly, recipients know who sent each message, and absence of an expected message can be detected. “Oral” means unauthenticated content can be forged as another participant’s report; it does not simply mean an unreliable courier can vanish unnoticed forever.

The paper’s “signed messages” model adds unforgeable, publicly verifiable signatures and changes the resilience result. It does not make signed content true, ensure delivery, solve fully asynchronous termination, protect stolen keys, or establish a modern protocol’s safety. The Byzantine Generals Problem, the Two Generals or coordinated-attack problem, FLP, BFT protocols, Proof of Work, and Proof of Stake are related but distinct models or constructions.

How to analyze it

  1. Define the agreement task. State the participants, inputs, outputs and precise agreement, validity and termination properties. For the commander formulation, write IC1 and IC2 explicitly rather than saying only “reach consensus.”
  2. Define identity and channels. State whether point-to-point messages are authenticated, delivered reliably, ordered, replay protected and attributable; whether omission is detectable; and whether broadcast is a primitive or implemented by repeated sends.
  3. Define timing. Separate synchronous bounded delay, partial synchrony after an unknown stabilization time and full asynchrony. Do not add disappearing messengers to one model and retain a theorem proved for another.
  4. Define the fault budget. Record total participants n, maximum Byzantine participants m, whether corruption is static or adaptive, and whether faults include omission, equivocation, collusion, key theft or faulty channels.
  5. Trace information recursively. For every loyal participant, list direct claims and relayed claims, including sender paths, missing-message defaults and deterministic tie rules. Compare what two loyal participants can distinguish from their local views.
  6. Check the theorem and algorithm together. Match lower bounds and sufficiency to the exact oral or signed model, connectivity and fault budget. A threshold inequality alone is not an implementation or a proof.
  7. Map the model to deployment. Verify the deployed protocol’s OM(m), SM(m) or other mechanism, message domains, rounds, locks, certificates, membership changes, timeouts, client behavior, finality rule and application confirmation policy.

The key proof technique is indistinguishability. A loyal participant sees only its local messages; if two executions look identical to it but require different decisions for validity, no deterministic rule can always choose correctly. Protocols succeed by adding enough independent participants, authenticated evidence, timing assumptions, randomness or other structure so that the required executions become distinguishable or the guarantee changes.

Worked examples

1. Why three oral-message generals cannot tolerate one traitor

Let n=3 and m=1. The required condition n>3m becomes 3>3, which is false. Suppose commander A tells lieutenant B ATTACK and lieutenant C RETREAT. B cannot tell whether A is the traitor sending conflicting orders or C is the traitor falsely reporting what A said; C has the symmetric uncertainty.

Any deterministic choice that preserves a loyal commander’s order in the corresponding loyal-A executions can force B and C to choose differently in the traitorous-A execution. Message forwarding does not create a fourth independent source, so both IC1 and IC2 cannot be guaranteed.

2. Four oral-message generals and one traitor

With OM(1), n=4 and m=1, the commander sends an order to three lieutenants; each lieutenant relays the value it received to the other two; each loyal lieutenant applies the same majority rule and default. If the commander is loyal and sends v, a loyal lieutenant sees values such as v, v, and a possible traitor’s x, so it selects v.

If the commander is the sole traitor, all three lieutenants are loyal and relay exactly what each received. They therefore reconstruct the same set of commander-to-lieutenant claims and apply the same deterministic rule. They may not recover the commander’s “true intent,” but they satisfy agreement.

3. General oral-message lower bound

For n=7 and m=2, 7>6 holds, so the participant-count precondition is satisfied and the recursive oral-message construction can tolerate at most two traitors under its assumptions. For n=6, 6>6 is false. For n=10 and m=3, 10>9 holds. Passing the inequality is necessary, but correct rounds, relaying, majority, defaults and channels are still required.

4. What signatures change

In a three-general SM(1) example, a traitorous commander signs ATTACK for B and RETREAT for C. The loyal lieutenants forward both signed orders, so each obtains the same set {ATTACK, RETREAT} and applies the same specified default, say RETREAT. The commander’s equivocation is attributable.

Signatures prevent a loyal participant’s order from being forged or altered undetectably under the model. They do not reveal which of two orders reflects a traitor’s real intent, guarantee timely delivery, or prevent an attacker controlling a legitimate private key from signing both.

Risks and review failures

Problem and model

  • Retelling the allegory without precise agreement, validity and termination conditions.
  • Treating the Byzantine Generals Problem as a historical siege, a single algorithm or a synonym for blockchain.
  • Mixing it with the Two Generals problem, which centers on common knowledge over an unreliable channel.
  • Adding undetectable permanent message loss while citing a theorem whose oral-message assumptions exclude it.
  • Applying n>3m to every authenticated, asynchronous, weighted, permissionless or resource-based protocol.
  • Calling crash, omission, equivocation, arbitrary computation, faulty channels and key compromise the same fault.
  • Assuming participant count equals independent entities, stake, hash power or committee weight.
  • Omitting the distinction between a loyal commander and a traitorous commander in the validity condition.

Algorithm and implementation

  • Checking only the final majority without tracing recursive sender paths and each loyal participant’s local view.
  • Using different missing-message defaults, tie rules, membership snapshots or message ordering across implementations.
  • Accepting messages without binding protocol, chain, task, height, round, value, sender and membership epoch.
  • Replaying or splicing messages across executions, rounds, forks, networks or membership changes.
  • Assuming signatures prove truth, freshness, authorization context, delivery, availability or honest key custody.
  • Quoting OM(m) or SM(m) without implementing the required rounds, forwarding, verification and connectivity.
  • Testing only one traitor placement instead of commander, lieutenant, colluding, omission and equivocation cases.

Deployment and interpretation

  • Claiming a consensus protocol “solves Byzantium” without its exact safety, liveness and network assumptions.
  • Treating agreement on bytes as proof that application execution or an off-chain fact is correct.
  • Ignoring common clients, operators, clouds, key systems or governance that correlate nominally separate participants.
  • Crediting deposits, minting bridged assets or settling irreversible actions before the required finality condition.
  • Inferring decentralization, asset safety, legal truth or token value from a fault-tolerance label.

Common misconceptions

  • The problem is simply a 51% attack. It concerns arbitrary and conflicting behavior under a defined agreement model; resource-majority attacks belong to particular protocols.
  • A majority always solves it. In the classic oral-message model, tolerating m traitors requires more than three times that number of total participants, not merely one more honest participant than traitors.
  • Digital signatures prove that a message is true. They can authenticate a key and protect integrity; a malicious or compromised key can still sign false or conflicting content.
  • Unreliable delivery is already covered by the original oral-message result. That result includes explicit delivery, sender-identity and detectable-omission assumptions; other timing and channel models need other results.
  • Agreement means the system learned reality. Loyal nodes can agree on invalid application output or incorrect external data unless separate validation rules prevent it.

Sources

Navigation

Search the wiki...