CP-SuperSpartan: commit-and-prove SNARKs for customizable constraint systems

Abstract

Commit-and-prove succinct non-interactive arguments of knowledge (CP-SNARKs) are an important class of SNARKs that allow proving the knowledge of a witness committed beforehand. They are crucial in proving composite statements that combine algebraic and non-algebraic statements. However, existing CP-SNARKs only support constraint systems with degree-2 gates, limiting their ability to express non-algebraic statements succinctly. We propose a new family of CP-SNARKs for Customizable Constraint Systems. The new family, named CP-SuperSpartan, supports high-degree gates, eliminates expensive fast Fourier transform operations and supports a general commit-and-prove relation including multiple commitments to different slots of the witness. CP-SuperSpartan has several instantiations based on different multilinear polynomial commitment schemes (PCS). 1) When using pairing-based PCS, CP-SuperSpartan provides the same universally updatable setup as LegoSNARK (CCS’19), but it reduces the proof size and verifier complexity from O({\log }^2|C|) to O(\log |C|) while maintaining the same prover complexity, where |C| is the circuit size. 2) When using discrete-logarithm-based PCS, CP-SuperSpartan provides a transparent setup and achieves O(\log |C|) proof size while the smallest proof size of existing transparent CP-SNARKs is O({\log }^{O(1)}|C|). 3) When using PCS based on interactive oracle proof of proximity, CP-SuperSpartan provides a transparent setup and firstly achieves O(|C|) prover complexity, O(\sqrt{|C|}) proof size and verifier complexity while the number of public-key operations for both the prover and verifier is independent of |C|.

Graphical abstract

Keywords

zero-knowledge proofs / SNARKs / CP-SNARKs / composite statements / customizable constraint systems

References

[1] Goldwasser S, Micali S, Rackoff C. The knowledge complexity of interactive proof-systems. In: Proceedings of the 17th Annual ACM Symposium on Theory of Computing. 1985, 291−304

[2] Kilian J. A note on efficient zero-knowledge proofs and arguments (extended abstract). In: Proceedings of the 24th Annual ACM Symposium on Theory of Computing. 1992, 723−732

[3] Micali S. CS proofs. In: Proceedings of the 35th Annual Symposium on Foundations of Computer Science. 1994, 436−453

[4] Campanelli M, Fiore D, Querol A. LegoSNARK: modular design and composition of succinct zero-knowledge proofs. In: Proceedings of 2019 ACM SIGSAC Conference on Computer and Communications Security. 2019, 2075−2092

[5] Cramer R. Modular design of secure yet practical cryptographic protocols. University of Amsterdam, Dissertation, 1997

[6] Thaler J . Proofs, arguments, and zero-knowledge. Foundations and Trends® in Privacy and Security, 2022, 4( 2−4): 117–660

[7] Agrawal S, Ganesh C, Mohassel P. Non-interactive zero-knowledge proofs for composite statements. In: Proceedings of the 38th Annual International Cryptology Conference on Advances in Cryptology. 2018, 643−673

[8] Chase M, Ganesh C, Mohassel P. Efficient zero-knowledge proof of algebraic and non-algebraic statements with applications to privacy preserving credentials. In: Proceedings of the 36th Annual International Cryptology Conference on Advances in Cryptology. 2016, 499−530

[9] Chen B, Bünz B, Boneh D, Zhang Z. HyperPlonk: plonk with linear-time prover and high-degree custom gates. In: Proceedings of the 42nd Annual International Conference on the Theory and Applications of Cryptographic Techniques. 2023, 499−530

[10] Benarroch D, Campanelli M, Fiore D, Kim J, Lee J, Oh H, Querol A. Proposal: commit-and-prove zero-knowledge proof systems and extensions. In: Proceedings of the 4th ZKProof Workshop. 2021

[11] Backes M, Hanzlik L, Herzberg A, Kate A, Pryvalov I. Efficient non-interactive zero-knowledge proofs in cross-domains without trusted setup. In: Proceedings of the 22nd IACR International Conference on Practice and Theory of Public-Key Cryptography. 2019, 286−313

[12] Aranha D F, Bennedsen E M, Campanelli M, Ganesh C, Orlandi C, Takahashi A. ECLIPSE: enhanced compiling method for Pedersen-committed zkSNARK engines. In: Proceedings of the 25th IACR International Conference on Practice and Theory of Public-Key Cryptography. 2022, 584−614

[13] Campanelli M, Faonio A, Fiore D, Querol A, Rodríguez H. Lunar: a toolbox for more efficient universal and updatable zkSNARKs and commit-and-prove extensions. In: Proceedings of the 27th International Conference on the Theory and Application of Cryptology and Information Security. 2021, 3−33

[14] Zhang M, Chen Y, Yao C, Wang Z. Sigma protocols from verifiable secret sharing and their applications. In: Proceedings of the 29th International Conference on the Theory and Application of Cryptology and Information Security. 2023, 208−242

[15] Gennaro R, Gentry C, Parno B, Raykova M. Quadratic span programs and succinct NIZKs without PCPs. In: Proceedings of the 32nd Annual International Conference on the Theory and Applications of Cryptographic Techniques. 2013, 626−645

[16] Bootle J, Cerulli A, Chaidos P, Groth J, Petit C. Efficient zero-knowledge arguments for arithmetic circuits in the discrete log setting. In: Proceedings of the 35th Annual International Conference on the Theory and Applications of Cryptographic Techniques. 2016, 327−357

[17] Ariel Gabizon A, Williamson Z J, Ciobotaru O. PLONK: permutations over Lagrange-bases for oecumenical noninteractive arguments of knowledge. 2019, Cryptology ePrint Archive, Paper 2019/953

[18] Setty S, Thaler J, Wahby R. Customizable constraint systems for succinct arguments. 2023, Cryptology ePrint Archive, Paper 2023/552

[19] Ben-Sasson E, Bentov I, Horesh Y, Riabzev M. Scalable zero knowledge with no trusted setup. In: Proceedings of the 39th Annual International Cryptology Conference on Advances in Cryptology. 2019, 701−732

[20] Bootle J, Chiesa A, Hu Y, Orrú M. Gemini: elastic SNARKs for diverse environments. In: Proceedings of the 41st Annual International Conference on the Theory and Applications of Cryptographic Techniques. 2022, 427−457

[21] Golovnev A, Lee J, Setty S, Thaler J, Wahby R S. Brakedown: linear-time and field-agnostic SNARKs for R1CS. In: Proceedings of the 43rd Annual International Cryptology Conference on Advances in Cryptology. 2023, 193−226

[22] Setty S. Spartan: efficient and general-purpose zkSNARKs without trusted setup. In: Proceedings of the 40th Annual International Cryptology Conference on Advances in Cryptology. 2020, 704−737

[23] Xie T, Zhang Y, Song D. Orion: zero knowledge proof with linear prover time. In: Proceedings of the 42nd Annual International Cryptology Conference on Advances in Cryptology. 2022, 299−328

[24] Kate A, Zaverucha G M, Goldberg I. Constant-size commitments to polynomials and their applications. In: Proceedings of the 16th International Conference on the Theory and Application of Cryptology and Information Security. 2010, 177−194

[25] Ben-Sasson E, Bentov I, Horesh Y, Riabzev M. Fast reed-Solomon interactive oracle proofs of proximity. In: Proceedings of the 45th International Colloquium on Automata, Languages, and Programming. 2018, 14: 1−14: 17

[26] Papamanthou C, Shi E, Tamassia R. Signatures of correct computation. In: Proceedings of the 10th Theory of Cryptography Conference. 2013, 222−242

[27] Attema T, Cramer R. Compressed Σ-protocol theory and practical application to plug & play secure algorithmics. In: Proceedings of the 40th Annual International Cryptology Conference on Advances in Cryptology. 2020, 513−543

[28] Bünz B, Maller M, Mishra P, Tyagi N, Vesely P. Proofs for inner pairing products and applications. In: Proceedings of the 27th International Conference on the Theory and Application of Cryptology and Information Security. 2021, 65−97

[29] Lund C, Fortnow L, Karloff H J, Nisan N. Algebraic methods for interactive proof systems. In: Proceedings of the 31st Annual Symposium on Foundations of Computer Science. 1990, 2−10

[30] Tian H, Li J . A short non-delegatable strong designated verifier signature. Frontiers of Computer Science, 2014, 8( 3): 490–502

[31] Reddy B S, Reddy T U K . CompactChain: an efficient stateless chain for UTXO-model blockchain. Frontiers of Computer Science, 2024, 18( 2): 182806

[32] Liang H, Chen J . Non-interactive SM2 threshold signature scheme with identifiable abort. Frontiers of Computer Science, 2024, 18( 1): 181802

[33] Ying C, Jin H, Li J, Si X, Luo Y . Incentive mechanism design via smart contract in blockchain-based edge-assisted crowdsensing. Frontiers of Computer Science, 2025, 19( 3): 193802

[34] Sha J, Liu S . Delegable zk-SNARKs with proxies. Frontiers of Computer Science, 2024, 18( 5): 185812

[35] Kilian J. Uses of randomness in algorithms and protocols. Massachusetts Institute of Technology, Dissertation, 1989

[36] Canetti R, Lindell Y, Ostrovsky R, Sahai A. Universally composable two-party and multi-party secure computation. In: Proceedings of the 34th Annual ACM Symposium on Theory of Computing. 2002, 494−503

[37] Jawurek M, Kerschbaum F, Orlandi C. Zero-knowledge using garbled circuits: how to prove non-algebraic statements efficiently. In: Proceedings of 2013 ACM SIGSAC Conference on Computer & Communications Security. 2013, 955−966

[38] Giacomelli I, Madsen J, Orlandi C. ZKBoo: faster zero-knowledge for Boolean circuits. In: Proceedings of the 25th USENIX Security Symposium. 2016, 1069−1083

[39] Chase M, Derler D, Goldfeder S, Orlandi C, Ramacher S, Rechberger C, Slamanig D, Zaverucha G. Post-quantum zero-knowledge and signatures from symmetric-key primitives. In: Proceedings of 2017 ACM SIGSAC Conference on Computer and Communications Security. 2017, 1825−1842

[40] Ganesh C, Nair V, Sharma A. Dual polynomial commitment schemes and applications to commit-and-prove SNARKs. In: Proceedings of 2024 on ACM SIGSAC Conference on Computer and Communications Security. 2024, 884−898

[41] Orrù M, Kadianakis G, Maller M, Zaverucha G . Beyond the circuit: how to minimize foreign arithmetic in ZKP circuits. IACR Communications in Cryptology, 2025, 2( 1): 23

[42] Daza V, Ràfols C, Zacharakis A. Updateable inner product argument with logarithmic verifier and applications. In: Proceedings of the 23rd IACR International Conference on Practice and Theory of Public-Key Cryptography. 2020, 527−557

[43] Boneh D, Boyen X . Short signatures without random oracles and the SDH assumption in bilinear groups. Journal of Cryptology, 2008, 21( 2): 149–177

[44] Fuchsbauer G, Kiltz E, Loss J. The algebraic group model and its applications. In: Proceedings of the 38th Annual International Cryptology Conference on Advances in Cryptology. 2018, 33−62

[45] Attema T, Fehr S, Klooß M. Fiat-Shamir transformation of multi-round interactive proofs. In: Proceedings of the 20th International Conference on Theory of Cryptography. 2022, 113−142

[46] Wikström D . Special soundness in the random oracle model. IACR Communications in Cryptology, 2024, 1( 3): 26

[47] Cormode G, Mitzenmacher M, Thaler J. Practical verified computation with streaming interactive proofs. In: Proceedings of the 3rd Innovations in Theoretical Computer Science Conference. 2012, 90−112

[48] Bünz B, Fisch B, Szepieniec A. Transparent SNARKs from DARK compilers. In: Proceedings of the 39th Annual International Conference on the Theory and Applications of Cryptographic Techniques. 2020, 677−706

[49] Schwartz J T . Fast probabilistic algorithms for verification of polynomial identities. Journal of the ACM (JACM), 1980, 27( 4): 701–717

[50] Bünz B, Bootle J, Boneh D, Poelstra A, Wuille P, Maxwell G. Bulletproofs: short proofs for confidential transactions and more. In: Proceedings of 2018 IEEE Symposium on Security and Privacy. 2018, 315−334

[51] Wahby R S, Tzialla I, Shelat A, Thaler J, Walfish M. Doubly-efficient zkSNARKs without trusted setup. In: Proceedings of 2018 IEEE Symposium on Security and Privacy. 2018, 926−943

[52] Zeilberger H, Chen B, Fisch B. BaseFold: efficient field-agnostic polynomial commitment schemes from foldable codes. In: Proceedings of the 44th Annual International Cryptology Conference on Advances in Cryptology. 2024, 138−169

[53] Vu V, Setty S, Blumberg A J, Walfish M. A hybrid architecture for interactive verifiable computation. In: Proceedings of 2013 IEEE Symposium on Security and Privacy. 2013, 223−237

RIGHTS & PERMISSIONS

Higher Education Press