Byzantine Fault Tolerance

The foundational thought experiment where generals must coordinate an attack via messengers, but some may be traitors sending false information. In distributed systems, this translates to nodes that may crash, malfunction, or be compromised by an adversary. BFT systems must tolerate these arbitrary faults, not just simple crash failures. The core challenge is achieving consensus when malicious actors actively try to prevent it.

BFT protocols provide two critical properties:

• Safety: All honest nodes agree on the same value. The system never commits conflicting transactions.
• Liveness: The system continues to make progress and eventually commits new transactions, even under attack. A classic BFT system tolerates up to f malicious nodes out of a total of 3f + 1 nodes. Exceeding this threshold breaks the protocol's guarantees.

In federated learning, BFT aggregation rules like Krum or Trimmed Mean protect the global model from malicious clients. Instead of simple averaging, these rules statistically filter out outlier model updates that deviate significantly from the norm. This prevents a single attacker from poisoning the joint model by submitting a crafted update designed to corrupt the shared weights or embed a backdoor.

Modern implementations move beyond theoretical models to achieve high throughput and low latency:

• PBFT (Practical Byzantine Fault Tolerance): Uses a leader-based, three-phase commit protocol with view changes to replace faulty leaders.
• Tendermint: A BFT consensus engine used in Cosmos, pairing a rotating proposer with a weighted voting mechanism.
• HotStuff: A linear communication complexity protocol enabling leader rotation without expensive view-change procedures, used in Facebook's Diem blockchain.

Crash Fault Tolerance (CFT) assumes nodes only fail by stopping. Systems like Raft and Paxos are CFT-only. BFT is a stronger guarantee that handles arbitrary behavior, including nodes that lie, send contradictory messages, or collude. While CFT is simpler and faster, BFT is essential for adversarial environments like permissionless blockchains, federated learning with untrusted clients, and secure multi-party computation.

BFT protocols assume a fixed set of known validators with equal voting power. To prevent a single adversary from creating thousands of fake nodes (a Sybil attack), BFT systems require a form of identity or stake. In permissioned networks, this is a static validator list. In permissionless systems like Proof-of-Stake blockchains, economic stake binds identity to voting power, making it costly for an attacker to control one-third of the total stake.

An integrity attack where a malicious participant manipulates local model updates to corrupt the global model. Unlike random failures, the adversary crafts updates to maximize divergence while evading detection. In Byzantine Fault Tolerance contexts, the attacker may send conflicting information to different honest nodes to skew consensus. Defenses include norm clipping and robust aggregation rules.

A cryptographic protocol enabling multiple parties to jointly compute a function over private inputs while keeping those inputs mutually secret. In contrast to BFT, which tolerates arbitrary faults, SMPC assumes a threshold of semi-honest or malicious adversaries and uses secret sharing to prevent data exposure. It provides privacy but does not inherently guarantee liveness under Byzantine conditions.

An attack reconstructing private training data from publicly shared model gradients. While BFT ensures system liveness against malicious nodes, it does not guarantee confidentiality. An honest-but-curious server can perform gradient inversion to recover sensitive inputs. This necessitates combining Byzantine resilience with differential privacy or secure aggregation for comprehensive protection.

A critical challenge in federated learning where local datasets have heterogeneous statistical distributions. Byzantine Fault Tolerance mechanisms often assume honest gradients are similar, but non-IID data creates natural variance that mimics adversarial behavior. This leads to high false-positive rates where robust aggregators incorrectly exclude honest but statistically divergent clients.