Recursive composition and bootstrapping for SNARKs and proof-carrying data

Succinct non-interactive arguments of knowledge (SNARKs) enable verifying NP statements with complexity that is essentially independent of that required for classical NP verification. In particular, they provide strong solutions to the problem of verifiably delegating computation. We construct the first fully-succinct publicly-verifiable SNARK. To do that, we first show how to "bootstrap" any SNARK that requires expensive preprocessing to obtain a SNARK that does not, while preserving public verifiability. We then apply this transformation to known SNARKs with preprocessing. Moreover, the SNARK we construct only requires of the prover time and space that are essentially the same as that required for classical NP verification. Our transformation assumes only collision-resistant hashing; curiously, it does not rely on PCPs. We also show an analogous transformation for privately-verifiable SNARKs, assuming fullyhomomorphic encryption. At the heart of our transformations is a technique for recursive composition of SNARKs. This technique uses in an essential way the proof-carrying data (PCD) framework, which extends SNARKs to the setting of distributed networks of provers and verifiers. Concretely, to bootstrap a given SNARK, we recursively compose the SNARK to obtain a "weak" PCD system for shallow distributed computations, and then use the PCD framework to attain stronger notions of SNARKs and PCD systems.