Proofs for Inner Pairing Products and Applications
Proofs for Inner Pairing Products and Applications
复制标题
DOI：
10.1007/978-3-030-92078-4_3
复制
发表时间：
2021
期刊：
影响因子：
--
通讯作者：
Benedikt Bünz;Mary Maller;Pratyush Mishra;Nirvan Tyagi;Psi Vesely
中科院分区：
文献类型：
--
作者：
Benedikt Bünz;Mary Maller;Pratyush Mishra;Nirvan Tyagi;Psi Vesely
我们提出了一个广义的内积参数，并展示了它的应用对为基础的语言。我们应用我们的广义参数来证明，一个内部配对产品是正确的评价相对于承诺向量ofnsource组元素。利用结构化引用串（SRS），我们实现了一个以目标群求幂运算为主要工作的时间验证器。证明是sizetarget组元素，计算使用6n配对和4n exponentiations在每个源group.We应用我们的内积参数建立第一个多项式承诺方案简洁（对数）验证，prover复杂度degreedpolynomials（不包括成本评估多项式），和SRS的大小。具体地说，这意味着，在我们的协议中生成评估证明比在KZG承诺方案中生成评估证明更快，并且我们的协议中的CRS更小：13 MB对KZG的13 GB。我们的协议比通过递归组合聚合SNARKs要快得多：我们在25分钟内聚合了证明，而通过递归组合聚合了90个证明。最后，我们进一步应用我们的聚合协议来构建一个低内存的SNARK机器计算，不依赖于递归组合。对于需要时间T和空间S的计算，我们的SNARK在空间中产生证明，这比需要空间的单片SNARK更有效。
We present a generalized inner product argument and demonstrate its applications to pairing-based languages. We apply our generalized argument to prove that an inner pairing product is correctly evaluated with respect to committed vectors ofnsource group elements. With a structured reference string (SRS), we achieve a logarithmic-time verifier whose work is dominated bytarget group exponentiations. Proofs are of sizetarget group elements, computed using 6npairings and 4nexponentiations in each source group.We apply our inner product arguments to build the first polynomial commitment scheme with succinct (logarithmic) verification,prover complexity for degreedpolynomials (not including the cost to evaluate the polynomial), and a SRS of size. Concretely, this means that for, producing an evaluation proof in our protocol isfaster than doing so in the KZG commitment scheme, and the CRS in our protocol issmaller: 13 MB vs 13 GB for KZG.As a second application, we introduce an argument for aggregatingnGroth16 zkSNARKs into ansized proof. Our protocol is significantly faster () than aggregating SNARKs via recursive composition: we aggregateproofs in 25 min, versus 90 proofs via recursive composition. Finally, we further apply our aggregation protocol to construct a low-memory SNARK for machine computations that does not rely on recursive composition. For a computation that requires timeTand spaceS, our SNARK produces proofs in space, which is significantly more space efficient than a monolithic SNARK, which requires space.