Byzantine Fault Tolerance & PBFT

Why arbitrary faults require 3f+1 replicas and 2f+1 certificates, how quorum intersection prevents conflicting decisions, and how PBFT turns those bounds into a practical partially synchronous protocol.

budding deep of deep confidence: certain planted 2026-08-21 tended 2026-08-21 bftpbftquorumpartial-synchronyconsensus

A crash-faulty process stops; a Byzantine process can lie, equivocate, collude, and send different authenticated messages to different peers. Byzantine fault tolerance (BFT) is the family of protocols that still keeps correct replicas from deciding conflicting histories under that stronger fault model.

The threshold comes from quorum intersection #

To tolerate at most $f$ Byzantine replicas, classical authenticated BFT uses $n \ge 3f+1$ replicas and decision certificates containing at least $2f+1$ votes.

Any two such quorums intersect in at least

2(2f+1)-(3f+1)=f+1

replicas. Since at most $f$ are Byzantine, the intersection contains at least one correct replica. If correct replicas never cast conflicting votes in the relevant protocol phase, two conflicting certificates cannot both exist.

This algebra is the real content behind the Byzantine Generals story. The story is useful intuition; the quorum invariant is what implementations depend on.

Safety is not liveness #

The FLP result rules out deterministic consensus that guarantees termination in a fully asynchronous network with even one crash. Real BFT protocols therefore state a timing model. Under partial synchrony, there is an unknown global stabilization time after which messages arrive and correct processes take steps within some bound. Timeouts may be wrong before then; after then, increasing timeouts eventually become long enough for progress.

Safety must not depend on a timeout being accurate. A slow network and a dead leader are observationally identical, so a timeout can justify changing leader or round, but never justify deciding a conflicting value.

PBFT's normal path #

PBFT runs a primary and backups in a numbered view. For one client request:

sequenceDiagram
  participant C as Client
  participant P as Primary
  participant B1 as Backup 1
  participant B2 as Backup 2
  participant B3 as Backup 3
  C->>P: signed request
  P->>B1: PRE-PREPARE(view, seq, digest)
  P->>B2: PRE-PREPARE(view, seq, digest)
  P->>B3: PRE-PREPARE(view, seq, digest)
  B1-->>P: PREPARE
  B2-->>P: PREPARE
  B3-->>P: PREPARE
  Note over P,B3: prepare certificate
  P-->>B1: COMMIT
  B1-->>B2: COMMIT
  B2-->>B3: COMMIT
  Note over P,B3: 2f+1 commits → execute
  P-->>C: reply
  B1-->>C: reply

PRE-PREPARE assigns a request digest to a sequence number. PREPARE makes replicas agree that the assignment is visible across a quorum, not merely claimed by the primary. COMMIT proves that enough replicas are prepared that the assignment will survive a view change. Authentication prevents forged votes; it does not prevent a Byzantine replica from signing two values, which is why certificates and intersection matter.

The client waits for $f+1$ matching replies: at least one must come from a correct replica. Checkpoints and watermarks bound the retained log. A view-change protocol moves to a new primary while carrying forward prepared requests that are safe to preserve.

What the guarantee does and does not say #

Condition	Consequence
At most $f$ Byzantine among $3f+1$	safety; liveness after synchrony stabilizes and a correct leader has enough time
Network partition leaves fewer than $2f+1$ reachable	no progress, preserving safety
More than $f$ Byzantine	protocol guarantee is void; accountability evidence may still identify equivocation
Keys stolen from $f+1$ validators	cryptographically indistinguishable from those validators being Byzantine

Where the fundamentals appear #

System	How the consensus ideas are used
Tendermint / CometBFT	A known, voting-power-weighted validator set proposes blocks and forms greater-than-two-thirds prevote/precommit certificates. Locks and round changes preserve safety across competing proposals. This is a direct blockchain application of authenticated BFT quorum reasoning.
Ethereum proof of stake	Validators use stake-weighted supermajority links to justify and finalize checkpoints, while a separate fork-choice rule selects the current head. It shares quorum-intersection and accountable-safety ideas with BFT protocols but is not PBFT or Tendermint.
Bitcoin	Miners extend competing histories with proof of work and nodes follow the valid chain with the most accumulated work. There is no fixed validator quorum or finalizing vote; confidence grows probabilistically with confirmations.

The reusable lesson is to identify the fault model, membership model, decision evidence, and finality rule before comparing systems. Similar words such as “two thirds,” “majority,” or “confirmation” do not imply the same guarantee.

Cost and scaling #

PBFT's all-to-all prepare/commit traffic is $O(n^2)$ messages in the simple form, so it fits tens or hundreds of known validators better than millions of anonymous participants. Aggregated signatures, collectors, pipelining, and committee selection reduce bytes or critical-path fan-out, but they do not remove the underlying need for independently checkable quorum evidence.

The 1999 paper's throughput numbers are historical, not a present benchmark. Its durable contribution is the protocol structure, recovery path, and the separation of safety from timing-dependent liveness.