SNARK ⇒ Recursive SNARKs

Free reduction · standard model · BCCT13 · security loss: polynomial for constant depth: each level of composition applies the SNARK extractor to the previous level’s extractor, a polynomial blow-up that compounds with the depth

Statement

Any SNARK for NP composes with itself, each proof attesting that one step was executed correctly and that the previous proof verifies, into proof-carrying data for constant-depth compliance predicates, and by depth reduction into incrementally verifiable computation for computations of any fixed polynomial length, with proof size and verification time independent of the number of steps, without random oracles — BCCT13.

Sketch

For a step function $F$, the prover at step $t$ proves with the SNARK that there exist $s_{t-1}$ and ${\pi }_{t-1}$ with $\mathsf{Vrfy}(\mathsf{crs},(t-1,s_{t-1}),{\pi }_{t-1})=1$ and $s_t=F(s_{t-1})$. Knowledge soundness applies the SNARK extractor to the outer proof to recover the inner one and repeats down the chain; each nesting costs a polynomial blow-up in extraction time, so the depth of direct composition must be constant.

Notes

• IVC was introduced, and realized from CS proofs of knowledge with an instantiated random oracle, by Val08; BCCT13 remove the random oracle, working from any SNARK — BCCT13.
• Concretely efficient recursion needs a SNARK whose verifier is efficiently arithmetizable (recursion-friendly) — folklore.