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

The previous note explained why leader-based 3f + 1 BFT needs a third round. This note explains the opposite direction: why, once you have more replicas, one voting round can already leave behind enough honest evidence for the next view.

This post is still about leader-based BFT protocols such as PBFT and FaB.

It gives the clean 5f + 1 counting intuition. It is not the full proof of the tighter 5f - 1 result.

The Question

If 3f + 1 fails because the next leader does not inherit enough evidence, what changes at 5f + 1?

The overlap between the old quorum and the new quorum becomes large enough that the next leader is guaranteed to inherit a built-in honest majority of evidence for the committed value.

A Concrete Case

Take f = 2 and n = 5f + 1 = 11. Use:

Honest replicas: A, B, C, D, E, F, G, H, I
Byzantine replicas: X, Y

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

Suppose one honest replica committed x in the old view after seeing those 9 votes for x. Call that old commit quorum C. Now a new leader starts the next view and collects a fresh quorum Q of 9 messages.

Two such quorums overlap in at least:

(4f + 1) + (4f + 1) - (5f + 1) = 3f + 1

For f = 2, that is:

9 + 9 - 11 = 7

That is already much better than the 3f + 1 case. After removing up to f = 2 Byzantine replicas from that overlap, the next leader is guaranteed to inherit at least 2f + 1 = 5 honest witnesses from the old commit quorum.

Those 5 honest replicas are the honest evidence for x that survives into the next view.

Why A Conflicting Value Cannot Keep Up

Now ask how much support a conflicting value y can still have in that new-view quorum.

At most:

f = 2 honest replicas can sit outside the old commit quorum and prefer something other than x.
f = 2 Byzantine replicas can equivocate and also claim support for y.

So y can have at most 2f = 4 supporters in the new-view quorum.

That gives the key inequality:

evidence for committed x: at least 2f + 1 = 5
evidence for conflicting y: at most 2f = 4

Unlike the 3f + 1 case, the new leader does not see one lonely honest witness for x. It sees a built-in honest majority of evidence for x.

Why This Replaces The Third Round

In 3f + 1, the third round is needed because the first voting round can leave the critical fact too private. One honest replica may know that x is now mandatory, while the next leader still cannot recover that fact.

In 5f + 1, the larger quorums do part of that job for free. Once an honest replica commits x, any future new-view quorum is forced to contain enough honest remnants of that old quorum that x still dominates every conflicting value.

That is the intuition for why one voting round can now be enough. The quorum overlap itself spreads the old fact far enough.

How Real Protocols Encode This

Real protocols do not literally compare two counters called evidence for x and evidence for y. They encode the same safety condition through protocol objects such as certificates, locks, and vote rules.

In PBFT-style protocols, view-change messages carry prepared or commit-related evidence from earlier views. In HotStuff- and DiemBFT-style protocols, proposals, timeout messages, and votes carry quorum certificates and are checked against explicit safety rules. The mechanism changes, but the purpose is the same: a new leader must not be able to revive a conflicting branch once an old one may already be committed.

The Easiest Comparison

Setting	Old quorum overlap with new quorum	Honest evidence guaranteed to survive	Conflicting support can reach
`n = 3f + 1`	`f + 1`	`1` honest witness	Up to `2f`
`n = 5f + 1`	`3f + 1`	`2f + 1` honest witnesses	Up to `2f`

At 3f + 1, the old value does not dominate in the next view.
At 5f + 1, it does.

What About The Later 5f - 1 Result?

The clean counting argument above is a sufficient intuition for the classic 5f + 1 regime. The later 2021 result is tighter: 2-round PBFT-style partially synchronous Byzantine broadcast is possible in the authenticated setting already at n >= 5f - 1.

The high-level lesson is the same: once quorums are large enough, one voting round can leave behind enough recoverable evidence for the next view. But the exact 5f - 1 protocol does not follow from the simple 2f + 1 versus 2f argument used in this note. It uses richer objects instead: 4f - 1-vote quorum certificates, 4f - 1-message timeout certificates that lock blocks, and a new-view rule that forces the leader to propose from the block locked by that carried-forward evidence.

So if your goal is intuition, 5f + 1 is the easiest case to understand first.

At this point the right question is no longer the round count, but what the next view must be able to recover. The next note makes that explicit.

Series

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

Next: Why view-change safety matters in leader-based BFT