Existing zk-SNARK implementations have severe scalability limitations, in terms of space complexity as a function of the size of the computation being proved (e.g., running time of the NP statementís decision program). First, the size of the proving key is quasilinear in the upper bound on the computation size. Second, producing a proof requires "writing down" all intermediate values of the entire computation, and then conducting global operations such as FFTs.
The bootstrapping technique of Bitansky et al. (STOC í13), following Valiant (TCC í08), offers an approach to scalability, by recursively composing proofs: proving statements about acceptance of the proof systemís own verifier (and correctness of the programís latest step). Alas, recursive composition of known zk-SNARKs has never been realized in practice, due to enormous computational cost.
Using new elliptic-curve cryptographic techniques, and methods for exploiting the proof systemsí field structure and nondeterminism, we achieve the first zk-SNARK implementation that practically achieves recursive proof composition. Our zk-SNARK implementation runs random-access machine programs and produces proofs of their correct execution, on todayís hardware, for any program running time. It takes constant time to generate the keys that support all computation sizes. Subsequently, the proving process only incurs a constant multiplicative overhead compared to the original computationís time, and an essentially-constant additive overhead in memory. Thus, our zk-SNARK implementation is the first to have a well-defined, albeit low, clock rate of "verified instructions per second".Category / Keywords: cryptographic protocols / computationally-sound proofs, proof-carrying data, zero knowledge, elliptic curves Original Publication (with major differences): IACR-CRYPTO-2014 Date: received 3 Aug 2014, last revised 28 Apr 2015 Contact author: alexch at mit edu Available format(s): PDF | BibTeX Citation Version: 20150428:114046 (All versions of this report) Short URL: ia.cr/2014/595 Discussion forum: Show discussion | Start new discussion