SPARKs: Succinct Parallelizable Arguments of Knowledge
We introduce the notion of a Succinct Parallelizable Argument of Knowledge (SPARK). This is an argument system with the following three properties for computing and proving a time T (non-deterministic) computation: 
 
 
The prover’s (parallel) running time is \(T + \mathrm {poly}\!\log T\). (In other words, the prover’s running time is essentially T for large computation times!) 
 
 
The prover uses at most \(\mathrm {poly}\!\log T\) processors. 
 
 
The communication complexity and verifier complexity are both \(\mathrm {poly}\!\log T\).