Consensus Fault Tolerance · Byzantine Fault Tolerance

Key Question

How does modern blockchain consensus relate to classical BFT?

Deep Dive

Classical BFT (PBFT) assumes a permissioned setting: you know all participants beforehand, and identities are fixed. Blockchains operate in permissionless environments where anyone can join and leave anonymously. This changes everything.

Nakamoto Consensus (Bitcoin):

Bitcoin solved permissionless BFT using Proof-of-Work (PoW). Instead of “f out of N nodes are faulty,” Bitcoin’s model is: “no adversary controls more than 50% of the total hashrate.”

Honest miners chain:  B1 ← B2 ← B3 ← B4 ← B5 (longest chain wins)
Adversary's chain:    B1 ← B2 ← B3'← B4'      (shorter, discarded)
                                       ^
                                  Honest chain accepted
                                  because it has more work

An attacker trying to double-spend must outpace the honest chain:
  Attacker: privately mines a fork, reveals it after the payment.
  If attacker has <50% hashrate, honest chain grows faster.
  If attacker has >50% hashrate, attacker can eventually overtake.

This is probabilistic BFT: finality is not guaranteed at any specific block — it becomes increasingly certain as more blocks are built on top. After 6 blocks (~1 hour), the probability of reversal is ~0.01% against a 10% adversary.

Modern BFT-blockchain hybrids:

Approach	Example	Mechanism	Finality
Classical BFT	Hyperledger Fabric	PBFT per block	Instant
BFT + PoS	Tendermint/Cosmos	PBFT-style with validator voting	Instant
Linear BFT	HotStuff/Diem	Leader-based, O(n) messages	Instant
Probabilistic	Bitcoin/Ethereum	PoW longest chain	Probabilistic
Hybrid	Algorand	VRF-based random committee	Instant

Tendermint: Uses a validator set elected by stake (Proof-of-Stake). Validators take turns proposing blocks. Each block requires a 2/3+ vote (Prep → Commit, similar to PBFT). Finality is instant: once 2/3+ validators commit, the block is final. If a proposer is faulty, the system moves to the next validator.

HotStuff: Used by Diem (Libra). The key innovation: linear message complexity (O(n) instead of O(n²)). The leader does all the work, replicas just respond. This makes it practical for thousands of validators. HotStuff uses a three-phase protocol (Propose → Prepare → Commit → Decide) but all messages go through the leader, creating a linear communication pattern.

PBFT:  O(n²) — every node talks to every node
  [P] ←→ [B1] ←→ [B2]
   ↓  ↕    ↕    ↕  ↓
  [B3] ←→ [B4] ←→ [B5]

HotStuff: O(n) — all messages through the leader
  [P] ←→ [B1]
  [P] ←→ [B2]
  [P] ←→ [B3]
  [P] ←→ [B4]
  [P] ←→ [B5]

Linear complexity = 1000 validators × 1 message each = 1000 messages
Quadratic complexity = 1000 × 1000 = 1,000,000 messages

Algorand: Uses Verifiable Random Functions (VRFs) to randomly select a small committee for each block. The committee runs a BFT protocol among themselves. Since the committee is tiny (~1000 nodes regardless of total stake), communication is efficient. No one knows who the committee members are until they reveal themselves, preventing targeted DoS attacks.

Check Your Understanding

How does Proof-of-Work act as a probabilistic BFT mechanism?
Why does HotStuff have better scalability than PBFT for large validator sets?
What is the key difference between permissioned BFT and permissionless BFT?

The “So What?”

Blockchain is BFT’s killer app — it solves the permissionless BFT problem that classical algorithms couldn’t address. Modern blockchains blend BFT with economic incentives (staking, mining rewards) to create systems that tolerate Byzantine faults while remaining open to anyone. Understanding this evolution from PBFT to HotStuff to PoS blockchains is essential for anyone working in distributed ledger technology.

✏️ Exercises

Byzantine Fault Tolerance: Exercises

Exercise 1: 3f+1 Bound

How many nodes are needed to tolerate 3 Byzantine faulty nodes? Show the math.

Exercise 2: PBFT Phases

In PBFT, why is the Prepare phase needed if we already have Pre-prepare? What problem would occur with only Pre-prepare and Commit?

Exercise 3: Proof-of-Work as BFT

How does Proof-of-Work act as a probabilistic BFT mechanism? What happens if an attacker controls 40% of the total hashrate?

👁️ View Solutions

Byzantine Fault Tolerance: Solutions

Exercise 1

N ≥ 3f + 1 = 3(3) + 1 = 10 nodes.

For f = 3, you need at least 10 nodes. With 10 nodes, you can tolerate up to 3 Byzantine faults. With only 9 nodes (3f, but 3f+1 is 10), you’d have 3 correct nodes per “group” — any 3 faulty nodes could group together and confuse the protocol since honest nodes need 2f+1 replies but can’t distinguish liars from honest ones in the worst case.

Compare to crash faults: 2f+1 = 7 nodes needed for f=3 crash tolerance. BFT requires 3 more nodes.

Exercise 2

Without the Prepare phase, a single faulty primary could send different Pre-prepare messages to different replicas, and those replicas would commit different values in the Commit phase — violating agreement.

The Prepare phase ensures within-view consistency: replicas share their Pre-prepare receipts with each other. When a replica collects 2f matching Prepare messages (including its own Pre-prepare), it knows that at least f+1 correct replicas received the same Pre-prepare. Even if the primary is Byzantine, the correct replicas have agreed on the ordering.

The Commit phase then ensures cross-view consistency: that the decision survives view changes.

Without Prepare, a Byzantine primary could send Pre-prepare(“attack”) to half the replicas and Pre-prepare(“retreat”) to the other half. The Commit phase alone can’t detect this because replicas don’t cross-check what they received from the primary.

Exercise 3

Proof-of-Work acts as probabilistic BFT because:

Identity is expensive: Each block requires computational work. An adversary must expend compute power proportional to their hashrate to produce blocks.
Chain selection rule: The longest (most work) chain is considered canonical. To reverse a transaction, the adversary must outpace the honest chain — requiring >50% of total hashrate.
Probabilistic finality: Each confirmation block reduces the probability that an adversary can rewrite history.

With 40% hashrate, an attacker has a significant but not dominant position. The probability of a successful double-spend attack decreases exponentially with confirmations:

After 1 block: ~40% chance (if attacker has pre-mined)
After 3 blocks: ~10% chance
After 6 blocks: ~0.8% chance
After 10 blocks: ~0.02% chance

The attacker can temporarily overtake the honest chain, but the honest chain grows faster on average. The system recommends waiting for enough confirmations (typically 6 for Bitcoin) to make reversal economically infeasible.

This contrasts with classical BFT where finality is instant and deterministic — once 2f+1 nodes commit, the decision is final regardless of adversarial hashrate.