BFT Protocols: PBFT and Tendermint

The Byzantine Generals Problem, formulated by Lamport, Shostak, and Pease in 1982, asks: can a distributed system reach consensus when some participants send contradictory messages? The problem is named after Byzantine generals who must coordinate an attack but may include traitors sending conflicting orders. A system is Byzantine Fault Tolerant (BFT) if it reaches correct consensus despite up to f malicious nodes among 3f+1 total. BFT is the gold standard for blockchain consensus requiring safety under adversarial conditions.

PBFT (Castro and Liskov, 1999) was the first practical BFT protocol, demonstrating that BFT could operate efficiently in real systems. PBFT operates in views (terms), each with a designated primary (leader). Normal operation runs three phases: pre-prepare (primary broadcasts client request + sequence number), prepare (replicas broadcast agreement with sequence), and commit (replicas broadcast commit confirmation). A request is executed once a replica collects 2f+1 matching commit messages. PBFT provides safety and liveness assuming fewer than 1/3 of replicas are Byzantine.

PBFT's main limitation is O(n^2) message complexity per request: each of n replicas sends messages to all others in the prepare and commit phases. For n=100 replicas, each request generates roughly 10,000 messages. This makes PBFT impractical for large validator sets. The BFT research community spent two decades improving this: BFT-SMART reduced constants, HotStuff achieved linear message complexity through a leader-relay model, and Tendermint adapted PBFT ideas for public blockchain use.

When a PBFT primary is suspected faulty (timeout), replicas trigger a view change. Each replica broadcasts a view-change message containing its state (prepared values from the old view). The new primary collects 2f+1 view-change messages, constructs a new-view message proving the state transition is consistent with prior committed values, and broadcasts it. View changes are expensive — O(n^3) messages — and were a practical bottleneck. Optimizations like PBFT's view-change certificate and HotStuff's pipelined design address this.

Tendermint (2014, Kwon; production in Cosmos 2019) adapts PBFT for public blockchain environments. Tendermint has three phases per block: propose (leader broadcasts proposed block), prevote (validators vote on the proposal), and precommit (validators vote to commit after seeing 2/3 prevotes). A block is committed when a validator collects 2/3 precommit votes (a quorum certificate). Validators take turns as proposers in round-robin order weighted by stake. If a round times out without a commit, validators advance to the next round with a nil vote.

Tendermint provides strong safety: a committed block is final and cannot be reverted as long as fewer than 1/3 of stake is Byzantine. This is synchronous finality — there are no forks after commit. Liveness requires a partially synchronous network: the protocol makes progress once message delays are bounded, but does not require synchrony continuously. The liveness-safety trade-off is fundamental: Tendermint sacrifices liveness (may halt if the network partitions) to guarantee safety, unlike chains like Bitcoin that sacrifice safety (allow temporary forks) for liveness.

A critical Tendermint mechanism is vote locking. When a validator sends a precommit for a block at round r, it is locked on that block. In subsequent rounds, a locked validator may only prevote for the block it is locked on (or a nil vote if it receives proof that the block was not committed). This prevents contradictory commits across rounds. A validator can only unlock if it receives a polka (2/3 prevotes) for a different block in a later round, proving the original block was not committed.

Cosmos Inter-Blockchain Communication (IBC) relies on Tendermint's instant finality for cross-chain transfers. A Tendermint light client tracks the validator set and the latest commit (a block header plus 2/3 precommit signatures). To verify a packet from chain A, chain B's IBC module verifies the quorum certificate — that 2/3 of chain A's validators signed the relevant block header. This makes IBC security depend on Tendermint's BFT guarantee: a cross-chain transfer is final as soon as the source block is committed.

HotStuff (Yin et al., 2018; basis for Facebook's LibraBFT/DiemBFT, now Aptos and Sui) achieves O(n) message complexity per consensus round using a star topology: all validators send votes to the leader, the leader aggregates into a threshold signature (QC, quorum certificate), and broadcasts the QC. HotStuff uses a three-phase chaining design where safety proofs span three consecutive QCs, enabling pipelining. The linear complexity makes HotStuff practical for 100-300 validators, as deployed in Aptos and Sui.

Enterprise blockchains (Hyperledger Fabric, Besu, Quorum) use BFT consensus for permissioned networks where validator identity is known. Hyperledger Fabric's Raft-based ordering service provides crash fault tolerance (not Byzantine) for trusted consortiums. Fabric's planned BFT milestone targets SmartBFT, a library-based implementation. R3 Corda uses a notary cluster with BFT-SMART for double-spend prevention. The choice between CFT and BFT reflects trust assumptions: BFT is needed when validators may be adversarial, CFT suffices when they are merely unreliable.

Understanding BFT requires understanding what attacks it resists and what it does not. BFT handles equivocating validators (sending conflicting messages to different peers) and validators that crash or go silent. It does not handle Sybil attacks — an attacker who controls 1/3 of validators by creating fake identities can break safety. This is why public BFT chains use PoS stake weighting: acquiring 1/3 of stake costs real money, providing Sybil resistance. BFT also assumes eventual message delivery (partial synchrony) — a network partition lasting longer than the liveness timeout can halt the chain.

What is the maximum fraction of validators that can be Byzantine in a standard BFT protocol while maintaining safety?

BFT protocols ensure consensus despite up to 1/3 malicious validators. PBFT (1999) proved BFT practical but has O(n^2) message complexity. Tendermint adapts PBFT for blockchains with instant finality and vote locking. HotStuff achieves O(n) complexity via threshold signature QCs and is used in Aptos and Sui. Cosmos IBC uses Tendermint's instant finality for verified cross-chain transfers. Enterprise blockchains use BFT-SMART or Raft depending on whether Byzantine or merely crash faults are expected.