byzantine fault tolerance, and when nodes lie

With three replicas and two votes required, I can leave two conflicting histories supported by quorums that share only the liar. Neither honest replica has to vote twice. Add a fourth replica and require three votes, and every quorum pair has an honest voter in common. That is the result of the small set check below. The protocol still has to make that honest voter refuse the conflicting history, including after the leader changes.

Raft and Paxos assume that replicas obey the voting rules and keep the required state through a crash. A replica that votes for conflicting proposals has stepped outside that model. Signing both proposals would only confirm who contradicted itself. If different organizations operate the replicas, I need to decide whether I can trust them to follow those rules. PBFT gives me a way to trace a proposal when one primary refuses to do so.

two orders from the commander

In Lamport, Shostak, and Pease's 1982 paper, generals send orders by messenger. When the commander is loyal, all loyal lieutenants should decide on that commander's order. Now let the commander tell one to "attack" and another to "retreat"; the commander is faulty, but the loyal lieutenants still have to agree with each other. Asking them to forward what they heard adds another possible liar: a faulty lieutenant can invent an order it never received.

Sending those conflicting accounts is equivocation. Even with an identified sender, each lieutenant has only its own copy of the order to work from. The sender may have told everyone else something different.

the overlap must outnumber the faults

I started the enumerator with three replicas and asked for two votes. Its three pairs of quorums include {0, 1} paired with {0, 2}. Replica 0 is the entire overlap. If it lies, it can give each of the other replicas a different history and a second vote to go with it. Replicas 1 and 2 need never contradict themselves. In the script's output, the minimum overlap is one; remove faulty replica 0 and the honest overlap falls to zero.

Now add replica 3 and ask for three votes. There are six pairs to check this time. Every intersection contains at least two replicas, so removing 0 always leaves someone. That remaining honest voter is what I was missing with three replicas. The script checks the sets, not PBFT: no messages or elections run in this model.

I can work backward from those counts. How many replies can I demand if all f faulty replicas refuse to answer? At most N−f, so q ≤ N−f. Now let the faulty ones answer both ways instead. Two sets of q votes drawn from N replicas must share at least 2q−N names. I need that overlap to contain more than the f names the attacker controls: 2q−N > f.

Try the largest reachable quorum, q=N−f. Substitution leaves N−2f > f, or N > 3f. Hence 3f+1 is the first integer replica count that works. Stop at N=3f and the smallest overlap is exactly f; the attacker can occupy all of it. Replica 0 did just that in our three-replica check.

Use PBFT's counts in the same calculation: N=3f+1, q=2f+1, hence 2(2f+1) − (3f+1) = f+1 shared voters. Spend the entire budget of f faults on that overlap and there is still a voter left. A crash-only majority can survive f crashes with 2f+1 replicas because it trusts the shared voter's behavior. Replica 0 showed why I could not use that argument here. I still owe the honest voter a rule: what state must it remember, and which vote must it refuse after a leader change? The protocol's voting and locking rules have to answer that.

I read 3f+1 with those two conditions attached: collect a quorum while faulty replicas are silent, and keep an honest voter in every intersection. Change the timing, authentication, or decision model for Byzantine agreement and the bound may change. The enumeration checks this particular construction.

following a proposal through PBFT

Castro and Liskov's 1999 PBFT paper supplies the rules missing from the set check. Its replicas run a deterministic service, know the membership, and authenticate messages. The normal path avoids doing a public-key operation for every message. We can delay messages arbitrarily and retain safety, although progress can stop. To make progress, communication must eventually behave well enough for a correct primary to finish its work.

For the message trace, I'll call the faulty primary P. Its three backups, A, B, and C, all follow the protocol. P picks a sequence number and view, then sends a pre-prepare naming the request digest. Give A and B a proposal for x. Give C a proposal for y at that very same position in that view. P has contradicted itself, but each backup has only its own proposal to check before accepting it.

A and B multicast prepare messages for x. C sends one for y. In the original protocol, being prepared requires the matching pre-prepare and 2f matching prepares from distinct backups. A backup counts its own prepare. Here f=1, so A and B each have the two backup prepares needed for x, along with P's matching pre-prepare. Both can become prepared. C has only its own prepare for y.

P can't add a second backup prepare by sending another message under its own name. Its authority as primary let it propose conflicting histories; it doesn't let it impersonate another voter. The prepared certificate ties x to this sequence number in this view.

I can follow that argument within one view. What will the next primary know? After becoming prepared, a replica multicasts commit. A prepared replica needs 2f+1 matching commits, including its own, before executing the request, and earlier sequence numbers must have executed first. In our four-replica case, three commits include at least two honest senders. Both were prepared for x before sending those commits.

Try to collect three view-change reports while avoiding both honest prepared replicas. Only two replicas remain, so it can't be done. At least one report carries evidence of x to the replacement primary. Section 4.4 of the paper spells out how the new primary must check the reports and choose a continuation; honest replicas check that evidence before voting in the new view. The commit phase makes execution depend on evidence that reaches across this change of primary. It also explains why preserving protocol state through recovery matters: a replica that forgets what it prepared can't supply the evidence this argument needs.

A timeout lets replicas attempt another primary when P stalls or misbehaves. They still have to check the prepared certificates before accepting the new view. On the client side, f+1 matching replies are enough to include at least one honest replica; a single reply could have come from P.

paying for the exchanged evidence

For one replica in a group of 100, there are 99 outgoing destinations in an all-to-all round. Do that for every sender and I have 100 × 99 = 9,900 directed sends to account for. It is tempting to turn that straight into a cost per request. I still need the primary's and backups' actual message counts, the number of requests sharing a batch, and the sizes and authentication work that the hardware must handle.

In the HotStuff paper, I can stop drawing an arrow from every voter to every recipient. The votes first meet at a collector. With a threshold signature, the evidence leaving that collector is a compact quorum certificate, so each recipient has one thing to check instead of the whole vote list. The paper gets linear communication under partial synchrony and responsive progress with a correct leader. Tendermint also rotates proposers, but I'd need another message trace for it. Its vote rounds use gossip. The fact that a proposer rotates gives me no message count on its own.

who gets a vote?

What stops replica 0 from renaming itself a thousand times? The configured membership does, both in the set check and in PBFT's A, B, C, and P. Each name has one known owner. For open participation, counting names would hand an attacker as many votes as it could invent. That is the Sybil problem. Proof of work gives influence to computing effort rather than names. More names can't create more committed stake. With proof of stake, I'd count that stake, then check the protocol's rules for the penalties a voter faces. After either choice, we have assigned influence; we have yet to say how those votes agree on a history.

With a Bitcoin-style history, each additional confirmation can make a replacement by reorganization less likely, under the protocol's assumptions. A client still relies on that probability. Buterin and Griffith's Casper FFG paper adds checkpoint votes with accountable safety. Two conflicting finalized checkpoints would implicate a threshold of stake in broken voting rules, for which it can be penalized. Clients get a different kind of evidence from a BFT certificate than from a count of confirmations.

choosing the fault assumption

Bring P back under the same operator as A, B, and C. I might now be willing to trust all four to persist their voting state and follow the rules, in which case Raft or Paxos could be enough. But a software bug could still produce the two proposals we traced, and a compromise could produce them deliberately. The backups would see the same x and y whether I owned P or somebody else did. I'd still use checksums against corruption, plus isolation and operational controls for the risks they can reduce. I can use those protections without full BFT, while keeping the crash model's limit explicit. Adding machines doesn't make it handle arbitrary messages.

Leave P with another organization and require safety despite its contradictions, and I need an argument like the PBFT trace. Known membership also leaves decisions outside that trace. Who may admit a new member or replace its key? What happens when a member refuses to cooperate? An open network needs a rule for voting weight as well. Proof of stake with BFT-style finality is one possible answer, rather than a consequence of allowing anyone to participate.

For f=1, the two formulas ask for three crash-tolerant replicas or four Byzantine-tolerant ones. The fault count includes different behavior in each case. Neither formula prices a request: that depends on the protocol's message exchange and the system running it, and a fixed operating-cost percentage would need a deployment measurement. The set check stops at finding the honest overlap. The PBFT trace then tells me what its honest voter must retain, and why the next primary cannot simply discard that evidence.