Efficient Zero-Knowledge Arguments for Arithmetic Circuits in the Discrete Log Setting学习笔记

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(\log n) O(logn)，其中 n n n为circuit size；具有的round complexity也为 O ( log ⁡ n ) O(\log n) O(logn)。且对于所有gates均为 2 fan-in的arithmetic circuit，Prover和Verifier的computation complexity均为 O ( n ) O(n) O(n)。该算法无需trusted setup，仅需基于discrete logarithm assumption in prime order groups即可。

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

• inner product 零知识证明算法。

该inner product 零知识证明算法，具有的communication complexity为 O ( log ⁡ n ) O(\log n) O(logn)，round complexity为 O ( log ⁡ n ) O(\log n) O(logn)，Prover和Verifier的computation complexity均为 O ( n ) 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 ( n ) O(\sqrt{n}) O(n ​)进一步优化降低为 O ( log ⁡ 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 w for u ∈ L u\in L u∈L can convince the verifier of this fact.
• Soundness：A prover cannot convince a verifier when u ∉ L u\notin L u∈/​L.
• Zero-knowledge：The interaction should not reveal anything to the verifier except that u ∈ L u\in L u∈L. In particular, it should not reveal the prover’s witness w 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]算法的基础上，分为两大步来改进： 1）首先实现5 moves，communication complexity为square root的argument：

• 避免使用[Gro09b]中的generic reductions to linear algebra statements，可由7 moves降为5 moves；
• 通过同时处理一系列的Hadamard products和linear relations，可去除argument中加法门的communication cost，comminication complexity 由 O ( n a d d + n m u l ) O(\sqrt{n_{add}+n_{mul}}) O(nadd​+nmul​ ​)降为 O ( n m u l ) O(\sqrt{n_{mul}}) O(nmul​ ​)（其中 n a d d + n m u l n_{add}+n_{mul} nadd​+nmul​代表total number of gates，而 n m u l n_{mul} nmul​为multiplication gates的数量。）。
• 同时还提出了一种polynomial commitment 零知识证明算法，其communication complexity为 O ( d ) O(\sqrt{d}) O(d ​)，其中 d d d为polynomial degree。

2）其次，在1）的基础上，进一步压缩communication complexity：

• 在1）算法中，仍然具有communication complexity O ( n m u l ) O(\sqrt{n_{mul}}) O(nmul​ ​)。原因是在第一轮Prover需要commit to all circuit wires using 3 m 3m 3m commitments to n n n elements each，其中 m n = N mn=N mn=N 为multiplication gate数量的上线。而在最后一轮当收到challenge后，Prover open one commitment that can be constructed from the previous ones and the challenge。当设置 m ≈ n m\approx n m≈n时，最小communication complexity即为 O ( N ) O(\sqrt{N}) O(N ​)。 本文将最后一轮的opening step替换为了an argument of knowledge of the opening values，利用Pedersen multicommitments的同态属性，将该argument实现为an argument of knowledge of openings of two homomorphic commitments，satisfying an inner product relation。该inner product argument通过借助递归方法，其communication complexity为 O ( log ⁡ n ) O(\log n) O(logn)，其中 n n n为vector size。借助该inner product argument，其最终实现的arithmetic circuit satisfiability argument的communication也为logarithmic。

将本文最终实现的5 moves， O ( log ⁡ n ) O(\log n) O(logn) communication argument算法与Pinocchio算法（[PHGR13] 2013年Parno等人论文 Pinocchio: Nearly practical verifiable computation）进行对比：（Pinocchio为使用的verifiable computation scheme，允许constrained client将a function的computation 外包给 a powerful worker，同时能高效验证该worker输出的function运算结果是否正确。Pinocchio采用quadratic arithmetic programs，为arithmetic circuits的generalisation，可以实现比本地直接计算更快的function verification。）

• 本文算法的verification虽然不够快，但是在基于更简单的assumption的基础上，具有更快的prover computation。

1.1 相关研究工作

• Goldwasser等人在1989（1985）年论文《The knowledge complexity of interactive proofs》中首次提出了Zero-knowledge proofs概念。 注意区分： – zero-knowledge proof：具有statistical soundness。proof仅能有computational zero-knowledge。 – zero-knowledge argument：具有computational soundness。而argument可能有perfect zero-knowledge。

• Brassard等人1988年论文《Minimum disclosure proofs of knowledge》中指出 all languages in NP have zero-knowledge arguments with perfect zero-knowledge。

• Goldreich等人1991年论文《Proofs that yield nothing but their validity or all languages in NP have zero-knowledge proof systems》中指出 all languages in NP have zero-knowledge proofs。

• Gentry等人2014年论文《Using fully homomorphic hybrid encryption to minimize non-interative zero-knowledge proofs》中采用全同态加密算法来构建 zero-knowledge proofs，其communication complexity与witness size相当。通常地，proofs的communication不会小于witness size，除非 surprising results about the complexity of solving SAT instances hold（参见论文[GH98][GVW02]）。

• Kilian在1992年论文《 A note on efficient zero-knowledge proofs and arguments》中指出，与 zero-knowledge proofs不同，若只实现 zero-knowledge arguments的话，可以具有很低的communication complexity。Kilian的构建依赖于 PCP theorem，无法生成实用的scheme。

• Schnorr 1991年论文《Efficient signature generation by smart cards》和Guilou等人1988年论文《 A practical zero-knowledge protocol fitted to security microprocessor minimizing both trasmission and memory》给出了早期的实用的zero-knowledge arguments for concrete number theoretic problems例子。基于Schnorr protocol，可扩展出很多基于discrete logarithms assumption的zero-knowledge arguments。

• Cramer等人1998年论文《Zero-knowledge proofs for finite field arithmetic; or: Can zero-knowledge be for free?》中给出了基于arithmetic circuit satisfiability的zero-knowledge argument算法，该算法具有linear communication complexity。

• 截至目前（2016年），基于discrete logarithm assumption 构建的arithmetic circuit zero-knowledge argument 最高效的算法有 Groth 2009年论文《Linear Algebra with Sub-linear Zero-Knowledge Arguments》中算法和Seo 2011年论文《Round-efficient sub-linear zero-knowledge arguments for linear algebra》中算法，二者均具有constant move，communication complexity为square root of the circuit size。 O ( N ) O(\sqrt{N}) O(N ​)

• 若不基于 discrete logarithm assumption，而采用 pairing-based cryptography，Groth 2009年论文《Efficient zero-knowledge arguments from two-tiered homomorphic commitments》中生成的arithmetic circuit zero-knowledge argument 具有 cubic root communication complexity。 O ( N 3 ) O(\sqrt[3]{N}) O(3N ​)

• 目前基于 specific languages构建的具有logarithmic communication complexity的算法有：（这些都是针对特定类型的statements——具有low circuit depth，且这些算法无法推广至任意的NP languages。） – 2013年Bayer和Groth 论文《Zero-knowledge argument for polynomial evaluation with application to blacklists》中指出，one can prove that a polynomial evaluated at a secret committed value gives a certain output with a logarithmic communication complexity。【注意普通的polynomial commitment，其evaluate的点是公开的，而此处是secret的。】 – 2014年Groth和Kohlweiss 论文《One-out-of-many proofs: Or how to leak a secret and spend a coin》中指出，one out of N N N commitments contain 0 with logarithmic communication complexity。

• 以下系列的研究均是基于pairing-based cryptography构建的succinct non-interactive arguments (SNARGs)，其argument具有 a constant number of group elements，但是它们都依赖于 a common reference string (with a special structure) and non-falsifiable knowledge extractor assumption： – Groth 2010年论文《Short pairing-based non-interactive zero-knowledge arguments》 – Lipmaa 2012年论文《Progression-free sets and sublinear pairing-based non-interactive zero-knowledge arguments》 – Bitansky等人2012年论文《From extractable collision resistance to succinct non-interactive arguments of knowledge, and back again》 – Gennaro等人2013年论文《Quadratic span programs and succinct NIZKs without PCPs》 – Bitansky等人2013年论文《Recursive composition and bootstrapping for SNARKS and proof-carrying data》 – Parno等人2013年论文《 Pinocchio: Nearly practical verifiable computation》 – Ben-Sasson等人2013年论文《SNARKs for C: verifying program executions succinctly and in Zero Knowledge》 – Ben-Sasson等人2014年论文《Succinct non-interactive zero knowledge for a von neumann architecture》 – Groth和Kohlweiss 2014年论文《One-out-of-many proofs: Or how to leak a secret and spend a coin》

• 本文构建的argument仅基于discrete logartihm assumption，且使用与 circuit无关的 small common reference string。

以下为对当前最高效的基于discrete logarithm assumption的zero-knowledge arguments的性能对比： 由上图可知：

• 同样是5 moves， 本文算法所需要的computation低于[Seo11]算法；
• 当使用logarithmic number of moves时，本文采用了与2012年论文《Efficient zero-knowledge argument for correctness of a shuffle》类似的reduction，在不增加其它开销的情况下，可大幅降低communication cost。与2012年论文《Efficient zero-knowledge argument for correctness of a shuffle》中使用reduction来降低computation不同，本文用来降低communication。（参见博客 Efficient Zero-Knowledge Argument for Correctness of a Shuffle学习笔记（1））

1.2 polynomial commitment

• Kate等人2010年论文《Constant-size commitments to polynomials and their applications》中提供了a protocol to commit to polynomial and then evaluate it at a given point in a verifiable way。该算法仅需a constant number of commitments，但是其security依赖于pairing assumption。

• 本文构建的polynomial commitment 具有 square root communication complexity，但是完全基于discrete logarithm assumption。

1.3 相关定义

A multi-exponentiation of size n n n can be computed at a cost of roughly n log ⁡ n \frac{n}{\log n} lognn​ single group exponentiations using the multi-exponentiation techniques of [Lim00, M¨ol01, MR08]。

• Pedersen Commitment定义： Breaking the binding property of Pedersen commitments corresponds to breaking the discrete logarithm assumption. Pedersen commitment具有加法同态属性： C o m c k ( m 0 ; r 0 ) ⋅ C o m c k ( m 1 ; r 1 ) = C o m c k ( m 0 + m 1 ; r 0 + r 1 ) Com_{ck}(m_0;r_0)\cdot Com_{ck}(m_1;r_1)=Com_{ck}(m_0+m_1;r_0+r_1) Comck​(m0​;r0​)⋅Comck​(m1​;r1​)=Comck​(m0​+m1​;r0​+r1​)

Pedersen multicommitment指： C o m c k ( m 1 , ⋯   , m n ; r ) = g r ∏ i = 1 n g i m i Com_{ck}(m_1,\cdots,m_n;r)=g^r\prod_{i=1}^{n}g_i^{m_i} Comck​(m1​,⋯,mn​;r)=gr∏i=1n​gimi​​

• Argument of knowledge定义：

• Public coin 和 Perfect special honest verifier zero-knowledge 定义：

• Full zero-knowledge 定义：

• Fiat-Shamir heuristic 定义： The Fiat-Shamir transformation takes an interactive public coin argument and replaces the challenges with the output of a cryptographic hash function. The idea is that the hash function will produce random looking output and therefore be a suitable replacement for the verifier.The Fiat-Shamir heuristic yields a non-interactive zero-knowledge argument in the random oracle model [BR93]. 本文可借助Fiat-Shamir heuristic，将logarithmic number of move转换为single one move的argument。

1.4 相关假设

• Discrete Logarithm Assumption：

• Discrete Logarithm Relation Assumption：（与Discrete Logarithm Assumption 等价）

• A general forking lemma定义： 假设有 ( 2 μ + 1 ) (2\mu+1) (2μ+1)-move public-coin argument，该argument有 μ \mu μ 个challenges —— 依次为 x 1 , ⋯   , x μ x_1,\cdots,x_{\mu} x1​,⋯,xμ​。 对于 1 ≤ i ≤ μ 1\leq i\leq \mu 1≤i≤μ，有 n i ≥ 1 n_i\geq 1 ni​≥1，将具有 ∏ i = 1 μ n i \prod_{i=1}^{\mu}n_i ∏i=1μ​ni​ 个accepting transcripts with challenges以tree 方式表示，该tree的depth为 μ \mu μ，具有的leaves数量为 ∏ i = 1 μ n i \prod_{i=1}^{\mu}n_i ∏i=1μ​ni​，该tree的根表示为the statement。每个depth i < μ i