Nova: Recursive Zero-Knowledge Arguments from Folding Schemes
Nova: Recursive Zero-Knowledge Arguments from Folding Schemes
复制标题
DOI：
10.1007/978-3-031-15985-5_13
复制
发表时间：
2021
期刊：
影响因子：
--
通讯作者：
Abhiram Kothapalli;Srinath T. V. Setty;Ioanna Tzialla
中科院分区：
文献类型：
--
作者：
Abhiram Kothapalli;Srinath T. V. Setty;Ioanna Tzialla
介绍了一种实现增量可验证计算(IVC)的新方法，其中证明者递归地证明形式的增量计算的正确执行，其中F是(潜在的不确定的)计算，X是输入，Y是输出，和。与已有的实现知识价值的方法不同，我们的方法完全避免了简洁的非交互的知识争论(Snarks)和一般的知识争论。相反，我们引入并使用折叠方案，这是一种更弱、更简单、更有效实现的原语，它减少了检查两个实例的任务，而不是检查单个实例的任务。我们构造了一个用于刻画NP的折叠方案，并证明了它蕴含了一种具有改进的效率特征的IVC方案：(1)递归开销(即证明者除了证明执行成功之外还证明的步数)是一个常数，它由两组标量乘法控制，表示为一个电路(这是文献中最小的递归开销)；(2)证明者在每一步的工作被Sizeo(|F|)的两个多指数所支配，提供了文献中最快的证明者。证明ISO(|F|)群元素的大小，但我们证明了使用现有zkSNARK的变体，证明者可以简洁地证明有效证明的知识，并且是零知识的群元素。最后，我们的方法既不需要可信的设置，也不需要FFT，所以它可以用任何DLOG困难的椭圆曲线周期有效地实例化。
We introduce a new approach to realize incrementally verifiable computation (IVC), in which the prover recursively proves the correct execution of incremental computations of the form, whereFis a (potentially non-deterministic) computation,xis the input,yis the output, and. Unlike prior approaches to realize IVC, our approach avoids succinct non-interactive arguments of knowledge (SNARKs) entirely and arguments of knowledge in general. Instead, we introduce and employfolding schemes, a weaker, simpler, and more efficiently-realizable primitive, which reduces the task of checking two instances in some relation to the task of checking a single instance. We construct a folding scheme for a characterization of NP and show that it implies an IVC scheme with improved efficiency characteristics: (1) the “recursion overhead” (i.e., the number of steps that the prover proves in addition to proving the execution ofF) is a constant and it is dominated by two group scalar multiplications expressed as a circuit (this is the smallest recursion overhead in the literature), and (2) the prover’s work at each step is dominated by two multiexponentiations of sizeO(|F|), providing the fastest prover in the literature. The size of a proof isO(|F|) group elements, but we show that using a variant of an existing zkSNARK, the prover can prove the knowledge of a valid proof succinctly and in zero-knowledge withgroup elements. Finally, our approach neither requires a trusted setup nor FFTs, so it can be instantiated efficiently with any cycles of elliptic curves where DLOG is hard.