Byzantine Fault Tolerance & BFT Consensus

When nodes can lie

Most consensus you will design assumes the crash-stop failure model: a faulty node either follows the protocol correctly or halts. It never lies. Under that model, Raft and Paxos tolerate f failures with 2f+1 nodes, because any two majority quorums of f+1 overlap in at least one node carrying the committed truth forward.

The Byzantine model drops the honesty assumption. A Byzantine node can send wrong values, equivocate (tell node A "the value is X" and node B "the value is Y" in the same round), forge or replay messages, selectively drop, or collude with other faulty nodes. The name comes from the Byzantine Generals Problem: generals agreeing to attack or retreat while traitors send contradictory orders. The crucial difference: a crash is detectable-ish (silence) whereas a lie is actively deceptive: the node participates, so you cannot wait it out.

Why 3f+1

To make a decision you need a quorum that (a) still forms even if the f liars refuse to participate, and (b) is large enough that the honest members of any two quorums overlap despite the liars. With 3f+1 total, a quorum of 2f+1 always contains at least f+1 honest nodes, so any two quorums share at least one honest node, and honest nodes always outvote the f liars. Concretely: tolerating 1 Byzantine node needs 4 nodes, not 3; tolerating 2 needs 7. You pay f extra nodes purely to survive lies rather than silence.

The other cost is messages. Because a node cannot trust a single report, classic BFT makes everyone cross-check everyone: O(n²) messages per decision, versus Raft's near-linear cost. Protocols to name:

• PBFT (Castro-Liskov 1999): the classic. Three phases (pre-prepare, prepare, commit), a primary that proposes, and a view-change protocol to depose a faulty primary. O(n²) messages.
• Tendermint (Cosmos): BFT with a rotating proposer, suited to proof-of-stake chains.
• HotStuff (Meta's former Diem): reduces message complexity to linear O(n) via threshold signatures and adds pipelining. The modern reference.

The threat-model decision

BFT is justified when participants are mutually distrusting or potentially compromised: public blockchains, some cross-organization financial settlement, hardware fault domains with undetectable silent corruption. It is over-engineering when all nodes sit inside one trusted datacenter under one operator: there, the realistic failures are crashes, disk faults, and partitions, not malice. Raft plus checksums (bit rot), TLS (tampering in transit), and authentication (unauthorized actors) covers the plausible threats at a fraction of BFT's node count and latency.

Interview nuance: the sophisticated answer is not "BFT is more robust so use it." It is a threat-model decision: state who the participants are and whether any could be adversarial. If yes, BFT (name HotStuff for scale). If one trusted operator, say so and pick Raft plus checksums/TLS/auth.

Recap: crash-stop consensus (2f+1) assumes nodes may halt but never lie; the Byzantine model allows lying, equivocation, and collusion, forcing 3f+1 nodes and often O(n²) messages (PBFT, or linear HotStuff); use BFT only across real trust boundaries and Raft plus checksums/TLS/auth inside one trusted operator.