Proving a Gradient Was Clipped

Every differential-privacy guarantee in federated learning rests on a sensitivity bound, and in practice that bound is a clipping step the client performs on itself. The server asks for an update $\Delta_i$ with $\lVert \Delta_i \rVert_2 \le B$ , adds noise calibrated to $B$ , and publishes an $(\varepsilon, \delta)$ claim. The claim is only as good as the clipping.

The awkward part is that the two properties the system wants are in direct tension. Secure aggregation exists so that the server never sees $\Delta_i$ . But if the server never sees $\Delta_i$ , it cannot check $\lVert \Delta_i \rVert_2 \le B$ either. The privacy mechanism and the integrity mechanism are asking for opposite things from the same bytes.

The bound is not an implementation detail of the client. It is a premise of the server’s privacy accounting. A protocol that cannot verify the premise is publishing an $\varepsilon$ it has not earned.

What goes wrong when nobody checks

The failure is not subtle. A client that skips clipping and submits an update scaled by $c$ contributes $c$ times the intended influence, and the noise the server adds is still calibrated to $B$ . One participant out of ten thousand, submitting a single unclipped update per round, is enough to plant a targeted backdoor in most vision and next-token models without moving aggregate accuracy enough to trip a validation-loss alarm.

The usual mitigations do not close it:

Norm-based outlier rejection at the server. Requires plaintext updates, so it is incompatible with the secure aggregation that motivated the design.
Multi-Krum and its relatives. Also plaintext, also $O(n^2)$ pairwise distances per round, and the robustness guarantees assume an honest majority in a setting where client identity is cheap.
Trusted client attestation. Moves the problem to the hardware vendor and does nothing against a client running an unmodified binary on doctored training data.
Bounding the aggregate instead. Cheap and useless: a single large update hides comfortably inside an aggregate whose norm is dominated by ten thousand honest ones.

What is actually wanted is a proof, attached to the ciphertext, that the plaintext inside satisfies the bound. That is a range proof over a committed vector, and it is a solved problem — the question is what it costs.

The shape of the circuit

The statement is small to write down. Given a Pedersen or KZG commitment $C_i$ to the update vector, prove knowledge of $\Delta_i$ such that $C_i$ opens to it and

\sum_{j=1}^{d} \Delta_{i,j}^{2} \;\le\; B^{2}

Note the squaring on both sides: the constraint is stated on the squared norm so no square root appears in the circuit. That single change is the difference between a few multiplications per coordinate and a full fixed-point Newton iteration per coordinate.

Three details do most of the damage to the cost:

Fixed-point encoding. Model updates are floats; circuits are over a prime field. Each coordinate becomes a signed fixed-point integer, and the soundness of the bound now depends on the range of that encoding rather than on the arithmetic being exact.
Overflow. With $d \approx 10^7$ and coordinates scaled to $2^{32}$ , the sum of squares does not fit in a 254-bit field without decomposition. The sum has to be accumulated in chunks with explicit carry handling, and the chunk boundaries are where soundness bugs live.
Commitment compatibility. The proof is worthless unless the commitment it opens is the same object the aggregation protocol consumes. Getting a Pedersen commitment over the proof system’s curve to line up with the masking scheme is usually the part that forces a redesign.

What it costs

Rough figures for a single client proving one round, $d = 10^7$ parameters, measured on one consumer CPU core, no GPU, no batching. Treat these as order-of-magnitude — they move by a factor of two with encoding choices — but the relative picture is stable:

Scheme	Prover	Proof size	Verifier	Trusted setup
Bulletproofs (inner product)	~110 s	~2 KB	~380 ms	none
Groth16 (per-circuit)	~45 s	128 B	~2 ms	per-circuit
PLONK (universal)	~70 s	~500 B	~6 ms	universal
STARK (FRI, 100-bit)	~25 s	~180 KB	~14 ms	none

The verifier column is what matters for the server, and all four are negligible against the cost of aggregation itself. The prover column is what decides whether the protocol is deployable: 45 seconds of proving per round on a phone is not happening, and a client that skips a round because proving timed out is a new availability problem the sampling assumptions did not account for.¹

The proof-size column matters more than it looks. STARK proofs at ~180 KB per client, times ten thousand clients, is 1.8 GB of proofs per round moving to the server — comparable to the model updates themselves, and the bandwidth asymmetry is exactly backwards for cross-device settings.

Where the bound stops being the hard part

Suppose all of this is built and the norm bound is enforced under encryption. The system has bought one thing: no single client can exceed influence $B$ in one round. It has not bought:

Sybil resistance. Ten clients each submitting a perfectly clipped update pointed the same direction reproduce the unclipped attack exactly. The bound is per-client, and client identity is the unsolved part.
Cross-round accumulation. $B$ per round, times $T$ rounds, is $TB$ of influence for a patient adversary. Bounding this needs state the server cannot keep without linking rounds to clients, which is what the privacy design forbids.
Direction. A clipped update can point anywhere on the sphere of radius $B$ . Nothing in a norm proof says the gradient came from data at all, and proving that means proving a training step, which is several orders of magnitude harder.

This is the pattern I keep running into, and it is why I find proofs of this shape interesting rather than exciting. The verifiable version of a system makes one assumption explicit and, in doing so, shows exactly how many other assumptions were leaning on it. A proof of clipping converts “we hope clients clip” into “clients clip, and identity, rounds, and direction remain unaccounted for” — which is worse-sounding and much more useful.

# The bound, before any of the above. Two lines, no enforcement.
def clip(delta: Tensor, B: float) -> Tensor:
    norm = delta.norm(p=2)
    return delta * min(1.0, B / (norm + 1e-12))

That function is the entire integrity story in most federated deployments shipping today. It runs on the client, and nothing downstream can tell whether it ran.

Privacy amplification by subsampling assumes each client is included with a known probability independent of its data. Dropping clients whose proving timed out correlates participation with device class, which correlates with data distribution, which breaks the independence the amplification bound needs. ↩

What goes wrong when nobody checks

The shape of the circuit

What it costs

Where the bound stops being the hard part

Footnotes