The Practical Guide To Implementing A Consensus Algorithm For Byzantine Faults: PBFT

Imagine you are not a single person, but a committee of five generals. You, and your four colleagues, are camped around a hostile city. The only way to win is to coordinate a simultaneous attack. You can send messages to one another, but there’s a catch: the messages are delivered by messengers who can be captured, delayed, or replaced. Worse, one of the generals might be a traitor. He might send you a message saying “Attack at dawn,” while sending another general a message saying “Retreat at sunset.” He might lie about having received a message, or simply stay silent to sow chaos. How do you, as a loyal general, confidently commit to a plan, knowing that a traitor is actively trying to break the entire operation?

This is the Byzantine Generals Problem, a thought experiment proposed by Leslie Lamport, Robert Shostak, and Marshall Pease in 1982. It is the foundational riddle of distributed computing. While the generals are a metaphor, the reality is far more concrete and far more frightening: the “traitors” are software bugs, hardware glitches, network partitions, and—most critically—malicious actors who have compromised a server.

For decades, this problem was considered an academic curiosity, a theoretical upper bound on what was possible. The consensus was simple: you need expensive, special-purpose hardware (like a Boeing 777’s flight control computer) or you accept that your system can only tolerate “crash faults”—where a node simply stops working, but never lies. This led to the widespread adoption of algorithms like Paxos and Raft. These algorithms are magnificent pieces of engineering, powering everything from Google’s Chubby lock service to Kubernetes. But they share a fatal flaw: they trust the data they receive. If a Raft leader becomes corrupted, it can cause catastrophic damage—proposing conflicting log entries, suppressing commits, or even splitting the cluster into multiple leaders.

Enter Practical Byzantine Fault Tolerance (PBFT) . Designed by Miguel Castro and Barbara Liskov in 1999, PBFT was the first algorithm to prove that Byzantine fault tolerance could be achieved in a practical, asynchronous network without requiring trusted hardware. It brought consensus into the realm of real-world distributed systems, paving the way for modern blockchain platforms like Hyperledger Fabric, Zilliqa, and many permissioned blockchains. But understanding PBFT is not just about blockchain—it is about understanding how to build systems that survive the worst possible failures.

In this guide, we will tear apart PBFT piece by piece. We will examine its core phases, its view-change protocol, its safety and liveness guarantees, and its performance characteristics. We will walk through a simplified pseudocode implementation, analyze real-world trade-offs, and compare PBFT with newer Byzantine fault-tolerant algorithms. By the end, you will have a deep, practical understanding of how to implement consensus when you cannot trust anyone.

1. The Byzantine Generals Problem: A Deeper Look

Before diving into PBFT, it is worth revisiting the Byzantine Generals Problem with modern terminology. The problem is often stated as: “How can a group of distributed processes reach agreement on a value when some of them may be faulty, and the faulty processes may behave arbitrarily?”

1.1 The Original Three-Generals Variant

The classic formulation involves three generals. Two loyal generals must agree on a common attack plan (e.g., attack or retreat). The third general may be a traitor. Lamport showed that with only three generals, no solution exists if one is traitor. Why? Because a loyal general receives two conflicting messages—one from the other loyal general and one from the traitor—and cannot determine which is correct. More generally, to tolerate f Byzantine faults, you need at least 3f + 1 nodes. This is a fundamental lower bound.

1.2 Assumptions of the Byzantine Model

In the Byzantine fault model, a faulty node can do anything:

• Send arbitrary messages (including false messages)
• Refuse to send messages
• Collude with other faulty nodes
• Delay messages arbitrarily (but not indefinitely, as we assume eventually messages arrive)
• Actively try to break the protocol

This is in contrast to the crash fault model, where a faulty node simply stops. Byzantine faults are strictly more general.

1.3 Why Is Byzantine Fault Tolerance So Hard?

The core difficulty lies in equivocation: a faulty node can tell different lies to different honest nodes. In a crash fault model, if a leader fails, all honest nodes eventually detect the absence of messages. In Byzantine model, a leader might send conflicting proposals to different followers. Classic algorithms like Paxos assume that nodes are “truthful” in the sense that they never spread conflicting information. The very mechanism of Byzantine consensus requires collective witness and cross-checking.

2. The Rise of Practical Byzantine Fault Tolerance

2.1 Before PBFT: The Academic Era

In the 1980s and 1990s, Byzantine fault tolerance was studied primarily in theoretical contexts. The famous DLS paper (Dwork, Lynch, Stockmeyer, 1988) proved that consensus is impossible in an asynchronous system with even a single crash fault—but that using a weak form of synchrony (eventual synchrony) you could achieve consensus. Several Byzantine agreement protocols were proposed, but they relied on massive message complexity (O(n²) or even O(n³)) and required full synchronous rounds. They were too slow and resource-intensive for practical use.

2.2 The PBFT Breakthrough

Castro and Liskov’s insight was that you could design a practical Byzantine fault-tolerant replication algorithm by:

• Using primary-based consensus (one node acts as leader for a view)
• Reducing message complexity to O(n²) for normal operation
• Using digital signatures (or MACs) to authenticate messages
• Adding a view change mechanism to replace a faulty primary
• Basing the algorithm on quorums and preparation phases that ensure safety even with equivocation

They implemented PBFT for a replicated file system (the “Byzantine File System” or BFS) and showed that it could achieve throughput within 3% of non-replicated systems in a local area network. That was a shock to the community. For the first time, Byzantine fault tolerance was practical.

2.3 PBFT’s Core Idea: Three Phases

PBFT works in three phases: pre-prepare, prepare, and commit. The leader (primary) proposes a value (e.g., a block of transactions) in a pre-prepare message. The replicas then go through a prepare phase to ensure that no other conflicting value has been prepared, and a commit phase to ensure that the value is finalized. The algorithm guarantees safety as long as at most f nodes are faulty (with n = 3f+1 replicas total). Liveness is guaranteed under eventual synchrony (i.e., after a Global Stabilization Time, messages arrive within bounded delay).

3. PBFT Algorithm Deep Dive

3.1 System Model and Assumptions

• Nodes: There are N = 3f + 1 replicas, where f is the maximum number of faulty nodes.
• Network: Asynchronous with eventual synchrony. Messages may be arbitrarily delayed, but are not lost (or if lost, eventually retransmitted). The network is not Byzantine—we assume point-to-point reliable links.
• Cryptography: Each node has a public/private key pair for digital signatures. Alternatively, we can use message authentication codes (MACs) with pairwise keys for efficiency. PBFT famously uses MACs to reduce overhead, but we will use signatures here for simplicity.
• Client: Clients send requests to the replicas. The replicas process requests and send replies. A client waits for f+1 identical replies to be sure the request has been committed (since at most f replicas are faulty).

3.2 Views and View Number

PBFT is organized in a sequence of views. Each view has a designated primary (leader). The primary is chosen deterministically: primary = view number mod N. When the primary is suspected to be faulty (e.g., not proposing requests in a timely manner), a view change is triggered to move to the next view and install a new primary.

3.3 Normal Case Operation

The normal case (when the primary is honest) proceeds through the following sequence:

1. Client sends request to the primary (or all replicas, but primary is typical). The request is signed by the client.

2. Pre-prepare phase: The primary assigns a sequence number n to the request, creates a pre-prepare message containing the request, sequence number, current view, and its signature. It sends this message to all other replicas.

3. Prepare phase: Upon receiving a valid pre-prepare, a replica (including the primary itself) multicasts a prepare message to all other replicas. The prepare message contains: view, sequence number, digest of the request, and the replica’s signature.

   A replica collects prepare messages. It accepts the pre-prepare and enters the prepared state for that view and sequence number when it has received 2f prepare messages from different replicas (including its own). The condition is: 2f+1 total messages (pre-prepare + 2f prepares) have been seen matching the same view and sequence number.

4. Commit phase: After reaching the prepared state, each replica multicasts a commit message to all others: view, sequence number, digest, and signature. A replica commits the request when it receives 2f+1 commit messages (including its own) that match. At that point, the request is considered committed, and the replica can execute it and send a reply to the client.

3.4 Why Three Phases?

Why not just two phases? The prepare phase ensures that no two honest replicas can prepare conflicting values for the same sequence number in the same view. The commit phase ensures that after a view change, the new primary can reliably identify which requests were committed in prior views. The commit phase also prevents a situation where a faulty primary could make some replicas commit while others do not.

3.5 The Importance of Quorums

PBFT uses quorum sizes of 2f+1 for both prepare and commit. This ensures that any two quorums intersect in at least f+1 honest replicas. This overlapping guarantees safety: a value that has been committed cannot later be “uncommitted” because any new quorum will contain at least one honest replica that knows about the commit.

3.6 Liveness and View Change

What if the primary is faulty and never proposes a request? Or proposes conflicting requests? Then the system stalls. PBFT uses a view change protocol to recover. Here’s a simplified view change:

• A replica suspects the primary is faulty (e.g., a timer expires while waiting for a pre-prepare). It increments its view number and multicasts a view-change message to all other replicas.
• The view-change message includes the latest known committed request, and a set of prepared proofs (evidence that a request reached the prepared state in the old view).
• The new primary (for the next view) collects 2f+1 view-change messages. It then sends a new-view message to all replicas, containing a set of proposals that must be retransmitted in the new view.
• The replicas then revert to the normal protocol with the new primary.

The view change ensures that requests that were prepared (but not yet committed) are not lost. It also guarantees liveness: eventually an honest primary will take over and progress will resume.

3.7 Garbage Collection

To prevent unbounded log growth, PBFT uses checkpointing. Every so many requests (e.g., every 100), replicas generate a checkpoint containing the state after executing those requests. They multicast checkpoint messages, and when a replica receives 2f+1 matching checkpoints for a given sequence number, it can discard all log entries up to that point.

4. Safety and Liveness Proof Sketch

4.1 Safety

Safety means that if a request r is committed at some honest replica, then no other request r’ can be committed at the same sequence number (or a conflicting sequence number with the same client request). PBFT achieves safety via quorum intersection: to commit a request, a replica needs 2f+1 commit messages. Any two quorums of 2f+1 replicas intersect in at least f+1 replicas. Since at most f are faulty, at least one honest replica belongs to both quorums. That honest replica would have seen both commits and thus would have prevented the second commit from occurring (because it would have detected a conflict at the prepare phase). Formal proof uses induction on view numbers.

4.2 Liveness

Liveness means that all client requests eventually receive a reply (i.e., are committed). Under eventual synchrony, the view change mechanism ensures that if the current primary is faulty, a new primary will be elected. If the new primary is also faulty, another view change occurs. Because views are monotonic and there are at most f faulty nodes, after at most f+1 view changes, an honest primary will be in charge. Under eventual synchrony, that honest primary will be able to propose requests and reach consensus, ensuring liveness.

5. Performance Analysis

5.1 Message Complexity

In the normal case, PBFT uses O(n²) messages per request: each replica sends one pre-prepare (if primary), n-1 prepares, and n-1 commits (all to all). That totals roughly 3n messages, but each message is multicast to all n-1 other replicas, leading to O(n²) network messages. For a system of 4 nodes (f=1), that’s 3×4 = 12 messages per request? Wait, careful: primary sends one pre-prepare to all (n-1 messages). Each of the n replicas sends prepares to all (n*(n-1) messages). Then each sends commits to all (n*(n-1) messages). Total ~ 2n(n-1) + (n-1) ≈ O(n²). For n=4, that’s 243 + 3 = 24+3 = 27 messages. That is higher than Raft’s O(n) (leader broadcasts to followers, followers acknowledge, then leader commits). However, PBFT’s advantage is resilience to Byzantine faults.

5.2 Latency

PBFT requires three message phases (pre-prepare, prepare, commit). In a synchronous network, that means three round trips after receiving the client request. Raft requires two (leader to followers, followers to leader). So PBFT adds one more network round trip. In practice, this leads to higher latency, typically in the range of a few milliseconds on a LAN, but can be significant in WAN environments.

5.3 Throughput

Castro and Liskov’s original implementation achieved ~30,000 requests per second on a cluster of 4 machines (f=1) for simple operations. That was impressive for 1999. Modern implementations, using batched requests and optimizations like speculation (e.g., Zyzzyva), can achieve much higher throughput. However, PBFT’s O(n²) communication becomes a bottleneck as n grows. For larger systems, alternative algorithms (like HotStuff with O(n) communication using linear broadcast) are preferred.

5.4 Client Overhead

Clients must send requests to the primary (or broadcast) and wait for f+1 identical replies. That adds overhead but is manageable.

6. PBFT vs Other BFT Protocols

PBFT is not the only game in town. Let’s compare it with a few notable alternatives.

6.1 Tendermint (Cosmos)

Tendermint is a BFT consensus algorithm used in many blockchains. It uses a rotating leader (similar to PBFT’s view changes) but with a two-phase commit (pre-vote and pre-commit) plus a commit phase. It also has a lock mechanism to prevent equivocation. Tendermint is designed for a public setting with stake-based voting, but the core consensus is similar to PBFT. Key differences:

• Tendermint uses validators with voting power, not equal replicas.
• It has a propose, pre-vote, pre-commit, commit cycle (more phases).
• It does not require a view change message; instead, it uses timeout mechanisms to move to the next round.

6.2 HotStuff (Libra/Diem)

HotStuff is a more recent BFT algorithm developed by the VMware research group. It achieves linear communication in the normal case by using a three-chain structure and a leader that collects signatures. HotStuff is simpler and more efficient for large networks (n > 100). PBFT’s O(n²) becomes impractical at that scale. HotStuff forms the basis of Facebook’s Libra (now Diem) blockchain.

6.3 IBFT (Istanbul BFT)

IBFT is used in Hyperledger Besu and Quorum (Ethereum-based). It is a variant of PBFT that uses a round-robin leader rotation and a three-phase commit (pre-prepare, prepare, commit) with a round change mechanism. IBFT is simpler than full PBFT but makes stronger synchrony assumptions (it requires a predictable round time). It is popular in permissioned blockchain settings.

6.4 Practical Byzantine Fault Tolerance vs. Raft

7. Implementing PBFT: A Pseudocode Walkthrough

Let’s walk through a simplified implementation of PBFT in pseudocode. We’ll assume a static set of N replicas, each with a unique ID. We’ll use digital signatures for simplicity (though real implementations use MACs for efficiency). We’ll also assume a reliable FIFO channel between each pair.

7.1 Data Structures

# Global constants
N = 4  # 3f+1, f=1
f = 1
MAX_FAULTY = f

# Per replica state
class Replica:
    def __init__(self, id):
        self.id = id
        self.view = 0
        self.sequence_number = 0
        self.log = {}  # sequence_number -> (request, pre-prepare, prepares, commits)
        self.last_committed = 0
        self.state = {}  # application state (e.g., key-value store)
        # For view change:
        self.view_change_messages = []
        self.new_view_sent = False

7.2 Client Request

A client c sends a signed request (operation, timestamp, c) to the primary. The primary is defined as primary = self.view % N.

def client_send_request(request):
    # sign request
    signed_req = sign(request, client_private_key)
    primary = current_view % N
    send_to(primary, signed_req)

7.3 Primary Pre-Prepare

Upon receiving a client request, the primary:

def primary_handle_request(self, request):
    # Validate signature
    if not verify_signature(request, client_public_key):
        return
    # Increment sequence number
    self.sequence_number += 1
    seq = self.sequence_number
    digest = hash(request)
    pre_prepare_msg = {
        'view': self.view,
        'seq': seq,
        'digest': digest,
        'request': request,
        'signature': sign(self.id, (self.view, seq, digest))
    }
    # Multicast to all replicas (including self)
    for replica_id in range(N):
        send_to(replica_id, pre_prepare_msg)

7.4 Replica Handles Pre-Prepare

A replica i receives a pre-prepare. It must verify:

• The pre-prepare is from the correct primary for the current view.
• The view number matches current view.
• The sequence number is valid (monotonic).
• The request’s digest matches.
• The signature is valid.

If valid, the replica enters the pre-prepared state and multicasts a prepare message.

def handle_pre_prepare(self, msg):
    if msg.view != self.view:
        return  # ignore stale messages
    if msg.sender != primary_of_view(msg.view):
        return
    # Verify signature
    if not verify(msg.signature, msg.sender's public key):
        return
    # Accept pre-prepare: log it
    if msg.seq not in self.log:
        self.log[msg.seq] = {}
    self.log[msg.seq]['pre_prepare'] = msg
    # Send prepare to all
    prepare_msg = {
        'view': self.view,
        'seq': msg.seq,
        'digest': msg.digest,
        'sender': self.id,
        'signature': sign(self.id, (self.view, msg.seq, msg.digest))
    }
    multicast(prepare_msg)

7.5 Prepare Phase

Prepare messages are collected. When a replica has a pre-prepare and 2f matching prepares (including its own? Not including itself? The original PBFT counts the pre-prepare as one vote, so need 2f additional prepares. Let’s keep it simple: total 2f+1 matching messages including pre-prepare). So we need 2f prepares matching the pre-prepare.

def handle_prepare(self, msg):
    if msg.view != self.view:
        return
    # Verify signature
    entry = self.log.get(msg.seq)
    if entry is None:
        return
    if 'prepare_msgs' not in entry:
        entry['prepare_msgs'] = []
    entry['prepare_msgs'].append(msg)
    # Check if reached threshold
    if len(entry['prepare_msgs']) >= 2*f:
        # prepared state: send commit
        commit_msg = {
            'view': self.view,
            'seq': msg.seq,
            'digest': msg.digest,
            'sender': self.id,
            'signature': sign(self.id, (self.view, msg.seq, msg.digest))
        }
        multicast(commit_msg)

Note: The prepare threshold should include the pre-prepare itself. So count pre-prepare + prepares. We’ll adjust: if 1 + len(entry['prepare_msgs']) >= 2*f+1.

7.6 Commit Phase

Commit messages are collected. When a replica receives 2f+1 commit messages (including its own) for the same view and sequence number, it commits the request.

def handle_commit(self, msg):
    if msg.view != self.view:
        return
    entry = self.log.get(msg.seq)
    if entry is None:
        return
    if 'commit_msgs' not in entry:
        entry['commit_msgs'] = []
    entry['commit_msgs'].append(msg)
    # Check threshold: 2f+1 total commit messages
    if len(entry['commit_msgs']) >= 2*f+1:
        # Commit the request
        self.last_committed = msg.seq
        request = self.log[msg.seq]['pre_prepare'].request
        # Execute request (deterministic)
        result = execute(request)
        # Send reply to client (maybe f+1 replicas to ensure client sees)
        # For simplicity, we send directly to client
        send_to(client, (msg.seq, result, self.id))

7.7 View Change

When a replica detects that the primary is faulty (e.g., timer expires after sending a request and not seeing pre-prepare), it initiates a view change.

Simplified view change:

1. Replica i increments view to view+1.
2. It sends a view-change message to the new primary, containing:
   • New view number
   • Last committed sequence number
   • A set of prepared proofs: for each sequence number where it has a prepared state (pre-prepare + 2f prepares), include the pre-prepare and the prepares
3. The new primary (for view v+1) collects 2f+1 view-change messages.
4. It constructs a new-view message containing:
   • New view number
   • A sequence of proposals (pre-prepares) to reissue in the new view. This includes:
     • All requests that were prepared in view v and earlier (taken from the view-change collected proofs).
     • Optionally, a special “null” request to fill gaps.
5. New primary multicasts new-view to all.
6. Each replica, upon receiving new-view, verifies it and then begins normal operation in the new view, re-issuing pre-prepares for the included requests.

This is simplified; the full protocol handles complex cases like missing sequence numbers and ensures that no committed request is lost.

7.8 Garbage Collection

Replicas periodically take a checkpoint (state hash). They multicast checkpoint messages. When a replica receives 2f+1 matching checkpoints for sequence number c, it can discard all log entries up to c.

def checkpoint(self):
    checkpoint_seq = self.last_committed
    state_hash = hash(self.state)
    ckpt_msg = {
        'seq': checkpoint_seq,
        'hash': state_hash,
        'sender': self.id,
        'signature': sign(self.id, (checkpoint_seq, state_hash))
    }
    multicast(ckpt_msg)

def handle_checkpoint(self, msg):
    # Collect
    # When 2f+1 matching for same seq and hash
    # then stable checkpoint: trim log

8. Real-World Use Cases

PBFT and its variants are deployed in several critical systems:

-Hyperledger Fabric: Uses a modified PBFT called SBFT (Simplified Byzantine Fault Tolerance) in its early versions, later replaced by Raft for crash faults, but PBFT remains for some ordering services. -Zilliqa: A high-throughput blockchain that uses PBFT for its consensus within shards. -Quorum: The Ethereum-based enterprise blockchain uses Istanbul BFT (IBFT) , a close cousin of PBFT. -Cosmos SDK: Uses Tendermint Core, which is a PBFT derivative. -Byzantine Fault Tolerant key-value stores: Some financial and defense systems use PBFT for replicated databases.

PBFT is not common in permissionless blockchains (like Bitcoin or Ethereum) due to its O(n²) scaling, but it is the gold standard for permissioned settings where the number of nodes is modest (typically 10-100) and trust is low.

9. Challenges and Pitfalls

Implementing PBFT is not trivial. Here are common pitfalls:

• Faulty primary equivocation: A primary can send different pre-prepare to different replicas. The protocol guards against this via prepare phase – honest replicas will not collect enough prepares for a conflicting message because the quorum intersection ensures they will see the conflict.
• Timing assumptions: View change timers must be carefully tuned. If too short, unnecessary view changes waste resources; if too long, liveness suffers.
• Message ordering: Since PBFT uses sequence numbers, a faulty primary could skip sequence numbers to cause gaps. The view change protocol handles this by re-proposing missing requests.
• State synchronization: After a view change, the new primary may need to synchronize its state with replicas that are behind. This requires a state transfer protocol (not covered here).
• Cryptographic overhead: Signing every message is expensive. PBFT original used MACs with pairwise keys to reduce cost. Modern implementations use BLS signatures (aggregatable) to reduce overhead.
• Non-determinism: The application logic must be deterministic; otherwise, replicas can diverge. This is especially important for smart contract execution.

10. Future of BFT

PBFT opened the door, but the field has advanced:

• HotStuff (2020) achieves linear communication with a fixed leader and uses a chained BFT approach. It is being adopted in projects like Diem and Aptos.
• HoneyBadgerBFT (2016) provides asynchronous BFT without a leader, using random coin flips. It is robust against adaptive adversaries but has high latency.
• Dumbo (2020) extends PBFT to reduce communication using erasure codes.
• Algorand uses a cryptographic sortition to select a committee, achieving scalability.

PBFT remains the best educational starting point. Its structure—phases, quorums, view changes—is the DNA of almost all modern BFT algorithms.

11. Conclusion

We began with an impossible-looking problem: generals trying to coordinate in the face of traitors. We saw that for decades, the cost of solving this problem was too high for practical use. Then came PBFT, a beautifully engineered algorithm that turned a theoretical curiosity into deployable software. By accepting that nodes can lie, PBFT requires more communication, more phases, and more cryptography than its crash-fault cousins. But the payoff is profound: a replicated system that can survive arbitrary faults, including malicious attacks.

Implementing PBFT is not for the faint of heart. You must handle equivocation, view changes, checkpointing, and careful timer management. But understanding it is essential for anyone building critical infrastructure—from blockchain networks to replicated control systems. The core lesson is simple: trust, but verify. And if you cannot trust, make every node verify everything.

The next time you design a distributed system, ask yourself: What if a node goes rogue? If the answer is “disaster,” then PBFT—or one of its modern descendants—deserves a place in your toolbox. The Byzantine Generals Problem is no longer a thought experiment; it’s a design challenge we can now solve.

This guide covered the fundamentals of PBFT from theory to pseudocode. In future posts, we will explore optimizations like speculative execution (Zyzzyva), view-change optimizations, and practical deployment considerations. Stay tuned.