Practical Byzantine Fault Tolenrance 201
This post focuses on the Byzantine Paxos algorithm, whose most famous variant is Practical Byzantine Fault Tolenrance (PBFT).
This post focuses on the Byzantine Paxos algorithm, whose most famous variant is Practical Byzantine Fault Tolenrance (PBFT).
A quick look at the Byzantine Generals problem
The Byzantine Generals problem is a computer science problem about reliable communication and fault handling in a distributed system.
The problem goes like this:
There are N generals, each commanding a different army, and M of them are traitors who try to stop the others from following the agreement:
- 4 generals want to attack
- 4 generals want to retreat
- 1 traitor tells the first group he wants to attack, and tells the second group he wants to retreat
How can the loyal generals reach an agreement?
One way to solve Byzantine Generals:
If there are M traitors, there must be at least 2M+1 loyal generals. That takes M+1 rounds of message exchange, and O(MN2) messages in total, which is very expensive.
The Byzantine Paxos algorithm
Paxos was extended for real-world environments where nodes fail (randomly or because of attacks) at random times, or get exploited to cause damage. That extension is Byzantine Paxos.
Byzantine Paxos was introduced in 1999 by Castro and Liskov (Lab of computer science, MIT). It adds a verify message to check correctness and the ability of nodes in the network to reach consensus.

Byzantine Paxos is widely used through its practical version, with many modifications to fit real-world behavior, called Practical Byzantine Fault Tolerance (PBFT). PBFT is gaining adoption today because cyber attacks keep increasing, which leads to very high failure rates on network nodes. Such nodes are called faulty nodes.
The PBFT algorithm
PBFT used in state machine replication is modeled like this: each network node is treated as a state machine that handles client queries and replicates its state to other nodes. These nodes are called replicas. PFBT can work with R replicas numbered 0,1,…,R-1, where R = 3f+1 and f is the maximum number of replicas that can fail in the network.
Roles of the replica nodes:
- PBFT defines a natural number view v representing a time frame in which the network nodes operate stably.
- In each view v, one replica is chosen as the primary, and the others are backups.
- The primary of view v is determined by the formula p = v mod R.
- Whenever the primary fails, v is increased to v+1.
The PBFT algorithm basically works as follows:
- The client sends a request to the primary to perform an operation
- The primary multicasts it to the backups
- All nodes execute the request and send a response back to the client
- The client waits until it receives f+1 identical responses, then the response is accepted as valid.
Note: Like other state machine replication techniques, PBFT must satisfy these 2 requirements:
- Executing client requests is deterministic - meaning the same state and the same input request must produce the same result.
- All replicas start from the same state.
Client
Client c sends a query to the primary through a REQUEST message of the form (REQUEST,o,t,c), where t is the timestamp at send time and o is the operation c wants to run. After running PBFT, the replicas send the client a REPLY message of the form (REPLY,v,t,c,i,r), where:
- v is the current view
- t is the timestamp of the REQUEST message
- i is the replica number
- r is the result of executing operation o
The client waits for f+1 REPLY messages with the same t and r before accepting result r. That means the system has at least f non-faulty replicas.
If the client doesn’t receive enough REPLY messages within the timeout, it broadcasts the REQUEST message to all replicas (in case the primary has failed). Then, if a replica has already recorded that this REQUEST was processed, it immediately sends back the RESPONSE message. Otherwise, it forwards the REQUEST to the primary it knows.
If the primary doesn’t respond within the timeout, the system changes view using the view_change protocol, covered later.
How PBFT works under normal conditions
With no failures, the replicas operate steadily and all exchanged messages are recorded in the message log.
The state of each replica includes: the state of the service, the message log containing the messages that replica has accepted and processed, and the natural number v, the current view of that replica.
When primary p receives a request from a client (m), it starts a 3-phase protocol to multicast that request to the backups/replicas. The primary processes it right away without waiting. If the number of requests exceeds the maximum, requests are buffered and processed gradually. The 3-phase protocol consists of pre-prepare, prepare and commit. The first two phases are used to order requests sent within the same view. The last two phases are used to make sure the requests are ordered correctly.
Phase 1: pre-prepare
The primary assigns sequence number n to the request, multicasts a pre-prepare message along with the client’s request message (m) to all backups, and saves the message in its log. The pre-prepare message has the format (<PRE-PREPARE,v,n,d>,m), where v is the current view, m is the client’s request, and d is the digest of message m. Note that the request message m is not attached to the pre-prepare message, to keep the data size small. The main purpose of the pre-prepare message is to carry the sequence number n and the view number v.
A backup only accepts a pre-prepare message when:
- d is really the digest of m, by recomputing d from the request m it has.
- the view v is the same.
- the sequence number n is within h <= n <= H (h: low watermark, H: high watermark). This condition prevents a bad node from sending a huge number that would corrupt the current sequence list.
Phase 2: prepare
When replica i accepts the pre-prepare message, it creates a prepare message, multicasts it to the other replicas, and writes it to its log. The prepare message is (PREPARE,v,n,d,i). If it doesn’t accept, it does nothing. A prepare message is only accepted when: the signature is correct, the view numbers v match, and the sequence number n is within (h,H).
The pair of pre-prepare and prepare messages is considered valid on replica i if it has stored this information in its log: the request m, the view number v, the sequence number n, and 2f prepare messages received from other replicas that match the pre-prepare message it has. The check is done by comparing n, v and the digest d.
Phase 3: Commit
Replica i multicasts a commit message once it has received enough prepare messages. The message (COMMIT,v,n,D(m),i) goes to the other replicas. When a replica receives a commit message, it accepts it into its log if the conditions hold: the view number v and the sequence number n are the same.
There are two commit states: committed and committed-local:
- committed: if f+1 replicas agree with each other on m,v,n
- committed-local: if replica i received 2f+1 valid commit messages.
A replica executes the client’s request m once it reaches the committed-local condition and the sequence number n keeps ordering: 1) it is the largest among those already processed, and 2) it increases monotonically. The timestamp must also keep the ordering.
The figure below shows how the algorithm works, where C is the client, node 0 is the primary, and nodes 1, 2, 3 are replicas with node 3 being faulty.

Garbage Collection (cleaning up old data)
On each replica, the message log fills up over time. It’s essential to detect which messages are no longer needed: when request m has been executed by at least f+1 non-faulty replicas. Also, when a replica is missing messages that the other replicas have already discarded, it needs to resync its state with them. This sync happens periodically (a predefined constant), not on every request. The moment of state sync is called a checkpoint.
Each replica keeps a few copies of the state: the state at the last checkpoint, some checkpoints that aren’t stable yet, and the current state. Copy-on-write can be used to reduce the amount of state to store (more on that later).
Proving the correctness of a checkpoint works like this:
- When replica i wants to make a checkpoint, it multicasts a message (CHECKPOINT,n,d,i) to the other replicas. Here n is the sequence number of the last request, and d is the digest of the state.
- Each replica records checkpoint messages in its message log until it has 2f+1 messages with the same n and d. Then the checkpoint is considered correct and becomes stable. => That means 2f+1 nodes agree!
When checkpoint s is considered correct, all pre-prepare, prepare and commit messages with sequence number <= n in the message log are deleted to save storage. Later checkpoints with sequence number <=n are also rejected.
Checking data integrity depends on the cryptographic algorithm used for digest d. The checkpoint number is also used to recompute the upper bound H and lower bound h as follows:
- h = the sequence number of the last checkpoint
- H = h + k (k is a predefined constant, large enough that replicas don’t have to wait until the checkpoint becomes stable)
View Changes
The view-change protocol keeps the system running when the primary fails. It is triggered on timeout so the other replicas don’t have to wait forever for a multicast.
Backup replicas (non-primary) wait for a request once they have received a valid request that isn’t processed yet. A backup starts a timer whenever it receives a request, and the timer stops when the timeout expires with the node having processed no other request.
If the timer expires in view v, that backup moves to view v+1. That means it rejects all incoming messages with view number v, and multicasts a view-change message (VIEW-CHANGE,v+1,n,C,P,i) to all other replicas. Here n is the sequence number of the latest stable checkpoint (s) it (replica i) knows of, C is the set of 2f+1 checkpoint messages it holds that prove the correctness of s, and P is the set of all pre-prepare and prepare messages for requests m with 1) a sequence number greater than n, 2) the same view v, for which it (replica i) created a prepare message, along with the digest of m.
When the primary p of view v+1 receives 2f view-change messages for view v+1 from the replicas, it multicasts a new-view message (NEW-VIEW,v+1,V,O) to all replicas, where V is the set of view-change messages it received and O is the set of pre-prepare messages. How O is determined will be written later.
Some implementations that use PBFT
- Bitcoin
- Boeing 777, 787 Aircraft Information Management System, Flight Control System
- Spacecraft flight system: SpaceX Dragon
- Tendermint Core
Some other variants of PBFT
After Castro and Liskov published PBFT in 1999, several variants appeared to improve speed, such as Q/U, HQ, Zyzzyva, ABsTRACTs, A2M-PBFT-EA, MinBFT.