The Byzantine Threat Model

From Honest-but-Curious to Malicious

Chapter 10's secure aggregation defended against an honest-but-curious server: one that follows the protocol but tries to extract information. This chapter confronts the harder problem: what if some users are malicious? They can deliberately upload corrupted gradients to bias the aggregate, poison the model, or otherwise sabotage the training run.

This is the Byzantine adversary model, named for the Byzantine Generals problem of distributed consensus. In federated learning, Byzantine users are a real threat: compromised devices, malicious actors seeking to bias a model, or simply faulty hardware can all produce arbitrarily bad gradient uploads. Bonawitz's protocol provides zero defense — the server cannot detect or filter Byzantine contributions because individual gradients are masked.

The point is that handling Byzantine adversaries requires new machinery. The CommIT-group ByzSecAgg protocol (Jahani-Nezhad, Maddah-Ali, and Caire 2023) is the headline result of this chapter: it combines Chapter 3's ramp secret sharing, Chapter 5's polynomial coding, and a vector-commitment primitive to achieve Byzantine resilience at $O(n \log n + Bd)$ communication. The construction is one of the most intricate in this book; reading Chapter 11 alongside Chapters 3, 5, 6, and 10 is recommended.

Definition:
Byzantine-Resilient Federated Aggregation

A Byzantine-resilient FL aggregation protocol for $n$ users with up to $B$ Byzantine users and privacy threshold $T$ satisfies:

Correctness under Byzantine attack. For any set $\mathcal{B} \subseteq [n]$ of Byzantine users with $|\mathcal{B}| \leq B$ , the server's output $\hat{\mathbf{G}}$ satisfies $\|\hat{\mathbf{G}} - \mathbf{G}^*\| \leq \rho$ , where $\mathbf{G}^* = \sum_{k \notin \mathcal{B}} \mathbf{g}_k$ is the honest aggregate and $\rho$ is a small bounded error. Strict equality $\hat{\mathbf{G}} = \mathbf{G}^*$ is achievable when $B$ is small.
Privacy. Same as Bonawitz: server + $T$ colluding (potentially Byzantine) users learn nothing about $\{\mathbf{g}_k\}$ beyond $\hat{\mathbf{G}}$ .
Byzantine identification (optional). The protocol may identify which users are Byzantine, enabling reputation systems or exclusion from future rounds.

The Byzantine adversary is active: they may deviate arbitrarily from the protocol, send arbitrary messages, refuse to send messages, or collude adaptively. This is much stronger than Chapter 10's honest-but-curious adversary.

Byzantine Adversary

A user (or set of users) that may deviate arbitrarily from the protocol — sending corrupted gradients, refusing to participate, or colluding adaptively. Strictly more powerful than the honest-but-curious adversary (Chapter 10), requiring different cryptographic / coding-theoretic machinery to defend against.

Byzantine Tolerance $B$

The maximum number of Byzantine users a protocol can tolerate while still producing a correct (within bounded error) aggregate. Bonawitz tolerates $B = 0$ (no Byzantine resilience). Krum and Median tolerate $B < n/2$ but lose privacy. ByzSecAgg tolerates $B$ while preserving privacy.

Theorem: Bonawitz Provides No Byzantine Defense

The Bonawitz secure-aggregation protocol (Chapter 10 §10.2) computes $\mathbf{G} = \sum_k \tilde{\mathbf{g}}_k$ where $\tilde{\mathbf{g}}_k$ is user $k$ 's masked upload. If user $k$ is Byzantine and uploads $\tilde{\mathbf{g}}_k = \mathbf{g}_k^{\text{adv}} + \sum_j \pm \mathbf{r}_{kj}$ for an arbitrary $\mathbf{g}_k^{\text{adv}}$ , the server's aggregate becomes $\mathbf{G} = \mathbf{G}^{\text{honest}} + \sum_{k \in \mathcal{B}} \mathbf{g}_k^{\text{adv}}$ — the Byzantine contributions add to the aggregate without any detection or filtering.

Even one Byzantine user with arbitrary $\mathbf{g}^{\text{adv}}$ can shift the aggregate arbitrarily. The Bonawitz protocol provides zero Byzantine resilience.

The privacy mechanism (mask cancellation) works irrespective of the gradient content. Honest masks cancel; the gradient inside is arbitrary. The server cannot distinguish a true gradient from a poisoned one because individual values are hidden.

Operationally: Bonawitz is fine when users are trusted (Apple Siri scenario) but breaks in adversarial deployments (open federated learning, competitive multi-organization settings). ByzSecAgg addresses this gap.

Proof

Direct calculation

$\mathbf{G} = \sum_k \tilde{\mathbf{g}}_k = \sum_{k \in \mathcal{H}} \mathbf{g}_k + \sum_{k \in \mathcal{B}} \mathbf{g}_k^{\text{adv}} + \sum_k \sum_j \pm \mathbf{r}_{kj} = \mathbf{G}^{\text{honest}} + \sum_{k \in \mathcal{B}} \mathbf{g}_k^{\text{adv}}$ . Masks cancel; the Byzantine contributions remain.

No defense

For Byzantine $\mathbf{g}^{\text{adv}}$ chosen adversarially, the bias is unbounded. A single Byzantine user can shift the aggregate by any vector — the protocol provides no defense.

Implication

Real-world Bonawitz deployments must be combined with robust-aggregation methods (Krum, Median, or ByzSecAgg) to handle Byzantine threats. $\blacksquare$

Example: A Single Byzantine User Defeats Bonawitz

In a Bonawitz-protocol round with $n = 100$ users, suppose user 1 is Byzantine and uploads $\tilde{\mathbf{g}}_1 = -100 \cdot \bar{\mathbf{g}}^{\text{honest}} + \sum_j \pm \mathbf{r}_{1j}$ where $\bar{\mathbf{g}}^{\text{honest}}$ is the mean honest gradient. What does the server receive as the aggregate?

Solution

Aggregate

$\mathbf{G} = -100 \cdot \bar{\mathbf{g}}^{\text{honest}} + \sum_{k=2}^{100} \mathbf{g}_k$ . Approximating $\sum_{k=2}^{100} \mathbf{g}_k \approx 99 \cdot \bar{\mathbf{g}}^{\text{honest}}$ , we get $\mathbf{G} \approx 99 \bar{\mathbf{g}}^{\text{honest}} - 100 \bar{\mathbf{g}}^{\text{honest}} = -\bar{\mathbf{g}}^{\text{honest}}$ .

Effect

The aggregate has flipped sign — the server applies $-\eta \cdot (-\bar{\mathbf{g}}^{\text{honest}}) = +\eta \bar{\mathbf{g}}^{\text{honest}}$ , moving the model in the wrong direction. A single attacker has complete control over the gradient update.

Why undetected

The mask structure hides the user's contribution. The server has no way to inspect $\mathbf{g}_1^{\text{adv}}$ before applying the aggregate. Byzantine resilience requires new machinery, the topic of §11.2.

Byzantine-Resilient Aggregation Approaches

Method	Aggregation	Byzantine tolerance $B$	Privacy guarantee
Krum (Blanchard et al. 2017)	Select user closest to others	$B < n/2$	None (server sees all gradients)
Median	Coordinate-wise median	$B < n/2$	None
Trimmed Mean	Mean after removing $\beta$ -fraction extremes	$B < \beta n$	None
Bulyan	Krum + trimmed-mean refinement	$B < n/4$	None
Bonawitz (Ch. 10)	Sum (no Byzantine defense)	$B = 0$	Information-theoretic
ByzSecAgg (this chapter)	Coded outlier-detected sum	$B = O(n)$	Information-theoretic

Existing Byzantine-Resilient Aggregators Are Not Private

The pre-2020 Byzantine-resilient FL literature (Krum, Median, Trimmed Mean, Bulyan) requires the server to see individual gradients to filter Byzantine contributions. This breaks the privacy guarantee of Bonawitz: the server learns each individual $\mathbf{g}_k$ .

The challenge addressed by ByzSecAgg is to combine both properties: Byzantine resilience and information-theoretic privacy. This is non-trivial because:

Filtering requires distinguishing good from bad gradients — naturally requires inspection.
Privacy requires hiding individual gradients — naturally prevents inspection.

The ByzSecAgg breakthrough is to filter Byzantine contributions without learning individual gradients, using coded distance computations. Section 11.3 develops the coded outlier detection; §11.2 puts the full protocol together.

🚨Critical Engineering Note

Real-World Byzantine Attacks on FL

Byzantine attacks on federated learning are not hypothetical. Several real-world examples:

Model poisoning attacks (Bhagoji et al. 2019): attackers craft gradient uploads to install backdoors in the global model — e.g., causing the model to misclassify a specific input class while otherwise functioning normally.
Untargeted attacks (Fang et al. 2020): attackers upload gradients that maximize the training loss, slowing convergence or causing divergence.
Sybil attacks (Fung et al. 2020): a single attacker creates many fake user identities to amplify their influence.

Production FL deployments (Google, Apple, NVIDIA) typically combine Byzantine defenses with secure aggregation. Pre-ByzSecAgg, this required either sacrificing privacy (by using Krum-style aggregators) or accepting bounded Byzantine impact (via trust assumptions or admission control). ByzSecAgg achieves both simultaneously, at a quantified cost.

Practical Constraints

•
Production: Byzantine attacks observed in open FL deployments
•
Mobile FL: Sybil attacks via compromised devices a documented threat
•
Pre-ByzSecAgg: required tradeoff between privacy and Byzantine defense

📋 Ref: Bhagoji et al. 2019; Fang et al. 2020; Fung et al. 2020

Common Mistake: Honest-Majority Assumption Is Not the Same as "No Byzantine"

Mistake:

Deploy Bonawitz secure aggregation under an "honest-majority" trust assumption ( $> n/2$ honest) and assume Byzantine resilience.

Correction:

Honest-majority is a trust assumption on the user population, not a protocol-level defense. Bonawitz does not actively defend against Byzantine users — it simply trusts that they don't exist. If even a small minority becomes Byzantine, the aggregate is corrupted. ByzSecAgg actively defends against up to $B$ Byzantine users (with $B = O(n)$ ), not by trust but by protocol design.

Historical Note: From Krum to ByzSecAgg

2017–2023

Byzantine resilience in federated learning began with Krum (Blanchard, El Mhamdi, Guerraoui, Stainer 2017), which proposed selecting the gradient most consistent with the rest as the round's aggregate. Median (Yin et al. 2018), Trimmed Mean (Yin et al. 2018), and Bulyan (El Mhamdi et al. 2018) followed, progressively improving Byzantine tolerance and convergence guarantees.

All these schemes assumed plaintext gradient uploads — the server inspects gradients to filter Byzantines. Combining Byzantine defense with secure aggregation was a long-standing open problem in the field.

ByzSecAgg (Jahani-Nezhad, Maddah-Ali, and Caire 2023, a CommIT-group result) closed this gap. The construction combines ramp secret sharing (Chapter 3), polynomial coding (Chapter 5), and vector commitments into a single protocol with both information-theoretic privacy and Byzantine resilience. The communication complexity $O(n \log n + Bd)$ is a substantial improvement over prior approaches that paid quadratic or worse overheads for combined guarantees.

Key Takeaway

Bonawitz protects against passive eavesdroppers but not active Byzantine adversaries. Real FL deployments face Byzantine attacks (model poisoning, Sybil, untargeted). Defending against them while preserving privacy requires a fundamentally new construction. The CommIT-group ByzSecAgg protocol of §11.2 achieves both properties at $O(n \log n + Bd)$ communication cost.

Quick Check

The Byzantine adversary in federated learning differs from the honest-but-curious adversary in that:

Byzantine adversaries follow the protocol but analyze observed messages.

Byzantine adversaries may deviate from the protocol — sending corrupted messages, refusing to participate, or adaptively colluding.

Byzantine adversaries are computationally bounded.

Byzantine adversaries are honest but unreliable (network failures).