SNARK + CRHF ⇒ Fully succinct SNARK (bootstrapping)

Free reduction · standard model · BCCT13

Statement

If collision-resistant hash functions exist, every publicly verifiable preprocessing SNARK, one whose reference string and setup time may grow with the computation, can be bootstrapped into a fully succinct publicly verifiable SNARK, whose reference string has size $\mathrm{poly}(\lambda )$ independent of the computation and whose prover needs time and space essentially those of classical $\mathbf{NP}$ verification; the transformation recursively composes the SNARK into a weak proof-carrying-data system for shallow distributed computations and does not rely on PCPs — BCCT13. Applied to known SNARKs with preprocessing, it gives the first fully succinct publicly verifiable SNARK — BCCT13.

Notes

• The $\mathsf{crs}$ and the proof have size $\mathrm{poly}(\lambda )$, the verifier runs in time $\mathrm{poly}(\lambda ,|M|,|x|,\log t)$, and the prover’s time and space are quasi-equal to those of $\mathbf{NP}$ verification — BCCT13.
• The same recursive composition gives incrementally verifiable computation: SNARK ⇒ Recursive SNARKs — BCCT13.