Byzantine Fault Tolerance (BFT)

BFT protocols operate under the Byzantine Generals' Problem, where faulty clients can behave arbitrarily, not just crash. This includes:

• Data Poisoning: Manipulating local training data.
• Model Poisoning: Sending crafted, malicious model updates.
• Collusion: Multiple adversarial clients coordinating attacks. The system is designed to tolerate up to f malicious clients out of N total, where N > 3f is a common requirement for consensus-based BFT.

The core of BFT is the server's aggregation algorithm, which must filter out malicious updates. Key methods include:

• Coordinate-wise Median/Trimmed Mean: For each model parameter, discards extreme values before averaging.
• Krum & Multi-Krum: Selects the update vector closest to its neighbors in Euclidean space.
• Bulyan: A meta-aggregation that applies a robust rule (e.g., Krum) to select candidates, then performs trimmed mean on them. These rules provide statistical robustness, ensuring the aggregated update is close to the true mean of honest clients.

A critical BFT characteristic is robustness under non-IID (Independent and Identically Distributed) data across clients. Malicious updates are distinguished by their geometric direction or magnitude, not their statistical origin. Defenses like gradient norm bounding (clipping) and anomaly detection in high-dimensional space ensure tolerance to natural heterogeneity while filtering adversarial signals.

BFT introduces a fundamental trade-off. Aggressively filtering updates to exclude all malicious clients may also discard updates from honest clients with unusual but legitimate data. This can:

• Slow convergence by reducing the useful signal per round.
• Bias the model towards the population centroid, potentially harming performance on edge-case distributions. The breakdown point of an aggregation rule defines the maximum fraction of malicious clients it can tolerate before accuracy degrades catastrophically.

BFT often operates alongside privacy-preserving techniques, creating a defense-in-depth architecture. Key interactions include:

• Secure Aggregation: Cryptographically hides individual updates but does not prevent poisoning; BFT is needed on the encrypted aggregate.
• Differential Privacy: Adding noise for privacy can mask malicious updates, requiring BFT algorithms robust to higher variance.
• Trusted Execution Environments (TEEs): Hardware enclaves can guarantee update integrity, simplifying the BFT problem to crash-fault tolerance.

BFT guarantees incur measurable system costs:

• Server Compute: Robust aggregation (e.g., calculating pairwise distances for Krum) is O(N²) in the number of clients per round.
• Client Compute: May require reputation-based protocols where clients perform additional validation.
• Communication: Some BFT consensus protocols require multiple rounds of client-server or client-client communication per learning round. This overhead must be justified by the threat model and value of the trained model.

This is the core algorithmic class that implements BFT. Instead of a simple average, these rules are designed to produce a correct global update even when a fraction of clients are malicious. Key examples include:

• Krum & Multi-Krum: Selects the update closest to its neighbors.
• Trimmed Mean: Discards the highest and lowest values per parameter.
• Median Aggregation: Uses the coordinate-wise median, highly resistant to extreme outliers. These methods statistically filter out adversarial updates before they corrupt the global model.

These cryptographic protocols ensure privacy-preserving aggregation, a complementary goal to BFT. While BFT ensures correctness despite malice, secure aggregation ensures confidentiality. They allow the server to compute the sum of client updates without learning any individual update's value. This is achieved through techniques like:

• Masking with Secret Sharing: Clients add cryptographic masks that cancel out in aggregate.
• Homomorphic Encryption: Enables computation on encrypted data. This prevents the server from performing privacy-invading inspection of individual contributions, a common limitation of pure BFT defenses.

This is the structured process that defines what "faults" BFT must tolerate. It involves identifying, quantifying, and prioritizing risks to the federated system. Key threat models relevant to BFT include:

• Data Poisoning: Malicious clients corrupt their local training data.
• Model Update Poisoning: Clients send arbitrary or designed-to-fail gradients.
• Sybil Attacks: A single entity controls many fake clients.
• Eclipse Attacks: Isolating honest clients from the consensus. Effective BFT design starts with a precise threat model specifying the assumed percentage and capabilities of Byzantine participants.

A dynamic, data-driven enhancement to static BFT algorithms. Instead of treating all clients equally or using a fixed threshold, the server assigns a continuous credibility score to each client based on their historical behavior. Scoring factors include:

• Update Consistency: How similar are a client's updates to a robust consensus?
• Contribution Quality: Does the client's update improve validation set performance?
• Statistical Normality: Does the update vector conform to expected distributions? Updates are then aggregated with weights proportional to their trust score, making the system adaptive and potentially more efficient than one-size-fits-all BFT rules.

While BFT defends against actively malicious clients, this mechanism identifies passively malicious or useless clients. A free-rider benefits from the global model without contributing meaningful updates, wasting system resources and potentially slowing convergence. Detection methods overlap with BFT techniques:

• Gradient Inspection: Identifying updates with near-zero magnitude or random noise.
• Contribution Assessment: Measuring the update's impact on a validation loss.
• Data Quality Inference: Estimating if the client has any relevant training data. Mitigation involves excluding or penalizing such clients, preserving system integrity and efficiency.

A hardware-rooted trust mechanism that can proactively prevent Byzantine behavior. It uses Trusted Execution Environments (TEEs) like Intel SGX or ARM TrustZone. Before accepting an update, the server cryptographically verifies (attests) that the client's code is running unmodified inside a secure enclave. This ensures:

• Code Integrity: The training algorithm has not been tampered with.
• Data Secrecy: Training data within the enclave is protected.
• Result Authenticity: The output update is genuine. This moves the defense from detecting malicious outputs (BFT) to guaranteeing the integrity of the computation process itself.