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

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²∣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(|C|) proof size and verifier complexity while the number of public-key operations for both the prover and verifier is independent of ∣C∣.