vault

Practical Byzantine Fault Tolerance

43 min read

Practical Byzantine Fault Tolerance

Practical Byzantine Fault Tolerance (PBFT) is the replication algorithm Miguel Castro and Barbara Liskov introduced at OSDI 1999 (Castro & Liskov 1999) — the first Byzantine-fault-tolerant protocol efficient enough to run a real service in a real, asynchronous network like the Internet. It tolerates up to f Byzantine (arbitrary, possibly malicious) replica failures using 3f + 1 replicas — the minimum the The Byzantine Generals Problem permits — and it does so with an order of magnitude less overhead than prior BFT work, which had assumed synchrony and used expensive public-key signatures on every message. PBFT is a state-machine replication protocol: clients submit operations, a designated primary assigns them sequence numbers, and all correct replicas execute the same operations in the same order, so the replicated service behaves like a single correct server (Replicated State Machine Architecture). Its engine is a three-phase commit — pre-prepare, prepare, commit — that establishes a total order robust to a lying primary and to view changes. The headline result was BFS, a Byzantine-fault-tolerant NFS file system that ran only 3% slower than the unreplicated NFS V2 implementation in the Digital Unix kernel on the Andrew benchmark — though, as the same table shows, 26% slower than an otherwise-identical unreplicated build of BFS itself, and the two numbers say very different things. The precise guarantee is the part most often stated wrong: safety holds in a fully asynchronous network with no timing assumption whatsoever; liveness requires a partial-synchrony assumption and cannot be provided without one, because a protocol that guaranteed both under pure asynchrony would refute FLP Impossibility Result. Its enduring weakness is O(n²) normal-case message complexity — and, worse, O(n³) authenticator complexity per view change — which caps practical replica counts and motivated the later linear-communication protocols (Tendermint/CometBFT, HotStuff) at the heart of modern blockchains. This note reads the OSDI ‘99 paper alongside Castro’s much longer PhD thesis (MIT-LCS-TR-817, 2001) and the TOCS 2002 journal version, which together carry the proofs, the proactive-recovery mechanism, and the admission — invisible in the conference paper — that swapping signatures for MACs was not an optimization but a redesign.

Mental Model — Three Phases, Two Quorum Certificates

PBFT turns the factorial fan-out of the original Byzantine Generals oral-message algorithm — up to (n−1)(n−2)⋯(n−m−1) messages over m+1 rounds — into a fixed pipeline of five message delays (four with the tentative-execution optimization), whose depth does not grow with f at all. The key idea: instead of recursively cross-checking, every replica broadcasts its vote to every other replica in two successive all-to-all rounds, and each replica advances only when it has collected a quorum certificate — a set of 2f + 1 matching signed votes — proving that a supermajority agrees.

sequenceDiagram
    participant C as Client
    participant P as Replica 0 (Primary)
    participant R1 as Replica 1
    participant R2 as Replica 2
    participant R3 as Replica 3 (faulty)
    C->>P: REQUEST o,t,c
    P->>R1: PRE-PREPARE v,n,d
    P->>R2: PRE-PREPARE v,n,d
    P->>R3: PRE-PREPARE v,n,d
    Note over P,R2: PREPARE phase: all-to-all broadcast
    R1->>R2: PREPARE v,n,d,1
    R2->>R1: PREPARE v,n,d,2
    Note over P,R2: prepared() = pre-prepare + 2f matching prepares
    Note over P,R2: COMMIT phase: all-to-all broadcast
    R1->>R2: COMMIT v,n,d,1
    R2->>R1: COMMIT v,n,d,2
    Note over P,R2: committed-local() = 2f+1 matching commits → execute
    R1->>C: REPLY v,t,c,1,r
    R2->>C: REPLY v,t,c,2,r
    P->>C: REPLY v,t,c,0,r

What it shows and the insight to take: with n = 3f + 1 = 4 replicas (f = 1), Replica 3 can be Byzantine and silent or lying, yet the three correct replicas still form quorums of 2f + 1 = 3. The prepare phase pins the order of a request within a view (agreement among honest replicas that request m gets sequence n); the commit phase makes that order survive across view changes, so a value committed under one primary can never be reassigned by the next. The client itself waits for f + 1 = 2 matching replies — enough to guarantee at least one came from a correct replica. Two all-to-all rounds are the price of Byzantine tolerance: they are why message complexity is quadratic in n.

Counting the messages for one request makes the quadratic concrete and is worth doing once by hand, because “PBFT is O(n²)” is repeated far more often than it is derived:

PhaseWho sendsTo whomMessages
REQUESTclientprimary (point-to-point)1
PRE-PREPAREprimaryn − 1 backupsn − 1
PREPAREeach of n − 1 backupsall other replicas(n − 1)²
COMMITevery replicaall other replicasn(n − 1)
REPLYevery replicaclientn
Total2n² − n + 1 = Θ(n²)

At n = 4 that is 29 messages for one request (1 + 3 + 9 + 12 + 4); at n = 100, 19,901. Two further facts round the picture out. First, latency in the base protocol is five one-way message delays (request → pre-prepare → prepare → commit → reply); the tentative execution optimization described below cuts it to four, and read-only operations to a single round trip. Zyzzyva’s comparison table lists PBFT at 4 critical-path one-way latencies for exactly this reason (Kotla et al. 2007). Second, and much less often noticed, the quadratic figure describes only the normal case: HotStuff’s authors count PBFT’s view change at O(n³) authenticators to convey one new proposal, rising to O(n⁴) if O(n) view changes precede a single decision, because the new primary must relay a certificate from each of n − f replicas to each of n replicas (Yin et al. 2019). It is the view change, not the happy path, that actually kills scaling.

Why Prior BFT Was Impractical, and How PBFT Escaped

Byzantine agreement had been known since 1980 (see The Byzantine Generals Problem; the famous 1982 TOPLAS paper is a retelling of a 1980 JACM result), but earlier algorithms were unusable in practice for two reasons, and the paper names both in its second paragraph: earlier work “either concerns techniques designed to demonstrate theoretical feasibility that are too inefficient to be used in practice, or assumes synchrony, i.e., relies on known bounds on message delays and process speeds.”

The synchrony objection is the sharper one, and it is a security argument rather than a performance argument. Castro and Liskov single out Rampart and SecureRing — the two systems closest to theirs — and observe that because both rely on synchrony for correctness, “an attacker may compromise the safety of a service by delaying non-faulty nodes or the communication between them until they are tagged as faulty and excluded from the replica group. Such a denial-of-service attack is generally easier than gaining control over a non-faulty node.” A protocol that excludes replicas on a timeout hands the adversary a cheap way to shrink the honest group below the threshold. PBFT “never needs to exclude replicas from the group” — view changes only rotate the primary — which is precisely why a timing violation costs it liveness and never safety.

The timing assumption, stated exactly. PBFT guarantees liveness “provided at most ⌊(n−1)/3⌋ replicas are faulty and delay(t) does not grow faster than t indefinitely,” where delay(t) is the time between a message first being sent and its receipt, assuming the sender keeps retransmitting. The paper calls this “a rather weak synchrony assumption that is likely to be true in any real system provided network faults are eventually repaired.” It is a restatement of the Dwork–Lynch–Stockmeyer partial-synchrony model: bounds exist but are unknown, or hold only after an unknown Global Stabilization Time (GST). DLS themselves proved these two formulations equivalent for consensus, by the same argument PBFT relies on — a safety violation happens at a finite instant, and any such execution has a continuation in which the delay bound eventually holds, so an algorithm safe under the GST model is safe under full asynchrony.

Two consequences follow that are worth separating carefully, because interview answers routinely fuse them:

  1. Safety needs no timing assumption at all. Correct replicas never disagree, whatever the network does, however long messages are delayed, forever.
  2. Liveness needs partial synchrony, and this is forced rather than chosen. The paper’s own justification is a one-line reduction: “The algorithm does not rely on synchrony to provide safety. Therefore, it must rely on synchrony to provide liveness; otherwise it could be used to implement consensus in an asynchronous system, which is not possible [FLP].” A protocol offering both unconditionally would be a counterexample to FLP Impossibility Result.

There is a third consequence, and it is the one that explains why PBFT pays for 3f + 1 replicas despite using cryptography. In the synchronous world of the 1982 paper, signatures collapse the replica bound. In the partially synchronous world PBFT actually inhabits, DLS’s Table I shows authenticated Byzantine consensus still requires N ≥ 3t + 1 — “for partially synchronous communication, authentication does not improve resiliency.” So 3f + 1 here is not merely inherited from Lamport; it is independently mandatory in PBFT’s own model.

The second engineering move is authentication cost: PBFT uses cheap message authentication codes (MACs) in the common case instead of signatures, reserving public-key operations for the rare view-change path. That change is usually described as an optimization. Castro’s thesis says flatly that it is not, and the next section is about why.

BFT-PK, BFT, BFT-PR — Three Algorithms Wearing One Name

“PBFT” is used as if it named a single protocol. Castro’s thesis is structured around three, and confusing them is the source of most inaccurate summaries.

NameChapterAuthenticationWhat it addsWhat it costs
BFT-PKthesis §2public-key signatures on every messagethe clean algorithm you can prove things about; this is essentially what OSDI ‘99 §4 describesRSA signing dominates latency and throughput
BFTthesis §3MACs everywhere, including client requests3 orders of magnitude cheaper authenticationa substantially different view-change protocol, and new failure modes around request authentication
BFT-PRthesis §4MACs + secure co-processor + watchdogproactive recovery: tolerate unboundedly many faults over a system’s lifetimea synchrony assumption, and periodic recovery overhead

The OSDI ‘99 paper presents BFT-PK in §4 and then says, in §5.2, that the implementation actually replaces signatures with MACs. That single sentence hides a redesign. The thesis section is titled, with unusual bluntness, “Why it is Hard to Replace Signatures by MACs”:

“Replacing signatures by MACs seems like a trivial optimization but it is not. The problem is that MACs are not as powerful as public-key signatures… MACs are not as powerful as signatures: the receiver may be unable to convince a third party that the message is authentic. This is a fundamental limitation due to the symmetry of MAC computation.” — Castro 2001, §3.1

Why that matters here specifically: BFT-PK’s correctness “relies on the exchange during view changes of certificates collected by the replicas. This works only if the messages in these sets are signed. If messages are authenticated with MACs, a replica can collect a certificate but may be unable to prove to others that it has the certificate.” The thesis’s fix is a change of certificate strength: if a correct replica i holds a quorum certificate (2f + 1 messages) for some fact x, the correct replicas inside that quorum can each retransmit their own message to a third replica j, which will therefore eventually assemble a weak certificate (f + 1 messages) for x. Weak certificates are strictly weaker — two of them can assign the same sequence number to different requests in the same view — so the new view-change protocol must break such ties using invariants established during normal-case operation. Castro’s own summary: “We were able to retain the same communication structure during normal case operation and garbage collection at the expense of significant and subtle changes to the view change protocol.”

The MAC switch also breaks a property BFT-PK took for granted: that all replicas agree on whether a client request is authentic. With signatures, “all replicas would agree either on the client that sent the request or that the request was a forgery.” With per-pair MACs, “some replicas may be able to authenticate a request while others are unable to do it,” which can deadlock or split the group. BFT therefore defines request authenticity by three alternative conditions at backup i:

  1. the MAC for i in the request’s authenticator verifies; or
  2. i has accepted f PREPARE messages carrying the request’s digest; or
  3. i has received the same operation and timestamp directly from client c with a correct MAC.

Condition 1 is the normal path. Condition 2 exists to prevent a permanent deadlock: a request with a corrupt authenticator can still commit if it has f + 1 correct MACs, and without condition 2 the remaining backups could never authenticate it — it is safe because a request only reaches f prepares if at least one correct replica verified its MAC. Condition 3 lets a correct client repair the situation by retransmitting to everyone. The thesis is honest about the residual hole: “faulty clients can still force view changes. Our current implementation does not deal with this problem,” with the suggested mitigation being to make suspected clients sign their requests and process those at lower priority.

The concrete numbers behind the switch. On the paper’s 200 MHz Pentium Pro, generating a 1024-bit-modulus RSA signature over an MD5 digest took 43 ms, verifying it 0.6 ms, while computing a MAC over a 64-byte message took 10.3 µs — “three orders of magnitude” faster. Each pair of nodes shares a 16-byte session key; a MAC is MD5 over message-plus-key, truncated to the 10 least significant bytes (a variant of the secret suffix method, truncated both to save space and to harden against certain attacks). A multicast message carries an authenticator: a vector of one MAC per other replica. Verification is O(1) but generation is O(n), and the authenticator’s size grows linearly — 30⌈(n−1)/3⌉ bytes in the OSDI ‘99 implementation, 8n bytes in the thesis’s later one, which stays smaller than a 1024-bit RSA signature up to n ≤ 16, i.e. f ≤ 5. Even at 37 replicas (f = 12) an authenticator is “much more than two orders of magnitude faster” to compute than an RSA signature.

System Model and the 3f + 1 Bound

Replicas are a set R of |R| = 3f + 1 deterministic state machines, indexed 0 … |R| − 1, connected by an asynchronous network that may lose, delay, duplicate, or reorder messages. Up to f replicas may be Byzantine — behaving arbitrarily, and assumed to be coordinated by a single adversary who can also delay correct nodes and the network (but who cannot break cryptographic primitives or delay the network indefinitely). The two guarantees, holding whenever no more than f replicas are faulty, are:

  • Safety (linearizability): the replicated service behaves like a centralized implementation executing operations atomically one at a time (see Linearizability).
  • Liveness: clients eventually receive replies, given the weak-synchrony delay bound.

Why exactly 3f + 1? The paper’s own derivation is the counting argument inherited from The Byzantine Generals Problem: a correct replica must be able to make progress after hearing from n − f replicas, because the f faulty ones may never respond. But among those n − f responders, up to f may themselves be faulty and lying. For the correct responses to outnumber the faulty ones — the only way to trust the result — we need n − 2f > f, hence n > 3f, so the minimum is n = 3f + 1. This is optimal: no asynchronous protocol can do better. Adding replicas beyond 3f + 1 only degrades performance (more and bigger messages) without improving resiliency, since resiliency is fixed by f.

Views, the Primary, and the Client Protocol

Replicas move through a succession of numbered configurations called views. In each view one replica is the primary and the rest are backups. The primary of view v is the replica p = v mod |R| — a simple rotation, so a view change deterministically hands leadership to the next replica. The primary’s job is to pick an order for client requests by assigning sequence numbers; the protocol’s machinery exists to stop a faulty primary from imposing an inconsistent or malicious order.

A client c invokes operation o by sending ⟨REQUEST, o, t, c⟩ signed, where t is a timestamp used to enforce exactly-once semantics — timestamps are totally ordered per client so replicas can discard duplicates and re-send the cached reply for an already-executed request (see Exactly-Once Semantics and Idempotency). Replicas send ⟨REPLY, v, t, c, i, r⟩ directly to the client, where i is the replica id and r the result. The client waits for f + 1 replies from different replicas with the same t and r before accepting r. Because at most f replicas are faulty, f + 1 matching replies guarantee at least one came from a correct replica — and since correct replicas only reply after the operation is properly committed and ordered, that one honest reply certifies the result. If the client times out without f + 1 matching replies, it broadcasts the request to all replicas, forcing a sluggish or faulty primary to be relayed and, if it persists in ignoring the request, eventually suspected and replaced by a view change.

Normal-Case Operation: Pre-Prepare, Prepare, Commit

When the primary p receives a client request m, it runs a three-phase atomic-multicast protocol. Each replica keeps a message log of accepted messages and a current view number.

Phase 1 — Pre-Prepare. The primary assigns request m a sequence number n and multicasts ⟨⟨PRE-PREPARE, v, n, d⟩, m⟩, where d is the digest of m and the inner tuple is signed by the primary. Critically, m is piggybacked but not part of the signed pre-prepare — the pre-prepare acts purely as proof that request m was assigned sequence n in view v, which decouples ordering from the (potentially large) request payload. A backup accepts the pre-prepare only if: the signatures are valid and d matches m; it is in view v; it has not already accepted a different pre-prepare for (v, n) with a different digest (this is what stops a faulty primary from equivocating — assigning the same sequence number to two different requests); and n lies between a low water mark h and high water mark H.

Phase 2 — Prepare. On accepting the pre-prepare, backup i enters the prepare phase by multicasting ⟨PREPARE, v, n, d, i⟩ to all replicas and logging both messages. A replica (including the primary) accepts prepares whose signature, view, and sequence number check out. The pivotal predicate:

prepared(m, v, n, i) is true when replica i has in its log: the request m, a pre-prepare for m in view v with sequence n, and 2f PREPARE messages from distinct backups matching that pre-prepare.

A pre-prepare plus 2f matching prepares is 2f + 1 matching endorsements (the primary’s pre-prepare counts as its vote). The pre-prepare and prepare phases together guarantee that correct replicas agree on a total order for requests within a view. The paper proves the invariant that if prepared(m, v, n, i) holds at a correct replica i, then prepared(m′, v, n, j) is false for any correct replica j and any m′ with a different digest. The proof is a quorum-intersection argument: prepared needs 2f + 1 replicas to have endorsed (v, n), and with only 3f + 1 replicas total, two such quorums must overlap in at least f + 1 replicas — of which at least one is correct. A correct replica never endorses two conflicting requests for the same (v, n), so the two conflicting prepared predicates cannot both hold. This is the same intersection logic that underlies ordinary Read and Write Quorums, hardened for the Byzantine case by inflating the quorum from a bare majority to 2f + 1.

Phase 3 — Commit. When prepared(m, v, n, i) becomes true, replica i multicasts ⟨COMMIT, v, n, d, i⟩. Replicas collect commits into the log, and define:

committed-local(m, v, n, i) is true when prepared(m, v, n, i) holds and replica i has accepted 2f + 1 COMMIT messages (possibly including its own) matching the pre-prepare.

Once committed-local holds and it has executed all lower-numbered requests, replica i executes m and replies to the client. Why is a third phase needed when prepare already fixed the order? Because prepare only guarantees ordering within a single view. The commit phase, and its 2f + 1 quorum, ensure the order survives across view changes: the paper proves that if committed-local(m, v, n, i) is true at any correct replica, then committed(m, v, n) is true — meaning prepared(m, v, n) held at a set of at least f + 1 correct replicas. Because any future correct new-view construction must intersect that set, a request committed at sequence n can never be superseded by a different request at n in a later view. Prepare orders within a view; commit makes the order durable across views.

Two water marks, h (low) and H = h + k, bound the sequence numbers a replica will accept, preventing a faulty primary from exhausting the sequence space by proposing an enormous n. They advance with checkpoints (below); k is chosen large enough that replicas do not stall waiting for a checkpoint to stabilize — the paper’s illustrative figure is k = 200 for checkpoints every 100 requests, and the actual BFS experiments used a checkpoint interval of 128 requests with a high water mark 256 above the last stable checkpoint.

One ordering subtlety is easy to miss and matters for implementers: PBFT “does not rely on ordered message delivery, and therefore it is possible for a replica to commit requests out of order.” A replica may reach committed-local for sequence n + 3 before n. That is harmless because execution is gated separately — a replica executes only when committed-local holds and its state already reflects every request with a lower sequence number — so the pre-prepare/prepare/commit entries simply stay in the log until the gap fills.

stateDiagram-v2
    [*] --> Idle: sequence number n unassigned
    Idle --> PrePrepared: accepted PRE-PREPARE (v,n,d)<br/>auth ok, in view v,<br/>no conflicting (v,n),<br/>n between water marks h and H
    PrePrepared --> Prepared: + 2f matching PREPAREs<br/>from distinct backups<br/>= 2f+1 endorsements of (v,n,d)
    Prepared --> CommittedLocal: + 2f+1 matching COMMITs<br/>(may include own)
    CommittedLocal --> Executed: all lower sequence<br/>numbers already executed
    Executed --> [*]: reply sent, entry kept<br/>until next stable checkpoint
    Prepared --> Tentative: optimization: execute early,<br/>send tentative reply
    Tentative --> Executed: request later commits
    Tentative --> Idle: view change replaced it<br/>with a null request;<br/>roll back to last checkpoint

What it shows and the insight to take: the two guards that matter sit on different transitions. Prepared is intra-view agreement — enough to order, not enough to be durable — which is exactly why the speculative Tentative branch exists and why it can be rolled back. CommittedLocal is cross-view durability. Every BFT protocol descended from PBFT is, structurally, an argument about whether that second guard can be made cheaper or moved somewhere else: Zyzzyva pushes it to the client, HotStuff replaces it with a third pipelined phase, Tendermint locks on it.

View Changes — Liveness When the Primary Is Faulty

If the primary is faulty — silent, or refusing to order some request — progress stalls. Backups detect this with timers: a backup starts a timer when it receives a request it has not yet executed; if the timer expires, the backup suspects the primary and starts a view change to move from view v to v + 1.

The backup stops accepting normal messages (it will still process checkpoint, view-change and new-view messages) and multicasts ⟨VIEW-CHANGE, v+1, n, C, P, i⟩, where n is the sequence number of its last stable checkpoint, C is a set of 2f + 1 checkpoint messages proving that checkpoint stable, and P carries, for each request prepared above n, its pre-prepare plus 2f matching prepares — the proof of what this replica had prepared. The new primary p′ = (v+1) mod |R| waits for 2f valid VIEW-CHANGE messages from other replicas; together with the view-change message it sent (or would have sent) itself, that makes the justifying set V a quorum of 2f + 1. It then multicasts ⟨NEW-VIEW, v+1, V, O⟩, where O is a freshly computed set of pre-prepares for view v + 1.

O is not hand-waved in the paper; the construction is mechanical, and reproducing it is what makes the safety argument checkable. The primary computes min-s, the sequence number of the latest stable checkpoint appearing in V, and max-s, the highest sequence number appearing in any prepare message in V. For every sequence number n in [min-s, max-s] it emits one pre-prepare, choosing between two cases:

  • Case 1 — some replica in V reported a prepared request at n. The primary re-proposes that request’s digest, taking the one from the pre-prepare with the highest view number among the candidates. This is the step that stops a committed request from being lost or replaced.
  • Case 2 — no replica in V reported anything at n. The primary proposes a special null request, which “goes through the protocol like other requests, but its execution is a no-op.” The paper credits Paxos with the same gap-filling trick, and it is the reason a view change cannot leave holes in the sequence space.
sequenceDiagram
    autonumber
    participant B1 as Backup 1
    participant B2 as Backup 2
    participant P2 as Replica 1 = new primary (v+1)
    participant P1 as Replica 0 = old primary (faulty)
    Note over B1,B2: request received, timer started, primary silent
    B1--xP1: request (ignored)
    B2--xP1: request (ignored)
    Note over B1,B2: timers expire
    B1->>P2: VIEW-CHANGE v+1, n, C, P, 1
    B2->>P2: VIEW-CHANGE v+1, n, C, P, 2
    Note over P2: has 2f VIEW-CHANGEs from others<br/>+ its own = quorum V of 2f+1
    Note over P2: compute min-s (latest stable checkpoint in V)<br/>and max-s (highest prepared seq in V)<br/>re-propose highest-view digest per slot,<br/>fill gaps with null requests
    P2->>B1: NEW-VIEW v+1, V, O
    P2->>B2: NEW-VIEW v+1, V, O
    Note over B1,B2: RECOMPUTE O from V and compare;<br/>only then enter view v+1
    B1->>B2: PREPARE for each message in O
    B2->>B1: PREPARE for each message in O

What it shows and the insight to take: the new primary is never trusted. It supplies V (the evidence) and O (its conclusion), and every backup re-derives O from V itself before accepting the view. This is the same design principle as the digest in a pre-prepare — the leader proposes, but nothing in the protocol requires believing it. The quorum size 2f + 1 is what makes the evidence sufficient: any V must intersect any previously-committed 2f + 1 set in at least one correct replica, so no committed request can be silently dropped across the change.

Backups verify O by recomputing it from V themselves and comparing — they do not trust the primary’s arithmetic — then log the new pre-prepares, multicast a prepare for each, and enter view v + 1. Replicas redo the three-phase protocol for everything between min-s and max-s but avoid re-executing client requests, using their cached last-reply-per-client to make redelivery idempotent.

The 2f + 1 view-change quorum is what makes this safe: it must intersect, in at least one correct replica, any 2f + 1 set that previously committed a request — so no committed request is lost across the change. Liveness is protected against faulty replicas trying to force needless view changes: a view change requires f + 1 genuine complaints, so f faulty replicas alone cannot trigger one; and because primaries rotate as p = v mod |R|, a faulty replica can be primary for at most f consecutive views. To ensure the system does not thrash, a replica waits for 2f + 1 view-change messages for v + 1 and sets its next timer to expire after time T; if it must escalate to v + 2 it doubles the wait to 2T, giving exponential backoff so that eventually a period arrives in which 2f + 1 correct replicas sit in the same view long enough to make progress.

Checkpoints, Garbage Collection, and the MAC Optimization

Replicas cannot keep their message log forever. Periodically — when a sequence number divisible by some constant (e.g. 100) executes — a replica takes a checkpoint of service state and multicasts ⟨CHECKPOINT, n, d, i⟩ with d the state digest. When a replica collects 2f + 1 matching checkpoint messages, the checkpoint is stable (that set of 2f + 1 is the proof of correctness for the checkpoint), and the replica discards all pre-prepare, prepare, and commit log entries with sequence number ≤ n, and advances the low water mark h to n. Copy-on-write and incremental cryptography keep the cost of snapshotting large state manageable.

The performance-critical optimization is authentication, covered in the BFT-PK/BFT section above: signatures are retained only for view-change and new-view messages, where proving authenticity to a third party genuinely matters, and everything else uses MACs. Three further optimizations in OSDI ‘99 §5.1 shape the protocol’s real cost profile and are the reason the measured overhead is nothing like the message count suggests:

  • Digest replies. A client request designates one replica to send the full result; every other replica sends only the digest of the result. The client can still verify the answer, but a large reply crosses the network once instead of 3f + 1 times. This is why the 0/4 (4 KB result) micro-benchmark overhead is 72% while the 4/0 (4 KB argument) case is 207% — the argument has to traverse the network twice, in the request and again in the pre-prepare.
  • Tentative execution. A replica executes a request as soon as prepared holds (plus all lower-numbered requests are known committed) and returns a tentative reply. The client waits for 2f + 1 matching tentative replies instead of f + 1 final ones; that many guarantees the request will eventually commit. This removes one message delay — “from 5 to 4” — at the cost of a rollback path: if a view change replaces the request with a null request, the replica reverts to the last stable checkpoint or its last checkpointed state, whichever has the higher sequence number.
  • Read-only requests. A client multicasts a read-only operation directly to all replicas, which execute it immediately against tentative state (after checking authentication, access control, and that it really is read-only) and reply once everything reflected in that state has committed. The client waits for 2f + 1 identical replies. One round trip, no ordering protocol at all. If concurrent writes prevent 2f + 1 replies from agreeing, the client falls back to issuing it as a normal read-write request.

The read-only optimization comes with a sharp lesson about interface design determining BFT cost. In NFS V2, “out of the 18 operations in the NFS V2 protocol only getattr is read-only because the time-last-accessed attribute of files and directories is set by operations that would otherwise be read-only, e.g. read and lookup.” A single incidental side effect — updating an access timestamp — disqualified almost every operation from the cheap path. Castro and Liskov measured a variant that declares lookup read-only anyway, “violating strict Unix file system semantics,” and it moved total Andrew-benchmark overhead from 26% to 20% against the unreplicated build, and from +3% to −2% against stock NFS. When budgeting a BFT deployment, how many of your operations are honestly read-only is a first-order question.

The system also handles non-determinism (e.g. NFS’s last-modified timestamps read from a clock): the primary proposes the non-deterministic value, concatenates it with the request, and orders the pair through the same three phases, so all correct replicas execute with identical inputs. The paper notes the residual hole — “a faulty primary might send the same, incorrect, value to all replicas” — so replicas must be able to decide deterministically from service state whether a proposed value is acceptable. Where the service specification requires the backups to participate in choosing (rather than merely validating), an extra phase is added: the primary collects authenticated candidate values from backups, concatenates 2f + 1 of them with the request, and the replicas derive the value by a deterministic function of those 2f + 1 values, e.g. the median. That extra phase can be optimized away when clocks are already synchronized within the tolerance the service needs.

Measured Performance — What “3% Slower” Actually Means

Castro and Liskov built BFS, a Byzantine-fault-tolerant NFS, on their replication library. The experimental setup matters for reading the numbers: four replicas and one client, all DEC 3000/400 Alpha workstations (133 MHz Alpha 21064, 128 MB RAM, Digital Unix 4.0), a DEC RZ26 disk per replica, and a 10 Mbit/s switched Ethernet on an isolated network. Four replicas means f = 1, which the authors say they “expect this reliability level to suffice for most applications.”

The micro-benchmark measures the latency of a null operation against a stateless service, and is the worst case for the protocol because there is no real work to amortize over. Notation a/b is argument and result size in kilobytes:

Operationreplicated, read-writereplicated, read-onlyunreplicated
0/03.35 ms (+309%)1.62 ms (+98%)0.82 ms
4/014.19 ms (+207%)6.98 ms (+51%)4.62 ms
0/48.01 ms (+72%)5.94 ms (+27%)4.66 ms

Of the 0/0 read-write overhead, ~1.06 ms is computation (0.55 ms of it cryptography) and ~1.47 ms is the extra network round trip plus larger and more numerous messages. The authors are careful that this is a floor-comparison artifact: measured against an unreplicated server that merely uses MACs for authentication — a fairer baseline, since real services authenticate — the overhead falls to 243% for read-write 0/0 and 4% for read-only 4/0.

The Andrew benchmark (five phases: create directories recursively, copy a source tree, stat every file, read every byte, compile and link) is the realistic case, because the client spends real time computing between operations. Two comparisons are reported, and they are not the same comparison:

PhaseBFS strictBFS r/o lookupBFS-nr (no replication)NFS-std (Digital Unix)
10.550.470.351.75
29.247.915.089.46
37.246.456.115.36
48.777.877.416.60
538.6838.3832.1239.35
total (s)64.4861.0751.0762.52

(Mean of 10 runs. Sample standard deviation was below 2.6% on the total but as high as 14% on the individual first four phases — a variance also present in the NFS-std configuration, so it is the workload, not the protocol.)

What it shows and the insight to take: the famous “3%” is 64.48 / 62.52 — BFS against stock NFS — and the honest reading is that BFS wins back most of its replication cost from disk I/O it no longer has to do. BFS is faster than NFS-std in phases 1, 2 and 5 precisely because those phases issue synchronous operations: NFS-std makes modified state stable by writing to disk, while BFS makes it stable by replicating it (the trick it inherits from Harp). In phases 3 and 4, where the client issues no synchronous operations, BFS is 32–35% slower. The apples-to-apples number — BFS against the identical code with replication removed — is +26%, or +20% with the read-only lookup variant. Quoting “3%” without naming the baseline is the most common way this protocol gets oversold.

Castro’s thesis, run later on faster hardware with 100-file and 500-file Andrew variants, gives a consistent picture and a wider spread: BFS takes 14% (Andrew100) and 22% (Andrew500) longer than the unreplicated NO-REP build, and 15%/24% longer than Linux’s NFS — but Linux’s NFS “does not ensure stability of modified data and meta-data before replying to the client as required by the NFS protocol,” so the comparison against Digital Unix’s correct implementation again shows BFS 2% faster. The thesis abstract’s own summary is the honest headline: “BFS performs 2% faster to 24% slower than production implementations of the NFS protocol that are not replicated.”

Proactive Recovery — BFT-PR and the Window of Vulnerability

Everything above holds “provided at most f replicas are faulty.” For a long-lived service that is not a guarantee, it is a countdown: given enough time an attacker compromises replicas one at a time until the bound breaks. The thesis and the TOCS 2002 journal version add BFT-PR, which “can tolerate any number of faults provided fewer than 1/3 of the replicas become faulty within a window of vulnerability.”

Recovery must be proactive rather than reactive, and the reason is the definition of a Byzantine fault: “a Byzantine-faulty replica may appear to behave properly even when broken; therefore recovery must be proactive to prevent an attacker from compromising the service by corrupting 1/3 of the replicas without being detected.” You cannot wait for a failure detector to fire, because a competent adversary makes sure it never fires. Replicas are therefore rejuvenated on a schedule, independent of any suspicion — and a recovering replica must keep participating in request processing while it recovers, since naively taking it offline would itself push the group past f.

Three mechanisms make it work, each solving a problem that does not arise in crash-fault recovery:

  • Fresh messages. Once an attacker has held a replica it can sign arbitrary bad messages — even with a secure co-processor — and replay them after recovery. BFT-PR defines an authentication-freshness notion and rejects stale messages. The price is that “replicas may be unable to prove to a third party that some message they received is authentic,” which is survivable only because BFT (the MAC version) had already stopped relying on such proofs. BFT-PK and every earlier state-machine-replication algorithm did rely on them, and therefore cannot support recovery at all. The MAC redesign was a precondition for proactive recovery, not merely a speed-up.
  • Secure cryptography and a watchdog. Each replica needs a secure cryptographic co-processor holding a key that survives compromise, plus a reliable timer to trigger recoveries; involving a human administrator is ruled out as impractical at the required frequency.
  • Efficient hierarchical state transfer. A recovering replica must determine which parts of its local state are simultaneously up to date and uncorrupted, and fetch the rest verifiably. The mechanism uses Merkle trees plus incremental cryptography, and tolerates concurrent modification while a transfer is in flight.

The resulting guarantee comes with an explicit formula: safety and liveness hold “provided at most f replicas become faulty within a window of vulnerability of size T_v = 2T_k + T_r,” where T_k is the maximum session-key refreshment period at a non-faulty node and T_r the maximum time between a replica failing and recovering from that fault. The 2T_k term bounds how long a stolen key stays useful. The thesis suggests T_k around 15 seconds, subject to one constraint that is easy to violate in a wide-area deployment: T_k “should be substantially larger than 3 message delays under normal load conditions to provide liveness.”

The honesty here is worth quoting, because it is the opposite of the usual marketing: bounding faults within a finite window is a synchrony assumption. “Limiting the number of faults that can occur in a finite window is a synchrony assumption but such an assumption is unavoidable: since Byzantine-faulty replicas can discard the service state, it is necessary to bound the number of failures that can occur before recovery completes. To tolerate f faults over the lifetime of the system, BFT-PR requires no synchrony assumptions.” And T_v is only partly under your control, since T_r can be inflated by a denial-of-service attack — which is why replicas time their own recoveries and alert an administrator when one runs long.

The measured cost is the surprising part: proactive-recovery overhead ranges from 27% at a 1.5-minute minimum window of vulnerability down to 2% at a 10.5-minute window, with one replica starting a recovery every 15 seconds in the most aggressive configuration.

gantt
    title BFT-PR staggers recoveries so the simultaneous-fault budget never fills
    dateFormat X
    axisFormat %S
    section Replica 0
    serving      :active, a1, 0, 15
    recovering   :crit,   a2, 15, 25
    serving      :active, a3, 25, 60
    section Replica 1
    serving      :active, b1, 0, 30
    recovering   :crit,   b2, 30, 40
    serving      :active, b3, 40, 60
    section Replica 2
    serving      :active, c1, 0, 45
    recovering   :crit,   c2, 45, 55
    serving      :active, c3, 55, 60
    section Replica 3
    serving      :active, d1, 0, 60

What it shows and the insight to take (x-axis in seconds): recoveries are staggered, never simultaneous, and a replica keeps serving while it recovers. The safety argument is not “recovered replicas are trustworthy” — it is that the number an adversary can hold at the same time is bounded, because every replica is scrubbed within T_v whether or not anyone suspects it. Shrinking T_v buys resilience and costs throughput, and the measured curve of that trade-off is unusually flat.

Legacy and the Modern Lineage

PBFT’s structural limitation is communication. The two all-to-all phases mean each request costs Θ(n²) messages, and — as HotStuff’s authors quantify — conveying one new proposal through a view change costs O(n³) authenticators, or O(n⁴) if O(n) view changes precede a single decision. That is acceptable for the small permissioned groups PBFT targeted; the paper’s own framing is n = 4 or n = 7 on a LAN. It does not survive the move to hundreds or thousands of validators on wide-area networks where Δ must be set generously.

Each successor attacks a different part of the structure. Status and dates below were checked against each project’s own repository or paper on 2026-08-29, because this is an area where dead projects routinely get described in the present tense.

SuccessorStructural changeStatus as of 2026-08-29
Zyzzyva (Kotla et al., SOSP 2007)speculative: replicas execute in the primary’s proposed order without agreeing first and reply immediately; the client detects divergence and drives convergence. 3 critical-path one-way latencies vs PBFT’s 4, and 2 + 3f/b MAC ops at the bottleneck server vs PBFT’s 2 + (8f+1)/b for batch size bresearch protocol; a safety violation in the published algorithm was demonstrated in 2017 — see below
Tendermint (Buchman, Kwon & Milosevic, arXiv 1807.04938)three steps per round — Propose → Prevote → Precommit, structurally parallel to pre-prepare/prepare/commit — with all votes gossiped, a +2/3 quorum at each step, validators locking on a value backed by a proof-of-lock-change, and the leader rotating every roundTendermint Core itself is frozen: its README states “TendermintCore featureset is frozen for LTS,” pinned at v0.34.24 for cosmoshub-4
CometBFTthe maintained fork of Tendermint Core — same consensus algorithm, plus ABCI++active; latest release v0.40.0 (2026-07-27), with v0.38.26 patched 2026-08-13
HotStuff (Yin et al., PODC 2019, arXiv 1803.05069)a three-phase core, so a new leader “can simply pick the highest QC it knows of”; votes are routed to the leader and aggregated into one threshold-signed quorum certificate, giving linear communication including at view change; pipelined, with the leader rotating every blockpublished; the direct ancestor of the DiemBFT/AptosBFT family
LibraBFT / DiemBFTHotStuff plus a pacemaker and explicit round timeouts, built for Libra/Diemdefunct as a project. The diem/diem README states that “Silvergate Capital Corporation announced in January 2022 that it acquired intellectual property and other technology assets related to running a blockchain-based payment network from Diem”
AptosBFTthe living descendant of DiemBFT: Jolteon’s 2-chain commit rule, order votes (AIP-89) and optimistic proposals (AIP-131) that extend a parent block before the parent’s QC existsactive in production; the aptos-core consensus README describes “a BFT state machine replication protocol for n = 3f+1 validators, tolerating up to f Byzantine faults… safety always and liveness during periods of synchrony (partial synchrony model)”

Three things are worth pulling out of that table.

The three-phase shape survived; the communication pattern did not. CometBFT’s Propose → Prevote → Precommit and HotStuff’s three-phase core are both recognizably PBFT’s pre-prepare/prepare/commit. What every successor changed is who talks to whom: PBFT broadcasts votes replica-to-replica, while the successors funnel votes through the leader and re-disseminate a single aggregated certificate. AptosBFT’s README shows how far that has been pushed — an optimistic proposal extends a block “before the parent’s QC arrives,” reducing block time “to a single network hop,” with 2f+1 order votes forming a commit certificate in “the theoretical minimum of 3 network hops for BFT ordering under partial synchrony.”

Linear communication is not the same as fast. HotStuff’s contribution is usually compressed to “linear instead of quadratic,” but its own framing is that the hard part was doing so without losing optimistic responsiveness — the property that “a non-faulty leader, once designated, can drive the protocol to consensus in time depending only on the actual message delays, independent of any known upper bound.” Tendermint and Casper get a simple leader regime but “are built around a synchronous core, wherein proposals are made in pre-determined intervals that must accommodate the worst-case time it takes to propagate messages over a wide-area peer-to-peer gossip network. In doing so, they forego” responsiveness. PBFT is responsive; the naive way to make it linear is not, and HotStuff’s added phase is what buys both at once.

PBFT’s conservatism about speculation was vindicated. Zyzzyva made the natural next move — let the client, not the replicas, perform the output commit — and reported peak throughput of 86 K ops/sec with batching against PBFT’s 59 K, a 45% gap attributed roughly half to cryptographic and half to message overhead, landing “within 35% of that of an unreplicated server.” Ten years later, Abraham, Gueta and Malkhi, with Alvisi, Kotla and Martin (2017) published a note reporting “a safety violation in Zyzzyva and a liveness violation in FaB,” demonstrable with “relatively simple scenarios, involving only four replicas, and one or two view changes. In all of them, the problem is manifested already in the first log slot.” Their diagnosis generalizes: “several key works in the ‘optimistic strand’ do not deal with optimism correctly.” HotStuff makes the same complaint about the whole family — PBFT-style view change “is far from simple, is bug-prone, and incurs a significant communication penalty for even moderate system sizes.” The operational lesson for anyone selecting a BFT engine is that the view-change path, not the happy path, is where BFT protocols are wrong — and it is the path least exercised by testing, because in a healthy deployment it almost never runs.

PBFT remains the reference point every BFT paper still measures against (see Major System Designs MOC for blockchain case studies, and Consensus as a Coordination Game for what changes once the faulty replicas are replaced by rational ones with utility functions).

Failure Modes and Practical Notes

  • More than f Byzantine replicas → safety loss. All guarantees hold only while at most f of 3f + 1 are faulty. Exceed f and correct replicas can be split into disagreeing quorums; there is no graceful degradation. Sizing f correctly, and keeping faults independent (diverse implementations, separate operators), is the whole game.
  • Liveness needs partial synchrony; safety needs nothing. Under a sufficiently adversarial network that delays messages unboundedly, PBFT preserves safety but can stall indefinitely — exactly what FLP Impossibility Result forces. It never sacrifices safety for progress, and the common claim that “PBFT works in asynchronous systems” is only half of the statement: it is safe in an asynchronous system and live in a partially synchronous one.
  • The primary is a throughput bottleneck. All requests funnel through one primary that must disseminate them; its uplink bandwidth caps system throughput, a structural issue inherited by all single-leader BFT and a prime motivation for multi-leader and leaderless BFT variants.
  • Beware the view-change thrash cycle. The liveness argument depends on three separate mechanisms working together, and dropping any one breaks it: a replica that sends a view-change for v+1 waits for 2f + 1 view-change messages before starting a timer of duration T, and doubles to 2T for v+2 (exponential backoff); a replica that sees f + 1 view-change messages for views beyond its own joins the smallest of them immediately, even if its own timer has not fired, so it cannot be left behind; and since the primary is v mod |R|, “the primary cannot be faulty for more than f consecutive views.” Only f + 1 complaints can start a view change at all, so the f faulty replicas cannot force one on their own.
  • O(n²) caps replica count. Practical only for small groups. Do not reach for PBFT-style BFT when crash faults are the real threat — Raft or Paxos High-Level tolerate f crash faults with just 2f + 1 nodes and far less communication. BFT’s 3f + 1 and quadratic cost are justified only when nodes may be malicious or corrupted, not merely down.
  • Determinism is mandatory. Replicas must produce identical output from identical input; any hidden non-determinism (unsynchronized clocks, random numbers, iteration order) diverges replica state and breaks agreement, which is why the non-determinism handling above exists.
  • A faulty client can force view changes. This is the failure mode the conference paper omits and the thesis admits. In the MAC version, a request whose authenticator has fewer than f + 1 correct MACs — or which the primary itself cannot authenticate — can trigger a view change. That is desirable when the primary is the faulty party, “but they can also be used to mount denial-of-service attacks by replacing correct primaries frequently… faulty clients can still force view changes. Our current implementation does not deal with this problem.” The suggested mitigation is to make suspected clients sign their requests and process signed requests at lower priority, bounding the rate.
  • Independent failure is an assumption you have to build, not one you get. The paper is explicit that 3f + 1 only helps if faults are uncorrelated, and that this costs real money: “each node should run different implementations of the service code and operating system and should have a different root password and a different administrator,” with N-version programming named as an option. Four replicas of the same binary, on the same distro, patched by the same automation, share one bug and one credential — f = 1 on paper, f = 0 in practice.
  • BFT does not give you privacy. “The algorithm does not address the problem of fault-tolerant privacy: a faulty replica may leak information to an attacker.” It cannot, in general, because replicas must see arguments and state in the clear to execute arbitrary operations. If confidentiality matters, secret sharing over the opaque portions of the state is a separate mechanism you must add.
  • Access control is doing more work than the protocol. Safety holds “regardless of how many faulty clients are using the service,” but safety only means the faulty client’s operations are observed consistently: “in a file system a faulty client can write garbage data to some shared file.” Bounding what a compromised client can destroy is authorization’s job, not consensus’s.

See Also

Graph View

Backlinks