1. 引言

Bootle和Groth等人2016年论文《Efficient Zero-Knowledge Arguments for Arithmetic Circuits in the Discrete Log Setting》。

在本论文中，主要为 (只有加法门和乘法门的) arithmetic circcuit satisfiability 提供了一种零知识证明算法，具有的communication complexity为$O(\log n)$O(logn)，其中$n$n为circuit size；具有的round complexity也为$O(\log n)$O(logn)。且对于所有gates均为 2 fan-in的arithmetic circuit，Prover和Verifier的computation complexity均为$O(n)$O(n)。该算法无需trusted setup，仅需基于discrete logarithm assumption in prime order groups即可。

在该零知识证明算法中，核心内容为：

• inner product 零知识证明算法。

该inner product 零知识证明算法，具有的communication complexity为$O(\log n)$O(logn)，round complexity为$O(\log n)$O(logn)，Prover和Verifier的computation complexity均为$O(n)$O(n)。

除此之外，还提供了一种polynomial commitment算法，用于reveal the evaluation at an arbitrary point in a verifiable manner。使用该polynomial commitment算法，可将Groth 2009年论文《Linear Algebra with Sub-linear Zero-Knowledge Arguments》中的constant round arithmetic circuit 零知识证明算法的communication complexity 由$O(\sqrt{n})$O(n​)进一步优化降低为$O(\log n)$O(logn)。（可参见博客 Linear Algebra with Sub-linear Zero-Knowledge Arguments学习笔记）

零知识证明算法可广泛用于authentication protocol, multi-parity computation, encryption primitives, electronic voting systems和verifiable computation protocols。
零知识证明算法应具有如下属性：

• Completeness：A prover with a witness $w$w for $u\in L$u∈L can convince the verifier of this fact.
• Soundness：A prover cannot convince a verifier when $u\notin L$u∈/​L.
• Zero-knowledge：The interaction should not reveal anything to the verifier except that $u\in L$u∈L. In particular, it should not reveal the prover’s witness $w$w.

[Gro09b] Groth 2009年论文《Linear Algebra with Sub-linear Zero-Knowledge Arguments》中各算法性能表现为：

上图Arithmetic circuit constant round 零知识证明算法中，需要7 moves，具有square root communication complexity in the total number of gates。在该算法中，Prover需commits to all the wires using homomorphic multicommitments, 对于加法门可利用同态属性来verify，对于乘法门可利用product argument来verify。

本文在[Gro09b]算法的基础上，做了改进，使其：

• 具有5 moves，