proof-carrying data from accumulation schemes學習筆記

1. 引言

B¨unz 等人2020年論文《proof-carrying data from accumulation schemes》，暫無收錄資訊。

代碼實作：

• https://github.com/scipr-lab/poly-commit 中的ipa_pc

Recursive proof composition可用于incrementally-verifiable computation (IVC)以及proof-carrying data (PCD)。

現有的基于遞歸調用構造的SNARK，Verifier的驗證時間是sublinear in the size of the statement。

Bowe等人2019年論文《Recursive Proof Composition without a Trusted Setup》中建構了特定的recursive composition用于SNARK，使得Verifier time不再是sub-linear了。但是他們在該論文中忽略了具體的細節同時也未能提供相應的security property證明。

在本文，定義了an accumulation scheme for a non-interactive argument，足以建構PCD以及SNARKs，且無需sublinear-time verifier。

要點：

相當于借助 “SNARK+accumulator” 來實作 PCD，對計算中的每個步驟進行驗證。

要求accumulator 不随計算步驟的增加而增長，且允許batch延遲驗證。

其中accumulator的實作有2種：

– 1）基于discrete logarithm的polynomial commitment P C D L PC_{DL} PCDL​ 的accumulator設計，參見本博文第5節内容。

– 2）基于 knowledge assumption in bilinear groups 的 polynomial commitment P C A G M PC_{AGM} PCAGM​ 的accumulator 設計，參見本博文第6節内容。

1.1 What is PCD?

proof-carrying data (PCD) 由Chiesa等人在2010年論文《Proof-Carrying Data and Hearsay Arguments from Signature Cards》中提出，可用于不信任的各方進行分布式無限計算，保證每個計算的中間狀态都可以succinctly verified。

PCD支援基于（可能是無限的）有向無環圖計算，with messages passed along directed edges。通過為每個message附加一個succinct proof以證明其correctness。

可将PCD看成是incrementally-verifiable computation (IVC) （參見Paul Valiant 2008年論文《Incrementally Verifiable Computation or Proofs of Knowledge Imply Time/Space Efficiency》）的generalization，IVC = PCD for the path graph。

PCD可廣泛用于：

• enforcing language semantics [CTV13]，Chong等人2013年論文《Enforcing Language Semantics Using Proof-Carrying Data》。
• verifiable MapReduce computations [CTV15]，Chiesa等人2015年論文《Cluster Computing in Zero Knowledge》。
• image authentication [NT16]，Naveh等人2016年論文《PhotoProof: Cryptographic Image Authentication for Any Set of Permissible Transformations》。
• succinct blockchains [Co17;KB20;BMRS20]，Coda protocol、Kattis等人2020年論文《Proof of Necessary Work: Succinct State Verification with Fairness Guarantees》以及Bonneau等人2020年論文《Coda: Decentralized Cryptocurrency at Scale》。

現有的建構PCD的方式是基于recursive composition of succinct non-interactive arguments (SNARGs) [BCCT13;BCTV14;COS20]（Bitansky等人2013年論文《Recursive Composition and Bootstrapping for SNARKs and Proof-Carrying Data》、Ben-Sasson等人2014年論文《Scalable Zero Knowledge via Cycles of Elliptic Curves》以及Chiesa等人2020年論文《Fractal: Post-Quantum and Transparent Recursive Proofs from Holography》）。證明某個具有 t t t steps的計算被正确執行了，基本思路為：

the t t t-th step of the computation was executed correctly, and there exists a proof that the computation was executed correctly for t − 1 t-1 t−1 steps。

現有的實作要求：the statement we are proving does not grow with the number of recursion steps t t t。

Bowe等人2019年論文《Recursive Proof Composition without a Trusted Setup》沒有verify the previous proof π t − 1 \pi_{t-1} πt−1​，而是将proof 添加僅accumulator，然後在最終進行verify。同時accumulator must not grow in size。該論文提供了一種特殊的SNARK建構思路，其證明了所建構的SNARK是secure的，但是并沒有包含其recursive安全性的相關定義或證明。

借助recursion的SNARK相關研究有：

• Halo
• Marlin

1.2 本文主要貢獻

本文的主要貢獻：

• 引入了accumulation scheme for a predicate Φ : X → { 0 , 1 } \Phi: X\rightarrow \{0,1\} Φ:X→{0,1}。

  在Bowe等人2019年論文《Recursive Proof Composition without a Trusted Setup》的基礎上進行了改進。

  accumulation scheme 可了解為：存在無限的stream q 1 , q 2 , c d o t s q_1,q_2,cdots q1​,q2​,cdots，其中每個 q i ∈ X q_i\in X qi​∈X。

  at time i i i，引入accumulators a c c i acc_i acci​，存在以下三種算法（均為stateless）：【accumulation prover、accumulation verifier和decider】

  – the accumulation prover receives ( q i , a c c i − 1 ) (q_i,acc_{i-1}) (qi​,acci−1​) and computes a c c i acc_i acci​。

  – the accumulation verifier receives ( q i , a c c i − 1 , a c c i ) (q_i,acc_{i-1},acc_i) (qi​,acci−1​,acci​)，然後驗證 a c c i − 1 acc_{i-1} acci−1​和 q i q_i qi​ were correctly accumulated into a c c i acc_i acci​，若驗證不通過，則流程停止。

  – at any time t t t，decider可validate a c c t acc_t acct​, which establishes that, for all i ∈ [ t ] i\in [t] i∈[t], Φ ( q i ) = 1 \Phi(q_i)=1 Φ(qi​)=1。

  以上三個算法都是無狀态的，為避免trivial construction，要求：

  – 1）accumulation verifier的效率應高于 Φ \Phi Φ；

  – 2）accumulator size以及以上三個算法的running time不會随時間而增長。

  any SNARK having an accumulation scheme where the accumulation verifier is sublinear can be used to build a proof-carrying data (PCD) scheme, even if the SNARK verifier is not itself sublinear。Chiesa等人2020年論文《Fractal: Post-Quantum and Transparent Recursive Proofs from Holography》中指出，若SNARK和accumulation scheme為量子安全的，則PCD scheme也為量子安全。而是否存在non-trivial accumulation schemes for post-quantum SNARKs仍是個公開的難題。

[MBKM19; GWC19; CHMMVW20] Maller等人2019年論文《Sonic: Zero-Knowledge SNARKs from Linear-Size Universal and Updateable Structured Reference Strings》、Gabizon等人2019年論文《PLONK: Permutations over Lagrange-bases for Oecumenical Noninteractive arguments of Knowledge》以及 Chiesa等人2020年論文《Marlin: Preprocessing zkSNARKs with Universal and Updatable SRS》中建構的SNARKs，其Verifiers are succinct relative to a specific predicate: checking the opening of a polynomial commitment [KZG10]。

現有的具有accumulation scheme in random oracle model的polynomial commitment scheme主要有兩大類：

• P C D L PC_{DL} PCDL​：基于security of discrete logarithm的，相關的研究成果有：[BCCGP16; BBBPWM18; WTSTW18]

  – Bootle等人2016年論文《Efficient Zero-Knowledge Arguments for Arithmetic Circuits in the Discrete Log Setting》，參見部落格 Efficient Zero-Knowledge Arguments for Arithmetic Circuits in the Discrete Log Setting學習筆記。

  – B¨unz等人2018年論文《Bulletproofs: Short Proofs for Confidential Transactions and More》，參見部落格 Bulletproofs: Short Proofs for Confidential Transactions and More學習筆記。

  – Wahby等人2018年論文《Doubly-Efficient zkSNARKs Without Trusted Setup》，參見部落格 Doubly-Efficient zkSNARKs Without Trusted Setup學習筆記。

• P C A G M PC_{AGM} PCAGM​：基于knowledge assumption in bilinear groups，相關的研究成果有：[KZG10; CHMMVW20]

  – Kate等人2010年論文《Constant-Size Commitments to Polynomials and Their Applications》

  – Chiesa等人2020年論文《Marlin: Preprocessing zkSNARKs with Universal and Updatable SRS》

對于這兩種schemes，the cost of checking that an accumulation step was performed correctly is much less than the cost of checking an evaluation proof。

本文的 accumulation scheme for P C D L PC_{DL} PCDL​ 是在Bowe等人2019年論文《Halo: Recursive Proof Composition without a Trusted Setup》中的Polynomial commitment的基礎上進行了改進。

建構PCD scheme的方式有兩種：

• 通過 P C D L PC_{DL} PCDL​：PCD based on discrete logarithms，可建構PCD scheme in the uniform reference string model (如，without secret parameters) and small argument sizes。之前的PCD scheme要麼需要structured reference strings [BCTV14]，要麼需要larger argument sizes ([COS20])。本文的PCD scheme可基于任意的cycle of elliptic curves來執行個體化。而之前的具有small argument size的PCD scheme需要使用昂貴的cycles of pairing-friendly elliptic cuves [BCTV14; CCW19]。

• 通過 P C A G M PC_{AGM} PCAGM​：lightweight PCD based on bilinear groups。這種PCD scheme中的recursive statement不需要任何的pairing computation check，因為pairing驗證推遲到了recursive statement之外。而之前基于pairing-based SNARK建構的PCD scheme則需要check pairing computations。

  本文建構的PCD具有啟發意義：instantiate the random oracle of certain SNARK constructions with an appropriate hash function。

1.3 IVC/PCD的相關研究成果

1.3.1 PCD from SNARKs

Bitansky等人2013年論文《Recursive Composition and Bootstrapping for SNARKs and Proof-Carrying Data》中證明了recursive composition of SNARKs for machine computations implies PCD for constant-depth graphs，同時也暗示 IVC for polynomial-time machine computations。為達成recursive composition，從實際效率上考慮，使用preprocessing SNARKs for circuits要優于使用SNARKs for machines [BCTV14; COS20]。相關的實際應用有：Coda項目。[Co17; BMRS20]

目前基于SNARKs建構PCD的思路主要有以下2種：

• 基于pairing-based SNARKs建構PCD：

  Ben-Sasson等人2014年論文《Scalable Zero Knowledge via Cycles of Elliptic Curves》中使用pairing-based SNARKs with a special algebraic property實作了efficient recursive composition with very small argument sizes (linear in the security parameter λ \lambda λ)。

  使用pairing-based SNARKs具有2個主要缺陷：

  1）需要sampling a structured reference string involving secret values (“toxic waste”)，這些有毒垃圾如果洩露，則會影響安全性。

  2）Verifier performs operations over a finite field that is necessarily different from the field supported “natively” by the statement it is checking。為了避免expensive simulation of field arithmetic，建構過程中需要使用pairing-friendly cycles of elliptic curves，進而限制了實際應用時field的選型，為了保證security，往往需要a large base field。

• 基于IOP-based SNARKs建構PCD：

  Chiesa等人2020年論文《Fractal: Post-Quantum and Transparent Recursive Proofs from Holography》中使用holographic IOP建構了一種preprocessing SNARK，在(quantum) random oracle model下是無條件安全的，是一種post-quantum preprocessing SNARK in the uniform reference string model (i.e., without toxic waste)。在該論文中z橫眉了任意的抗量子攻擊SNARK可通過recursive composition産生抗量子攻擊的PCD scheme。主要缺點在于：基于現有的holographic IOPs，其argument size很大，為 O ( λ 2 log ⁡ 2 N ) O(\lambda^2\log^2N) O(λ2log2N)bits，其中 N N N為circuit size。

1.3.2 IVC from homomorphic encryption

Naor等人2019年論文《Incrementally Verifiable Computation via Incremental PCPs》中将某種omomorphic encryption和incrmental PCP結合實作了IVC。其security基于falsifiable assumption。其IVC實作主要有2種缺陷：

• 待驗證的computation必須為deterministic的（所有基于falsifiable assumption的建構都有此要求）。
• 更微妙的是，completeness僅在intermediate proofs were honestly generated場景下才成立。這就意味着可能存在以下攻擊：an adversary provides an intermediate proof that verifies, but it is impossible for honest parties to generate new proofs for subsequent computations。即中途塞入無效的intermediate proof将影響後續的流程。

本文建構的PCD可避免以上這兩種缺陷，實作nondeterministic computation和相應的completeness，避免被中間錯誤intermediate proof攻擊。

1.4 Pedersen commitment定義及屬性

• Pedersen commitment定義：

  

  

• Pedersen commitment的雙線性屬性：

  

1.5 基于discrete logarithm 建構的polynomial commitment

以下所有算法中的oracle access都是基于相同的random oracle ρ 0 \rho_0 ρ0​。

為了友善描述，假設 d + 1 d+1 d+1和 D + 1 D+1 D+1均為2的幂乘，即滿足 d + 1 = 2 k , D + 1 = 2 m d+1=2^k,D+1=2^m d+1=2k,D+1=2m。

對于向量 a ⃗ ∈ S n \vec{a}\in S^n a

∈Sn，二分法時， l ( a ⃗ ) = ( a 1 , ⋯   , a n / 2 ) l(\vec{a})=(a_1,\cdots,a_{n/2}) l(a

)=(a1​,⋯,an/2​)和 r ( a ⃗ ) = ( a n / 2 + 1 , ⋯   , a n ) r(\vec{a})=(a_{n/2+1},\cdots,a_n) r(a

)=(an/2+1​,⋯,an​)分别表示 a ⃗ \vec{a} a

的左半部分和右半部分。

基于discrete logarithm，對單變量多項式 p ( X ) = c 0 + c 1 X + ⋯ + c d X d p(X)=c_0+c_1X+\cdots+c_dX^d p(X)=c0​+c1​X+⋯+cd​Xd的polynomial commitment算法實作細節為：

• P C D L . S e t u p PC_{DL}.Setup PCDL​.Setup：

  

• P C D L . T r i m PC_{DL}.Trim PCDL​.Trim：（暫時隻考慮所有polynomial degree均為 d d d的情況）

  

• P C D L . C o m m i t PC_{DL}.Commit PCDL​.Commit：引入随機數 w w w，對多項式系數進行commit C = w S + ∑ i = 0 d c i G i C=wS+\sum_{i=0}^{d}c_iG_i C=wS+∑i=0d​ci​Gi​。

  

• P C D L . O p e n PC_{DL}.Open PCDL​.Open：借助[BCCGP16; BBBPWM18]中inner product argument的變種，計算evaluation proof π \pi π：（evaluation point為 z z z）

  – 1. 計算evaluation v = p ( z ) ∈ F q v=p(z)\in\mathbb{F}_q v=p(z)∈Fq​。

  – 2. sample 随機多項式 p ˉ ∈ F q ≤ d [ X ] \bar{p}\in\mathbb{F}_q^{\leq d}[X] pˉ​∈Fq≤d​[X]，使得 p ˉ ( z ) = 0 \bar{p}(z)=0 pˉ​(z)=0。

  – 3. sample 相應的commitment randomness w ˉ ∈ F q \bar{w}\in\mathbb{F}_q wˉ∈Fq​。

  – 4. 計算随機多項式 p ˉ \bar{p} pˉ​的hiding commitment： C ˉ = C M . C o m m i t ρ 0 ( c k ⃗ , p ˉ ; w ˉ ) \bar{C}=CM.Commit^{\rho_0}(\vec{ck},\bar{p};\bar{w}) Cˉ=CM.Commitρ0​(ck

  ,pˉ​;wˉ)。

  – 5. 計算challenge α = ρ ( C , z , v , C ˉ ) ∈ F q ∗ \alpha=\rho(C,z,v,\bar{C})\in\mathbb{F}_q^* α=ρ(C,z,v,Cˉ)∈Fq∗​。

  – 6. 計算多項式： p ’ = p + α p ˉ = ∑ i = 0 d c i X i ∈ F q [ X ] p’=p+\alpha \bar{p}=\sum_{i=0}^{d}c_iX^i\in\mathbb{F}_q[X] p’=p+αpˉ​=∑i=0d​ci​Xi∈Fq​[X]。

  – 7. 計算commitment randomness： w ′ = w + α w ˉ ∈ F q w'=w+\alpha\bar{w}\in\mathbb{F}_q w′=w+αwˉ∈Fq​。

  – 8. 計算多項式 p ’ p’ p’的non-hiding commitment： C ′ = C + α C ˉ − w ′ S ∈ G C'=C+\alpha\bar{C}-w'S\in\mathbb{G} C′=C+αCˉ−w′S∈G。

  計算 0 0 0-th challenge field element ξ 0 = ρ o ( C ′ , z , v ) ∈ F q \xi_0=\rho_o(C',z,v)\in\mathbb{F}_q ξ0​=ρo​(C′,z,v)∈Fq​，用它來計算group element H ′ = ξ 0 H ∈ G H'=\xi_0H\in\mathbb{G} H′=ξ0​H∈G。

  轉為inner product 證明：

  a)public info： z ⃗ 0 = ( 1 , z , ⋯   , z d ) ∈ F q d + 1 \vec{z}_0=(1,z,\cdots,z^d)\in\mathbb{F}_q^{d+1} z

  0​=(1,z,⋯,zd)∈Fqd+1​ 和 G ⃗ 0 = ( G 0 , G 1 , ⋯   , G d ) ∈ G d + 1 \vec{G}_0=(G_0,G_1,\cdots,G_d)\in\mathbb{G}^{d+1} G

  0​=(G0​,G1​,⋯,Gd​)∈Gd+1， v ∈ F q v\in\mathbb{F}_q v∈Fq​， C ’ ∈ G C’\in\mathbb{G} C’∈G。

  b)private info： c ⃗ 0 = ( c 0 , c 1 , ⋯   , c d ) ∈ F q d + 1 \vec{c}_0=(c_0,c_1,\cdots,c_d)\in\mathbb{F}_q^{d+1} c

  0​=(c0​,c1​,⋯,cd​)∈Fqd+1​

  c)relation： < c ⃗ 0 , z ⃗ 0 > = v <\vec{c}_0,\vec{z}_0>=v <c

  0​,z

  0​>=v且 C ′ = ∑ i = 0 d c i G i C'=\sum_{i=0}^{d}c_iG_i C′=∑i=0d​ci​Gi​

  借助[BCCGP16; BBBPWM18]中二分法遞歸調用思想，在每一輪 i ∈ { 1 , ⋯   , log ⁡ 2 ( d + 1 ) } i\in \{1,\cdots,\log_2(d+1)\} i∈{1,⋯,log2​(d+1)}，有：

  1）設定 ∑ L = l ( G ⃗ i − 1 ) ∣ ∣ H ’ \sum_L=l(\vec{G}_{i-1})||H’ ∑L​=l(G

  i−1​)∣∣H’，計算left commitment L i = C M . C o m m i t ∑ L ( r ( c ⃗ i − 1 ) ∣ ∣ < r ( c ⃗ i − 1 ) , l ( z ⃗ i − 1 ) > ) L_i=CM.Commit_{\sum_L}(r(\vec{c}_{i-1})||<r(\vec{c}_{i-1}),l(\vec{z}_{i-1})>) Li​=CM.Commit∑L​​(r(c

  i−1​)∣∣<r(c

  i−1​),l(z

  i−1​)>)。

  2）設定 ∑ R = r ( G ⃗ i − 1 ) ∣ ∣ H ’ \sum_R=r(\vec{G}_{i-1})||H’ ∑R​=r(G

  i−1​)∣∣H’，計算right commitment R i = C M . C o m m i t ∑ R ( l ( c ⃗ i − 1 ) ∣ ∣ < l ( c ⃗ i − 1 ) , r ( z ⃗ i − 1 ) > ) R_i=CM.Commit_{\sum_R}(l(\vec{c}_{i-1})||<l(\vec{c}_{i-1}),r(\vec{z}_{i-1})>) Ri​=CM.Commit∑R​​(l(c

  i−1​)∣∣<l(c

  i−1​),r(z

  i−1​)>)。

  3）生成 i i i-th challenge ξ i = ρ 0 ( ξ i − 1 , L i , R i ) ∈ F q \xi_i=\rho_0(\xi_{i-1}, L_i,R_i)\in\mathbb{F}_q ξi​=ρ0​(ξi−1​,Li​,Ri​)∈Fq​。

  4）為下一輪建構新的commitment key： G ⃗ i = l ( G ⃗ i − 1 ) + ξ i ⋅ r ( G ⃗ i − 1 ) \vec{G}_i=l(\vec{G}_{i-1})+\xi_i\cdot r(\vec{G}_{i-1}) G

  i​=l(G

  i−1​)+ξi​⋅r(G

  i−1​)。

  5）建構下一輪的輸入： c ⃗ i = l ( c ⃗ i − 1 ) + ξ i − 1 ⋅ r ( c ⃗ i − 1 ) \vec{c}_i=l(\vec{c}_{i-1})+\xi_i^{-1}\cdot r(\vec{c}_{i-1}) c

  i​=l(c

  i−1​)+ξi−1​⋅r(c

  i−1​)和 z ⃗ i = l ( z ⃗ i − 1 ) + ξ i ⋅ r ( z ⃗ i − 1 ) \vec{z}_i=l(\vec{z}_{i-1})+\xi_i\cdot r(\vec{z}_{i-1}) z

  i​=l(z

  i−1​)+ξi​⋅r(z

  i−1​)。

  最後一輪，設定 U = G log ⁡ 2 ( d + 1 ) , c = c log ⁡ 2 ( d + 1 ) U=G_{\log_2(d+1)},c=c_{\log_2(d+1)} U=Glog2​(d+1)​,c=clog2​(d+1)​。

  最終給receiver發送的evaluation proof 為： π = ( L ⃗ , R ⃗ , U , c , C ˉ , w ′ ) \pi=(\vec{L},\vec{R},U,c,\bar{C},w') π=(L

  ,R

  ,U,c,Cˉ,w′)

• P C D L . C h e c k PC_{DL}.Check PCDL​.Check：receiver的輸入為：receiver key r k ⃗ P C \vec{rk}_{PC} rk

  PC​、commitment C C C、degree bound d d d、evaluation point z z z、claimed evaluation v v v 以及 evaluation proof π \pi π。 P C D L . C h e c k PC_{DL}.Check PCDL​.Check verifies the evaluation proof by invoking the verifier of the inner product argument：

  – 1. Parse c k ⃗ \vec{ck} ck

  as ( < g r o u p > , h k ⃗ , S ) (<group>,\vec{hk},S) (<group>,hk

  ,S)。

  – 2. 設定 d ’ = ∣ h k ⃗ ∣ − 1 d’=|\vec{hk}|-1 d’=∣hk

  ∣−1。

  – 3. 設定 r k ⃗ = ( < g r o u p > , S , H , d ’ ) \vec{rk}=(<group>,S,H,d’) rk

  =(<group>,S,H,d’)。

  – 4. 驗證 P C D L . S u c c i n c t C h e c k ρ 0 ( r k ⃗ , C , d , z , v , π ) PC_{DL}.SuccinctCheck^{\rho_0}(\vec{rk},C,d,z,v,\pi) PCDL​.SuccinctCheckρ0​(rk

  ,C,d,z,v,π) 是否成立，輸出為 ( h , U ) (h,U) (h,U)。

  – 5. 驗證 U = C M . C o m m i t ( c k , h ⃗ ) U=CM.Commit(ck,\vec{h}) U=CM.Commit(ck,h

  )，其中 h ⃗ \vec{h} h

  為多項式 h h h的系數。

• P C D L . S u c c i n c t C h e c k PC_{DL}.SuccinctCheck PCDL​.SuccinctCheck：在 P C D L . C h e c k PC_{DL}.Check PCDL​.Check和本文的accumulation scheme中均會調用。【 P C D L . O p e n PC_{DL}.Open PCDL​.Open中的inner product argument遞歸調用建構proof過程中，保證了每一輪的 C i = C M . C o m m i t G ⃗ i ( c i ⃗ ) + < c ⃗ i , z ⃗ i > H ′ C_i=CM.Commit_{\vec{G}_i}(\vec{c_i})+<\vec{c}_i,\vec{z}_i>H' Ci​=CM.CommitG

  i​​(ci​

  ​)+<c

  i​,z

  i​>H′成立。在最後一輪的 c ⃗ log ⁡ 2 ( d + 1 ) = c , z ⃗ log ⁡ 2 ( d + 1 ) = h ( z ) \vec{c}_{\log_2(d+1)}=c,\vec{z}_{\log_2(d+1)}=h(z) c

  log2​(d+1)​=c,z

  log2​(d+1)​=h(z)。】

  – 1. Parse r k ⃗ \vec{rk} rk

  as ( < g r o u p > , S , H , d ’ ) (<group>, S,H,d’) (<group>,S,H,d’)，和 π \pi π as ( L ⃗ , R ⃗ , U , c , C ˉ , w ’ ) (\vec{L},\vec{R},U,c,\bar{C},w’) (L

  ,R

  ,U,c,Cˉ,w’)。

  – 2. 驗證 d = d ’ d=d’ d=d’。

  – 3. 計算challenge： α = ρ 0 ( C , z , v , C ˉ ) ∈ F q ∗ \alpha=\rho_0(C,z,v,\bar{C})\in\mathbb{F}_q^* α=ρ0​(C,z,v,Cˉ)∈Fq∗​。

  – 4. 計算non-hiding commitment C ′ = C + α C ˉ − w ′ S ∈ G C'=C+\alpha\bar{C}-w'S\in\mathbb{G} C′=C+αCˉ−w′S∈G。

  – 5. 計算 0 0 0-th challenge ξ 0 = ρ 0 ( C ’ , z , v ) \xi_0=\rho_0(C’,z,v) ξ0​=ρ0​(C’,z,v)，設定 H ’ = ξ 0 H ∈ G H’=\xi_0H\in\mathbb{G} H’=ξ0​H∈G。

  – 6. 計算 group element C 0 = C ′ + v H ′ ∈ G C_0=C'+vH'\in\mathbb{G} C0​=C′+vH′∈G。

  – 7. 在每一輪 i ∈ { 1 , ⋯   , log ⁡ 2 ( d + 1 ) } i\in \{1,\cdots,\log_2(d+1)\} i∈{1,⋯,log2​(d+1)}，有：

  （a）生成 i i i-th challenge： ξ i = ρ 0 ( ξ i − 1 , L i , R i ) ∈ F q \xi_i=\rho_0(\xi_{i-1},L_i,R_i)\in\mathbb{F}_q ξi​=ρ0​(ξi−1​,Li​,Ri​)∈Fq​。

  （b）計算the i i i-th commitment： C i = ξ i − 1 L i + C i − 1 + ξ i R i ∈ G C_i=\xi_i^{-1}L_i+C_{i-1}+\xi_iR_i\in\mathbb{G} Ci​=ξi−1​Li​+Ci−1​+ξi​Ri​∈G。

  – 8. 定義單變量多項式 h ( X ) = ∏ i = 0 log ⁡ 2 ( d + 1 ) − 1 ( 1 + ξ log ⁡ 2 ( d + 1 ) − i X 2 i ) ∈ F q [ X ] h(X)=\prod_{i=0}^{\log_2(d+1)-1}(1+\xi_{\log_2(d+1)-i}X^{2^i})\in\mathbb{F}_q[X] h(X)=∏i=0log2​(d+1)−1​(1+ξlog2​(d+1)−i​X2i)∈Fq​[X]。

  – 9. 計算evaluation v ′ = c ⋅ h ( z ) ∈ F q v'=c\cdot h(z)\in\mathbb{F}_q v′=c⋅h(z)∈Fq​。

  – 10. 驗證 C log ⁡ 2 ( d + 1 ) = C M . C o m m i t ∑ ( c ∣ ∣ v ′ ) C_{\log_2(d+1)}=CM.Commit_{\sum}(c||v') Clog2​(d+1)​=CM.Commit∑​(c∣∣v′)，其中 ∑ = ( U ∣ ∣ H ′ ) \sum=(U||H') ∑=(U∣∣H′)。

  – 11. 輸出 ( h , U ) (h,U) (h,U)。

以上整個 P C D L PC_{DL} PCDL​算法具有hiding和extractability屬性。

注意：

借鑒了[BMMV19]中inner-product argument（參見部落格 Proofs for Inner Pairing Products and Applications 學習筆記 5.2.1節内容。）中的思想，由于 z ⃗ = ( 1 , z , z 2 , ⋯   , z d ) \vec{z}=(1,z,z^2,\cdots,z^d) z

=(1,z,z2,⋯,zd)為public info，且為structured，Verifier中的遞歸調用計算 z ⃗ i \vec{z}_i z

i​，可延遲計算最終以多項式 h ( z ) = ∏ i = 0 log ⁡ 2 ( d + 1 ) − 1 ( 1 + ξ log ⁡ 2 ( d + 1 ) − i z 2 i ) h(z) =\prod_{i=0}^{\log_2(d+1)-1}(1+\xi_{\log_2(d+1)-i}z^{2^i}) h(z)=∏i=0log2​(d+1)−1​(1+ξlog2​(d+1)−i​z2i)表示。

甚至可以建構多項式 h ( X ) = ∏ i = 0 log ⁡ 2 ( d + 1 ) − 1 ( 1 + ξ log ⁡ 2 ( d + 1 ) − i X 2 i ) ∈ F q [ X ] h(X)=\prod_{i=0}^{\log_2(d+1)-1}(1+\xi_{\log_2(d+1)-i}X^{2^i})\in\mathbb{F}_q[X] h(X)=∏i=0log2​(d+1)−1​(1+ξlog2​(d+1)−i​X2i)∈Fq​[X]，如 部落格 Proofs for Inner Pairing Products and Applications 學習筆記 5.2.1節内容 所示，為減少Verifier的計算壓力，再引入一個對 h ( X ) h(X) h(X)的polynomial commitment，将相應的計算壓力轉移給Prover。

1.6 基于knowledge assumption in bilinear groups 建構的polynomial commitment

已知maximum degree bound D D D，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： c k = { G , β G , ⋯   , β D G } ∈ G 1 D + 1 ck=\{G,\beta G,\cdots, \beta^D G\}\in\mathbb{G}_1^{D+1} ck={G,βG,⋯,βDG}∈G1D+1​，其中 β \beta β為random field element，為有毒垃圾；
• receiver key r k rk rk： r k = ( G , H , β H ) ∈ G 1 × G 2 rk=(G,H,\beta H)\in\mathbb{G}_1\times \mathbb{G}_2 rk=(G,H,βH)∈G1​×G2​。

• Committer：對多項式 p ∈ F q ≤ D [ X ] p\in\mathbb{F}_q^{\leq D}[X] p∈Fq≤D​[X]的commitment為：

  C = p ( β ) G C=p(\beta)G C=p(β)G

• Committer：為證明 p p p evaluates to v v v at a given point z ∈ F q z\in\mathbb{F}_q z∈Fq​，committer需建構一個witness polynomial w ( X ) = ( p ( X ) − v ) / ( X − z ) w(X)=(p(X)-v)/(X-z) w(X)=(p(X)−v)/(X−z)，輸出的evaluation proof 為 π = w ( β ) G ∈ G 1 \pi=w(\beta)G\in\mathbb{G}_1 π=w(β)G∈G1​。
• Receiver：驗證pairing方程式 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)是否成立。

基于knowledge assumption in bilinear groups，本文對單變量多項式 p ( X ) = c 0 + c 1 X + ⋯ + c d X d p(X)=c_0+c_1X+\cdots+c_dX^d p(X)=c0​+c1​X+⋯+cd​Xd的polynomial commitment scheme P C A G M PC_{AGM} PCAGM​的詳細算法實作為：（與Marlin論文中的實作略有不同，

Check

算法中的opening challenge ξ = ρ 0 ( r k , C , z , d , v ) \xi=\rho_0(rk,C,z,d,v) ξ=ρ0​(rk,C,z,d,v) 由random oracle計算獲得，而Marlin中的 ξ \xi ξ是外部輸入（explicit external input）。【實際算法實作與Marlin還是有差異的。】）

• P C A G M . S e t u p PC_{AGM}.Setup PCAGM​.Setup：

  

• P C A G M . T r i m PC_{AGM}.Trim PCAGM​.Trim：生成commitment key c k ck ck 和 receiver key r k rk rk。當比對多個degree為 [ d i ] i = 1 n [d_i]_{i=1}^{n} [di​]i=1n​的多項式時，取degree最大值為 d d d生成（ d = m a x i ∈ [ n ] ( d 1 , ⋯   , d n ) d=max_{i\in[n]}(d_1,\cdots,d_n) d=maxi∈[n]​(d1​,⋯,dn​)）。

  

• P C A G M . C o m m i t PC_{AGM}.Commit PCAGM​.Commit：輸入為commitment key c k ck ck、單變量多項式 p p p、degree bound d d d、commitment randomness ( w , w ∗ ) (w,w^*) (w,w∗)。

  – 1. 從 c k ck ck中擷取所支援的degree bounds [ d i ] i = 1 n [d_i]_{i=1}^{n} [di​]i=1n​。若 d e g ( p ) > d deg(p)>d deg(p)>d或者 d ∉ [ d i ] i = 1 n d\notin [d_i]_{i=1}^{n} d∈/​[di​]i=1n​，則abort；否則繼續。

  – 2. 若随機數 w , w ∗ w,w^* w,w∗不為空，則計算degree 為 d e g ( p ) deg(p) deg(p)的随機單變量多項式 p ˉ \bar{p} pˉ​和 p ˉ ∗ \bar{p}^* pˉ​∗；否則，設定 p ˉ \bar{p} pˉ​和 p ˉ ∗ \bar{p}^* pˉ​∗為zero polynomial。

  – 3. 計算unshifted commitment U = p ( β ) G + p ˉ ( β ) γ G U=p(\beta)G+\bar{p}(\beta)\gamma G U=p(β)G+pˉ​(β)γG 和 shifted commitment S = β D − d p ( β ) G + p ˉ ∗ γ G S=\beta^{D-d}p(\beta)G+\bar{p}^*\gamma G S=βD−dp(β)G+pˉ​∗γG。

  – 4. 輸出為： C = ( U , S ) C=(U,S) C=(U,S)。注意其中 U , S U,S U,S都是由 c k ck ck中的元素線性計算獲得。

• P C A G M . O p e n PC_{AGM}.Open PCAGM​.Open：輸入為commitment key c k ck ck、單變量多項式 p p p、a commitment C C C to p p p、degree bound d d d、evaluation point z z z、commitment randomness ( w , w ∗ ) (w,w^*) (w,w∗)。

  – 1. 1. 從 c k ck ck中擷取所支援的degree bounds [ d i ] i = 1 n [d_i]_{i=1}^{n} [di​]i=1n​。若 d e g ( p ) > d deg(p)>d deg(p)>d或者 d ∉ [ d i ] i = 1 n d\notin [d_i]_{i=1}^{n} d∈/​[di​]i=1n​，則abort；否則繼續。

  – 2. 若随機數 w , w ∗ w,w^* w,w∗不為空，則擷取degree 為 d e g ( p ) deg(p) deg(p)的随機單變量多項式 p ˉ \bar{p} pˉ​和 p ˉ ∗ \bar{p}^* pˉ​∗；否則，設定 p ˉ \bar{p} pˉ​和 p ˉ ∗ \bar{p}^* pˉ​∗為zero polynomial。

  – 3. 計算evaluation v = p ( z ) v=p(z) v=p(z) 和 opening challenge ξ = ρ 0 ( r k , C , z , d , v ) ∈ F q \xi=\rho_0(rk,C,z,d,v)\in\mathbb{F}_q ξ=ρ0​(rk,C,z,d,v)∈Fq​。

  – 4. 定義多項式 p ∗ ( X ) = X D − d p ( X ) − X D − d p ( z ) p^*(X)=X^{D-d}p(X)-X^{D-d}p(z) p∗(X)=XD−dp(X)−XD−dp(z)，計算witness 多項式 w ( X ) = p ( X ) − p ( z ) X − z w(X)=\frac{p(X)-p(z)}{X-z} w(X)=X−zp(X)−p(z)​ for p p p，計算witness polynomial w ∗ ( X ) = X D − d w ( X ) w^*(X)=X^{D-d}w(X) w∗(X)=XD−dw(X) for p ∗ p^* p∗。将這兩個witness結合為 w ′ = w + ξ w ∗ w'=w+\xi w^* w′=w+ξw∗。

  – 5. 計算witness 多項式 w ˉ ( X ) = p ˉ ( X ) − p ˉ ( z ) X − z \bar{w}(X)= \frac{\bar{p}(X)-\bar{p}(z)}{X-z} wˉ(X)=X−zpˉ​(X)−pˉ​(z)​ for p ˉ \bar{p} pˉ​，計算witness 多項式 w ˉ ∗ ( X ) = p ˉ ∗ ( X ) − p ˉ ∗ ( z ) X − z \bar{w}^*(X)= \frac{\bar{p}^*(X)-\bar{p}^*(z)}{X-z} wˉ∗(X)=X−zpˉ​∗(X)−pˉ​∗(z)​ for p ˉ ∗ \bar{p}^* pˉ​∗。将這兩個witness結合為 w ˉ ′ = w ˉ + ξ w ˉ ∗ \bar{w}'=\bar{w}+\xi \bar{w}^* wˉ′=wˉ+ξwˉ∗。

  – 6. 計算evaluation v ˉ = p ˉ ( z ) + ξ p ˉ ∗ ( z ) \bar{v}=\bar{p}(z)+\xi\bar{p}^*(z) vˉ=pˉ​(z)+ξpˉ​∗(z)。

  – 7. 計算 W = w ′ ( β ) G + w ˉ ′ ( β ) γ G W=w'(\beta)G+\bar{w}'(\beta)\gamma G W=w′(β)G+wˉ′(β)γG。

  – 8. 輸出的evaluation proof 為： π = ( W , v ˉ ) \pi=(W,\bar{v}) π=(W,vˉ)。

• P C A G M . C h e c k PC_{AGM}.Check PCAGM​.Check：輸入為commitment key r k rk rk、a commitment C C C t、degree bound d d d、evaluation point z z z、a claimed evaluation v v v、a evaluation proof π \pi π。

  – 1. 若 d ∉ r k d\notin rk d∈/​rk，則abort；否則繼續。

  – 2. 解析commitment C C C 為 ( U , S ) ∈ G 1 2 (U,S)\in \mathbb{G}_1^2 (U,S)∈G12​。

  – 3. 解析 proof π \pi π 為 ( W , v ˉ ) ∈ G 1 × F q (W,\bar{v})\in\mathbb{G}_1\times\mathbb{F}_q (W,vˉ)∈G1​×Fq​。

  – 4. 計算opening challenge ξ = ρ 0 ( r k , C , z , d , v ) ∈ F q \xi=\rho_0(rk,C,z,d,v)\in\mathbb{F}_q ξ=ρ0​(rk,C,z,d,v)∈Fq​。

  – 5. 計算combined commitment C ′ = U + ξ S C'=U+\xi S C′=U+ξS。

  – 6. 驗證 e ( C ′ − v G − v ξ β D − d G − v ˉ γ G , H ) = e ( W , β H − z H ) e(C'-vG-v\xi\beta^{D-d}G-\bar{v}\gamma G,H)=e(W,\beta H-zH) e(C′−vG−vξβD−dG−vˉγG,H)=e(W,βH−zH) 是否成立。

2 技術要點

2.1 PCD from arguments with accumulation schemes

[BCTV14; COS20] 在每一步 i i i，證明 “ z i = F ( z i − 1 ) z_i=F(z_{i-1}) zi​=F(zi−1​)，且存在proof π i − 1 \pi_{i-1} πi−1​ 可證明 z i − 1 z_{i-1} zi−1​的正确性”。為了保證Verifier驗證proof的複雜度低于直接進行相應計算，關注重點在于實作succinct verification。

succinct verification似乎是個沖突的需求：Verifier沒有時間來讀取整個circuit R R R。解決該問題的辦法之一是借助preprocessing：在recursion開始時，為 R R R計算一個短的cryptographic digest，recursive Verifier可用該digest而不用直接讀取整個circuit R R R。對于固定的circuit R R R，這種preprocessing 僅需offline 執行一次，對後續online phase中的each recursive step的性能影響可忽略。

僅有preprocessing還不夠，[BGH19] Bowe等人2019年論文《Halo: Recursive Proof Composition without a Trusted Setup》中引入了 post-processing 技術，基于以下發現：

if a SNARK is such that we can efficiently “defer” the verification of a claim in a way that does not grow in cost with the number of claims to be checked, then we can hope to achieve recursive composition by deferring the verification of all claims to the end。

本文建構的基于SNARKs的PCD算法具有post-processing屬性。

本文的accumulation scheme在 [BGH19] Bowe等人2019年論文《Halo: Recursive Proof Composition without a Trusted Setup》的基礎上進行generalization，主要包括3組算法：

• accumulation prover。輸入為：an instance-proof pair ( z , π ) (z,\pi) (z,π)和a previous accumulator a c c acc acc；輸出為：new accumulator a c c ∗ acc^* acc∗ that “includes” the new instance。
• accumulation verifier。輸入為 ( ( z , π ) , a c c , a c c ∗ ) ((z,\pi),acc,acc^*) ((z,π),acc,acc∗)，然後驗證 a c c ∗ acc^* acc∗計算正确（i.e., that it accumulates ( z , π ) (z,\pi) (z,π) into a c c acc acc）。
• decider。輸入為：a single accumulator a c c acc acc，然後perform a single check that simultaneously ensures that every instance-proof pair accumulated in a c c acc acc verifies。

基于以上accumulation scheme，可建構IVC：

• IVC prover。輸入為：previous instance z i z_i zi​, proof π i \pi_i πi​和accumulator a c c i acc_i acci​。IVC prover首先accumulate ( z i , π i ) (z_i,\pi_i) (zi​,πi​) with a c c i acc_i acci​ to obtain a new accumulator a c c i + 1 acc_{i+1} acci+1​；生成 a SNARK proof π i + 1 \pi_{i+1} πi+1​ of the claim: " z i + 1 = F ( z i ) z_{i+1}=F(z_i) zi+1​=F(zi​), and there exist a proof π i \pi_i πi​ and an accumulator a c c i acc_i acci​ such that the accmulation verifier accepts ( ( z i , π i ) , a c c i , a c c i + 1 ) ((z_i,\pi_i), acc_i, acc_{i+1}) ((zi​,πi​),acci​,acci+1​)", expressed as a circuit R R R。

  最終的IVC proof包含 ( π T , a c c T ) (\pi_T,acc_T) (πT​,accT​)。

• IVC verifier。通過running the SNARK verifier on π T \pi_T πT​ and the accumulation scheme decider on a c c T acc_T accT​來驗證IVC proof。

以上流程能實作IVC的原因在于：

若 a c c i acc_i acci​ is a valid accumulator (according to the decider) 且 π i \pi_i πi​ is a valid proof，則可說明computation is correct up to the i i i-th step。

若在time T T T都一直成立，則IVC verifier就成功check了整個計算。

注意到，若我們能通過一個an invariant 來證明 “ z i + 1 = F ( z i ) z_{i+1}=F(z_i) zi+1​=F(zi​), π i \pi_i πi​ is a valid proof, and a c c i acc_i acci​ is a valid accumulator”，則可認為 the computation is correct up to step i + 1 i+1 i+1。但是迄今為止我們無法直接實作相應的證明，原因有二：

1）證明 π i \pi_i πi​是一個有效的proof需要證明a statement about the argument verifier, which may not be sublinear；

2）證明 a c c i acc_i acci​是一個有效的accumulator需要證明 a statement about the decider, which may not be sublinear。

是以，與其直接進行證明，我們可以“defer”（推遲）：prover accumulate ( z i , π i ) (z_i,\pi_i) (zi​,πi​) into a c c i acc_i acci​ to obtain a new accumulator a c c i + 1 acc_{i+1} acci+1​。

這種accumulation scheme的soundness可保證，若 a c c i + 1 acc_{i+1} acci+1​是有效的且accumulation verfier accepts ( ( z i , π i ) , a c c i , a c c i + 1 ) ((z_i,\pi_i), acc_i, acc_{i+1}) ((zi​,πi​),acci​,acci+1​)，則 π i \pi_i πi​是一個有效的proof且 a c c i acc_i acci​是一個有效的accumulator。剩下的就是要找到相應的invariant，使得prover能用于prove that the accumulation verifer accepts，同時可實作sublinear accumulation verifier。

PCD是IVC的generalization，與IVC每次計算步驟中隻接收一個input z i z_i zi​不同，PCD支援接收 m m m個inputs from different nodes。

PCD中證明正确性，要求證明所有的inputs都被正确計算了。

本文建構的PCD支援check m m m proofs and m m m accumulators。是以，需要拓展上述accumulation scheme的定義，以允許 accmulate 多個 instance-proof pairs和多個 “old” accumulators。

本文建構的PCD具有如下屬性：

• 滿足效率要求。要求accumulation verifier run in time sublinear in the size of the circuit R R R，這就意味着 an accumulator must be of size sublinear in the size of R R R，不能随着每次accumulation step 增長。而 the SNARK verifier和decider algorithm均隻需要有正常的運作效率即可（如，polynomial-time）。
• Soundness。若底層的SNARK is knowledge sound 和 accumulation scheme is sound，則本文的PCD scheme也是sound的。本文強調這兩種情況都是secure in the standard (CRS) model without any random orcales (as in prior PCD constructions)。
• Zero knowledge。若底層的SNARK和accumulation scheme都是zero knowledge的，則相應的PCD scheme也是zero knowledge的。
• Post-quantum security。若底層的SNARK和accumulation scheme都是post-quantum secure的，則相應的PCD scheme也是post-quantum secure的。

2.2 Accumulation scheme

• accumulation scheme for a predicate 定義：

  

  而accumulation scheme for a SNARK 是 accumulation scheme for a predicate induced by the argument verifier，上圖中的predicate input q q q 包含 an instance-proof pair ( x , π ) (x,\pi) (x,π)。

  對于IVC/PCD，相當于有某個fixed circuit R R R，需要accumulate pairs ( x i , π i ) (x_i,\pi_i) (xi​,πi​)，其中 π i \pi_i πi​是a SNARK proof，證明存在 w i w_i wi​使得 R ( x i , w i ) = 1 R(x_i,w_i)=1 R(xi​,wi​)=1。此時，predicate依賴的要素有：

  – pair ( x i , π i ) (x_i,\pi_i) (xi​,πi​)

  – circuit R R R

  – public parameters of the argument scheme p p pp pp

  – random oracle ρ \rho ρ

  circuit R R R 不能是input q q q 的一部分，因為其太大的，是以circuit R R R必須在一開始就fixed。

  需要同時定義：

  – a predicate Φ : U ( ∗ ) × ( { 0 , 1 } ∗ ) 3 → { 0 , 1 } \Phi:\mathcal{U}(*)\times(\{0,1\}^*)^3\rightarrow \{0,1\} Φ:U(∗)×({0,1}∗)3→{0,1}

  – a predicate-specification algorithm H \mathcal{H} H

  調整2.1定義中的predicate為 Φ ( ρ , p p Φ , i Φ , ⋅ ) \Phi(\rho,pp_{\Phi},i_{\Phi},\cdot) Φ(ρ,ppΦ​,iΦ​,⋅)，其中 ρ \rho ρ為a random oracle， p p Φ pp_{\Phi} ppΦ​為output by H ρ \mathcal{H}^{\rho} Hρ， i Φ i_{\Phi} iΦ​為chosen adversarially。

  在本文的SNARK中， H \mathcal{H} H相當于the SNARK generator， i Φ i_{\Phi} iΦ​為circuit R R R，且 Φ ( ρ , p p , R , ( x , π ) ) = V ρ ( p p , R , x , π ) \Phi(\rho,pp,R,(x,\pi))=\mathcal{V}^{\rho}(pp,R,x,\pi) Φ(ρ,pp,R,(x,π))=Vρ(pp,R,x,π)。

• zero knowledge accumulation scheme：

  

Maller等人2019年論文《Sonic: Zero-Knowledge SNARKs from Linear-Size Universal and Updateable Structured Reference Strings》中提出了“helped verification”定義（即支援batch verification？），在具有helped verification 的SNARK中，an untrusted party known as the helper can, given n n n proofs, produce an auxiliary proof that enables checking the n n n proofs at lower cost than that of checking each proof individually。這種batching 能力可看成是accumulation的特例，as it applies to n n n “fresh” proofs only; there is no notion of batching “old” accumulators。目前不清晰僅靠helped verification 是否足以建構IVC/PCD schemes。

2.3 建構arguments with accumulation schemes

• predicate-efficient SNARKs：

  

  近期的一些SNARK都可看成是predicate-efficient with respect to a “polynomial commitment” predicate：[MBKM19; GWC19; CHMMVW20]

  – Maller等人2019年論文《Sonic: Zero-Knowledge SNARKs from Linear-Size Universal and Updateable Structured Reference Strings》

  – Gabizon等人2019年論文《PLONK: Permutations over Lagrange-bases for Oecumenical Noninteractive arguments of Knowledge》

  – Chiesa等人2020年論文《Marlin: Preprocessing zkSNARKs with Universal and Updatable SRS》

2.4 accumulation schemes for polynomial commitments

polynomial commitment scheme (PC scheme) 定義為：

one produce a commitment C C C to a polynomial p p p，然後證明該committed polynomial evaluates to a claimed value v v v at a desired point z z z。

相應的an accumulation scheme for a PC scheme為：

accmulates claims of the form " C C C commits to p p p such that p ( z ) = v p(z)=v p(z)=v" for arbitrary polynomials p p p and evaluation points z z z。

基于目前流行的兩種 (hiding） polynomial commitment scheme建構的 (zero knowledge) accumulation scheme為：

• P C D L PC_{DL} PCDL​：基于security of discrete logarithm的，相關的研究成果有：[BCCGP16; BBBPWM18; WTSTW18] [BMMV19]

  – Bootle等人2016年論文《Efficient Zero-Knowledge Arguments for Arithmetic Circuits in the Discrete Log Setting》，參見部落格 Efficient Zero-Knowledge Arguments for Arithmetic Circuits in the Discrete Log Setting學習筆記。

  – B¨unz等人2018年論文《Bulletproofs: Short Proofs for Confidential Transactions and More》，參見部落格 Bulletproofs: Short Proofs for Confidential Transactions and More學習筆記。

  – Wahby等人2018年論文《Doubly-Efficient zkSNARKs Without Trusted Setup》，參見部落格 Doubly-Efficient zkSNARKs Without Trusted Setup學習筆記。

  – Benedikt Bünz 等人（standford,ethereum,berkeley） 2019年論文《Proofs for Inner Pairing Products and Applications》。參見部落格 Proofs for Inner Pairing Products and Applications 學習筆記。

• P C A G M PC_{AGM} PCAGM​：基于knowledge assumption in bilinear groups，相關的研究成果有：[KZG10; CHMMVW20]

  – Kate等人2010年論文《Constant-Size Commitments to Polynomials and Their Applications》

  – Chiesa等人2020年論文《Marlin: Preprocessing zkSNARKs with Universal and Updatable SRS》

無論是基于哪種 polynomial commitment scheme建構的accumulation scheme，accumulation verifier的running time都是sublinear in the degree of the polynomial，而accumulator本身并不會随着accumulation steps數量增加而增長。

2.4.1 基于 P C D L PC_{DL} PCDL​建構的accumulation scheme

對于degree小于 d d d的單變量多項式， P C D L PC_{DL} PCDL​的evaluation proof size 為 O ( λ log ⁡ d ) O(\lambda\log d) O(λlogd) in the random oracle model。 P C D L PC_{DL} PCDL​基于的安全假設為：the hardness of the discrete logarithm problem in a prime order group G \mathbb{G} G，這就使得 P C D L PC_{DL} PCDL​的參數中沒有secret資訊，即沒有有毒垃圾。

但是 P C D L PC_{DL} PCDL​的verification complexity很高：驗證an evaluation proof需要 Ω ( d ) \Omega (d) Ω(d)個scalar multiplications in G \mathbb{G} G。[BGH19] Bowe等人2019年論文《Halo: Recursive Proof Composition without a Trusted Setup》通過實作a batch of n n n proofs的攤銷相應的verification complexity。

接下來将介紹Halo中對 P C D L PC_{DL} PCDL​的accumulation scheme，其accumulation verifier僅需 O ( n log ⁡ d ) O(n\log d) O(nlogd)個scalar multiplications而不是直接的 Θ ( n ⋅ d ) \Theta (n\cdot d) Θ(n⋅d)，accumulator size為 O ( log ⁡ d ) O(\log d) O(logd) elements in G \mathbb{G} G。

public parameter： { G 0 , G 1 , ⋯   , G d } ∈ G d + 1 \{G_0,G_1,\cdots,G_d\}\in\mathbb{G}^{d+1} {G0​,G1​,⋯,Gd​}∈Gd+1 in a group G \mathbb{G} G of prime order q q q。

角色：committer和receiver。

committer：對polynomial p ( X ) = ∑ i = 0 d a i X i ∈ F q ≤ d [ X ] p(X)=\sum_{i=0}^{d}a_iX^i\in\mathbb{F}_q^{\leq d}[X] p(X)=∑i=0d​ai​Xi∈Fq≤d​[X]進行commit，相應的commitment值為： C = ∑ i = 0 d a i G i C=\sum_{i=0}^{d}a_iG_i C=∑i=0d​ai​Gi​

為了證明the committed polynomial p p p evaluates to v v v at a given point z ∈ F q z\in\mathbb{F}_q z∈Fq​，相當于證明 ( C , z , v ) (C,z,v) (C,z,v)滿足如下 N P NP NP statement：

∃ a 0 , ⋯   , a d ∈ F   s . t .   v = ∑ i = 0 d a i z i   a n d   C = ∑ i = 0 d a i G i \exists a_0,\cdots,a_d\in\mathbb{F}\ s.t.\ v=\sum_{i=0}^{d}a_iz^i\ and\ C=\sum_{i=0}^{d}a_iG_i ∃a0​,⋯,ad​∈F s.t. v=∑i=0d​ai​zi and C=∑i=0d​ai​Gi​

以上可看成是一種特殊inner product argument (IPA)，receiver僅需verify the inner product argument to check the evaluation。[BCCGP16] Bootle等人2016年論文《Efficient Zero-Knowledge Arguments for Arithmetic Circuits in the Discrete Log Setting》是prove the inner product of two committed vectors。不過此處與[BCCGP16]論文中的inner product argument實作略有不同，其中的向量 ( 1 , z , ⋯   , z d ) (1,z,\cdots,z^d) (1,z,⋯,zd)為public info，verifier也知道。是以相應的算法需做調整。

本文所實作的accumulation scheme依賴于一種特殊結構的IPA verifier，該IPA verifier具有如下特點：

• 使用random oracle生成 O ( log ⁡ d ) O(\log d) O(logd)個challenges；
• 運作僅需 O ( log ⁡ d ) O(\log d) O(logd)次field 和group operations的cheap checks ；
• 最終運作需要 Ω d \Omega{d} Ωd次scalar multiplications的expensive check。該check可保證consistency between the challenges and a group element U U U contained in the proof。

以上這種IPA verifier簡明扼要地阻止了expensive check，是以為該IPA建構accumulation scheme reduce為了 為包含 U U U的expensive check建構accumulation scheme。

本文基于[BGH19] Bowe等人2019年論文《Halo: Recursive Proof Composition without a Trusted Setup》中的思路：（而Halo又是基于[BBBPWM18] B¨unz等人2018年論文《Bulletproofs: Short Proofs for Confidential Transactions and More》）

• ξ 1 , ⋯   , ξ log ⁡ 2 d \xi_1,\cdots,\xi_{\log_2d} ξ1​,⋯,ξlog2​d​為protocol challenges；
• U U U 可看成是對polynomial h ( X ) = ∏ i = 0 log ⁡ 2 ( d ) − 1 ( 1 + ξ log ⁡ 2 ( d ) − i X 2 i ) ∈ F q ≤ d [ X ] h(X)=\prod_{i=0}^{\log_2(d)-1}(1+\xi_{\log_2(d)-i}X^{2^i})\in\mathbb{F}_q^{\leq d}[X] h(X)=∏i=0log2​(d)−1​(1+ξlog2​(d)−i​X2i)∈Fq≤d​[X]的commitment，該polynomial具有的特殊屬性為：可evaluated at any point in just O ( log ⁡ d ) O(\log d) O(logd) field operations (exponentially smaller than its degree d d d)。進而就運作将expensive check on U U U 轉換為 a check that is amenable to bathching：不再直接驗證 U U U is a commitment to h h h，改為驗證 the polynomial committed inside U U U agrees with h h h at a challenge point z z z sampled via the random oracle。

利用以上思路，轉為實作：

有多個polynomials p 1 , ⋯   , p n p_1,\cdots,p_n p1​,⋯,pn​，需要有 n n n checks of the form “check that the polynomial contained in U i U_i Ui​ evaluates to h i ( z ) h_i(z) hi​(z) at the point z z z”。由于此處針對的相同的evaluation point z z z，是以可以利用标準的同态屬性進行accumulate。

需要accumulated的instance為：

• ( C , z , v , π ) (C,z,v,\pi) (C,z,v,π)，其中 π \pi π為an evaluation proof for the claim “p(z)=v” and p p p is the polynomial committed in C C C。

具體的accumulation scheme for P C D L PC_{DL} PCDL​ A S = ( P , V , D ) AS=(P,V,D) AS=(P,V,D)實作方式為：

• Accumulation prover P P P：根據old accumulator a c c = ( C 1 , z 1 , v 1 , π 1 ) acc=(C_1,z_1,v_1,\pi_1) acc=(C1​,z1​,v1​,π1​)和instance ( C 2 , z 2 , v 2 , π 2 ) (C_2,z_2,v_2,\pi_2) (C2​,z2​,v2​,π2​) 計算 new accumulator a c c ∗ = ( C , z , v , π ) acc^*=(C,z,v,\pi) acc∗=(C,z,v,π)：

  – 分别從 π 1 , π 2 \pi_1,\pi_2 π1​,π2​計算 U 1 , U 2 U_1,U_2 U1​,U2​， U 1 , U 2 U_1,U_2 U1​,U2​可看成是commitment to polynomials h 1 , h 2 h_1,h_2 h1​,h2​ defined by the challenges derived from π 1 , π 2 \pi_1,\pi_2 π1​,π2​。

  – 使用random oracle ρ \rho ρ 來計算random challenge： α = ρ ( [ h 1 , U 1 ] , [ h 2 , U 2 ] ) \alpha=\rho([h_1,U_1],[h_2,U_2]) α=ρ([h1​,U1​],[h2​,U2​])。

  – 計算 C = U 1 + α U 2 C=U_1+\alpha U_2 C=U1​+αU2​，為commitment to polynomial p ( X ) = h 1 ( X ) + α h 2 ( X ) p(X)=h_1(X)+\alpha h_2(X) p(X)=h1​(X)+αh2​(X)。

  – 計算challenge point： z = ρ ( C , p ) z=\rho(C,p) z=ρ(C,p)，其中 p p p為uniquely represented via the tuple ( [ h 1 , h 2 ] , α ) ([h_1,h_2],\alpha) ([h1​,h2​],α)。

  – 建構an evaluation proof π \pi π for the claim “ p ( z ) = v p(z)=v p(z)=v”。（該步驟是唯一expensive的一步）

  – 輸出新的accumulator a c c ∗ = ( C , z , v , π ) acc^*=(C,z,v,\pi) acc∗=(C,z,v,π)。

• Accumulation verifier V V V：驗證new accumulator a c c ∗ = ( C , z , v , π ) acc^*=(C,z,v,\pi) acc∗=(C,z,v,π)确實是由ld accumulator a c c = ( C 1 , z 1 , v 1 , π 1 ) acc=(C_1,z_1,v_1,\pi_1) acc=(C1​,z1​,v1​,π1​)和instance ( C 2 , z 2 , v 2 , π 2 ) (C_2,z_2,v_2,\pi_2) (C2​,z2​,v2​,π2​) 正确計算而來的。

  – 分别驗證 ( C 1 , z 1 , v 1 , π 1 ) (C_1,z_1,v_1,\pi_1) (C1​,z1​,v1​,π1​)和 ( C 2 , z 2 , v 2 , π 2 ) (C_2,z_2,v_2,\pi_2) (C2​,z2​,v2​,π2​) pass the cheap checks of the IPA verifier。

  – 分别從 π 1 , π 2 \pi_1,\pi_2 π1​,π2​計算 U 1 , U 2 U_1,U_2 U1​,U2​， U 1 , U 2 U_1,U_2 U1​,U2​可看成是commitment to polynomials h 1 , h 2 h_1,h_2 h1​,h2​ defined by the challenges derived from π 1 , π 2 \pi_1,\pi_2 π1​,π2​。

  – 使用random oracle ρ \rho ρ 來計算random challenge： α = ρ ( [ h 1 , U 1 ] , [ h 2 , U 2 ] ) \alpha=\rho([h_1,U_1],[h_2,U_2]) α=ρ([h1​,U1​],[h2​,U2​])。

  – 驗證 C = U 1 + α U 2 C=U_1+\alpha U_2 C=U1​+αU2​ 成立。

  – 計算challenge point： z = ρ ( C , p ) z=\rho(C,p) z=ρ(C,p)，其中polynomial p ( X ) = h 1 ( X ) + α h 2 ( X ) p(X)=h_1(X)+\alpha h_2(X) p(X)=h1​(X)+αh2​(X)。

  – 驗證 h 1 ( z ) + α h 2 ( z ) = v h_1(z)+\alpha h_2(z)=v h1​(z)+αh2​(z)=v成立。

• Decider D D D：輸入為最終的accumulator a c c ∗ = ( C , z , v , π ) acc^*=(C,z,v,\pi) acc∗=(C,z,v,π)，驗證 π \pi π為a valid evaluation proof for the claim that the polynomial committed inside C C C evaluates to v v v at the point z z z。

為了在以上accumulation scheme for P C D L PC_{DL} PCDL​中增加zero knowledge 屬性，即需要引入hiding variant of P C D L PC_{DL} PCDL​：在每一步，accumulation prover需要引入新的random polynomial h 0 h_0 h0​，進而保證the evaluation claim in a c c ∗ acc^* acc∗ is for a random polynomial，進而hiding all information about the original evaluation claims。而為了讓accumulation verifier可驗證通過，prover 需為 h 0 h_0 h0​引入相應的輔助proof π V \pi_V πV​。

2.4.2 基于 P C A G M PC_{AGM} PCAGM​建構的Accumulation scheme

P C A G M PC_{AGM} PCAGM​：基于knowledge assumption in bilinear groups 建構的polynomial commitment scheme。

checking an evaluation proof in P C A G M PC_{AGM} PCAGM​ 需要1個pairing計算，是以驗證 n n n個evaluation proof則需要 n n n個pairing計算。

而accumulation scheme A S = ( P , V , D ) AS=(P,V,D) AS=(P,V,D) for P C A G M PC_{AGM} PCAGM​ 對此進行了改進：

驗證accumulation of n n n個evaluation proofs時，accumulation verifier V V V 僅需 O ( n ) O(n) O(n)次scalar multiplications in G 1 \mathbb{G}_1 G1​ ，而decider D D D僅需要運作1次pairing計算來驗證the resulting accumulator。

将pairing計算次數由 n n n降為 1 1 1，同時将single pairing計算推遲到了the end of the accumulation (the decider)。若将 P C A G M PC_{AGM} PCAGM​-based SNARK和accumulation scheme for P C A G M PC_{AGM} PCAGM​結合，則可消除所有的pairings計算from the circuit being verified in the PCD construction。

[CHMMVW20] Chiesa等人2020年論文《Marlin: Preprocessing zkSNARKs with Universal and Updatable SRS》中介紹了如何利用random linear combination來batching pairings，進而實作an accumulation scheme for P C A G M PC_{AGM} PCAGM​。

借助1.6節的表示，即需要驗證 n n n個instance [ C i , z i , v i , π i ] i = 1 n [C_i,z_i,v_i,\pi_i]_{i=1}^{n} [Ci​,zi​,vi​,πi​]i=1n​，第 i i i個instance的pairing check方程式表示為：

e ( C i − v i G , H ) = e ( π , β ) ⇔ e ( C i − v i G + z i π i , H ) = e ( π i , β H ) e(C_i-v_iG,H)=e(\pi,\beta) \Leftrightarrow e(C_i-v_iG+z_i\pi_i,H)=e(\pi_i,\beta H) e(Ci​−vi​G,H)=e(π,β)⇔e(Ci​−vi​G+zi​πi​,H)=e(πi​,βH) ……(1)

經過以上轉換，pairing等式左右兩側的 G 2 \mathbb{G}_2 G2​ inputs ( H , β H H,\beta H H,βH) 均于所聲明的資訊無關，進而允許引入random challenge r = ρ ( [ C i , z i , v i , π i ] i = 1 n ) r=\rho([C_i,z_i,v_i,\pi_i]_{i=1}^{n}) r=ρ([Ci​,zi​,vi​,πi​]i=1n​) 進行random linear combination 來 實作batch pairing check，最終combined方程式為：

e ( ∑ i = 1 n r i ( C i − v i G + z i π i ) , H ) = e ( ∑ i = 1 n r i π i , β H ) e(\sum_{i=1}^{n}r^i(C_i-v_iG+z_i\pi_i),H)=e(\sum_{i=1}^{n}r^i\pi_i,\beta H) e(∑i=1n​ri(Ci​−vi​G+zi​πi​),H)=e(∑i=1n​riπi​,βH) ……(2)

以上pairing方程式中包含了：

• accumulated commitment： C ∗ = ∑ i = 1 n r i ( C i − v i G + z i π i ) C^*=\sum_{i=1}^{n}r^i(C_i-v_iG+z_i\pi_i) C∗=∑i=1n​ri(Ci​−vi​G+zi​πi​)
• accumulated proof：$\pi*=\sum_{i=1}{n}r^i\pi_i $

進而引申出accumulation scheme A S AS AS for P C A G M PC_{AGM} PCAGM​的實作為：

A S AS AS 中的accumulator包含a commitment-proof pair ( C ∗ , π ∗ ) (C^*, \pi^*) (C∗,π∗)，decider D D D僅需驗證 e ( C ∗ , H ) = e ( π ∗ , β H ) e(C^*,H)=e(\pi^*,\beta H) e(C∗,H)=e(π∗,βH)是否成立。

觀察公式（1）中，驗證a claimed evaluation ( C , z , v , π ) (C,z,v,\pi) (C,z,v,π) within P C A G M PC_{AGM} PCAGM​ 的有效性 相當于 驗證 the accumulator ( C − v G + z π , π ) (C-vG+z\pi,\pi) (C−vG+zπ,π) is accepted by the decider D D D。

• accumulation prover P P P：輸入為a list of old accumulators [ a c c i ] i = 1 n = [ ( C i ∗ , π i ∗ ) ] i = 1 n [acc_i]_{i=1}^{n}=[(C_i^*,\pi_i^*)]_{i=1}^{n} [acci​]i=1n​=[(Ci∗​,πi∗​)]i=1n​，計算random challenge r = ρ ( [ a c c i ] i = 1 n ) r=\rho([acc_i]_{i=1}^{n}) r=ρ([acci​]i=1n​)，建構 C ∗ = ∑ i = 1 n r i C + i ∗ , π ∗ = ∑ i = 1 n r i π i ∗ C^*=\sum_{i=1}^{n}r^iC+i^*,\pi^*=\sum_{i=1}^{n}r^i\pi_i^* C∗=∑i=1n​riC+i∗,π∗=∑i=1n​riπi∗​，輸出為 a c c ∗ = ( C ∗ , π ∗ ) ∈ G 1 2 acc^*=(C^*,\pi^*)\in\mathbb{G}_1^2 acc∗=(C∗,π∗)∈G12​。
• accumulation verifier V V V：驗證 a c c ∗ acc^* acc∗ accumulates [ a c c i ] i = 1 n [acc_i]_{i=1}^{n} [acci​]i=1n​，invoke P P P and check that its output matches the claimed new accumulator a c c ∗ acc^* acc∗。

為了在以上accumulation scheme for P C A G M PC_{AGM} PCAGM​中增加zero knowledge 屬性，即需要在 a c c ∗ acc^* acc∗中額外引入 對應為random polynomial 的 “old” accumulator，進而statistically hide the accumulated claims。而為了讓accumulation verifier可驗證通過，prover 需為“old” accumulator引入相應的輔助proof π V \pi_V πV​。

3. 相關定義

• indexed relations：

  indexed relation r r r為a set of triples ( i , x , w ) (i,x,w) (i,x,w)，其中 i i i為index， x x x為instance， w w w為witness。

  相應的indexed language L ( R ) L(R) L(R)為：對于 ( i , x ) (i,x) (i,x)，存在witness w w w，使得 ( i , x , w ) ∈ R (i,x,w)\in R (i,x,w)∈R。

  以satisfiable Boolean circuit的indexed relation為例： i i i表示the description of a boolean circuit， x x x為partial assignment to its input wires， w w w為assignment to the remaining wires that makes the circuit to output 0。

• Security parameter 和 random oracle：

  

• non-interactive arguments in the ROM：

  

  

  

• proof-carrying data PCD：（由于目前無法證明基于random oracle model建構的PCD是否安全，本文采用的standard (CRS) model。）

  

  

  

4. accumulation scheme

predicate Φ : U ( ∗ ) × ( { 0 , 1 } ∗ ) 3 → { 0 , 1 } \Phi: \mathcal{U}(*)\times (\{0,1\}^*)^3\rightarrow \{0,1\} Φ:U(∗)×({0,1}∗)3→{0,1}。

将 Φ ( ρ , p p Φ , i Φ , q ) \Phi(\rho,pp_{\Phi},i_{\Phi},q) Φ(ρ,ppΦ​,iΦ​,q)簡化表示為 Φ ρ ( p p Φ , i Φ , q ) \Phi^{\rho}(pp_{\Phi},i_{\Phi},q) Φρ(ppΦ​,iΦ​,q)。

H \mathcal{H} H為randomized algorithm with access to a (random) oracle，輸出為predicate參數 p p Φ pp_{\Phi} ppΦ​。

accumulation scheme for ( Φ , H ) (\Phi,\mathcal{H}) (Φ,H) 包含的算法有 A S = ( G , I , P , V , D ) AS=(G,I,P,V,D) AS=(G,I,P,V,D)，均使用相同的random oracle ρ \rho ρ，各算法基本語義為：

• Generator：輸入為security parameter λ \lambda λ， G G G samples 然後輸出public parameter p p pp pp。
• Indexer：輸入為public parameter p p pp pp、predicate parameter p p Φ pp_{\Phi} ppΦ​ (由 H \mathcal{H} H生成)、predicate index i Φ i_{\Phi} iΦ​， I I I 确定性地計算輸出triple ( a p k , a v k , d k ) (apk,avk,dk) (apk,avk,dk)，其中 a p k apk apk為accumulator proving key， a v k avk avk 為accumulator verification key， d k dk dk 為decision key。
• Accumulation Prover：輸入為accumulator proving key a p k apk apk、 [ q i ] i = 1 n [q_i]_{i=1}^{n} [qi​]i=1n​和old accumulators [ a c c j ] j = 1 m [acc_j]_{j=1}^{m} [accj​]j=1m​， P P P 輸出new accumulator a c c acc acc 和proof π V \pi_V πV​ 給accumulation verifier。
• Accumulation Verifier：輸入為 accumulator verification key a v k avk avk、 [ q i ] i = 1 n [q_i]_{i=1}^{n} [qi​]i=1n​和accumulator instances [ a c c j ] j = 1 m [acc_j]_{j=1}^{m} [accj​]j=1m​、new accumulator a c c acc acc 和proof π V \pi_V πV​， V V V 輸出a bit indicating whether a c c acc acc correctly accumulates [ q i ] i = 1 n [q_i]_{i=1}^{n} [qi​]i=1n​和 [ a c c j ] j = 1 m [acc_j]_{j=1}^{m} [accj​]j=1m​。
• Decider：輸入為decision key d k dk dk、accumulator a c c acc acc， D D D 輸出a bit indicating whether a c c acc acc is a valid accumulator。

A S = ( G , I , P , V , D ) AS=(G,I,P,V,D) AS=(G,I,P,V,D) 均應具有completeness和soundness屬性。

• accumulation for non-interactive argument system ARG：

  

• accumulation for polynomial commitment scheme PC：

  

4.1 基于accumulation scheme建構的Proof-carrying data

本文建構的PCD在[COS20] Chiesa等人2020年論文《Fractal: Post-Quantum and Transparent Recursive Proofs from Holography》的基礎上進行了改進：

• [COS20]中SNARK prover circuit包含了SNARK verifier circuit；而本文為了使verifier succinct，改為要求SNARK prover包含accumulation verifier circuit。
• PCD proof中包含了a SNARK proof π \pi π和an accumulator a c c acc acc，驗證計算需要running the SNARK verifier on π \pi π and the accumulation scheme decider on a c c acc acc。
• accumulation scheme的安全性與SNARK本身的安全性需結合考慮。要求SNARK remain secure with respect to the auxiliary input distribution induced by the public parameters of the accumulation scheme。

詳細的PCD建構思路為：

4.2 為non-interactive arguments建構accumulation scheme

詳細的建構思路為：

5. accumulation scheme for P C D L PC_{DL} PCDL​

本文主要基于 [BGH19] Bowe等人2019年論文《Halo: Recursive Proof Composition without a Trusted Setup》batch思想，将the expensive check 推遲給decider：

• accumulation verifier V V V僅需 O ( log ⁡ d ) O(\log d) O(logd)次scalar multiplications per accmulation；
• decider D D D需要 O ( d ) O(d) O(d)次scalar multiplications。

是以，驗證 n n n個 evaluation proofs 總共需要 O ( n log ⁡ d + d ) O(n\log d+d) O(nlogd+d)次 scalar multiplications，而如果直接驗證的話需要 Θ ( n ⋅ d ) \Theta(n\cdot d) Θ(n⋅d)。

詳細的accumulation scheme for P C D L PC_{DL} PCDL​ 建構思路為：

6. accumulation scheme for P C A G M PC_{AGM} PCAGM​

主要借鑒了[CHMMVW20] Chiesa等人2020年論文《Marlin: Preprocessing zkSNARKs with Universal and Updatable SRS》中的batch思想。

直接驗證 n n n個 P C A G M PC_{AGM} PCAGM​ evaluation proofs需要 O ( n ) O(n) O(n)個pairings，而若借助accumulation scheme，則：

• Verifier V V V僅需 O ( n ) O(n) O(n)次scalar multiplications in G 1 \mathbb{G}_1 G1​；
• decider D D D需要運作一次pairing計算。

詳細的accumulation scheme for P C A G M PC_{AGM} PCAGM​建構思路為：