Byzantine Quorum Size Formula: Why 3-of-4 Beats 2-of-3

Ask ten engineers how many nodes need to agree before a signed checkpoint is trustworthy, and most will say "a majority." That answer works fine when every node is honest. It falls apart the moment one node can lie to two different observers at once, which is exactly what a compromised or buggy authority can do.

This is the problem Byzantine quorum systems exist to solve, and the fix isn't a bigger majority. It's a specific inequality that tells you how large your witness set needs to be for a given number of tolerated faults. Below is the derivation, a worked attack walkthrough, a lookup table, and a checklist you can apply to any quorum-based verification system you're building.

The Problem: Majority Vote Doesn't Survive Equivocation

A single authority signing a checkpoint proves that checkpoint existed. It does not prove the authority showed the same checkpoint to everyone. If that authority is compromised, it can hand one client checkpoint X and another client checkpoint Y, and both clients will see a locally valid, correctly signed view with no way to detect the fork on their own.

Adding witnesses fixes this only if you choose the witness threshold correctly. A threshold that looks safe on a whiteboard, like 2-of-3, can still let two contradictory checkpoints both pass. The rest of this guide walks through why, and what threshold actually closes the gap.

Step 1: Understand What Quorum Intersection Actually Guarantees

The property you need isn't "most witnesses agree." It's "any two quorums that could each independently form must share at least one honest member." That shared member is what prevents two conflicting histories from both getting approved, because an honest witness never signs two different things for the same slot.

If two valid quorums can form without sharing an honest witness, you have no safety guarantee at all. Two isolated observers can each collect a legitimate-looking quorum for two different, mutually exclusive facts. That's the exact failure mode a compromised authority exploits.

Step 2: Walk Through the Double-Signing Attack on 2-of-3

Here's the concrete failure. Set up three witnesses, A, B, and C, with a 2-of-3 approval threshold. Witness B turns out to be Byzantine, meaning it will sign whatever it's told to sign, including two contradictory things.

An attacker asks B to sign root X alongside A, and separately sign root Y alongside C. Now root X has signatures from A and B, two out of three, which clears the 2-of-3 bar. Root Y has signatures from B and C, also two out of three, which also clears the bar.

Both roots are independently "approved." Job 1 sees root X as valid. Job 2 sees root Y as valid. The only witness common to both quorums is B, the compromised one, so there's zero honest overlap forcing consistency.

The threshold felt safe because it was a majority, but a majority isn't the property that matters. Intersection is.

Here's the same attack expressed as a quick simulation you can run to convince yourself:

witnesses = {"A", "B", "C"}
byzantine = {"B"}

root_x_signers = {"A", "B"}
root_y_signers = {"B", "C"}

quorum = 2

root_x_valid = len(root_x_signers) >= quorum
root_y_valid = len(root_y_signers) >= quorum
honest_overlap = (root_x_signers & root_y_signers) - byzantine This pairs well with [ai code review checklist: what to automate vs block explained](/ai-code-review-checklist-what-to-automate-vs-block).

print(root_x_valid, root_y_valid, honest_overlap)
## True True set() -- both roots pass, no honest witness forces a choice

Step 3: Derive the Formula That Actually Closes the Gap

The rule you need is: for up to f Byzantine witnesses among n total, any two valid quorums of size q must intersect in more than f members. Written as an inequality, that's q > (n + f) / 2.

The logic behind it is simple once you see it. Two quorums of size q drawn from n witnesses overlap in at least 2q - n members, by basic set arithmetic. For that overlap to guarantee at least one honest witness even in the worst case, where f of the overlapping members are Byzantine, you need the overlap to exceed f. Solve 2q - n > f for q and you get q > (n + f) / 2.

Plug in f = 1. With n = 3, the inequality becomes q > 2, meaning q must be at least 3, not 2. That's why 2-of-3 fails and 3-of-3 would be needed if you insist on only three witnesses, which leaves zero slack for an offline witness. The practical fix is to add a fourth witness instead.

Step 4: Apply the Standard Construction, n = 3f + 1 and q = 2f + 1

Rather than solving the inequality from scratch every time, use the standard Byzantine quorum construction: set n = 3f + 1 total witnesses and require q = 2f + 1 signatures. For f = 1, that's n = 4 and q = 3, the 3-of-4 rule.

Check it against the attack from Step 2. With four witnesses, A, B, C, D, and B still Byzantine, root X needs three signers, say A, B, and one more. Root Y needs three signers too.

Because B can only contribute to one side of the double-sign without a second corrupted witness, at least one of the two roots can't reach three genuine signatures. This blocks the dual-admit that broke 2-of-3.

This construction is also the minimum witness set for a given f. You can always add more witnesses beyond 3f + 1 and scale q proportionally, which buys you flexibility for witness rotation or geographic distribution, but you can't go below it without losing the guarantee.

Step 5: Look Up Your Own Fault-Tolerance Target

Use this table to pick n and q for the number of Byzantine witnesses you want to tolerate. Each row uses the standard n = 3f + 1, q = 2f + 1 construction.

Also read: go deeper on beyond the 100x engineer: rethinking ai adoption

| f (tolerated Byzantine witnesses) | n (total witnesses) | q (required quorum) | |---|---|---| | 1 | 4 | 3 | | 2 | 7 | 5 | | 3 | 10 | 7 | | 4 | 13 | 9 | | 5 | 16 | 11 |

Notice the pattern: each additional tolerated fault costs three more total witnesses and two more required signatures. That cost is why most real systems target f = 1 or f = 2 rather than scaling fault tolerance arbitrarily. Witness sets get expensive to operate and coordinate past a handful of members.

Step 6: Checklist for Choosing Witness-Set Size in Any Quorum System

Before you hardcode a threshold in your verification pipeline, run through this list.

1. Decide f explicitly. Don't pick a witness count first and back into a threshold; start from how many compromised or offline witnesses you must survive.
2. Compute q from q > (n + f) / 2, or use n = 3f + 1 and q = 2f + 1 if you want the minimum-size construction.
3. Verify quorum on the exact artifact, not just a version number or timestamp. A quorum over "minimum version 2" is weaker than a quorum over the specific signed root at that version.
4. Add a monotonic freshness check alongside the quorum. A quorum on a stale but internally consistent head will pass forever unless you also require progress.
5. Persist signed receipts with enough context that a later auditor can detect a fork without re-trusting the original authority.
6. Govern witness-set membership with the same anti-rollback discipline as your version floor. If whoever runs CI can shrink the set back to a weaker n or q, the arithmetic in Step 4 becomes irrelevant.
7. Fail closed when you can't reach quorum, rather than falling back to a single authority's word, which reopens the exact equivocation problem you built the witness set to close.

What to Expect Next

Getting the quorum math right solves the intersection problem, but it assumes witnesses don't collude and that membership itself is tamper-resistant. The next design question worth tackling is how you rotate witness keys and update n or q over time without ever letting a single writable slot undo the guarantee you just built.