Skip to content

Byzantine fault tolerance in the small#

2024-08-19

Notes from re-reading PBFT (Castro & Liskov, 1999) and comparing to modern BFT variants.

The 3f+1 result#

Classic result: to tolerate f Byzantine failures, you need 3f+1 nodes. Why 3f+1 and not 2f+1?

  • With 2f+1 nodes and f Byzantine, in the worst case you can partition the honest majority (f+1 nodes) into two groups that both think they have quorum, but with different values.
  • With 3f+1, the quorum size is 2f+1, which guarantees intersection: any two quorums share at least one honest node.

PBFT protocol phases#

  1. Pre-prepare: primary broadcasts a proposal.
  2. Prepare: replicas broadcast that they've seen the pre-prepare. Wait for 2f+1 prepare messages.
  3. Commit: replicas broadcast commit. Wait for 2f+1 commits.
  4. Reply: replicas send response to client. Client waits for f+1 matching replies.

Total: 3 message rounds + client reply. Compare to Raft's 1 round for commit.

Modern BFT variants#

  • HotStuff (2019): linear message complexity per view. Basis for LibraBFT / Diem.
  • Tendermint (2014): PBFT with rotating leader per block. Used in Cosmos.
  • Zyzzyva (2007): speculative execution to reduce latency; clients can help detect bad primaries.

For blockchain use, protocols also need to be chained — each block commits proof that the previous block was BFT-committed. This adds complications around finality.

When you actually need BFT#

  • Public/permissionless blockchain — yes.
  • Cross-organizational replicas that don't trust each other — probably.
  • Internal cluster replication — no. Fault model is too pessimistic; use Paxos/Raft and monitor for misbehavior.

Reference#

  • Castro & Liskov, Practical Byzantine Fault Tolerance (OSDI 1999).
  • Yin et al., HotStuff: BFT Consensus with Linearity and Responsiveness (PODC 2019).