pith. sign in

arxiv: 2602.04810 · v2 · submitted 2026-02-04 · 💻 cs.IT · math.IT

Game of Coding for Vector-Valued Computations

Hanzaleh Akbari Nodehi , Parsa Moradi , Soheil Mohajer , Mohammad Ali Maddah-Ali This is my paper

Pith reviewed 2026-05-16 06:52 UTC · model grok-4.3

classification 💻 cs.IT math.IT
keywords game of codingvector-valued computationrational adversarydecentralized machine learningequilibrium strategiesrepetition codesinformation theory
0
0 comments X

The pith

In vector computations such as gradients, a two-repetition coding game with at least one rational adversary fully characterizes the equilibrium where reliable decoding holds.

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

The paper extends the game-of-coding framework from scalars to vectors in Euclidean space to handle decentralized machine learning tasks. It focuses on the two-repetition code case where at least one node is controlled by a rational adversary and determines the exact equilibrium points together with the optimal strategies for every player. A sympathetic reader would care because most machine learning outputs are vectors and permissionless volunteer networks require incentives that deter manipulation even when adversaries form a majority. The characterization shows that rational reward-seeking behavior can be aligned to produce honest decoding outcomes under the given payoff structure.

Core claim

For a two-repetition code in multi-dimensional Euclidean space with at least one rational adversary, the equilibrium and optimal strategies of the players are fully characterized, guaranteeing reliable decoding despite the possibility of an adversarial majority.

What carries the argument

The two-repetition code whose equilibrium analysis in vector space determines the strategies that align rational players with honest decoding.

If this is right

  • Reliable decoding remains possible for vector outputs even when adversaries outnumber honest nodes.
  • The equilibrium strategies provide a concrete foundation for constructing codes that handle higher-dimensional computations.
  • Decentralized machine learning systems can assign payments according to the derived optimal strategies to enforce honest behavior.
  • The scalar-case results generalize directly once the vector equilibrium is known.
  • More complex repetition schemes can be built by treating the two-repetition equilibrium as a primitive.

Where Pith is reading between the lines

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

  • The same equilibrium techniques might apply to other vector operations such as matrix multiplications or embeddings in distributed training.
  • If node utilities become private information, additional incentive layers would be needed to restore the known-utility equilibrium.
  • Permissionless networks outside machine learning, such as distributed scientific computing, could adopt the repetition-plus-equilibrium template once utilities are aligned.
  • Testing the predicted strategies in a small-scale volunteer network would reveal whether real-world rationality assumptions hold.

Load-bearing premise

Players are rational reward-seekers whose utilities are known in advance and the two-repetition structure alone suffices to deter adversarial behavior.

What would settle it

An explicit counter-example in which a rational adversary chooses a strategy outside the characterized equilibrium set yet receives strictly higher expected reward than the equilibrium payoff.

Figures

Figures reproduced from arXiv: 2602.04810 by Hanzaleh Akbari Nodehi, Mohammad Ali Maddah-Ali, Parsa Moradi, Soheil Mohajer.

Figure 1
Figure 1. Figure 1: System model for the N-Dimensional game of coding. The network consists of one honest node and one adversarial node. Each node reports a noisy version of the ground truth U to the DC. For the honest node, the noise Nh is uniformly distributed within BN (∆), while for the adversarial node, the noise Na follows an arbitrary distribution g(·) chosen by the adversary. Upon receiving the data, the DC decides wh… view at source ↗
Figure 2
Figure 2. Figure 2: The Pareto frontier cη(α) and adversarial rationality. Point A (red) is inefficient compared to point B (black), while Point C (gray) lies in the unattainable region beyond the maximum possible error for α1. Algorithm 1 Determination of the Optimal Threshold η ∗ 1: Input: Utility functions UAD(·, ·), UDC(·, ·), and the function {cη(·) : η ∈ ΛDC}. 2: Output: Optimal threshold ηˆ. 3: Step 1: Follower’s Ratio… view at source ↗
Figure 3
Figure 3. Figure 3: Geometric proof of Lemma 1. Point A represents a suboptimal response where [PITH_FULL_IMAGE:figures/full_fig_p020_3.png] view at source ↗
Figure 4
Figure 4. Figure 4: Visual representation of the contradiction for [PITH_FULL_IMAGE:figures/full_fig_p021_4.png] view at source ↗
Figure 5
Figure 5. Figure 5: The honest noise Nh is uniformly distributed on the blue ball of radius ∆. Given any adversarial noise na with magnitude z, the condition ∥Nh − na∥2 ≤ η∆ is satisfied if Nh falls within the red ball. Due to spherical symmetry, the conditional probability Pr(Aη | Z = z) depends only on the scalar distance z. Mean Squared Error (MSE) in terms of the adversarial noise distribution gNa (na), and ideally show t… view at source ↗
Figure 6
Figure 6. Figure 6: A sample potential function Ψ˜ N (q) and its upper concave envelope Ψ˜ ∗ N (q). Over the interval [0, q1], the concave envelope is defined by the linear chord connecting points A and B, while for q ∈ [q1, 1], the envelope coincides with the function itself. To achieve the upper bound in (87), for the case of α1, we use a noise distribution uniformly distributed over the surface of an N-sphere with radius z… view at source ↗
Figure 7
Figure 7. Figure 7: Characteristic curves cη(α) defined in (19), for N = 2 and ∆ = 1 (Example 1). Each curve corresponds to a specific threshold η ∈ [2, 8], mapping the acceptance probability α (x-axis) to the maximum enforceable MSE (y-axis). The dots (red and black) on each curve represent the adversary’s best response operating point (PA∗ , MSE∗ ) for that specific η, and the utility function of the adversary defined in (1… view at source ↗
Figure 8
Figure 8. Figure 8: Equilibrium analysis for N = 25 with η ∈ [2.0, 8.0] (Example 2). The curves represent the characteristic functions cη(α). The red dots indicate the adversary’s best response for each η, with respect to the utility function of the adversary, defined in (107). The black dot marks the equilibrium for DC Case 1 (108), at η ∗ = 4.0. The green dot marks the equilibrium for DC Case 2 (109), at η ∗ = 2.0. Numerica… view at source ↗
Figure 9
Figure 9. Figure 9: April 13, 2026 DRAFT [PITH_FULL_IMAGE:figures/full_fig_p037_9.png] view at source ↗
Figure 9
Figure 9. Figure 9: Equilibrium analysis for N = 250 with η ∈ [2.0, 8.0] (Example 3). The curves represent the characteristic functions cη(α). The red dots indicate the adversary’s best response for each η maximizing (115). The black dot highlights the global Stackelberg equilibrium where the DC’s utility (116) is maximized. To determine the equilibrium, the DC evaluates its utility (116) across the set of induced operating p… view at source ↗
Figure 10
Figure 10. Figure 10: Decomposition of the N-ball volume into infinitesimal spherical shells. The integral sums the contributions of shells with radius ρ and thickness dρ from the center to the boundary r. Consequently, the differential volume element of a shell at radius ρ is du = AN−1(ρ) dρ = NCN ρ N−1 dρ. (122) Since the squared magnitude ∥u∥ 2 2 = ρ 2 is constant on a spherical shell of radius ρ, the integral becomes M2(N,… view at source ↗
Figure 11
Figure 11. Figure 11: Illustration of a hyperspherical cap (shown in 2D). The cap is decomposed into infinitesimal slices. Each [PITH_FULL_IMAGE:figures/full_fig_p046_11.png] view at source ↗
Figure 12
Figure 12. Figure 12: Geometry of the shifted, left-oriented hyperspherical cap [PITH_FULL_IMAGE:figures/full_fig_p049_12.png] view at source ↗
Figure 13
Figure 13. Figure 13: Sub-case 3a: Both centers are outside the intersection, resulting in [PITH_FULL_IMAGE:figures/full_fig_p052_13.png] view at source ↗
Figure 14
Figure 14. Figure 14: Sub-case 3b: Center o2 is inside the intersection, resulting in c (2) 1 − c (2) 2 = d. 3) Aggregation of Cases: We observe that (170) and (173) can be unified into a single expression by allowing c2 to be a signed distance. If we define c2 = d 2+r 2 2−r 2 1 2d as in (169), then in Case 3b, c2 becomes naturally negative (c2 = −c (2) 2 ). Thus, for all configurations of partial overlap, we have V (r1, r2, d… view at source ↗
Figure 15
Figure 15. Figure 15: Cross-sectional decomposition of the N-dimensional intersection region Rlens(na). The vertical line at nh,1 = uc represents the radical hyperplane, which divides the volume into standard cap R1 and shifted cap R2. Before calculating I1 and I2, we analyze the geometry of the integration domain. As discussed in Appendix C-C, the integration domain Rlens(na) comprises of two hyperspherical caps, obtained by … view at source ↗
Figure 16
Figure 16. Figure 16: Visualization of an initial adversarial noise density [PITH_FULL_IMAGE:figures/full_fig_p062_16.png] view at source ↗
Figure 17
Figure 17. Figure 17: Intermediate distribution f1(z) following the truncation and renormalization process defined in (219). By removing the tail mass Ptail and scaling the remaining density, the probability of acceptance is increased according to (220) while the conditional MSE remains constant. Using Lemma 2, the acceptance probability for f1(z) is Pr(Aη; f1) = Z ∞ 0 ΦN (z)f1(z) dz (a) = 1 1 − Ptail Z (η+1)∆ 0 ΦN (z)fZ(z) dz… view at source ↗
Figure 18
Figure 18. Figure 18: Final optimal distribution f ∗ Z (z) (illustrating the construction in (224)). All mass from the region z < (η−1)∆ is concentrated at the boundary point (η − 1)∆. This shift maximizes the conditional MSE, without decreasing the probability of acceptance. First, we analyze the acceptance probability. We have Pr(Aη; f ∗ Z) = Z ∞ 0 ΦN (z)f ∗ Z(z) dz (a) = PheadΦN ((η − 1)∆) + Z (η+1)∆ (η−1)∆ ΦN (z)f1(z) dz (… view at source ↗
Figure 19
Figure 19. Figure 19: z fZ,1(z) (η − 1)∆ (η + 1)∆ S1 Area(S1) = 1 Pr(Aη; fZ,1) = α1 > α [PITH_FULL_IMAGE:figures/full_fig_p066_19.png] view at source ↗
Figure 20
Figure 20. Figure 20: The adjusted distribution fZ,2(z). The original mass is scaled down to exactly α (e.g., 2/3). The discarded mass (e.g., 1/3) is concentrated into a Dirac delta at the boundary zout = (η + 1)∆, ensuring the total integral is 1 while the acceptance probability is exactly α. First, we calculate the probability of acceptance for the new distribution using (65). Noting that ΦN (·) is a continuous function and … view at source ↗
read the original abstract

Traditional coding theory guarantees valid decoding only if a minority of symbols are adversarially manipulated. In contrast, the game of coding framework ensures reliable decoding, even in the presence of an adversarial majority. This formulation is motivated by emerging permissionless applications, particularly decentralized machine learning (DeML), where computation tasks are outsourced to external volunteer nodes that are predominantly rational and reward-seeking. Prior investigations have analyzed the game of coding in the scalar setting. Since the results of most major computations in machine learning are vectors (e.g., computing the gradient of the loss for a machine learning model), we extend the framework in this paper to the general multi-dimensional Euclidean space. As a first, yet fundamental step, in this paper, we study a two-repetition code in which at least one node is controlled by a rational adversary, and we fully characterize the equilibrium and the optimal strategies of the players. Similar to the scalar case, this result serves as a cornerstone for addressing more general scenarios.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

2 major / 2 minor

Summary. The manuscript extends the game-of-coding framework to vector-valued computations in Euclidean space. It focuses on the two-repetition code in which at least one node is controlled by a rational adversary and claims to fully characterize the Nash equilibria together with the players' optimal strategies, inheriting the scalar-case detection rule and utility functions as a cornerstone for more general repetition codes.

Significance. A correct characterization would supply a concrete foundation for reliable vector computations (e.g., gradients) under rational adversaries in permissionless settings such as decentralized machine learning. The work correctly identifies the move from scalars to vectors as the next necessary step after prior scalar results.

major comments (2)
  1. [§4] §4 (Equilibrium Characterization) and the main theorem: the claimed full characterization inherits the scalar detection rule (comparison of the two received vectors) and the associated Euclidean-distance penalty without an explicit argument that this rule remains dominant once orthogonal perturbations are admitted. For any honest vector v ∈ ℝ^d (d>1) an adversary can send v + εu with u ⊥ v and ||u||=1; the Euclidean distance remains ε while the component-wise or projected penalty inherited from the scalar utilities may be zero. No equation or lemma in the provided characterization shows that all such deviations are rendered unprofitable.
  2. [§3.2] §3.2 (Model and Utility Functions): the utility functions are stated to be the same as in the scalar case, yet the manuscript does not derive or verify that the resulting best-response correspondence continues to exclude profitable orthogonal deviations. This assumption is load-bearing for the central claim that the two-repetition structure suffices in Euclidean space.
minor comments (2)
  1. Notation: vector quantities should be consistently bold-faced or arrowed throughout; the current mixed usage makes it difficult to track when a quantity is scalar versus vector-valued.
  2. [Conclusion] The abstract states that the result 'serves as a cornerstone'; a short forward-looking paragraph in the conclusion outlining the precise next technical obstacle (e.g., three-repetition or general linear codes) would improve readability.

Simulated Author's Rebuttal

2 responses · 0 unresolved

We thank the referee for the constructive comments on the transition from the scalar to the vector setting. The points raised highlight the need for explicit verification that the inherited utilities and detection rule remain dominant under orthogonal perturbations. We address each comment below and will revise the manuscript accordingly.

read point-by-point responses

  1. Referee: [§4] §4 (Equilibrium Characterization) and the main theorem: the claimed full characterization inherits the scalar detection rule (comparison of the two received vectors) and the associated Euclidean-distance penalty without an explicit argument that this rule remains dominant once orthogonal perturbations are admitted. For any honest vector v ∈ ℝ^d (d>1) an adversary can send v + εu with u ⊥ v and ||u||=1; the Euclidean distance remains ε while the component-wise or projected penalty inherited from the scalar utilities may be zero. No equation or lemma in the provided characterization shows that all such deviations are rendered unprofitable.

    Authors: We agree that an explicit argument is required. In the manuscript the utility is defined directly via the Euclidean norm of the difference between the two received vectors, so the penalty depends only on the magnitude of any deviation and is invariant to its direction. An orthogonal perturbation of norm ε therefore produces exactly the same utility as an aligned perturbation of the same norm. We will add a short lemma (new Lemma 4.1) immediately before the main theorem that proves this invariance: for any deviation δ with ||δ|| = ε the utility equals the scalar-case value regardless of the angle between δ and v. This establishes that no orthogonal deviation is more profitable and that the Nash characterization carries over unchanged. We also clarify that the formulation uses the full-vector Euclidean norm rather than any component-wise or projected scalar penalties. revision: yes

  2. Referee: [§3.2] §3.2 (Model and Utility Functions): the utility functions are stated to be the same as in the scalar case, yet the manuscript does not derive or verify that the resulting best-response correspondence continues to exclude profitable orthogonal deviations. This assumption is load-bearing for the central claim that the two-repetition structure suffices in Euclidean space.

    Authors: We acknowledge that §3.2 would benefit from an explicit derivation. We will expand this section to derive the best-response correspondence for the vector case, showing that it is identical to the scalar case once distances are measured by the Euclidean norm. Because the norm is rotationally invariant, any deviation vector of a given length yields the same utility irrespective of its direction relative to the honest vector. A brief verification will be inserted demonstrating that the best responses therefore exclude all profitable orthogonal deviations and that the two-repetition structure remains sufficient in Euclidean space. revision: yes

Circularity Check

0 steps flagged

No circularity: vector equilibrium characterization is a direct game-theoretic derivation

full rationale

The paper performs a first-principles characterization of Nash equilibria and optimal strategies for the two-repetition code in Euclidean space when at least one node is a rational adversary. This is presented as an extension of the scalar setting without any fitted parameters, self-definitional loops, or reductions where a 'prediction' is forced by construction from the inputs. The abstract and described approach treat the vector case as a new analysis whose validity rests on the explicit game rules and rationality assumptions rather than inheriting a scalar result by tautology or unverified self-citation. No load-bearing step collapses to a prior ansatz or renaming of known patterns; the derivation remains self-contained.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 0 invented entities

The framework rests on the domain assumption that nodes are rational reward-seekers; no free parameters or invented entities are mentioned in the abstract.

axioms (1)
  • domain assumption Nodes are rational and reward-seeking
    Explicitly stated as motivation for permissionless DeML applications.

pith-pipeline@v0.9.0 · 5479 in / 1028 out tokens · 28030 ms · 2026-05-16T06:52:38.194251+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Forward citations

Cited by 2 Pith papers

Reviewed papers in the Pith corpus that reference this work. Sorted by Pith novelty score.

  1. Learning from Acceptance: Cumulative Regret in the Game of Coding

    cs.IT 2026-05 unverdicted novelty 7.0

    A new algorithm for the incomplete-information game of coding learns adversary preferences through repeated interactions and achieves sublinear cumulative regret by focusing search on promising acceptance rules.

  2. \mathsf{VISTA}: Decentralized Machine Learning in Adversary Dominated Environments

    cs.LG 2026-05 unverdicted novelty 6.0

    VISTA adaptively tunes consistency thresholds in decentralized SGD so that the system converges asymptotically like standard SGD even when adversaries dominate the worker pool.

Reference graph

Works this paper leans on

49 extracted references · 49 canonical work pages · cited by 2 Pith papers

  1. [1]

    Guruswami, A

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

    work page 2022

  2. [2]

    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

    work page 2019

  3. [3]

    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

    work page 2021

  4. [4]

    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

    work page 2021

  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

    work page 2020

  6. [6]

    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

    work page 2023

  7. [7]

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

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

    work page 2008

  8. [8]

    Ethereum white paper,

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

    work page 2013

  9. [9]

    SoK: Blockchain technology and its potential use cases,

    S. Ruoti, B. Kaiser, A. Yerukhimovich, J. Clark, and R. Cunningham, “SoK: Blockchain technology and its potential use cases,”arXiv preprint arXiv:1909.12454, 2019

    work page arXiv 1909

  10. [10]

    Blockchain for deep learning: review and open challenges,

    M. Shafay, R. W. Ahmad, K. Salah, I. Yaqoob, R. Jayaraman, and M. Omar, “Blockchain for deep learning: review and open challenges,”Cluster Computing, vol. 26, no. 1, pp. 197–221, 2023

    work page 2023

  11. [11]

    Survey on the convergence of machine learning and blockchain,

    S. Ding and C. Hu, “Survey on the convergence of machine learning and blockchain,” inProceedings of SAI Intelligent Systems Conference, pp. 170–189, Springer, 2022. April 13, 2026 DRAFT 41

    work page 2022

  12. [12]

    Blockchain meets machine learning: a survey,

    S. Kayikci and T. M. Khoshgoftaar, “Blockchain meets machine learning: a survey,”Journal of Big Data, vol. 11, no. 1, pp. 1–29, 2024

    work page 2024

  13. [13]

    Blockchain and machine learning: A critical review on security,

    H. Taherdoost, “Blockchain and machine learning: A critical review on security,”Information, vol. 14, no. 5, p. 295, 2023

    work page 2023

  14. [14]

    Blockchain technology and artificial intelligence together: a critical review on applications,

    H. Taherdoost, “Blockchain technology and artificial intelligence together: a critical review on applications,” Applied Sciences, vol. 12, no. 24, p. 12948, 2022

    work page 2022

  15. [15]

    Blockchain for ai: A disruptive integration,

    R. Tian, L. Kong, X. Min, and Y. Qu, “Blockchain for ai: A disruptive integration,” in2022 IEEE 25th International Conference on Computer Supported Cooperative Work in Design (CSCWD), pp. 938–943, IEEE, 2022

    work page 2022

  16. [16]

    Blockchain for ai: Review and open research challenges,

    K. Salah, M. H. U. Rehman, N. Nizamuddin, and A. Al-Fuqaha, “Blockchain for ai: Review and open research challenges,”IEEE Access, vol. 7, pp. 10127–10149, 2019

    work page 2019

  17. [17]

    VeriML: Enabling integrity assurances and fair payments for machine learning as a service,

    L. Zhao, Q. Wang, C. Wang, Q. Li, C. Shen, and B. Feng, “VeriML: Enabling integrity assurances and fair payments for machine learning as a service,”IEEE Transactions on Parallel and Distributed Systems, vol. 32, no. 10, pp. 2524–2540, 2021

    work page 2021

  18. [18]

    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

    work page 2024

  19. [19]

    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

    work page arXiv 2024

  20. [20]

    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

    work page 2025

  21. [21]

    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

    work page arXiv 2026

  22. [22]

    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

    work page 2022

  23. [23]

    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

    work page 2021

  24. [24]

    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

    work page 2021

  25. [25]

    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

    work page arXiv 2023

  26. [26]

    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

    work page 2017

  27. [27]

    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

    work page 2024

  28. [28]

    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

    work page 2021

  29. [29]

    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. April 13, 2026 DRAFT 42

    work page 2022

  30. [30]

    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

    work page 2022

  31. [31]

    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

    work page 2012

  32. [32]

    Sakshi: Decentralized ai platforms,

    S. Bhat, C. Chen, Z. Cheng, Z. Fang, A. Hebbar, S. Kannan, R. Rana, P. Sheng, H. Tyagi, P. Viswanath,et al., “Sakshi: Decentralized ai platforms,”arXiv preprint arXiv:2307.16562, 2023

    work page arXiv 2023

  33. [33]

    opml: Optimistic machine learning on blockchain,

    K. Conway, C. So, X. Yu, and K. Wong, “opml: Optimistic machine learning on blockchain,”arXiv preprint arXiv:2401.17555, 2024

    work page arXiv 2024

  34. [34]

    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

    work page 2017

  35. [35]

    SoK: Oracles from the ground truth to market manipulation,

    S. Eskandari, M. Salehi, W. C. Gu, and J. Clark, “SoK: Oracles from the ground truth to market manipulation,” inProceedings of the 3rd ACM Conference on Advances in Financial Technologies, pp. 127–141, 2021

    work page 2021

  36. [36]

    Chainlink 2.0: Next steps in the evolution of decentralized oracle networks,

    L. Breidenbach, C. Cachin, B. Chan, A. Coventry, S. Ellis, A. Juels, F. Koushanfar, A. Miller, B. Magauran, D. Moroz,et al., “Chainlink 2.0: Next steps in the evolution of decentralized oracle networks,”Chainlink Labs, vol. 1, pp. 1–136, 2021

    work page 2021

  37. [37]

    Decentralized APIs for web 3.0,

    B. Benligiray, S. Milic, and H. Vänttinen, “Decentralized APIs for web 3.0,”API3 Foundation Whitepaper, 2020

    work page 2020

  38. [38]

    Von Stackelberg,Market structure and equilibrium

    H. Von Stackelberg,Market structure and equilibrium. Springer Science & Business Media, 2010. Appendix A Hypersphere: The Second Moment of anN-Ball In this section, we derive the general formula for the second moment (polar moment of inertia) of anN-dimensional ball with uniform density. LetB(N,r)denote anN-ball of radiusrcentered at the origin inRN, and ...

    work page 2010

  39. [39]

    The volume of this(N−1)-ball is given byVN−1 (√ r2−x2 1 ) . A. Derivation of the Hyperspherical Cap Volume To compute the volumeKN(r,c), we integrate the volumes of its cross-sections along the axis of symmetryx 1. Consider a slice of the cap at a positionx1 for somec≤x1≤ras shown in Figure 11. April 13, 2026 DRAFT 45 This volume is given by the integral ...

    work page 2026

  40. [40]

    By substituting the(N−1)-dimensional volume formula, we write the total volume as KN(r,c) = ∫ r c VN−1 (√ r2−x2 1 ) dx1.(132) Recall from (3), that the volume of an(N−1)-ball of radiusρis given byVN−1(ρ) =π(N−1)/2 Γ(N+1 2 )ρN−1. Substitutingρ= √ r2−x2 1 into (132) leads to KN(r,c) = π(N−1)/2 Γ( 1 2(N+ 1)) ∫ r c (r2−x2 1) N−1 2 dx1.(133) By performing the ...

    work page 2026

  41. [41]

    By linearity, we split this integral into two integrals, one forx2 1 and another one for∥x∼1∥2

    Substituting this decomposition into the volume integral in (130), we get JN(r,c) = ∫ CN(r,c) ∥x∥2 2dx= ∫ r c [ ∫ ∥x∼1∥2 2≤r2−x2 1 (x2 1 +∥x∼1∥2 2)dx∼1 ] dx1.(141) April 13, 2026 DRAFT 47 We now focus on evaluating the inner integral in (141). By linearity, we split this integral into two integrals, one forx2 1 and another one for∥x∼1∥2

    work page 2026

  42. [42]

    Note that the slice is a ball of dimension k=N−1with radiusa= √ r2−x2

    For the first term, sincex1 is constant with respect tox∼1, we simply have ∫ ∥x∼1∥2 2≤r2−x2 1 x2 1dx∼1=x 2 1 ∫ ∥x∼1∥2 2≤r2−x2 1 1dx∼1=x 2 1VN−1 (√ r2−x2 1 ) .(142) For the second term, the integral ∫ ∥x∼1∥2 2≤r2−x2 1 ∥x∼1∥2 2dx∼1represents the second moment of the slice about its own center, which is studied in Appendix A. Note that the slice is a ball of...

    work page

  43. [43]

    This integral is exactly the volume of the hyperspherical cap, evaluated in (133)

    Hence, applying the general formula derived in (126), i.e., M2(k,a) = k k+2a2Vk(a)fork=N−1anda= √ r2−x2 1, we obtain ∫ ∥x∼1∥2 2≤r2−x2 1 ∥x∼1∥2 2dx∼1= N−1 (N−1) + 2(r2−x2 1)VN−1 (√ r2−x2 1 ) = N−1 N+ 1 (r2−x2 1)VN−1 (√ r2−x2 1 ) .(143) Substituting (142) and (143) back into (141), the integral becomes JN(r,c) = ∫ r c [ x2 1VN−1 (√ r2−x2 1 ) + N−1 N+ 1 (r2−...

    work page 2026

  44. [44]

    Then, we can characterize the two Sub-cases as follows

    work page

  45. [45]

    Our goal is to determinec1 andc 2

    Sub-case 3a: Centers on opposite sides of the hyperplane:Whend 2 ≥r2 1−r2 2, the radical hyperplane lies between the centers. Our goal is to determinec1 andc 2. In this configuration, we have c1 +c 2 =d.(167) Moreover, pluggingyin (165), we get c2 1−r2 1 =c 2 2−r2 2.(168) Solving (167) and (168) forc1 andc 2, we arrive at c(1) 1 = d2 +r 2 1−r2 2 2d , c (1...

    work page 2026

  46. [46]

    Sub-case 3b: Centers on the same side of the hyperplane:Whend 2 < r2 1−r2 2, the radical hyperplane lies to the right of both centers. Therefore, we have c1−c2 =d.(171) Solving this equation together with (168) forc1 andc 2, leads to c(2) 1 = d2 +r 2 1−r2 2 2d , c (2) 2 = r2 1−r2 2−d2 2d .(172) As illustrated in Figure 14, in this case, for the intersecti...

    work page

  47. [47]

    If we definec2 = d2+r2 2−r2 1 2d as in (169), then in Case 3b,c2 becomes naturally negative (c2 =−c(2) 2 )

    Aggregation of Cases:We observe that (170) and (173) can be unified into a single expression by allowingc 2 to be a signed distance. If we definec2 = d2+r2 2−r2 1 2d as in (169), then in Case 3b,c2 becomes naturally negative (c2 =−c(2) 2 ). Thus, for all configurations of partial overlap, we have V(r 1,r 2,d) =K N(r1,c 1) +KN(r2,c 2),(174) April 13, 2026 ...

    work page 2026

  48. [48]

    = 1/2 Fig. 17. Intermediate distributionf 1(z)following the truncation and renormalization process defined in (219). By removing the tail massPtail and scaling the remaining density, the probability of acceptance is increased according to (220) while the conditional MSE remains constant. Using Lemma 2, the acceptance probability forf1(z)is Pr(Aη;f 1) = ∫ ...

    work page 2026

  49. [49]

    = 1/2 Fig. 18. Final optimal distributionf∗ Z(z)(illustrating the construction in (224)). All mass from the regionz <(η−1)∆ is concentrated at the boundary point(η−1)∆. This shift maximizes the conditional MSE, without decreasing the probability of acceptance. First, we analyze the acceptance probability. We have Pr(Aη;f∗ Z) = ∫ ∞ 0 ΦN(z)f∗ Z(z)dz (a) =P ...

    work page 2026