Skip to content
Tutorials Center
My learning

Topics

Lesson 21 of 41 ยท Consensus and Networks

BFT, Delegated and Other Consensus Mechanisms

Compare PBFT-style voting, quorum math (3f+1), Raft, delegated and authority-based consensus and DAG ledgers, with a live quorum calculator in Python.

Proof of work and proof of stake are not the only ways for a group of computers to agree. Long before Bitcoin, researchers built protocols in which a known set of participants votes in rounds until enough of them agree. These protocols give up open membership in exchange for speed and immediate finality, and many modern blockchains use a version of them, alone or combined with proof of stake.

This lesson explains the idea behind Byzantine fault tolerant (BFT) voting, derives the famous 3f + 1 rule, contrasts it with crash-tolerant protocols such as Raft, and surveys delegated, authority-based and DAG designs. It is mostly conceptual, with two small Python tools to make the numbers concrete. The background problem is explained in The Double-Spend Problem and Byzantine Faults.

Two kinds of failure

Distributed systems classify failures by how nasty they are.

  • A crash fault means a node stops: power cut, process killed, network cable pulled. It never lies; it just goes silent.
  • A Byzantine fault means a node may do anything: send different answers to different peers, claim to have received messages it never got, or collude with other bad nodes.

Protocols for crash faults are simpler and need fewer machines. Protocols for Byzantine faults cost more but are the right choice when participants may be hostile, which is the situation blockchains are designed for.

PBFT: the idea of voting rounds

Practical Byzantine Fault Tolerance (PBFT), published in 1999, showed that a system could tolerate malicious nodes with reasonable speed. The sequence in one round, simplified, is:

  1. Pre-prepare. A leader (the primary) proposes a value, for example the next block, and sends it to everyone.
  2. Prepare. Every replica that accepts the proposal broadcasts "I saw this proposal".
  3. Commit. A replica that has seen enough matching prepares broadcasts "I am ready to commit".
  4. Decide. A replica that has seen enough matching commits executes the block. Once it decides, the decision is final.

"Enough" always means a quorum, a number large enough that two quorums must overlap in at least one honest node. If the leader is faulty or slow, replicas time out and start a view change that elects a new leader.

sequenceDiagram
    participant L as Leader
    participant A as Replica A
    participant B as Replica B
    participant C as Replica C
    L->>A: pre-prepare(block)
    L->>B: pre-prepare(block)
    L->>C: pre-prepare(block)
    A->>B: prepare
    B->>C: prepare
    C->>A: prepare
    A->>B: commit
    B->>C: commit
    C->>A: commit
    Note over A,C: Each replica decides after a quorum of matching commits

A simplified PBFT round; the arrows between replicas are drawn for a few pairs only, in reality everybody messages everybody.

Why 3f + 1?

Suppose up to f of the n nodes are Byzantine. Two facts must hold at the same time:

  • Liveness. The system must be able to make progress even if the f bad nodes stay silent. So a quorum of n - f nodes must be enough to decide.
  • Safety. Among a quorum of n - f, up to f might be liars. The honest ones, n - 2f, must still outnumber the liars: n - 2f > f, so n > 3f, or n >= 3f + 1.

Another way to see it: any two quorums must overlap in more than f nodes so that the overlap contains at least one honest node. With n = 3f + 1 and quorum size 2f + 1, two quorums share at least 2(2f + 1) - (3f + 1) = f + 1 nodes. At least one of those is honest, so it will not vote for two conflicting values.

Let us tabulate the numbers for both fault models.

Python Quorum calculator

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Read the table row by row. Four nodes tolerate one Byzantine node, but five and six do not tolerate any more (the extra node adds cost without adding resilience); you need seven for two. For crash faults, three nodes already tolerate one failure, which is why so many databases run three replicas.

Now a tiny round of voting. Honest nodes all vote for value A. Faulty nodes tell the first half of the nodes they vote B and stay silent to the others. Does anyone commit the wrong thing?

Python Votes with faulty nodes

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

When the number of faulty nodes is within the limit (4 with 1, 7 with 2), every node commits A. When it goes beyond (4 with 2, 7 with 3), the honest nodes cannot reach a quorum and the system waits. Notice what did not happen: no node committed the wrong value. BFT protocols prefer to stop rather than to be wrong when too many nodes are bad. In the beyond-limit case an attacker with even more faulty nodes could break safety, which is why the assumption "fewer than one third are Byzantine" is the foundation of the whole design.

Raft and Paxos: consensus for crash faults

Raft and Paxos keep replicas of a database or log consistent. One leader accepts writes and replicates them to followers; a write counts once a majority has stored it. This tolerates crashes and network delays, but not liars: a malicious leader could simply tell followers wrong things. That makes them perfect inside one company's data center (etcd, Consul and many databases use Raft) and unsuitable for a network of strangers.

Raft / Paxos PBFT-style BFT Nakamoto (PoW/PoS)
Faults tolerated Crashes Up to one third Byzantine Up to a minority of resources
Membership Known, fixed Known, permissioned or staked Open
Finality Immediate Immediate Probabilistic or checkpointed
Message cost Linear Quadratic (classic PBFT) Low per node
Typical size 3 to 7 nodes Tens to a few hundred Thousands

PBFT's quadratic message cost (every replica talks to every other) limits it to a few hundred participants. Newer protocols reduce this with leader rotation, pipelining and aggregated signatures, and proof-of-stake chains often run a BFT voting layer over a stake-selected validator committee.

Delegated and authority-based designs

Delegated proof of stake (DPoS). Token holders vote for a small set of delegates (a few dozen), who take turns producing blocks. It is fast and cheap, but power concentrates in the delegates and their voters, so it is considerably more centralized than open mining.

Proof of authority (PoA). A fixed list of approved identities (companies, universities, a consortium) are the only block producers; their reputation is the stake. It suits private and test networks and consortium chains, where participants are known and legal agreements exist. A rogue authority can be removed by vote, but the trust model is the same as running a shared database among partners.

Other families. Proof of space or proof of storage replaces computing with disk capacity. Proof of elapsed time depends on trusted hardware. Proof of history (used by Solana) is a verifiable clock built from a sequential hash chain that helps validators agree on ordering. Each makes different trade-offs between decentralization, speed and trust assumptions.

DAG ledgers

A blockchain is a single line of blocks, so only one block can be added at a time. A DAG (directed acyclic graph) ledger lets many records be added in parallel: each new transaction or block references several earlier ones, forming a web instead of a line. Examples include IOTA's Tangle and Hedera Hashgraph. Parallel writes promise more throughput, but ordering conflicting transactions (the double-spend problem) still needs a rule: some DAGs use witnesses or a coordinator, others use gossip-about-gossip voting that is BFT in spirit.

flowchart LR
    G["genesis"] --> A["tx A"]
    G --> B["tx B"]
    A --> C["tx C"]
    B --> C
    B --> D["tx D"]
    C --> E["tx E"]
    D --> E

In a DAG, each record confirms several earlier ones, so records can be added side by side.

Choosing a mechanism

Ask three questions. Who may join, and do you know them? What failures do you need to survive (crashes or attacks)? And do you need immediate finality? Open, adversarial, global networks lean toward proof of work or stake; consortium chains lean toward BFT or authority; a single organization needs only Raft.

Check your understanding

Quick check ยท 4 questions

of 4 answered You scored / 4 ยท perfect!

  1. 1. How many nodes are needed at minimum to tolerate f Byzantine nodes?

    Safety and liveness together require n >= 3f + 1, so a quorum of 2f + 1 always contains an honest majority.
  2. 2. What is a main difference between Raft and PBFT?

    Raft assumes nodes fail by stopping, not by lying. PBFT is designed for arbitrary (Byzantine) behavior.
  3. 3. In the voting demo, 4 nodes with 2 faulty ones cannot reach a quorum. What does the protocol do?

    BFT protocols favor safety over liveness when the fault assumption is broken, so they stall rather than decide inconsistently.
  4. 4. Which chain type fits a consortium of known companies best?

    When participants are known and accountable, authority or BFT designs give fast, final blocks without mining.

Summary

  • Crash faults mean a node stops; Byzantine faults mean it may lie or collude.
  • BFT protocols such as PBFT reach agreement through voting rounds with quorums, and decisions are final at once.
  • To tolerate f Byzantine nodes you need 3f + 1 nodes and quorums of 2f + 1; for crash faults 2f + 1 nodes suffice.
  • Raft and Paxos are for trusted data centers; they cannot handle malicious nodes.
  • Delegated and authority-based chains trade decentralization for speed; DAG ledgers add records in parallel but still need an ordering rule.
  • Pick the mechanism from the membership model, the failures you must survive and the finality you need.

Next: What Are Smart Contracts?, programs that run on the agreed-upon ledger.