Scalable zero knowledge with no trusted setup
发表信息
作者
- Eli Ben-Sasson
- Iddo Bentov
- Yinon Horesh
- Michael Riabzev
笔记
One of the approaches to constructing zero knowledge (ZK) arguments relies on “PCP techniques” that date back to influential works from the early 1990’s [Babai et al., Arora et al. 1991-2]. These techniques require only minimal cryptographic assumptions, namely, the existence of a family of collision-resistant hash functions [Kilian, STOC 1992], and achieve two remarkable properties: (i) all messages generated by the verifier are public random coins, and (ii) total verification time is merely poly-logarithmic in the time needed to naïvely execute the computation being verified [Babai et al., STOC 1991].
Those early constructions were never realized in code, mostly because proving time was too large. To address this, the model of interactive oracle proofs (IOPs), which generalizes the PCP model, was recently suggested. Proving time for ZK-IOPs was reduced to quasi-linear, even for problems that require nondeterministic exponential time to decide [Ben-Sasson et al., TCC 2016, ICALP 2017].
Despite these recent advances it was still not clear whether ZK-IOP systems can lead to concretely efficient succinct argument systems. Our main claim is that this is indeed the case. We present a new construction of an IOP of knowledge (which we call a zk-STIK) that improves, asymptotically, on the state of art: for log-space computations of length T it is the first to arithmetic prover complexity and verifier arithmetic complexity. Prior IOPs had additional factors in both prover and verifier. Additionally, we report a C++ realization of this system (which we call libSTARK). Compared to prevailing ZK realizations, it has the fastest proving and (total) verification time for sufficiently large sequential computations.
以下是中文翻译：
构建零知识(Zero Knowledge, ZK)论证的方法之一依赖于可追溯至20世纪90年代初具有影响力的研究成果中的”PCP技术”[Babai等人, Arora等人 1991-2]。这些技术仅需要最基本的密码学假设，即存在抗碰撞哈希函数族[Kilian, STOC 1992]，并实现了两个显著特性：(i)验证者生成的所有消息都是公开的随机数，以及(ii)总验证时间仅为朴素执行被验证计算所需时间的多项式对数[Babai等人, STOC 1991]。
那些早期构造从未在代码中实现，主要是因为证明时间过长。为解决这个问题，最近提出了交互式预言证明(Interactive Oracle Proofs, IOPs)模型，该模型是对PCP模型的推广。ZK-IOPs的证明时间已降低到准线性，即使对于需要非确定性指数时间才能判定的问题也是如此[Ben-Sasson等人, TCC 2016, ICALP 2017]。
尽管有这些最新进展，ZK-IOP系统是否能够带来具体高效的简洁论证系统仍不明确。我们的主要论点是这确实是可行的。我们提出了一个新的知识交互式预言证明构造（我们称之为zk-STIK），它在渐近性能上改进了现有技术水平：对于长度为T的对数空间计算，它是首个实现O(T log T)算术证明者复杂度和O(log T)验证者算术复杂度的系统。此前的IOPs在证明者和验证者复杂度上都有额外的poly log T因子。此外，我们报告了该系统的C++实现（我们称之为libSTARK）。与现有的ZK实现相比，对于足够大的顺序计算，它具有最快的证明和（总）验证时间。