Byzantine Fault Tolerance

The guarantee that all non-faulty nodes agree on the same value. In a BFT system, safety ensures that no two correct nodes decide on conflicting outputs, even when Byzantine nodes attempt to send contradictory messages. This is the consistency property—once a value is committed, the system will not fork or diverge. Protocols like PBFT achieve safety through a three-phase commit process (pre-prepare, prepare, commit) requiring 2f+1 matching messages from a quorum of 3f+1 total nodes, where f is the maximum number of faulty nodes tolerated.

The guarantee that the system eventually makes progress and produces an output. Liveness prevents deadlock scenarios where the protocol stalls indefinitely. In asynchronous networks, BFT protocols rely on view changes and timeout mechanisms to replace unresponsive leaders. Practical Byzantine Fault Tolerance (PBFT) triggers a view change when the primary fails to propose within a timeout window, electing a new leader deterministically. This ensures the system continues processing requests even when the current leader is Byzantine or has crashed.

The theoretical upper bound on the fraction of faulty nodes a BFT system can tolerate. For partially synchronous networks, the optimal resilience is f < n/3—meaning fewer than one-third of nodes can be Byzantine. This bound was proven by Lamport, Shostak, and Pease in 1982. With digital signatures and authenticated channels, some protocols achieve f < n/2 in synchronous settings. The 3f+1 requirement arises because a quorum of 2f+1 honest nodes must intersect with any other quorum by at least f+1 honest nodes, preventing conflicting decisions.

BFT protocols require cryptographic authentication of all inter-node messages to prevent spoofing and message tampering. Each message is signed with the sender's digital signature, allowing recipients to verify origin and integrity. Modern BFT systems use threshold signatures and aggregate signatures to reduce communication overhead—combining multiple signatures into a single compact proof. Without authentication, a Byzantine node could impersonate honest nodes and violate safety. Authenticated channels transform the adversary's capability from arbitrary message injection to only equivocation and omission.

Unlike probabilistic consensus in Nakamoto-style protocols, BFT systems provide absolute finality—once a transaction or state update is committed, it cannot be reversed or reorganized. This is achieved through quorum intersection: any two quorums of size 2f+1 share at least f+1 honest nodes, ensuring that conflicting decisions cannot both receive sufficient votes. Deterministic finality is critical for financial applications where settlement finality must be guaranteed within bounded time, not merely probabilistically after multiple confirmations.

The mechanism by which a BFT system replaces a faulty or unresponsive leader to maintain liveness. When nodes detect the primary is not making progress—via timeout expiration—they broadcast view-change messages containing their latest stable checkpoint and prepared requests. The new primary collects 2f+1 view-change messages to establish the system's state before resuming operation. This ensures that any request prepared in a previous view is carried forward, preserving safety across leadership transitions. View changes are the most complex component of BFT protocol implementations.

Distributed systems classify node failures along a spectrum of severity. Crash faults assume nodes simply stop responding—they never send incorrect data. Byzantine faults allow arbitrary, adversarial behavior including sending contradictory messages to different peers, deliberate protocol violations, and coordinated attacks.

• Crash fault tolerance requires only 2f + 1 replicas; BFT requires 3f + 1
• Fail-silent and fail-stop are intermediate models where faulty nodes halt detectably
• Byzantine model captures software bugs, compromised nodes, and malicious insiders
• Most cloud infrastructure assumes crash faults; blockchain systems must assume Byzantine

BFT protocol guarantees depend critically on network timing assumptions. Synchronous networks bound message delivery within a known maximum delay Δ. Asynchronous networks make no timing guarantees—messages can be delayed arbitrarily. Partially synchronous models assume the system eventually becomes synchronous after an unknown Global Stabilization Time (GST).

• FLP impossibility proves deterministic consensus is impossible in pure asynchrony with even one crash fault
• PBFT uses weak synchrony: safety holds always, liveness requires eventual synchrony
• Randomized BFT protocols like HoneyBadgerBFT achieve liveness in asynchrony using cryptographic sortition