PBFT.

For sixteen years after the Byzantine Generals paper (6.1), practical Byzantine fault tolerance remained mostly a theoretical curiosity — the known protocols were too slow for real systems. Miguel Castro and Barbara Liskov's 1999 PBFT (Practical Byzantine Fault Tolerance) changed that, delivering the first BFT protocol with performance close enough to non-Byzantine systems to be genuinely usable in practice. This article covers PBFT's three-phase normal-case protocol (pre-prepare, prepare, commit), its view-change mechanism, and — the piece that makes everything work — how digital signatures and message authentication codes replace the "trust the overlap node" assumption that article 6.1 showed Byzantine failures break.

Why earlier BFT protocols were impractical

The original Byzantine Generals protocols (article 6.1) required a number of message rounds proportional to f — meaning to tolerate a modest number of simultaneous faults, the protocol needed many sequential rounds of communication, each adding real latency. For anything beyond toy fault-tolerance levels, this made the protocols too slow for practical, latency-sensitive production use. PBFT's core engineering achievement was reducing this to a small, constant number of message phases regardless of f — the same qualitative leap Multi-Paxos (article 5.3) made over naive per-entry Paxos, but for the much harder Byzantine setting.

The normal-case protocol: three phases

PBFT operates in a sequence of views (yes, the same term VR used in article 5.4 — PBFT's authors were working in the same MIT lab lineage as Liskov's earlier VR work, and the terminology directly carries over), each with a designated primary. A client sends a request to the primary, which then drives three phases among all replicas:

Phase 1: Pre-Prepare

The primary assigns the request a sequence number and broadcasts a PRE-PREPARE(view, seq, digest) message, digitally signed, to all backups. This is the primary's proposal — directly analogous to article 5.2's Paxos Phase 2 Accept, or article 5.6's Raft AppendEntries.

Phase 2: Prepare

Each backup, upon accepting a valid pre-prepare, broadcasts a signed PREPARE(view, seq, digest, replica_id) to every other replica (not just back to the primary — this all-to-all broadcast is a key structural difference from Phase 5's leader-centric message flow, and it's the direct mechanism that lets replicas verify agreement without needing to fully trust the primary). A replica considers a request prepared once it has collected 2f matching Prepare messages from distinct replicas (plus its own), for a total of 2f+1 — chosen specifically because, per article 6.1's 3f+1 threshold, 2f+1 is guaranteed to include a majority of honest nodes even if all f faulty nodes participate.

Phase 3: Commit

Once prepared, each replica broadcasts a signed COMMIT(view, seq, digest, replica_id) to all others. A replica considers the request committed (and executes it, replying to the client) once it has collected 2f+1 matching Commit messages — a second round of cross-verification, ensuring that a sufficient number of replicas have independently confirmed they each saw the same prepared certificate, closing off a specific attack where a faulty primary might show different "prepared" sets to different subsets of replicas.

Client -> Primary:                REQUEST

Primary -> all Backups:           PRE-PREPARE(view, seq, digest)   [signed]

Each replica (incl. primary)
  -> all other replicas:          PREPARE(view, seq, digest, id)   [signed]
  (once 2f matching PREPAREs + own pre-prepare/prepare = 2f+1: request is PREPARED)

Each replica -> all others:       COMMIT(view, seq, digest, id)    [signed]
  (once 2f+1 matching COMMITs: request is COMMITTED -> execute, reply to client)

Why digital signatures are load-bearing, not optional

This is the direct payoff for article 6.1's oral-vs-signed message discussion. Every message in PBFT is digitally signed (or, in performance-optimized variants, authenticated with message authentication codes). This closes off exactly the attack article 6.1's Fig 1 illustrated — a Byzantine node cannot forge a message claiming to be from another replica, and cannot alter a message in transit without detection, because any tampering invalidates the signature. This is precisely why PBFT can operate with the theoretical minimum 3f+1 nodes: the cryptography does real, load-bearing work that the original unsigned oral-message protocols couldn't rely on, letting PBFT hit the tightest bound article 6.1 proved achievable.

View changes: Byzantine-tolerant leader election

When backups suspect the primary is faulty (either genuinely crashed, or — the new wrinkle this phase introduces — actively misbehaving, such as sending inconsistent pre-prepares to different replicas), they trigger a view change, PBFT's Byzantine-hardened analog of article 4.2/5.5's leader election. Replicas broadcast signed VIEW-CHANGE messages containing proof of their prepared certificates (the 2f+1 matching Prepare messages, individually signed and therefore independently verifiable by any recipient — not just trusted on the replica's word alone). The new primary collects 2f+1 such view-change messages, and — cryptographically verifiable, unlike Phase 5's simple "trust the reported log" comparisons — can prove to every replica exactly which requests were already prepared, ensuring no committed work is lost across the leadership change, the same safety guarantee article 5.6 proved for Raft, now re-derived under a strictly harder adversarial model with cryptographic backing instead of simple trust.

Why blockchains adopted PBFT-family protocols

PBFT's practical efficiency, combined with its explicit design for a threat model where participants might be actively adversarial (exactly the situation in any open, permissionless or semi-permissionless network where you can't assume every validator is honestly operated), made it and its direct descendants the foundation for a large fraction of blockchain consensus design — a connection this series will trace explicitly through HotStuff (6.3) and Tendermint (6.4), both of which build directly on PBFT's core ideas while addressing specific scalability limitations PBFT's original design has at very large validator-set sizes (the all-to-all O(n²) message complexity in Prepare/Commit becomes a real bottleneck as n grows into the hundreds or thousands — precisely the scale many blockchain networks operate at).

FAQ

Is PBFT's O(n²) message complexity a fundamental limit, or an artifact of this specific protocol?

It's specific to PBFT's design (the all-to-all Prepare/Commit broadcast), not a fundamental Byzantine-agreement limit — this is exactly the scalability gap HotStuff (article 6.3) is built to close, using a linear, leader-centric communication pattern instead, while preserving BFT safety.

Does PBFT tolerate network partitions the same way crash-fault algorithms do?

Yes, in spirit — PBFT remains safe (never commits conflicting requests) under any network conditions, and remains live (continues committing new requests) as long as at least 2f+1 replicas can communicate with reasonably bounded delay, directly paralleling article 2.5's partial-synchrony escape hatch, just requiring a larger surviving quorum (2f+1 out of 3f+1, rather than a simple crash-fault majority) due to the Byzantine threat model.

Can a client be tricked by a faulty primary into thinking a request committed when it didn't?

No — a client only accepts a request as complete once it receives f+1 matching, individually signed replies from distinct replicas, guaranteeing at least one honest replica genuinely executed and confirmed the request (since at most f replicas can be faulty). This client-side verification is a deliberate, necessary part of the protocol, not an afterthought.

Is PBFT still used directly in production today, or mostly its descendants?

Both — PBFT and close variants remain in use in permissioned blockchain and consortium settings (notably early Hyperledger Fabric configurations), while HotStuff and Tendermint-family protocols (6.3, 6.4) have become more common for larger-scale, more performance-sensitive deployments, precisely because of the O(n²) scalability gap noted above.

Takeaways

• PBFT (Castro & Liskov, 1999) was the first Byzantine fault-tolerant protocol efficient enough for practical, real-world use — a constant number of phases instead of the O(f) rounds earlier protocols needed.
• The normal-case protocol: Pre-Prepare (primary proposes), Prepare (all-to-all broadcast, 2f+1 needed), Commit (all-to-all broadcast, 2f+1 needed) — the all-to-all pattern lets replicas cross-verify without trusting the primary alone.
• Digital signatures are load-bearing, not optional — they close off the message-forgery attack article 6.1 identified, letting PBFT operate at the theoretical minimum 3f+1 node count.
• View changes are Byzantine-hardened leader election, using cryptographically verifiable prepared certificates instead of simple trust in a reported log.
• PBFT's all-to-all Prepare/Commit gives it O(n²) message complexity — fine for small clusters, a real bottleneck at blockchain-scale validator counts, motivating HotStuff's linear-communication redesign next.

References & further reading

• Castro & Liskov — Practical Byzantine Fault Tolerance (OSDI 1999) — the primary source.
• cvam.sight — Consensus 6.1: The Byzantine Generals Problem — the 3f+1 threshold and signed-message insight this article builds on directly.
• cvam.sight — Consensus 5.4: Viewstamped Replication — the shared MIT research lineage and "view" terminology PBFT carries forward.