Cryptology ePrint Archive: Report 2020/994

SPARKs: Succinct Parallelizable Arguments of Knowledge

Naomi Ephraim and Cody Freitag and 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.

Category / Keywords: foundations / Succinct arguments, SNARK, verifiable computation, interactive proofs

Original Publication (with major differences): EUROCRYPT 2020

Date: received 17 Aug 2020

Contact author: nephraim at cs cornell edu,cfreitag@cs cornell edu

Available format(s): PDF | BibTeX Citation

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

Version: 20200818:084146 (All versions of this report)

Short URL: ia.cr/2020/994


[ Cryptology ePrint archive ]