REVIEW 3 major objections 4 minor 42 references
zkVC: Fast Zero-Knowledge Proof for Private and Verifiable Computing
T0 review · 3 major / 4 minor · reviewed 2026-08-16 · deepseek-v4-flash
Pith's one-line read zkVC reduces ZKP proving time for matrix multiplication by encoding the product as a polynomial evaluation, claiming 12x speedup and enabling verifiable Transformer models.
desk verdict zkVC's 12x speedup for zero-knowledge matrix multiplication comes from a single-point polynomial check with no soundness argument; the encoding trick is clever but the paper is not a sound cryptographic construction as written. read the letter →
The pith
A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.
The reading
Extended reading notes
Core claim
The CRPC transformation (Section III.A) reduces the constraint complexity of zero-knowledge matrix multiplication from O(n^3) to O(n), and the paper reports a 12.5x reduction in proof time over vanilla groth16. The generalized identity is: sum_{i,j} y_{ij} Z^{i b + j} = sum_k (sum_i x_{ik} Z^{i b})(sum_j w_{kj} Z^j). If sound, this makes verifiable Transformer inference practical, with the paper claiming a 15x runtime reduction on ViT models.
Load-bearing premise
The soundness of CRPC depends on the random evaluation point Z being unknown to the prover at witness-selection time and on the R1CS circuit being fixed even though its coefficients are powers of Z. The paper never specifies whether Z is a public Fiat-Shamir challenge, a hidden setup trapdoor, or a fixed constant (Section III.A). If Z is public and fixed, a malicious prover can choose Y such that the polynomial identity holds at that single point while Y != XW; if Z is secret, the circuit's constraint matrices depend on the secret and the standard groth16/Spartan compilation is not justified. The paper also omits any Schwartz-Zippel or adversary argument.
Signed reviews
Editorial analysis
A structured set of objections, weighed in public.
Referee Report
Summary. The manuscript presents zkVC, a set of optimizations for zero-knowledge proofs of matrix multiplication and Transformer inference. The main component, Constraint-reduced Polynomial Circuit (CRPC), is introduced in Section III.A to replace the a·b·n multiplication constraints of Y = X·W with n constraints using a polynomial identity evaluated at an intermediate value Z; the second component, Prefix-Sum Query (PSQ), in Section III.B reduces the number of left-wire variables for accumulation. The authors implement the optimizations on top of Groth16 and Spartan and report about 12x faster proving for matrix multiplication and about 15x faster end-to-end ViT proving, with an ablation study and accuracy comparisons across CIFAR-10, Tiny-ImageNet, ImageNet, and GLUE tasks.
Significance. If the CRPC transformation were sound, this would be a significant step toward practical zero-knowledge verifiable Transformer inference, because matrix multiplication is the dominant proving cost and the reported speedups are large. The paper includes a concrete implementation, an ablation study, and comparisons against several prior systems, and it makes the code available, which are all strengths. However, the central cryptographic claim is not established. As written, CRPC verifies a single evaluation of a polynomial identity, not the a·b·n scalar products of the original matrix multiplication, and the manuscript does not specify how Z is generated or provide any Schwartz-Zippel-style soundness analysis. The claimed O(n) constraint complexity therefore does not come with a demonstrated security guarantee, and the experimental speedups are measured against a relation whose soundness is in question.
major comments (3)
- [Section III.A, generalized CRPC identity] The reduction replaces a·b·n constraints by the single equation sum_{i,j} y_ij Z^{ib+j} = sum_k (sum_i x_ik Z^{ib})(sum_j w_kj Z^j), but the paper never states how Z is chosen. If Z is a public constant, a malicious prover can add any nonzero error matrix E satisfying sum_{i,j} E_ij Z^{ib+j} = 0 and submit Y = XW + E, and the CRPC check will pass although Y != XW. If Z is a secret setup value, the constraint matrices depend on Z and the standard Groth16/Spartan compilation to a fixed R1CS is not justified. If Z is intended as a Fiat-Shamir challenge, no challenge-binding protocol or commitment to the witness appears anywhere. None of the three readings yields a sound fixed-R1CS construction with the claimed O(n) complexity.
- [Section III.A, soundness of the one-point check] The paper's own text observes that summing all y_ij values compromises soundness and then claims that CRPC 'addresses this issue,' but the only difference between the naive sum and the CRPC equation is the weighting of the entries by powers of Z. A single weighted sum is still one linear equation in the a·b output entries; without a random challenge that is unknown to the prover at witness-selection time, this cannot enforce the a·b·n individual product relations. No Schwartz-Zippel argument, adversary definition, or security theorem is supplied, so the central claim of Section III.A is unsupported.
- [Sections II-III (protocol specification)] The manuscript uses the standard language of Gen/Prove/Verify for zk-SNARKs but never defines these algorithms for zkVC. In particular, there is no formal statement of the relation R that CRPC is supposed to prove, no completeness theorem, no soundness theorem, and no zero-knowledge claim for the optimized circuit. For a paper whose contribution is a cryptographic optimization, these are load-bearing omissions rather than presentation issues.
minor comments (4)
- [Section V.A] In the ablation discussion, the text refers to 'CRCP' instead of 'CRPC' in the sentence 'the enhancement is more significant when PSQ is coupled with CRCP.'
- [Section III.A] The boxed example for the 'another possible transformation' uses a '≠' sign between the weighted sum and the product of row-column polynomials; if the intent is to exhibit an invalid transformation, this should be stated explicitly in the surrounding text.
- [Section III.C] The SoftMax approximation has two free parameters, the clipping threshold T and the Taylor exponent n, but the paper does not report how their values were chosen or how sensitive the accuracy and proving time are to them.
- [References] References [12] and [30] cite the same work (Wahby et al., 'Doubly-efficient zkSNARKs without trusted setup'); one duplicate should be removed.
Circularity Check
No material circularity: CRPC is an algebraic constraint-encoding identity and the speedups are direct measurements; self-citations are background only.
full rationale
The central derivation in Section III.A is an algebraic identity: if Y = XW, then sum_{i,j} y_{ij} Z^{ib+j} equals sum_k (sum_i x_{ik} Z^{ib})(sum_j w_{kj} Z^j), and coefficient-wise equality of the two polynomials is equivalent to Y = XW. This is a self-contained mathematical transformation, not a fitted parameter renamed as a prediction. The reported 12x/15x improvements are measured proving times from implemented systems (Table II, Figure 6), not quantities forced by construction. The self-citation cluster [20]-[29] appears only in the background paragraph contrasting homomorphic encryption with zero-knowledge proofs; none of those citations carries the burden of the CRPC, PSQ, or Transformer results. The paper's own statement that summing all y_ij 'compromises the soundness' and that CRPC 'addresses this issue' is a correctness claim about the constraint-reduction transformation, and the possible unsoundness of checking the identity at a single public Z is a security-analysis gap, not a circular definition. No step in the derivation reduces to its own inputs by construction, and no load-bearing self-citation chain is present. The low score reflects only the minor self-citation cluster in the background section, which does not affect the independent content of the paper's central claims.
Assumptions & free parameters
free parameters (2)
- SoftMax clipping threshold T
- Taylor exponent n in (1+x/2^n)^(2^n)
assumptions (3)
- standard math Schwartz-Zippel lemma bounds the probability of a false polynomial identity passing at a random point
- domain assumption The random challenge Z is generated in a way unknown to the prover at witness-selection time
- domain assumption R1CS constraint matrices are fixed and independent of the instance
Cite this review
Pith. "Pith review of zkVC: Fast Zero-Knowledge Proof for Private and Verifiable Computing." pith.science (2026). https://pith.science/paper/42RIP6Q2
@misc{pith2026250412217,
author = {Pith},
title = {Pith review of: zkVC: Fast Zero-Knowledge Proof for Private and Verifiable Computing},
year = {2026},
howpublished = {\url{https://pith.science/paper/42RIP6Q2}},
note = {Machine review of arXiv:2504.12217}
}
read the original abstract
In the context of cloud computing, services are held on cloud servers, where the clients send their data to the server and obtain the results returned by server. However, the computation, data and results are prone to tampering due to the vulnerabilities on the server side. Thus, verifying the integrity of computation is important in the client-server setting. The cryptographic method known as Zero-Knowledge Proof (ZKP) is renowned for facilitating private and verifiable computing. ZKP allows the client to validate that the results from the server are computed correctly without violating the privacy of the server's intellectual property. Zero-Knowledge Succinct Non-Interactive Argument of Knowledge (zkSNARKs), in particular, has been widely applied in various applications like blockchain and verifiable machine learning. Despite their popularity, existing zkSNARKs approaches remain highly computationally intensive. For instance, even basic operations like matrix multiplication require an extensive number of constraints, resulting in significant overhead. In addressing this challenge, we introduce \textit{zkVC}, which optimizes the ZKP computation for matrix multiplication, enabling rapid proof generation on the server side and efficient verification on the client side. zkVC integrates optimized ZKP modules, such as Constraint-reduced Polynomial Circuit (CRPC) and Prefix-Sum Query (PSQ), collectively yielding a more than 12-fold increase in proof speed over prior methods. The code is available at https://github.com/UCF-Lou-Lab-PET/zkformer
Figures
Figures from the paper (3 more)
Reference graph
Works this paper leans on
-
[1]
Pinocchio: Nearly practical verifiable computation,
B. Parno, J. Howell, C. Gentry, and M. Raykova, “Pinocchio: Nearly practical verifiable computation,”Communications of the ACM, vol. 59, no. 2, pp. 103–112, 2016
work page 2016
-
[2]
On the size of pairing-based non-interactive arguments,
J. Groth, “On the size of pairing-based non-interactive arguments,” in Advances in Cryptology–EUROCRYPT 2016: 35th Annual International Conference on the Theory and Applications of Cryptographic Techniques, Vienna, Austria, May 8-12, 2016, Proceedings, Part II 35. Springer, 2016, pp. 305–326
work page 2016
-
[3]
Attention is all you need,
A. Vaswani, N. Shazeer, N. Parmar, J. Uszkoreit, L. Jones, A. N. Gomez, Ł. Kaiser, and I. Polosukhin, “Attention is all you need,”Advances in neural information processing systems, vol. 30, 2017
2017
-
[4]
An image is worth 16x16 words: Transformers for image recognition at scale,
A. Dosovitskiy, L. Beyer, A. Kolesnikov, D. Weissenborn, X. Zhai, T. Unterthiner, M. Dehghani, M. Minderer, G. Heigold, S. Gellyet al., “An image is worth 16x16 words: Transformers for image recognition at scale,” arXiv preprint arXiv:2010.11929, 2020
arXiv 2010
-
[5]
Imagenet: A large-scale hierarchical image database,
J. Deng, W. Dong, R. Socher, L.-J. Li, K. Li, and L. Fei-Fei, “Imagenet: A large-scale hierarchical image database,” in2009 IEEE conference on computer vision and pattern recognition. Ieee, 2009, pp. 248–255
2009
-
[6]
vcnn: Verifiable convolutional neural network based on zk-snarks,
S. Lee, H. Ko, J. Kim, and H. Oh, “vcnn: Verifiable convolutional neural network based on zk-snarks,”IEEE Transactions on Dependable and Secure Computing, 2024
2024
-
[7]
Zkcnn: Zero knowledge proofs for convolutional neural network predictions and accuracy,
T. Liu, X. Xie, and Y. Zhang, “Zkcnn: Zero knowledge proofs for convolutional neural network predictions and accuracy,” inProceedings of the 2021 ACM SIGSAC Conference on Computer and Communications Security, 2021, pp. 2968–2985
work page 2021
-
[8]
Scaling up trustless dnn inference with zero-knowledge proofs,
D. Kang, T. Hashimoto, I. Stoica, and Y. Sun, “Scaling up trustless dnn inference with zero-knowledge proofs,” 2022
work page 2022
Show all 42 references
-
[9]
pvcnn: Privacy-preserving and verifiable convolutional neural network testing,
J. Weng, J. Weng, G. Tang, A. Yang, M. Li, and J.-N. Liu, “pvcnn: Privacy-preserving and verifiable convolutional neural network testing,” IEEE Transactions on Information Forensics and Security, vol. 18, pp. 2218–2233, 2023
2023
-
[10]
Sonic: Zero- knowledge snarks from linear-size universal and updatable structured reference strings,
M. Maller, S. Bowe, M. Kohlweiss, and S. Meiklejohn, “Sonic: Zero- knowledge snarks from linear-size universal and updatable structured reference strings,” inProceedings of the 2019 ACM SIGSAC Conference on Computer and Communications Security, 2019, pp. 2111–2128
2019
-
[11]
Marlin: Preprocessing zksnarks with universal and updatable srs,
A. Chiesa, Y. Hu, M. Maller, P. Mishra, N. Vesely, and N. Ward, “Marlin: Preprocessing zksnarks with universal and updatable srs,” inAdvances in Cryptology–EUROCRYPT 2020: 39th Annual International Conference on the Theory and Applications of Cryptographic Techniques, Zagreb, ...
2020
-
[13]
Spartan: Efficient and general-purpose zksnarks without trusted setup,
S. Setty, “Spartan: Efficient and general-purpose zksnarks without trusted setup,” inAnnual International Cryptology Conference. Springer, 2020, pp. 704–737
2020
-
[14]
Safetynets: Verifiable execution of deep neural networks on an untrusted cloud,
Z. Ghodsi, T. Gu, and S. Garg, “Safetynets: Verifiable execution of deep neural networks on an untrusted cloud,”Advances in Neural Information Processing Systems, vol. 30, 2017
2017
-
[15]
Efficient proof composition for verifiable computation,
J. Keuffer, R. Molva, and H. Chabanne, “Efficient proof composition for verifiable computation,” in Computer Security - 23rd European Symposium on Research in Computer Security, ESORICS 2018, Barcelona, Spain, September 3-7, 2018, Proceedings, Part I, ser. Lecture Notes in Com...
2018
-
[16]
Veriml: Enabling integrity assurances and fair payments for machine learning as a service,
L. Zhao, Q. Wang, C. Wang, Q. Li, C. Shen, and B. Feng, “Veriml: Enabling integrity assurances and fair payments for machine learning as a service,”IEEE Trans. Parallel Distributed Syst., vol. 32, no. 10, pp. 2524–2540, 2021
2021
-
[17]
Zen: An optimizing compiler for verifiable, zero-knowledge neural network inferences,
B. Feng, L. Qin, Z. Zhang, Y. Ding, and S. Chu, “Zen: An optimizing compiler for verifiable, zero-knowledge neural network inferences,” Cryptology ePrint Archive, Paper 2021/087, 2021
2021
-
[18]
Interactive oracle proofs,
E. Ben-Sasson, A. Chiesa, and N. Spooner, “Interactive oracle proofs,” in Theory of Cryptography: 14th International Conference, TCC 2016-B, Beijing, China, October 31-November 3, 2016, Proceedings, Part II 14. Springer, 2016, pp. 31–60
2016
-
[19]
Transparent snarks from dark compilers,
B. Bünz, B. Fisch, and A. Szepieniec, “Transparent snarks from dark compilers,” inAdvances in Cryptology–EUROCRYPT 2020: 39th Annual International Conference on the Theory and Applications of Crypto- graphic Techniques, Zagreb, Croatia, May 10–14, 2020, Proceedings, Part I 39....
2020
-
[20]
She: A fast and accurate deep neural network for encrypted data,
Q. Lou and L. Jiang, “She: A fast and accurate deep neural network for encrypted data,”Advances in neural information processing systems, vol. 32, 2019
2019
-
[21]
Primer: Fast private transformer inference on encrypted data,
M. Zheng, Q. Lou, and L. Jiang, “Primer: Fast private transformer inference on encrypted data,” in2023 60th ACM/IEEE Design Automation Conference (DAC). IEEE, 2023, pp. 1–6
2023
-
[22]
Safenet: A secure, accurate and fast neural network inference,
Q. Lou, Y. Shen, H. Jin, and L. Jiang, “Safenet: A secure, accurate and fast neural network inference,” inInternational Conference on Learning Representations, 2021
2021
-
[23]
Hemet: A homomorphic-encryption-friendly privacy-preserving mobile neural network architecture,
Q. Lou and L. Jiang, “Hemet: A homomorphic-encryption-friendly privacy-preserving mobile neural network architecture,” inInternational conference on machine learning. PMLR, 2021, pp. 7102–7110
2021
-
[24]
vfhe: Verifiable fully homomorphic encryption with blind hash,
Q. Lou, M. Santriaji, A. W. B. Yudha, J. Xue, and Y. Solihin, “vfhe: Verifiable fully homomorphic encryption with blind hash,”arXiv preprint arXiv:2303.08886, 2023
2023 arXiv
-
[25]
Dataseal: Ensuring the verifiability of private computation on encrypted data,
M. H. Santriaji, J. Xue, Y. Zhang, Q. Lou, and Y. Solihin, “Dataseal: Ensuring the verifiability of private computation on encrypted data,” in 2025 IEEE Symposium on Security and Privacy (SP). IEEE Computer Society, 2024, pp. 78–78
2025
-
[26]
Tfhe-coder: Evaluating llm- agentic fully homomorphic encryption code generation,
M. Kumar, J. Xue, M. Zheng, and Q. Lou, “Tfhe-coder: Evaluating llm- agentic fully homomorphic encryption code generation,”arXiv preprint arXiv:2503.12217, 2025
2025 arXiv
-
[27]
Heprune: Fast private training of deep neural networks with encrypted data pruning,
Y. Zhang, M. Zheng, Y. Shang, X. Chen, and Q. Lou, “Heprune: Fast private training of deep neural networks with encrypted data pruning,” in Advances in Neural Information Processing Systems, vol. 37. Curran Associates, Inc., 2024, pp. 51063–51084
2024
-
[28]
Cipherprune: Efficient and scalable private transformer inference,
Y. Zhang, J. Xue, M. Zheng, M. Xie, M. Zhang, L. Jiang, and Q. Lou, “Cipherprune: Efficient and scalable private transformer inference,”arXiv preprint arXiv:2502.16782, 2025
2025 arXiv
-
[29]
Trinity: A general purpose fhe accelerator,
X. Deng, S. Fan, Z. Hu, Z. Tian, Z. Yang, J. Yu, D. Cao, D. Meng, R. Hou, M. Liet al., “Trinity: A general purpose fhe accelerator,” in 2024 57th IEEE/ACM International Symposium on Microarchitecture (MICRO). IEEE, 2024, pp. 338–351
2024
-
[30]
Doubly- efficient zksnarks without trusted setup,
R. S. Wahby, I. Tzialla, A. Shelat, J. Thaler, and M. Walfish, “Doubly- efficient zksnarks without trusted setup,” in2018 IEEE Symposium on Security and Privacy (SP). IEEE, 2018, pp. 926–943
2018
-
[31]
How to prove yourself: Practical solutions to identification and signature problems,
A. Fiat and A. Shamir, “How to prove yourself: Practical solutions to identification and signature problems,” inConference on the theory and application of cryptographic techniques. Springer, 1986, pp. 186–194
1986
-
[32]
Escaping the big data paradigm with compact transformers,
A. Hassani, S. Walton, N. Shah, A. Abuduweili, J. Li, and H. Shi, “Escaping the big data paradigm with compact transformers,”arXiv preprint arXiv:2104.05704, 2021
2021 arXiv
-
[33]
Mpcvit: Searching for mpc-friendly vision transformer with heteroge- neous attention,
W. Zeng, M. Li, W. Xiong, W. Lu, J. Tan, R. Wang, and R. Huang, “Mpcvit: Searching for mpc-friendly vision transformer with heteroge- neous attention,”arXiv preprint arXiv:2211.13955, 2022
2022 arXiv
-
[34]
Swintransformer:Hierarchicalvisiontransformerusingshiftedwindows,
Z. Liu, Y. Lin, Y. Cao, H. Hu, Y. Wei, Z. Zhang, S. Lin, and B. Guo, “Swintransformer:Hierarchicalvisiontransformerusingshiftedwindows,” in Proceedings of the IEEE/CVF international conference on computer vision, 2021, pp. 10012–10022
2021
-
[35]
Metaformer is actually what you need for vision,
W. Yu, M. Luo, P. Zhou, C. Si, Y. Zhou, X. Wang, J. Feng, and S. Yan, “Metaformer is actually what you need for vision,” inProceedings of the IEEE/CVF conference on computer vision and pattern recognition, 2022, pp. 10819–10829
2022
-
[36]
Glue: A multi-task benchmark and analysis platform for natural language understanding,
A. Wang, A. Singh, J. Michael, F. Hill, O. Levy, and S. R. Bowman, “Glue: A multi-task benchmark and analysis platform for natural language understanding,” arXiv preprint arXiv:1804.07461, 2018
2018 arXiv
-
[37]
libsnark,
“libsnark,” https://github.com/scipr-lab/libsnark
-
[38]
Efficient attention: Attention with linear complexities,
Z. Shen, M. Zhang, H. Zhao, S. Yi, and H. Li, “Efficient attention: Attention with linear complexities,” 2020
2020
-
[39]
Non-local neural networks,
X. Wang, R. Girshick, A. Gupta, and K. He, “Non-local neural networks,” in Proceedings of the IEEE conference on computer vision and pattern recognition, 2018, pp. 7794–7803
2018
-
[40]
Fnet: Mixing tokens with fourier transforms,
J. Lee-Thorp, J. Ainslie, I. Eckstein, and S. Ontanon, “Fnet: Mixing tokens with fourier transforms,”arXiv preprint arXiv:2105.03824, 2021
2021 arXiv
-
[41]
Darts: Differentiable architecture search,
H. Liu, K. Simonyan, and Y. Yang, “Darts: Differentiable architecture search,” arXiv preprint arXiv:1806.09055, 2018
2018 arXiv
-
[42]
NITI: Training integer neural networks using integer-only arithmetic,
M. Wang, S. Rasoulinezhad, P. H. W. Leong, and H. K.-H. So, “NITI: Training integer neural networks using integer-only arithmetic,”IEEE Transactions on Parallel and Distributed Systems, vol. 33, no. 11, pp. 3249–3261, nov 2022
2022
-
[43]
Recursive proof composition without a trusted setup,
S. Bowe, J. Grigg, and D. Hopwood, “Recursive proof composition without a trusted setup,”Cryptology ePrint Archive, 2019
2019
Reviewed August 16, 2026 · model on record in the stance chip above.
Discussion (0). Continue with ORCID to comment.