Recursive composition and bootstrapping for SNARKS and proof-carrying data

By Nir Bitansky, Ran Canetti, Alessandro Chiesa, Eran Tromer. 2013

364 citations recorded by the source corpus.

Subfields: Artificial Intelligence, Computational Theory and Mathematics

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

1. Srinath T. V. Setty
2. Dan Boneh
3. Eli Ben-Sasson
4. Michael Walfish
5. Andrew Justin Blumberg
6. Iddo Bentov
7. Eran Tromer
8. Justin Thaler

In Computational Theory and Mathematics

1. Srinath T. V. Setty
2. Eli Ben-Sasson
3. Dan Boneh
4. Michael Walfish
5. Andrew Justin Blumberg
6. Eran Tromer
7. Justin Thaler
8. Brent Waters

Citations in the corpus

• Bulletproofs: Short Proofs for Confidential Transactions and More (2018, background): “Zero-knowledge SNARKs have been the subject of extensive research [Gro10,BCCT12,GGPR13, BCCT13,PHGR16,BSCG ` 13,Gro16].”
• Geppetto: Versatile Verifiable Computation (2015, methodology): “In theory, with proof bootstrapping [11, 53], the prover can combine any series of proofs into one by verifiably computing the verification of all of those proofs.”
• Computational Integrity with a Public Random String from Quasi-Linear PCPs (2017, methodology): “Incrementally verifiable computation (IVC) [75] and bootstrapping [28] shorten the length of kP to poly log T and an IVC-based system has been implemented recently [18].”
• Hawk: The Blockchain Model of Cryptography and Privacy-Preserving Smart Contracts (2016, methodology): “Examples include recursively composed SNARKs [18], [25] or other efficient PCP constructions [16].”
• SNARKs for C: Verifying Program Executions Succinctly and in Zero Knowledge (2013, neutral): “[BCCT13].”
• Privacy-Preserving Solutions for Blockchain: Review and Challenges (2019, background): “zkSNARK (zero-knowledge Succinct Non-Interactive ARgument of Knowledge) [95] is similar to ZKP, but their construction offers more possibilities that the blockchain technology [103], [104].”
• Fast reductions from RAMs to delegatable succinct constraint satisfaction problems: extended abstract (2013, background): “[15] cannot be performed on the circuit obtained in the proof of Theorem 1.”
• Efficient Zero-Knowledge Arguments for Arithmetic Circuits in the Discrete Log Setting (2016, background): “An exciting line of research [22, 30, 6, 13, 7, 34, 4, 5, 24] has developed many proposals for succinct non-interactive arguments (SNARGs) yielding pairingbased constructions where the arguments consist of a constant number of group elements.”
• Time-Optimal Interactive Proofs for Circuit Evaluation (2013, background): “As short PCPs are often a bottleneck in the development of efficient argument systems, other works have focused on avoiding their use [3,6,7,19].”
• On the concrete efficiency of probabilistically-checkable proofs (2013, background): “One additional property that is often essential in constructions of succinct arguments is proof of knowledge, which makes it possible to delegate “cryptographic computations” [13] and to recursively compose non-interactive proofs [45, 17, 16, 14, 18].”
• Scalable, transparent, and post-quantum secure computational integrity (2018, methodology): “[29] Nir Bitansky, Ran Canetti, Alessandro Chiesa, and Eran Tromer.”
• Verifying computations without reexecuting them (2015, result): “(This is theoretically possible [8, 11], but overhead is very high: in a recent implementation [8], the prover’s computational costs are orders of magnitude higher than in TinyRAM.)”
• Functional Signatures and Pseudorandom Functions (2014, background): “We note that the SNARK construction in [BCCT13] satisfies a stronger definition, where the extraction process has to work for a honestly generated crs , without having access to a trapdoor.”
• PhotoProof: Cryptographic Image Authentication for Any Set of Permissible Transformations (2016, methodology): “This work is also the first application-specific use of PCD (prior prototypes were either proofs-of-concept for generic computation [7], [13] or used the special case of SNARKs [3]).”
• Efficient RAM and control flow in verifiable outsourced computation (2015, background): “Buffet allows the programmer to express programs in an expansive subset of C (disallowing only “goto” and function pointers), can handle essentially any example in the verifiable computation literature, and achieves the best performance in the area by multiple orders of magnitude.”
• Succinct Non-Interactive Zero Knowledge for a von Neumann Architecture (2014, background): “Theoretical constructions of such zk-SNARKs are known, based on various cryptographic assumptions [54, 69, 21].”