Supersonic Transparent SNARKs from DARK Compilers学习笔记

1. 引言

Bünz 等人2020年论文《Transparent SNARKs from DARK Compilers》，首次发表于IACR-EUROCRYPT-2020。

代码实现可参见：

• https://github.com/ksju6561/Transparent-SNARKs-from-DARK-Compilers

视频解说：

• https://www.youtube.com/watch?v=m3Cc0kuzhfg

1）本文为单变量多项式和多变量多项式构建了新的polynomial commitment scheme——DARK polynomial commitment scheme：

• 该scheme的evaluation proof size为 O ( log ⁡ ( n ) ) O(\log(n)) O(log(n))的，verification time也为 O ( log ⁡ ( n ) ) O(\log(n)) O(log(n))，其中 n n n为polynomial中系数的个数。
• 底层的技术称为DARK (Diophantine Argument of Knowledge)，利用的是integer representations of polynomials和groups of unknown order。
• 基于的安全假设是strong RSA和adaptive root assumptions。
• 若以class groups来实例化，则无需trusted setup。
• 当采用a restricted class of algebraic linear IOPs时，可称为Polynomial IOPs，可实现双倍高效的public-coin interactive arguments of knowledge for any NP relation with succinct communication。
• 借助linear preprocessing，online verifier’s work is logarithmic in the circuit complexity of the relation。

2）在Sonic (Maller等人2019年论文《Sonic: Zero-knowledge snarks from linear-size universal and updatable structured reference strings》) 和 PLONK (Gabizon等人2019年论文《Plonk: Permutations over lagrangebases for oecumenical noninteractive arguments of knowledge》) 的基础上，构建了SNARK算法——Supersonic：

• 具有quasi-linear preprocessing，quasi-linear (online) prover time, logarithmic communication, and logarithmic (online) verification time in the circuit size。
• 120-bit security场景下，对于具有100万个gates的circuit，Supersonic的proof size为10KB，verification time低于100ms。
• Supersonic为transparent的，无需trusted setup。
• 通过在polynomial commitment scheme中增加hiding 变量来实现zero-knowledge evaluation。
• Supersonic为第一个完整的zk-SNARK system，具有实用的prover time和近似logarithmic proof size and verification time。

interactive proofs (IPs)的源头：

• 1985年Goldwasser等人论文《The knowledge complexity of interactive proof-systems (extended abstract)》。

probabilistically checkable proofs (PCPs)的源头：

• 1991年Babai等人论文《Checking computations in polylogarithmic time》。（最早的Polynomial IOPs (PIOPs)）
• 1992年Arora等人论文《Proof verification and hardness of approximation problems》。

proof system的一些要素：

• a prover establishes the correct performance of an arbitrary computation in a way that can be verified much more efficiently than performing the computation itself。
• succinct：prover和verifier之间的communication cost应为low，如protocol transcript应小于witness size。
• zero-knowledge：the computation may involve secret information and the prover demonstrates correct performance without leaking the secrets。如Ben-Or等人1988年论文《Everything provable is provable in zero-knowledge》中的ZK-IPs和Kilian 1992年论文《A note on efficient zero-knowledge proofs and arguments (extended abstract)》中的ZK-PCPs。

最近几年，有来自verifiable outsourced computation (such as trustless cloud computing) 的工业需求（如Walfish等人2015年论文《Verifying computations without reexecuting them: From theoretical possibility to near practicality》）。 在区块链中使用zero-knowledge proofs来平衡privacy 和 public-verifiable integrity（如ZCash中的anonymous transactions （参见Ben-Sasson等人2014年论文《Zerocash: Decentralized anonymous payments from bitcoin》、Hopwood等人2019年论文《Zcash Protocol Specification》）和以太坊中对smart contracts over private inputs的verify（如Zokrates）。在这些应用中，会将zero-knowledge proofs作为交易的一部分也记录在账本中，同时要求节点可在短时间内verify many proofs。因此，对succinctness和fast verification会有要求。 Vitalik Buterin 2016年提出的Zk rollup 中使用verifiable computation来实现区块链交易扩容。 O(1) Labs 2018年提出的 Coda protocol 中希望消除对历史区块链数据的维护。

SNARGs (succinct non-interactive arguments) 的要点：

• succinctness (the proof size is sublinear in the original computation length T T T)。
• non-interactivity (the proof is a single message)。
• prover-scalability (proof generation time scales linearly or quasi-linearly in T T T)。
• verifier-scalability (verification time is sublinear in T T T)。

目前来看，succinct statistically sound proofs是似乎不存在的。

构建proof system需要平衡的元素有：

• proof size；
• proof time；
• verification time;
• 不同的trust model；
• 不同的cryptographic assumption。

如有些proof system可借助a one-time expensive setup procedure 的preprocessing model来生成compact verification key V K VK VK，使得Verifier在后续验证proof时的效率更高。

考虑proof size和verification time，迄今为止效率最高的proof system都需要trusted preprocessing。 基于GGPR扩展的pairing-based SNARKs有：[GGPR13, SBV+13, BCI+13, BCG+13, Gro16]

• [GGPR13] Gennaro等人2012年论文《Quadratic span programs and succinct NIZKs without PCPs》
• [SBV+13] Setty等人2013年论文《Resolving the conflict between generality and plausibility in verified computation》
• [BCI+13] Bitansky等人2012年论文《Succinct noninteractive arguments via linear interactive proofs》
• [BCG+13] Ben-Sasson等人2013年论文《SNARKs for C: Verifying program executions succinctly and in zero knowledge》
• [Gro16] Groth 2016年论文《On the size of pairing-based non-interactive arguments》（在https://github.com/zkcrypto/bellman 中有相应代码实现。）

通过在a committee of parties中运行multi-party computation (MPC)，可实现相应的trusted setup——只需保证其中的一方是可信任的就足够了。在Zcash中已构建了2次这样的trusted setup仪式—— The design of the ceremony。

当proof system中不需要任何的trusted setup，则可称其为transparent的：

• Ben-Sasson等人2019年论文《Scalable zero knowledge with no trusted setup》中提出的zk-STARKs 算法，其proof size 为 O ( log ⁡ 2 T ) O(\log^2T) O(log2T)，其中 T T T为circuit size。
• Goldwasser等人2008年论文《Delegating computation: interactive proofs for muggles》中的GKR protocol可构建interactive proof，communication cost为 O ( d log ⁡ T ) O(d\log T) O(dlogT)，适于low-depth circuit of total size T T T and depth d d d。

以上这些transparent proof system的性能远远低于 SNARKs based on preprocessing。以100万gate的circuit为例，zk-STARKs的proof size为600KB，而基于preprocessing的SNARKs仅需200bytes（Groth 2016年论文《On the size of pairing-based non-interactive arguments》）。Bulletproofs也是transparent proof system，Bulletproofs的proof size要小于STARK的proof size，但是Bulletproofs的verification time与circuit size呈线性关系，对于100万gate的circuit，Bulletproofs的verification time需要将近1分钟，比STARK的verification time慢1000倍。

还有一种构建思路是，从proof system中 remove trust from the circuit preprocessing step, and instead have a universal (trusted) setup：即不再需要为每个circuit都进行一次trusted setup，a one-time trusted setup that can be reused for any computation。universal SNARK相关的研究有：[MBKM19, XZZ+19, GWC19]

• Maller等人2019年论文《Sonic: Zero-knowledge snarks from linear-size universal and updatable structured reference strings》
• Tiacheng Xie等人2019年论文《Libra: Succinct zero-knowledge proofs with optimal prover computation》
• Gabizon等人2019年论文《Plonk: Permutations over lagrangebases for oecumenical noninteractive arguments of knowledge》

以上这些proof system都是build SNARKs by combining an underlying reduction of circuit satisfiability to probabilistic testing of polynomials (with degree at most linear in the circuit size) together with polynomial commitment schemes。

在polynomial commitment scheme中：

• Prover commit to μ \mu μ-variate多项式 f f f over F \mathbb{F} F of total degree at most d d d，commitment的值远远小于直接发送 f f f的所有系数。
• Prover 提供a non-interactive argument that f ( z ⃗ ) = y f(\vec{z})=y f(z )=y，对于任意的 z ⃗ ∈ F μ , y ∈ F \vec{z}\in\mathbb{F}^{\mu},y\in\mathbb{F} z ∈Fμ,y∈F。

universal SNARK的trusted部分完全由polynomial commitment scheme’s setup来限制。可采用[KZG10] Kate等人2010年论文《Constant-size commitments to polynomials and their applications》的单变量polynomial commitment算法，但是该算法需要trusted setup。

本文在现有universal SNARK的基础上，主要贡献是：

• 提出了一种新的transparent polynomial commitment，与[KZG10] 中的 polynomial commitment算法不同，本文的不需要trusted setup。 在Ben-Sasson等人2018年论文《Fast reed-solomon interactive oracle proofs of proximity》中也指出了：transparent polynomial commitment可imply transparent SNARKs。
• 提出了一种框架，可将现有的基于polynomial commitment构建的SNARK通过interactive oracle proofs (IOPs) language 进行统一。[RRR16, BCS16]（可参见Reingold等人2016年论文《 Constant-round interactive proofs for delegating computation》和 Ben-Sasson等人2016年论文《 Interactive oracle proofs》） 本文将polynomial commitment scheme看成是Polynomial IOPs的编译器compiler，从而可以将之前的SNARKs都看成是Polynomial IOPs for NP。

1.1 DARK polynomial commitment scheme

本文构建的polynomial commitment scheme称为DARK：

• 对于有 μ \mu μ个变量的多项式，最高阶为 d d d，可选zero-knowledge的argument of knowledge for correct evaluation，具有的proof size为 O ( μ log ⁡ d ) O(\mu\log d) O(μlogd)，verify time为 O ( μ log ⁡ d ) O(\mu\log d) O(μlogd)。
• 需要unknown order group，可供选择的有2种：RSA groups和具有imaginary quadratic order的class groups。 – 若采用RSA groups，则可实现univeral preprocessing SNARKs with constant-size setup parameters。之前的研究都需要linear-size parameters。 – 若采用calss groups，则可将trusted-setup SNARKs中的trusted-setup移除，从而实现transparent SNARKs。
• 采用了Lipmaa 2013年论文《On diophantine complexity and statistical zero-knowledge arguments》中的integer commitment和Diophantine Aargument of Knowledge技术。

1.2 Polynomial IOP

所有的SNARK都可看成是：“information-theoretic statistically-sound protocol” + “cryptographic compiler”。 其中cryptographic compiler用于将protocol转换为a succinct argument at the cost of computational soundness。

在 [IKO07, BCI+13, BBC+19] Ishai等人2007年论文《Efficient arguments without short pcps》、Bitansky等人2012年论文《Succinct noninteractive arguments via linear interactive proofs》、Boneh等人2019年论文《Zero-knowledge proofs on secret-shared data via fully linear PCPs》 的algebraic linear IOPs的基础上进行了改进，提出了Polynomial IOP:

• 在每一轮交互中，Prover都给Verifier oracle access to a multivariate polynomial function of bounded degree。
• Verifier可query this oracle to evaluate the polynomial on arbitrary points of its choice。

现有的universal SNARK和transparent SNARK均为circuit satisfiability 提供了各种statistically-sound Polynomial IOPs（对于STARKs，提供的是RAM programs），然后通过某种形式的polynomial commitment（通常使用Merkle trees 或pairing groups）来进行cryptographically compile。

GGPR中的linear PCPs和其它基于QAP以及R1CS的SNARK均可转换为Polynomial IOPs。（在 Ben-Sasson等人2019年论文《Aurora: Transparent succinct arguments for R1CS》中也指出了这一点。） 这种转换有助于强调 non-transparent non-universal SNARKs（基于linear PCP或linear-only encodings）和 基于polynomial commitment SNARK 之间的fundamental paradigm shift。 【LM19/LRY16】

• Russell W. F. Lai 和 Giulio Malavolta 在Crypto 2019上发表的论文《Subvector Commitments with Application to Succinct Arguments》：（可参见博客 Subvector Commitments with Application to Succinct Arguments学习笔记） 在 Benoˆıt Libert, Somindu C. Ramanna 和 Moti Yung 2016年论文 《Functional Commitment Schemes: From Polynomial Commitments to Pairing-Based Accumulators from Simple Assumptions》（参见博客 Functional Commitment Schemes: From Polynomial Commitments to Pairing-Based Accumulators学习笔记） 的functional commitment的基础上进行了扩展，提供了 n n n-dimensional linear-map commitment based on bilinear pairings。但是verify claimed evaluations of the committed function on query points需要的复杂度为 O ( n ) O(n) O(n)。

本文提供了2种类型的Polynomial IOP:

• 单变量Polynomial IOP：可提取polynomial 中的特定系数。
• 多变量Polynomial IOP：用于证明两个多项式的系数向量的inner product为特定值。增加一个offline pre-processing phase用于确定多变量多项式的正确性，从而可用多变量Polynomial IOP实现任意的algebraic linear IOP。

1.3 Supersonic——SNARK without trusted setup

Supersonic可表示任意的arithmetic circuit计算。可使用DARK polynomial commitment scheme 对如下论文的Polynomial IOPs进行cryptographically compile：

• Sonic (Maller等人2019年论文《Sonic: Zero-knowledge snarks from linear-size universal and updatable structured reference strings》)
• PLONK (Gabizon等人2019年论文《Plonk: Permutations over lagrangebases for oecumenical noninteractive arguments of knowledge》)
• Marlin ( Chiesa等人2019年论文《Marlin: Preprocessing zksnarks with universal and updatable srs》)

Supersonic VS STARK:

• Supersonic的verification time与STARK相当，但proof size降低了一个数量级。以100万gates为例，Supersonic的proof size为7.8KB，verify time为75ms左右。以 λ \lambda λ表示security parameter，STARK的proof size和verification complexity为 O λ ( log ⁡ 2 T ) O_{\lambda}(\log^2T) Oλ​(log2T)，而Supersonic的proof size和verification complexity为 O λ ( log ⁡ T ) O_{\lambda}(\log T) Oλ​(logT)。
• 两者的prover time基本相当，都为quasi-linear in T T T。当时Supersonic使用的是heavy-weight “crypto operations” over 1200bit class group elements，而STARK使用的是light-weight FFTs和hash functions。
• Supersonic不是量子安全的，因为其依赖unknown order group，而STARK是量子安全的SNARK。

1.4 相关工作 1.4.1 基于hidden order group的argument相关工作

• Fujisaki and Okamoto 1997年《Statistical zero knowledge protocols to prove modular polynomial relations》基于RSA group构建了homomorphic integer commitment scheme。同时可证明a list of committed integers满足modular polynomial equations，可open a commtiment bit by bit。

• Damg˚ard and Fujisaki 2002年论文《 A statistically-hiding integer commitment scheme based on groups with hidden order》在Fujisaki and Okamoto 1997年的论文提供了soundness proof，同时首次提出了可使用imaginary quadratic order class group 来作为备选。

• Lipmaa 2003年论文《 On diophantine complexity and statistical zero-knowledge arguments》中指出了基于integer commitment scheme构建的zero-knowledge proof 与 Diophantine complexity之间的关系，创造了“Diophantine Arguments of Knowledge” 这个术语。

• Couteau 等人2017年论文《Removing the strong RSA assumption from arguments over the integers》对基于RSA group的integer commitment scheme进行了研究，实现了security assumption的reduce；同时提供了 polynomial evaluation modulo a prime π \pi π proof；以及通过发现 1 + 4 ( X − a ) ( b − X ) 1+4(X-a)(b-X) 1+4(X−a)(b−X)为the sum of 3 squares 来 证明 an integer X X X lies in the range [ a , b ] [a,b] [a,b]。

• Pietrzak 2019年论文《 Simple verifiable delay functions》中提供了repeated squaring的证明算法，如证明 x 2 T = y x^{2^T}=y x2T=y，其proof size为 O ( log ⁡ T ) O(\log T) O(logT)，verification time为 O ( log ⁡ T ) O(\log T) O(logT)，从而可构建简单的verifiable delay function （Boneh等人2018年论文《Verifiable delay functions》） based on the RSW time-lock puzzle（Rivest等人1996年论文《Time-lock puzzles and timed-release crypto》）。

• Wesolowski 2019年论文《Efficient verifiable delay functions》在Pietrzak 2019年论文的基础上进行了改进，实现了a single-round protocol来证明repeated squaring in unknown order group，且proof size为constant的。

• Boneh等人2019年论文《Batching techniques for accumulators with applications to IOPs and stateless blockchains》发现Wesolowski 的protocol 可generalize to arbitray exponents (PoE)，提出了proof of knowledge of an integer exponent (PoKE)和zero-knowledge variant。同时利用了PoE和PoKE构建了efficient accumulators和vector commitment schemes。

1.4.2 transparent polynomial commitment相关工作

• Whaby等人2018年论文《Doubly-efficient zkSNARKs without trusted setup》中构建了a transparent polynomial commitment scheme for multilinear polynomials by combining a matrix commitment of Bootle[BCC+ 16b] 和 inner-product argument of Bunz [BBB+ 18]。（参见博客 Hyrax: Doubly-efficient zkSNARKs without trusted setup学习笔记 第4.2节，将其中的public info 理解为 a ⃗ = ( 1 , x , ⋯   , x d ) \vec{a}=(1,x,\cdots,x^{d}) a =(1,x,⋯,xd)，其中的private info 理解为是多项式系数 x ⃗ = ( a 0 , a 1 , ⋯   , a d ) \vec{x}=(a_0,a_1,\cdots,a_{d}) x =(a0​,a1​,⋯,ad​)，则 y = < a ⃗ , x ⃗ > y= y=表示的就是对多项式 P ( X ) = a 0 + a 1 X + ⋯ + a d X d P(X)=a_0+a_1X+\cdots + a_{d}X^{d} P(X)=a0​+a1​X+⋯+ad​Xd在 x x x处的evaluation值，这样inner(dot) product proof 相应的其实即为polynomial commitment scheme。不过Hyrax中evaluation值 y y y为private info，未直接open给Verifier。） Hyrax中的transparent polynomial commitment，对于 d d d阶多项式，其commitment size为 O ( d ) O(\sqrt{d}) O(d ​)，相应的evaluation argument 的communication complexity 为 O ( d ) O(\sqrt{d}) O(d ​)。

• Zhang等人2019年论文《Transparent polynomial delegation and its applications to zero knowledge proof》和Kattis等人2019年论文《RedShift: Transparent SNARKs from list polynomial commitment IOPs》同时独立地基于FRI (Fast Reed Solomon IOPP) 构建了transparent polynomial commitment，具有的commitment size为 O ( λ ) O(\lambda) O(λ)，evaluation argument的communication complexity为 O ( log ⁡ 2 d ) O(\log^2 d) O(log2d)。（关于FRI (Fast Reed Solomon IOPP)知识，可参见Ben-Sasson等人2018年论文《Fast reed-solomon interactive oracle proofs of proximity》Ben-Sasson等人2019年论文《DEEP-FRI: sampling outside the box improves soundness》）

1.4.3 Polynomial IOP 相关工作

• 同期研究成果，Chiesa等人在2019年论文《Marlin: Preprocessing zksnarks with universal and updatable srs》中引入了一个叫algebraic holographic proofs (AHP) 的information theoretic 框架。同时指出，借助a polynomial commitment scheme，an AHP可被编译为a preprocessing SNARK。 该AHP框架和本文的Polynomial IOP框架是等价的。

• 同时，Chiesa等人在2019年论文《Fractal: Post-quantum and transparent recursive proofs from holography》中指出了algebraic holographic proofs和recursive proof composition之间的有趣关联，构建了一个称为Fractal的AHP-based transparent SNARK。

1.5 unknown order group选择

主要有2类unknown order group可供选择：

• RSA group：multiplicative group Z n ∗ \mathbb{Z}_n^* Zn∗​，modulo为 n = p ⋅ q n=p\cdot q n=p⋅q，其中 p , q p,q p,q为大素数，计算该group的order和对 n n n进行因式分解的难度相当。不过Adaptive Root Assumption 在 Z n ∗ \mathbb{Z}_n^* Zn∗​ group 中不成立，因为 − 1 ∈ Z n ∗ -1\in\mathbb{Z}_n^* −1∈Zn∗​，其order为2。可以降为使用 quotient group Z n ∗ / < − 1 > ≅ Q R n \mathbb{Z}_n^*/\cong QR_n Zn∗​/≅QRn​，使得Adaptive Root Assumption成立。 使用RSA group的缺点是，或者准确说使用group of quadratic residues modulo an RSA modulus的缺点是：该modulus无法在不暴露order的情况下以publicly verifiable的方式生成，所以需要trusted setup。

• Class group：class group of an imaginary quadratic order可认为是 the quaotient group of fractional ideals by principal ideals of an order of a number field Q ( Δ ) \mathbb{Q}(\sqrt{\Delta}) Q(Δ ​)， with ideal multiplication。 class group C l ( Δ ) Cl(\Delta) Cl(Δ) 完全由其discriminant Δ \Delta Δ决定， Δ \Delta Δ需满足： Δ ≡ 1   m o d   4 \Delta\equiv 1\ mod\ 4 Δ≡1 mod 4和 − Δ -\Delta −Δ must be prime。 由此可知， Δ \Delta Δ可generated from public coins，从而无需trusted setup。 详细学习可参看： – Buchmann and Hamdy的2001年调查：《A survey on iq cryptography》 – Straka的2019年blog：Class Groups for Cryptographic Accumulators

在class group C l ( Δ ) Cl(\Delta) Cl(Δ)中的一个难点是： 当前已存在Gauss算法可计算square roots of arbitrary elements (参看1996年论文《》)，重复调用的话，也可计算任意的 2 k 2^k 2k root。这样的group无法用于commit to integers，只能用于dyadic rationals，这些rational numbers的分母为 2 k 2^k 2k。同时，如果计算square root is easy，则标准的Strong RSA group也不成立。因此，我们需要用更弱的Strong RSA assumption，称为 2 2 2-Strong-RSA assumption：假设计算非square roots is hard。尽管computing square roots is easy，但其仍然成立。

1.6 相关定义

• Interactive Argument：
• Witness-extended emulation：
• Generalized Forking Lemma：
• HVZK for interactive arguments：
• Commitment scheme：
• Polynomial commitment：

2. 技术要点 2.1 integer encoding of polynomials

对单变量多项式 f ( X ) ∈ Z p [ X ] f(X)\in\mathbb{Z}_p[X] f(X)∈Zp​[X]，prover首先将该多项式encode as an integer。将系数以 [ 0 , p ) [0,p) [0,p)表示（后续实际选择的是平衡表示 [ − p − 1 2 , p − 1 2 ] [-\frac{p-1}{2},\frac{p-1}{2}] [−2p−1​,2p−1​]），define f ^ ( X ) \hat{f}(X) f^​(X) to be the integer polynomial with these coefficients。 prover计算 f ^ ( q ) ∈ Z \hat{f}(q)\in\mathbb{Z} f^​(q)∈Z for some large integer q ≥ p q\geq p q≥p。该过程可看成是 an injective map from polynomial with bounded coefficients to integers，同时该过程可逆： f ( q ) f(q) f(q)的系数可从 base- q q q expansion of f ^ ( q ) \hat{f}(q) f^​(q) 中恢复出来。 如： 已知 f ( X ) = 2 X 3 + 3 X 2 + 4 X + 1 ∈ Z 5 [ X ] f(X)=2X^3+3X^2+4X+1\in\mathbb{Z}_{5}[X] f(X)=2X3+3X2+4X+1∈Z5​[X]， q = 10 q=10 q=10，则有 integer f ^ ( 10 ) = 2341 \hat{f}(10)=2341 f^​(10)=2341，该integer encodes the polynomial f ( X ) f(X) f(X) because its coefficients appear in the decimal expansion of f ^ ( 10 ) \hat{f}(10) f^​(10)。 这种encoding具有加法同态属性。假设 q q q足够大，如 g ( X ) = 4 X 3 + 1 X 2 + 3 g(X)=4X^3+1X^2+3 g(X)=4X3+1X2+3，有 g ^ ( 10 ) = 4103 \hat{g}(10)=4103 g^​(10)=4103，则有 f ^ ( 10 ) + g ^ ( 10 ) = 6444 = ( g ^ + f ^ ) ( 10 ) \hat{f}(10)+\hat{g}(10)=6444=(\hat{g}+\hat{f})(10) f^​(10)+g^​(10)=6444=(g^​+f^​)(10)。 以及有 f ^ ( q ) ⋅ q k \hat{f}(q)\cdot q^k f^​(q)⋅qk is equal to the encoding of f ( X ) ⋅ X k f(X)\cdot X^k f(X)⋅Xk。

The integer x ← f ^ ( q ) x\leftarrow \hat{f}(q) x←f^​(q) encoding a degree d d d polynomial f ( X ) f(X) f(X) lies between q d q^d qd and q d + 1 q^{d+1} qd+1，换句话说，integer x x x的size为 ( d + 1 ) log ⁡ 2 q (d+1)\log_2q (d+1)log2​q bits。 Prover可采用具有加法同态性的succinct integer commitment scheme对 x x x进行commit。可供选项之一是：使用unknown order group G \mathbb{G} G 的exponentiation运算： commitment表示为 g x g^x gx，其中 g ∈ G g\in\mathbb{G} g∈G为base element。 注意此处的group G \mathbb{G} G 必须为unknown order，若已知其order为 n n n，则 g x g^x gx可open为满足 x ’ ≡ x   m o d   n x’\equiv x\ mod\ n x’≡x mod n的任意数。

Evaluation protocol基本信息为：

• public info: commitment C C C, evaluated point z z z。
• private info：多项式 f ( X ) f(X) f(X)的系数，以及evaluation值 y y y。
• relation： f ( z ) = y f(z)=y f(z)=y 且 C = C o m ( y ) = g y C=Com(y)=g^y C=Com(y)=gy。

假设 d = 2 k − 1 d=2^k-1 d=2k−1阶多项式 f ( X ) f(X) f(X)。 （1）为证明 C = g f ^ ( q ) C=g^{\hat{f}(q)} C=gf^​(q)可采用divide-and-combine 递归策略来表示： 将 f ( X ) f(X) f(X)拆分为两个degree为 d ’ = ⌊ d 2 ⌋ d’=\left \lfloor \frac{d}{2} \right \rfloor d’=⌊2d​⌋ 的多项式 f L ( X ) f_L(X) fL​(X)和 f R ( X ) f_R(X) fR​(X)，其中 f L ( X ) f_{L}(X) fL​(X)包含 f ( X ) f(X) f(X)的前 d ’ + 1 d’+1 d’+1个系数， f R ( X ) f_R(X) fR​(X)包含后剩下的系数，满足 f ( X ) = f L ( X ) + X d ’ + 1 f R ( X ) f(X)=f_L(X)+X^{d’+1}f_R(X) f(X)=fL​(X)+Xd’+1fR​(X)。

• 1）Prover：分别对 f L f_L fL​和 f R f_R fR​进行commit： C L ← g f ^ L ( q ) , C R ← g f ^ R ( q ) C_L\leftarrow g^{\hat{f}_L(q)}, C_R\leftarrow g^{\hat{f}_R(q)} CL​←gf^​L​(q),CR​←gf^​R​(q)。
• 2）Verifier：验证 C L C R q d ’ + 1 = C C_LC_R^{q^{d’+1}}=C CL​CRqd’+1​=C 是否成立即可。
• 3）Verifier：提供challenge α ∈ Z p \alpha\in\mathbb{Z}_p α∈Zp​。
• 4）Prover和Verifier：都计算 C ’ = C L α C R C’=C_L^{\alpha}C_R C’=CLα​CR​，对应为 α f ^ L ( q ) + f ^ R ( q ) \alpha\hat{f}_L(q)+\hat{f}_R(q) αf^​L​(q)+f^​R​(q)的commitment。然后递归调用步骤1）证明 C ’ C’ C’为a commitment to a polynomial of degree at most d ’ d’ d’ （ f ’ ( X ) = α f ^ L ( X ) + f ^ R ( X ) f’(X)=\alpha\hat{f}_L(X)+\hat{f}_R(X) f’(X)=αf^​L​(X)+f^​R​(X)），从而实现half the size of the statement。
• 5）经过 log ⁡ 2 ( d + 1 ) \log_2(d+1) log2​(d+1)轮后，commitment C ’ C’ C’ 为a commitment to a polynomial of degree 0 0 0，即 to a scalar c ∈ Z p c\in\mathbb{Z}_p c∈Zp​。即 C ’ = g c ^ C’=g^{\hat{c}} C’=gc^，其中 c ^ \hat{c} c^ is some integer congruent to c c c modulo p。 Prover：发送 c ^ \hat{c} c^给Verifier。
• 6）Verifier：验证 g c ^ = C ’ g^{\hat{c}}=C’ gc^=C’且 c ^ < q \hat{c}