The idea: agree even when a replica lies
Raft and Paxos assume a server either works or stops. A
Byzantine server is worse: a bug, a hacked machine or a bad disk makes it send wrong data, or
send one thing to one server and something else to another. PBFT (Practical Byzantine Fault
Tolerance, Castro and Liskov, 1999) keeps a replicated service correct while up to f of its
replicas behave like that. It needs n = 3f + 1 replicas: 4 to survive 1 traitor. One replica
is the primary and picks the order of requests; the others are backups.
| On the page | Meaning |
|---|---|
| C | the client; its request x=7 is signed, so nobody can forge it; it accepts a result once f + 1 = 2 replies match |
| R0 … R3 | replicas; the blue border marks the primary, red marks the traitor; each box shows the PRE-PREPARE it got, its PREPARE and COMMIT counts and what it executed |
| boxes in flight | messages, named sender: TYPE value; each appears at its sender in one step and reaches its receiver in the next; blue = x=7, orange = the lie x=9, purple = view change |
| top row | the current phase; the panel below lists the quorum sizes for the chosen n |
The three phases
The client sends its request to the primary. The primary gives it a sequence number (a slot in
the log) and sends PRE-PREPARE(view, n, request) to the backups. Then come two all-to-all rounds.
A replica is prepared once it has the PRE-PREPARE plus 2f matching PREPAREs: then
2f + 1 replicas agree on what goes in slot n. It is committed once it has
2f + 1 matching COMMITs: then enough replicas know the order is fixed that it survives a view change.
It executes the request and replies (Demo 1: normal case).
| Message | From → to | A replica moves on when it has |
|---|---|---|
REQUEST | client → primary | — |
PRE-PREPARE | primary → backups | one from the primary of its current view, for a free slot |
PREPARE | each backup → all | the PRE-PREPARE + 2f matching PREPAREs (own included): prepared |
COMMIT | each prepared replica → all | 2f + 1 matching COMMITs (own included): committed, execute |
REPLY | each replica → client | the client needs f + 1 matching replies |
Why two all-to-all rounds? PREPARE makes the honest replicas agree on the order within a view. COMMIT makes sure that order is known to a quorum, so a new primary will find it after a view change.
Why 3f + 1 replicas
A replica can never wait for all n answers: the f traitors may simply stay silent. So it waits for
n − f. Among those, up to f may be traitors that answered, so only n − 2f are surely
honest. Two such groups must share at least one honest replica, or they could decide different things. Two
groups of n − f share at least n − 2f replicas; for one of them to be honest we need
n − 2f ≥ f + 1, that is n ≥ 3f + 1. With n = 4 and f = 1 a quorum is 3, and two quorums
of 3 share 2 replicas, at least one of them honest.
| Crash faults (Raft, Paxos) | Byzantine faults (PBFT) | |
|---|---|---|
| a faulty node | stops | stops, lies, or says different things to different nodes |
| replicas for f faults | 2f + 1 (3 for f = 1) | 3f + 1 (4 for f = 1) |
| quorum | f + 1 (a majority) | 2f + 1 |
| messages per request | about n (leader → followers → leader) | about n² (two all-to-all rounds) |
| the client trusts | the leader's answer | f + 1 matching answers |
A traitor backup is outvoted
In Demo 2 R3 sends PREPARE x=9, COMMIT x=9 and REPLY x=9. It changes nothing. Each honest replica still collects 2 matching PREPAREs and 3 matching COMMITs for x=7, because R0, R1 and R2 are 3 = 2f + 1 honest replicas. The client gets 3 replies for x=7 and 1 for x=9; f + 1 = 2 matching replies cannot all come from the one traitor, so x=7 is the answer.
A lying primary and the view change
The primary can't forge the client's signed request, but it can lie about the order: send different backups different PRE-PREPAREs for the same slot. This is called equivocation. In Demo 3 R0 tells R1 x=7, R2 x=9 and R3 nothing. The PREPAREs now disagree, nobody reaches 2 matching PREPAREs, and nothing commits. So nothing wrong happens, but nothing happens at all.
The way out is a view change. The client resends its request to all replicas; each backup starts
a timer and, when it expires, sends VIEW-CHANGE(v + 1) with the requests it prepared. The primary of the
new view is (v + 1) mod n = R1. With 2f + 1 VIEW-CHANGE messages it sends NEW-VIEW,
which re-issues a PRE-PREPARE for every slot that some replica had prepared (here none, so it just proposes the
client's x=7). The normal case then finishes in view 1, and R0 is just one outvoted backup.
Why 3 replicas can't survive 1 traitor
This is the Byzantine generals problem (Lamport, Shostak and Pease, 1982): three generals, one of them a traitor, cannot agree on a plan by messages alone. A loyal general who hears "attack" from one side and "retreat" from the other cannot tell which of the two is lying. In Demo 4 there are only R0, R1 and R2. A replica can wait for just 2 votes, because the third may be the silent traitor. The traitor R0 tells R1 x=7 and R2 x=9, and backs each of them with a matching COMMIT. R1 sees 2 votes for x=7, R2 sees 2 votes for x=9, and both commit. Waiting for all 3 votes instead would not help: then a traitor who stays silent stops the system forever.
With 4 replicas the same trick fails: to commit, a value needs 3 votes, and the traitor can add only 1 to each side. That is why every Byzantine-fault-tolerant protocol (PBFT, Tendermint, HotStuff) uses 3f + 1 replicas. The messages are signed or MACed, so a traitor can lie about its own vote but can't fake another replica's vote; see Digital Signatures.
Where PBFT ideas are used
Plain PBFT costs about n² messages per request, so it suits small groups (4 to a few dozen replicas). Blockchains with known validators use its descendants: Tendermint (Cosmos), HotStuff (the base of Diem's consensus) and IBFT in some Ethereum clients. Most data centres don't: they trust their own machines and use crash-fault protocols like Raft. For what a crash-fault majority store gives up in a partition see The CAP Theorem; for how nodes find out a peer is dead see Gossip and SWIM and Leader Election.
Open blockchains with no list of members use Proof of Work instead of voting: the cost of hashing, not a quorum, stops cheaters.
What the page leaves out
Signatures and MACs on every message, request digests (replicas send a hash, not the whole request), the message log, checkpoints and garbage collection of old slots, the high and low water marks, many requests in flight at once and batching, read-only requests, the proof a replica sends in VIEW-CHANGE (its prepared certificates), how NEW-VIEW fills gaps with no-ops, timer doubling, and replicas that recover. Simplifications: one request in one slot; the traitor's behaviour is scripted; a traitor that was voted out stays silent; the primary's PRE-PREPARE counts as its PREPARE; with n = 3 the page uses quorum n − f = 2 to show what goes wrong.