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} }