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 (non-deterministic, 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 near-optimal 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 collision-resistant hash functions. When suitably instantiating our construction, we achieve a four-round SPARK for any parallel RAM computation assuming only collision resistance. Additionally assuming the existence of a succinct non-interactive argument of knowledge (SNARK), we construct a non-interactive SPARK that also preserves the space complexity of the underlying computation up to polylog(T * p) factors. We also show the following applications of non-interactive 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 memory-hard, this yields the first construction of a memory-hard VDF.

Note: This version includes constructions of SPARKs for parallel RAM computations.

Metadata
Available format(s)
PDF
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
2020-08-18: received
Short URL
https://ia.cr/2020/994
License
Creative Commons Attribution
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}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.