Making Byzantine tolerance practical
PBFT, Practical Byzantine Fault Tolerance, showed that tolerating malicious nodes can run fast enough for real services. It uses 3f plus 1 replicas, a designated primary per view, and a three phase agreement on each request's ordering.
The three phases
For a client request the primary assigns a sequence number, then the replicas run three message rounds.
- Pre prepare: the primary multicasts the request with its assigned sequence number.
- Prepare: replicas multicast prepare messages. A replica is prepared once it collects 2f matching prepares plus the pre prepare, proving a quorum agrees on ordering within this view.
- Commit: replicas multicast commit. After 2f plus 1 matching commits a replica executes the request and replies to the client.
A client accepts a result after f plus 1 matching replies, since at least one comes from an honest replica.
View changes
If the primary is faulty or slow, replicas run a view change to rotate to a new primary, carrying proof of prepared requests so committed ordering survives. The all to all messaging makes PBFT communication grow with the square of the replica count, which limits cluster size.
Key idea
PBFT commits each request through pre prepare, prepare, and commit phases with quorum certificates, tolerating f malicious replicas out of 3f plus 1 at the cost of quadratic messaging.