1. 引言

Jiaheng Zhang等人2020年论文《Virgo: Transparent Polynomial Delegation and Its Applications to Zero Knowledge Proof》发表于 IEEE Symposium on Security and Privacy 2020。

相应的代码实现：

https://github/sunblaze-ucb/Virgo （C++语言实现）

相应的视频介绍：

https://www.youtube/watch?v=dRggr686ZzE&t=154s

要点：
1）不基于discrete log或bilinear map，但为了low degree test (LDT)的运行效率考虑，实际Field选型有要求，详见5.1节field选型。现有的Stark和Aurora也是基于LDT protocol的。
2）文中涉及的4个protocol分别为：
– protocol 1：对应为 Zhang等人2019年论文《Libra: Succinct zero-knowledge proofs with optimal prover computation》中的 zero knowledge argument；
– protocol 2：为本文构建的verifiable polynomial delegation (实际亦为transparent polynomial commitment)。
– protocol 3：将protocol 2中的第6步和第2步改进，实现了zero knowledge属性，即构建了zkVPD。
– protocol 4：将protocol 1中Libral论文中的zkVPD算法替换为了本文的protocol 3中的zkVPD算法，同时对输入层和内部层进行了相应的优化，实现了本文的zero knowledge argument。
3）将polynomial commitment中的public info 各单项式的组合进行了优化，实现了算力外包给Prover，同时为减轻Prover的计算量，为Prover设计了相应的layered circuit，详见Figure 1。
4）sumcheck protocol和GKR protocol，以及单变量sumcheck protocol。

本文主要是针对layered arithmetic circuits构建了无需trusted setup的succinct zero knowledge argument scheme：

Prover time为 O ( C + n log ⁡ n ) O(C+n\log n) O(C+nlogn)，proof size为 O ( D log ⁡ C + log ⁡ 2 n ) O(D\log C+\log^2 n) O(DlogC+log2n)，for a D D D-depth circuit with n n n inputs 和 C C C gates。
若circuit为结构化的，则Verification time也是succinct的，为 O ( D log ⁡ C + log ⁡ 2 n ) O(D\log C+\log^2 n) O(DlogC+log2n)。
仅需用了轻量级的cryptographic primitives如collision-resistant hash functions，具有合理的抗量子安全性。
基于该scheme实现了一个名为Virgo的zero knowledge argument system，实验表明，其仅需53秒来生成a proof for a circuit computing a Merkle tree with 256 leaves，比其它succinct zero knowledge argument scheme快至少一个量级。其verification time为50ms，proof size为253KB，相比于现有其它系统均有竞争力。
Virgo的底层是一个新的transparent zero knowledge verifiable polynomial delegation scheme，该scheme具有logarithmic proof size和logarithmic verification time。同时该scheme is in the interactive oracle proof model。

Zero knowledge proof (ZKP) 可广泛用于：

delegation of computation
anonymous credential
privacy-preserving cryptocurrency
smart contract

现有的基于pairing构建的zkSNARK，其特点为：

proof size仅为几百bytes，verification time为几ms，且均与statement size无关；
但是需要trusted setup来生成structured reference string (SRS)，若trapdoor 泄露，则安全性将破坏。

因此，有很多研究致力于去除trusted setup，相应的协议统称为transparent ZKP protocols。
其中，Goldwasser等人2015年论文《Delegating Computation: Interactive Proofs for Muggles》中的GKR protocol具有efficient prover time和sublinear verification time for statements represented as structured arithmetic circuits，可用于large statements的证明，为doubly efficient interactive proof。但是目前为止，基于GKR protocol无法构建具有succinct proof size and verification time的transparent ZKP system。

Wahby等人2018年论文《Hyrax: Doubly-efficient zkSNARKs without trusted setup》中的transparent scheme具有square-root proof size and verification time。（详细参见博客 Hyrax: Doubly-efficient zkSNARKs without trusted setup学习笔记）
Zhang等人2019年论文《Libra: Succinct zero-knowledge proofs with optimal prover computation》中需要一个one-time trusted setup。

1.1 本文主要贡献

本文主要基于GKR构建了a transparent ZKP protocol，当the arithmetic circuit representing the statement is structured时，具有succinct proof size and verification time。本文的prover time尤其有优势，比现有的ZKP系统快一个量级，而verification time也仅需几十ms。
本文的主要贡献在于：

构建了a transparent zero knowledge verifiable polynomial delegation scheme (zkVPD)。与现有的pairing-based zkVPD schemes [59,72,73] 相比，本文的zkVPD无需trapdoor和linear-size public keys，不需要modular exponentiation 和bilinear pairing等expensive 运算。同时，本文的这种polynomial delegation/commitment机制，也可用于如verifiable secret sharing [6]，proof of retrievability [71]以及构建其它ZKP系统[55]。
– 本文的zkVPD具有特点为：
Prover time为 O ( N log ⁡ N ) O(N\log N) O(NlogN)，proof size为 O ( log ⁡ 2 N ) O(\log^2 N) O(log2N)，verification time为 O ( log ⁡ 2 N ) O(\log^2 N) O(log2N)，其中 N N N为polynomial size。
– 本文的zkVPD的构建思路为：
1）首先将polynomial evaluation看成是inner product between two vectors of size N N N：其中一个Vector为polynomial的系数（为secret info，需要由Prover commit，或者delegated to the prover after preprocessing in the case of delegation of computation）；另一个Vector为evaluation point computed on each monomial of the polynomial（为public info， Prover和Verifier均已知）。
2）然后基于Ben-Saason等人2018年论文《Aurora: Transparent Succinct Arguments for R1CS》中提出的单变量sumcheck protocol，构建了a protocol，使得Verifier相信the correctness of the inner product between a committed vector and a public vector with proof size O ( log ⁡ 2 N ) O(\log ^2 N) O(log2N)。为了保证安全性，在协议期间，Verifier需要access the two vectors at some locations randomly chosen by the verifier。对于第一个Vector，Prover可用标准的commitment scheme（如Merkle hash tree）来open it at these locations；对于第二个Vector，Verifier需要 O ( N ) O(N) O(N) time来本地计算这些值。
为了改进verification time，第二个Vector可看成是由evaluation point of size only l l l for l l l-variate polynomial组成，其中 l = O ( log ⁡ N ) l=O(\log N) l=O(logN) if the polynomial is dense。因此，可将该计算看成是a function that takes l l l inputs, expands them to a vector of N N N monomials and outputs some locations of the vector。此时，相比于本地计算，Verifier可使用GKR protocol来delegate the computation to the prover，然后验证prover的输出结果就行。对GKR protocol进行合理设计，相应的verification time可reduce为 O ( log ⁡ 2 N ) O(\log ^2 N) O(log2N)，整个Prover time为 O ( N log ⁡ N ) O(N\log N) O(NlogN)。
3）最后，借助Ames等人2017年论文《Ligero: Lightweight sublinear arguments without a trusted setup》和 Ben-Saason等人2018年论文《Aurora: Transparent Succinct Arguments for R1CS》中的类似技术，可为以上basic protocol 添加zero knowledge属性。
依照 Zhang等人2017年论文《vSQL: Verifying arbitrary SQL queries over dynamic outsourced databases》中的思想，本文将zkVPD与GKR protocol结合，构建了a transparent ZKP scheme。
基于本文scheme，实现了ZKP 系统——Virgo，优化为可take arithmetic circuits on the field generated by Mersenne primes，the operations on which can be implemented efficiently using integer additions, multiplications and bit operations in C++。相应的代码已开源在https://github/sunblaze-ucb/Virgo 。

1.2 相关研究

1.2.1 zero knowledge proof相关研究

1989年，Goldwasser等人1989年论文《The knowledge complexity of interactive proof systems》中，基于probabilistically checkable proofs (PCPs)提出了zero knowledge proof。
Gennaro等人2013年论文《Quadratic span programs and succinct NIZKs without PCPs》中引入了quadratic arithmetic programs (QAPs)，基于此产生了一系列efficient implementation of SNARKs：[12, 17, 24, 35, 38, 60, 68]
– Ben-Sasson等人2013年论文《SNARKs for C: Verifying program executions succinctly and in zero knowledge》
– Ben-Sasson等人2014年论文《Scalable zero knowledge via cycles of elliptic curves》
– Braun等人2013年论文《Verifying computations with state》
– Costello等人2015年论文《Geppetto: Versatile veriﬁable computation》
– Fiore等人2016年论文《Hash ﬁrst, argue later: Adaptive veriﬁable computations on outsourced data》
– Parno等人2013年论文《Pinocchio: Nearly practical veriﬁable computation》
– Wahby等人2015年论文《Eﬃcient ram and control ﬂow in veriﬁable outsourced computation》
以上这些基于QAP构建的SNARKs具有constant proof size，constant verification time，这些特性在cryptocurrency和smart contract等实际应用中非常有用。但是，其需要a per-statement trusted setup，且在Prover端具有高开销和高内存消耗，使得其难以扩展用于large statements。
目前也有基于安全多方技术来生成SRS，以make the SRS universal and updatable的研究，比如：
– Groth等人2018年论文《Updatable and universal common reference strings with applications to zk-snarks》
– Maller等人2019年论文《Sonic: Zero-knowledge snarks from linearsize universal and updateable structured reference strings》

为了去除trusted setup，构建transparent ZKP scheme：

Ames等人2017年论文Ames等人2017年论文《Ligero: Lightweight sublinear arguments without a trusted setup》中基于“(MPC)-in-the-head”技术，构建了名为Ligero的ZKP scheme。仅需要使用对称密钥操作，实际prover time很快，但是其proof size为 O ( C ) O(\sqrt{C}) O(C )，verification time为quasi-linear to the size of the circuit。这个可归类为 interactive oracle proofs (IOPs)。
Ben-Sasson等人2018年论文《STARK: Scalable, transparent, and post-quantum secure computational integrity》中构建的transparent ZKP in the RAM model of computation也可归类为IOPs。它们的verification time is only linear to the description of the RAM program，and succinct (logarithmic) in the time required for program execution。
Ben-Sasson等人2018年论文《Aurora: Transparent Succinct Arguments for R1CS》中的ZKP系统也可归类为IOPs，具有的proof size为 O ( log ⁡ 2 C ) O(\log^2 C) O(log2C)。
本文构建的zkVPD和ZKP scheme也属于IOPs范畴。
Goldwasser等人2015年论文《Delegating Computation: Interactive Proofs for Muggles》中构建了an efficient interactive proof for layered arithmetic circuits。
Zhang等人2017年论文《vSQL: Verifying arbitrary SQL queries over dynamic outsourced databases》中，在Goldwasser等人2015年论文《Delegating Computation: Interactive Proofs for Muggles》的基础上，将其扩展为an argument system，以用于verifiable polynomial delegation。

后续研究中借助Cramer and Damgard transformation [36] （Cramer和Damgard 1998年论文《Zero-knowledge proofs for ﬁnite ﬁeld arithmetic, or: Can zeroknowledge be for free?》）and random masking polynomials [32] （Chiesa等人2017年论文《A Zero Knowledge Sumcheck and its Applications》）实现了zero knowledge属性：

Wahby等人2018年论文《Hyrax: Doubly-efficient zkSNARKs without trusted setup》中的transparent ZKP，其proof size和verification time均为 O ( n ) O(\sqrt{n}) O(n )，其中 n n n为the input size of the circuit。
Zhang等人2017年论文《A Zero-Knowledge version of vSQL》和 Zhang等人2019年论文《Libra: Succinct zero-knowledge proofs with optimal prover computation》需要one-time trusted setup，其为succinct for structured circuits。

GKR协议在[34, 64, 67, 69, 75]等中进行了改进，Zhang等人2019年论文《Libra: Succinct zero-knowledge proofs with optimal prover computation》中的GKR协议可实现 O ( C ) O(C) O(C) prover time for arbitrary circuits。

基于discrete log assumption构建的transparent ZKP有：[8, 21, 28, 44]

Groth等人2009年论文《Linear algebra with sub-linear zero-knowledge arguments》
Bayer等人2012年论文《Eﬃcient zero-knowledge argument for correctness of a shuﬄe》
Bootle等人2016年论文《Eﬃcient zero-knowledge arguments for arithmetic circuits in the discrete log setting》
Bu¨nz等人2018年论文《Bulletproofs: Short proofs for confidential transactions and more》

基于hash 构建的transparent ZKP有：[22]

Bootle等人2017年论文《Linear-time zero-knowledge proofs for arithmetic circuit satisfiability》

基于lattice构建的transparent ZKP有：

Baum等人2018年论文《Sub-linear lattice-based zero-knowledge arguments for arithmetic circuits》

相应各transparent ZKP的性能对比为：

1.2.2 verifiable polynomial delegation相关研究

Verifiable polynomial delegation (VPD)：
允许Verifier将polynomial evaluation的计算委托给a powerful Prover，Verifier只需验证结果是否正确 in time that is constant or logarithmic to the size of polynomial。

早期的研究主要有：[18,39,50]

Benabbas等人2011年论文《Verifiable delegation of computation over large datasets》
Fiore等人2012年论文《Publicly verifiable delegation of large polynomials and matrix computations, with applications》
Kate等人2010年论文 [KZG10]《Constant-size commitments to polynomials and their application》
Papamanthou等人2013年论文《Signatures of correct computation》在[KZG10]的基础上，实现了多变量polynomial commitment。
Zhang等人2017年论文《vSQL: Verifying arbitrary SQL queries over dynamic outsourced databases》基于powers of exponent assumption 假设，extend the scheme to an argument of knowledge，允许Prover commit to a multivariate polynomial，和 open to evaluations at points queried by the verifier。
Zhang等人2017年论文《A Zero-Knowledge version of vSQL》进一步增加了zero knowledge属性。

以上这些研究都是基于bilinear maps构建的，需要a trusted setup phase来生成linear-size public keys with a trapdoor。

Bu¨nz等人2019年论文《Transparent snarks from dark compilers》中提出了另一种transparent polynomial commitment scheme without trusted setup。该scheme使用unknown order group，技术细节有别于本文的实现。在该论文中指出，Prover time为 O ( N ) O(N) O(N) modulo exponentiation in the group, Verifier time为 O ( log ⁡ N ) O(\log N) O(logN) modulo exponentiation in the group，Proof size为 O ( log ⁡ N ) O(\log N) O(logN) group elements。在该论文第6章指出，对于具有 2 20 2^{20} 220 gates的circuit，proof size约为10~20KB，相应的prover time和verifier time未指出。本文的方案，proof size会更大一点，但是prover time和verifier time 应该会更快一点。

1.3 相关定义

对于多变量polynomial f f f，其”variable-degree”为 the maximum degree of f f f in any of its variables。
相关的多项式运算，可通过FFT（加速多项式乘法，通过两次FFT可知道多项式乘积的点值表示）或者IFFT（将点值表示法转换为系数表示法）来高效实现。（可参见博客十分简明易懂的FFT（快速傅里叶变换））
特别地，基于divide-and-conquer算法，polynomial evaluation and interpolation over a multiplicative coset of size n n n of a finite field借助标准FFT协议，可仅通过 O ( n log ⁡ n ) O(n\log n) O(nlogn) field operations实现。
zero-knowledge verifiable polynomial delegation（zkVPD）定义：
设置 F \mathbb{F} F为a finite field， F \mathcal{F} F为a family of l l l-variate polynomial over F \mathbb{F} F， d d d为a variable-degree parameter。
使用 W l , d \mathcal{W}_{l,d} Wl,d来表示the collection of all monomials in F \mathcal{F} F， N = ∣ W l , d ∣ = ( d + 1 ) l N=|\mathcal{W}_{l,d}|=(d+1)^l N=∣Wl,d∣=(d+1)l。
A zkVPD for f ∈ F f\in\mathcal{F} f∈F and t ∈ F l t\in\mathbb{F}^l t∈Fl 包含如下算法：
（1） p p ← z k V P D . K e y G e n ( 1 λ ) pp\leftarrow zkVPD.KeyGen(1^{\lambda}) pp←zkVPD.KeyGen(1λ) （为transparent，不需要trapdoor信息）
（2） c o m ← z k V P D . C o m m i t ( f , r f , p p ) com\leftarrow zkVPD.Commit(f,r_f,pp) com←zkVPD.Commit(f,rf,pp)
（3） ( ( y , π ) ; { 0 , 1 } ) ← < z k V P D . O p e n ( f , r f ) , z k V P D . V e r i f y ( c o m ) > ( t , p p ) ((y,\pi);\{0,1\})\leftarrow <zkVPD.Open(f,r_f), zkVPD.Verify(com)>(t,pp) ((y,π);{0,1})←<zkVPD.Open(f,rf),zkVPD.Verify(com)>(t,pp) （其中 π \pi π为the transcript seen by the verifier during the interaction with zkVPD.Open，类似non-interactive scheme中的proof。）
zkVPD除具有completeness和soundness属性之外，还具有zero knowledge属性：

2. 基于GKR构建的zero knowledge argument

Goldwasser等人2015年论文《Delegating Computation: Interactive Proofs for Muggles》中的GKR protocol 构建了an interactive proof protocol for layered arithmetic circuit。
Zhang等人2019年论文《Libra: Succinct zero-knowledge proofs with optimal prover computation》Goldwasser的基础上进行了改进，通过使用multiple instances of zkVPD schemes，扩展为了a zero knowledge argument。
Libra的详细内容有：

Sumcheck protocol
GKR protocol

2.1 Sumcheck protocol

Sumcheck protocol：是指sum a polynomial f : F l → F f:\mathbb{F}^l\rightarrow \mathbb{F} f:Fl→F on te binary hypercube ∑ b 1 , b 2 , ⋯ , b l ∈ { 0 , 1 } f ( b 1 , b 2 , ⋯ , b l ) \sum_{b_1,b_2,\cdots,b_l\in\{0,1\}}f(b_1,b_2,\cdots,b_l) ∑b1,b2,⋯,bl∈{0,1}f(b1,b2,⋯,bl)。若直接计算该sum，需要exponential time in l l l，因为存在 2 l 2^l 2l个 b 1 , b 2 , ⋯ , b l b_1,b_2,\cdots, b_l b1,b2,⋯,bl组合。Lund等人1992年论文《Algebraic Methods for Interactive Proof Systems》中提出了a sumcheck protocol，允许a verifier V V V to delegate the computation to a computationally unbounded prover P P P, who can convince V V V the correctness of the sum。在sumcheck protocol的最后， V V V需要an oracle access to the evaluation of f f f at a random point r ∈ F l r\in\mathbb{F}^l r∈Fl chosen by V V V。该sumcheck protocol的proof size为 O ( d l ) O(dl) O(dl)，其中 d d d为the variable-degree of f f f，verification time 为 O ( d l ) O(dl) O(dl)。该sumcheck protocol为complete and sound with ϵ = d l ∣ F ∣ \epsilon=\frac{dl}{|\mathbb{F}|} ϵ=∣F∣dl。

2.2 GKR protocol

GKR protocol：假设 C C C为a layered arithmetic circuit with depth D D D over a finite field F \mathbb{F} F。第 i i i层的每个gate的输入来自于第 i + 1 i+1 i+1层的2个gates，第 0 0 0层为输出层，第 D D D层为输入层。
GKR协议需要逐层处理：

Upon receiving the claimed output from P P P，in the first round, V V V和 P P P运行a sumcheck protocol来将the claim about the output reduce为 a claim about the values in the layer above。
在第 i i i轮， P P P和 V V V通过sumcheck协议将a claim about layer i − 1 i-1 i−1 reduce为a claim about layer i i i。
最后，the protocol terminates with a claim about the input layer D D D, which can be checked directly by V V V。若该check passes，则 V V V 接收the claimed output。

将第 i i i层的gates数量表示为 S i S_i Si，设置 s i = ⌈ log ⁡ S i ⌉ s_i= \left \lceil \log S_i \right \rceil si=⌈logSi⌉。
定义a function V i : { 0 , 1 } s i → F V_i:\{0,1\}^{s_i}\rightarrow \mathbb{F} Vi:{0,1}si→F，输入为a binary string b ∈ { 0 , 1 } s i b\in\{0,1\}^{s_i} b∈{0,1}si，输出为第 i i i层的gate b b b的输出，其中 b b b称为the gate label。
根据function的定义， V 0 V_0 V0表示的是circuit的输出， V D V_D VD表示的是circuit的输入.
由于sumcheck protocol works on F \mathbb{F} F，可将 V i V_i Vi extend为its multilinear extension，the unique polynomial V ~ i : F s i → F \tilde{V}_i:\mathbb{F}^{s_i}\rightarrow \mathbb{F} V~i:Fsi→F，使得 V ~ i ( x 1 , x 2 , ⋯ , x s i ) = V i ( x 1 , x 2 , ⋯ , x s i ) \tilde{V}_i(x_1,x_2,\cdots,x_{s_i})=V_i(x_1,x_2,\cdots,x_{s_i}) V~i(x1,x2,⋯,xsi)=Vi(x1,x2,⋯,xsi) for all x 1 , x 2 , ⋯ , x s i ∈ { 0 , 1 } s i x_1,x_2,\cdots,x_{s_i}\in\{0,1\}^{s_i} x1,x2,⋯,xsi∈{0,1}si。
根据Cormode等人2012年论文《Practical Veriﬁed Computation with Streaming Interactive Proofs》中的研究成果，the closed form of V ~ i \tilde{V}_i V~i可按如下方式计算：
V ~ i ( x 1 , x 2 , ⋯ , x s i ) = ∑ b ∈ { 0 , 1 } s i ∏ i = 1 s i [ ( ( 1 − x i ) ( 1 − b i ) + x i b i ) ⋅ V i ( b ) ] \tilde{V}_i(x_1,x_2,\cdots,x_{s_i})=\sum_{b\in\{0,1\}^{s_i}}\prod_{i=1}^{s_i}[((1-x_i)(1-b_i)+x_ib_i)\cdot V_i(b)] V~i(x1,x2,⋯,xsi)=∑b∈{0,1}si∏i=1si[((1−xi)(1−bi)+xibi)⋅Vi(b)] …… （1）
其中 b i b_i bi为 i i i-th bit of b。
根据以上定义，可将the evaluations of V ~ i \tilde{V}_i V~i表示为a summation of evaluations of V ~ i + 1 \tilde{V}_{i+1} V~i+1：
α i V ~ i ( u ( i ) ) + β i V ~ i ( v ( i ) ) = ∑ x , y ∈ { 0 , 1 } s i + 1 f i ( V ~ i + 1 ( x ) , V ~ i + 1 ( y ) ) \alpha_i\tilde{V}_i(u^{(i)})+\beta_i\tilde{V}_i(v^{(i)})=\sum_{x,y\in\{0,1\}^{s_{i+1}}}f_i(\tilde{V}_{i+1}(x),\tilde{V}_{i+1}(y)) αiV~i(u(i))+βiV~i(v(i))=∑x,y∈{0,1}si+1fi(V~i+1(x),V~i+1(y)) …… （2）
其中 u ( i ) , v ( i ) ∈ F s i u^{(i)}, v^{(i)}\in\mathbb{F}^{s_i} u(i),v(i)∈Fsi为random vectors， α i , β i ∈ F \alpha_i,\beta_i\in\mathbb{F} αi,βi∈F为random values。注意 f i f_i fi depends on α i , β i , u ( i ) , v ( i ) \alpha_i,\beta_i, u^{(i)}, v^{(i)} αi,βi,u(i),v(i)。

根据公式（2），GKR protocol的运行流程为：

P： P P P将the claimed output of the circuit 发送给 V V V。
V： V V V定义polynomial V ~ 0 \tilde{V}_0 V~0，并计算KaTeX parse error: Expected 'EOF', got '}' at position 42: …e{V}_0(v^{(0)})}̲ for random u ( 0 ) , v ( 0 ) ∈ F s 0 u^{(0)},v^{(0)}\in\mathbb{F}^{s_0} u(0),v(0)∈Fs0。然后 V V V选择2个随机值 α 0 , β 0 \alpha_0,\beta_0 α0,β0，然后触发a sumcheck protocol on 公式（2） with P P P for i = 0 i=0 i=0。
在sumcheck的最后， V V V需要an oracle access to the evaluation of f 0 f_0 f0 at u ( 1 ) , v ( 1 ) u^{(1)},v^{(1)} u(1),v(1) randomly selected in F s 1 \mathbb{F}^{s_1} Fs1。为了计算该evaluation值， V V V asks P P P to send V ~ 1 ( u ( 1 ) ) \tilde{V}_1(u^{(1)}) V~1(u(1)) and V ~ 1 ( v ( 1 ) ) \tilde{V}_1(v^{(1)}) V~1(v(1))。除了 V ~ 1 ( u ( 1 ) ) \tilde{V}_1(u^{(1)}) V~1(u(1)) 和 V ~ 1 ( v ( 1 ) ) \tilde{V}_1(v^{(1)}) V~1(v(1)) 这两个值之外， f 0 f_0 f0 only depends on α 0 , β 0 , u ( 0 ) , v ( 0 ) \alpha_0,\beta_0,u^{(0)},v^{(0)} α0,β0,u(0),v(0) and the gates and wiring in layer 0, which are all known to V V V and can be computed by V V V directly。
这样， V V V和 P P P就将two evaluations of V ~ 0 \tilde{V}_0 V~0 reduce为了two evaluations of V ~ 1 \tilde{V}_1 V~1 in layer 1。
V V V和 P P P逐层 repeat the protocol recursively layer by layer。
最终， V V V收到2个claimed evaluations V ~ D ( u ( D ) ) , V ~ D ( v ( D ) ) \tilde{V}_D(u^{(D)}), \tilde{V}_D(v^{(D)}) V~D(u(D)),V~D(v(D))，然后check the correctness of these two claims directly by evaluating V ~ D \tilde{V}_D V~D，which is defined by the input of the circuit。

2.3 将GKR扩展至zero knowledge argument

GKR协议存在2个缺陷：

（1）It is not an argument system supporting witness from P P P，as V V V needs to evaluate V ~ D \tilde{V}_D V~D locally in the last round；（即不支持在circuit输入存在私有信息——witness w w w，因为GKR最后一轮中 V V V需要获取circuit的所有输入来进行本地计算。）
（2）It is not zero knowledge, as in each round, both the sumcheck protocol and the two evaluations of V ~ i \tilde{V}_i V~i leak information about the values in layer i i i。（不具有zero knowledge属性。）

Xie等人2019年论文《Libra: Succinct zero-knowledge proofs with optimal prover computation》中，借助zero knowledge polynomial delegation，解决了以上两个问题，将GKR扩展至了zero knowledge argument。

为了支持witness w w w as the input to the circuit， P P P commits to V ~ D \tilde{V}_D V~D using zkVPD before running the GKR protocol。在GKR的最后一轮，不再由 V V V在本地进行evaluating V ~ D \tilde{V}_D V~D，而改为 V V V asks P P P to open V ~ D \tilde{V}_D V~D at two random points u ( D ) , v ( D ) u^{(D)},v^{(D)} u(D),v(D) selected by V V V and validates them using zkVPD.Verify。这样， V V V就不再需要直接获取 w w w，而相应的soundness still holds because of the soundness guarantee of zkVPD。
为了增加zero-knowledge属性，借鉴Chiesa等人2017年论文《A Zero Knowledge Sumcheck and its Applications》中的思路，引入random polynomials来mask the polynomial V ~ i \tilde{V}_i V~i和the sumcheck protocol，使得proof不再泄露信息。为了保证correctness和soundness，这些random polynomials 需使用zkVPD协议进行commit，然后open at random points chosen by V V V。
(a) 以第 i i i层为例，Prover可选择一个随机的双变量多项式 R i ( x 1 , z ) R_i(x_1,z) Ri(x1,z)，定义：【来mask polynomial V ~ i \tilde{V}_i V~i】
V ˙ i ( x 1 , ⋯ , x s i ) = V ~ i ( x 1 , ⋯ , x s i ) + Z i ( x 1 , ⋯ , x s i ) ∑ z ∈ { 0 , 1 } R i ( x 1 , z ) \dot{V}_i(x_1,\cdots,x_{s_i})=\tilde{V}_i(x_1,\cdots,x_{s_i})+Z_i(x_1,\cdots,x_{s_i})\sum_{z\in\{0,1\}}R_i(x_1,z) V˙i(x1,⋯,xsi)=V~i(x1,⋯,xsi)+Zi(x1,⋯,xsi)∑z∈{0,1}Ri(x1,z) …… （3）
其中：
Z i ( x ) = ∏ i = 1 s i x i ( 1 − x i ) Z_i(x)=\prod_{i=1}^{s_i}x_i(1-x_i) Zi(x)=∏i=1sixi(1−xi)，即 Z i ( x ) = 0 Z_i(x)=0 Zi(x)=0 for all x ∈ { 0 , 1 } s i x\in\{0,1\}^{s_i} x∈{0,1}si
V ˙ i \dot{V}_i V˙i可看成是 V i V_i Vi的low degree extension，有 V ˙ i ( x ) = V ~ i ( x ) = V i ( x ) \dot{V}_i(x)=\tilde{V}_i(x)=V_i(x) V˙i(x)=V~i(x)=Vi(x) for all x ∈ { 0 , 1 } s i x\in\{0,1\}^{s_i} x∈{0,1}si。
由于 R i R_i Ri由 P P P随机选择的，因此revealing evaluations of V ˙ i \dot{V}_i V˙i不会泄露关于 V i V_i Vi的信息，也不会泄露circuit中的其它信息。
(b) P P P选择另一个随机多项式 δ i ( x 1 , ⋯ , x s i + 1 , y 1 , ⋯ , y s i + 1 , z ) \delta_i(x_1,\cdots,x_{s_{i+1}}, y_1,\cdots, y_{s_{i+1}},z) δi(x1,⋯,xsi+1,y1,⋯,ysi+1,z)来mask the sumcheck protocol：
设置 H i = ∑ x , y ∈ { 0 , 1 } s i + 1 , z ∈ { 0 , 1 } δ i ( x 1 , ⋯ , x s i + 1 , y 1 , ⋯ , y s i + 1 , z ) H_i=\sum_{x,y\in\{0,1\}^{s_{i+1}}, z\in\{0,1\}}\delta_i(x_1,\cdots,x_{s_{i+1}},y_1,\cdots,y_{s_{i+1}},z) Hi=∑x,y∈{0,1}si+1,z∈{0,1}δi(x1,⋯,xsi+1,y1,⋯,ysi+1,z)
运行sumcheck的公式（2）变为了：
α i V ˙ i ( u ( i ) ) + β i V ˙ i ( v ( i ) ) + γ i H i = ∑ x , y ∈ { 0 , 1 } s i + 1 , z ∈ { 0 , 1 } f ’ i ( V ˙ i + 1 ( x ) , V ˙ i + 1 ( y ) , R i ( u 1 i , z ) , δ i ( x , y , z ) ) \alpha_i\dot{V}_i(u^{(i)})+\beta_i\dot{V}_i(v^{(i)})+\gamma_iH_i=\sum_{x,y\in\{0,1\}^{s_{i+1}}, z\in\{0,1\}}f’_i(\dot{V}_{i+1}(x), \dot{V}_{i+1}(y), R_i(u_1^{i},z),\delta_i(x,y,z)) αiV˙i(u(i))+βiV˙i(v(i))+γiHi=∑x,y∈{0,1}si+1,z∈{0,1}f’i(V˙i+1(x),V˙i+1(y),Ri(u1i,z),δi(x,y,z)) …… （4）
其中 γ i ∈ F \gamma_i\in\mathbb{F} γi∈F由 V V V随机选择， f i ’ f_i’ fi’由 α i , b e t a i , γ i , u ( i ) , v ( i ) , Z i ( u ( i ) ) , Z i ( v ( i ) ) \alpha_i,beta_i,\gamma_i,u^{(i)},v^{(i)},Z_i(u^{(i)}), Z_i(v^{(i)}) αi,betai,γi,u(i),v(i),Zi(u(i)),Zi(v(i)) 定义。。

这样 V V V和 P P P就可以在公式（4）上运行sumcheck协议和GKR协议。在每一轮， P P P需要额外open R i , δ i R_i, \delta_i Ri,δi at R i ( u 1 ( i ) . g ( i ) ) , R i ( v 1 ( i ) . g ( i ) ) , δ i ( u ( i + 1 ) , v ( i + 1 ) , g ( i ) ) R_i(u_1^{(i)}.g^{(i)}), R_i(v_1^{(i)}.g^{(i)}),\delta_i(u^{(i+1)}, v^{(i+1)}, g^{(i)}) Ri(u1(i).g(i)),Ri(v1(i).g(i)),δi(u(i+1),v(i+1),g(i)) for g ( i ) ∈ F g^{(i)}\in\mathbb{F} g(i)∈F randomly selected by V V V。根据这些值，在每一层， V V V可将the correctness of two evaluations V ˙ u ( i ) , V ˙ i ( v ( i ) ) \dot{V}_{u^{(i)}},\dot{V}_i(v^{(i)}) V˙u(i),V˙i(v(i)) reduce 为 two evaluations V ˙ u ( i + 1 ) , V ˙ i ( v ( i + 1 ) ) \dot{V}_{u^{(i+1)}},\dot{V}_i(v^{(i+1)}) V˙u(i+1),V˙i(v(i+1))。
此外，由于 f i f_i fi is masked by d e l t a i delta_i deltai，所以the sum check protocol is zero knowledge；
由于 V ~ i \tilde{V}_i V~i is masked by R i R_i Ri，所以the two evaluations of V ˙ i \dot{V}_i V˙i do not leak information。

Libra论文中的完整的zero knowledge argument协议为：

Libra的中定理为：

2.4 单变量sumcheck

本文的transparent zkVPD protocol是受Ben-Saason等人2018年论文《Aurora: Transparent Succinct Arguments for R1CS》中的单变量sumcheck protocol 启发的。

所谓单变量sumcheck protocol是指：
允许verifier验证the result of the sum of a univariate polynomial on a subset H \mathbb{H} H of the field F \mathbb{F} F： μ = ∑ a ∈ H f ( a ) \mu=\sum_{a\in\mathbb{H}}f(a) μ=∑a∈Hf(a)。【在Aurora论文中，要求 H \mathbb{H} H为additive coset of F \mathbb{F} F，而本文中要求 H \mathbb{H} H为multiplicative coset of F \mathbb{F} F】

当 H \mathbb{H} H为a multiplicative coset of F \mathbb{F} F时，若 g ( x ) g(x) g(x)为一个单变量多项式over F \mathbb{F} F of degree strictly less than ∣ H ∣ |\mathbb{H}| ∣H∣，则有 ∑ a ∈ H g ( a ) = g ( 0 ) ⋅ ∣ H ∣ \sum{a\in\mathbb{H}}g(a)=g(0)\cdot |\mathbb{H}| ∑a∈Hg(a)=g(0)⋅∣H∣。具体定理描述为：

根据以上定理，有：

其中 p ( x ) p(x) p(x)必须为a polynomial of degree less than ∣ H ∣ − 1 |\mathbb{H}|-1 ∣H∣−1。为了测试这个，该单变量sumcheck使用a low degree test (LDT) protocol on Reed-Solomon (RS) code。

详细的单变量sumcheck思路为：

为了证明 μ = ∑ a ∈ H f ( a ) \mu=\sum_{a\in\mathbb{H}}f(a) μ=∑a∈Hf(a)，the verifier和prover选择了a multiplicative coset of F \mathbb{F} F—— L \mathbb{L} L，以及a superset of H \mathbb{H} H，其中 ∣ L ∣ > k |\mathbb{L}|>k ∣L∣>k。
Prover将 f ( x ) f(x) f(x)分解表示为 f ( x ) = g ( x ) + Z H ( x ) ⋅ h ( x ) f(x)=g(x)+Z_{\mathbb{H}}(x)\cdot h(x) f(x)=g(x)+ZH(x)⋅h(x)，计算vectors f ∣ L f|\mathbb{L} f∣L和 h ∣ L h|\mathbb{L} h∣L。
Prover commit to 这两个vectors ( f ∣ L f|\mathbb{L} f∣L和 h ∣ L h|\mathbb{L} h∣L) using Merkle trees。
Prover定义a polynomial p ( x ) = ∣ H ∣ ⋅ f ( x ) − ∣ H ∣ ⋅ Z H ⋅ h ( x ) − μ ∣ H ∣ ⋅ x p(x)=\frac{|\mathbb{H}|\cdot f(x)- |\mathbb{H}|\cdot Z_{\mathbb{H}\cdot h(x)-\mu}}{|\mathbb{H}|\cdot x} p(x)=∣H∣⋅x∣H∣⋅f(x)−∣H∣⋅ZH⋅h(x)−μ，为a rational constraint of f f f and h h h。
为了保证the correctness of μ \mu μ，仅需测试that the degree of ( f , h ) , p (f,h),p (f,h),p低于 ( k , k − ∣ H ∣ ) , ∣ H ∣ − 1 (k,k-|\mathbb{H}|), |\mathbb{H}|-1 (k,k−∣H∣),∣H∣−1，该测试可通过low degree test（LDT）实现即可。
在LDT的最后， V V V需要oracle access to k \mathcal{k} k points of f ∣ L f|\mathbb{L} f∣L和 h ∣ L h|\mathbb{L} h∣L。 P P P将这些points和相应的merkle tree proofs一起发送给 V V V， V V V验证这些proof的正确性即可。（设置 ∣ L ∣ = O ( ∣ H ∣ ) |\mathbb{L}|=O(|\mathbb{H}|) ∣L∣=O(∣H∣)）

详细的单变量sumcheck protocol为：

2.4.1 Reed-Solomon Code定义

设 L \mathbb{L} L为a subset of F \mathbb{F} F，an RS code是指the evaluations of a polynomial ρ ( x ) \rho(x) ρ(x) of degree less than m m m ( m < L m<\mathbb{L} m<L) on L \mathbb{L} L。
使用 ρ ∣ L \rho|\mathbb{L} ρ∣L 来表示the vector of the evaluations ( ρ ( a ) ) a ∈ L (\rho(a))_{a\in\mathbb{L}} (ρ(a))a∈L，用 R S [ L , m ] RS[\mathbb{L}, m] RS[L,m] 来表示 the set of all such vectors generated by polynomials of degree less than m m m。
注意，任意的vector of size ∣ L ∣ |\mathbb{L}| ∣L∣ 都可看成是某个单变量多项式of degree less than ∣ L ∣ |\mathbb{L}| ∣L∣ evaluated on L \mathbb{L} L，因此vector和polynomial可互换使用。

2.4.2 Low degree test LDT定义

low degree test允许verifier测试 whether a polynomial/vector belongs to an RS code，即 the vector is the evaluations of some polynomial of degree less than m m m on L \mathbb{L} L。

在本文中，用 Ben-Saason等人2018年论文《Aurora: Transparent Succinct Arguments for R1CS》中的8.2 protocol (LDT protocol) 来将 an RS-encoded IOP 转换为 a regular IOP。将LDT protocol用于a sequence of polynomials ρ ⃗ \vec{\rho} ρ and their rational constraint p p p，其中 p p p为a polynomial can be computed as the division of the polynomials in ρ ⃗ \vec{\rho} ρ 。在单变量sumcheck中，the sequence of polynomials 为 ρ ⃗ = ( f , h ) \vec{\rho}=(f,h) ρ =(f,h)，the rational constraint为公式（5）。

详细的思路为：

2.4.3 Merkle hash tree定义

Ralph Merkle 1989年论文《A certified digital signature》中首次提出了Merkle hash tree的概念，用于commit a vector and open it at an index with logarithmic proof size and verification time，主要包含3个算法：

r o o t c ← M T . C o m m i t ( c ) root_c\leftarrow MT.Commit(c) rootc←MT.Commit(c)
( c i d x , π i d x ) ← M T . O p e n ( i d x , c ) (c_{idx},\pi_{idx})\leftarrow MT.Open(idx,c) (cidx,πidx)←MT.Open(idx,c)
( 1 , 0 ) ← M T . V e r i f y ( r o o t c , i d x , c i d x , π i d x ) (1,0)\leftarrow MT.Verify(root_c,idx,c_{idx},\pi_{idx}) (1,0)←MT.Verify(rootc,idx,cidx,πidx)

其安全性依赖于构建Merkle tree时所选择的hash函数的collision-resistant属性。

3. transparent zkVPD

受Ben-Saason等人2018年论文《Aurora: Transparent Succinct Arguments for R1CS》中2.4节的单变量sumcheck启发，首先构建a VPD scheme that is correct and sound。

基本的思路为：
可将 evaluation an l l l-variate polynomial f f f with variable degree d d d at point t = ( t 1 , ⋯ , t l ) t=(t_1,\cdots,t_l) t=(t1,⋯,tl) 看成是 an inner product between the vector of coefficients in f f f and the vector of all monomials in f f f evaluated at t t t。
则对于 l l l-variate polynomial with degree d d d，possible monomials的数量为 N = ∣ W l , d ∣ = ( d + 1 ) l N=|W_{l,d}|=(d+1)^l N=∣Wl,d∣=(d+1)l。设置 c = ( c 1 , ⋯ , c N ) c=(c_1,\cdots,c_N) c=(c1,⋯,cN)为the coefficients of f f f in the order defined by W l , d W_{l,d} Wl,d，使得 f ( x 1 , ⋯ , x l ) = ∑ i = 1 N c i W i ( x ) f(x_1,\cdots,x_l)=\sum_{i=1}^{N}c_iW_i(x) f(x1,⋯,xl)=∑i=1NciWi(x)，其中 W i ( x ) W_i(x) Wi(x)为the i i i-th monomial in W l , d W_{l,d} Wl,d。
定义vector T = ( W 1 ( t ) , ⋯ , W N ( t ) ) T=(W_1(t),\cdots,W_N(t)) T=(W1(t),⋯,WN(t))，则the evaluation值为 f ( t = ∑ i = 1 N c i ⋅ T i ) f(t=\sum_{i=1}^{N}c_i\cdot T_i) f(t=∑i=1Nci⋅Ti)，即可看成是the inner product of the two vectors。

选择a multiplicative coset H \mathbb{H} H，使得 ∣ H ∣ = 1 |\mathbb{H}|=1 ∣H∣=1，并插值vectors c c c和 T T T来找到the unique univariate polynomials that evaluate to c c c and T T T on H \mathbb{H} H。将这些单变量多项式分别表示为 l ( x ) , q ( x ) l(x),q(x) l(x),q(x)，分别使得 l ∣ H = c l|\mathbb{H}=c l∣H=c和 q ∣ H = T q|\mathbb{H}=T q∣H=T成立。
此时有， f ( t ) = ∑ i = 1 N c i ⋅ T i = ∑ a ∈ H l ( a ) ⋅ q ( a ) f(t)=\sum_{i=1}^{N}c_i\cdot T_i=\sum_{a\in\mathbb{H}}l(a)\cdot q(a) f(t)=∑i=1Nci⋅Ti=∑a∈Hl(a)⋅q(a)，即为the sum of the polynomial l ( x ) ⋅ q ( x ) l(x)\cdot q(x) l(x)⋅q(x) on H \mathbb{H} H。Verifier可验证该evaluation值，通过a univariate sumcheck protocol with the prover。（对应下图protocol 2的步骤1，2，3，4。）

注意 l ( x ) l(x) l(x) is defined by c c c，即the coefficients of f f f，the prover can commit to l ∣ L l|\mathbb{L} l∣L at the beginning of the protocol，而 q ( x ) q(x) q(x) is defined by the public vector T T T， verifier需要本地进行计算，需要take linear time。这就是为啥Aurora/Ligero 论文中的zero knowledge proof scheme for generic arithmetic circuit的verification time is linear in the size of the circuits了。

3.1 reduce verification time

通过以下方式，本文实现了将verification time由linear reduce为了poly-logarithmic。

基于以下观察：
尽管 T T T和 q ( x ) q(x) q(x)的size都是linear in N N N，但是defined by only l = O ( log ⁡ N ) l=O(\log N) l=O(logN) values of the evaluation point t t t。这就意味着the oracle access of k \mathcal{k} k points of q ( x ) q(x) q(x)可modeled as a function：
（1）将 t t t作为输入，evaluates all monomials W i ( t ) W_i(t) Wi(t) for all W i ∈ W l , d W_i\in W_{l,d} Wi∈Wl,d as a vector T T T；
（2）推断the vector T T T to find polynomial q ( x ) q(x) q(x), and evaluates q ( x ) q(x) q(x) on L \mathbb{L} L；
（3）输出 k \mathcal{k} k points of q ∣ L q|\mathbb{L} q∣L chosen by the verifier。
尽管the size of the function modeled as an arithmetic circuit is Ω ( N ) \Omega (N) Ω(N) with Ω ( log ⁡ N ) \Omega(\log N) Ω(logN) depth, and the size of its input and output is only O ( log ⁡ N + k ) O(\log N+\mathcal{k}) O(logN+k)。
这样，相比于直接在本地进行evaluation，Verifier可将该computation delegate给prover，然后通过GKR protocol来验证计算结果即可。同时，为了降低Prover的负担，本文专门设计了an efficient layered arithmetic circuit：

在上图中：

第一部分：input t t t中的每个 t i t_i ti值，均raised to powers of 0 , 1 , ⋯ , d 0,1,\cdots,d 0,1,⋯,d，然后expanded to T T T——the evaluations of all monomials in W l , d W_{l,d} Wl,d by multiplying one t i t_i ti at a time through a ( d + 1 ) (d+1) (d+1)-ary tree。
该部分的size为 O ( N ) = O ( ( d + 1 ) l ) O(N)=O((d+1)^l) O(N)=O((d+1)l)，depth为 O ( log ⁡ d + l ) O(\log d+l) O(logd+l)。
第二部分：首先构建a circuit for an IFFT 来计算 q ( x ) q(x) q(x)多项式的系数 from its evaluations T T T，然后运行an FFT 来evaluate q ∣ L q|\mathbb{L} q∣L from the coefficients of q ( x ) q(x) q(x)。
本文实际使用Butterfly circuit来实现FFT和IFFT，该Butterfly circuit的size为 O ( N log ⁡ N ) O(N\log N) O(NlogN)，depth为 O ( log ⁡ N ) O(\log N) O(logN)。
最终： k \mathcal{k} k points are selected from q ∣ L q|\mathbb{L} q∣L。由于该算力委托of the GKR protocol发生在Protocol 2的最后阶段，这些points已经由Verifier确定了，因此，the points to output are directly hard-coded into the circuit with size O ( k ) O(\mathcal{k}) O(k) and depth 1。No heavy techniques for random accesses in the circuit is needed。因此，the whole circuit size 为 O ( N log ⁡ N ) O(N\log N) O(NlogN)，depth为 O ( log ⁡ N ) O(\log N) O(logN)，with l l l inputs and k \mathcal{k} k outputs。

可将以上技术用于generic zero knowledge proof scheme，如证明 y ⃗ = A w ⃗ \vec{y}=\mathbf{A}\vec{w} y =Aw ，其中矩阵 y ⃗ , A \vec{y},\mathbf{A} y ,A为public info， w ⃗ \vec{w} w 为secret info。
可引入随机vector r ⃗ \vec{r} r ，改为证明 μ = r ⃗ y ⃗ = r ⃗ A ⋅ w ⃗ \mu=\vec{r}\vec{y}=\vec{r}\mathbf{A}\cdot \vec{w} μ=r y =r A⋅w 。从而借助以上protocol 2来实现证明。并使用Figure 1中的GKR protocol来将 r ⃗ A \vec{r}\mathbf{A} r A的计算委托给prover。

3.2 添加zero knowledge 属性

Protocol 2中的VPD不具备zero knowledge属性。
直观地，在Protocol 2 中有2处存在信息泄露：
1）在第6步中， P P P opens evaluations of l ( x ) l(x) l(x)，会泄露 f f f的系数；
2）在第4步， P P P和 V V V执行low degree tests on ( l ( x ) ⋅ q ( x ) , h ( x ) ) , p ( x ) (l(x)\cdot q(x),h(x)),p(x) (l(x)⋅q(x),h(x)),p(x)，the proofs of LDT会泄露这些多项式的信息，进而泄露 f f f的信息。

为了实现zero knowledge属性，借助 [5,14] 论文中的思想：

为了避免第6步中的泄露，Prover引入随机degree k \mathcal{k} k 多项式 r ( x ) r(x) r(x)，mask l ( x ) l(x) l(x)为 l ’ ( x ) = l ( x ) + Z H ( x ) ⋅ r ( x ) l’(x)=l(x)+Z_{\mathbb{H}}(x)\cdot r(x) l’(x)=l(x)+ZH(x)⋅r(x)，其中 Z H ( x ) = ∏ a ∈ H ( x − a ) Z_{\mathbb{H}}(x)=\prod_{a\in\mathbb{H}}(x-a) ZH(x)=∏a∈H(x−a)。注意其中 l ’ ( a ) = l ( a ) l’(a)=l(a) l’(a)=l(a) for all a ∈ H a\in\mathbb{H} a∈H。因此，对于任意的 k \mathcal{k} k evaluations of l ’ ( x ) l’(x) l’(x) outside H \mathbb{H} H do not reveal any information about l ( x ) l(x) l(x) because of the masking polynomial r ( x ) r(x) r(x)。 l ’ ( x ) l’(x) l’(x)的degree为 ∣ H ∣ + k |\mathbb{H}|+\mathcal{k} ∣H∣+k，同时定义 U = L − H \mathbb{U}=\mathbb{L}-\mathbb{H} U=L−H。
为了避免第4步中的泄露，Prover引入随机多项式 s ( x ) s(x) s(x)， s ( x ) s(x) s(x)的degree与 l ’ ( x ) ⋅ q ( x ) l’(x)\cdot q(x) l’(x)⋅q(x)相同。将 S = ∑ a ∈ H s ( a ) S=\sum_{a\in\mathbb{H}}s(a) S=∑a∈Hs(a)发送给 V V V，然后运行单变量sumcheck protocol on their random linear combination: KaTeX parse error: Undefined control sequence: \alphal at position 35: …\in\mathbb{H}}(\̲a̲l̲p̲h̲a̲l̲’(x)\cdot q(x)+… for a random α ∈ F \alpha\in\mathbb{F} α∈F chosen by V V V。这可保证both μ \mu μ和 S S S计算正确 because of the random linear combination and the linearity of the univariate sumcheck，while leaking no information about l ’ ( x ) ⋅ q ( x ) l’(x)\cdot q(x) l’(x)⋅q(x) during the protocol, as it is masked by s(x)。

本文构建的zkVPD的优点之一为：

在Protocol 2第7步仍保留在zkVPD中，其使用GKR protocol 来计算evaluations of q ( x ) q(x) q(x)，因为 q ( x ) q(x) q(x)和其evaluations值都与具体的polynomial f f f或者任何prover’s secret input 均无关。因此，可直接apply the plain version of GKR without zero knowledge, avoiding any expensive cryptographic primitives。

完整的zkVPD表示为如下Protocol 3：（注意所有的evaluations取为on U = L − H \mathbb{U}=\mathbb{L}-\mathbb{H} U=L−H而不是 L \mathbb{L} L，因为evaluations on H \mathbb{H} H将leak information about the original l ( x ) l(x) l(x)。同时， s ( x ) s(x) s(x) is also committed and opened using Merkle tree for the purpose of correctness and soundness。）

以上Protocol 3具备zero knowledge属性：

4. zero knowledge argument

可将Protocol 1中的zkVPD替换为本文的Protocol 3中的transparent zkVPD，从而实现zero knowledge argument of knowledge scheme for layered arithmetic circuits without trusted setup。
本文在此基础上从两方面进行了优化，以提升性能：

zkVPD for 输入层；
zkVPD for 内部层。

本文优化后的完整的zero knowledge argument协议为Protocol 4：

Protocol 4满足zero knowledge属性：

4.1 优化zkVPD for 输入层

对于输入层有：
V ˙ D ( x 1 , ⋯ , x s D ) = V ~ D ( x 1 , ⋯ , x s i ) + Z D ( x 1 , ⋯ , x s D ) ∑ z ∈ { 0 , 1 } R D ( x 1 , z ) \dot{V}_D(x_1,\cdots,x_{s_D})=\tilde{V}_D(x_1,\cdots,x_{s_i})+Z_D(x_1,\cdots,x_{s_D})\sum_{z\in\{0,1\}}R_D(x_1,z) V˙D(x1,⋯,xsD)=V~D(x1,⋯,xsi)+ZD(x1,⋯,xsD)∑z∈{0,1}RD(x1,z) …… （3）

观察公式（3）可发现，the variable degree of V ˙ D \dot{V}_D V˙D for x 2 , ⋯ , x s D x_2,\cdots,x_{s_D} x2,⋯,xsD为2，the variable degree for x 1 x_1 x1为3。若直接使用本文的zkVPD protocol，则prover time为 O ( s D 3 s D ) O(s_D3^{s_D}) O(sD3sD)，superlinear in the size of the input n = O ( 2 s D ) n=O(2^{s_D}) n=O(2sD)。
注意，公式（3）中的 Z D ( x ) Z_D(x) ZD(x)为公开已知的， ∑ z ∈ { 0 , 1 } R D x 1 , z ) \sum_{z\in\{0,1\}}R_Dx_1,z) ∑z∈{0,1}RDx1,z)为degree-1 univariate polynomial，即 ∑ z ∈ { 0 , 1 } R D ( x 1 , z ) = a 0 + a 1 x 1 \sum_{z\in\{0,1\}}R_D(x_1,z)=a_0+a_1x_1 ∑z∈{0,1}RD(x1,z)=a0+a1x1。因此，可将the evaluation of V ˙ D \dot{V}_D V˙D at point t ∈ F s D t\in\mathbb{F}^{s_D} t∈FsD看成是 the inner product between two vectors T T T and c c c of length n + 2 n+2 n+2。其中 T T T的前 n n n个元素为 ∏ i = 1 s D ( ( 1 − t i ) ( 1 − b i ) + t i b i ) \prod_{i=1}^{s_D}((1-t_i)(1-b_i)+t_ib_i) ∏i=1sD((1−ti)(1−bi)+tibi) for all b ∈ { 0 , 1 } s D b\in\{0,1\}^{s_D} b∈{0,1}sD，最后2个元素为 Z D ( t ) , Z D ( t ) ⋅ t 1 Z_D(t),Z_D(t)\cdot t_1 ZD(t),ZD(t)⋅t1。同理， c c c中的前 n n n个元素为 V D b V_D{b} VDb for all b ∈ { 0 , 1 } s D b\in\{0,1\}^{s_D} b∈{0,1}sD，最后2个元素为 a 0 , a 1 a_0,a_1 a0,a1。
可将Protocol 3中的vectors T T T和 c c c进行如上替换。
另外，Figure 1中的GKR circuit的第一部分的计算 T T T from t 1 , ⋯ , t s D t_1,\cdots, t_{s_D} t1,⋯,tsD 也需要做相应调整。协议的其它部分保持不变即可。
通过对输入层的优化，the prover time为 O ( n log ⁡ n ) O(n\log n) O(nlogn)，proof size为 O ( log ⁡ 2 n ) O(\log ^2 n) O(log2n)，verification time为 O ( log ⁡ 2 n ) O(\log^2 n) O(log2n)。

4.2 优化zkVPD for 内部层

Protocol 1中使用zkVPD来引入the masking polynomials R i R_i Ri和 δ i \delta_i δi in each layer。
根据定理2， δ i : F 2 s i + 1 + 1 → F \delta_i: \mathbb{F}^{2^{s_{i+1}+1}}\rightarrow \mathbb{F} δi:F2si+1+1→F为sparse polynomial，可表示为the sum of 2 s i + 1 + 1 2s_{i+1}+1 2si+1+1 univariate polynomials of degree d e g ( δ i ) = O ( 1 ) deg(\delta_i)=O(1) deg(δi)=O(1) on each variable。因此，相比于直接使用zkVPD with d = d e g ( δ i ) d=deg(\delta_i) d=deg(δi)，可model the evaluation of δ i \delta_i δi as a vector inner product between two dense vectors of size ( d e g ( δ i ) + 1 ) ⋅ ( 2 s i + 1 + 1 ) (deg(\delta_i)+1)\cdot (2s_{i+1}+1) (deg(δi)+1)⋅(2si+1+1)。the vector committed by P P P consists of all coefficients in δ i \delta_i δi，and the one known to V V V consists of the value of each variable raised to degree 0 , 1 , ⋯ , d e g ( δ i ) 0,1,\cdots,deg(\delta_i) 0,1,⋯,deg(δi)。
此外，由于Protocol 3中的第9步和第10步的vector size和variable numbers数量几乎相等， V V V可compute the evaluations of q ( x ) q(x) q(x) directly in time O ( s i + 1 ) O(s_{i+1}) O(si+1) 而不再需要通过GKR将其委托给Prover计算。
经过以上调整，最终的prover time for evaluating the masking polynomials R i R_i Ri和 δ i \delta_i δi of all layers 为 O ( D log ⁡ C log ⁡ log ⁡ C ) O(D\log C\log\log C) O(DlogCloglogC)，proof size为 O ( D log ⁡ log ⁡ 2 C ) O(D\log\log^2C) O(Dloglog2C)，verification time为 O ( D log ⁡ C ) O(D\log C) O(DlogC)。

5. 代码实现及性能评估

采用C++编写，其中transparent zkVPD的代码里大约在700行，GKR部分的代码里在2000行左右。

5.1 Field选型

本文不依赖于任何discrete log 或bilinear pairing选项，但是对finite field的选型有如下要求：
为了运行low degree test protocol，要求the field要么是an extension of F 2 \mathbb{F}_2 F2，要么存在a multiplicative subgroup of order 2 k 2^k 2k in the field for large enough k k k （可想象 2 k ≥ ∣ L ∣ = O ( ∣ H ∣ ) = O ( n ) 2^k\geq |\mathbb{L}|=O(|\mathbb{H}|)=O(n) 2k≥∣L∣=O(∣H∣)=O(n)）。