1. 引言

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

代码实现可参见：

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

视频解说：

  • https://www.youtube/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/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=<\vec{a},\vec{x}> y=<a ,x >表示的就是对多项式 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^*/<-1>\cong QR_n Zn∗​/<−1>≅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}<q c^<q 即可。

（2）为证明 f ( z ) = y f(z)=y f(z)=y，方法类似，要求在每一轮，Prover都额外再发送 y L = f L ( z )   m o d   p y_L=f_L(z)\ mod\ p yL​=fL​(z) mod p和 y R = f R ( z )   m o d   p y_R=f_R(z)\ mod\ p yR​=fR​(z) mod p，然后Verifier验证 y L + z d ’ + 1 y R = y y_L+z^{d’+1}y_R=y yL​+zd’+1yR​=y成立，同时对challenge，计算 y ’ ← α y L + y R   m o d   p y’\leftarrow \alpha y_L+y_R\ mod\ p y’←αyL​+yR​ mod p，在下一轮递归调用时满足 f ’ ( z ) = y ’ f’(z)=y’ f’(z)=y’。
最终，Verifier在验证 g c ^ = C ’ g^{\hat{c}}=C’ gc^=C’且 c ^ < q \hat{c}<q c^<q的同时，还需要验证 c ^ ≡ y   m o d   p \hat{c}\equiv y\ mod\ p c^≡y mod p。

上述（1）和（2）构成的evaluation protocol，在每一轮均需要传递2个group elements和2个field elements，每一轮Verifier均需验证 C L C R q d ’ + 1 = C C_LC_R^{q^{d’+1}}=C CL​CRqd’+1​=C，若直接计算该验证公式中的exponentiation，则需要的work为 Ω ( d ⋅ log ⁡ q ) \Omega(d\cdot \log q) Ω(d⋅logq)。为了减轻Verifier的计算压力，可将该计算压力转移给Prover，本文引入了Wesolowski 2019年论文《Efficient verifiable delay functions》中的proof of exponentiation (PoE) in groups of unknown order 算法，由Prover来计算该exponentiation，Verifier的验证时间为constant time。通过这种方式，可将evaluation protocol中Verifier 的验证时间降低为 O ( log ⁡ d ) O(\log d) O(logd)。

2.2 proof of exponentiation in groups of unknown order

Wesolowski 2019年论文《Efficient verifiable delay functions》中的proof of exponentiation (PoE) in groups of unknown order 算法：（主要用于将Verifier的计算压力转移给Prover，此时不存在private信息）

  • Public info： u , w ∈ G u,w\in\mathbb{G} u,w∈G 和 x ∈ Z x\in\mathbb{Z} x∈Z
  • private info：
  • Relation： w = u x w=u^x w=ux

详细的证明过程为：

详细也可参见博客 Proof (of knowledge) of exponentiation

3. 相关安全假设

  • Bari等人1997年论文《Collision-free accumulators and fail-stop signature schemes without trees》中提出的Strong RSA Assumption 是指：it is hard to take arbitrary roots of random elements
  • Wesolowski 2019年论文《Efficient verifiable delay functions》中提出的Adaptive Root Assumption，是双重Strong RSA Assumption，是指：it is hard to take random roots of arbitrary group elements。
    Strong RSA Assumption和Adaptive Root Assumption 在generic groups of unknown order中均成立。（参见 Damgard等人2002年论文《Generic lower bounds for root extraction and signature
    schemes in general groups》和 Boneh等人2019年论文《Batching techniques for accumulators with applications to IOPs and stateless blockchains》）

4. unknown order group下的polynomial commitment

定义homomorphic commitment 函数：（后续会用groups of unknown order和an encoding of polynomials as integers来将该函数实例化。）
[ ∗ ] : Z p [ X ] → S [*]:\mathbb{Z}_p[X]\rightarrow \mathbb{S} [∗]:Zp​[X]→S。
S \mathbb{S} S域内支持加法和乘法运算：

  • ∗ + ∗ : S × S → S *+*:\mathbb{S}\times\mathbb{S}\rightarrow \mathbb{S} ∗+∗:S×S→S；
  • ∗ ⋅ ∗ : Z p [ X ] × S → S *\cdot *: \mathbb{Z}_p[X]\times\mathbb{S}\rightarrow \mathbb{S} ∗⋅∗:Zp​[X]×S→S。

该commitment具有如下同态属性：

  • 线性同态： a ⋅ [ f ( X ) ] + b ⋅ [ g ( X ) ] = [ a f ( X ) + b g ( X ) ] a\cdot [f(X)]+b\cdot [g(X)]=[af(X)+bg(X)] a⋅[f(X)]+b⋅[g(X)]=[af(X)+bg(X)]
  • 单项式同态： X d ⋅ [ f ( X ) ] = [ X d f ( X ) ] X^d\cdot [f(X)]=[X^df(X)] Xd⋅[f(X)]=[Xdf(X)]

同时假设Prover和Verifier对commitment函数 [ ∗ ] [*] [∗]及其加法和乘法运算均具有oracle access。

evaluation protocol的核心思想是：
将：
需证明 degree 为 d d d 的多项式 f ( X ) f(X) f(X)，其在 z z z point 的evaluation值为 y y y， y = f ( z ) y=f(z) y=f(z)。
reduce 为：
需证明 degree 为 d ’ = ⌊ d 2 ⌋ d’=\left \lfloor \frac{d}{2}\right \rfloor d’=⌊2d​⌋ 的多项式 f ’ ( X ) f’(X) f’(X)，其在 z z z point 的evaluation值为 y ‘ y‘ y‘， y ’ = f ‘ ( z ) y’=f‘(z) y’=f‘(z)。

基本信息为：

  • public info：polynomial commitment [ f ( X ) ] [f(X)] [f(X)]，evaluation point z z z，commitment C C C。
  • private info：多项式 f ( X ) f(X) f(X)的系数（在有限域内），以及evaluation值 y y y。
  • relation： y = f ( z ) y=f(z) y=f(z)且 C = C o m ( y ) C=Com(y) C=Com(y)

为简单起见，假设 d + 1 d+1 d+1为2的幂乘，即 d = 2 k − 1 d=2^k-1 d=2k−1。采用二分法：

  • 1）Prover：将 f ( X ) f(X) f(X)拆分为degree 最高为 d ’ d’ d’ 的多项式 f L ( X ) f_L(X) fL​(X)和 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)。构建polynomial commitment [ f ( X ) ] = C o m ( f ( X ) ) , [ f L ( X ) ] = C o m ( f L ( X ) ) , [ f R ( X ) ] = C o m ( f R ( X ) ) [f(X)]=Com(f(X)), [f_L(X)]=Com(f_L(X)), [f_R(X)]=Com(f_R(X)) [f(X)]=Com(f(X)),[fL​(X)]=Com(fL​(X)),[fR​(X)]=Com(fR​(X))，将 [ f L ( X ) ] , [ f R ( X ) ] . [ f ( X ) ] [f_L(X)],[f_R(X)].[f(X)] [fL​(X)],[fR​(X)].[f(X)] 发送给Verifier。
  • 2）Verifier：验证 [ 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’+1[fR​(X)]成立，给Prover发送challenge α ∈ Z p \alpha\in\mathbb{Z}_p α∈Zp​。【不够，还需增加 [ f L ( X ) ] [f_L(X)] [fL​(X)]和 [ f R ( X ) ] [f_R(X)] [fR​(X)]的有效性验证】
  • 3）Prover：构建多项式 f ’ ( X ) = α ⋅ f L ( X ) + f R ( X ) f’(X)=\alpha\cdot f_L(X)+f_R(X) f’(X)=α⋅fL​(X)+fR​(X)，其degree 为 d ’ d’ d’。
    转为证明 f ’ ( z ) = y ’ = α y L + y R f’(z)=y’=\alpha y_L+y_R f’(z)=y’=αyL​+yR​，其中 y L = f L ( z ) , y R = f R ( z ) y_L=f_L(z),y_R=f_R(z) yL​=fL​(z),yR​=fR​(z)。构建polynomial commitment [ f ‘ ( X ) ] = C o m ( f ( X ) ) [f‘(X)]=Com(f(X)) [f‘(X)]=Com(f(X))，将 [ f ’ ( X ) ] [f’(X)] [f’(X)]发送给Verifier。
  • 4）Verifier：验证 [ f ’ ( X ) ] = α ⋅ [ f L ( X ) ] + [ f R ( X ) ] [f’(X)]=\alpha\cdot [f_L(X)]+[f_R(X)] [f’(X)]=α⋅[fL​(X)]+[fR​(X)]成立。
  • 5） f ( X ) = f ’ ( X ) , y = y ’ f(X)=f’(X),y=y’ f(X)=f’(X),y=y’递归调用1），直到degree为 0 0 0，对应的 f ( X ) = f f(X)=f f(X)=f为常量多项式，Prover将commitment [ f ] = C o m ( f ) [f]=Com(f) [f]=Com(f)和最终的evaluation值 y y y发送给Verifier，Verifier仅需验证 [ f ] = C o m ( y ) [f]=Com(y) [f]=Com(y)成立即可。

4.1 homomorphic commitment函数的实例化

本文采用integer commitment in a group of unknown order来对上述homomorphic commitment 函数进行实例化。

注意：在上述Verifier仅仅验证 [ 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’+1[fR​(X)]是不够的，还需要额外增加对 [ 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 R ( X ) ] [f_R(X)] [fR​(X)]的有效性，约定了多项式 f ( X ) f(X) f(X)的系数的取值范围为 ( − p / 2 , p / 2 ) (-p/2,p/2) (−p/2,p/2)，同时challenge α \alpha α 的取值范围为 ( − p / 2 , p / 2 ) (-p/2,p/2) (−p/2,p/2)，从而保证递归调用过程中的 a tighter bound on coefficient growth。

一些定义：

  • Z ( b ) = { x ∈ Z : ∣ x ∣ ≤ b } \mathbb{Z}(b)=\{x\in\mathbb{Z}:|x|\leq b\} Z(b)={x∈Z:∣x∣≤b}，表示绝对值不大于 b b b的一系列数值。
  • Z ( b ) [ X ] = { f ∈ Z [ X ] : ∥ f ∥ ∞ ≤ b } \mathbb{Z}(b)[X]=\{f\in\mathbb{Z}[X]: \left \| f \right \| _{\infty}\leq b\} Z(b)[X]={f∈Z[X]:∥f∥∞​≤b}，表示该多项式的系数均来自于 Z ( b ) \mathbb{Z}(b) Z(b)，其中 ∥ f ∥ ∞ \left \| f \right \| _{\infty} ∥f∥∞​ 表示polynomial norm，其值为多项式 f f f中系数绝对值最大值。（ P = ∑ k = 0 n a k z k P=\sum_{k=0}^{n}a_kz^k P=∑k=0n​ak​zk，对应地 ∥ P ∥ ∞ = m a x k ∣ a k ∣ \left \| P \right \| _{\infty}=max_{k}|a_k| ∥P∥∞​=maxk​∣ak​∣）

详细的homomorphic commitment函数的实例化思路为：

  • Encoding流程为：
    对于任意的integer q q q，函数 E n c : Z ( b ) [ X ] → Z Enc:\mathbb{Z}(b)[X]\rightarrow \mathbb{Z} Enc:Z(b)[X]→Z maps h ( X ) ↦ h ( q ) h(X)\mapsto h(q) h(X)↦h(q)。
    首先将多项式 f ( X ) ∈ Z p [ X ] f(X)\in\mathbb{Z}_p[X] f(X)∈Zp​[X] map 到 Z ( p / 2 ) [ X ] \mathbb{Z}(p/2)[X] Z(p/2)[X]，方法是：将 f f f中的每个系数都替换为 ( − p / 2 , p / 2 ) (-p/2,p/2) (−p/2,p/2)区间内的值。（通过modulo p p p 来等价实现。）

  • Decoding流程为：
    定义partial sum S k = ∑ i = 0 k f i q i S_k=\sum_{i=0}^{k}f_iq^i Sk​=∑i=0k​fi​qi，其中 S − 1 = 0 S_{-1}=0 S−1​=0。假设对所有的 i i i， ∣ f i ∣ < q / 2 |f_i|<q/2 ∣fi​∣<q/2都成立，则对任意的partial sum S k S_k Sk​，都满足 ∣ S k ∣ < q k + 1 2 |S_k|<\frac{q^{k+1}}{2} ∣Sk​∣<2qk+1​。
    当 S k < 0 S_k<0 Sk​<0时，有 S k   m o d   q k + 1 > q k + 1 / 2 S_k\ mod\ q^{k+1} > q^{k+1}/2 Sk​ mod qk+1>qk+1/2；
    当 S k ≥ 0 S_k\geq 0 Sk​≥0时，有 S k   m o d   q k + 1 < q k + 1 / 2 S_k\ mod\ q^{k+1} < q^{k+1}/2 Sk​ mod qk+1<qk+1/2。
    从而有从 y ∈ Z y\in\mathbb{Z} y∈Z中恢复 S k S_k Sk​的decode策略为：
    若 y   m o d   q k + 1 < q k + 1 / 2 y\ mod\ q^{k+1}<q^{k+1}/2 y mod qk+1<qk+1/2，则设置 S k = y   m o d   q k + 1 S_k= y\ mod\ q^{k+1} Sk​=y mod qk+1；
    若 y   m o d   q k + 1 ≥ q k + 1 / 2 y\ mod\ q^{k+1}\geq q^{k+1}/2 y mod qk+1≥qk+1/2，则设置 S k = q k + 1 − ( y   m o d   q k + 1 ) S_k= q^{k+1}-( y\ mod\ q^{k+1}) Sk​=qk+1−(y mod qk+1)。
    由相邻的partial sum值可计算 f ( X ) f(X) f(X)的系数： f k = S k − S k − 1 q k ∈ Z ( b ) f_k=\frac{S_k-S_{k-1}}{q^k}\in\mathbb{Z}(b) fk​=qkSk​−Sk−1​​∈Z(b)。
    详细的decoding 算法为：（即满足Encoding和Decoding之间的一一映射。）

    当扩展至dyadic rational polynomial时，其Encoding流程基本相同，而在Decoding流程中需对分子和分母分别做限定，如设置 N ∈ N N\in\mathbb{N} N∈N为分子绝对值的上限， 2 D ∈ N 2^{D}\in\mathbb{N} 2D∈N为分母绝对值的上限。

4.2 详细的polynomial commitment scheme

group of unknown order G \mathbb{G} G， g g g 为该group的随机元素。

基本思路为：

  • Lift the field polynomial f ( X ) ∈ Z p [ X ] f(X)\in\mathbb{Z}_p[X] f(X)∈Zp​[X] to an integer polynomial with bounded coefficients，如 f ^ ( X ) ∈ Z ( p − 1 2 ) [ X ] \hat{f}(X)\in\mathbb{Z}(\frac{p-1}{2})[X] f^​(X)∈Z(2p−1​)[X]，使得 f ^ ( X )   m o d   p = f ( x ) \hat{f}(X)\ mod\ p=f(x) f^​(X) mod p=f(x)。
  • encode f ^ ( X ) \hat{f}(X) f^​(X) as an integer by evaluating it at a “large enough” integer q q q。
  • use exponentiation in G \mathbb{G} G to commit to the integer (该integer即为 f ^ ( q ) \hat{f}(q) f^​(q))。可表示为 [ f ( X ) ] = C o m ( f ^ ( q ) ) = g f ^ ( q ) [f(X)]=Com(\hat{f}(q))=g^{\hat{f}(q)} [f(X)]=Com(f^​(q))=gf^​(q)。该commitment函数具有 homomorphic properties of the integer encoding for a limited number of additions and multiplications-by-constant。
    而单项式同态性 for X d X^d Xd is achieved by raising the group element to the power q d q^d qd。
    To maintain consistency between the prover’s witness polynomials and the verifier’s commitments, the prover operates on polynomials with integer coefficients f ^ ( X ) , g ^ ( X ) \hat{f}(X),\hat{g}(X) f^​(X),g^​(X), etc., without ever reducing them modulo p p p。

Polynomial commitment scheme中的Setup、Commit、Open 算法为：

  • S e t u p ( 1 λ ) Setup(1^{\lambda}) Setup(1λ)：随机 G ← G G e n ( λ ) \mathbb{G}\leftarrow GGen(\lambda) G←GGen(λ)和 g ← G g\leftarrow \mathbb{G} g←G。返回 p p = ( λ , G , g , q ) pp=(\lambda,\mathbb{G},g,q) pp=(λ,G,g,q)。
  • C o m m i t ( p p ; f ( X ) ∈ Z p [ X ] ) Commit(pp;f(X)\in\mathbb{Z}_p[X]) Commit(pp;f(X)∈Zp​[X])：计算 C ← g f ^ ( q ) C\leftarrow g^{\hat{f}(q)} C←gf^​(q)，返回 ( C ; f ^ ( X ) ) (C;\hat{f}(X)) (C;f^​(X))。
  • O p e n ( p p , C , f ( X ) , f ^ ( X ) ) Open(pp,C,f(X),\hat{f}(X)) Open(pp,C,f(X),f^​(X))：验证 f ^ ( X ) ∈ Z ( q / 2 ) [ X ] \hat{f}(X)\in\mathbb{Z}(q/2)[X] f^​(X)∈Z(q/2)[X] and g f ^ ( q ) = C g^{\hat{f}(q)}=C gf^​(q)=C and f ( X ) = f ^ ( X )   m o d   p f(X)=\hat{f}(X)\ mod\ p f(X)=f^​(X) mod p。

Evaluation protocol Eval 具有logarithmic communication。
在每一轮，为了验证 [ f L ( X ) ] , [ f R ( X ) ] , [ f ( X ) ] [f_L(X)],[f_R(X)],[f(X)] [fL​(X)],[fR​(X)],[f(X)]之间的consistency，Verifier会验证 C L ⋅ C R q d ’ + 1 = C C_L\cdot C_R^{q^{d’+1}}=C CL​⋅CRqd’+1​=C。直接做该公式验证的效率很低，因为幂指数 q d ’ + 1 q^{d’+1} qd’+1具有 O ( d ) O(d) O(d) bits。为了减轻Verifier的验证压力，引入了proof of exponentiation (PoE)，将相应的计算压力外包给Prover。（参见本博文2.2节内容。 PoE protocol为an argument that a large exponentiation in a group of unknown order was performed correctly。Wesolowski 2019年论文《Efficient verifiable delay functions》 的PoE argument为public coin, 具有constant communication and verification time。）

接下来，补充2处之前忽略的场景：

  • 当 d + 1 ≠ 2 k d+1\neq 2^k d+1​=2k时，可以将polynomial进行shift by one degree，如 f ’ ( X ) = X f ( X ) f’(X)=Xf(X) f’(X)=Xf(X)，转为证明degree为 d ’ = d + 1 d’=d+1 d’=d+1的多项式 f ’ ( X ) f’(X) f’(X)，其在 z z z处的evaluation值为 y ’ = z y y’=zy y’=zy。Verifier获得的commitment为 C ’ ← C q C’\leftarrow C^q C’←Cq。
  • 在每一次递归调用中， f ( X ) f(X) f(X)的系数都以 p + 1 2 \frac{p+1}{2} 2p+1​的倍数进行增长，但是最终在最后一轮传输的constant f f f has to be tested against some bound because if it is too large it should be rejected。但是，函数接口中并未明确指出系数的allowable size。
    因此引入了具有参数 b b b 的子程序 EvalBounded，除了用于证明 what Eval proves，同时证明 all coefficients f i f_i fi​ of f ( X ) f(X) f(X) 满足 ∣ f i ∣ ≤ b |f_i|\leq b ∣fi​∣≤b。Importantly， b b b会在每一次递归调用以 p + 1 2 \frac{p+1}{2} 2p+1​的倍数递增。引入该子程序 is also useful if commitments were homomorphically combined prior to the execution of EvalBounded。
    系数值的增长决定了 q q q的下限值： q q q值应远大于 b b b值。
  • 在最后一轮，需要验证常量 f f f是否满足 ∣ f ∣ ≤ b |f|\leq b ∣f∣≤b，以及 b = p − 1 2 ( p + 1 2 ) ⌈ log ⁡ 2 ( d + 1 ) ⌉ b=\frac{p-1}{2}(\frac{p+1}{2})^{\left \lceil \log_2{(d+1)} \right \rceil} b=2p−1​(2p+1​)⌈log2​(d+1)⌉。 q q q needs to be even larger than this value in order for extraction to work。
    – 在RSA group中，假设computing square root is hard，要求 q > p 2 log ⁡ 2 ( d + 1 ) + 1 q>p^{2\log_2{(d+1)}+1} q>p2log2​(d+1)+1；
    – 在class group中，计算square root是简单的，要求 q > p 3 log ⁡ 2 ( d + 1 ) + 1 q>p^{3\log_2{(d+1)}+1} q>p3log2​(d+1)+1，

    详细的Evaluation protocol Eval算法实现为：

    具有的属性为：

4.3 Evaluation protocol的一些优化

evaluation protocol中可通过以下措施进行优化：

  • precomputation：Prover需要计算powers of g g g as large as q d q^d qd，可在预处理阶段计算所有的 g q i , i ∈ { 1 , ⋯   , d m a x } g^{q^i},i\in\{1,\cdots,d_{max}\} gqi,i∈{1,⋯,dmax​}。
    PoE proof中的计算可借助Boneh等人2019年论文《Batching techniques for accumulators with applications to IOPs and stateless blockchains》的算法实现并行化。（The prover can express each Q Q Q as a power of g g g which enables pre-computation of powers of g g g and parallelism。）
    PoE幂指数最大为 q d + 1 2 q^{\frac{d+1}{2}} q2d+1​具有 O ( λ d log ⁡ ( d ) ) O(\lambda d\log(d)) O(λdlog(d))，再借助Pippenger multi-exponentiation算法，可将prover的工作量由 O ( λ d log ⁡ ( d ) ) O(\lambda d\log(d)) O(λdlog(d)) reduce 为 O ( λ d ) O(\lambda d) O(λd)。

  • 去除冗余：在每一轮，Verifier有commitment C C C，同时收到 C L , C R C_L,C_R CL​,CR​，满足 C L C R q d ’ + 1 = C C_LC_R^{q^{d’+1}}=C CL​CRqd’+1​=C，可减少communication压力，Prover只发送 C R C_R CR​，Verifier计算 C L ← C ⋅ C R − q d ’ + 1 C_L\leftarrow C\cdot C_R^{-q^{d’+1}} CL​←C⋅CR−qd’+1​，这种情况Verifier需要做幂乘运算。替代方案是，Verifier infers C R q d ’ + 1 C_R^{q^{d’+1}} CRqd’+1​ from PoE：（PoE的security不要求 C R q d ’ + 1 C_R^{q^{d’+1}} CRqd’+1​在challenge l l l之前发送，因为其仅由 C R C_R CR​和 q d ’ + 1 q^{d’+1} qd’+1唯一确定。）
    – Prover提供 Q Q Q值，Verifier直接计算 C R q d ’ + 1 ← Q l C R r C_R^{q^{d’+1}}\leftarrow Q^lC_R^r CRqd’+1​←QlCRr​ for a challenge l l l and r ← q d ’ + 1 m o d    l r\leftarrow q^{d’+1}\mod l r←qd’+1modl。
    – Verifier计算 C L ← C / C R q d ’ + 1 C_L\leftarrow C/{C_R^{q^{d’+1}}} CL​←C/CRqd’+1​。
    同理，也可通过 y L ← y − z d ’ + 1 y R y_L\leftarrow y-z^{d’+1}y_R yL​←y−zd’+1yR​来计算 y L y_L yL​。
    最终，可将communication cost reduce为仅需要2个group elements和1个field element。
    再加上Prover发送 f f f具有约 log ⁡ ( d + 1 ) \log(d+1) log(d+1)个field elements，最终总的communication为约 2 log ⁡ ( d ) 2\log(d) 2log(d)个group elements和 2 log ⁡ ( d ) 2\log(d) 2log(d)个field elements。

  • 在多个点进行evaluation：evaluate at a vector of points z ⃗ ∈ Z p k \vec{z}\in\mathbb{Z}_p^k z ∈Zpk​，对应为 a vector of evaluation values y ⃗ ∈ Z p k \vec{y}\in\mathbb{Z}_p^k y ​∈Zpk​。
    Prover在每一轮仍然发送 C L ∈ G C_L\in\mathbb{G} CL​∈G和 C R ∈ G C_R\in\mathbb{G} CR​∈G，以及 y ⃗ L , y ⃗ R ∈ Z p k \vec{y}_L,\vec{y}_R\in\mathbb{Z}_p^k y ​L​,y ​R​∈Zpk​。
    在最后一轮，Prover仅需发送一个integer f f f 使得 g f = C g^f=C gf=C和 f   m o d   p = y f\ mod\ p=y f mod p=y均成立。
    多个点进行evaluation比单独每个点都运行一次evaluation的效率要高。当 λ = ⌈ log ⁡ 2 ( p ) ⌉ \lambda= \left \lceil \log_2{(p)}\right \rceil λ=⌈log2​(p)⌉为120时，evaluating the polynomial at an additional point increases the proof size by only 15 log ⁡ ( d + 1 ) 15\log(d+1) 15log(d+1) bytes。

  • Joining Evals：在一些应用场景中，需要对多个（ m m m个）polynomial commitments 在同一个point z z z 进行evaluate。
    可以对这些polynomials进行random linear combination为一个polynomial，然后evaluate at z z z。由此，the size of the eval proof 与 m m m无关。这种random linear combination会轻微增加 q q q的上限值。

    以上也可引申为evaluate a single polynomial at different points，或者evaluate m m m polynomials at k k k points with very little overhead。

  • Evaluate the polynomial over multiple fields：polynomial commitment scheme非常灵活，在Setup时，并未限定prime field Z p \mathbb{Z}_p Zp​或者degree d d d。而是commit to an integer polynomial with bounded coefficients。该integer polynomial 可被evaluated modulo任意素数 which are exponential in the security parameter λ \lambda λ as the soundness error is proportional to its inverse。同时， q q q必须足够大，以保证特定prime p p p 和 degree d d d 场景下的安全。另外，challenge α \alpha α 的区间应为 [ − 2 λ , 2 λ ] [-2^{\lambda}, 2^{\lambda}] [−2λ,2λ]。

4.4 多变量polynomial commitment

先考虑有 μ \mu μ 个变量的多项式，每个变量的degree为 d d d；后续可扩展至每个变量的degree不同的情况。

设置 q i = q ( d + 1 ) i q_i=q^{(d+1)^i} qi​=q(d+1)i，则 f ^ ( q 1 , ⋯   , q μ ) ∈ Z \hat{f}(q_1,\cdots,q_{\mu})\in\mathbb{Z} f^​(q1​,⋯,qμ​)∈Z为an encoding of the multivariate polynomial f ( X 1 , ⋯   , X μ ) f(X_1,\cdots,X_{\mu}) f(X1​,⋯,Xμ​) with maximum degree d d d。
使用 D e c M u l t i ( f ( q ) , μ , d ) Dec_{Multi}(f(q),\mu,d) DecMulti​(f(q),μ,d)来表示the decoding of an μ \mu μ-variate polynomial with degree exactly d d d in each variable。该decoding算法可使用上面的单变量decoding算法来decode a univariate polynomial h ^ ( X ) \hat{h}(X) h^(X) of degree ( d + 1 ) μ − 1 (d+1)^{\mu}-1 (d+1)μ−1。然后associate each monomial of the univariate polynomial with a degree vector ( d 1 , ⋯   , d μ ) (d_1,\cdots,d_{\mu}) (d1​,⋯,dμ​) of the multivariate polynomial。The coefficient of the i i ith monomial becomes the coefficient of the ( d 1 , ⋯   , d μ ) (d_1,\cdots,d_{\mu}) (d1​,⋯,dμ​)-monomial, where ( d 1 , ⋯   , d μ ) (d_1,\cdots,d_{\mu}) (d1​,⋯,dμ​) is the base- ( d + 1 ) (d+1) (d+1) decomposition of i i i。

多变量polynomial commitment的思路为：（ f ( X 1 , ⋯   , X μ ) f(X_1,\cdots,X_{\mu}) f(X1​,⋯,Xμ​)）

  • 先设置所有变量 ( X 1 , ⋯   , X μ ) = ( q 1 , ⋯   , q μ ) (X_1,\cdots,X_{\mu})=(q_1,\cdots,q_{\mu}) (X1​,⋯,Xμ​)=(q1​,⋯,qμ​)，其中 q i = q ( d + 1 ) i − 1 q_i=q^{(d+1)^{i-1}} qi​=q(d+1)i−1；
  • 对 ( q 1 , ⋯   , q μ ) (q_1,\cdots,q_{\mu}) (q1​,⋯,qμ​) 进行commit， C = g f ( q 1 , ⋯   , q μ ) C=g^{f(q_1,\cdots,q_{\mu})} C=gf(q1​,⋯,qμ​)；
  • 由后往前，逐步替换调用单变量polynomial commitment。

4.5 为polynomial commitment增加hiding属性

4.6 为polynomial commitment增加zero-knowledge属性

借鉴了Chiesa等人2017年论文《A zero knowledge sumcheck and its applications》以及Bulletproofs系列论文思路，引入了degree为 d d d的random polynomial r ( X ) r(X) r(X)。
详细算法如下图所示：（其中 k ( X ) k(X) k(X)为随机多项式， r k r_k rk​用于对随机多项式的commitment增加hiding属性，随机多项式的commitment值为 R R R，随机多项式在 z z z点的evaluation值为 y k y_k yk​。）

4.7 polynomial commitment的性能对比



现有的polynomial commitment方案有：

  • 基于pairing的单变量polynomial commitment：
    如Kate等人2010年论文《Constant-size commitments to polynomials and their applications》为单变量polynomial commitment，其evaluation proof仅有a single element in a bilinear group，验证过程仅需要a single pairing computation。但是需要trusted setup，且其structured reference string的size与polynomial的degree呈linear关系。
    而本文的DARK polynomial commitment scheme无需trusted setup，proof size和verification work均为 O ( log ⁡ ( d ) ) O(\log(d)) O(log(d))，其中 d d d为polynomial degree。

  • 基于pairing的多变量polynomial commitment：
    本文的DARK polynomial commitment scheme，对于 u u u-variate polynomial of degree d d d in each variable，其proof size为 O ( log ⁡ ( μ log ⁡ ( d ) ) ) O(\log(\mu\log(d))) O(log(μlog(d)))。
    在Kate等人基础上扩展的，Yupeng Zhan等人2017年论文《vSQL: Verifying arbitrary SQL queries over dynamic outsourced databases》中的多变量polynomial其evaluation proof包含 μ \mu μ个group elements。其中 μ \mu μ表示变量的个数。

  • 基于Discrete Logarithm的polynomial commitment：
    Bulletproofs系列论文（2016年论文《Efficient Zero-Knowledge Arguments for Arithmetic Circuits in the Discrete Log Setting》 和 2018年论文《Bulletproofs: Short Proofs for Confidential Transactions and More》）均是基于prime order groups in which the discrete logarithm is hard。
    Wahby等人2018年论文《Doubly-efficient zkSNARKs without trusted setup》中是依赖inner product argument来实现polynomial commitment。该polynomial commitment 具有logarithmic evaluation proofs with great constants。但是其verifier time为linear in the size of the polynomial，如 ( d + 1 ) μ (d+1)^{\mu} (d+1)μ for μ \mu μ-variate degree d d d polynomial。
    2016年论文《Efficient Zero-Knowledge Arguments for Arithmetic Circuits in the Discrete Log Setting 》中的more general version commitment也可用于实现polynomial commitment，其evaluation proof具有square root verifier time和square root proof size。

  • 基于Merkle trees of Reed-Solomon codewords的polynomial commitment：
    Ben-Sasson等人2018年论文《Fast reed-solomon interactive oracle proofs of proximity》中的FRI protocol是一个高效的interactive oracle proof (IOP)，其committed oracle非常接近a Reed-Solomon codeword，意味着Prover commits to large sequences of field elements，Verifier queries only a few specific elements rather than reading the entire sequence。
    该抽象功能编译为了a Merkle tree，具有constant-size commitments，query的elements数量为logarithmic in the length of the codeword, i.e., the size of the oracle。
    FRI在最近的一些zero-knowledge proof system中都有应用，如：
    – Ben-Sasson等人2019年论文《Scalable zero knowledge with no trusted setup》的STARK方案。
    – Ben-Sasson等人2019年论文《Aurora: Transparent succinct arguments for R1CS》的Aurora方案。
    – Chiesa等人2019年论文《Fractal: Post-quantum and transparent recursive proofs from holography》的Fractal方案。
    该oracle为a Reed-Solomon codeword，可代表evaluations of a low-degree polynomial f f f on an evaluation set S ⊂ F S\subset\mathbb{F} S⊂F。而polynomial commitment scheme要求可query the polynomial outside of the evaluation set。基于FRI构建polynomial commitment相关的研究有：（需依赖对称密码学并具有抗量子性，evaluation proof size和verifier time为 O ( λ log ⁡ 2 ( d ) ) O(\lambda\log^2(d)) O(λlog2(d))）
    – Ben-Sasson等人2019年论文《DEEP-FRI: sampling outside the box improves soundness》
    – Jiaheng Zhang等人2019年论文《Transparent polynomial delegation and its applications to zero knowledge proof》
    – Kattis等人2019年论文《RedShift: Transparent SNARKs from list polynomial commitment IOPs》

各方案性能详细对比见下图：

5. Transparent SNARKs via Polynomial IOPs

5.1 Algebraic Linear IOPs

interactive oracle proof (IOP) 为multi-round interactive PCP：

  • 在IOP的每一轮，Verifier给Prover发送a message，Prover respond a polynomial length proof。Verifier可query via random access。
    A t t t-round l l l-query IOP 具有 t t t rounds of interaction in which the Verifier makes exactly l l l queries in each round。

5.2 Polynomial IOP reduction

可基于a (multivariate) Polynomial IOP 构建 algebraic linear IOP，需要用到单变量Polynomial IOPs的2个工具：

  • Coefficient queries：Verifier验证多项式的某个系数确实是某个值。
  • Inner product：Verifier验证两组向量的inner product为指定值。其中向量可理解为多项式系数。

5.2.1 多项式系数查询coefficient query

对于一个 ( 1 , d ) (1,d) (1,d)-Polynomial IOP for the statement f i = a f_i=a fi​=a with respect to a polynomial f ( X ) = ∑ j = 0 d f j X j f(X)=\sum_{j=0}^{d}f_jX^j f(X)=∑j=0d​fj​Xj，系数查询的相应思路为：

  • Prover：将 f ( X ) f(X) f(X)拆分为 f ( X ) = f L ( X ) + a X i + X i + 1 f R ( X ) f(X)=f_L(X)+aX^i+X^{i+1}f_R(X) f(X)=fL​(X)+aXi+Xi+1fR​(X)，将多项式 f L ( X ) f_L(X) fL​(X)和 f R ( X ) f_R(X) fR​(X)发送给Verifier。
  • Verifier：选择随机数 β ← F p \beta\leftarrow \mathbb{F}_p β←Fp​，query for y L ← f L ( β ) , y R ← f R ( β ) , y ← f ( β ) y_L\leftarrow f_L(\beta),y_R\leftarrow f_R(\beta),y\leftarrow f(\beta) yL​←fL​(β),yR​←fR​(β),y←f(β)。验证 y = y L + a β i + β i + 1 y R   m o d   p y=y_L+a\beta^i+\beta^{i+1}y_R\ mod\ p y=yL​+aβi+βi+1yR​ mod p。

Verifier仅接收given proof oracles for polynomials f , f L , f R f,f_L,f_R f,fL​,fR​ in F p [ X ] \mathbb{F}_p[X] Fp​[X] of degree at most d , i − 1 , d − i − 1 d,i-1,d-i-1 d,i−1,d−i−1 such that f ( β ) = f L ( β ) + a β i + β i + 1 f R ( β ) f(\beta)=f_L(\beta)+a\beta^i+\beta^{i+1}f_R(\beta) f(β)=fL​(β)+aβi+βi+1fR​(β) for random β ← F \beta\leftarrow \mathbb{F} β←F。通过Schwartz-Zippel lemma可知，若 f ( X ) ≠ f L ( X ) + a X i + X i + 1 f R ( X ) f(X)\neq f_L(X)+aX^i+X^{i+1}f_R(X) f(X)​=fL​(X)+aXi+Xi+1fR​(X)的情况下Verifier验证通过的概率不高于 d / ∣ F ∣ d/|\mathbb{F}| d/∣F∣。由此可知，若验证通过，则意味着 a a a即为 f f f的第 i i i个系数。

5.2.2 inner product

Prover首先发送2个degree为 d d d的单变量多项式 f , g f,g f,g，然后需向Verifier证明 < f ⃗ , g ⃗ r > = a = ∑ i = 0 d f i g d − i <\vec{f},\vec{g}^r>=a=\sum_{i=0}^{d}f_ig_{d-i} <f ​,g ​r>=a=∑i=0d​fi​gd−i​，其中 f ⃗ , g ⃗ \vec{f},\vec{g} f ​,g ​分别表示 f , g f,g f,g的系数向量， g ⃗ r \vec{g}^r g ​r表示 g ⃗ \vec{g} g ​的逆向量。
(因为有 g ( X ) = X d g r ( X − 1 ) = X d ( g d + g d − 1 X − 1 + ⋯ + g 0 X − d ) = g 0 + g 1 X + ⋯ + g d X d g(X)=X^dg^r(X^{-1})=X^d(g_d+g_{d-1}X^{-1}+\cdots+g_0X^{-d})=g_0+g_1X+\cdots+g_dX^d g(X)=Xdgr(X−1)=Xd(gd​+gd−1​X−1+⋯+g0​X−d)=g0​+g1​X+⋯+gd​Xd，从而也可进行 < f ⃗ , g ⃗ > <\vec{f},\vec{g}> <f ​,g ​>的inner product证明。)
详细思路为：

  • Prover：发送proof oracles for f ( X ) , g ( X ) f(X),g(X) f(X),g(X)，以及degree 为 2 d 2d 2d的多项式乘积 h ( X ) = f ( X ) ⋅ g ( X ) h(X)=f(X)\cdot g(X) h(X)=f(X)⋅g(X) 给Verifier。
  • Verifier：选择随机数 β ← F \beta\leftarrow\mathbb{F} β←F，然后query for y 1 ← f ( β ) , y 2 ← g ( β ) , y 3 ← h ( β ) y_1\leftarrow f(\beta),y_2\leftarrow g(\beta),y_3\leftarrow h(\beta) y1​←f(β),y2​←g(β),y3​←h(β)。Verifier验证 y 1 y 2 = y 3 y_1y_2=y_3 y1​y2​=y3​是否成立。若不成立则返回0，不执行后续步骤。
  • Prover和Verifier：调用1 round IOP (5.2.1节的多项式系数查询coefficient query) 来证明h(X)的 d d dth 系数（on term X d X^d Xd）为 a a a即可。（注意，此处的调用可在第一轮即发起，从而不需要额外再增加一轮。）

根据Schwartz-Zippel lemma，若 h ( X ) ≠ f ( X ) ⋅ g ( X ) h(X)\neq f(X)\cdot g(X) h(X)​=f(X)⋅g(X)而Verifier check y 1 y 2 = y 3 y_1y_2=y_3 y1​y2​=y3​的概率不高于 2 d / ∣ F ∣ 2d/|\mathbb{F}| 2d/∣F∣。从而借助Polynomial IOP实现了inner product < f ⃗ , g ⃗ r > = a <\vec{f},\vec{g}^r>=a <f ​,g ​r>=a证明。

任意的public-coin t t t-round stateless algebraic linear IOP可借助preprocessing 转换为 t + 1 t+1 t+1-round Polynomial IOP。


5.3 compiling Polynomial IOPs

5.4 Polynomial IOP的应用案例

Polynomial IOP可用于如：
– STARK （Ben-Sasson等人2019年论文《Scalable zero knowledge with no trusted setup》）。
– 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》)。
– Spartan （微软研究中心2019年论文《Spartan: Efficient and general-purpose zkSNARKs without trusted setup》。）
– QAP （Gennaro等人2012年论文《Quadratic span programs and succinct NIZKs without PCPs》）

根据NP relation R \mathcal{R} R的complexity类型不同，可分为：

  • 具有arithmetic complexity n n n，可表示为 2 2 2-fan-in arithmetic circuit with a total of n n n gates。
  • 具有multiplicative complexity n n n，可表示为an arithmetic circuit with a total of n n n multiplication gates, where each multiplication gate has 2 2 2 inputs。
  • 具有R1CS complexity，可表示为 ( A , B , C , v , w ) (A,B,C,v,w) (A,B,C,v,w)，其中 A , B , C ∈ F m × ( l + 1 ) , ( v , w ) ∈ F l A,B,C\in\mathbb{F}^{m\times (l+1)},(v,w)\in\mathbb{F}^l A,B,C∈Fm×(l+1),(v,w)∈Fl， n n n为maximum number of non-zero entries in either A , B A,B A,B, or C C C。

5.4.1 Sonic

Sonic为具有universal trusted setup的zk-SNARK system。生成具有 n n n个group elements的Structured Reference String (SRS)，后续可用于prove any statement represented as an arithmetic circuit with at most n n n gates。
同时SRS can be updated without re-doing the initial setup，如用于prove larger circuit或increase the distribution of trust。
Sonic论文中未以IOP形式描述，而是依赖于KZG10的基础上构建了一种特殊的polynomial commitment，要求Prover commit to a Laurent polynomial with no constant term。

借助本文的多项式系数查询coefficient query，可将Sonic的核心思想重新描述为：

  • Sonic双变量polynomial commitment：
  • Sonic 单变量polynomial commitment：

PLONK和Marlin在Sonic的基础上进行了改进，构建了不同的Polynomial IOP：

  • Plonk：
  • Marlin：

将Sonic Polynomial IOP与本文第四节中的transparent polynomial compiler结合，可构建新的transparent zk-SNARK：

5.4.2 STARK

STRAK build an IOP for uniform computations, specified by a program P P P and timebound T T T on the running time of P P P. IOP本身可compiled into a concrete proof system using FRI和Merkle trees。
STARK IOP可看成是单变量Polynomial IOP：

5.4.3 Spartan

5.4.4 QAP

参考资料

[1] polynomial norm

更多推荐

Supersonic Transparent SNARKs from DARK Compilers学习笔记