Welcome to the resource topic for 2012/095
Title:
Recursive Composition and Bootstrapping for SNARKs and Proof-Carrying Data
Authors: Nir Bitansky, Ran Canetti, Alessandro Chiesa, Eran Tromer
Abstract:\emph{Succinct non-interactive arguments} (SNARGs) enable verifying NP statements with much lower complexity than required for classical NP verification (in fact, with complexity that is \emph{independent} of the NP language at hand). In particular, SNARGs provide strong solutions to the problem of verifiably delegating computation. 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.
ePrint: https://eprint.iacr.org/2012/095
See all topics related to this paper.
Feel free to post resources that are related to this paper below.
Example resources include: implementations, explanation materials, talks, slides, links to previous discussions on other websites.
For more information, see the rules for Resource Topics .