6. Practical: cryptography and the 3 percent

Why cryptography is not optional here

The quorum math of the third chapter has an unstated dependency, and it is time to make it explicit. The scheme counts messages: 2f+1 prepares, 2f+1 commits, f+1 matching replies. Counting only works if a message's sender cannot be faked. If a single faulty node could forge messages that appear to come from honest replicas, it could fabricate an entire quorum by itself, manufacture 2f+1 agreements out of nothing, and drive the honest replicas to commit whatever it liked. The arithmetic would be meaningless. So every message in PBFT is authenticated: a receiver can verify that a message genuinely came from the replica that claims to have sent it, and a faulty node cannot put words in an honest node's mouth.

This is why cryptography is load-bearing rather than decorative, and it is also why PBFT is not "trustless" in the sense the word later acquired. The protocol assumes a known, fixed set of replicas, each with a cryptographic identity that all the others recognize. You have to know who the participants are. Byzantine tolerance here means the known participants might misbehave, not that anonymous strangers can join. That assumption is the hinge on which the blockchain distinction in the next chapter turns.

One natural question deserves a direct answer: this cryptography does not buy back any replicas. PBFT still needs 3f+1 even though every message is authenticated, because that number comes from having to proceed after hearing from only n minus f replicas in an asynchronous network, not from any inability to tell who sent what. Signatures stop a faulty node from forging an honest node's words; they do not change how many replicas you must outvote.

The move that made it fast

Load-bearing cryptography is also where earlier Byzantine systems died, because the obvious way to authenticate a message is a public-key digital signature, and signatures are slow. Each signing and verification costs on the order of milliseconds, and PBFT is chatty: the prepare and commit phases are all-to-all, so a single request generates a flurry of messages across all the replicas. Sign and verify every one of them and the cryptography, not the network or the disk, becomes the bottleneck. This is roughly what happened to the Byzantine systems of the mid-1990s.

PBFT's central performance decision is to not use signatures for the common case. Instead it authenticates normal-operation messages with message authentication codes, symmetric-key tags that are about three orders of magnitude cheaper to compute than public-key signatures. A MAC lets the intended recipient verify the sender, which is all the normal protocol needs. Signatures are kept only for the few places that require a proof one party can show to a third, most importantly the view-change evidence, where a replica must convince a new primary of what it prepared. Reserving expensive cryptography for the rare case and using cheap cryptography for the hot path is the optimization the paper singles out, and it removed the main obstacle that had made Byzantine tolerance impractical. A handful of further tricks help, batching requests together under load and ordering by small message digests rather than whole requests, but the MAC decision is the heart of "practical."

The three percent

The argument for all of this is a number. Castro and Liskov did not just describe the algorithm; they built BFS, a Byzantine-fault-tolerant network file system, on top of a PBFT replication library, and measured it against a standard unreplicated NFS using the Andrew benchmark. BFS ran about three percent slower. That figure is the entire thesis of the paper compressed to a point. Tolerating arbitrary, malicious, colluding replica failures, the strongest failure model there is, cost roughly three percent over a system that tolerated nothing at all. Byzantine fault tolerance moved from "too expensive to consider" to "a small insurance premium," and that shift is why the paper mattered and why its descendants exist.

One limit is worth stating so the claim is not oversold. PBFT protects integrity and agreement, not secrecy. A faulty replica still sees the data it stores and can leak it, because replicas must operate on requests and state in the clear. The paper is candid that it does not solve fault-tolerant privacy. What it delivers is that the honest replicas agree and the service stays correct, cheaply, even while some of its members are actively hostile.

Principle: Correctness against lies is worthless if it is too slow to run, so the practical contribution is an engineering one: use cheap cryptography on the common path and expensive cryptography only where a portable proof is unavoidable. The measure of a security mechanism is not only that it works, but that its overhead is small enough that people leave it turned on.