Paper 2020/994
SPARKs: Succinct Parallelizable Arguments of Knowledge
Naomi Ephraim, Cody Freitag, Ilan Komargodski, and Rafael Pass
Abstract
We introduce the notion of a Succinct Parallelizable Argument of Knowledge (SPARK). This is an argument of knowledge with the following three efficiency properties for computing and proving a (nondeterministic, polynomial time) parallel RAM computation that can be computed in parallel time T with at most p processors: (1) The prover’s (parallel) running time is T + polylog(T * p). (In other words, the prover’s running time is essentially T for large computation times!) (2) The prover uses at most p * polylog(T * p) processors, and (3) the communication and verifier complexity are both polylog(T * p). The combination of all three is desirable as it gives a way to leverage a moderate increase in parallelism in favor of nearoptimal running time. We emphasize that even a factor two overhead in the prover’s parallel running time is not allowed. Our main contribution is a generic construction of SPARKs from any succinct argument of knowledge where the prover’s parallel running time is T * polylog(T * p) when using p processors, assuming collisionresistant hash functions. When suitably instantiating our construction, we achieve a fourround SPARK for any parallel RAM computation assuming only collision resistance. Additionally assuming the existence of a succinct noninteractive argument of knowledge (SNARK), we construct a noninteractive SPARK that also preserves the space complexity of the underlying computation up to polylog(T * p) factors. We also show the following applications of noninteractive SPARKs. First, they immediately imply delegation protocols with near optimal prover (parallel) running time. This, in turn, gives a way to construct verifiable delay functions (VDFs) from any sequential function. When the sequential function is also memoryhard, this yields the first construction of a memoryhard VDF.
Note: This version includes constructions of SPARKs for parallel RAM computations.
Metadata
 Available format(s)
 Category
 Foundations
 Publication info
 Published elsewhere. Major revision. EUROCRYPT 2020
 Keywords
 Succinct argumentsSNARKverifiable computationinteractive proofs
 Contact author(s)

nephraim @ cs cornell edu
cfreitag @ cs cornell edu  History
 20200818: received
 Short URL
 https://ia.cr/2020/994
 License

CC BY
BibTeX
@misc{cryptoeprint:2020/994, author = {Naomi Ephraim and Cody Freitag and Ilan Komargodski and Rafael Pass}, title = {{SPARKs}: Succinct Parallelizable Arguments of Knowledge}, howpublished = {Cryptology ePrint Archive, Paper 2020/994}, year = {2020}, note = {\url{https://eprint.iacr.org/2020/994}}, url = {https://eprint.iacr.org/2020/994} }