Byzantine Fault Tolerance (BFT)

The ability of a distributed system to reach correct consensus even when some nodes send arbitrary, conflicting, or malicious messages rather than merely crashing.

Practical example

Hyperledger Fabric's ordering service uses BFT-style consensus so that mutually distrusting organisations sharing a ledger can agree on transaction order even if one participant's node is compromised or acts maliciously.

Byzantine Fault Tolerance addresses failure modes that go beyond the fail-stop model assumed by protocols like Raft or Paxos. A Byzantine node can lie differently to different peers, replay stale messages, equivocate on votes, or collude with other faulty nodes — behavior indistinguishable from a compromised host or a buggy implementation sending garbage. Classical CFT (crash-fault-tolerant) systems tolerate f failures with 2f+1 nodes; BFT systems require 3f+1 nodes to tolerate f Byzantine actors, because the protocol must be able to out-vote both the faulty nodes and any honest nodes they successfully confuse via conflicting messages.

The canonical construction is PBFT (Practical Byzantine Fault Tolerance), which uses a three-phase message pattern (pre-prepare, prepare, commit) with quadratic O(n²) message complexity per view, since every node must communicate with every other node to detect equivocation. Modern variants like HotStuff (used in Diem/LibraBFT and several blockchain stacks) linearize this to O(n) per round using a rotating leader and threshold signatures, making BFT viable at larger cluster sizes. View changes — the BFT equivalent of leader election — are notoriously complex because the protocol must prove to all honest replicas that the previous leader was faulty without itself becoming a vector for a Byzantine leader to stall progress indefinitely (a liveness attack, not just a safety violation).

Outside of public blockchains, BFT shows up in permissioned multi-party systems: cross-organization ledgers (Hyperledger Fabric’s ordering service), aerospace/avionics flight control computers voting on sensor input, and any control plane spanning trust boundaries where one party’s infrastructure cannot be assumed honest even under normal operation. It is deliberately not used inside a single trust domain — etcd, Zookeeper, and CockroachDB all use CFT consensus because within one operator’s blast radius, crash-fault assumptions hold and the 3x replication overhead plus cryptographic signature cost of BFT is pure waste.

Cost: BFT typically requires digital signatures or MACs on every consensus message to prevent forgery, adding CPU and latency overhead absent in CFT.
Cluster sizing: Tolerating even 1 Byzantine node requires 4 replicas minimum (3f+1 with f=1), versus 3 for CFT tolerating 1 crash.
Common failure: Engineers apply BFT reasoning to single-tenant infra where crash-fault assumptions are correct, over-provisioning nodes and adding signature verification latency for a threat model that doesn’t exist in that trust boundary.