Byzantine Fault Tolerance (PBFT)

Why Byzantine fault tolerance matters

Most fault-tolerant systems assume the kindest possible failure: a node either works correctly or stops entirely. That is the crash-stop or fail-stop model, and it is what Paxos and Raft are built for. But real systems fail in nastier ways. A corrupted disk returns garbage that passes a checksum. A buggy replica double-replies. A compromised validator in an open financial network actively lies to steal money. In every one of these cases a node sends messages that are not merely absent — they are wrong, and worse, they can be inconsistent: one story to node A, a contradictory story to node B. This is a Byzantine fault, named after the generals who might be traitors.

Byzantine fault tolerance is what lets a group of replicas keep a single, agreed-upon history of operations even when a bounded number of them are actively adversarial. The payoff is enormous: it is the theoretical foundation of every system where mutually distrusting parties must share one ledger — cryptocurrency validators, cross-bank settlement networks, aircraft flight-control voting, and the ordering service of permissioned blockchains. When the participants have money or lives riding on the outcome and no reason to trust each other, crash tolerance is not enough. You need to tolerate malice.

The Byzantine Generals Problem

In their 1982 paper The Byzantine Generals Problem, Leslie Lamport, Robert Shostak, and Marshall Pease dressed the abstraction in a memorable allegory. Several divisions of the Byzantine army surround an enemy city. Each division is commanded by a general, and the generals can communicate only by messenger. They must agree on a common battle plan — attack or retreat — because a half-hearted, split attack is the worst outcome of all. The trouble: some generals may be traitors who deliberately send conflicting orders to sow confusion, and a messenger's word cannot be independently verified.

The requirement is captured by two properties that any Byzantine agreement protocol must guarantee:

• Agreement (consistency). All loyal generals decide on the same plan.
• Validity. If the commanding general is loyal, every loyal general follows the order the commander actually sent.

Their central result is a hard impossibility bound. With oral messages — unauthenticated, so a traitor can relay any value it likes without detection — agreement is achievable if and only if more than two-thirds of the generals are loyal. In fault terms: to tolerate f traitors you need n ≥ 3f + 1 generals total. With three generals and one traitor, agreement is provably impossible; you need four. If messages can be signed with unforgeable digital signatures ("written" messages), a traitor can no longer forward a different value than it received, and agreement becomes possible for any number of traitors — at the cost of the cryptographic machinery.

Why exactly 3f + 1 nodes?

The 3f+1 bound is the single most important number in this field, and it falls out of a quorum-intersection argument. Suppose we have n replicas and want to tolerate f Byzantine ones. When we make a decision we cannot wait for all n replies, because up to f nodes might be faulty and simply never answer. So a decision can commit after collecting replies from a quorum of only n − f replicas.

Now two dangers must be defeated simultaneously:

• Availability. The quorum of size n − f must be reachable even if f nodes are down. That is automatic.
• Consistency. Any two quorums must overlap in at least one honest node, so a second decision cannot contradict the first. Two quorums of size n − f intersect in at least (n − f) + (n − f) − n = n − 2f nodes. Of those, up to f could be Byzantine and lie about what they saw, so the honest overlap is n − 2f − f = n − 3f. We need that to be at least 1, giving n ≥ 3f + 1.

The clean way to remember it: the quorum size is 2f + 1 (that is n − f when n = 3f + 1). Any two 2f+1 quorums out of 3f+1 nodes share at least one honest replica, because their overlap is at least 2(2f+1) − (3f+1) = f + 1 nodes, and at most f of those can be faulty — leaving one honest node in common to carry the decision forward.

How PBFT works, step by step

PBFT is a state-machine replication protocol: all replicas run the same deterministic service and must apply client requests in the same total order. One replica is the primary (leader) for the current view; the others are backups. A view number v identifies which replica is primary — replica (v mod n). Every message is authenticated (MACs in the original PBFT, signatures in many descendants), so replicas can prove what they received.

The happy path for a single request runs through three phases:

1. Pre-prepare. The client sends the request to the primary. The primary assigns it a sequence number n in the current view v and multicasts <PRE-PREPARE, v, n, d> (where d is a digest of the request) to all backups. This fixes the ordering the primary proposes.
2. Prepare. Each backup that accepts the pre-prepare multicasts <PREPARE, v, n, d, i> to everyone. A replica is prepared for the request once it holds the pre-prepare plus 2f matching prepares from other replicas — that is 2f+1 replicas including itself agreeing on (v, n, d). This guarantees that no two honest replicas can be prepared for different requests with the same (v, n): it pins the order within a view.
3. Commit. Once prepared, each replica multicasts <COMMIT, v, n, d, i>. A replica is committed-local when it holds 2f+1 matching commits (including its own). Only then does it execute the request and reply to the client. This second all-to-all round is what makes the decision survive a view change — even if the primary is later replaced, a committed request stays committed, because a 2f+1 commit quorum intersects any future prepared quorum in an honest node.

The client waits for f + 1 matching replies from different replicas before accepting a result. Since at most f replicas are faulty, f+1 identical replies guarantee at least one honest replica vouches for the answer. Two all-to-all rounds are why PBFT costs O(n²) messages per request.

View change: replacing a faulty primary

A Byzantine primary can misbehave by ignoring requests, assigning duplicate sequence numbers, or equivocating. Backups run a timer on the request they forwarded; if it expires without progress, they broadcast a VIEW-CHANGE message carrying proof of their latest prepared state (the pre-prepare and 2f matching prepares). When the new primary — replica (v+1 mod n) — collects 2f+1 VIEW-CHANGE messages, it broadcasts a NEW-VIEW that re-proposes any request that might have committed, and the protocol resumes. Quorum intersection guarantees no committed request is lost across the transition. This machinery is why PBFT preserves safety even under full asynchrony and only relies on eventual synchrony (partial synchrony) for liveness — a direct consequence of the FLP impossibility result, which forbids a deterministic protocol that is both always-safe and always-live under asynchrony.

BFT vs crash tolerance vs Nakamoto consensus

	PBFT / classical BFT	Paxos / Raft (CFT)	Nakamoto (proof-of-work)
Fault model	Arbitrary / Byzantine	Crash-stop only	Byzantine, probabilistic
Nodes for f faults	3f + 1	2f + 1	> 50% honest hash power
Quorum	2f + 1	f + 1 (majority)	Longest chain
Membership	Known, fixed set	Known, fixed set	Open / permissionless
Finality	Instant, deterministic	Instant, deterministic	Probabilistic (waits k blocks)
Message complexity	O(n²) per request	O(n) per request	O(n) gossip
Needs cryptographic auth	Yes (MAC / signatures)	No	Yes (PoW + signatures)
Typical scale	Tens of replicas	3–7 replicas	Thousands of miners

The headline trade-off: Byzantine tolerance buys you protection against liars, but it costs a bigger cluster (3f+1 instead of 2f+1), an extra voting round, cryptographic authentication, and quadratic message blow-up. That quadratic cost is exactly why classical BFT tops out at tens of validators and why newer protocols work hard to shrink it.

How a PBFT replica works (pseudocode)

# One replica in a PBFT cluster of n = 3f + 1 replicas.
# Quorum = 2f + 1. All messages are authenticated (MAC or signature).

QUORUM = 2 * f + 1          # = n - f

def on_client_request(req):
    if i == primary(view):          # replica (view mod n) is primary
        seq = next_sequence_number()
        digest = hash(req)
        log[(view, seq)] = req
        multicast(("PRE-PREPARE", view, seq, digest))
    else:
        forward_to_primary(req)     # start a view-change timer

def on_pre_prepare(view, seq, digest, from_primary):
    if not valid(from_primary) or seq_out_of_range(seq):
        return                      # reject; may trigger view change
    accept_pre_prepare(view, seq, digest)
    multicast(("PREPARE", view, seq, digest, i))

def on_prepare(view, seq, digest, j):
    record_prepare(view, seq, digest, j)
    # 2f matching PREPAREs + the PRE-PREPARE => 2f+1 replicas agree on order
    if count_prepares(view, seq, digest) >= 2 * f and have_pre_prepare(view, seq, digest):
        mark_prepared(view, seq, digest)
        multicast(("COMMIT", view, seq, digest, i))

def on_commit(view, seq, digest, j):
    record_commit(view, seq, digest, j)
    # 2f+1 matching COMMITs => decision survives any future view change
    if count_commits(view, seq, digest) >= QUORUM and is_prepared(view, seq, digest):
        result = execute_in_order(seq, log_request(digest))
        send_to_client(("REPLY", view, seq, i, result))
        # Client accepts once it holds f+1 matching REPLYs from distinct replicas.

def on_request_timeout():
    # Suspect a faulty primary: broadcast proof of prepared state.
    multicast(("VIEW-CHANGE", view + 1, prepared_certificate(), i))

Two subtleties an implementer must get right. First, a replica must not act on a COMMIT until it is itself prepared for that (view, seq, digest) — otherwise a faulty primary could push it to execute an order the honest majority never certified. Second, the counts are on distinct senders; a Byzantine replica that floods duplicate messages must not be counted twice, which is why each vote is keyed by sender identity j.

Common misconceptions and pitfalls

• "BFT means unlimited faults." No — it tolerates a bounded f. If more than f nodes are Byzantine, all guarantees evaporate: two conflicting values can commit. The bound f = ⌊(n−1)/3⌋ is a design parameter, not a magic shield.
• "More nodes always means more safety." Adding nodes without adjusting f can hurt: 3f+1 must hold. Seven nodes tolerate f=2; going to eight nodes still only tolerates f=2 (since 3·2+1 = 7 ≤ 8 but 3·3+1 = 10 > 8), while paying more O(n²) traffic for nothing.
• "PBFT gives liveness under asynchrony." It does not, and cannot — FLP forbids it. PBFT is always safe, but it only makes progress during periods of partial synchrony when the network delivers messages within a bound. A perfectly Byzantine network scheduler can stall it forever without ever violating agreement.
• "The primary decides the value." The primary only proposes an order. The two voting rounds mean a faulty primary cannot force an inconsistent commit; the worst it can do is stall progress until a view change replaces it.
• "Signatures make 3f+1 unnecessary." Signatures help — they defeat message-relaying attacks and are needed across view changes — but PBFT still keeps 3f+1 because the quorum-intersection argument for liveness plus safety under asynchrony requires it, independent of authentication.

Byzantine fault tolerance in the wild

• Permissioned blockchains. Hyperledger Fabric's ordering service and many consortium chains run PBFT-style consensus among a known validator set to get instant, deterministic finality — no waiting for confirmations.
• Proof-of-stake finality. Tendermint (Cosmos) and HotStuff/LibraBFT (the lineage behind Diem and Aptos) are direct PBFT descendants. HotStuff replaces the two all-to-all rounds with a leader-collected, threshold-signature pipeline that cuts steady-state cost to O(n), enabling hundreds of validators.
• Aerospace and avionics. Flight-control and engine systems use Byzantine-tolerant voting (e.g. the SAFEbus / Boeing 777 architecture) so a single lying sensor or channel cannot corrupt a control decision.
• Cross-organization coordination. Any setting where mutually distrusting operators must share one authoritative log — settlement networks, certificate transparency logs, decentralized identity — is a candidate for BFT ordering.

The through-line from 1982 to today is unbroken: Lamport's generals framed the impossibility, PBFT made it practical, and the blockchain era turned it into infrastructure that moves billions of dollars. Every one of those systems is still living inside the same 3f+1 constraint.