Why leader-based 3f+1 BFT needs a third round

This post is about leader-based BFT protocols such as PBFT. In the usual 3f + 1 setting, the happy path is usually described as three rounds:

1. The leader proposes a value.
2. Replicas vote for it.
3. Replicas who saw enough round-2 votes send one more round of commit or acknowledgment messages.

The Question

The natural question is simple:

If a quorum is already 2f + 1, and if a replica sees 2f + 1 votes in round 2, why is that not already enough to commit? Why is round 3 needed at all?

If a replica already saw a full quorum, it is tempting to think the job is done. At first glance, round 3 looks redundant.

Views and View Change

These protocols run in numbered views. Each view has a leader. If replicas stop making progress in one view, they timeout and move to the next view with a different leader. That move is a view change.

To start the next view, the new leader collects messages from a quorum of replicas. In this post, when I say the next quorum, I mean that quorum gathered by the new leader during the view change.

So the real question is not just whether one replica saw enough votes. It is whether, if that view ends badly, the next leader can still recover what happened without violating agreement.

The Claim

One honest replica may already have enough evidence to commit x, while the next leader still cannot tell that this happened. If that occurs, the next view might continue as if nothing was committed.

That would be fatal, because once one honest replica commits x, no later view may lead honest replicas to commit a different value y.

Round 3 exists to stop that from happening. It spreads the evidence of the old view widely enough that the next leader can recover it during the view change.

The rest of the post shows this with one concrete n = 7, f = 2 execution. It is not the full impossibility proof, but it makes the obstruction explicit.

A Concrete Case

The easiest way to see the issue is to stop talking abstractly and write down one full execution. The example below shows how one honest replica can already have enough evidence to commit x, while the next leader still cannot recover that fact during the view change.

Take f = 2, so n = 3f + 1 = 7. Use:

• Honest replicas: A, B, C, D, E
• Byzantine replicas: X, Y

A commit quorum has size n - f = 5. A new leader also collects 5 view-change messages before moving on.

Two such quorums overlap in at least:

(2f + 1) + (2f + 1) - (3f + 1) = f + 1

For f = 2, that is:

5 + 5 - 7 = 3

But among those 3 overlapping replicas, up to 2 may be Byzantine. So the next quorum is guaranteed to inherit only one honest witness from the old commit quorum.

World 1: x Is Secretly Committed

1. Byzantine leader X equivocates:
   • sends proposal x to A, B, C
   • sends proposal y to D, E
2. Honest replicas vote once:
   • A, B, C vote for x
   • D, E vote for y
3. Delivery is selective. Replica A receives votes for x from: A, B, C, X, Y
4. That is 5 votes, so A commits x.
5. Right after that, the network delays A's outgoing messages. This does not count as an extra Byzantine fault in partial synchrony. It just means the others do not learn yet what A learned.
6. New leader D starts the next view and collects 5 view-change messages from: B, D, E, X, Y

Call the old commit quorum C and the new leader's quorum Q:

C = {A, B, C, X, Y}
Q = {B, D, E, X, Y}
C ∩ Q = {B, X, Y}

The overlap has size 3, but only B is guaranteed honest.

So what does D learn?

In reality, A already committed x. So from this point on, any execution that later commits y would violate agreement. In that sense, only x is safe.

World 2: The Same New-View Evidence, But No Commit

Now change just one thing. In World 1, replica A received votes for x from A, B, C, X, Y and committed x. In World 2, suppose Y's vote for x never reaches A.

Then A sees only 4 votes for x: A, B, C, X. That is not enough to commit. So in World 2, no honest replica commits anything in that view.

But the new leader D still collects the same 5 view-change messages from B, D, E, X, Y, and they can still look exactly the same as in World 1:

So from D's point of view, World 1 and World 2 look the same, even though in World 1 an honest replica already committed x and in World 2 no one did.

Why This Is The Core Difficulty

This is the simplest form of indistinguishability:

• In World 1, preserving x is mandatory.
• In World 2, no honest commit happened yet, so a different value may still be legal.
• But the new leader sees the same evidence in both worlds, so it cannot know which world it is in.

That is why one honest witness is not enough. A single vote for x proves only that someone supported x. It does not prove that an honest replica already saw a full commit quorum for x.

A vote for x is not the same thing as durable evidence that x has already become the only legal continuation.

What The Third Round Buys

The extra round is not just more voting. It forces the fact that x is now mandatory to be copied into enough honest places that a future leader cannot miss it.

In other words, the third round makes the commit evidence recoverable.

Real protocols encode this with protocol-specific view-change evidence. The exact mechanism may be prepared or commit-related evidence in PBFT-style protocols, or quorum certificates and vote rules tied to earlier certificates in newer descendants, but the job is the same: the next leader must be forced to respect any value that may already have become mandatory.

With larger replica sets, such as the FaB-style 5f + 1 regime or the later 5f - 1 bound, the overlap between old and new quorums is larger, so one voting round can already leave behind enough honest evidence. At 3f + 1, it cannot.

For the clean FaB-style 5f + 1 intuition, larger overlap alone already explains why one voting round can be enough. The tighter 5f - 1 result needs extra certificate-and-lock structure during view change.

What This Example Does And Does Not Prove

This execution shows the obstruction. It explains why the hidden commit story is a useful intuition.

It is not the full impossibility proof. The formal lower bound is stronger: it rules out all 2-round PBFT-style partially synchronous Byzantine broadcast protocols below the right threshold, not just the naive version sketched here.

The precise 2021 result is:

2-round PBFT-style partially synchronous Byzantine broadcast is possible if and only if n >= 5f - 1.

So for f >= 2, the optimal-resilience point n = 3f + 1 lies strictly below that threshold, and the third round is unavoidable.

The special case f = 1 is different: 3f + 1 = 5f - 1 = 4. That is why the usual slogan 3f+1 needs 3 rounds should always be read as shorthand for the standard regime, not as a literal theorem for every f.

So what changes when one voting round does become enough? The next note answers that question.

Series

Next: Why larger replica sets can replace the third round in leader-based BFT

Sources

• Good-case Latency of Byzantine Broadcast: A Complete Categorization
• Brief Note: Fast Authenticated Byzantine Consensus