Byzantine fault tolerance: authenticated quorums despite equivocation

Byzantine faults include arbitrary behavior: lying, omission, equivocation, and collusion. Practical Byzantine Fault Tolerance (PBFT) replicates a deterministic state machine with authenticated replica identities. In the classic configuration n=3f+1; a prepared condition combines the primary pre-prepare with 2f matching prepares, and commit-local requires 2f+1 matching commit messages.

Any two 2f+1 certificates in 3f+1 replicas intersect in at least f+1 replicas, so at least one correct replica is in the intersection when at most f are Byzantine. Authentication prevents impersonation but does not make a four-replica system safe against two Byzantine replicas. Safety can survive asynchronous periods; liveness needs eventual synchrony and a correct primary after view changes.

Prerequisites and model

• At most f of n=3f+1 replicas are Byzantine and replica identities cannot be cheaply forged.
• Messages/certificates are authenticated and replay-protected for view, sequence, and request id.
• The replicated state machine is deterministic or agrees on nondeterministic inputs.
• Stable logs/checkpoints and view-change certificates preserve prepared/committed work.

Correctness claims and invariants

• BFT-C1. Classic PBFT uses n=3f+1; prepared combines pre-prepare plus 2f matching prepares, and commit-local requires 2f+1 matching commits.
• BFT-C2. Two 2f+1 certificates intersect in at least f+1, including at least one correct replica under the fault bound.
• BFT-C3. Pre-prepare, prepare, and commit phases prevent a faulty primary from committing two orders at one view/sequence.
• BFT-C4. View change carries prepared/committed evidence so a new primary cannot discard safe work.
• BFT-C5. A client waits for matching replies from enough replicas rather than trusting only the primary.
• BFT-C6. Safety assumes at most f Byzantine replicas; liveness additionally requires eventual synchrony.

What the scenarios prove

• PBFT pre-prepare, prepare, commit (normal-pbft): Four replicas tolerate one Byzantine fault using authenticated 3-of-4 certificates.

• Faulty primary equivocation (faulty-primary-equivocation): Conflicting pre-prepares cannot both gather matching correct prepare certificates.

• Certificate intersection arithmetic (certificate-intersection): For n=4,f=1, any two 3-replica certificates share at least two replicas, one correct.

• View change preserves prepared work (view-change-preserves): New-primary selection carries certificates and cannot discard a prepared/committed request.

• Client waits for matching replies (client-matching-replies): The client does not trust one possibly Byzantine primary response.

• Eventual synchrony for liveness (liveness-partition): Safety remains while messages are delayed, but progress waits for a timely correct primary/quorum.

• Fault bound exceeded (too-many-faults): Two Byzantine replicas in a four-replica PBFT deployment exceed f=1 assumptions.

Failure, concurrency, and retry traps

• 2f+1 total replicas are insufficient for classic asynchronous Byzantine quorum safety.
• Signatures do not prevent Sybil identities or deterministic application divergence.
• Trusting the primary reply bypasses replicated verification.
• A view change without prepared certificates can lose or reorder safe requests.
• PBFT is not crash-fault Paxos with only a larger node count.

Boundaries and non-guarantees

• Guarantees stop when more than f replicas are Byzantine or authentication/key assumptions fail.
• Safety does not imply progress in a fully asynchronous partition.
• Application nondeterminism must become agreed input.
• Permissionless membership needs Sybil resistance beyond PBFT message authentication.

Related material

Primary sources

1. USENIX OSDI 1999: Practical Byzantine Fault Tolerance
2. Castro and Liskov PBFT full paper HTML
3. Castro and Liskov, Practical Byzantine Fault Tolerance and Proactive Recovery
4. Castro, Practical Byzantine Fault Tolerance thesis