Consensus Algorithms: From Basics to BFT

⏱️ Duration: 1.5-2 hours 📊 Difficulty: Basic

Learning Objectives

1. The Consensus Problem

What is Consensus?

In a distributed system, consensus is the process of getting all honest nodes to agree on a single value or sequence of values, even when some nodes may be faulty or malicious.

Example: Imagine 4 generals trying to coordinate an attack. One might be a traitor. How do the honest generals agree on a plan?

Why is Consensus Hard?

The FLP Impossibility Result

Fischer, Lynch, and Paterson proved that in an asynchronous network, it's impossible to guarantee consensus if even one node can fail. This is why blockchain systems assume something stronger than full asynchrony (e.g. partial synchrony). For why BFT can still guarantee progress, see Distributed Systems Fundamentals (partial synchrony, GST).

2. Byzantine Fault Tolerance (BFT)

What is BFT?

Byzantine Fault Tolerance is the ability of a system to function correctly even when some nodes are Byzantine (malicious or faulty).

Fault Model

In a BFT system with n = 3f + 1 nodes:

Example: n = 4, f = 1
- Total nodes: 4
- Byzantine nodes: up to 1
- Honest nodes: at least 3
- Quorum size: 2f + 1 = 3

Any two groups of 3 nodes must share at least 1 honest node.

BFT vs Crash Fault Tolerance (CFT)

Aspect CFT BFT
Fault Model Nodes crash Nodes can be malicious
Tolerance f out of 2f+1 f out of 3f+1
Use Case Databases, distributed systems Blockchains, critical systems

3. Quorum Certificates (QCs)

What is a Quorum Certificate?

A Quorum Certificate (QC) is cryptographic proof that at least 2f+1 validators have voted for a block. It's an aggregated signature from a quorum of validators.

Properties of QCs

How a QC is Formed – Steps

In HotStuff-style BFT, a quorum certificate is produced and then carried in the next block’s header. Conceptually:

  1. (i) The proposer for block H builds the block (including parent_qc = QC for H−1 in the header) and broadcasts the block header to the shard.
  2. (ii) Validators receive the header, validate it, and each signs a vote (block hash + metadata). Votes are broadcast to the shard (so every validator, including the next proposer, receives them).
  3. (iii) When any validator has 2f+1 valid votes for block H, it requests aggregation into a single QC (verify signatures and build aggregated signature). That node’s state stores the new QC as its latest_qc.
  4. (iv) The QC is not sent as a separate network message. The next proposer (for H+1) either formed QC(H) locally from the broadcast votes, or later sees QC(H) when it receives a block whose header contains it.
  5. (v) When the next proposer builds block H+1, it sets the new header’s parent_qc = QC(H) (from its latest_qc) and broadcasts block H+1. All validators then see QC(H) inside the header of H+1.

So: votes are broadcast → (any) validator with 2f+1 votes forms the QC locally → QC is carried in the next block’s header.

Communication flow (matches (i)–(v) above)

(i) Block H proposal
- Proposer builds block H (header has parent_qc = QC(H−1)), broadcasts header
↓
(ii) Validators receive & validate; votes broadcast to shard
↓
(iii) When 2f+1 votes: request QC build → latest_qc updated
↓
(iv)–(v) Block H+1
- Next proposer sets parent_qc = QC(H), broadcasts H+1
- All validators see QC(H) in H+1’s header
Key point: The QC is not broadcast as a separate message. Votes are broadcast; validators with 2f+1 votes form the QC locally; the next block’s header carries that QC as parent_qc, so everyone sees it when they receive the next block.

Example timeline

T1: Proposer builds Block 10 (header includes QC for Block 9), broadcasts header
T2: Validators validate, sign votes, broadcast votes to shard
T3: When 2f+1 votes received → any such validator requests QC build → QC(10) formed, stored as latest_qc
T4: Next proposer builds Block 11 with parent_qc = QC(10), broadcasts Block 11
T5: All nodes receive Block 11 → see QC(10) in header

In hyperscale-rs (crate and line references)

References are to the hyperscale-rs repo (paths and line numbers may shift slightly with upstream).

4. HotStuff-2 Protocol Basics

What is HotStuff-2?

HotStuff-2 is a BFT consensus protocol that uses a two-chain commit rule. It's an improvement over traditional BFT protocols like PBFT.

What is PBFT?

PBFT (Practical Byzantine Fault Tolerance) is a classic BFT consensus protocol introduced by Castro and Liskov in 1999. It was one of the first practical BFT protocols that could handle Byzantine faults in asynchronous networks.

PBFT Characteristics:

Why PBFT matters: PBFT established the foundation for BFT consensus. Many modern protocols (including HotStuff-2) are improvements on PBFT's core ideas, addressing its limitations around communication complexity and view changes.

Key Features of HotStuff-2

Basic Flow

  1. Proposal: Proposer creates and broadcasts block header
  2. Voting: Validators validate and vote
  3. QC Formation: When 2f+1 votes collected, QC is formed
  4. Commit: Block commits when next block gets QC (two-chain rule)

Two-Chain Commit Rule

Block at height H commits when block at height H+1 gets a QC.

Rule: Block H commits when block H+1 receives a QC.

Example scenario:
1. Block H is proposed and receives QC
2. Block H+1 is proposed and receives QC
   → Block H NOW COMMITS (because H+1 has QC)
3. Block H+2 is proposed and receives QC
   → Block H+1 NOW COMMITS (because H+2 has QC)

Visual representation:
Block H:    [has QC] → commits when H+1 gets QC ✓
Block H+1:  [has QC] → commits when H+2 gets QC (waiting...)
Block H+2:  [no QC yet] → will commit when H+3 gets QC (waiting...)

The "two-chain" name comes from needing 2 consecutive blocks with QCs:
- H has QC and H+1 has QC → H commits (2 blocks in chain)
Why Two-Chain? Ensures finality even under network partitions. Only one chain can get consecutive QCs.
Understanding Finality:

Finality means once a block is committed, it cannot be reverted. In two-chain commit: Block H commits when H+1 gets a QC, creating a chain of QCs proving agreement by 2f+1 validators.

Under network partitions, only the majority partition (2f+1 validators) can produce consecutive QCs. The minority cannot, so their blocks won't commit. This ensures safety: only one valid chain exists, and committed blocks are permanent.

5. What PoW and BFT Mean (and How They Relate)

BFT and Proof of Work (PoW) answer different questions:

How they relate: BFT and PoW are on different axes. BFT is about the agreement rule (voting, quorums, deterministic finality). PoW (and PoS) are about who participates or who gets to propose. Many chains use BFT for agreement and PoS for validator selection (e.g. Tendermint: BFT consensus + PoS to choose the validator set). PoW chains typically do not use BFT; they use Nakamoto (longest-chain) consensus with probabilistic finality.

BFT vs Proof-of-Stake (PoS)

Below compares classic BFT (fixed validator set, as in Hyperscale-rs) with open PoS (anyone can join by staking). Many chains combine both (e.g. Tendermint: BFT consensus + PoS for validator selection).

Key Differences

Aspect BFT (classic) PoS (open)
Validator Set Fixed, known Dynamic, stake-weighted
Finality Immediate, deterministic Probabilistic or economic; often requires time
Communication O(n) per block Often O(n) among validators (when BFT-style)
Fault Tolerance Up to f of 3f+1 Byzantine (≤1/3) Honest majority of stake (<50% adversarial)

Comparison with Proof of Work (PoW): PoW does not use BFT: it uses the longest-chain rule (Nakamoto consensus). There is no fixed validator set (any miner can participate), only probabilistic finality (confirmations over time), and security relies on honest majority of hashrate (attack requires >50% hashrate). BFT gives deterministic finality and provable safety with ≤1/3 Byzantine nodes.

When to Use BFT

6. Exploring BFT in Hyperscale-rs

Key Files to Explore

View these in the repo (links open the file on GitHub):

  1. crates/bft/src/lib.rs — module documentation
  2. crates/bft/src/state.rs — BFT state machine implementation
  3. crates/bft/src/vote_set.rs — vote collection and QC formation
  4. guides/04-consensus-protocol.md — detailed protocol documentation

Practical Exercise

Open crates/bft/src/lib.rs in the repo and find:

7. Knowledge Check Quiz

8. Practical Assignment

Assignment: Understanding BFT Consensus

Tasks:

  1. Read protocol docs and code in the repo:
  2. Trace a block through consensus:
    • Open crates/bft/src/state.rs in the repo
    • Find the block proposal function
    • Find the vote handling function
    • Find the QC formation logic
    • Find the commit logic
    • Create a diagram showing the flow
  3. Answer Questions:
    • In a system with 7 validators, how many can be Byzantine?
    • How many votes are needed for a quorum in a 7-validator system?
    • When does block H commit in HotStuff-2?
    • What is the difference between a vote and a QC?
  4. Update Learning Journal:
    • Add a section on BFT consensus
    • Document what you learned
    • List questions you still have

Success Criteria:

  • ✅ You can explain BFT to someone else
  • ✅ You understand quorum certificates
  • ✅ You can trace through the code
  • ✅ You can answer the questions correctly
← Back to Index Next Module →