A polynomial proxy model approach to verifiable decentralized federated learning Authors: Tan Li, Samuel Cheng, Tak Lam Chan, Haibo Hu Published: 2024 ABSTRACT Decentralized Federated Learning improves data privacy and eliminates single points of failure by removing reliance on centralized storage and model aggregation in distributed computing systems. Ensuring the integrity of computations during local model training is a significant challenge, especially before sharing gradient updates from each local client. Current methods for ensuring computation integrity often involve patching local models to implement cryptographic techniques, such as Zero-Knowledge Proofs. However, this approach becomes highly complex and sometimes impractical for large-scale models that use techniques such as random dropouts to improve training convergence. These random dropouts create non-deterministic behavior, making it challenging to verify model updates under deterministic protocols. We propose ProxyZKP, a novel framework combining Zero-Knowledge Proofs with polynomial proxy models to provide computation integrity in local training to address this issue. Each local node combines a private model for online deep learning applications and a proxy model that mediates decentralized model training by exchanging gradient updates. The multivariate polynomial nature of proxy models facilitates the application of Zero-Knowledge Proofs. These proofs verify the computation integrity of updates from each node without disclosing private data. Experimental results indicate that ProxyZKP significantly reduces computational load. Specifically, ProxyZKP achieves proof generation times that are 30–50% faster compared to established methods like zk-SNARKs and Bulletproofs. This improvement is largely due to the high parallelization potential of the univariate polynomial decomposition approach. Additionally, integrating Differential Privacy into the ProxyZKP framework reduces the risk of Gradient Inversion attacks by adding calibrated noise to the gradients, while maintaining competitive model accuracy. The results demonstrate that ProxyZKP is a scalable and efficient solution for ensuring training integrity in decentralized federated learning environments, particularly in scenarios with frequent model updates and the need for strong model scalability. Introduction Federated Learning (FL)1 has revolutionized machine learning by moving away from centralized data processing to decentralized methods, enhancing data privacy, and reducing dependence on centralized data storage. Google researchers initially developed FL, allowing client devices to perform local computations on model updates, which a central server then aggregates. While FL preserves user privacy by keeping data local, it faces significant challenges in multi-institutional collaborations, particularly in sectors such as healthcare, where stringent security standards are mandatory. These problems mostly come from the fact that it relies on a single authority, which leaves it open to problems like a single point of failure and not enough ways to check that model gradient transfers are being done correctly. To overcome these limitations, there is growing adoption of decentralized learning platforms2,3 because the role of the central aggregator is not required. Therefore, these vulnerabilities can be diminished. However, decentralized architectures4,5 introduce new complexities in verifying the integrity of model updates without compromising privacy. Advanced cryptographic techniques, like Zero-Knowledge Proof (ZKP)6,7 which allows one party to prove the correctness of a statement without revealing any additional information, offer a promising solution to these challenges by enabling secure verification of model updates at each local node8,9 in a decentralized learning environment. However, conventional ZKP approaches, which often include intricate structures like Rank-1 Constrained System (R1CS) and Quadratic Arithmetic Programs (QAP)10,11, are challenging to implement on large-scale models. Moreover, random elements such as dropouts during model training, which contradict the deterministic requirements of ZKP procedures, make it fairly impractical to patch the original model for merging with the ZKP process. This study introduces ProxyZKP, a novel framework that integrates Deep Mutual Learning12,13 with ZKP to provide the computation integrity signature in training local models. Each node in decentralized architecture operates with a dual-model setup: a private model for online deployment on local data and a proxy model guided by multivariate polynomial loss function14, providing gradient updates during federated model training. Within the framework of Deep Mutual Learning, the proxy model is linked to the private models to maintain consistency and alignment. The ZKP is used to verify the integrity of the computation on the proxy model’s gradient update before the new gradient is exchanged among decentralized peers. ProxyZKP accomplishes training integrity verification of proxy model by efficiently applying Kate Polynomial Commitment15,16 with a two-stage multivariate polynomial decomposition method. Our numerical experiments demonstrate the efficacy of this approach, showing that ProxyZKP delivers the best trade-off among alternative Zero-Knowledge Proof methods like ZK-SNARKs17 and Bulletproofs18 for training integrity verification in decentralized, federated learning models. Additionally, privacy breaches caused by Gradient Inversion19 attacks can be mitigated by implementing an additional defense measure such as Differential Privacy (DP)20,21 after the ZKP process. This involves adding calibrated noise to the gradients, based on a privacy budget (\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\epsilon , \delta$$\end{document}), before using them for federated model training. Our benchmarks show that this method effectively reduces the risk of Gradient Inversion attacks, where attackers can reconstruct original data from gradient updates. Specifically, a lower privacy budget \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$(\epsilon = 0.5)$$\end{document} requires adding significant noise (\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\sigma = 1.5$$\end{document}), resulting in a model accuracy of 60.0% for MLP on the MNIST dataset and 52.3% for CNN on the CIFAR dataset. In contrast, a higher privacy budget (\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\epsilon = 5.0$$\end{document}) reduces the noise level (\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\sigma = 0.5$$\end{document}), leading to an accuracy of 80.1% for MLP and 62.0% for CNN. The results show that ProxyZKP effectively strikes a balance between privacy and utility. It offers strong protection while maintaining high performance of private models. Therefore, it has the potential to address both the integrity of model training and local data privacy in decentralized federated learning environments. The previous works of Joen et al.22 and Zhao et al.23 also focus on addressing security and privacy concerns in decentralized federated machine learning. The unique aspect of ProxyZKP is its utilization of ZKPs to verify the entire gradient update of the proxy model. This is further strengthened by the application of local differential privacy (LDP), which enhances privacy by adding noise to the verified updates. In contrast, Zhao et al.23 concentrates on verifying only the linear layers of the machine learning model through a verifiable matrix multiplication technique. Joen et al.22 achieve privacy by adopting a communication-based approach, without relying on encryption or noise addition. ProxyZKP provides a more comprehensive solution by combining ZKPs and differential privacy to verify the full gradient update and enhance privacy.Fig. 1ProxyZKP is a decentralized federated learning technique in which, each client, maintains a private model, a proxy model, and private data. During distributed training, the client exclusively connects with others by sharing their proxy model, which facilitates data and model privacy. The verification node checks the training integrity of each proxy model before it is shared. Following the completion of training, a client can utilize their private model for inference purposes. ProxyZKP is a decentralized federated learning technique in which, each client, maintains a private model, a proxy model, and private data. During distributed training, the client exclusively connects with others by sharing their proxy model, which facilitates data and model privacy. The verification node checks the training integrity of each proxy model before it is shared. Following the completion of training, a client can utilize their private model for inference purposes. Trusted gradient computation in decentralized learning The basic components that constitute Decentralized Federated Learning2,3 and the role of gradient computation and verification by Zero-Knowledge Proof (ZKP) under the ProxyZKP framework are discussed in the section. These components work in cohort to provide secure, privacy-preserving, and reliable model training across multiple participants. Decentralized federated learning procedure ProxyZKP, as depicted in Fig. 1a, enables multiple clients to collaboratively train machine learning models without relying on a central aggregation server. It involves several key components:Local gradient computation and verification: As shown in Fig. 1b, each local client independently trains a dual-model setup using its private data under the Deep Mutual Learning framework12,13. This setup involves two models: a private model and a proxy model. The private model performs online inference on local data after training completion and remains isolated from the network, while the proxy model provides training updates across the decentralized network. Once the gradients are computed, each client generates a proof of the integrity of the update. This proof, along with the gradient, is transmitted to the network for verificationVerification of gradient updates: Upon receiving proof from each local client, the verifier node checks the integrity of the gradient updates. If the verification succeeds, the gradients are accepted and shared with all other nodes. If the verification fails, the gradient update is discarded to ensure that only valid updates are used.Decentralized gradient averaging at each client: Each client computes the averaged gradient from all verified updates. This decentralized averaging ensures that every node calculates the same average gradient without needing a central aggregator.Model update and iteration: After averaging the gradients, each client updates its local model using the averaged gradient. This iterative process continues with further rounds of gradient computations and verifications until the models converge or meet predefined performance criteria.Decentralized communication and coordination: Efficient communication of model updates is crucial to decentralized machine learning. Network structures such as peer-to-peer, ring, or mesh topologies are commonly used to facilitate the exchange and synchronization of information without the need for a central server. Local gradient computation and verification: As shown in Fig. 1b, each local client independently trains a dual-model setup using its private data under the Deep Mutual Learning framework12,13. This setup involves two models: a private model and a proxy model. The private model performs online inference on local data after training completion and remains isolated from the network, while the proxy model provides training updates across the decentralized network. Once the gradients are computed, each client generates a proof of the integrity of the update. This proof, along with the gradient, is transmitted to the network for verification Local gradient computation and verification: As shown in Fig. 1b, each local client independently trains a dual-model setup using its private data under the Deep Mutual Learning framework12,13. This setup involves two models: a private model and a proxy model. The private model performs online inference on local data after training completion and remains isolated from the network, while the proxy model provides training updates across the decentralized network. Once the gradients are computed, each client generates a proof of the integrity of the update. This proof, along with the gradient, is transmitted to the network for verification Verification of gradient updates: Upon receiving proof from each local client, the verifier node checks the integrity of the gradient updates. If the verification succeeds, the gradients are accepted and shared with all other nodes. If the verification fails, the gradient update is discarded to ensure that only valid updates are used. Verification of gradient updates: Upon receiving proof from each local client, the verifier node checks the integrity of the gradient updates. If the verification succeeds, the gradients are accepted and shared with all other nodes. If the verification fails, the gradient update is discarded to ensure that only valid updates are used. Decentralized gradient averaging at each client: Each client computes the averaged gradient from all verified updates. This decentralized averaging ensures that every node calculates the same average gradient without needing a central aggregator. Decentralized gradient averaging at each client: Each client computes the averaged gradient from all verified updates. This decentralized averaging ensures that every node calculates the same average gradient without needing a central aggregator. Model update and iteration: After averaging the gradients, each client updates its local model using the averaged gradient. This iterative process continues with further rounds of gradient computations and verifications until the models converge or meet predefined performance criteria. Model update and iteration: After averaging the gradients, each client updates its local model using the averaged gradient. This iterative process continues with further rounds of gradient computations and verifications until the models converge or meet predefined performance criteria. Decentralized communication and coordination: Efficient communication of model updates is crucial to decentralized machine learning. Network structures such as peer-to-peer, ring, or mesh topologies are commonly used to facilitate the exchange and synchronization of information without the need for a central server. Decentralized communication and coordination: Efficient communication of model updates is crucial to decentralized machine learning. Network structures such as peer-to-peer, ring, or mesh topologies are commonly used to facilitate the exchange and synchronization of information without the need for a central server. ProxyZKP in decentralized federated learning The integration of ProxyZKP within the DFL framework addresses the challenges of securely verifying model updates without revealing sensitive data:Proof generation: Each node generates ZKP on the integrity of its proxy model updates after local training. This proof provides the signature of correct gradient computations without exposing any underlying data. The use of Kate polynomial commitment scheme15 allows for the compact proof generation, due to the multivariate polynomial nature of the proxy model.Verification and decentralized aggregation: Verification nodes (or a subset of nodes) validate the submitted ZKP to ensure that updates are both accurate and untampered before aggregation. This process prevents malicious updates from being included in the new global model and safeguard the reliability of the decentralized federated learning environment. Proof generation: Each node generates ZKP on the integrity of its proxy model updates after local training. This proof provides the signature of correct gradient computations without exposing any underlying data. The use of Kate polynomial commitment scheme15 allows for the compact proof generation, due to the multivariate polynomial nature of the proxy model. Proof generation: Each node generates ZKP on the integrity of its proxy model updates after local training. This proof provides the signature of correct gradient computations without exposing any underlying data. The use of Kate polynomial commitment scheme15 allows for the compact proof generation, due to the multivariate polynomial nature of the proxy model. Verification and decentralized aggregation: Verification nodes (or a subset of nodes) validate the submitted ZKP to ensure that updates are both accurate and untampered before aggregation. This process prevents malicious updates from being included in the new global model and safeguard the reliability of the decentralized federated learning environment. Verification and decentralized aggregation: Verification nodes (or a subset of nodes) validate the submitted ZKP to ensure that updates are both accurate and untampered before aggregation. This process prevents malicious updates from being included in the new global model and safeguard the reliability of the decentralized federated learning environment. Dual-model training framework The dual-model training approach, as shown Fig. 1b, is based the work on Deep Mutual Learning12. It involves the simultaneous training of a private deep learning model, \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$f_{\textrm{NN}}\left( x ; \theta _{\textrm{NN}}\right)$$\end{document}, and a multivariate polynomial proxy model, \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$f_{\text {poly}}\left( x ; \theta _{\text {poly}}\right)$$\end{document}. The training objectives are defined as:1\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\begin{aligned} L_{\theta _k}&= (1-\alpha ) \cdot L_{\text {Cross-Entropy}}(f_{\textrm{NN},\theta _k}) + \alpha \cdot L_{2}(f_{\textrm{NN},\theta _k}, f_{\text {poly},\phi _k}), \end{aligned}$$\end{document}2\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\begin{aligned} L_{\phi _k}&= (1-\beta ) \cdot L_{\text {MSE}}(f_{\text {poly},\phi _k}) + \beta \cdot L_{2}(f_{\text {poly},\phi _k}, f_{\textrm{NN},\theta _k}), \end{aligned}$$\end{document}where \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\alpha$$\end{document} and \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\beta$$\end{document} balance the contributions of individual model training and cross-model mismatch. To couple the learning of the two models, we replace the Kullback–Leibler (KL) divergence used in the original Deep Mutual Learning12 formulation with an \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$L_{2}$$\end{document} divergence24 as the distance metric between the outputs of the private model and the proxy model. This modification aligns their predictions while ensuring that the gradient updates for the proxy model \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$f_{\text {poly}}$$\end{document} remain in multivariate polynomial form, which is crucial for meeting the structural requirements of subsequent cryptographic operations. In this configuration, the private model \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$f_{\textrm{NN}}$$\end{document} is trained using the Cross-Entropy loss function, while the proxy model \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$f_{\text {poly}}$$\end{document} uses Mean Square Error (MSE) as its loss function. The MSE loss function is essential for maintaining the polynomial structure in the gradient updates of the proxy model, as required by the Kate polynomial commitment15 ZKP process. Soft labels from private model pre-training help address limitations in regression-based training and improve consistency with the private model. For more details on soft label generation, refer to Hinton et al.25 and Vargas et al.26. Multivariate polynomial model for multi-layer perceptron and convolutional neural network The use of a multivariate polynomial form as the proxy model in neural networks presents challenges due to the increasing complexity of terms, which grows exponentially with the number of inputs (\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$n$$\end{document}) and the polynomial degree (\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$d$$\end{document}). Our work introduces specialized polynomial proxy models named PolyMLP and PolyCNN to address this issue. These models use a Taylor expansion-like structure for deep learning, where the ReLU activation function is expanded into 2nd order polynomials27. The outputs of both the PolyMLP and PolyCNN models can be represented as multivariate polynomials in terms of their input variables. Let \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$x = (x_1, x_2, \ldots , x_n)$$\end{document} denote the input vector, where \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$n = 784$$\end{document} for the MLP model (MNIST dataset) and \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$n = 1024$$\end{document} for the CNN model (CIFAR dataset). The unified polynomial expression for the output of both models is given by:3\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\begin{aligned} f_{\text {poly}}(x) = \sum _{i_1=0}^{2} \sum _{i_2=0}^{2} \cdots \sum _{i_n=0}^{2} a_{i_1 i_2 \cdots i_n} x_1^{i_1} x_2^{i_2} \cdots x_n^{i_n} , \end{aligned}$$\end{document}where:\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$a_{i_1 i_2 \cdots i_n}$$\end{document} are the polynomial coefficients,\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$i_1, i_2, \ldots , i_n$$\end{document} are the degrees associated with each variable, andThe multivariate polynomial models approximate the behavior of the original MLP and CNN using quadratic expansions up to the \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$2^{nd}$$\end{document} order. It is important to note that the PolyMLP and PolyCNN models, in their multivariate polynomial forms, have the same number of learnable parameters as the original MLP and CNN models before expansion. This means the complexity in terms of the number of parameters remains the same. However, polynomial models require significantly more dense computations due to the lack of optimizations inherent in neural networks, such as parameter sharing and hardware acceleration28,29. Consequently, the original MLP and CNN models are more computationally efficient and better suited for online applications. In contrast, the polynomial models are particularly valuable in contexts where polynomial representations are crucial, such as in cryptographic and privacy-preserving computations30. \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$a_{i_1 i_2 \cdots i_n}$$\end{document} are the polynomial coefficients, \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$a_{i_1 i_2 \cdots i_n}$$\end{document} are the polynomial coefficients, \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$i_1, i_2, \ldots , i_n$$\end{document} are the degrees associated with each variable, and \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$i_1, i_2, \ldots , i_n$$\end{document} are the degrees associated with each variable, and Polynomial model for multi-layer perceptron (PolyMLP) The Multi-Layer Perception (MLP) model processes input data from the MNIST dataset. The dataset consists of \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$28 \times 28$$\end{document} grayscale images that are flattened into vectors of 784 elements. The MLP architecture considered in this work includes one hidden layer with 10 neurons, respectively, and an output layer corresponding to the 10 possible digit classes. Each layer of the MLP performs a linear transformation followed by a non-linear activation function. By approximating the ReLU activation function with a quadratic polynomial, the output of each layer can be expressed as a polynomial:Layer 1 The input layer computes a linear transformation of the input vector x:4\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\begin{aligned} z_i^{(1)} = \sum _{j=1}^{784} W_{ij}^{(1)} x_j + b_i^{(1)}, \end{aligned}$$\end{document}where \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$W_{ij}^{(1)}$$\end{document} are the weights and \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$b_i^{(1)}$$\end{document} are the biases for the first layer. The ReLU activation is approximated quadratically27 as:5\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\begin{aligned} \operatorname {ReLU}\left( z_i^{(1)}\right) \approx a_0 + a_1 z_i^{(1)} + a_2 \left( z_i^{(1)}\right) ^2. \end{aligned}$$\end{document}Substituting the expression for \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$z_i^{(1)}$$\end{document}, the output of the first layer becomes:6\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\begin{aligned} y_i^{(1)} = a_0 + a_1 \left( \sum _{j=1}^{784} W_{ij}^{(1)} x_j + b_i^{(1)}\right) + a_2 \left( \sum _{j=1}^{784} W_{ij}^{(1)} x_j + b_i^{(1)}\right) ^2. \end{aligned}$$\end{document}Expanding the square term yields a polynomial that includes linear and quadratic terms in the input features \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$x_j$$\end{document}.Layer 2 The output of the first layer is processed by the second hidden layer:7\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\begin{aligned} z_i^{(2)} = \sum _{k=1}^{10} W_{ik}^{(2)} y_k^{(1)} + b_i^{(2)}. \end{aligned}$$\end{document}Substituting \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$y_k^{(1)}$$\end{document} from the first layer, we obtain:8\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\begin{aligned} z_i^{(2)} = \sum _{k=1}^{10} W_{ik}^{(2)} \left[ a_0 + a_1 \left( \sum _{j=1}^{784} W_{kj}^{(1)} x_j + b_k^{(1)}\right) + a_2 \left( \sum _{j=1}^{784} W_{kj}^{(1)} x_j + b_k^{(1)}\right) ^2 \right] + b_i^{(2)}. \end{aligned}$$\end{document}Since we apply a linear activation function in the second layer, the output remains a quadratic polynomial in the input variables \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$x_j$$\end{document}. Layer 1 The input layer computes a linear transformation of the input vector x:4\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\begin{aligned} z_i^{(1)} = \sum _{j=1}^{784} W_{ij}^{(1)} x_j + b_i^{(1)}, \end{aligned}$$\end{document}where \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$W_{ij}^{(1)}$$\end{document} are the weights and \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$b_i^{(1)}$$\end{document} are the biases for the first layer. The ReLU activation is approximated quadratically27 as:5\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\begin{aligned} \operatorname {ReLU}\left( z_i^{(1)}\right) \approx a_0 + a_1 z_i^{(1)} + a_2 \left( z_i^{(1)}\right) ^2. \end{aligned}$$\end{document}Substituting the expression for \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$z_i^{(1)}$$\end{document}, the output of the first layer becomes:6\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\begin{aligned} y_i^{(1)} = a_0 + a_1 \left( \sum _{j=1}^{784} W_{ij}^{(1)} x_j + b_i^{(1)}\right) + a_2 \left( \sum _{j=1}^{784} W_{ij}^{(1)} x_j + b_i^{(1)}\right) ^2. \end{aligned}$$\end{document}Expanding the square term yields a polynomial that includes linear and quadratic terms in the input features \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$x_j$$\end{document}. Layer 1 The input layer computes a linear transformation of the input vector x:4\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\begin{aligned} z_i^{(1)} = \sum _{j=1}^{784} W_{ij}^{(1)} x_j + b_i^{(1)}, \end{aligned}$$\end{document}where \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$W_{ij}^{(1)}$$\end{document} are the weights and \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$b_i^{(1)}$$\end{document} are the biases for the first layer. The ReLU activation is approximated quadratically27 as:5\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\begin{aligned} \operatorname {ReLU}\left( z_i^{(1)}\right) \approx a_0 + a_1 z_i^{(1)} + a_2 \left( z_i^{(1)}\right) ^2. \end{aligned}$$\end{document}Substituting the expression for \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$z_i^{(1)}$$\end{document}, the output of the first layer becomes:6\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\begin{aligned} y_i^{(1)} = a_0 + a_1 \left( \sum _{j=1}^{784} W_{ij}^{(1)} x_j + b_i^{(1)}\right) + a_2 \left( \sum _{j=1}^{784} W_{ij}^{(1)} x_j + b_i^{(1)}\right) ^2. \end{aligned}$$\end{document}Expanding the square term yields a polynomial that includes linear and quadratic terms in the input features \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$x_j$$\end{document}. Layer 2 The output of the first layer is processed by the second hidden layer:7\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\begin{aligned} z_i^{(2)} = \sum _{k=1}^{10} W_{ik}^{(2)} y_k^{(1)} + b_i^{(2)}. \end{aligned}$$\end{document}Substituting \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$y_k^{(1)}$$\end{document} from the first layer, we obtain:8\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\begin{aligned} z_i^{(2)} = \sum _{k=1}^{10} W_{ik}^{(2)} \left[ a_0 + a_1 \left( \sum _{j=1}^{784} W_{kj}^{(1)} x_j + b_k^{(1)}\right) + a_2 \left( \sum _{j=1}^{784} W_{kj}^{(1)} x_j + b_k^{(1)}\right) ^2 \right] + b_i^{(2)}. \end{aligned}$$\end{document}Since we apply a linear activation function in the second layer, the output remains a quadratic polynomial in the input variables \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$x_j$$\end{document}. Layer 2 The output of the first layer is processed by the second hidden layer:7\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\begin{aligned} z_i^{(2)} = \sum _{k=1}^{10} W_{ik}^{(2)} y_k^{(1)} + b_i^{(2)}. \end{aligned}$$\end{document}Substituting \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$y_k^{(1)}$$\end{document} from the first layer, we obtain:8\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\begin{aligned} z_i^{(2)} = \sum _{k=1}^{10} W_{ik}^{(2)} \left[ a_0 + a_1 \left( \sum _{j=1}^{784} W_{kj}^{(1)} x_j + b_k^{(1)}\right) + a_2 \left( \sum _{j=1}^{784} W_{kj}^{(1)} x_j + b_k^{(1)}\right) ^2 \right] + b_i^{(2)}. \end{aligned}$$\end{document}Since we apply a linear activation function in the second layer, the output remains a quadratic polynomial in the input variables \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$x_j$$\end{document}. Polynomial model for convolutional neural network (PolyCNN) The Convolutional Neural Network (CNN) model processes input data from the CIFAR dataset. Each image is a single color channel flattened into a vector of 1024 elements. The CNN architecture includes two convolutional layers, followed by a fully connected layer and an output layer corresponding to the 10 possible classes. The PolyCNN model applies block Toeplitz matrices31 to input vectors from the CIFAR dataset. Layer 1 (Convolution): Each filter in the first convolutional layer is represented as a multiplication by a block Toeplitz matrix \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\textbf{T}$$\end{document}. The convolution operation is represented as:9\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\begin{aligned} \operatorname {conv}\left( \textbf{T}, \textbf{x}\right) = \textbf{T} \cdot \textbf{x}, \end{aligned}$$\end{document}where \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\textbf{T}$$\end{document} is the block Toeplitz matrix and \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\textbf{x}$$\end{document} is the input vector. The ReLU activation is approximated quadratically27 as:10\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\begin{aligned} y^{(1)} = a_0 + a_1 \left( \textbf{T} \cdot \textbf{x} + b_1\right) + a_2 \left( \textbf{T} \cdot \textbf{x} + b_1\right) ^2. \end{aligned}$$\end{document}Expanding the square term gives:11\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\begin{aligned} \left( \textbf{T} \cdot \textbf{x} + b_1\right) ^2 = \left( \textbf{T} \cdot \textbf{x}\right) ^2 + 2 b_1 \textbf{T} \cdot \textbf{x} + b_1^2, \end{aligned}$$\end{document}which produces a quadratic polynomial in the input variables \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\textbf{x}_i$$\end{document} with interaction terms. Layer 2 (Convolution with linear activation) The second convolutional layer applies a linear activation function, meaning no quadratic terms are introduced. The convolution is represented as:12\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\begin{aligned} \operatorname {conv}_f\left( \textbf{T}_2, \textbf{y}^{(1)}\right) = \textbf{T}_2 \cdot \textbf{y}^{(1)}, \end{aligned}$$\end{document}where \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\textbf{T}_2$$\end{document} is the block Toeplitz matrix in the second layer and \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\textbf{y}^{(1)}$$\end{document} is the output from the first layer. Since this layer uses a linear activation function, the output \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$z_f^{(2)}$$\end{document} is:13\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\begin{aligned} z_f^{(2)} = \textbf{T}_2 \cdot \textbf{y}^{(1)} + b_2, \end{aligned}$$\end{document}where \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$b_2$$\end{document} is the bias term, and no additional non-linearity is applied. Complexity comparison The complexity of both PolyMLP and PolyCNN stems from the use of polynomial activation, which increase computational complexity during forward and backward passes. Specifically, the PolyCNN processes images of size \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$32 \times 32$$\end{document} (1,024 input elements) and introduces approximately \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$648,\!000$$\end{document} quadratic terms in the hidden layer. In contrast, the PolyMLP processes images of size \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$28 \times 28$$\end{document} (784 input elements) and introduces \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$307,\!720$$\end{document} quadratic terms in its first hidden layer. While the polynomial activation capture more complex patterns, they increase the computational load but maintain the same number of learnable parameters as their conventional counterparts. For PolyMLP, with one hidden layer of 10 neurons, the total number of parameters remains 7960, the same as in the original unexpanded MLP. Similarly, for PolyCNN, using block Toeplitz matrices to represent convolutional layers does not increase the parameter count, which stays at 2,590 for a minimal CNN structure with two convolutional layers and one fully connected layer. Gradient update for the original network parameters with polynomial mapping To train the model, we update the original network parameters (e.g., weights \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$W$$\end{document} and biases \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$b$$\end{document}) instead of the polynomial coefficients \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$a_{i_1 i_2 \dots i_n}$$\end{document}. The relationship between the original network parameters and the polynomial coefficients is managed by a mapping function \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$g_{i_1 i_2 \dots i_n}(\theta _k)$$\end{document}, where \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\theta _k$$\end{document} denotes the original parameters. This mapping is handled using symbolic mathematics to compute the final gradients in polynomial form. The polynomial coefficients \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$a_{i_1 i_2 \dots i_n}$$\end{document} are functions of the original network parameters \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\theta _k$$\end{document}:14\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\begin{aligned} a_{i_1 i_2 \dots i_n} = g_{i_1 i_2 \dots i_n}(\theta _k) \end{aligned}$$\end{document}This relationship captures how the original parameters influence the polynomial coefficients and how the input features interact through the polynomial structure. The gradient of the loss function \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$L_{\phi _k}$$\end{document} with respect to each original network parameter \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\theta _k$$\end{document} is given by:15\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\begin{aligned} \nabla _{\theta _k} L_{\phi _k}&= (1 - \beta ) \sum _{j=1}^N \left( f_{\text {Poly}}(\phi _k, x_j) - y_j \right) \cdot \nabla _{\theta _k} f_{\text {Poly}}(\phi _k, x_j) \nonumber \\&\quad + \beta \sum _{j=1}^N \left( f_{\text {Poly}}(\phi _k, x_j) - f_{\text {CNN}}(\theta _k, x_j) \right) \cdot \nabla _{\theta _k} f_{\text {Poly}}(\phi _k, x_j), \end{aligned}$$\end{document}where:\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$f_{\text {Poly}}(\phi _k, x_j)$$\end{document} is the output of the polynomial model,\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$f_{\text {CNN}}(\theta _k, x_j)$$\end{document} is the output of the CNN model,\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\nabla _{\theta _k} f_{\text {Poly}}(\phi _k, x_j)$$\end{document} is the gradient of the polynomial model with respect to the original network parameters.Using symbolic mathematics, we can compute the gradient of the polynomial model output \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$f_{\text {Poly}}$$\end{document} with respect to \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\theta _k$$\end{document} as follows:16\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\begin{aligned} \nabla _{\theta _k} f_{\text {Poly}}(\phi _k, x_j) = \sum _{(i_1, i_2, \dots , i_n)} x_{1,j}^{i_1} x_{2,j}^{i_2} \cdots x_{n,j}^{i_n} \cdot \nabla _{\theta _k} a_{i_1 i_2 \dots i_n}. \end{aligned}$$\end{document}Since \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$a_{i_1 i_2 \dots i_n}$$\end{document} is a function of \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\theta _k$$\end{document}, a symbolic differentiation tool like SymPy (Meurer et al., 2017)39 enables symbolic differentiation of polynomial coefficients and original network parameters. Finally, the update rule for each original network parameter \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\theta _k$$\end{document} is given by:17\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\begin{aligned} \theta _k^{(t+1)} = \theta _k^{(t)} - \eta \cdot \nabla _{\theta _k} L_{\phi _k}, \end{aligned}$$\end{document}where \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\eta$$\end{document} is the learning rate. \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$f_{\text {Poly}}(\phi _k, x_j)$$\end{document} is the output of the polynomial model, \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$f_{\text {Poly}}(\phi _k, x_j)$$\end{document} is the output of the polynomial model, \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$f_{\text {CNN}}(\theta _k, x_j)$$\end{document} is the output of the CNN model, \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$f_{\text {CNN}}(\theta _k, x_j)$$\end{document} is the output of the CNN model, \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\nabla _{\theta _k} f_{\text {Poly}}(\phi _k, x_j)$$\end{document} is the gradient of the polynomial model with respect to the original network parameters. \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\nabla _{\theta _k} f_{\text {Poly}}(\phi _k, x_j)$$\end{document} is the gradient of the polynomial model with respect to the original network parameters. Zero-knowledge proof construction for multivariate polynomial computations We propose a two-stage proof scheme to verify the accuracy of multivariate polynomial computations using the Kate Commitment ZKP15. The scheme begins by breaking down the multivariate polynomial into a series of checks for univariate polynomials. A consistency check is then performed using Sigma protocol to ensure the overall evaluation’s validity. Unlike existing methods32,33 that rely on computationally intensive algebraic structures, our approach transforms the problem into a series of univariate checks, thereby reducing verification computational workload. By simplifying the complexity of Zero-Knowledge Proofs (ZKP), our scheme is well-suited for large-scale applications, such as decentralized federated learning. A detailed schematic of this scheme is shown in Fig. 2.Fig. 2Two-stage proof of multivariate polynomial computation integrity scheme. Two-stage proof of multivariate polynomial computation integrity scheme. Decomposition and commitment to univariate polynomials In order to efficiently and securely verify a multivariate polynomial \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$P(x_1, x_2, \ldots , x_m)$$\end{document}, the prover breaks it down into a series of univariate polynomials by fixing all variables except one. Upon receiving the challenge point \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$x_o = (x_{o1}, x_{o2}, \ldots , x_{om})$$\end{document} from the verifier, the multivariate polynomial \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$P(x_1, x_2, \ldots , x_m)$$\end{document} is broken down into univariate polynomials \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$F_i(x_i)$$\end{document}, as follows:18\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\begin{aligned} F_i(x_i) = P(x_{o1}, \ldots , x_i, \ldots , x_{om}), \end{aligned}$$\end{document}where \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$x_o$$\end{document} is a fixed value for all variables except \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$x_i$$\end{document}. When evaluated at \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$x_o$$\end{document}, each individual polynomial \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$F_i(x_{oi})$$\end{document} equals the evaluation of the original multivariate polynomial at the point where all variables are set to \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$x_0$$\end{document}:19\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\begin{aligned} P(x_o) = F_i(x_{oi}) \quad \text {for all} \; i. \end{aligned}$$\end{document}Next, the prover commits to each univariate polynomial \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$F_i(x_i)$$\end{document} using the Kate polynomial commitment scheme, which relies on cryptographic commitments in group \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$G_1$$\end{document} with a trusted setup parameter \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\tau$$\end{document}. The commitment to a univariate polynomial \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$F_i(x_i)$$\end{document} is calculated as:20\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\begin{aligned} C(F_i) = g_1^{F_i(\tau )} = g_1^{a_0 + a_1 \tau + \cdots + a_d \tau ^{d}}, \end{aligned}$$\end{document}where \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$g_1$$\end{document} is the generator of the elliptic curve group \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$G_1$$\end{document}34, and \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$a_j$$\end{document} are the coefficients of the polynomial. These commitments ensure that the polynomial coefficients are securely encapsulated, allowing the prover to respond to verification challenges while maintaining data privacy. Commitment to the quotient polynomial The prover evaluates the univariate polynomial \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$F_i(x_i)$$\end{document} at the challenge point \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$x_o$$\end{document}, obtaining \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$F_i(x_{oi})$$\end{document}. Instead of sending this value directly, the prover constructs a quotient polynomial \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$q_i(x)$$\end{document} to capture the difference between \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$F_i(x)$$\end{document} and its evaluation at \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$x_0$$\end{document}:21\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\begin{aligned} q_i(x) = \frac{F_i(x) - F_i(x_{oi})}{x - x_{oi}} \end{aligned}$$\end{document}This quotient polynomial enables the verifier to confirm the correctness of \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$F_i(x_0)$$\end{document}. The prover also computes a commitment to the quotient polynomial \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$q_i(x)$$\end{document}, denoted as \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$C(q_i)$$\end{document}:22\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\begin{aligned} C(q_i) = g_1^{q_i(\tau )} = g_1^{b_0 + b_1 \tau + \cdots + b_{d-1} \tau ^{d-1}} \end{aligned}$$\end{document}where \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$b_j$$\end{document} are the coefficients of \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$q_i(x)$$\end{document}. Proof generation The prover sends the following to the verifier:The commitment \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$C(F_i)$$\end{document} to the univariate polynomial \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$F_i(x_i)$$\end{document},The commitment \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$C(q_i)$$\end{document} to the quotient polynomial \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$q_i(x)$$\end{document},The evaluation \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$F_i(x_0)$$\end{document} (not sent directly, but part of the proof). The commitment \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$C(F_i)$$\end{document} to the univariate polynomial \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$F_i(x_i)$$\end{document}, The commitment \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$C(F_i)$$\end{document} to the univariate polynomial \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$F_i(x_i)$$\end{document}, The commitment \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$C(q_i)$$\end{document} to the quotient polynomial \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$q_i(x)$$\end{document}, The commitment \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$C(q_i)$$\end{document} to the quotient polynomial \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$q_i(x)$$\end{document}, The evaluation \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$F_i(x_0)$$\end{document} (not sent directly, but part of the proof). The evaluation \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$F_i(x_0)$$\end{document} (not sent directly, but part of the proof). Verification using bilinear pairing To verify the correctness of \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$F_i(x_0)$$\end{document}, the verifier checks the following bilinear pairing equation:23\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\begin{aligned} e\left( C(F_i) - g_1^{F_i(x_0)},\ g_2 \right) {\mathop {=}\limits ^{?}} e\left( C(q_i),\ g_2^{x_0} \cdot h \right) \end{aligned}$$\end{document}where \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$e(\cdot , \cdot )$$\end{document} denotes the bilinear pairing operation35, \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$g_2$$\end{document} is the generator of a different elliptic curve group \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$G_2$$\end{document}34, and \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$h = g_2^{-\tau }$$\end{document} is a public parameter from the trusted setup. If the equation holds, the verifier is convinced of the correctness of \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$F_i(x_0)$$\end{document}, without learning the actual value. Sigma protocol for consistency verification After the zero-knowledge proof for each univariate polynomial \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$F_i(x_0)$$\end{document}, the prover must demonstrate that these evaluations are consistent with the evaluation of the original multivariate polynomial \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$P(x_0)$$\end{document}. This consistency is verified using the Sigma protocol36, which allows the prover to prove that the committed evaluations \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$F_i(x_0)$$\end{document} are consistent with \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$P(x_0)$$\end{document}, without revealing any additional information. Commitments to \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$P(x_0)$$\end{document} and \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$F_i(x_0)$$\end{document} The prover begins by committing to both the evaluation of the multivariate polynomial \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$P(x_0)$$\end{document} and each univariate polynomial \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$F_i(x_{0i})$$\end{document}. The prover commits to the value \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$P(x_0)$$\end{document} as:24\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\begin{aligned} C_P = g^{P(x_0)} h^{r_P} \end{aligned}$$\end{document}where \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$g$$\end{document} and \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$h$$\end{document} are generators of a group \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$G$$\end{document}, and \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$r_P$$\end{document} is a random blinding factor. For each univariate polynomial \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$F_i(x_0)$$\end{document}, the verifier knows:25\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\begin{aligned} C_{F_i} = g^{F_i(x_0)} \end{aligned}$$\end{document} Sigma protocol execution To prove the consistency between \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$P(x_0)$$\end{document} and the set of univariate polynomials \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$F_i(x_0)$$\end{document}, the prover engages in a Sigma protocol with the verifier. The protocol proceeds as follows: For each \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$i = 1, \ldots , n$$\end{document}, the prover and verifier follow these steps:Verifier computes the difference commitment The verifier calculates the difference between the commitments:26\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\begin{aligned} C_{d_i} = C_P \cdot C_{F_i}^{-1} = g^{P(x_0) - F_i(x_0)} h^{r_P} \end{aligned}$$\end{document}Since \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$P(x_0) = F_i(x_0)$$\end{document}, this simplifies to:27\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\begin{aligned} C_{d_i} = h^{r_P} \end{aligned}$$\end{document}Prover’s commitment (first message) The prover picks a random value \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$s \in \mathbb {Z}_q$$\end{document} and computes:28\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\begin{aligned} t = h^s \end{aligned}$$\end{document}Prover Sends: \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$t$$\end{document} to the verifier.Verifier’s challenge (Second Message) The verifier selects a random challenge \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$e \in \mathbb {Z}_q$$\end{document}. Verifier Sends: \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$e$$\end{document} to the prover.Prover’s response (Third Message) The prover computes:29\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\begin{aligned} z = s + e \cdot r_P \end{aligned}$$\end{document}Prover Sends: \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$z$$\end{document} to the verifier.Verifier’s verification The verifier checks if:30\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\begin{aligned} h^z {\mathop {=}\limits ^{?}} t \cdot (C_{d_i})^e \end{aligned}$$\end{document}If this holds, the verifier is convinced that \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$P(x_0) = F_i(x_0)$$\end{document}. This sigma protocol efficiently proves that \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$P(x_0) = F_i(x_0)$$\end{document} for all \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$i = 1, \ldots , n$$\end{document}, while maintaining zero-knowledge, ensuring privacy and consistency without additional information leakage. Verifier computes the difference commitment The verifier calculates the difference between the commitments:26\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\begin{aligned} C_{d_i} = C_P \cdot C_{F_i}^{-1} = g^{P(x_0) - F_i(x_0)} h^{r_P} \end{aligned}$$\end{document}Since \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$P(x_0) = F_i(x_0)$$\end{document}, this simplifies to:27\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\begin{aligned} C_{d_i} = h^{r_P} \end{aligned}$$\end{document} Verifier computes the difference commitment The verifier calculates the difference between the commitments:26\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\begin{aligned} C_{d_i} = C_P \cdot C_{F_i}^{-1} = g^{P(x_0) - F_i(x_0)} h^{r_P} \end{aligned}$$\end{document}Since \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$P(x_0) = F_i(x_0)$$\end{document}, this simplifies to:27\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\begin{aligned} C_{d_i} = h^{r_P} \end{aligned}$$\end{document} Prover’s commitment (first message) The prover picks a random value \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$s \in \mathbb {Z}_q$$\end{document} and computes:28\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\begin{aligned} t = h^s \end{aligned}$$\end{document}Prover Sends: \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$t$$\end{document} to the verifier. Prover’s commitment (first message) The prover picks a random value \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$s \in \mathbb {Z}_q$$\end{document} and computes:28\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\begin{aligned} t = h^s \end{aligned}$$\end{document}Prover Sends: \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$t$$\end{document} to the verifier. Verifier’s challenge (Second Message) The verifier selects a random challenge \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$e \in \mathbb {Z}_q$$\end{document}. Verifier Sends: \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$e$$\end{document} to the prover. Verifier’s challenge (Second Message) The verifier selects a random challenge \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$e \in \mathbb {Z}_q$$\end{document}. Verifier Sends: \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$e$$\end{document} to the prover. Prover’s response (Third Message) The prover computes:29\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\begin{aligned} z = s + e \cdot r_P \end{aligned}$$\end{document}Prover Sends: \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$z$$\end{document} to the verifier. Prover’s response (Third Message) The prover computes:29\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\begin{aligned} z = s + e \cdot r_P \end{aligned}$$\end{document}Prover Sends: \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$z$$\end{document} to the verifier. Verifier’s verification The verifier checks if:30\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\begin{aligned} h^z {\mathop {=}\limits ^{?}} t \cdot (C_{d_i})^e \end{aligned}$$\end{document}If this holds, the verifier is convinced that \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$P(x_0) = F_i(x_0)$$\end{document}. This sigma protocol efficiently proves that \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$P(x_0) = F_i(x_0)$$\end{document} for all \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$i = 1, \ldots , n$$\end{document}, while maintaining zero-knowledge, ensuring privacy and consistency without additional information leakage. Verifier’s verification The verifier checks if:30\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\begin{aligned} h^z {\mathop {=}\limits ^{?}} t \cdot (C_{d_i})^e \end{aligned}$$\end{document}If this holds, the verifier is convinced that \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$P(x_0) = F_i(x_0)$$\end{document}. This sigma protocol efficiently proves that \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$P(x_0) = F_i(x_0)$$\end{document} for all \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$i = 1, \ldots , n$$\end{document}, while maintaining zero-knowledge, ensuring privacy and consistency without additional information leakage. Final decision and summary of the proof system The proof system combines the Kate polynomial commitment scheme, which verifies the correct evaluation of univariate polynomials \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$F_i(x_i)$$\end{document} at specific points, with the Sigma protocol, which ensures consistency in evaluations of univariate \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$F_i(x_i)$$\end{document} align with the multivariate polynomial \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$P(x_0)$$\end{document}. The verifier’s final decision is based on the bilinear pairing and consistency checks. If both are validated, the proof is accepted, confirming correct computations. If either check fails, the proof is rejected, indicating a discrepancy. As outlined in Table 1, the soundness of the system is guaranteed by the binding property of Kate polynomial commitment and the robustness of the Sigma protocol.Table 1Soundness, completeness, and zero-knowledge properties of ProxyZKP.PropertyDefinitionProtocol’s assuranceSoundnessIf the statement is false, no dishonest prover can convince the honest verifier of its truth, except with negligible probability.The Kate polynomial commitment ensures integrity by guaranteeing the correctness of \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$F_i(x_i)$$\end{document}. If \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$F_i(x_i)$$\end{document} is incorrect, the prover cannot generate a valid commitment that matches the verifier’s challenge.The Sigma protocol ensures consistency and soundness by verifying the equivalence between \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$F_i(x_0)$$\end{document} and \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$P(x_0)$$\end{document}, catching any inconsistency with negligible probability.CompletenessIf the statement is true, an honest prover can convince an honest verifier of its truth with high probability.The Kate polynomial commitment ensures that if the prover has correctly computed \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$F_i(x_i)$$\end{document}, the commitment will pass the verifier’s checks. The Sigma protocol ensures that if the evaluations of \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$F_i(x_0)$$\end{document} are consistent with \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$P(x_0)$$\end{document}, the prover can successfully pass the consistency proof, thereby ensuring completeness.Zero-KnowledgeThe verifier learns nothing beyond the validity of the statement being proven.The Sigma protocol ensures that no information about \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$P(x_0)$$\end{document} and \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$F_i(x_0)$$\end{document} is revealed beyond their consistency. To ensure the integrity of the computation for \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$F_i(x_i)$$\end{document}, the Kate polynomial commitment binds the prover to the polynomial, and its structure enables efficient verification of evaluations at specific points without disclosing the polynomial itself. Table 1Soundness, completeness, and zero-knowledge properties of ProxyZKP.PropertyDefinitionProtocol’s assuranceSoundnessIf the statement is false, no dishonest prover can convince the honest verifier of its truth, except with negligible probability.The Kate polynomial commitment ensures integrity by guaranteeing the correctness of \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$F_i(x_i)$$\end{document}. If \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$F_i(x_i)$$\end{document} is incorrect, the prover cannot generate a valid commitment that matches the verifier’s challenge.The Sigma protocol ensures consistency and soundness by verifying the equivalence between \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$F_i(x_0)$$\end{document} and \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$P(x_0)$$\end{document}, catching any inconsistency with negligible probability.CompletenessIf the statement is true, an honest prover can convince an honest verifier of its truth with high probability.The Kate polynomial commitment ensures that if the prover has correctly computed \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$F_i(x_i)$$\end{document}, the commitment will pass the verifier’s checks. The Sigma protocol ensures that if the evaluations of \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$F_i(x_0)$$\end{document} are consistent with \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$P(x_0)$$\end{document}, the prover can successfully pass the consistency proof, thereby ensuring completeness.Zero-KnowledgeThe verifier learns nothing beyond the validity of the statement being proven.The Sigma protocol ensures that no information about \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$P(x_0)$$\end{document} and \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$F_i(x_0)$$\end{document} is revealed beyond their consistency. To ensure the integrity of the computation for \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$F_i(x_i)$$\end{document}, the Kate polynomial commitment binds the prover to the polynomial, and its structure enables efficient verification of evaluations at specific points without disclosing the polynomial itself. Soundness, completeness, and zero-knowledge properties of ProxyZKP. Zero-knowledge proof of training integrity with polynomial proxy model To demonstrate the effectiveness of the ProxZKP platform on decentralized models, benchmarks on scalability, proof generation and verification are obtained on a high-performance computing system consisting of 8 nodes. Each node is equipped with AMD EPYC 7742 64-core processors and 1 TB of system memory, providing sufficient resources to manage the intensive proof generation tasks. Efficient networking protocols like openMPI are utilized as the communication protocol, similar to the work by Kalra et al.13. For the evaluation, we employed two image classification datasets: MNIST and CIFAR. The MNIST dataset consists of 60,000 grayscale images of size \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$28\times 28$$\end{document}, while the CIFAR dataset comprises 50,000 RGB images of size \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$32\times 32$$\end{document}, both with 10,000 test images used for model evaluation.Fig. 3Training performance of different private models and polynomial proxy models.Table 2Training parameters and model accuracy.Parameter/metricMNIST datasetCIFAR datasetConverged private model accuracy80%63%Converged proxy model accuracy73%53%Global communication rounds200200Local training epochs per round55Batch size250250OptimizerAdam (LR: 0.001, Weight Decay: \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$1 \times 10^{-4}$$\end{document})Adam (LR: 0.001, Weight Decay: \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$1 \times 10^{-4}$$\end{document}) Training performance of different private models and polynomial proxy models. Table 2Training parameters and model accuracy.Parameter/metricMNIST datasetCIFAR datasetConverged private model accuracy80%63%Converged proxy model accuracy73%53%Global communication rounds200200Local training epochs per round55Batch size250250OptimizerAdam (LR: 0.001, Weight Decay: \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$1 \times 10^{-4}$$\end{document})Adam (LR: 0.001, Weight Decay: \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$1 \times 10^{-4}$$\end{document}) Training parameters and model accuracy. Local dual model training performance Each local client holds a subset of the training data with non-overlapping private datasets. In this configuration, every client is assigned 1,000 images from the MNIST dataset or 3,000 images from the CIFAR dataset. The experiment involved an 8-client decentralized network. We used the local dual models LeNet537-PolyMLP and CNN238-PolyCNN to train on the MNIST and CIFAR datasets, respectively. A decentralized learning environment was established using a peer-to-peer communication protocol based on OpenMPI. Experimental results from training local dual model according to Eqs. 1 and 2 are shown in Fig. 3a and b. The training process is carried out with the Adam optimizer at a learning rate of 0.001, and the deep mutual learning parameters, \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\alpha$$\end{document} and \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\beta$$\end{document}, are set to 0.5. Figure 3a and b depict the training accuracy of both the private and proxy models across several epochs for both datasets. Because of their optimised architecture, the private models, LeNet537 and CNN238, demonstrate high accuracy in capturing intricate patterns within the datasets. In contrast, the observed lower accuracy of the proxy models, PolyMLP and PolyCNN, can be attributed to two factors. The primary factor arises from the reduced expressiveness of 2nd polynomial models, which restricts their ability to model more complex, non-linear relationships in the data. The second contributing factor is the choice of a regression-based loss function, Mean Squared Error (MSE), that further misaligns with the classification task objectives and leads to slower convergence. Although proxy models show lower classification accuracy than their private model counterparts, this trade-off in machine learning performance is justified by the computation integrity and privacy gains they offer. Polynomial proxy models fulfill the system’s security objectives by providing a verifiable mechanism for model updates and ensuring that the private models are isolated from external tempering. The quadratic mathematical structure as shown in Eq. 3 is crucial for maintaining compatibility with cryptographic proofs, such as Kate polynomial Commitment, even though this limits proxy models’ ability to capture complex data relationships. Table 2 shows the performance and convergence results for both datasets. The private model achieved a converged accuracy of about 80% on the MNIST dataset, while the proxy model achieved around 65%. The CIFAR dataset, which is more complex, led to converged accuracy of approximately 63% for the private model and 53% for the proxy model. These results highlight the ability of federated learning models to adjust to different data complexities while still achieving effective learning outcomes. Proof generation performance studies Table 3ProxyZKP benchmarks across MNIST and CIFAR datasets.MetricMNIST datasetCIFAR datasetAverage verification Time (ms)8095Computational overhead (%)400%500%Proof size (KB)5068Proof generation time (ms)600780Kate commitment overhead (%)90%90%Sigma protocol overhead (%)10%10% Table 4Summary of analysis: training vs cryptographic proof generation.StepTraining (PolyMLP/PolyCNN)Cryptographic proof generationMultivariate polynomial evaluationShared between training and proof generationShared between training and proof generationUnivariate polynomial EvaluationNot required in trainingRequired for proof generation (extra workload)Cryptographic operationsNot required in trainingRequired for integrity/consistency proof generation (elliptic curve operations, bilinear pairing)Overall computational costStandard arithmetic operationsCryptographic overhead Table 3ProxyZKP benchmarks across MNIST and CIFAR datasets.MetricMNIST datasetCIFAR datasetAverage verification Time (ms)8095Computational overhead (%)400%500%Proof size (KB)5068Proof generation time (ms)600780Kate commitment overhead (%)90%90%Sigma protocol overhead (%)10%10% ProxyZKP benchmarks across MNIST and CIFAR datasets. Table 4Summary of analysis: training vs cryptographic proof generation.StepTraining (PolyMLP/PolyCNN)Cryptographic proof generationMultivariate polynomial evaluationShared between training and proof generationShared between training and proof generationUnivariate polynomial EvaluationNot required in trainingRequired for proof generation (extra workload)Cryptographic operationsNot required in trainingRequired for integrity/consistency proof generation (elliptic curve operations, bilinear pairing)Overall computational costStandard arithmetic operationsCryptographic overhead Summary of analysis: training vs cryptographic proof generation. Experimental results from implementing the two-stage polynomial commitment scheme, as shown in Fig. 2, to verify the training integrity of the local node through the proxy model are presented in Table 3. We evaluated the effectiveness of this approach using the MNIST and CIFAR datasets. The key to this process is the decomposition of complex multivariate polynomials into univariate components, facilitated by SymPy39, a Python library for symbolic mathematics. By isolating each variable and treating the others as constants, SymPy converts a single multivariate polynomial terms across 784 variables (PolyMLP) or 1024 variables (PolyCNN) into 784 or 1024 univariate polynomials, respectively. The decomposition simplifies the task of verifying the polynomial in Eq. 15 by its reducing complexity. This reduced complexity facilitates faster proof generation and verification, primarily through the use of the Kate polynomial commitment scheme. This scheme is implemented using open-source libraries such as Galois40 and py_ecc41, allowing for succinct proofs and computationally efficient verification on the resulting univariate polynomials. The results in Table 3 indicate that the proof generation processes introduce significant overhead, but it remains manageable for both the MNIST and CIFAR datasets. The verification times are relatively low, with an average of 80 ms for PolyMLP and 95 ms for PolyCNN. The comparison between training and proof generation, as shown in Table 4, highlights the significant computational overhead introduced during cryptographic proof generation. While both processes share the step of multivariate polynomial evaluation, proof generation adds the burden of univariate polynomial evaluation, which is not required in training. Additionally, cryptographic operations, such as elliptic curve operations and bilinear pairings, further increase the workload, introducing complexities absent from the training phase. The need for a cryptographic consistency proof to verify the integrity of the univariate evaluations adds to the computational cost. The Sigma protocol, implemented using open-source Python libraries such as PyCryptodome42, ensures the consistency of polynomial evaluations. The computational overhead is divided between the Sigma protocol and the Kate polynomial commitment, as shown in Table 3. This overhead is primarily determined by the overall complexity of the proxy model and the dataset used. Overall, the proof generation process is approximately 400-500% more computationally expensive than training due to these added tasks. However, the compact proof sizes-50 KB for PolyMLP on MNIST and 68 KB for PolyCNN on CIFAR-demonstrate a balance between the increased complexity and scalability. Privacy-preserving mechanisms in decentralized model training: zero-knowledge proofs and differential privacy Although ZKP can provide integrity verification for the gradient data without revealing any data, sharing gradient updates across the network to train a decentralized federated model is not without privacy challenges. Adversaries can exploit these updates through attacks like Gradient Inversion19, where gradient information is used to reconstruct the private training data. To mitigate this risk, Differential Privacy (DP) techniques20,21 have been proposed to reduce the ability of attackers to extract individual data points by adding calibrated noise to the transmitting data. On the other hand, DP offers privacy protection by obscuring sensitive information, but it does not ensure the integrity of the underlying data generation process, such as gradient updates in the present case. Malicious clients can still submit manipulated gradients to undermine the integrity of the model training. By combining ZKP with DP in the ProxyZKP framework, an extra layer of data privacy protection can be deployed to minimize the risk of Gradient Inversion attacks. Impact of noise addition on gradient updates In the ProxyZKP framework, gradient updates are represented by multivariate polynomials, as shown in Eq. 15, where each gradient \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\nabla _{\theta _k} L_{\phi _k}$$\end{document} is computed locally based on private data and model parameters. To ensure computation integrity and data privacy, each local node first computes its local gradient and generates a ZKP to prove the correctness of this computation. Once the ZKP is verified, a calibrated Gaussian noise \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\mathcal {N}(0, \sigma ^2)$$\end{document} vector, is added to the gradient vector to satisfy local DP requirements by extending Eq. 15 to:31\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\begin{aligned} \tilde{\nabla _{\theta _k} L_{\phi _k} } = \nabla _{\theta _k} L_{\phi _k} + \mathcal {N}(0, \sigma ^2). \end{aligned}$$\end{document}The Diffprivlib library, a Python based open-source differential privacy tool developed by Holohan et al.43, is used to provide this calibrated noise. The amount of noise added to each element of the gradient vector is determined by the privacy parameters \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\epsilon$$\end{document} (privacy budget) and \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\delta$$\end{document} (failure probability), along with the sensitivity. In the present case, the sensitivity is controlled by the clipping factor set to unity13. After clipping the gradient’s norm at 1.0, noise is added to each element of the gradient vector based on the given privacy parameters, to make sure that each gradient vector element is protected according to the local DP practice. The noisy gradient \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\tilde{\nabla _{\theta _k} L_{\phi _k} }$$\end{document} is then shared across the network to ensure that the gradients are both valid and private. Table 5 presents the combined results of proxy models. It demonstrates how the accuracy of the private model and computational overhead vary under different privacy budgets and noise levels.Table 5Local DP protection level, private model accuracy, and computational overhead.Model/datasetPrivacy budget (\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\epsilon , \delta$$\end{document})Noise Level (\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\sigma$$\end{document})Accuracy (%)Local DP overhead (ms)MLP/MNIST\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$(0.5, 10^{-5}$$\end{document})1.560.015–20MLP/MNIST\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$(1.0, 10^{-5}$$\end{document})1.070.215–20MLP/MNIST\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$(2.0, 10^{-5}$$\end{document})0.875.315–20MLP/MNIST\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$(5.0, 10^{-5}$$\end{document})0.580.115–20CNN/CIFAR\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$(0.5, 10^{-5}$$\end{document})1.552.330–40CNN/CIFAR\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$(1.0, 10^{-5}$$\end{document})1.054.030–40CNN/CIFAR\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$(2.0, 10^{-5}$$\end{document})0.858.430–40CNN/CIFAR\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$(5.0, 10^{-5}$$\end{document})0.562.030–40 Table 5Local DP protection level, private model accuracy, and computational overhead.Model/datasetPrivacy budget (\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\epsilon , \delta$$\end{document})Noise Level (\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\sigma$$\end{document})Accuracy (%)Local DP overhead (ms)MLP/MNIST\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$(0.5, 10^{-5}$$\end{document})1.560.015–20MLP/MNIST\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$(1.0, 10^{-5}$$\end{document})1.070.215–20MLP/MNIST\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$(2.0, 10^{-5}$$\end{document})0.875.315–20MLP/MNIST\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$(5.0, 10^{-5}$$\end{document})0.580.115–20CNN/CIFAR\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$(0.5, 10^{-5}$$\end{document})1.552.330–40CNN/CIFAR\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$(1.0, 10^{-5}$$\end{document})1.054.030–40CNN/CIFAR\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$(2.0, 10^{-5}$$\end{document})0.858.430–40CNN/CIFAR\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$(5.0, 10^{-5}$$\end{document})0.562.030–40 Local DP protection level, private model accuracy, and computational overhead. For the MLP model on MNIST dataset, accuracy decreases from 80% to 60% as the privacy budget becomes stricter, with \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\epsilon$$\end{document} reduced from 5.0 to 0.5 and the noise level \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\sigma$$\end{document} increasing from 0.5 to 1.5. The stricter privacy budget introduces more noise during training, which hinders the model’s ability to learn effectively from the data, thereby reducing its accuracy. Similarly, for CNN model on CIFAR dataset, accuracy decreases from 62% to 52% under the same privacy budget reduction. However, the CNN model experiences a more pronounced drop in accuracy due to the complexity of the CIFAR dataset. The proxy model for CIFAR, PolyCNN, which needs to capture more spatial features, is more sensitive to noisy gradients. The \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$L_{2}$$\end{document} divergence coupling transfers incomplete information to private model which converges sub-optimally, resulting in a sharper accuracy drop. Diffprivlib employs well-established algorithms such as the Box-Muller transform44 and the Ziggurat algorithm45 to efficiently generate Gaussian-distributed samples in constant time, independent of the variance of the distribution. As a result, the computational overhead incurred by Diffprivlib is determined primarily by the size of the gradient vector (i.e., the number of elements to which noise is added), rather than by the variance or magnitude of the noise itself. The local differential privacy (DP) overhead is minimal compared to the proof generation overhead, which remains constant at 600 ms for PolyMLP and 780 ms for PolyCNN. The local DP process accounts for about 10% of the computational workload of proof generation. Therefore, adding DP as an additional layer of privacy protection only slightly increases the overall workload, ensuring that the extra privacy measures have insignificant impact on the performance of local clients. Scalability and performance The scalability of decentralized learning systems is critical, particularly in scenarios where the number of participating nodes varies. In this study, we benchmarked the scaling performance of ProxyZKP by focusing on the relationship between the verification node’s computational load and overall communication delay, as both factors significantly impact the system’s efficiency. These key performance metrics are needed to be examined to help optimizing the system’s performance.Table 6Network size impact on communication time and computational overhead for MLP and CNN on MNIST and CIFAR datasets.Number of nodesModel/datasetDelay time (ms)Local node overheadVerifier node overhead2MLP/MNIST6–7Baseline (0%)Baseline (0%)4MLP/MNIST8–9+5–10%+30–40%6MLP/MNIST10–11+10–12%+60–70%8MLP/MNIST12–13+15%+100–120%2CNN/CIFAR6–7Baseline (0%)Baseline (0%)4CNN/CIFAR8–9+5–10%+30–40%6CNN/CIFAR10–11+10–12%+60–70%8CNN/CIFAR12–13+15%+100–120% Table 6Network size impact on communication time and computational overhead for MLP and CNN on MNIST and CIFAR datasets.Number of nodesModel/datasetDelay time (ms)Local node overheadVerifier node overhead2MLP/MNIST6–7Baseline (0%)Baseline (0%)4MLP/MNIST8–9+5–10%+30–40%6MLP/MNIST10–11+10–12%+60–70%8MLP/MNIST12–13+15%+100–120%2CNN/CIFAR6–7Baseline (0%)Baseline (0%)4CNN/CIFAR8–9+5–10%+30–40%6CNN/CIFAR10–11+10–12%+60–70%8CNN/CIFAR12–13+15%+100–120% Network size impact on communication time and computational overhead for MLP and CNN on MNIST and CIFAR datasets. As summarized in Table 6, the impact of network size on communication time and computational overhead for MLP on the MNIST dataset and CNN on the CIFAR dataset reveals important trends. The delay time increases predictably with the number of nodes, ranging from 6 to 13 ms as the number of nodes increases from 2 to 8 for both MLP and CNN models. This linear growth in communication time remains manageable and does not pose a major issue for system scalability. On the other hand, the local node overhead grows more gradually, by as much as 15% at most up to 8 nodes. The small increase in local node overhead indicates that local tasks, such as model training and cryptographic processes, are only minimally affected as the number of nodes increases However, when scaling up to 8 nodes from a baseline of 2 nodes, the overhead of the verifier node increases to +100–120%. This significant growth suggests that the verifier node becomes a scalability bottleneck. Introducing a multi-verifier ZKP approach46 could help reduce the load on a single verifier by distributing the verification tasks among multiple nodes and enables better scalability. This approach would enable ProxyZKP to maintain the advantages of decentralized learning without facing performance bottlenecks as the network grows. Comparative analysis: proxy model zero-knowledge verification system In the ProxyZKP, where each local client node has a private model coupled to a proxy multivariate polynomial model, selecting the right cryptographic proof approach is crucial for efficient communication of gradient updates in addition to integrity verification. In the two-stage proof scheme, multivariate polynomials are decomposed into multiple univariate polynomials, resulting in simpler cryptographic computations. Due to the simplicity of univariate polynomials, the multi-scalar multiplications47 required in elliptic curve operations for commitments and proofs are smaller and less computationally intensive. ProxyZKP can independently generate proofs for each univariate polynomial, enabling concurrent proof generation and verification through multi-threaded processing. To provide more context on ProxyZKP’s performance, we compare it with establish ZKP methods, including Bulletproofs18 and zk-SNARKs17. Open-source Python libraries such as PyBulletproofs48 and PySNARK49 are used for benchmarking these ZKP schemes.Table 7Comparison of univariate polynomial decomposition, zk-SNARKs, and bulletproofs for federated learning (with sigma protocol impact and multivariate polynomial).AspectUnivariate polynomial decomposition (with sigma protocol)zk-SNARKsBulletproofsNumber of variables784784784Number of terms784 univariate polynomials (3 terms each)308,505 terms308,505 termsExponentiations3920 exponentiation308,505 exponentiations617,148 exponentiationsSigma protocol for consistency checkProves consistency between univariate and multivariate polynomials, efficient proof of agreement without full computationNot neededNot neededProof generation time600 milliseconds (including sigma protocol overhead)7 s12 sProof size50KB (including sigma protocol impact on proof size)300 bytes (trusted setup excluded)2700 bytes (logarithmic)ScalabilityGood scalability due to parallelization, sigma protocol ensures correctnessLimited scalabilityLogarithmic scalability Table 7Comparison of univariate polynomial decomposition, zk-SNARKs, and bulletproofs for federated learning (with sigma protocol impact and multivariate polynomial).AspectUnivariate polynomial decomposition (with sigma protocol)zk-SNARKsBulletproofsNumber of variables784784784Number of terms784 univariate polynomials (3 terms each)308,505 terms308,505 termsExponentiations3920 exponentiation308,505 exponentiations617,148 exponentiationsSigma protocol for consistency checkProves consistency between univariate and multivariate polynomials, efficient proof of agreement without full computationNot neededNot neededProof generation time600 milliseconds (including sigma protocol overhead)7 s12 sProof size50KB (including sigma protocol impact on proof size)300 bytes (trusted setup excluded)2700 bytes (logarithmic)ScalabilityGood scalability due to parallelization, sigma protocol ensures correctnessLimited scalabilityLogarithmic scalability Comparison of univariate polynomial decomposition, zk-SNARKs, and bulletproofs for federated learning (with sigma protocol impact and multivariate polynomial). Table 7 presents the main findings regarding the performance of PolyMLP. By examining these aspects, it becomes clear why the two-stage proof scheme (univariate polynomial decomposition) may be the most suitable for this use case. Parallelization When PolyMLP is used under ProxyZKP, each node processes a multivariate polynomial with 784 variables. In the two-stage proof scheme, this multivariate polynomial is decomposed into 784 univariate quadratic polynomials, each representing a single variable, while the others are treated as constants. Since each univariate polynomial is independent, the two-stage proof scheme can distribute the computation across multiple threads, making it highly parallelizable. This parallelization greatly reduces the computational workload. The time required for proof generation in this approach benefits from this parallelization. On a 64-thread processor, proof generation for all 784 univariate polynomials takes approximately 600 milliseconds. This makes the univariate approach particularly efficient for decentralized federated learning, where real-time communication of updates is critical. In contrast, zk-SNARKs and Bulletproofs handle the entire multivariate polynomial directly, with 308,505 terms. While zk-SNARKs and Bulletproofs allow for some degree of parallelization during certain elliptic curve operations, they lack the modular, parallel structure of the univariate approach. As a result, zk-SNARKs and Bulletproofs take about 7 seconds and 12 seconds, respectively, to generate proofs on the same hardware, which makes them notably slower in situations that require rapid exchanges between nodes. Cryptographic operations Exponentiations in the proof generation process involve raising a group element, such as a generator \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$g$$\end{document}, to a power, typically a secret value or a polynomial coefficient, within a cryptographic group, often an elliptic curve or a finite field. In zero-knowledge proof systems like zk-SNARKs, Bulletproofs, or the two-stage proof scheme, exponentiations play a central role. They are used to commit to polynomial coefficients or evaluations, such as when computing \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$g^a$$\end{document}, where \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$a$$\end{document} represents a value or a polynomial evaluation. These commitments allow the prover to convince the verifier of the correctness of a statement without revealing the underlying data. Exponentiations are computationally demanding, but they are vital to the security of the proof, ensuring that commitments are binding and unforgeable, thus maintaining the overall integrity and privacy of the proof system. In terms of exponentiations, Table 7 reveals distinct differences in the computational demands of each approach. For the two-stage proof scheme(univariate polyomial appaorach), the prover needs to commit to each univariate polynomial’s evaluation, which requires 2304 exponentiations(3 for each of the 784 univariate polynomials). Additionally, to ensure consistency between the evaluations of the univariate polynomials and the full multivariate polynomial, Sigma protocol requires one more exponentiation is required for the commitment to the multivariate polynomial at the evaluation point. This brings the total number of exponentiations to 3920. The workload remains manageable and parallelizable due to the independent processing of each univariate polynomial. In contrast, zk-SNARKs and Bulletproofs require 308,505 and 617,148 exponentiations, respectively, to handle the entire multivariate polynomial at once. This makes them significantly more computationally expensive compared to the univariate decomposition approach. The combination of highly parallelizable computations and fewer cryptographic operations gives the univariate polynomial approach a significant computational workload advantage over zk-SNARKs and Bulletproofs. This makes the two-stage proof scheme particularly efficient for scenarios that require rapid proof generation and frequent exchanges between nodes, such as in decentralized federated learning environments. Proof size Another important factor for ProxyZKP is proof size, as it directly affects network bandwidth and storage requirements. The univariate polynomial decomposition approach generates proofs for each of the 784 univariate polynomials, resulting in a linear growth of proof size. For 784 univariate polynomials, each requiring 2 group elements (one for the commitment and one for the evaluation proof), the total proof size is 50 KB. This is significantly larger than the 300 bytes required by zk-SNARKs, which provide a constant proof size regardless of the complexity of the polynomial. However, zk-SNARKs come with a much higher computational cost, which makes them less attractive for systems prioritizing parallelization and speed. Bulletproofs offer a middle ground with logarithmic proof size scaling. For a polynomial with 308,505 terms, the Bulletproof proof size is approximately 2700 bytes. This is significantly smaller than the proof size for the univariate polynomial decomposition approach but larger than zk-SNARKs. While Bulletproofs are more scalable in terms of proof size, they still do not match the univariate approach’s speed in parallelized environments. Scalability Finally, scalability is a key consideration for ProxyZKP. The univariate polynomial decomposition approach scales well in terms of computational workload because each univariate polynomial can be handled independently. This makes it ideal for systems with a growing number of variables, as the workload can be distributed across multiple processor threads. However, the proof size grows linearly, which could become a limitation in systems with very large numbers of variables or polynomials. zk-SNARKs, on the other hand, are highly scalable in terms of proof size, as they remain constant regardless of the number of variables or terms. However, zk-SNARKs do not scale as well in terms of computational workload, especially when dealing with larger polynomials or more complex models. Bulletproofs provide strong scalability in both proof size and computational workload. The logarithmic growth in proof size makes them more efficient than the univariate approach for larger polynomials, while their computational workload can still be distributed across multiple threads, although not as efficiently as in the univariate approach. Conclusion The ProxyZKP framework combines Zero-Knowledge Proofs with polynomial proxy models to verify the integrity of model training at each local node in a decentralized federated machine-learning network. The two-stage proof scheme allows gradient updates be verified in highly parallelization manner, leading to fast proof generation and verification. While the proof size grows linearly with the number of variables, the computational efficiency of this approach makes it ideal in distributed settings. By comparison, zk-SNARKs offer small, constant proof sizes but are less practical due to their high computational cost and limited parallelization. Bulletproofs, with logarithmic proof size and better parallelization potential, offer a balanced solution for larger networks, but they still fall short of the univariate approach in terms of speed and parallelization. Overall, the two-stage proof scheme, integrated with the ProxyZKP framework, provides a highly efficient and secure solution for decentralized federated learning, maintaining both computational integrity and data privacy.