Byzantine Failures, and Why You Probably Do Not Assume Them

The name comes from a thought experiment about generals coordinating an attack when some of them may be traitors, and it is unfortunate in one respect: it makes people think of malice, when the model is simply *unconstrained behaviour*. Under a crash model, a node’s only permitted misbehaviour is to stop. Under a Byzantine model it may do anything the protocol allows a message to express, including things no honest implementation would do.

The behaviours worth having in mind: equivocation — telling node A one thing and node B another, which is the behaviour that breaks quorum arguments, since two nodes can each hold a majority-backed but different view. Well-formed falsehood — a value that passes every validation and is simply wrong. Selective participation — behaving correctly except in the specific circumstances that matter, which is indistinguishable from bad luck. Delayed betrayal — behaving correctly for a long time, which is why "it has been fine so far" is not evidence.

The causes are more mundane than the name suggests. Memory bit flips in a machine without ECC. A storage device returning stale or corrupted blocks after an incomplete write. A firmware bug. Two versions of a service deployed simultaneously with an incompatible interpretation of the same field. A compromised host. Only the last one involves an adversary, and the first two occur at measurable rates in any large fleet.

The arithmetic is worth understanding because it explains the cost. With n nodes and up to f faulty, you must be able to make progress after hearing from only n − f nodes, since the faulty ones may simply never answer. Among those n − f responses, up to f may be from Byzantine nodes telling you something false. So the honest responses number at least n − 2f, and for the honest ones to outnumber the false ones you need n − 2f > f, giving n > 3f. Hence 3f+1.

Contrast the crash case: a node that fails simply does not answer, so every answer you receive is honest. You need only that any two quorums intersect, giving n > 2f. The entire extra cost of Byzantine tolerance comes from the fact that a received answer might be a lie, and therefore cannot be counted as evidence on its own.

The second cost, equally important, is that a quorum is no longer sufficient on its own. A Byzantine node can equivocate, so nodes must also verify that everyone was told the same thing — which requires an extra communication phase where nodes exchange what they heard. That is why Byzantine protocols have more rounds, and why their message complexity grows faster with cluster size.

Almost every distributed database, queue and coordination service in common use assumes non-Byzantine faults, and that is a reasonable engineering decision when all participants are inside one trust boundary and one operator. The threats the model would address are cheaper to handle by other means: TLS prevents tampering in transit, access control prevents unauthorised participants, code review and deployment controls address the compromised-host case, and — critically — checksums address corruption.

That last one deserves emphasis, because it is the Byzantine fault that actually occurs. A storage device returning a corrupted block is a node giving a well-formed wrong answer, which is Byzantine by definition. The response is not a Byzantine consensus protocol; it is end-to-end checksums, so the wrong answer is detected as wrong rather than voted on. This is a targeted defence against the specific arbitrary behaviour that happens in practice, at a rounding error of the cost — and it is worth checking whether your storage layer, your network protocol and your application actually have it, because the assumption that "something below me checksums this" is frequently false.

Where the choice genuinely flips is when participants are outside your trust boundary: a public ledger where anyone may join, a consortium where the members are separate legal entities with conflicting interests, or a safety-critical system where a sensor may fail in an arbitrary rather than a fail-stop manner. In those settings the extra node and the extra round are the price of the problem, not overhead.

You do not have to choose between full Byzantine tolerance and nothing. Several cheap practices buy meaningful protection against the arbitrary behaviours that actually occur.

Verify rather than trust. Where one component computes something another depends on, having the consumer check the result — a checksum, a re-derived total, a range assertion — turns a silent wrong answer into a loud one. This is defence in depth applied to correctness rather than to security.

Make claims attributable. Signed or at least authenticated messages mean that when something wrong appears, you can determine which component produced it. Without attribution, a corrupted value propagated through three services is nearly impossible to trace to its origin.

Cross-check independent derivations. Where two systems should agree — a ledger and an accounting system, a search index and its source — a periodic comparison catches arbitrary faults that no individual health check would. This is the same reconciliation machinery that partial failure requires, doing double duty.

Treat clients as Byzantine, always. This one is not optional. Anything outside your trust boundary — a browser, a mobile app, a partner integration — may send arbitrary input, and the server must validate rather than trust. Security owns this thoroughly, and it is worth noticing that it is the same model: you simply already apply Byzantine assumptions at the edge, and choose not to apply them internally.