Byzantine faults

Four banks in a small country settle transfers between them on a shared ledger. Each bank runs one node, and every node must hold the same list of transfers in the same order. Raft would handle a node that crashes (Consensus & leader election). But the banks don't control each other's servers, and a node that is compromised, misconfigured or simply buggy doesn't stop. It answers, and its answers are wrong.

The name comes from a framing of the problem as generals of the Byzantine army agreeing on a plan while some of them are traitors. Telling different peers different things, as bank C does above, is the hard case: each honest node sees a consistent story, and only by comparing notes can they find out the stories differ (Why distributed systems are hard).

Byzantine behavior doesn't need an attacker. Large fleets see CPU cores that silently compute wrong results, called mercurial cores, at a rate of a few per several thousand machines: hundreds of them across hundreds of thousands of machines. Nothing crashes and no error is logged; the only symptom is a wrong answer. Examples from large fleets include database index corruption and an encryption result that only the faulty core could decrypt.

Storage and networks have long had defenses for this: error-correcting codes, checksums from end to end, and scrubbing stored data for corruption. Computation is harder, because there's no cheap check for an arbitrary result. Google has written self-checking versions of critical functions, such as encryption and compression, and is willing to pay for double or triple computation where a wrong answer is costly. The banks' nodes face the same risk, before anyone is malicious.

A crash-tolerant cluster needs 2f + 1 nodes to survive f failures: any two majorities share a node, and every node tells the truth. With liars, that's not enough.

The argument goes like this. A node must be able to move on after hearing from n − f nodes, since f may never answer. But the f that stayed silent may be honest and slow, so f of the n − f that did answer may be liars. The honest answers must still outnumber the lies: n − 2f > f, so n ≥ 3f + 1.

The same numbers explain the voting. With 3f + 1 nodes, a quorum is 2f + 1. Two quorums overlap in at least f + 1 nodes, so at least one honest node is in both, and it won't vote for two conflicting orders. For the banks, a quorum is 3 of 4.

With plain messages the bound is proven: with three generals, no algorithm survives one traitor. Unforgeable signatures remove that bound, in a model where a missing message can always be detected. On a real network, where delays have no limit, 3f + 1 is still the minimum for staying both correct and live.

Practical Byzantine Fault Tolerance (PBFT), from 1999, was the first replication protocol to survive Byzantine faults correctly on an asynchronous network, and fast enough to use. One node is the primary and proposes an order; the others don't trust it, so they check it with each other before acting:

Each phase has a job. Pre-prepare carries the primary's proposal: transfer T gets sequence number 812. Prepare has every node tell every other what it received, so a primary that sends different proposals to different nodes can't get two orders accepted. Commit makes sure the order survives even if the primary is replaced. The client, here the bank that submitted T, waits for f + 1 = 2 matching replies, since at least one of them must be honest.

If the primary stalls or misbehaves, the others vote it out in a view change and the next node takes over. Messages are authenticated, so no node can forge another's vote; PBFT uses message authentication codes, about a thousand times faster to compute than signatures. A file service replicated with PBFT ran only 3% slower than an unreplicated one.

The cost is the everyone-to-everyone rounds: with n nodes, each phase sends about n × (n − 1) messages. That's 12 for the four banks, but 9,900 for 100 nodes, which is why classic BFT groups stay small.

BFT voting counts nodes, so it needs a fixed, known list of who votes. The banks have that: four signed-up members with known keys. On an open network anyone can start nodes, and one attacker could start a thousand. One vote per IP address could be subverted by anyone able to allocate many addresses.

Proof of work makes a vote cost computing power, one CPU one vote, so faking a thousand voters means paying for a thousand voters' work. CometBFT keeps PBFT's shape, with propose, prevote and precommit steps and more than two-thirds of voting power needed to commit, but counts voting power instead of nodes. Bitcoin instead follows the longest chain, which becomes harder to reverse with every block added after a transaction.

Inside one company, the usual consensus protocols are crash tolerant: Raft and Paxos assume nodes may stop but never lie, and Hyperledger Fabric's Raft ordering service, for one, is crash fault tolerant only. That's reasonable when one team runs every node, because BFT's extra nodes and messages buy protection against a threat the company mostly doesn't face, an operator attacking their own cluster.

The Byzantine faults a single company does face, corrupt bits and wrong computations, are handled with cheaper, targeted checks. The banks use both: BFT between banks, and checks inside each one: