Byzantine Fault Tolerance (BFT)

The Safety property guarantees that all non-faulty (honest) nodes in the system agree on the same value or state transition. No two correct nodes will decide on conflicting outputs. This is the fundamental guarantee of consensus, ensuring the system's state remains consistent and deterministic even in the presence of Byzantine (arbitrarily faulty) nodes. In a blockchain context, this prevents double-spending and ensures a single, canonical history.

• Core Guarantee: All honest nodes agree on the same sequence of commands.
• Violation Example: Two honest nodes finalizing different blocks at the same height.

The Liveness property guarantees that the system will eventually produce an output and make progress. Honest nodes will not stall indefinitely waiting for a decision. This ensures the system remains usable and responsive. In practice, liveness assumes a partially synchronous network model—periods of asynchrony are bounded—and that the number of faulty nodes does not exceed the protocol's resilience threshold (typically f < n/3 for optimal BFT).

• Core Guarantee: The protocol eventually completes and delivers results to clients.
• Dependency: Requires sufficient network connectivity and honest participation.

This defines the maximum number of Byzantine nodes a BFT consensus protocol can withstand while maintaining both Safety and Liveness. The classic result, known as the PBFT resilience bound, is that a system of n nodes can tolerate f faulty nodes where n ≥ 3f + 1. This means up to one-third of the participating nodes can be malicious or arbitrarily faulty. This threshold is optimal for deterministic, synchronous protocols. Some protocols (e.g., Tendermint, HotStuff) operate at this bound.

• Formula: n = 3f + 1 (e.g., 4 nodes tolerate 1 fault).
• Implication: Requires a supermajority (2f + 1) of honest nodes for correctness.

A key property distinguishing BFT protocols is their resilience to asynchronous network conditions, where message delays are unbounded. The FLP Impossibility result proves that in a fully asynchronous network, no deterministic consensus protocol can guarantee both safety and liveness with even one crash failure. Practical BFT protocols circumvent this by assuming partial synchrony—there exists an unknown global stabilization time (GST) after which messages are delivered within a known delay. Protocols like Paxos, Raft, and PBFT are designed for this model.

• Challenge: Distinguishing a slow node from a malicious one.
• Solution: Use of timeouts and view-change protocols after GST.

BFT protocols rely heavily on cryptographic primitives to authenticate messages and provide non-repudiation. Digital signatures (e.g., ECDSA, EdDSA) allow any node to verify that a message originated from a specific sender and was not altered. Threshold signatures can be used to create compact, verifiable proofs that a supermajority of nodes agree on a value. Verifiable Broadcast (or Reliable Broadcast) is a sub-protocol that guarantees if an honest node delivers a message, all honest nodes will eventually deliver that same message, even if the sender is Byzantine.

• Purpose: Prevents spoofing and enables accountability.
• Example: A Prepare message in PBFT is signed by a replica.

To maintain liveness, BFT protocols include a view-change mechanism. If the designated leader (or primary) for a consensus round is suspected to be faulty or slow, honest nodes can collaboratively elect a new leader and resume progress. This process must itself be Byzantine fault-tolerant to prevent malicious nodes from forcibly triggering unnecessary view changes (a denial-of-service attack). The protocol must also ensure state recovery, allowing a newly elected leader to synchronize with the latest, agreed-upon system state before proposing new commands.

• Function: Recovers liveness when the primary fails.
• Complexity: Must preserve safety throughout the leadership transition.

A fundamental technique for implementing a fault-tolerant service by replicating a deterministic state machine across multiple nodes. All replicas start in the same state and execute the same sequence of client commands in the same order. Consensus algorithms like Paxos and Raft are used to agree on this total order. BFT protocols extend SMR to handle Byzantine (arbitrary) faults in the replicas.

• Core Principle: If replicas start identically and process the same inputs in the same order, they will produce identical outputs and states.
• Application: The basis for building highly available key-value stores, lock managers, and configuration services.

A mathematical framework for ensuring consistency in distributed read/write operations by requiring a minimum number of nodes (a quorum) to participate. In a system of N nodes, a write quorum W and a read quorum R are chosen such that W + R > N. This guarantees that any read operation intersects with the nodes that performed the most recent write. Quorums are a building block for many replication and consensus protocols, including those tolerating Byzantine faults.

• Trade-off: Configurable for read-heavy (R=1, W=N) or write-heavy (W=1, R=N) workloads.
• Byzantine Quorums: Require larger intersections (e.g., 3f + 1 nodes) to overcome malicious responses.