Extractable PCS ⇒ SNARK
Statement
Any extractable polynomial commitment scheme (PCS) with succinct commitments and evaluation proofs yields a preprocessing SNARK for NP in the random-oracle model: the prover of a polynomial IOP for NP, which exists unconditionally, commits to each round’s polynomials and answers the verifier’s evaluation queries with evaluation proofs, and Fiat–Shamir makes the resulting public-coin argument non-interactive; CHM+20 compile algebraic holographic proofs and BFS20 polynomial IOPs. The setup of the PCS carries over, so a transparent PCS yields a transparent SNARK, and a hiding PCS with zero-knowledge evaluation proofs, compiling a zero-knowledge polynomial IOP, yields a zk-SNARK — CHM+20, BFS20.
Sketch
For knowledge soundness, the PCS extractor recovers the committed polynomials from a convincing prover; these define a polynomial-IOP prover, from which the polynomial-IOP extractor recovers a witness.
Notes
- With the KZG10 commitment scheme the SNARK has a universal and updatable structured reference string; Marlin and Plonk are instances — CHM+20. Plonk compiles PLONKish arithmetization, via a permutation argument and KZG commitments, into a universal-setup zk-SNARK — GWC19.