Byzantine Fault Tolerance

The guarantee that all non-faulty nodes agree on the same value. If one correct node commits a transaction, no other correct node will commit a different, conflicting transaction. This property prevents forks and ensures the system maintains a single, consistent history. In blockchain systems, safety prevents double-spending. In federated learning, it ensures all honest clients converge to the same model update despite malicious contributions.

The guarantee that the system eventually makes progress and produces an output. A BFT protocol must not stall indefinitely due to malicious nodes refusing to send messages or sending conflicting information. Liveness ensures that transactions are eventually committed and the system remains available. Protocols like PBFT achieve liveness through view changes that replace an unresponsive leader.

A BFT system can tolerate up to f Byzantine nodes out of a total of n = 3f + 1 nodes. This means fewer than one-third of participants can be malicious without compromising safety or liveness. This bound is provably optimal for deterministic protocols in asynchronous networks. For example, a 7-node BFT network tolerates up to 2 Byzantine replicas.

The guarantee that the agreed-upon value was actually proposed by a correct node. A malicious leader cannot force the system to commit an arbitrary or fabricated value. In the context of robust aggregation for federated learning, validity ensures the final model update is a meaningful combination of honest client contributions, not a value injected entirely by an attacker.

BFT protocols operate under different network timing assumptions:

• Synchronous: Messages arrive within a known bounded delay. Enables higher throughput but is fragile in real-world networks.
• Asynchronous: No timing bounds exist. Protocols like HoneyBadgerBFT work here but are more complex.
• Partially Synchronous: Assumes the network is eventually synchronous after an unknown Global Stabilization Time. Used by PBFT and most practical systems.

Once a transaction is committed by a correct node, it is irreversibly final and cannot be rolled back. This differs from probabilistic finality in Nakamoto consensus, where a transaction's confidence grows over time but can theoretically be reversed. BFT finality provides deterministic settlement, making it suitable for financial applications where immediate certainty is required.

A defense mechanism that identifies malicious clients in federated learning by analyzing the diversity of their historical gradient updates, assuming Sybil attackers produce highly similar contributions. The core insight is that honest clients, training on distinct local data distributions, naturally produce diverse gradient updates, while coordinated adversaries tend to submit nearly identical gradients to amplify their influence. FoolsGold assigns a per-client trust score based on the cosine similarity of their update history, down-weighting clients that exhibit excessive uniformity. This approach is particularly effective against label-flipping Sybil attacks where a single adversary controls multiple identities to poison the global model.

A technique that caps the L2-norm of individual per-example gradients during training to bound the maximum influence any single data point can exert on the model update. In the context of Byzantine resilience, gradient clipping serves as a first line of defense by preventing malicious clients from submitting arbitrarily large gradient vectors that could dominate the aggregation step. When combined with differential privacy via DP-SGD, clipping thresholds are calibrated to the desired privacy budget, simultaneously providing privacy guarantees and robustness against poisoning. Typical clipping values are determined empirically by monitoring the gradient norm distribution of clean training data.

A property of a model that provides a mathematical proof guaranteeing its prediction will remain constant for any input within a specified Lp-norm radius, defending against adversarial perturbations. Unlike empirical defenses that can be broken by stronger attacks, certified robustness offers formal worst-case guarantees. Key techniques include:

• Randomized Smoothing: Adding Gaussian noise to inputs and returning the most probable prediction under that noise distribution
• Interval Bound Propagation: Propagating verified bounds through each network layer
• Satisfiability Modulo Theories (SMT): Encoding the network as logical constraints and proving no adversarial example exists within the epsilon-ball