Marlin:Preprocessing zkSNARKs with Universal and Updatable SRS学习笔记

1. 引言

Chiesa等人2019年论文《Marlin:Preprocessing zkSNARKs with Universal and Updatable SRS》。

相关代码实现有：

• https://github.com/arkworks-rs/marlin
• https://github.com/AleoHQ/snarkVM/tree/testnet2/marlin【Aleo 2020/12/30拷贝了arkworks-rs的代码，并在此基础上进行了相应的优化和扩展】

前序博客有：

• Zcash halo2 背后技术衍化介绍

Marlin论文中，构建了预处理zkSNARKs，其structured reference string (SRS)为universal 和 updatable的。SRS具有linear size，生成的argument为constant size。

Marlin比Sonic改进了：

• prove速度快了10倍；
• verify速度快了3倍；
• 具有更小的SRS size和argument size。

Marlin中主要有2大成果：

• 1）AHP（an algebraic holographic proof (AHP) for rank-1 constraint satisfiability (R1CS)）——为information-theoretic primitive：具有linear proof length和constant query complexity。待验证的statement以encoded form存在，可实现fast verification。
• 2）a polynomial commitment scheme——为cryptographic primitive：相关实现可参看：https://github.com/arkworks-rs/poly-commit/tree/master/src/marlin。

1.1 fast verification

通常，要求Verifier验证proof的时间 应远小于 自身进行相应计算所需时间。理想情况下，验证时间 应与 read the SNARG 或 read the description of the computation 的时间相当。

为了实现fast verification，可将verification过程分为2个阶段：

• 1）offline phase：生成a short summary for a given circuit。
• 2）online phase：使用offline phase中生成的short summary来verify SNARGs（Succinct non-interactive arguments） that attest to the satisfiability of the circuit with different partial assignments to its input wires。

fast verification可要求online phase与read the SNARG (and the partial assignment)的速度相当，即可认为其是fast的。

可借助preprocessing SNARGs来实现online fast verification。

1.2 universal (and updatable) SRS

在preprocessing SNARGs中，其offline phase包含了与待预处理circuit相关的structured reference string (SRS)。这就意味着，生成/验证 不同circuit的proof 需要 不同的SRS。SRS应为无需任何可信一方参与的，可通过如ZCash的trusted setup仪式来构建。但是，对circuit的任何修改，需要再举行一次trusted setup 仪式，当应用很多时这种方式是不可持续的。

因此，要求SRS为universal的，即该SRS可支持 any circuit up to a given size bound by enabling anyone, in an offline phase after the SRS is sampled, to publicly derive a cricuit-specific SRS。

1.3 性能对比

2. 主要成果 2.1 一种生成Preprocessing SNARK with universal SRS的方法论

在offline phase对circuit进行预处理的方法 类似于构建 “holographic proofs”，即意味着：

• Verifier 无法将circuit description作为input接收，而是，make a small number of queries to an encoding of the circuit description。
• Verifier 会make a small number of queries to the proof sent by the Prover。

在本文中，假设circuit description都是low-degree polynomials，proofs也是low-degree polynomials，同时honest Prover和malicious Prover都是“algebraic”，从而成为algebraic holographic proof (AHP)。

通过合适的extractable polynomial commitment，可将任意public-coin AHP 编译转换为 相应的具有universal (and updatable) SRS的preprocessing argument。

2.2 AHP for R1CS

本文中专门为R1CS设计AHP可实现：

• linear proof length
• constant query complexity

R1CS中的circuit description为coefficient matrices。将Verifier端的输入分为：

• offline phase：称为index，包含了coefficient matrices。offline phase中encode index (coefficient matrices)的算法称为indexer。
• online phase：称为instance：包含了a partial assignment to the variables。

[Bab+91]和[GKR15]等之前的holographic算法无法实现constant query complexity。这些算法依赖multivariate sumcheck protocol applied to certain multivariate polynomials，即因以下原因会引入大量的communication cost：

• 1）the many rounds of the sumcheck protocol。
• 2）需要多变量polynomial commitment scheme，使得相应的communication cost与变量数呈线性关系。

而Marlin中的AHP：

• 1）依赖的是单变量多项式
• 2）并实现了constant query complexity
• 3）具有small communication costs

Marlin中的AHP可看成是Aurora [Ben+19c] 中R1CS algebraic protocol的“holographic 变种”。相比于Aurora，其verification time 实现了指数级改进：

2.3 Extractable polynomial commitment

[KZG10]为单变量polynomial commitment scheme。本文在此基础上进行了扩展，使其具有足够的安全性。

Papamanthou等人2013年论文 PST13——Signatures of Correct Computation 中包含多变量polynomial commitment scheme。本文算法也可扩展为基于多变量polynomial commitment scheme实现，详细可参见：

• https://github.com/arkworks-rs/poly-commit/tree/master/src/marlin/marlin_pst13_pc

3. AHP

Interactive oracle proofs (IOPs)为multi-round protocol，在每一轮中，Verifier发送a challenge，Prover会发送an oracle (which the verifier can query)。 IOP结合了 interactive proof 和 probabilistically checkable proof 的特征。

AHP在以下两方面对IOP进行了修改：

• 1）Holographic：Verifier does not receive its input explicitly，但是，具有oracle access to a prescribed encoding of it。使得Verifier可run in time that is much faster than the time to read its input in full。（基于此，可实现fast verification。）
• 2）Algebraic：honest Prover必须produce oracles that are low-degree polynomials（可保证完备性）。malicious Prover必须produce oracles that are low-degree polynomials（可保证soundness）。同时the encoded input to the verifier也必须为a low-degree polynomial。

relation表示以triple ( I , X , W ) (\mathbb{I},\mathbb{X},\mathbb{W}) (I,X,W)，其中 I \mathbb{I} I为index， X \mathbb{X} X为instance， w \mathbb{w} w为witness。 I \mathbb{I} I代表Verifier offline phase进行预处理的输入（如circuit description）。 X \mathbb{X} X代表Verifier offline phase的输入（如a partial assignment to the circuit’s input wires）。

对应an indexed relation R \mathcal{R} R的indexed language 表示为 L ( R ) \mathcal{L}(\mathcal{R}) L(R)，为对于set of pairs ( I , X ) (\mathbb{I},\mathbb{X}) (I,X)，存在witness W \mathbb{W} W使得 ( I , X , W ) ∈ R (\mathbb{I},\mathbb{X},\mathbb{W})\in\mathcal{R} (I,X,W)∈R。

AHP中包含3种角色：

• 1）Indexer I \mathbf{I} I
• 2）Prover P \mathbf{P} P
• 3）Verifier V \mathbf{V} V

a (public-coin) AHP over a field F \mathbb{F} F for an indexed relation R \mathcal{R} R 中相应的流程为：

• 1）offline phase：Indexer I \mathbf{I} I 收到待预处理的输入 index I \mathbb{I} I，输出为一个或多个单变量多项式over F \mathbb{F} F encoding I \mathbb{I} I。
• 2）online phase：Prover的输入为 ( I , X , W ) (\mathbb{I},\mathbb{X},\mathbb{W}) (I,X,W)，Verifier的输入为 X \mathbb{X} X。Prover和Verifier进行constant round交互。在每一轮中，Verifier发送a challenge，Prover发送一个或多个多项式。交互完成后， V ( X ) \mathbf{V}(\mathbb{X}) V(X) probabilistically queries the polynomials output by the indexer and the polynomials output by the prover，然后accept或reject。最重要的是，线上阶段，Verifier V \mathbf{V} V的输入不包含 I \mathbb{I} I，而是query the polynomials output by Indexer I \mathbf{I} I that encode I \mathbb{I} I。从而使所构建的Verifier V \mathbf{V} V 可run in time that is sublinear in ∣ I ∣ |\mathbb{I}| ∣I∣。

4. (Extractable) polynomial commitment

[KZG10] polynomial commitment scheme中的流程为：

• 1）Prover：为单变量多项式 p ∈ F [ X ] p\in\mathbb{F}[X] p∈F[X]生成commitment c c c
• 2）Prover：open p ( X ) p(X) p(X) at any point z ∈ F z\in\mathbb{F} z∈F，open的值为 p ( z ) p(z) p(z)
• 3）Prover：生成evaluation proof π \pi π 来证明the opened value p ( z ) p(z) p(z) is consistent with the polynomial “inside” c c c at z z z。

polynomial commitment scheme应满足如下要求：

• 1）commitment c c c 要远小于 多项式 p p p（如 c c c中包含a constant number of group elements）。【efficiency属性】
• 2）proof π \pi π必须可快速验证（如in a constant number of cryptographic operations）。【efficiency属性】
• 3）应满足binding属性，即an efficient adversary无法open the same commitment to two different values。【binding属性】
• 4）可保证the degree of the committed function。即若某adversary可open values of some function f : F → F f:\mathbb{F}\rightarrow \mathbb{F} f:F→F，则该函数 f f f的degree 应高于 所声明的多项式的degree。【extractability属性】

此外，很多polynomial commitment应用场景中，包含了多个多项式的多个commitment，也可能包含open多个point values。此时，需要考虑：

• 1）仅基于一组public parameter来commit to 多项式，这些多项式可具有不同的degree。可将[KZG10]修改为commit both to the polynomial and its shift to the maximum degree，类似于Aurora中bundle multiple low-degree tests into a single one的技术。【Enforcing multiple degree bounds：即若不同多项式 p i p_i pi​的degree d i d_i di​小于setup时的degree bound D D D，则由对 p i p_i pi​的commit 改为 对“shifted polynomials” p i ′ = X D − d i p i ( X ) p_i'=X^{D-d_i}p_i(X) pi′​=XD−di​pi​(X) 进行commit。proof evaluation时，若 p i p_i pi​ evaluate to v i v_i vi​ at z z z，则 p i ′ p_i' pi′​ evaluate to z D − d i v i z^{D-d_i}v_i zD−di​vi​。Aurora中基于此派生了low-degree tests for specific degree bounds。 为了进一步减少scalar multiplications（由 Ω ( D ) \Omega(D) Ω(D) reduce为 O ( d i ) O(d_i) O(di​)），Marlin中构建的多项式为 p i ⋆ ( X ) = p i ′ ( x ) − p i ( z ) X D − d i p_i^{\star}(X)=p_i'(x)-p_i(z)X^{D-d_i} pi⋆​(X)=pi′​(x)−pi​(z)XD−di​，该多项式evaluate to 0 0 0 at z z z。 】
• 2）需要可batch evaluation proofs across different polynomials for the same location。【Committing to multiple polynomials at once：针对的场景为open multiple polynomials [ p i ] i = 1 n [p_i]_{i=1}^{n} [pi​]i=1n​ at the same point z z z。由Verifier提供challenge ξ \xi ξ，Prover构建多项式 p = ∑ i = 1 n ξ i p i p=\sum_{i=1}^{n}\xi^ip_i p=∑i=1n​ξipi​，然后改为对 p p p进行commit和open。利用了commitment的加法同态属性。有 c = ∑ i = 1 n ξ i c i c=\sum_{i=1}^{n}\xi^ic_i c=∑i=1n​ξici​， v = ∑ i = 1 n ξ i v i v=\sum_{i=1}^{n}\xi^iv_i v=∑i=1n​ξivi​。】
• 3）Evaluate at a query set instead of a single point。多项式 [ p i ] i = 1 n [p_i]_{i=1}^{n} [pi​]i=1n​ evaluate at a set of points Q = [ z i ] i = 1 k Q=[z_i]_{i=1}^{k} Q=[zi​]i=1k​，Prover将多项式根据所需evaluate的point进行分组，即partition the polynomials [ p i ] i = 1 n [p_i]_{i=1}^{n} [pi​]i=1n​ into different groups such that every polynomial in a group is to be evaluated at the same point z i z_i zi​。Prover为每个group运行 P C . O p e n PC.Open PC.Open，然后输出the resulting list of evaluation proofs。

polynomial commitment scheme P C PC PC中的算法 P C = ( S e t u p , T r i m , C o m m i t , O p e n , C h e c k ) PC=(Setup, Trim, Commit,Open,Check) PC=(Setup,Trim,Commit,Open,Check)：

• P C . S e t u p PC.Setup PC.Setup：输入为security parameter 和 maximum supported degree bound D D D，输出为public parameters p p pp pp——包含the description of a finite field F \mathbb{F} F。
• P C . T r i m PC.Trim PC.Trim：deterministically specialize these parameters for a given set of degree bounds，输出为a committer key c k ck ck 和 a receiver key r k rk rk。
• P C . C o m m i t PC.Commit PC.Commit：输入为committer key c k ck ck、a list of polynomials p p p with respective degree bounds d d d，输出为a set of commitments c c c。
• P C . O p e n PC.Open PC.Open：输入为degree bounds为 d d d 的 polynomials p p p、具有任意evaluation points for each polynomial的query set Q Q Q，输出为claimed evaluation set values v v v 和 proof π \pi π。
• P C . C h e c k PC.Check PC.Check：输入为commitment c c c、query set Q Q Q、evaluation set values v v v 和 proof π \pi π，输出为accept或reject。

4.1 [KZG10]的 P o l y C o m m i t D L PolyCommit_{DL} PolyCommitDL​ polynomial commitment scheme

[KZG10]中：

• setup phase P C . S e t u p PC.Setup PC.Setup的输出有：

  • bilinear group ( G 1 , G 2 , G T , q , G , H , E ) (\mathbb{G}_1,\mathbb{G}_2,\mathbb{G}_T,q, G,H,E) (G1​,G2​,GT​,q,G,H,E)
  • Committer key c k ck ck 和 receiver key r k rk rk for a given degree bound D D D committer key中包含了group elements encoding powers of a random field element β \beta β，即 c k = { G , β G , ⋯   , β D G } ∈ G 1 D + 1 ck=\{G,\beta G,\cdots, \beta^DG\}\in\mathbb{G}_1^{D+1} ck={G,βG,⋯,βDG}∈G1D+1​。 receiver key中包含group elements r k = ( G , H , β H ) ∈ G 1 × G 2 2 rk=(G,H,\beta H)\in \mathbb{G}_1\times \mathbb{G}_2^2 rk=(G,H,βH)∈G1​×G22​。 注意，SRS中包含了 c k ck ck和 r k rk rk，SRS为updatable是因为SRS中的group element的系数都是monomials。

• P C . C o m m i t PC.Commit PC.Commit：对于多项式 p ∈ F q [ X ] p\in\mathbb{F}_q[X] p∈Fq​[X]，Prover计算commitment c = p ( β ) G c=p(\beta)G c=p(β)G。

• P C . O p e n PC.Open PC.Open：Prover计算 v = p ( z ) v=p(z) v=p(z)，计算witness polynomial w ( X ) = ( p ( X ) − p ( z ) ) / ( X − z ) w(X)=(p(X)-p(z))/(X-z) w(X)=(p(X)−p(z))/(X−z)，对 w ( X ) w(X) w(X)进行commit，将该commitment值作为proof： π = w ( β ) G \pi=w(\beta)G π=w(β)G。当且仅当 p ( z ) = v p(z)=v p(z)=v时，witness function w w w为a polynomial。若 w w w为a rational function，则无法使用 c k ck ck进行commit。

• P C . C h e c k PC.Check PC.Check：可通过判断 e ( c − v G , H ) = e ( π , β H − z H ) e(c-vG,H)=e(\pi,\beta H-zH) e(c−vG,H)=e(π,βH−zH)是否成立，来check that the proof commits to a polynomial of the form ( p ( X ) − p ( z ) ) / ( X − z ) (p(X)-p(z))/(X-z) (p(X)−p(z))/(X−z)。

为了实现extractability，目前有2种方式：

• 1）[Gro10] Groth 2010年论文《Short Pairing-based Non-interactive Zero-Knowledge Arguments》中的knowledge commitment方案，但是该方案需要依赖concrete knowledge assumption。同时，该方案的一个主要缺点是，每个commitment doubles in size。详细也可看 Short Pairing-based Non-interactive Zero-Knowledge Arguments。
• 2）[FKL18] Fuchsbauer等人2018年论文《The Algebraic Group Model and its Applications》中的commitment仍为a single group element，其安全性依赖于algebraic group model (AGM)。

4.2 基于[Gro10]的knowledge assumption构建的extractable PC【single degree bound】

基于[Gro10]的knowledge assumption构建的extractable polynomial commitment scheme为： 【其中蓝色字体通过引入randomness实现的PC具有hiding属性。】

4.3 基于[FKL18]的algebraic group model构建的extractable PC【single degree bound】

基于[FKL18]的algebraic group model构建的extractable polynomial commitment scheme为： 【其中蓝色字体通过引入randomness实现的PC具有hiding属性】

4.4 基于[FKL18]的algebraic group model构建的extractable PC【multiple degree bounds】

下图中，相比于 “4.3 基于[FKL18]的algebraic group model构建的extractable PC【single degree bound】"的不同之处以红色字体表示了：

5. Compiler：将AHP 转换为 preprocessing arguments with universal SRS

compiler的主要作用为“commit to oracles and then open query answers”。

基本流程为：

• 1）argument Index 触发 AHP Indexer生成多项式，然后使用PC Scheme来deterministically commit这些多项式。
• 2）argument Prover 和 argument Verifier交互，分别模拟AHP Prover和AHP Verifier。在每一轮中，argument Prover将AHP Prover输出的succinct polynomial commitments发出。
• 3）交互完成后，argument Verifier声明其queries to the polynomials (of the Prover and of the Indexer)。
• 4）argument Prover返回the evaluations along with an evaluation proof来证明their correctness relative to the commitments。

6. AHP for R1CS

Marlin中的AHP可看成是Aurora [Ben+19c] 中non-holographic algebraic proof for R1CS的“holographic 变种”。为了实现holography，需设计一个新的sub-protocol，来允许Verifier evaluate low-degree extensions of the coefficient matrices at a random location。而在Auora中，Verifier自身运行该计算所需时间为 p o l y ( ∣ I ∣ ) poly(|\mathbb{I}|) poly(∣I∣)；而在Marlin中，通过借助Prover的帮助 和 oracle access to the polynomials produced by Indexer，Verifier的性能实现了指数级提升，所需时间为 O ( log ⁡ ∣ I ∣ ) O(\log{|\mathbb{I}|}) O(log∣I∣)。

• Index I = ( F , n , m , A , B , C ) \mathbb{I}=(\mathbb{F},n,m,A,B,C) I=(F,n,m,A,B,C)表示coefficient matrices。【 m m m表示矩阵 A , B , C A,B,C A,B,C中具有的最多非零entry数量。 n n n表示公有和私有输入变量数之和。】
• Instance X = x ∈ F ∗ \mathbb{X}=x\in\mathbb{F}^* X=x∈F∗ 表示公有输入变量。
• Witness W = w ∈ F ∗ \mathbb{W}=w\in\mathbb{F}^* W=w∈F∗ 表示私有输入变量。

当且仅当 A z ∘ B z = C z Az\circ Bz=Cz Az∘Bz=Cz for z = ( x , w ) ∈ F n z=(x,w)\in\mathbb{F}^n z=(x,w)∈Fn时，R1CS方程式成立。

令：【set S S S的vanishing polynomial为：monic polynomial of degree ∣ S ∣ |S| ∣S∣ that vanishes on S S S，即为 ∏ γ ∈ S ( X − γ ) \prod_{\gamma\in S}(X-\gamma) ∏γ∈S​(X−γ)。】

• H H H：表示size为 n n n的subset of F \mathbb{F} F。 v H ( X ) v_H(X) vH​(X)为相应的vanishing polynomial。【所有变量】
• K K K：表示size为 m m m的subset of F \mathbb{F} F。 v K ( X ) v_K(X) vK​(X)为相应的vanishing polynomial。【矩阵中的非零entry。】

假设 H H H和 K K K为smooth multiplicative subgroups【即为FFT friendly subgroup】，从而支持：

• interpolation/evaluation over H H H in O ( n log ⁡ n ) O(n\log n) O(nlogn) operations；
• make v H ( X ) v_H(X) vH​(X) computable in O ( log ⁡ n ) O(\log n) O(logn) operations。
• interpolation/evaluation over K K K in O ( m log ⁡ m ) O(m\log m) O(mlogm) operations；
• make v K ( X ) v_K(X) vK​(X) computable in O ( log ⁡ m ) O(\log m) O(logm) operations。

令：

• M M M：为 n × n n\times n n×n矩阵，其rows/columns indexed by elements of H H H。
• M ^ ( X , Y ) \hat{M}(X,Y) M^(X,Y)：为low-degree extension of M M M，即the polynomial of individual degree less than n n n，使得对于任意的 κ , ι ∈ H \kappa,\iota\in H κ,ι∈H， M ^ ( κ , ι ) \hat{M}(\kappa,\iota) M^(κ,ι)为 M M M矩阵中的第 ( κ , ι ) (\kappa,\iota) (κ,ι)-th entry。

6.1 Aurora中的non-holographic protocol for R1CS

Aurora中的non-holographic protocol for R1CS具有：

• linear proof length
• constant query complexity

在non-holographic protocol中，Prover的输入为 ( I , X , W ) (\mathbb{I},\mathbb{X},\mathbb{W}) (I,X,W)，Verifier的输入为 ( I , X ) (\mathbb{I},\mathbb{X}) (I,X)（Verifier需要读取non-encoded index I \mathbb{I} I）。【而在holographic protocol中，Verifier的输入为 ( X ) (\mathbb{X}) (X)。】

基本流程为：

• 1）Prover P \mathbf{P} P：发送单变量多项式 z ^ ( X ) \hat{z}(X) z^(X)，其degree小于 n n n，且agrees with the variable assignment z z z on H H H；发送单变量多项式 z ^ A ( X ) , z ^ B ( X ) , z ^ C ( X ) \hat{z}_A(X),\hat{z}_B(X),\hat{z}_C(X) z^A​(X),z^B​(X),z^C​(X)，相应的degree小于 n n n，且aggress with the linear combinations z A = A z , z B = B z , z C = C z z_A=Az,z_B=Bz,z_C=Cz zA​=Az,zB​=Bz,zC​=Cz on H H H。

• 2）Prover P \mathbf{P} P：此时Prover仅需convince Verifier以下两个条件成立：

  • （1）Entry-wise product： ∀ κ ∈ H , z ^ A ( κ ) z ^ B ( κ ) − z ^ C ( κ ) = 0 \forall \kappa\in H, \hat{z}_A(\kappa)\hat{z}_B(\kappa)-\hat{z}_C(\kappa)=0 ∀κ∈H,z^A​(κ)z^B​(κ)−z^C​(κ)=0
  • （2）Linear relation： ∀ M ∈ { A , B , C } , ∀ κ ∈ H , z ^ M ( κ ) = ∑ ι ∈ H M [ κ , ι ] z ^ ( ι ) \forall M\in \{A,B,C\},\forall \kappa\in H,\hat{z}_M(\kappa)=\sum_{\iota\in H}M[\kappa,\iota]\hat{z}(\iota) ∀M∈{A,B,C},∀κ∈H,z^M​(κ)=∑ι∈H​M[κ,ι]z^(ι) （此外，prover还需convince Verifier that z ^ ( X ) \hat{z}(X) z^(X) encodes a full assignment z z z that is consistent with the partial assignment x x x。为了简化，在此处故意先不讨论此条件。）

• 3）为了证明第一个条件（Entry-wise product），

  • Prover P \mathbf{P} P：发送满足 z ^ A ( X ) z ^ B ( X ) − z ^ C ( X ) = h 0 ( X ) v H ( X ) \hat{z}_A(X)\hat{z}_B(X)-\hat{z}_C(X)=h_0(X)v_H(X) z^A​(X)z^B​(X)−z^C​(X)=h0​(X)vH​(X)的多项式 h 0 ( X ) h_0(X) h0​(X)。【该等式左侧equals zero everywhere on H H H if and only if it is a multiple of H H H's vanishing polynomial。】
  • Verifier V \mathbf{V} V： 选择random point β ∈ F \beta\in\mathbb{F} β∈F。query z ^ A ( X ) , z ^ B ( X ) , z ^ C ( X ) , h 0 ( X ) \hat{z}_A(X), \hat{z}_B(X), \hat{z}_C(X),h_0(X) z^A​(X),z^B​(X),z^C​(X),h0​(X) at β \beta β，然后自身evaluate v H ( X ) v_H(X) vH​(X) at β \beta β，最后check z ^ A ( β ) z ^ B ( β ) − z ^ C ( β ) = h 0 ( β ) v H ( β ) \hat{z}_A(\beta)\hat{z}_B(\beta)-\hat{z}_C(\beta)=h_0(\beta)v_H(\beta) z^A​(β)z^B​(β)−z^C​(β)=h0​(β)vH​(β)。 相应的soundness error为the maximum degree over the field size，此处不高于 2 n / ∣ F ∣ 2n/|\mathbb{F}| 2n/∣F∣。

• 4）为了证明第二个条件（Linear relation），Prover首先受到Verifier发来的random challenge α ∈ F \alpha\in \mathbb{F} α∈F，然后回复第二条消息：

  • 对于每个 M ∈ { A , B , C } M\in\{A,B,C\} M∈{A,B,C}，Prover P \mathbf{P} P：发送多项式 h M ( X ) , g M ( X ) h_M(X),g_M(X) hM​(X),gM​(X)，使得对于 r M ( Z , X ) = ∑ κ ∈ H r ( Z , κ ) M ^ ( κ , X ) r_M(Z,X)=\sum_{\kappa\in H}r(Z,\kappa)\hat{M}(\kappa,X) rM​(Z,X)=∑κ∈H​r(Z,κ)M^(κ,X)，满足 r ( α , X ) z ^ M ( X ) − r M ( α , X ) z ^ ( X ) = h M ( X ) v H ( X ) + X g M ( X ) r(\alpha,X)\hat{z}_M(X)-r_M(\alpha,X)\hat{z}(X)=h_M(X)v_H(X)+Xg_M(X) r(α,X)z^M​(X)−rM​(α,X)z^(X)=hM​(X)vH​(X)+XgM​(X)成立。其中 r Z , X r_{Z,X} rZ,X​为a prescribed polynomial of individual degree less than n n n such that ( r ( Z , κ ) ) κ ∈ H (r(Z,\kappa))_{\kappa\in H} (r(Z,κ))κ∈H​ are n n n linearly independent polynomials。 Aurora中通过univariate sumcheck来验证linear relation，相应的soundness error为 n / ∣ F ∣ n/|\mathbb{F}| n/∣F∣ over α \alpha α。【在Aurora中支持，已知a multiplicative subgroup S S S of F \mathbb{F} F，多项式 f ( X ) f(X) f(X) sums to σ \sigma σ，当且仅当 f ( X ) f(X) f(X)可表示为 h ( X ) v S ( X ) + X g ( X ) + σ / ∣ S ∣ h(X)v_S(X)+Xg(X)+\sigma/|S| h(X)vS​(X)+Xg(X)+σ/∣S∣ for some h ( X ) h(X) h(X) and g ( X ) g(X) g(X) with deg ⁡ ( g ) < ∣ S ∣ − 1 \deg(g)