Practical Byzantine Fault Tolerance and Proactive Recovery
📜 Abstract
Our growing reliance on online services accessible on the Internet demands highly available systems that provide correct service without interruptions. Software bugs, operator mistakes, and malicious attacks are a major cause of service interruptions and they can cause arbitrary behavior, that is, Byzantine faults. This article describes a new replication algorithm, BFT, that can be used to build highly available systems that tolerate Byzantine faults. BFT can be used in practice to implement real services: it performs well, it is safe in asynchronous environments such as the Internet, it incorporates mechanisms to defend against Byzantine-faulty clients, and it recovers replicas proactively. The recovery mechanism allows the algorithm to tolerate any number of faults over the lifetime of the system provided fewer than 1/3 of the replicas become faulty within a small window of vulnerability. BFT has been implemented as a generic program library with a simple interface. We used the library to implement the first Byzantine-fault-tolerant NFS file system, BFS. The BFT library and BFS perform well because the library incorporates several important optimizations, the most important of which is the use of symmetric cryptography to authenticate messages. The performance results show that BFS performs 2% faster to 24% slower than production implementations of the NFS protocol that are not replicated. This supports our claim that the BFT library can be used to build practical systems that tolerate Byzantine faults.
✨ Summary
Contribution
The paper presents BFT, a practical state-machine-replication algorithm that tolerates Byzantine failures when fewer than one-third of the replicas are faulty. Its safety property is linearizability, and safety does not depend on synchrony; liveness requires that message delays eventually become bounded. The protocol uses a primary-backup organization, quorum certificates, and the three phases pre-prepare, prepare, and commit. View changes replace an unresponsive or faulty primary while preserving the ordering of committed requests. Clients accept a result after receiving matching replies from at least (f+1) replicas.
The paper also introduces proactive recovery. Replicas periodically recover even when no fault is suspected, refresh authentication keys, verify or repair their state, and rejoin normal operation. This changes the fault model from tolerating fewer than one-third of all replicas over the system lifetime to tolerating an unbounded total number of faults, provided fewer than one-third become faulty within a bounded window of vulnerability. Efficient checkpointing, state transfer, batching, digest replies, tentative execution, and symmetric-key message authentication are used to make the design practical. The authors implemented the BFT library and used it to build BFS, a Byzantine-fault-tolerant NFS service. In the reported experiments, BFS ranged from 2% faster to 24% slower than nonreplicated production NFS implementations. (microsoft.com)
Influence
The work became a foundational reference for practical Byzantine fault-tolerant state-machine replication. Later research continued to formalize and refine the protocol; for example, Lamport’s Byzantizing Paxos by Refinement explicitly studies the Castro–Liskov algorithm as a refinement of ordinary Paxos and provides formal specifications and a mechanically checked proof. (microsoft.com) Subsequent systems such as SBFT use PBFT as a performance baseline while addressing scalability, communication complexity, and geo-replication; SBFT reports evaluations with more than 200 active replicas and compares its performance with an optimized PBFT implementation. (arxiv.org)
The protocol family also influenced permissioned blockchain infrastructure. Hyperledger Fabric’s documentation states that its SmartBFT-based ordering service is heavily inspired by BFT-SMaRt, which is described as a non-pipelined version of the seminal PBFT protocol. Fabric provides a production-oriented BFT ordering mode that tolerates fewer than one-third malicious or unreachable ordering nodes, demonstrating the continued use of the paper’s core model in industry software. (hyperledger-fabric.readthedocs.io)