You are looking at a specific version 20201024:000153 of this paper. See the latest version.

Paper 2020/1275

Quarks: Quadruple-efficient transparent zkSNARKs

Srinath Setty and Jonathan Lee

Abstract

We introduce Xiphos and Kopis, new transparent zero-knowledge succinct non-interactive arguments of knowledge (zkSNARKs) for R1CS. They do not require a trusted setup, and their security relies on the standard SXDH problem. They achieve non-interactivity in the random oracle model using the Fiat-Shamir transform. Unlike prior transparent zkSNARKs, which support either a fast prover, short proofs, or quick verification, our work is the first to simultaneously achieve all three properties (both asymptotically and concretely) and in addition an inexpensive setup phase, thereby providing the first quadruple-efficient transparent zkSNARKs (Quarks). Under both schemes, for an R1CS instance of size n and security parameter $\lambda$, the prover incurs $O_{\lambda}(n)$ costs to produce a proof of size $O_{\lambda}(\log{n})$. In Xiphos, verification time is $O_{\lambda}(\log{n})$, and in Kopis it is $O_{\lambda}(\sqrt{n})$. In terms of concrete efficiency, compared to prior state-of-the-art transparent zkSNARKs, Xiphos offers the fastest verification; its proof sizes are competitive with those of SuperSonic [EUROCRYPT 2020], a prior transparent SNARK with the shortest proofs in the literature. Xiphos’s prover is fast: its prover is $\approx$$3.8\times$ of Spartan [CRYPTO 2020], a prior transparent zkSNARK with the fastest prover in the literature, and is $376$$\times$ faster than SuperSonic. Kopis, at the cost of increased verification time (which is still concretely faster than SuperSonic), shortens Xiphos’s proof sizes further, thereby producing proofs shorter than SuperSonic. Xiphos and Kopis incur $10$--$10,000\times$ lower preprocessing costs for the verifier in the setup phase depending on the baseline. Finally, a byproduct of Kopis is Lakonia, a NIZK for R1CS with $O_{\lambda}(\log{n})$-sized proofs, which provides an alternative to Bulletproofs [S&P 2018] with over an order of magnitude faster proving and verification times.

Note: Report improved performance by switching to a faster library for curve arithmetic; fix small typos.

Metadata
Available format(s)
PDF
Category
Cryptographic protocols
Publication info
Preprint. MINOR revision.
Keywords
SNARKszero-knowledgetransparent SNARKs
Contact author(s)
srinath @ microsoft com,j d lee0 @ gmail com
History
2020-10-24: last of 2 revisions
2020-10-14: received
See all versions
Short URL
https://ia.cr/2020/1275
License
Creative Commons Attribution
CC BY
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.