Quarks: Quadruple-efficient transparent zkSNARKs
Quarks: Quadruple-efficient transparent zkSNARKs
复制标题
DOI：
--
复制
发表时间：
2020-10
期刊：
影响因子：
--
通讯作者：
Srinath T. V. Setty;Jonathan Lee
中科院分区：
文献类型：
--
作者：
Srinath T. V. Setty;Jonathan Lee
我们介绍了Xiphos和Kopis，这是针对R1CS的新的透明零知识简洁非交互式知识论证（zkSNARKs）。它们不需要可信设置，其安全性依赖于标准的SXDH问题。它们使用Fiat - Shamir变换在随机预言模型中实现非交互性。与之前的透明zkSNARKs不同，之前的那些要么支持快速证明者、要么支持短证明、要么支持快速验证，我们的工作首次同时实现了这三个特性（渐近地和具体地），并且还有一个低成本的设置阶段，从而提供了首个四重高效的透明zkSNARKs（Quarks）。在这两种方案下，对于大小为n且安全参数为λ的R1CS实例，证明者产生大小为$O_{\lambda}(\log{n})$的证明的成本为$O_{\lambda}(n)$。在Xiphos中，验证时间为$O_{\lambda}(\log{n})$，在Kopis中为$O_{\lambda}(\sqrt{n})$。就具体效率而言，与之前最先进的透明zkSNARKs相比，Xiphos提供了最快的验证；其证明大小与SuperSonic（[EUROCRYPT 2020]）相当，SuperSonic是文献中证明最短的先前的透明SNARK。Xiphos的证明者速度很快：其证明者速度约是Spartan（[CRYPTO 2020]）的3.85倍，Spartan是文献中证明者最快的先前的透明zkSNARK，并且比SuperSonic快376倍。Kopis以增加验证时间为代价（但仍然比SuperSonic在具体上更快），进一步缩短了Xiphos的证明大小，从而产生比SuperSonic更短的证明。根据基线不同，Xiphos和Kopis在设置阶段为验证者带来的预处理成本比之前低10 - 10000倍。最后，Kopis的一个副产品是Lakonia，这是一种针对R1CS的NIZK，其证明大小为$O_{\lambda}(\log{n})$，它为Bulletproofs（[S&P 2018]）提供了一种替代方案，其证明和验证时间快了一个数量级以上。
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λ(n)">O_{\lambda}(n)$ costs to produce a proof of size $Oλ(n)">O_{\lambda}(\log{n})$. In Xiphos, verification time is $Oλ(n)">O_{\lambda}(\log{n})$, and in Kopis it is $Oλ(n)">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 $\approx3.85×">\times$ of Spartan [CRYPTO 2020], a prior transparent zkSNARK with the fastest prover in the literature, and is $250"> 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$–$10,000×">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λ(n)">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.