Byzantine Fault Tolerance (BFT)

A BFT system can tolerate up to f faulty nodes out of a total N nodes, where N = 3f + 1. This is the fundamental resilience bound.

• Example: In a network of 10 nodes (N=10), it can withstand up to 3 malicious or non-responsive nodes (f=3), as 10 ≥ (3*3)+1.
• This formula ensures that the honest majority (2f+1) can always outvote the faulty minority to reach correct consensus.
• Exceeding this threshold breaks the system's safety guarantees, potentially leading to forking or double-spending.

BFT protocols provide two critical, non-negotiable guarantees:

• Safety: Also known as consistency. All honest nodes agree on the same sequence of committed transactions. It is impossible for two honest nodes to finalize conflicting states. This prevents double-spending.
• Liveness: Also known as termination. The network continues to process new transactions and make progress. Honest clients will eventually have their valid transactions included in the ledger, provided the fault threshold is not exceeded. These properties hold under partial synchrony, where messages are eventually delivered within a bounded but unknown delay.

Most practical BFT algorithms (e.g., PBFT, Tendermint) use a rotating leader (or proposer) model to drive consensus efficiently.

• A designated leader proposes a block of transactions for a specific view or round.
• Other nodes act as validators, voting on the proposal in multi-phase broadcasts (pre-prepare, prepare, commit).
• If the leader is faulty or slow, a view-change protocol is triggered to elect a new leader, ensuring liveness.
• This structure reduces message complexity from O(N²) to O(N) per round compared to leaderless designs.

BFT consensus is the engine for Byzantine Fault Tolerant State Machine Replication.

• Each node starts with the same initial state and runs the same deterministic application logic (the state machine).
• The consensus protocol is responsible only for agreeing on an ordered log of inputs (transactions).
• Because all honest nodes apply the same inputs in the same order, their internal states remain synchronized despite faulty nodes. This is how blockchains like Cosmos (Tendermint) and DiemBFT maintain a consistent global ledger.

Classic BFT algorithms like Practical BFT (PBFT) have O(N²) message complexity per consensus decision, where N is the number of nodes.

• In the three-phase commit, each node must broadcast messages to all other nodes, leading to N * (N-1) messages.
• This becomes a scalability bottleneck, limiting traditional BFT networks to tens or low hundreds of nodes.
• Modern variants like HotStuff and SBFT reduce this to O(N) linear complexity using threshold signatures or aggregation, enabling larger validator sets.

BFT consensus provides immediate, deterministic finality, unlike Nakamoto Consensus (Proof-of-Work) which offers probabilistic finality.

• Once a block is committed by a supermajority (2f+1) of honest nodes, it is irreversible. There is no possibility of reorganization unless the fault threshold is exceeded.
• This is critical for high-value financial settlements and bridges between chains, where transaction rollbacks are unacceptable.
• Finality is typically achieved after two rounds of voting (prepare and commit phases) following a valid proposal.

Crash Fault Tolerance is the property of a distributed system to remain operational and consistent when some of its components fail by stopping (crashing) and ceasing to respond. This is a strict subset of the Byzantine failure model. CFT protocols, like Paxos or Raft, are simpler and more performant because they do not need to defend against malicious, arbitrary behavior from participating nodes. They assume failures are benign.

• Key Assumption: Failed nodes are silent, not deceptive.
• Use Case: The internal coordination of trusted data centers where hardware faults are the primary concern.

The FLP impossibility result (Fischer, Lynch, Paterson) is a fundamental theorem in distributed computing proving that in an asynchronous network (where messages have no guaranteed timing bound), it is impossible for a deterministic consensus protocol to guarantee both safety (no two correct nodes decide different values) and liveness (eventually deciding a value) in the presence of even a single crash failure. This result shapes all practical BFT protocols, which circumvent it by making partial synchrony assumptions (e.g., known timeouts) or using randomness.

State Machine Replication is a fundamental technique for implementing fault-tolerant services where multiple replicas (servers) start from the same initial state and apply an identical, ordered sequence of client requests (commands) to their local state machines. BFT consensus protocols are the engine that ensures this consistent ordering across replicas, even with Byzantine faults. The system provides a single, highly available logical service to clients, masking the complexity and potential failures of the underlying replicas.

A Sybil attack is a scenario where a single adversary creates and controls a large number of fake identities (Sybil nodes) in a peer-to-peer network to subvert its reputation system or consensus mechanism. BFT consensus in permissionless settings must be combined with a Sybil resistance mechanism (like Proof-of-Work or Proof-of-Stake) to make creating a significant fraction of identities prohibitively expensive. The classic BFT model assumes a fixed, known set of nodes (n), so tolerating f Byzantine faults where f < n/3 implicitly assumes the adversary cannot arbitrarily inflate n.