Learning Where to Audit in Compressed Decentralized Training

When several organizations train a model together over a slow network, each machine sends compressed updates to its neighbors and trusts that they computed those updates honestly. Checking every update with zero-knowledge proofs is far too slow. Checking none of them leaves the group open to poisoning. A middle ground exists in cryptography: covert security with public verifiability. Under this model, each party commits to what it will compute. A random fraction of its steps is then opened and re-checked. Anyone caught deviating produces a signed, third-party-checkable "certificate of misbehavior." This proposal applies that idea to decentralized training and asks a question the cryptographic literature has not posed: given a fixed audit bandwidth, which steps should be audited?

Our answer is to treat audit allocation as a learning problem under bandit feedback, meaning the auditors learn only from the outcome of the audits they actually run (caught or not caught) and never see what would have happened elsewhere. The key observation is that public verifiability makes this feedback trustworthy. Because a certificate can be checked by anyone and cannot be forged against an honest party, honest nodes can pool their audit outcomes into one shared learner. A malicious node cannot poison that learner with fake "catches" that pull attention away from itself. Without public verifiability, pooled audit feedback would be an attack surface. With it, the honest nodes get a shared, unforgeable reward signal for learning where cheaters strike.

Core Claim

Take a semi-honest compressed gossip training protocol and lift it to publicly verifiable covert security. Then allocate audits with a discounted, floor-constrained bandit learner fed by verified certificates. At equal audit bandwidth, this should reduce an adaptive attacker's achievable harm below what uniform random auditing allows. The gain should appear exactly when the harm of cheating differs across nodes, rounds, or parameter blocks, and should vanish when harm is uniform. The second half of the claim matters as much as the first: in the homogeneous case, uniform auditing is already the right answer, and the method must match it rather than beat it.

Research Program

Making lossy compression auditable. The first step makes compressed training steps exactly re-checkable. Compressed decentralized methods such as DaSHCo and DAMSCo from Compressed Decentralized Momentum Stochastic Gradient Methods for Nonconvex Optimization send quantized differences of momentum and tracking vectors. The sparse-gossip method in DisPFL sends masked parameter subsets. The research file flags a tension here: cryptographic checks demand bit-identity, while compression is lossy. We resolve it by changing what is checked. We do not try to prove that a compressed message is "close" to an honest update, which would require expensive range proofs. Instead, we make the compressor deterministic given a committed seed and use fixed-point arithmetic. The honest compressed message then becomes a deterministic function of committed inputs: the model state, a commitment to the local minibatch, and the seed. An audit re-executes one step and checks exact equality.

Input consistency across rounds uses the indexed-hash commitments of MPC-Friendly Commitments for Publicly Verifiable Covert Security. That work reports 60x faster checks and 36x less communication than SHA3-256 inside secure computation. It applied them to static two-party inference in Certified Predictions using MPC-Friendly Publicly Verifiable Covertly Secure Commitments, not to multi-round training. Signed messages and certificate extraction follow Calling Out Cheaters. The generic semi-honest-to-verifiable lifting follows Black-Box Transformations from Passive to Covert Security with Public Verifiability, with certificate formats borrowed from Faster, Leaner, and Simpler. These papers supply the method. Our contribution in this step is the seeded-compressor commitment that makes compressed gossip fit their assumptions.

The privacy cost of re-execution. Re-executing a training step requires the minibatch, and we will not hide that cost. We run two audit modes. In the first, the minibatch is re-checked inside a garbled-circuit re-execution, which is feasible only for small models such as MNIST multilayer perceptrons and logistic regression. In the second, the opened step is revealed to one randomly drawn auditor. This suits cross-silo settings where integrity is the main concern. We report each mode's costs separately.

Scope boundary. Verification catches deviation from the protocol on committed data. It does not catch data that was poisoned before it was committed. The file notes this boundary for both PVC commitments and Helen. Model-poisoning attacks that craft updates directly, such as those in Covert Model Poisoning Against Federated Learning, are deviations and are in scope.

The audit-allocation learner. The second step is the learner itself. Audit targets are "arms" $k$, each a node-by-parameter-block-by-round-type pair with audit cost $c_k$ in bytes. Each round, the honest nodes jointly choose audit probabilities $p_k$ subject to

$$p_k \ge \epsilon_{\min} \ \text{for all } k, \qquad \sum_k p_k c_k \le B,$$

where $B$ is the per-round audit bandwidth and $\epsilon_{\min}$ is a deterrence floor. The floor preserves the standard covert guarantee: no target is ever audited with probability below $\epsilon_{\min}$. For a rational attacker with gain $G_k$ and certified penalty $P$, cheating on $k$ is unprofitable whenever $(1-p_k)G_k < p_k P$. The learner's job is to spend the budget above the floor where the unknown $G_k$ is largest. The reward for arm $k$ is a verified certificate, weighted by the measured harm of the deviation it exposes.

Two prior results constrain this design. First, Multi-Agent Learning for Iterative Dominance Elimination proves that standard no-regret learners weight all history equally and take exponentially long to react once an opponent shifts strategy. An attacker who moves targets after being caught would exploit exactly this. We therefore build on their Exp3-DH, which discounts old rewards. Second, Survival of the strictest shows that mixed equilibria are unstable under bandit-feedback learning. Inspection games between auditor and cheater typically have mixed equilibria, so an unconstrained learner would drift toward a predictable pure allocation that the attacker can evade. The floor, together with entropy regularization in the style of Uncoupled and Convergent Learning in Two-Player Zero-Sum Markov Games with Bandit Feedback, is how we keep the allocation from collapsing. The analysis goal is a regret bound against the best fixed floor-feasible allocation in hindsight, under an attacker whose target sequence has bounded switches. We do not expect better than the slow last-iterate rates known for bandit games, and we state that up front.

Prior work on incentives. The game-theoretic work closest to ours is A Game-theoretic Framework for Privacy-preserving Federated Learning. It derives conditions under which a server has no incentive to attack, but it relies on an abstract oracle that supplies payoff bounds. Our certificates replace that oracle with a concrete, checkable signal. Our learner replaces known payoff bounds with ones learned from outcomes.

Baselines

Naive references. The do-nothing reference is the unmodified semi-honest protocol: DaSHCo on Fixup-ResNet-20 and NanoGPT, and DisPFL on CIFAR-10. We run it with and without attackers to measure the damage ceiling. For the clean case, the file reports DisPFL at 85.70% on Dirichlet non-IID CIFAR-10, and DAMSCo/DaSHCo at 1.62–1.64 validation loss on Tiny-Shakespeare, both from the cited papers. We reproduce these before adding any verification.

Uniform random auditing (strongest competitor). The strongest competitor is uniform random auditing at the same bandwidth $B$. This is what the black-box PVC transformation gives by default, applied to our seeded-compressor protocol. It is the strongest competitor because it is the cryptographic default, it is minimax-safe when harm is homogeneous, and it costs the same per round. Both methods use identical commitments, certificates, data partitions, attack implementations and audit bytes. The uniform baseline's rate is tuned over the same grid as our floor $\epsilon_{\min}$. No reported result found on Lacuna for uniform PVC auditing of decentralized training, so we establish this number ourselves. Beating it means lower attacker success, or lower harm-weighted undetected deviation, at equal $B$, across at least three of the four attacker types below. It also means no worse than uniform in the homogeneous-harm control, where we require statistical parity.

Score-guided auditing. A third baseline audits the updates that a Krum-style anomaly score ranks most suspicious, plus the same floor.

Robust aggregation without audits. We also run Krum and Trimmed Mean with no audits. Against Krum, Covert Model Poisoning reports 87% attacker accuracy for its low-complexity attack, 76% for its blind attack, and about 90% targeted attack accuracy on MNIST. These are the reference points our MNIST runs must reproduce first.

Ablations. Two ablations isolate the key ingredients. The first keeps the learner but pools audit outcomes without public verifiability, as in plain covert security. Malicious nodes may then report fabricated catches. This isolates whether public verifiability is what makes pooled bandit learning safe. The second removes the history discount and the floor, separately, to test the predictions drawn from Wu et al. and Giannou et al.

Why not just…?

Why not just use robust aggregation like Krum? The cited covert-poisoning results show 87% attacker accuracy against Krum even for a low-complexity attack. An outlier flag also cannot be proven to a third party: a non-IID honest client and a cheater look alike. We still run robust aggregation as a baseline and combine it with auditing. If Krum alone holds attacker accuracy as low as our method at zero audit bandwidth on our benchmarks, the proposal's case weakens and we will say so.

Why not just audit uniformly at random, as standard PVC does? This is the real threat. If cheating harm is roughly equal across targets, uniform auditing is already optimal, and learning only adds variance. The experiments sweep harm heterogeneity explicitly: uniform layers versus a backdoor confined to one block, and early versus late training rounds. Our claim survives only if the gap opens as heterogeneity grows and closes to parity when harm is uniform.

Why not just audit whatever the anomaly score flags? Deterministic targeting by score tells an adaptive attacker exactly where not to be. Covert poisoning is designed to stay below such scores. The score-guided baseline with the same floor tests this directly. If it matches the bandit learner, the simpler method wins, and we would recast the anomaly score as context for the learner rather than claim the learner is needed.

Why not just use zero-knowledge proofs for every step? Helen shows that malicious-secure training is practical only for regularized linear models, after heavy restructuring. Its generic malicious baseline took months, 20,689x slower. On the Gas Sensor dataset we can compare our audited linear-model training against Helen's reported runtime of under 3 hours. That comparison is about cost, since Helen gives full rather than probabilistic integrity.

Proposed Experiments

Attack setups. We start on MNIST with MLP and SVM models under the covert-poisoning attacks, where garbled-circuit audits are feasible. We then move to CIFAR-10 Dirichlet non-IID with DisPFL and with DaSHCo on Fixup-ResNet-20, and to Tiny-Shakespeare with NanoGPT, the latter two in revealed-audit mode. Each setting has 16 to 32 nodes on ring and random graphs, with 10–25% attackers. We use four attacker types: a static cheater; a target-switching cheater; a best-responder to the empirical audit frequencies; and a harm-concentrated backdoor attacker confined to one parameter block or late rounds.

Metrics. We report targeted attack accuracy, clean accuracy or validation loss, harm-weighted undetected deviation, rounds to first certificate, audit bytes per round as a fraction of gossip bytes, and false certificates. The last should be zero under defamation-freeness, and we verify that empirically.

Decisive checks. Four checks decide the outcome. First, at equal $B$, the learner must beat uniform auditing against the best-responding and concentrated attackers and tie it in the homogeneous control. Second, the non-verifiable pooling ablation must collapse under fabricated-catch attacks, which would show that public verifiability carries the result. Third, removing the discount should slow recovery after an attacker switches targets, and removing the floor should let the best-responder escape detection, matching the two theoretical predictions. Fourth, the seeded deterministic compressor must reproduce the reported DisPFL and DaSHCo accuracy within seed variance, showing that auditability does not cost accuracy.