Despite recent progress in the understanding and construction of SNARGs, there remain unattained goals. First, \emph{publicly-verifiable SNARGs} are only known either in the random oracle model, or in a model that allows expensive offline preprocessing. Second, known SNARGs require from the prover significantly more time or space than required for classical NP verification.
We show that, assuming collision-resistant hashing, \emph{any} SNARG having a natural \emph{proof of knowledge} property (i.e., a SNARK) can be ``bootstrapped" to obtain a \emph{complexity-preserving} SNARK, i.e., one without expensive preprocessing and where the prover's time and space complexity is essentially the same as that required for classical NP verification. By applying our transformation to known publicly-verifiable SNARKs with expensive preprocessing, we obtain the first publicly-verifiable complexity-preserving SNARK in the plain model (and in particular, eliminate the expensive preprocessing), thereby attaining the aforementioned goals. We also show an analogous transformation for privately-verifiable SNARKs, assuming fully-homomorphic encryption. Curiously, our transformations do not rely on PCPs.
At the heart of our transformations is \emph{recursive composition} of SNARKs and, more generally, new techniques for constructing and using \emph{proof-carrying data} (PCD) systems, which extend the notion of a SNARK to the distributed setting. 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, complexity-preserving SNARKs and PCD systems.
Category / Keywords: Date: received 23 Feb 2012, last revised 28 Dec 2012 Contact author: alexch at csail mit edu Available format(s): PDF | BibTeX Citation Version: 20121228:123450 (All versions of this report) Short URL: ia.cr/2012/095 Discussion forum: Show discussion | Start new discussion