Game of Coding under Computation-Dependent Adversarial Noise

Hanzaleh Akbari Nodehi; Mohammad Ali Maddah-Ali

REVIEW 2 major objections 4 minor 40 references

The paper proves that allowing an adversary to tailor its noise distribution to the realized computation does not enlarge its achievable performance region: every input-dependent strategy has an input-independent counterpart with exactly th

Reviewed by Pith at T0; open to challenge. T0 means a machine referee read the full paper against a public rubric. the ladder, T0–T4 →

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗

T0 review · deepseek-v4-flash

2026-07-31 23:44 UTC pith:UHOZQQGX

load-bearing objection Correct but narrower than the abstract suggests: the equivalence holds for adversaries that adapt to U alone, and the paper should say so; worth a serious referee. the 2 major comments →

arxiv 2607.23318 v1 pith:UHOZQQGX submitted 2026-07-25 cs.IT math.IT

Game of Coding under Computation-Dependent Adversarial Noise

Hanzaleh Akbari Nodehi , Mohammad Ali Maddah-Ali This is my paper

classification cs.IT math.IT MSC 94A1591A80

keywords game of codinginput-dependent adversarial noiseStackelberg equilibriumachievable performance regionprobability of acceptancemean-squared estimation errordecentralized machine learningrational adversaries

verification ladder T0 review T1 audit T2 compute T3 formal T4 reserved

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper asks whether an adversary who can condition its report noise on the true value being computed can do better than one who must use a fixed noise distribution. It answers no. In a unified n-node, d-dimensional game-of-coding model, the authors show that averaging any input-dependent noise distribution over the distribution of the ground truth yields an input-independent strategy with identical acceptance probability and identical accepted mean-squared error. Therefore the achievable (acceptance, error) region and the Stackelberg equilibrium are unchanged. This matters for decentralized computation, where workers may know or infer the target value; the framework's guarantees survive such adaptive attackers.

Core claim

The central result is Theorem 1: for any conditional adversarial-noise family {g_u}, the averaged distribution g(z_Q) = E_U[g_U(z_Q)] is a valid noise distribution, and using it unconditionally preserves both P_A(g,η) and MSE(g,η) for every threshold η. The proof rests on two observations: the acceptance event and the midrange-estimator error depend only on the noise realizations, not on U; and marginalizing the joint distribution over U collapses the conditional dependence, leaving the same joint noise distribution as the averaged strategy. Consequently, the input-dependent and input-independent games have identical performance regions (Theorem 2) and identical optimal thresholds and equili

What carries the argument

The averaging identity g(z_Q) = E_U[g_U(z_Q)], applied to the joint noise vector. The acceptance rule uses the coordinatewise max–min spread (range) of all reports, and the estimator is the coordinatewise midrange; Lemma 3 shows both are functions of the noise tuple N alone, so the ground truth U cancels. Lemma 2 shows that after averaging, the marginal distribution of honest and adversarial noises is f_{N_K}(x_K) g(z_Q), exactly as under the averaged input-independent strategy.

Load-bearing premise

The entire argument assumes the adversary's noise is conditionally independent of the honest noises given the ground truth; if the adversary can observe or statistically depend on the honest nodes' noise realizations, the averaging reduction and the equivalence of the two models can fail.

What would settle it

Give the adversary access to the realized honest noises (e.g., by observing the honest nodes' reports before submitting its own) and search over conditional strategies g_{u,x_K}; if any such strategy achieves a (P_A, MSE) pair outside the set achievable by input-independent strategies for some threshold η, then the equivalence in Theorem 1 breaks, confirming that the conditional-independence assumption in equation (6) is load-bearing.

Watch this falsifier. Get emailed when new claim-graph text bears on it.

If this is right

The game-of-coding guarantees proved for input-independent adversaries transfer unchanged to adversaries who can adapt their noise to the computed value.
A data collector can design acceptance thresholds and estimators while ignoring the possibility of input-dependent noise; worst-case behavior is identical.
The achievable (probability-of-acceptance, mean-squared-error) region is the same for both models, so the adversary's best-response utility and the DC's worst-case utility are equal at every threshold.
Prior scalar and two-node vector models are exact special cases, so the result unifies and extends them.
The reduction works for arbitrary U distribution and arbitrary correlation among adversarial nodes, so it covers coordinated multi-node attacks.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

The result depends crucially on the adversary not observing the honest noises (conditional independence given U). If the adversary could condition its noise on the honest reports, the factorization in Lemma 2 fails; a carefully constructed input-dependent strategy could then beat any input-independent one. Constructing a counterexample for that variant would delineate the boundary of the theorem.
The same averaging argument may generalize to other acceptance and estimation rules that are shift-invariant in the noise (depend only on report differences), suggesting input-dependent noise is broadly harmless whenever the adversary is blind to honest noise.
In practice, an adversary that knows U but not the honest noise is roughly as powerful as one that knows only the distribution of U; the paper makes this intuition exact for the game-of-coding metrics.
A testable consequence: in simulations where g_u is sharply peaked at values far from U, the averaged strategy should reproduce identical acceptance and error curves, confirming the equivalence.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit.

Desk Editor's Note

Correct but narrower than the abstract suggests: the equivalence holds for adversaries that adapt to U alone, and the paper should say so; worth a serious referee.

read the letter

Main takeaway: Theorem 1 is correct, and it is narrower than the abstract suggests. It shows that if the adversary can adapt its noise distribution to the ground-truth value U but not to the honest noise realizations, then that adaptation buys nothing: averaging the conditional distributions g_u over U gives an input-independent strategy with exactly the same probability of acceptance and accepted mean-squared error. The proof is a short marginalization argument, and it works because the acceptance event and the estimation error depend only on the noise tuple, not on U. That is a real result, and it unifies the earlier game-of-coding models cleanly.

What the paper does well: the unified n-node, d-dimensional formulation is genuinely useful, and the appendices hold up. Lemmas 2 and 3 are the right pieces, and the chain from Theorem 1 to Theorems 2 and 3 is sound. There are no fitted parameters, no code, no data, and none are needed. The equivalence is not stated in the cited prior work, though it is a natural consequence of the model.

The soft spot is Eq. (6), and it is a scope boundary rather than an internal error. Eq. (6) assumes the adversarial noise is conditionally independent of the honest noise given U. If the adversary can see or couple its reports to the realized honest noises, then the joint density becomes f_NK(x) f_NQ|NK,U(z|x,u), which does not factor as in (6), and no input-independent averaged strategy can reproduce the joint distribution. The paper states Eq. (6) but does not flag it as the key restriction. The introduction's motivating examples — adversarial examples, model poisoning with 'available information about benign updates' — invite a broader reading than the model supports. The honest takeaway is: input-dependence on U alone buys nothing; adversaries that adapt to honest noise are outside the model. That sentence should be more prominent, ideally in the abstract.

Minor point: the theorem statements omit the positivity-of-acceptance-probability condition for MSE. The proof includes it, so the fix is easy. If PA = 0, MSE is undefined and the equality needs to be qualified.

Who this is for: people working on game-of-coding or rational-adversary coding, especially equilibrium analysis. It is not going to change practice outside that niche. It deserves a serious referee; it is a clean, honest, small paper that needs a moderate revision to scope its claims.

Referee Report

2 major / 4 minor

Summary. The paper introduces a unified n-node, d-dimensional 'game of coding' model in which the adversarial noise distribution may depend on the realized ground-truth computation U. The main result (Theorem 1) constructs, for any input-dependent adversarial strategy {g_u}_{u∈U}, an averaged input-independent strategy ̄g = E_U[g_U] that achieves exactly the same probability of acceptance and the same accepted mean-squared estimation error for every threshold η. From this, the authors conclude that the input-dependent and input-independent models have identical achievable performance regions (Theorem 2) and identical Stackelberg equilibria (Theorem 3). The proofs in Appendices B–D are built on the law of total probability and on the observation that both the acceptance event and the midrange estimation error depend only on the noise realizations, not on U.

Significance. If the result stands, this is a clean negative result: allowing adversarial noise to depend on the ground-truth computation U does not enlarge the adversary's power within the modeled class of acceptance/estimation rules. The paper's main technical contribution is an exact averaging reduction, and it provides a useful unification of previous scalar and vector game-of-coding models. The proof is transparent, self-contained, and free of fitted parameters. However, the scope of the claim is narrower than the Introduction's motivating examples suggest, and the formal theorem statements omit a positivity condition needed for the conditional MSE. These issues are correctable but must be addressed before the paper can be accepted.

major comments (2)

[Section II, Eq. (6)] The equivalence in Theorem 1 relies critically on the factorization f_{N_K,N_Q|U}=f_{N_K}g_u, which excludes adversaries that observe or couple their reports with realized honest noises. The Introduction's motivating examples (adversarial examples, model poisoning with 'available information about benign updates') invite a broader reading. Without (6), Lemma 2's marginalization fails: the joint density becomes f_{N_K|U}(x|u)f_{N_Q|N_K,U}(z|x,u), which cannot generally be written as f_{N_K}(x)\bar g(z). Please state prominently in the abstract and Section I that only dependence on U is covered, and identify honest-noise-adaptive adversaries as an explicit limitation.
[Section III, Theorem 1 and Appendix B] The proof of Theorem 1, specifically the step at Eq. (80)–(81), establishes MSE equality only under the condition PA(g,η)>0, but the theorem statement claims equality for every η∈Λ_DC with no qualification. When an adversarial strategy makes acceptance probability zero (e.g., reports far outside the threshold), MSE is undefined, so the statement 'MSE(g,η)=MSE(\bar g,η)' is not a well-formed equality. The same issue affects the definition of the performance region R^σ(η) in (30) and, consequently, Theorems 2–3. Please add the positivity precondition (or a consistent convention for zero-probability acceptance) to the theorem statements and adjust the performance-region definitions accordingly.

minor comments (4)

[Section II, Eq. (8)] The definition of Λ^ind_AD uses '∃g such that g_u=g' but the symbol g is also used for the averaged PDF in (23) and for the strategy. Please use distinct notation (e.g., g_0 for the common PDF) to avoid confusion.
[Appendix B, Lemma 1, Eq. (54)] The exchange of expectation and integral is justified by Tonelli's theorem (nonnegativity is the applicable condition); please cite Tonelli explicitly rather than writing 'because the integrand is nonnegative'.
[Abstract and Introduction] The phrase 'for every family of conditional adversarial-noise distributions' in the abstract should be qualified by the conditional independence assumption (6), so that readers are immediately aware that the adversary cannot adapt to honest noise realizations.
[Section III, after Theorem 1] The sentence 'Theorem 1 states that the dependence of the adversarial-noise distribution on U can be removed without changing either performance metric' is correct, but it would be helpful to add '(under the standing assumption (6))' to keep the scope in view.

Circularity Check

0 steps flagged

No significant circularity; Theorem 1 is a direct averaging/marginalization identity under the paper's explicitly stated conditional-independence assumption in Eq. (6).

full rationale

Theorem 1 is derived self-containedly from the model definitions. For any input-dependent strategy g, the averaged PDF \bar g(z_Q)=E_U[g_U(z_Q)] is shown to be a valid joint PDF (Lemma 1). Lemma 2 then proves, using the stated conditional-independence assumption in Eq. (6), that both the original and the averaged strategy induce exactly the same marginal joint noise density f_{N_K}(x_K)\bar g(z_Q). Lemma 3 shows that the acceptance event and the squared estimation error depend only on the noise tuple, because L(Y)=U+L(N) and R(Y)=U+R(N). The equalities PA(g,η)=PA(\bar g,η) and MSE(g,η)=MSE(\bar g,η) therefore follow from the law of total probability and the shift-invariance of the acceptance/estimation mechanism—not from any fitted parameter, hidden assumption, or circular definition. The citations to the authors' prior game-of-coding works are contextual and used to identify special cases; Appendix A derives those reductions from the present definitions rather than importing them as load-bearing. The only genuinely load-bearing modeling choice is Eq. (6), namely that the adversary cannot observe or statistically couple its reports with the realized honest noises, and that honest noises are independent of U. This is explicitly stated in the paper and functions as a scope boundary, not a circular step: if (6) failed, the marginalization f_{N_K}(x_K)\bar g(z_Q) would not hold and the equivalence could fail. No prediction is a renamed fit, no ansatz is smuggled in via citation, and no uniqueness claim is invoked. Hence the paper is not circular.

Axiom & Free-Parameter Ledger

0 free parameters · 5 axioms · 0 invented entities

The central result needs no fitted parameters. It depends structurally on the conditional-independence assumption (Eq. 6) and the additive noise representation; both are explicit model choices. The mathematical steps use standard integration facts.

axioms (5)

domain assumption The adversary's conditional noise distribution is independent of honest noises given U (Eq. 6: f_{N_K,N_Q|U} = f_{N_K} g_u)
Central to Lemma 2; without it, averaging over U would not reproduce the joint noise distribution.
domain assumption Additive noise representation Y_i = U + N_i for all nodes (Eqs. 2-3), which is without loss of generality for arbitrary reports
Underpins the cancellation of U in Lemma 3.
domain assumption Honest noises are independent of U and bounded by Δ (Eq. 4)
Used to define Λ_DC and the acceptance threshold; not load-bearing for the equivalence but part of the model.
standard math Tonelli's theorem / interchange of expectation and integral for nonnegative integrands
Used in Lemma 1 to show the averaged PDF integrates to one.
domain assumption Existence of joint PDFs for adversarial strategies, including Dirac-delta generalized densities for mixed/discrete strategies
The action sets (7)-(8) are defined in terms of PDFs; the proof follows the density formalism of the prior game-of-coding papers.

pith-pipeline@v1.3.0-alltime-deepseek · 15892 in / 14623 out tokens · 138660 ms · 2026-07-31T23:44:33.815713+00:00 · methodology

0 comments

read the original abstract

The game of coding framework was introduced to extend coding-theoretic recovery beyond its traditional limit, under which the number of honest reports must exceed the number of adversarial or corrupted reports. It does so by exploiting the rational behavior of adversarial participants and their incentive to keep the system live. Existing game-of-coding formulations, however, assume that the adversarial-noise distribution is independent of the realized ground-truth computation. This assumption may be restrictive when an informed adversary can adapt its reports to the value being computed. In this paper, we study the game of coding with input-dependent adversarial noise. We introduce a unified multi-node, multidimensional formulation. For every family of conditional adversarial-noise distributions, we construct an input-independent joint noise distribution, and prove that this reduction exactly preserves the probability of acceptance and the accepted mean-squared estimation error. Consequently, the input-dependent and input-independent models have identical achievable performance regions, and the same equilibrium utilities.

discussion (0)

Reference graph

Works this paper leans on

40 extracted references · 3 linked inside Pith

[1]

Guruswami, A

V. Guruswami, A. Rudra, and M. Sudan,Essential Coding Theory. Draft is Available, 2022

2022
[2]

Frame codes for distributed coded computation,

R. Yosibash and R. Zamir, “Frame codes for distributed coded computation,” in2021 11th International Symposium on Topics in Coding (ISTC), pp. 1–5, 2021

2021
[3]

Polynomial codes: an optimal design for high-dimensional coded matrix multiplication,

Q. Yu, M. Maddah-Ali, and S. Avestimehr, “Polynomial codes: an optimal design for high-dimensional coded matrix multiplication,”Advances in Neural Information Processing Systems, vol. 30, 2017

2017
[4]

Lagrange coded computing: Optimal design for resiliency, security, and privacy,

Q. Yu, S. Li, N. Raviv, S. M. M. Kalan, M. Soltanolkotabi, and S. A. Avestimehr, “Lagrange coded computing: Optimal design for resiliency, security, and privacy,” inThe 22nd International Conference on Artificial Intelligence and Statistics, pp. 1215–1225, PMLR, 2019

2019
[5]

Analog error-correcting codes,

R. M. Roth, “Analog error-correcting codes,”IEEE Transactions on Information Theory, vol. 66, no. 7, pp. 4075– 4088, 2020. July 28, 2026 DRAFT 13

2020
[6]

Codedsketch: A coding scheme for distributed computation of approximated matrix multiplication,

T. Jahani-Nezhad and M. A. Maddah-Ali, “Codedsketch: A coding scheme for distributed computation of approximated matrix multiplication,”IEEE Transactions on Information Theory, vol. 67, no. 6, pp. 4185–4196, 2021

2021
[7]

Berrut approximated coded computing: Straggler resistance beyond polynomial computing,

T. Jahani-Nezhad and M. A. Maddah-Ali, “Berrut approximated coded computing: Straggler resistance beyond polynomial computing,”IEEETransactionsonPatternAnalysisandMachineIntelligence, vol. 45, no. 1, pp. 111– 122, 2023

2023
[8]

Bitcoin: A peer-to-peer electronic cash system,

N. S. Bitcoin, “Bitcoin: A peer-to-peer electronic cash system,” 2008

2008
[9]

Ethereum white paper,

V. Buterinet al., “Ethereum white paper,”GitHub repository, vol. 1, pp. 22–23, 2013

2013
[10]

Blockchains cannot rely on honesty,

J. Sliwinski and R. Wattenhofer, “Blockchains cannot rely on honesty,” inThe 19th International Conference on Autonomous Agents and Multiagent Systems (AAMAS 2020), 2019

2020
[11]

Fact and fiction: Challenging the honest majority assumption of permissionless blockchains,

R. Han, Z. Sui, J. Yu, J. Liu, and S. Chen, “Fact and fiction: Challenging the honest majority assumption of permissionless blockchains,” inProceedings of the 2021 ACM Asia Conference on Computer and Communications Security, pp. 817–831, 2021

2021
[12]

"Zero Cost

J. S. Gans and H. Halaburda, “"Zero Cost" majority attacks on permissionless blockchains,” tech. rep., National Bureau of Economic Research, 2023

2023
[13]

Proofs, arguments, and zero-knowledge,

J. Thaler, “Proofs, arguments, and zero-knowledge,”Foundations and Trends®in Privacy and Security, vol. 4, no. 2–4, pp. 117–660, 2022

2022
[14]

ZEN: An optimizing compiler for verifiable, zero-knowledge neural network inferences,

B. Feng, L. Qin, Z. Zhang, Y. Ding, and S. Chu, “ZEN: An optimizing compiler for verifiable, zero-knowledge neural network inferences,”Cryptology ePrint Archive, 2021

2021
[15]

ZkCNN: Zero knowledge proofs for convolutional neural network predictions and accuracy,

T. Liu, X. Xie, and Y. Zhang, “ZkCNN: Zero knowledge proofs for convolutional neural network predictions and accuracy,” inProceedings of the 2021 ACM SIGSAC Conference on Computer and Communications Security, pp. 2968–2985, 2021

2021
[16]

Zero-knowledge proof meets machine learning in verifiability: A survey,

Z. Xing, Z. Zhang, J. Liu, Z. Zhang, M. Li, L. Zhu, and G. Russello, “Zero-knowledge proof meets machine learning in verifiability: A survey,”arXiv preprint arXiv:2310.14848, 2023

Pith/arXiv arXiv 2023
[17]

SecureML: A system for scalable privacy-preserving machine learning,

P. Mohassel and Y. Zhang, “SecureML: A system for scalable privacy-preserving machine learning,” in2017 IEEE symposium on security and privacy (SP), pp. 19–38, IEEE, 2017

2017
[18]

vCNN: Verifiable convolutional neural network based on zk-snarks,

S. Lee, H. Ko, J. Kim, and H. Oh, “vCNN: Verifiable convolutional neural network based on zk-snarks,”IEEE Transactions on Dependable and Secure Computing, 2024

2024
[19]

Mystique: Efficient conversions for{Zero-Knowledge}proofs with applications to machine learning,

C. Weng, K. Yang, X. Xie, J. Katz, and X. Wang, “Mystique: Efficient conversions for{Zero-Knowledge}proofs with applications to machine learning,” in30th USENIX Security Symposium (USENIX Security 21), pp. 501– 518, 2021

2021
[20]

Interactive proofs for rounding arithmetic,

S. Chen, J. H. Cheon, D. Kim, and D. Park, “Interactive proofs for rounding arithmetic,”IEEE Access, vol. 10, pp. 122706–122725, 2022

2022
[21]

Succinct zero knowledge for floating point computations,

S. Garg, A. Jain, Z. Jin, and Y. Zhang, “Succinct zero knowledge for floating point computations,” inProceedings of the 2022 ACM SIGSAC Conference on Computer and Communications Security, pp. 1203–1216, 2022

2022
[22]

Taking{Proof-Based}verified computation a few steps closer to practicality,

S. Setty, V. Vu, N. Panpalia, B. Braun, A. J. Blumberg, and M. Walfish, “Taking{Proof-Based}verified computation a few steps closer to practicality,” in21st USENIX Security Symposium (USENIX Security 12), pp. 253–268, 2012

2012
[23]

Experimenting with zero-knowledge proofs of training,

S. Garg, A. Goel, S. Jha, S. Mahloujifar, M. Mahmoody, G.-V. Policharla, and M. Wang, “Experimenting with zero-knowledge proofs of training,”Cryptology ePrint Archive, 2023. July 28, 2026 DRAFT 14

2023
[24]

Game of coding: Beyond honest-majority assumptions,

H. A. Nodehi, V. R. Cadambe, and M. A. Maddah-Ali, “Game of coding: Beyond honest-majority assumptions,” IEEE Transactions on Information Theory (submitted), 2024

2024
[25]

Game of coding: Sybil resistant decentralized machine learning with minimal trust assumption,

H. A. Nodehi, V. R. Cadambe, and M. A. Maddah-Al, “Game of coding: Sybil resistant decentralized machine learning with minimal trust assumption,”arXiv preprint, 2024. https://arxiv.org/abs/2410.05540

arXiv 2024
[26]

Game of coding for vector-valued computations,

H. A. Nodehi, P. Moradi, S. Mohajer, and M. A. Maddah-Ali, “Game of coding for vector-valued computations,” arXiv preprint arXiv:2602.04810, 2026

Pith/arXiv arXiv 2026
[27]

\mathsf{VISTA}:Decentralizedmachinelearning in adversary dominated environments,

H.A.Nodehi,P.Moradi,S.Mohajer,andM.A.Maddah-Ali,“\mathsf{VISTA}:Decentralizedmachinelearning in adversary dominated environments,”arXiv preprint arXiv:2605.07841, 2026

Pith/arXiv arXiv 2026
[28]

Game of coding with an unknown adversary,

H. Akbari Nodehi, P. Moradi, and M. A. Maddah-Ali, “Game of coding with an unknown adversary,” in2025 IEEE International Symposium on Information Theory (ISIT), (Ann Arbor, MI, USA), 2025

2025
[29]

Learning from acceptance: Cumulative regret in the game of coding,

H. Akbari Nodehi, P. Moradi, and M. A. Maddah-Ali, “Learning from acceptance: Cumulative regret in the game of coding,”arXiv e-prints, pp. arXiv–2605, 2026

2026
[30]

Game of coding: Coding theory in the presence of rational adversaries, motivated by decentralized machine learning,

H. A. Nodehi, V. R. Cadambe, and M. A. Maddah-Ali, “Game of coding: Coding theory in the presence of rational adversaries, motivated by decentralized machine learning,”arXiv preprint arXiv:2601.02313, 2026

arXiv 2026
[31]

Intriguing properties of neural networks,

C. Szegedy, W. Zaremba, I. Sutskever, J. Bruna, D. Erhan, I. Goodfellow, and R. Fergus, “Intriguing properties of neural networks,” inInternational Conference on Learning Representations, 2014

2014
[32]

Explaining and harnessing adversarial examples,

I. J. Goodfellow, J. Shlens, and C. Szegedy, “Explaining and harnessing adversarial examples,” inInternational Conference on Learning Representations, 2015

2015
[33]

Towards deep learning models resistant to adversarial attacks,

A. Madry, A. Makelov, L. Schmidt, D. Tsipras, and A. Vladu, “Towards deep learning models resistant to adversarial attacks,” inInternational Conference on Learning Representations, 2018

2018
[34]

Towards evaluating the robustness of neural networks,

N. Carlini and D. Wagner, “Towards evaluating the robustness of neural networks,” in2017 IEEE Symposium on Security and Privacy, pp. 39–57, IEEE, 2017

2017
[35]

Analyzing federated learning through an adversarial lens,

A. N. Bhagoji, S. Chakraborty, P. Mittal, and S. Calo, “Analyzing federated learning through an adversarial lens,” inProceedings of the 36th International Conference on Machine Learning, vol. 97 ofProceedings of Machine Learning Research, pp. 634–643, PMLR, 2019

2019
[36]

A little is enough: Circumventing defenses for distributed learning,

M. Baruch, G. Baruch, and Y. Goldberg, “A little is enough: Circumventing defenses for distributed learning,” inAdvances in Neural Information Processing Systems, vol. 32, Curran Associates, Inc., 2019

2019
[37]

How to backdoor federated learning,

E. Bagdasaryan, A. Veit, Y. Hua, D. Estrin, and V. Shmatikov, “How to backdoor federated learning,” in Proceedings of the Twenty Third International Conference on Artificial Intelligence and Statistics, vol. 108 of Proceedings of Machine Learning Research, pp. 2938–2948, PMLR, 2020

2020
[38]

Local model poisoning attacks to Byzantine-Robust federated learning,

M. Fang, X. Cao, J. Jia, and N. Gong, “Local model poisoning attacks to Byzantine-Robust federated learning,” in29th USENIX Security Symposium (USENIX Security 20), pp. 1605–1622, USENIX Association, August 2020

2020
[39]

Von Stackelberg,Market structure and equilibrium

H. Von Stackelberg,Market structure and equilibrium. Springer Science & Business Media, 2010. Appendix A Relationship with Previous Game-of-Coding Models In this appendix, we show that the acceptance and estimation mechanism defined in (10)–(15) provides a common generalization of the mechanisms considered in the previous game-of-coding papers [24]–[26]. ...

2010
[40]

This completes the proof

Equation (71) proves (63). This completes the proof. We are now ready to prove Theorem 1. Proof of Theorem 1.Consider an arbitrary input-dependent adversarial strategy g∈Λ dep AD (t).(72) Let gand gbe defined according to (23) and (24), respectively. Lemma 1 establishes thatgis a valid joint PDF and that g∈Λ ind AD(t).(73) We next prove equality of the pr...

2026

[1] [1]

Guruswami, A

V. Guruswami, A. Rudra, and M. Sudan,Essential Coding Theory. Draft is Available, 2022

2022

[2] [2]

Frame codes for distributed coded computation,

R. Yosibash and R. Zamir, “Frame codes for distributed coded computation,” in2021 11th International Symposium on Topics in Coding (ISTC), pp. 1–5, 2021

2021

[3] [3]

Polynomial codes: an optimal design for high-dimensional coded matrix multiplication,

Q. Yu, M. Maddah-Ali, and S. Avestimehr, “Polynomial codes: an optimal design for high-dimensional coded matrix multiplication,”Advances in Neural Information Processing Systems, vol. 30, 2017

2017

[4] [4]

Lagrange coded computing: Optimal design for resiliency, security, and privacy,

Q. Yu, S. Li, N. Raviv, S. M. M. Kalan, M. Soltanolkotabi, and S. A. Avestimehr, “Lagrange coded computing: Optimal design for resiliency, security, and privacy,” inThe 22nd International Conference on Artificial Intelligence and Statistics, pp. 1215–1225, PMLR, 2019

2019

[5] [5]

Analog error-correcting codes,

R. M. Roth, “Analog error-correcting codes,”IEEE Transactions on Information Theory, vol. 66, no. 7, pp. 4075– 4088, 2020. July 28, 2026 DRAFT 13

2020

[6] [6]

Codedsketch: A coding scheme for distributed computation of approximated matrix multiplication,

T. Jahani-Nezhad and M. A. Maddah-Ali, “Codedsketch: A coding scheme for distributed computation of approximated matrix multiplication,”IEEE Transactions on Information Theory, vol. 67, no. 6, pp. 4185–4196, 2021

2021

[7] [7]

Berrut approximated coded computing: Straggler resistance beyond polynomial computing,

T. Jahani-Nezhad and M. A. Maddah-Ali, “Berrut approximated coded computing: Straggler resistance beyond polynomial computing,”IEEETransactionsonPatternAnalysisandMachineIntelligence, vol. 45, no. 1, pp. 111– 122, 2023

2023

[8] [8]

Bitcoin: A peer-to-peer electronic cash system,

N. S. Bitcoin, “Bitcoin: A peer-to-peer electronic cash system,” 2008

2008

[9] [9]

Ethereum white paper,

V. Buterinet al., “Ethereum white paper,”GitHub repository, vol. 1, pp. 22–23, 2013

2013

[10] [10]

Blockchains cannot rely on honesty,

J. Sliwinski and R. Wattenhofer, “Blockchains cannot rely on honesty,” inThe 19th International Conference on Autonomous Agents and Multiagent Systems (AAMAS 2020), 2019

2020

[11] [11]

Fact and fiction: Challenging the honest majority assumption of permissionless blockchains,

R. Han, Z. Sui, J. Yu, J. Liu, and S. Chen, “Fact and fiction: Challenging the honest majority assumption of permissionless blockchains,” inProceedings of the 2021 ACM Asia Conference on Computer and Communications Security, pp. 817–831, 2021

2021

[12] [12]

"Zero Cost

J. S. Gans and H. Halaburda, “"Zero Cost" majority attacks on permissionless blockchains,” tech. rep., National Bureau of Economic Research, 2023

2023

[13] [13]

Proofs, arguments, and zero-knowledge,

J. Thaler, “Proofs, arguments, and zero-knowledge,”Foundations and Trends®in Privacy and Security, vol. 4, no. 2–4, pp. 117–660, 2022

2022

[14] [14]

ZEN: An optimizing compiler for verifiable, zero-knowledge neural network inferences,

B. Feng, L. Qin, Z. Zhang, Y. Ding, and S. Chu, “ZEN: An optimizing compiler for verifiable, zero-knowledge neural network inferences,”Cryptology ePrint Archive, 2021

2021

[15] [15]

ZkCNN: Zero knowledge proofs for convolutional neural network predictions and accuracy,

T. Liu, X. Xie, and Y. Zhang, “ZkCNN: Zero knowledge proofs for convolutional neural network predictions and accuracy,” inProceedings of the 2021 ACM SIGSAC Conference on Computer and Communications Security, pp. 2968–2985, 2021

2021

[16] [16]

Zero-knowledge proof meets machine learning in verifiability: A survey,

Z. Xing, Z. Zhang, J. Liu, Z. Zhang, M. Li, L. Zhu, and G. Russello, “Zero-knowledge proof meets machine learning in verifiability: A survey,”arXiv preprint arXiv:2310.14848, 2023

Pith/arXiv arXiv 2023

[17] [17]

SecureML: A system for scalable privacy-preserving machine learning,

P. Mohassel and Y. Zhang, “SecureML: A system for scalable privacy-preserving machine learning,” in2017 IEEE symposium on security and privacy (SP), pp. 19–38, IEEE, 2017

2017

[18] [18]

vCNN: Verifiable convolutional neural network based on zk-snarks,

S. Lee, H. Ko, J. Kim, and H. Oh, “vCNN: Verifiable convolutional neural network based on zk-snarks,”IEEE Transactions on Dependable and Secure Computing, 2024

2024

[19] [19]

Mystique: Efficient conversions for{Zero-Knowledge}proofs with applications to machine learning,

C. Weng, K. Yang, X. Xie, J. Katz, and X. Wang, “Mystique: Efficient conversions for{Zero-Knowledge}proofs with applications to machine learning,” in30th USENIX Security Symposium (USENIX Security 21), pp. 501– 518, 2021

2021

[20] [20]

Interactive proofs for rounding arithmetic,

S. Chen, J. H. Cheon, D. Kim, and D. Park, “Interactive proofs for rounding arithmetic,”IEEE Access, vol. 10, pp. 122706–122725, 2022

2022

[21] [21]

Succinct zero knowledge for floating point computations,

S. Garg, A. Jain, Z. Jin, and Y. Zhang, “Succinct zero knowledge for floating point computations,” inProceedings of the 2022 ACM SIGSAC Conference on Computer and Communications Security, pp. 1203–1216, 2022

2022

[22] [22]

Taking{Proof-Based}verified computation a few steps closer to practicality,

S. Setty, V. Vu, N. Panpalia, B. Braun, A. J. Blumberg, and M. Walfish, “Taking{Proof-Based}verified computation a few steps closer to practicality,” in21st USENIX Security Symposium (USENIX Security 12), pp. 253–268, 2012

2012

[23] [23]

Experimenting with zero-knowledge proofs of training,

S. Garg, A. Goel, S. Jha, S. Mahloujifar, M. Mahmoody, G.-V. Policharla, and M. Wang, “Experimenting with zero-knowledge proofs of training,”Cryptology ePrint Archive, 2023. July 28, 2026 DRAFT 14

2023

[24] [24]

Game of coding: Beyond honest-majority assumptions,

H. A. Nodehi, V. R. Cadambe, and M. A. Maddah-Ali, “Game of coding: Beyond honest-majority assumptions,” IEEE Transactions on Information Theory (submitted), 2024

2024

[25] [25]

Game of coding: Sybil resistant decentralized machine learning with minimal trust assumption,

H. A. Nodehi, V. R. Cadambe, and M. A. Maddah-Al, “Game of coding: Sybil resistant decentralized machine learning with minimal trust assumption,”arXiv preprint, 2024. https://arxiv.org/abs/2410.05540

arXiv 2024

[26] [26]

Game of coding for vector-valued computations,

H. A. Nodehi, P. Moradi, S. Mohajer, and M. A. Maddah-Ali, “Game of coding for vector-valued computations,” arXiv preprint arXiv:2602.04810, 2026

Pith/arXiv arXiv 2026

[27] [27]

\mathsf{VISTA}:Decentralizedmachinelearning in adversary dominated environments,

H.A.Nodehi,P.Moradi,S.Mohajer,andM.A.Maddah-Ali,“\mathsf{VISTA}:Decentralizedmachinelearning in adversary dominated environments,”arXiv preprint arXiv:2605.07841, 2026

Pith/arXiv arXiv 2026

[28] [28]

Game of coding with an unknown adversary,

H. Akbari Nodehi, P. Moradi, and M. A. Maddah-Ali, “Game of coding with an unknown adversary,” in2025 IEEE International Symposium on Information Theory (ISIT), (Ann Arbor, MI, USA), 2025

2025

[29] [29]

Learning from acceptance: Cumulative regret in the game of coding,

H. Akbari Nodehi, P. Moradi, and M. A. Maddah-Ali, “Learning from acceptance: Cumulative regret in the game of coding,”arXiv e-prints, pp. arXiv–2605, 2026

2026

[30] [30]

Game of coding: Coding theory in the presence of rational adversaries, motivated by decentralized machine learning,

H. A. Nodehi, V. R. Cadambe, and M. A. Maddah-Ali, “Game of coding: Coding theory in the presence of rational adversaries, motivated by decentralized machine learning,”arXiv preprint arXiv:2601.02313, 2026

arXiv 2026

[31] [31]

Intriguing properties of neural networks,

C. Szegedy, W. Zaremba, I. Sutskever, J. Bruna, D. Erhan, I. Goodfellow, and R. Fergus, “Intriguing properties of neural networks,” inInternational Conference on Learning Representations, 2014

2014

[32] [32]

Explaining and harnessing adversarial examples,

I. J. Goodfellow, J. Shlens, and C. Szegedy, “Explaining and harnessing adversarial examples,” inInternational Conference on Learning Representations, 2015

2015

[33] [33]

Towards deep learning models resistant to adversarial attacks,

A. Madry, A. Makelov, L. Schmidt, D. Tsipras, and A. Vladu, “Towards deep learning models resistant to adversarial attacks,” inInternational Conference on Learning Representations, 2018

2018

[34] [34]

Towards evaluating the robustness of neural networks,

N. Carlini and D. Wagner, “Towards evaluating the robustness of neural networks,” in2017 IEEE Symposium on Security and Privacy, pp. 39–57, IEEE, 2017

2017

[35] [35]

Analyzing federated learning through an adversarial lens,

A. N. Bhagoji, S. Chakraborty, P. Mittal, and S. Calo, “Analyzing federated learning through an adversarial lens,” inProceedings of the 36th International Conference on Machine Learning, vol. 97 ofProceedings of Machine Learning Research, pp. 634–643, PMLR, 2019

2019

[36] [36]

A little is enough: Circumventing defenses for distributed learning,

M. Baruch, G. Baruch, and Y. Goldberg, “A little is enough: Circumventing defenses for distributed learning,” inAdvances in Neural Information Processing Systems, vol. 32, Curran Associates, Inc., 2019

2019

[37] [37]

How to backdoor federated learning,

E. Bagdasaryan, A. Veit, Y. Hua, D. Estrin, and V. Shmatikov, “How to backdoor federated learning,” in Proceedings of the Twenty Third International Conference on Artificial Intelligence and Statistics, vol. 108 of Proceedings of Machine Learning Research, pp. 2938–2948, PMLR, 2020

2020

[38] [38]

Local model poisoning attacks to Byzantine-Robust federated learning,

M. Fang, X. Cao, J. Jia, and N. Gong, “Local model poisoning attacks to Byzantine-Robust federated learning,” in29th USENIX Security Symposium (USENIX Security 20), pp. 1605–1622, USENIX Association, August 2020

2020

[39] [39]

Von Stackelberg,Market structure and equilibrium

H. Von Stackelberg,Market structure and equilibrium. Springer Science & Business Media, 2010. Appendix A Relationship with Previous Game-of-Coding Models In this appendix, we show that the acceptance and estimation mechanism defined in (10)–(15) provides a common generalization of the mechanisms considered in the previous game-of-coding papers [24]–[26]. ...

2010

[40] [40]

This completes the proof

Equation (71) proves (63). This completes the proof. We are now ready to prove Theorem 1. Proof of Theorem 1.Consider an arbitrary input-dependent adversarial strategy g∈Λ dep AD (t).(72) Let gand gbe defined according to (23) and (24), respectively. Lemma 1 establishes thatgis a valid joint PDF and that g∈Λ ind AD(t).(73) We next prove equality of the pr...

2026