Jiaheng Zhang等人2020年论文《Virgo: Transparent Polynomial Delegation and Its Applications to Zero Knowledge Proof》发表于 IEEE Symposium on Security and Privacy 2020。
相应的代码实现：
- https://github.com/sunblaze-ucb/Virgo （C++语言实现）
相应的视频介绍：
- https://www.youtube.com/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。
本文主要基于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.com/sunblaze-ucb/Virgo 。
- 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 verifiable computation》 – Fiore等人2016年论文《Hash first, argue later: Adaptive verifiable computations on outsourced data》 – Parno等人2013年论文《Pinocchio: Nearly practical verifiable computation》 – Wahby等人2015年论文《Efficient ram and control flow in verifiable 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 finite field 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年论文《Efficient zero-knowledge argument for correctness of a shuffle》
- Bootle等人2016年论文《Efficient 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的性能对比为： 
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 应该会更快一点。
-
对于多变量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 (t,pp) ((y,π);{0,1})←(t,pp) （其中 π \pi π为the transcript seen by the verifier during the interaction with zkVPD.Open，类似non-interactive scheme中的proof。） zkVPD除具有completeness和soundness属性之外，还具有zero knowledge属性：
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
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 protocolGKR 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 Verified 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。
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的中定理为： 
本文的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为： 
设 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
最近更新
- 深拷贝和浅拷贝的区别（重点）
- 【Vue】走进Vue框架世界
- 【云服务器】项目部署—搭建网站—vue电商后台管理系统
- 【React介绍】 一文带你深入React
- 【React】React组件实例的三大属性之state，props，refs（你学废了吗）
- 【脚手架VueCLI】从零开始，创建一个VUE项目
- 【React】深入理解React组件生命周期----图文详解（含代码）
- 【React】DOM的Diffing算法是什么？以及DOM中key的作用----经典面试题
- 【React】1_使用React脚手架创建项目步骤--------详解(含项目结构说明)
- 【React】2_如何使用react脚手架写一个简单的页面？
