多项式承诺Polynomial commitment方案汇总

1. 引言

在这里插入图片描述上图源自 Vitalik 2021年11月博客 Halo and more: exploring incremental verification and SNARKs without pairings。

目前的多项式承诺Polynomial commitment方案主要有：

Kate polynomial commitment：具体可参见Dankrad Feist的介绍 Kate polynomial commitments
Bulletproofs commitment：具体可参见curve25519-dalek团队的介绍 Module bulletproofs:: notes::inner_product_proof
FRI (Fast Reed-Solomon Interactive Oracle Proofs of Proximity)：具体可参见V神的介绍 STARKs, Part II: Thank Goodness It’s FRI-day

其中，Kate polynomial commitment需要用到 elliptic curve pairing。相对来说，FRI更容易理解。

2. Kate多项式承诺

Kate多项式承诺又称KZG承诺，基于pairing曲线构建，满足bilinear属性：在这里插入图片描述详细的Kate多项式承诺方案见Kate等人2010年论文《Constant-Size Commitments to Polynomials and Their Applications》：

3. Bulletproofs多项式承诺

见博客 Halo: Recursive Proof Composition without a Trusted Setup 学习笔记中“3. Polynomial commitments”：假设polynomial p ( X ) p(X) p(X) 的degree bound为 d − 1 d-1 d−1，则：

S e t u p ( 1 λ , d ) Setup(1^{\lambda}, d) Setup(1λ,d)：输出为common reference string σ = ( G , F p , G ⃗ , H ) \sigma=(\mathbb{G},\mathbb{F}_p,\vec{G},H) σ=(G,Fp,G ,H) for group G \mathbb{G} G of prime order p p p， with random G ⃗ ∈ G d \vec{G}\in\mathbb{G}^d G ∈Gd and H ∈ G H\in\mathbb{G} H∈G。
C o m m i t ( σ , p ( X ) ; r ) = < a ⃗ , G ⃗ > + [ r ] H Commit(\sigma,p(X);r)=+[r]H Commit(σ,p(X);r)=+[r]H，其中 r r r为blinding factor， a i ∈ F a_i\in\mathbb{F} ai∈F为多项式 p ( X ) p(X) p(X)的 i i ith degree term 系数， p ( X ) ∈ F p [ X ] p(X)\in\mathbb{F}_p[X] p(X)∈Fp[X]为maximal degree d − 1 d-1 d−1。可将其看成是对多项式系数的Pedersen vector commitment，具有很好的hiding和加法同态属性——对于 ∀ a , b , r , s ∈ F p , p ( X ) , q ( X ) ∈ F p [ X ] \forall a,b,r,s\in\mathbb{F}_p, p(X),q(X)\in\mathbb{F}_p[X] ∀a,b,r,s∈Fp,p(X),q(X)∈Fp[X]，有： [ a ] C o m m i t ( σ , p ( X ) ; r ) + [ b ] C o m m i t ( σ , q ( X ) ; s ) = C o m m i t ( σ , a ⋅ p ( X ) + b ⋅ q ( X ) ; a r + b s ) [a]Commit(\sigma,p(X);r)+[b]Commit(\sigma,q(X);s)=Commit(\sigma,a\cdot p(X)+b\cdot q(X); ar+bs) [a]Commit(σ,p(X);r)+[b]Commit(σ,q(X);s)=Commit(σ,a⋅p(X)+b⋅q(X);ar+bs)
O p e n ( p ( X ) , x ) Open(p(X),x) Open(p(X),x)：输出为 v ∈ F p v\in\mathbb{F}_p v∈Fp。
V e r i f y O p e n ( P , x , v ) VerifyOpen(P,x,v) VerifyOpen(P,x,v)：判断the polynomial contained “inside” the commitment P P P evaluates to v v v at x x x。输出为1表示接受，0表示拒绝。

然后可将 ( S e t u p , O p e n , V e r i f y O p e n ) (Setup,Open,VerifyOpen) (Setup,Open,VerifyOpen)看成是a PSHVZK (perfect special honest-verifier zero knowledge) argument of knowledge for the relation： { ( ( P , x , v ) : ( a ⃗ , r ) ) : P = < a ⃗ , G ⃗ > + [ r ] H ∧ v = < a ⃗ , ( 1 , x , x 2 , ⋯ , x d − 1 ) > } \{((P,x,v):(\vec{a},r)): P=+[r]H\wedge v=\} {((P,x,v):(a ,r)):P=+[r]H∧v=} 以上relation 可用于证明 the polynomial contained “inside” the commitment P P P evaluates to v v v at x x x，甚至 the committed polynomial has maximum degree d − 1 d-1 d−1。

基本信息展开为：

public info： P ∈ G , x , v ∈ F p P\in\mathbb{G},x,v\in\mathbb{F}_p P∈G,x,v∈Fp
private info： a ⃗ ∈ F p n , r ∈ F p \vec{a}\in\mathbb{F}_p^n,r\in\mathbb{F}_p a ∈Fpn,r∈Fp
relation： P = < a ⃗ , G ⃗ > + [ r ] H ∧ v = < a ⃗ , ( 1 , x , x 2 , ⋯ , x d − 1 ) > P=+[r]H\wedge v= P=+[r]H∧v=

详细的思路为：

Verifier：生成随机group element U ∈ G U\in\mathbb{G} U∈G，将 U ∈ G U\in\mathbb{G} U∈G发送给Prover。
Prover和Verifier：都计算 P ′ = P + [ v ] U P'=P+[v]U P′=P+[v]U。
Prover：转为证明Prover知道 a ⃗ ∈ F p d , r , v ′ ∈ F p \vec{a}\in\mathbb{F}_p^d,r,v'\in\mathbb{F}_p a ∈Fpd,r,v′∈Fp，使得 P ′ = < a ⃗ , G ⃗ > + [ r ] H + [ v ′ ] U P'=+[r]H+[v']U P′=+[r]H+[v′]U成立，其中 v ′ = < a ⃗ , ( 1 , x , x 2 , ⋯ , x d − 1 ) > v'= v′=。若Prover无法提前知道 U U U，则 v = v ′ v=v' v=v′成立。【注意，本文的“U”由Verifier在收到commitment P P P之后才提供，Bulletproofs中的也类似，而Hyrax中的dot-product proof protocol中没有做相应约定，存在prover在 P P P中包含 U U U信息，进而伪造证明的情况——a prover with malicious control of P P P would then be able to interfere with the argument by including terms involving U U U in P P P。】（参见博客 Hyrax: Doubly-efficient zkSNARKs without trusted setup学习笔记第4.2节“dot-product proof with Bulletproofs”）

Bulletproofs中实现的基本信息为：（此处的 U U U由Verifier先知道 P = < a ⃗ , G ⃗ > + < b ⃗ , H ⃗ > P=+ P=+后，发送challenge x ∈ F x\in\mathbb{F} x∈F，然后Prover和Verifier重新计算的 U = x U ∈ G U=xU\in\mathbb{G} U=xU∈G。）【非zero-knowledge的inner product argument】

public info：commitment P ′ P' P′，generators G ⃗ , H ⃗ ∈ G d , U ∈ G \vec{G},\vec{H}\in\mathbb{G}^d,U\in\mathbb{G} G ,H ∈Gd,U∈G。
private info： a ⃗ , b ⃗ ∈ F d \vec{a},\vec{b}\in\mathbb{F}^d a ,b ∈Fd。
relation： P ′ = < a ⃗ , G ⃗ > + < b ⃗ , H ⃗ > + [ < a ⃗ , b ⃗ > ] U P'=++[]U P′=++[]U

本文针对的情况是，其中 b ⃗ = ( 1 , x , x 2 , ⋯ , x n − 1 ) \vec{b}=(1,x,x^2,\cdots,x^{n-1}) b =(1,x,x2,⋯,xn−1) 为public info，对Prover和Verifier均已知，所以，此时不再需要 H ⃗ ∈ G d \vec{H}\in\mathbb{G}^d H ∈Gd。根据需要，可额外再引入generator H ∈ G H\in\mathbb{G} H∈G来实现blinding both prover messages and the commitment P ′ P' P′。最终基本信息为：

public info：commitment P ′ P' P′，generators G ⃗ ∈ G d , H , U ∈ G \vec{G}\in\mathbb{G}^d, H, U\in\mathbb{G} G ∈Gd,H,U∈G 和 b ⃗ ∈ F d \vec{b}\in\mathbb{F}^d b ∈Fd。
private info： a ⃗ ∈ F d \vec{a}\in\mathbb{F}^d a ∈Fd和blinding r ∈ F r\in\mathbb{F} r∈F。
relation： P ′ = < a ⃗ , G ⃗ > + r H + [ < a ⃗ , b ⃗ > ] U P'=+rH+[]U P′=+rH+[]U。

假设 d = 2 k , k > 0 d=2^k,k>0 d=2k,k>0，Prover初始化 G ⃗ ′ = G ⃗ , a ⃗ ′ = a ⃗ , b ⃗ ′ = b ⃗ , P = P ′ \vec{G}'=\vec{G},\vec{a}'=\vec{a},\vec{b}'=\vec{b},P=P' G ′=G ,a ′=a ,b ′=b ,P=P′，然后进行 k k k轮交互，其中 in the j j jth round (starting with j = k j=k j=k and finishing with j = 1 j=1 j=1)： 1）若 d = 1 d=1 d=1，则：【目前有2种实现思路。】 1.1）Hyrax中的思路为：【此时有 P = a ′ G ′ + r H + a ′ b ′ U P=a'G'+rH+a'b'U P=a′G′+rH+a′b′U，其中 a ′ , r ∈ F a',r\in\mathbb{F} a′,r∈F为private info， b ′ ∈ F , G ′ , H , U , P ∈ G b'\in\mathbb{F}, G',H,U,P\in\mathbb{G} b′∈F,G′,H,U,P∈G均为public info。】

Prover：引入Prover私有blinding随机数 d , r δ , r β ← F d,r_{\delta},r_{\beta}\leftarrow\mathbb{F} d,rδ,rβ←F，计算 δ = d G ′ + r δ H , β = d U + r δ H \delta=dG'+r_{\delta}H, \beta=dU+r_{\delta}H δ=dG′+rδH,β=dU+rδH，将 δ , β ∈ G \delta,\beta\in\mathbb{G} δ,β∈G发送给Verifier。
Verifier：发送challenge c ← F c\leftarrow \mathbb{F} c←F 给Prover。
Prover：计算 z 1 = d + c ⋅ a ′ b ′ , z 2 = b ′ ( c ⋅ r + r β ) + r δ z_1=d+c\cdot a'b', z_2=b'(c\cdot r+r_{\beta})+r_{\delta} z1=d+c⋅a′b′,z2=b′(c⋅r+rβ)+rδ，将 z 1 , z 2 ∈ F z_1,z_2\in\mathbb{F} z1,z2∈F发送给Verifier。
Verifier：验证 b ′ ( c P + β ) + δ = z 1 ( G ′ + b ′ U ) + z 2 H b'(cP+\beta)+\delta=z_1(G'+b'U)+z_2H b′(cP+β)+δ=z1(G′+b′U)+z2H是否成立即可。

1.2）本文的思路为（相比于Hyrax方案，proof size少了一个group element G \mathbb{G} G）：【此时有 P = [ a ′ ] G ′ + [ r ] H + [ a ′ b ′ ] U = [ a ′ ] ( G + [ b ′ ] U ) + [ r ] H P=[a']G'+[r]H+[a'b']U=[a'](G+[b']U)+[r]H P=[a′]G′+[r]H+[a′b′]U=[a′](G+[b′]U)+[r]H，其中 a ′ , r ∈ F a',r\in\mathbb{F} a′,r∈F为private info， b ′ ∈ F , G ′ , H , U , P ∈ G b'\in\mathbb{F}, G',H,U,P\in\mathbb{G} b′∈F,G′,H,U,P∈G均为public info。】（其中 ( G + [ b ′ ] U ) (G+[b']U) (G+[b′]U)为public info，可直接用博客基于Sigma protocol实现的零知识证明protocol集锦第2.4节 “2.4 Protocol 4. Knowledge of the opening of Pedersen commitment”来计算。）

Prover：引入Prover私有blinding随机数 d , r δ ← F d,r_{\delta}\leftarrow\mathbb{F} d,rδ←F，计算 δ = d ( G ′ + b ′ U ) + r δ H \delta=d(G'+b'U)+r_{\delta}H δ=d(G′+b′U)+rδH，将 δ ∈ G \delta \in\mathbb{G} δ∈G发送给Verifier。
Verifier：发送challenge c ← F c\leftarrow \mathbb{F} c←F 给Prover。
Prover：计算 z 1 = d + a ′ c , z 2 = r δ + r c z_1=d+a'c, z_2=r_{\delta}+rc z1=d+a′c,z2=rδ+rc，将 z 1 , z 2 ∈ F z_1,z_2\in\mathbb{F} z1,z2∈F发送给Verifier。
Verifier：验证 c P + δ = z 1 ( G ′ + b ′ U ) + z 2 H cP+\delta=z_1(G'+b'U)+z_2H cP+δ=z1(G′+b′U)+z2H是否成立即可。

2）若 d > 1 d>1 d>1，则 j = log ⁡ 2 d , d ′ = d 2 j=\log_2{d}, d'=\frac{d}{2} j=log2d,d′=2d，有：

Prover：计算： d ′ = d / 2 d'=d/2 d′=d/2。引入Prover私有blinding随机数 l j , r j ← F l_j,r_j\leftarrow\mathbb{F} lj,rj←F，计算 L j = < a ⃗ l o ′ , G ⃗ h i ′ > + [ l j ] H + [ < a ⃗ l o ′ , b ⃗ h i ′ > ] U L_j=+[l_j]H+[]U Lj=+[lj]H+[]U， R j = < a ⃗ h i ′ , G ⃗ l o ′ > + [ r j ] H + [ < a ⃗ h i ′ , b ⃗ l o ′ > ] U R_j=+[r_j]H+[]U Rj=+[rj]H+[]U。将 L j , R j ∈ G L_j,R_j\in\mathbb{G} Lj,Rj∈G发送给Verifier。
Verifier：发送random challenge u j ∈ F u_j\in\mathbb{F} uj∈F 给Prover。
Prover：计算： a ⃗ ′ = a ⃗ h i ′ ⋅ u j − 1 + a ⃗ l o ′ ⋅ u j \vec{a}'=\vec{a}'_{hi}\cdot u_j^{-1}+\vec{a}'_{lo}\cdot u_j a ′=a hi′⋅uj−1+a lo′⋅uj r ′ = l j u j 2 + r + r j u j − 2 r'=l_ju_j^2+r+r_ju_j^{-2} r′=ljuj2+r+rjuj−2
Prover和Verifier：计算： b ⃗ ′ = b ⃗ l o ′ ⋅ u j − 1 + b ⃗ h i ′ ⋅ u j \vec{b}'=\vec{b}'_{lo}\cdot u_j^{-1}+\vec{b}'_{hi}\cdot u_j b ′=b lo′⋅uj−1+b hi′⋅uj G ⃗ ′ = G ⃗ l o ′ ⋅ u j − 1 + G ⃗ h i ′ ⋅ u j \vec{G}'=\vec{G}'_{lo}\cdot u_j^{-1}+\vec{G}'_{hi}\cdot u_j G ′=G lo′⋅uj−1+G hi′⋅uj P ′ = [ u j 2 ] L j + P + [ u j − 2 ] R j P'= [u_j^2]L_j+P+ [u_j^{-2}]R_j P′=[uj2]Lj+P+[uj−2]Rj
设置 d = d ′ , P = P ′ , r = r ′ d=d',P=P',r=r' d=d′,P=P′,r=r′，继续从步骤1）开始执行。

在以上证明过程中，关注Prover在每轮递归调用时计算的内容： a ⃗ ′ = a ⃗ h i ′ ⋅ u j − 1 + a ⃗ l o ′ ⋅ u j \vec{a}'=\vec{a}'_{hi}\cdot u_j^{-1}+\vec{a}'_{lo}\cdot u_j a ′=a hi′⋅uj−1+a lo′⋅uj b ⃗ ′ = b ⃗ l o ′ ⋅ u j − 1 + b ⃗ h i ′ ⋅ u j \vec{b}'=\vec{b}'_{lo}\cdot u_j^{-1}+\vec{b}'_{hi}\cdot u_j b ′=b lo′⋅uj−1+b hi′⋅uj G ⃗ ′ = G ⃗ l o ′ ⋅ u j − 1 + G ⃗ h i ′ ⋅ u j \vec{G}'=\vec{G}'_{lo}\cdot u_j^{-1}+\vec{G}'_{hi}\cdot u_j G ′=G lo′⋅uj−1+G hi′⋅uj

与最后一轮 d = 1 d=1 d=1时的 G ′ ∈ G , b ′ ∈ F G'\in\mathbb{G},b'\in\mathbb{F} G′∈G,b′∈F之间的关系为 G ′ = < s ⃗ , G ⃗ > , b ′ = < s ⃗ , b ⃗ > G'=,b'= G′=,b′=，其中 s ⃗ \vec{s} s 为： s ⃗ = ( u 1 − 1 u 2 − 1 ⋯ u k − 1 , u 1 u 2 − 1 ⋯ u k − 1 , u 1 − 1 u 2 ⋯ u k − 1 , u 1 u 2 ⋯ u k − 1 , ⋮ u 1 u 2 ⋯ u k ) \vec{s}=(u_1^{-1}u_2^{-1}\cdots u_k^{-1}, \\ u_1 u_2^{-1}\cdots u_k^{-1}, \\ u_1^{-1}u_2\cdots u_k^{-1},\\ u_1u_2\cdots u_k^{-1},\\ \vdots \\ u_1u_2\cdots u_k) s =(u1−1u2−1⋯uk−1,u1u2−1⋯uk−1,u1−1u2⋯uk−1,u1u2⋯uk−1,⋮u1u2⋯uk)
Verifier在最后一轮收到的commitment P ′ P' P′，满足以下公式： P ′ = ∑ j = 1 k ( [ u j 2 ] L j ) + P + ∑ j = 1 k ( [ u j − 2 ] R j ) P'= \sum_{j=1}^{k}([u_j^2]L_j)+P+ \sum_{j=1}^{k}([u_j^{-2}]R_j) P′=∑j=1k([uj2]Lj)+P+∑j=1k([uj−2]Rj)
Prover在最后一轮的blinding值 r ′ r' r′满足如下公式： r ′ = ∑ j = 1 k ( l j u j 2 ) + r + ∑ j = 1 k ( r j u j − 2 ) r'=\sum_{j=1}^{k}(l_ju_j^2)+r+\sum_{j=1}^{k}(r_ju_j^{-2}) r′=∑j=1k(ljuj2)+r+∑j=1k(rjuj−2)

3.1 Amortization Strategy摊销策略

以上polynomial commitment，尽管其communication complexity为 O ( log ⁡ 2 ( d ) ) O(\log_2(d)) O(log2(d))，其中 d − 1 d-1 d−1为多项式的degree bound，但是Verifier必须在验证时计算 G ′ = < s ⃗ , G ⃗ > , b ′ = < s ⃗ , b ⃗ > G'=,b'= G′=,b′=，其中 s ⃗ = ( u 1 − 1 u 2 − 1 ⋯ u k − 1 , u 1 u 2 − 1 ⋯ u k − 1 , u 1 − 1 u 2 ⋯ u k − 1 , u 1 u 2 ⋯ u k − 1 , ⋮ u 1 u 2 ⋯ u k ) \vec{s}=(u_1^{-1}u_2^{-1}\cdots u_k^{-1}, \\ u_1 u_2^{-1}\cdots u_k^{-1}, \\ u_1^{-1}u_2\cdots u_k^{-1},\\ u_1u_2\cdots u_k^{-1},\\ \vdots \\ u_1u_2\cdots u_k) s =(u1−1u2−1⋯uk−1,u1u2−1⋯uk−1,u1−1u2⋯uk−1,u1u2⋯uk−1,⋮u1u2⋯uk)。

注意，本文针对的情况是 b ⃗ = ( 1 , x , x 2 , ⋯ , x n − 1 ) \vec{b}=(1,x,x^2,\cdots,x^{n-1}) b =(1,x,x2,⋯,xn−1)为public info的情况，其中的 < s ⃗ , b ⃗ > 可看成对多项式：【注意，感觉论文的 g ( X , u 1 , u 2 , ⋯ , u k ) g(X,u_1,u_2,\cdots,u_k) g(X,u1,u2,⋯,uk)公式有点问题，但是作者说木问题。。。】 g ( X , u 1 , u 2 , ⋯ , u k ) = ∏ i = 1 k ( u i − 1 + u i X 2 i − 1 ) g(X,u_1,u_2,\cdots,u_k)=\prod_{i=1}^{k}(u_i^{-1}+u_iX^{2^{i-1}}) g(X,u1,u2,⋯,uk)=∏i=1k(ui−1+uiX2i−1) 在point x x x的evaluation值，即 b ′ = < s ⃗ , b ⃗ > = g ( x , u 1 , u 2 , ⋯ , u k ) b'==g(x,u_1,u_2,\cdots,u_k) b′==g(x,u1,u2,⋯,uk)。Verifier可计算该evaluation值in logarithmic time。但是，对于 G ′ = < s ⃗ , G ⃗ > G'= G′=计算，仍然需要a linear-time multiscalar multiplication。但是仔细观察，可将 G ′ G' G′看成是对多项式 g ( X , u 1 , u 2 , ⋯ , u k ) g(X,u_1,u_2,\cdots,u_k) g(X,u1,u2,⋯,uk)系数的commitment值： G ′ = C o m m i t ( σ , g ( X , u 1 , u 2 , ⋯ , u k ) ) G'=Commit(\sigma, g(X,u_1,u_2,\cdots,u_k)) G′=Commit(σ,g(X,u1,u2,⋯,uk)) 所以与其让Verifier为 m m m个（independent）arguments 自己计算 G i ′ G'_i Gi′，不如将该计算外包给不可信的第三方“helper“ ，”helper”在提供 G 1 ′ , G 2 ′ , ⋯ , G m ′ G_1',G_2',\cdots,G_m' G1′,G2′,⋯,Gm′ (for m m m separate arguments) 计算结果的同时提供相应的argument that each are correct by demonstrating that a random linear combination of the commitments opens at a random point to a value the verifier can compute in time O ( m log ⁡ ( d ) ) O(m\log(d)) O(mlog(d))。基于Schwartz-Zippel Lemma，”helper“可让Verifier信服其结果是正确计算的（其伪造成功的概率不高于 d − 1 p − 1 \frac{d-1}{p-1} p−1d−1）。也就是说，此时，Verifier需调用“helper“运行对 g ( X , u 1 , u 2 , ⋯ , u k ) g(X,u_1,u_2,\cdots,u_k) g(X,u1,u2,⋯,uk)的polynomial commitment opening protocol，最终Verifier仍需要进行一次linear-time operation，但是通过此操作，the verifier has traded m m m linear-time operations for one, with a marginal cost that is logarithmic in the degree bound。

4. FRI多项式承诺

详细见：

STARK入门知识 “第4章 FRI”
Fast Reed-Solomon Interactive Oracle Proofs of Proximity学习笔记

采用基于FRI的compiler可将Polynomial IOP转换为a concrete proof system。

FRI协议用于确认a committed polynomial具有bounded degree。

FRI全称为Fast Reed-Solomon IOP of Proximity，其中IOP表示interactive oracle proof。

FRI采用codewords来表示，Verifier无法读取Prover发来的所有codewords，Verifier会make oracle-queries to read them in select locations。 FRI中的codewords为Reed-Solomon codewords，即其值对应为the evaluation of some low-degree polynomial in a list of points called the domain D D D。该list的length要大于多项式中可能的非零值系数的个数 ρ \rho ρ倍， ρ \rho ρ称为expansion factor（或blowup factor）。【即有：initial_codeword_length = (degree + 1) * expansion_factor】

codewords表示low-degree polynomials。codewords采用merkle tree来实例化。

常规的Polynomial commitment scheme为：

polynomial commitment及实现方式对比

而FRI scheme有所不同。FRI用于证明某codeword属于a polynomial of low degree。所谓low，是指degree 值不高于 ρ ⋅ l e n ( c o d e w o r d ) \rho\cdot len(codeword) ρ⋅len(codeword)。Prover知道codeword具体内容，而Verifier仅知道Merkle root和其选择的leaf。通过authentication path verification来确认the leaf’s membership to the Merkle tree。

proof system中很赞的一个思想是：split-and-fold技术。可：（假设待证明的claim size为 n n n）

1）将a claim reduce为 two claims of half the size。
2）然后利用Verifier提供的random challenge合并为一个claim。
3）重复以上步骤 log ⁡ 2 ( n ) − 1 \log_2(n)-1 log2(n)−1次，可最终reduce为a trivial size claim，其为true 当且仅当原始claim为true。

对于FRI，相应的computational claim为：某特定codeword对应为a polynomial of low degree。令 N N N为codeword length。 d d d为该对应多项式的最大degree，表示为 f ( X ) = ∑ i d c i X i f(X)=\sum_{i}^{d}c_iX^i f(X)=∑idciXi。

根据FFT的divide-and-conquer策略，可将多项式分为奇数项和偶数项表示： f ( X ) = f E ( X 2 ) + X ⋅ f O ( X 2 ) f(X)=f_E(X^2)+X\cdot f_O(X^2) f(X)=fE(X2)+X⋅fO(X2) 其中： f E ( X 2 ) = f ( X ) + f ( − X ) 2 = ∑ i = 0 d + 1 2 − 1 c 2 i X 2 i f_E(X^2)=\frac{f(X)+f(-X)}{2}=\sum_{i=0}^{\frac{d+1}{2}-1}c_{2i}X^{2i} fE(X2)=2f(X)+f(−X)=∑i=02d+1−1c2iX2i f O ( X 2 ) = f ( X ) − f ( − X ) 2 X = ∑ i = 0 d + 1 2 − 1 c 2 i + 1 X 2 i f_O(X^2)=\frac{f(X)-f(-X)}{2X}=\sum_{i=0}^{\frac{d+1}{2}-1}c_{2i+1}X^{2i} fO(X2)=2Xf(X)−f(−X)=∑i=02d+1−1c2i+1X2i

FRI协议的关键是根据codeword for f ( X ) f(X) f(X) 来派生 codeword for f ∗ ( X ) = f E ( X ) + α ⋅ f O ( X ) f^{*}(X)=f_E(X)+\alpha\cdot f_O(X) f∗(X)=fE(X)+α⋅fO(X)。其中 α \alpha α为由Verifier提供的random scalar。

假设 D D D为某multiplicative group的subgroup， D D D 具有even order N N N。令 ω \omega ω为生成subgroup D D D的generator： ⟨ ω ⟩ = D ⊂ F p \ { 0 } \langle \omega \rangle = D \subset \mathbb{F}_p \backslash\lbrace 0\rbrace ⟨ω⟩=D⊂Fp\{0}。令 { f ( ω i ) } i = 0 N − 1 \lbrace f(\omega^i)\rbrace_{i=0}^{N-1} {f(ωi)}i=0N−1 为 f ( X ) f(X) f(X)的codeword，其实对应为evaluation on D D D。

令 D ⋆ = ⟨ ω 2 ⟩ D^\star = \langle \omega^2 \rangle D⋆=⟨ω2⟩ 为另一domain，其length为 D D D的一半。令 { f E ( ω 2 i ) } i = 0 N / 2 − 1 \lbrace f_ E(\omega^{2i})\rbrace_{i=0}^{N/2-1} {fE(ω2i)}i=0N/2−1， { f O ( ω 2 i ) } i = 0 N / 2 − 1 \lbrace f_ O(\omega^{2i})\rbrace_{i=0}^{N/2-1} {fO(ω2i)}i=0N/2−1 和 { f ⋆ ( ω 2 i ) } i = 0 N / 2 − 1 \lbrace f^\star(\omega^{2i})\rbrace_ {i=0}^{N/2-1} {f⋆(ω2i)}i=0N/2−1 分别为 the codewords for f E ( X ) f_E(X) fE(X)， f O ( X ) f_O(X) fO(X) 和 f ⋆ ( X ) f^\star(X) f⋆(X)，其实对应为evaluation on D ⋆ D^\star D⋆。

将 f ⋆ ( X ) f^\star(X) f⋆(X) 的定义扩展为： { f ⋆ ( ω 2 i ) } i = 0 N / 2 − 1 = { f E ( ω 2 i ) + α ⋅ f O ( ω 2 i ) } i = 0 N / 2 − 1 . \lbrace f^\star(\omega^{2i})\rbrace_{i=0}^{N/2-1} = \lbrace f_E(\omega^{2i}) + \alpha \cdot f_O(\omega^{2i})\rbrace_{i=0}^{N/2-1} . {f⋆(ω2i)}i=0N/2−1={fE(ω2i)+α⋅fO(ω2i)}i=0N/2−1.

再次根据 f E ( X 2 ) f_E(X^2) fE(X2) 和 f O ( X 2 ) f_O(X^2) fO(X2) 的定义将 f ⋆ ( X ) f^\star(X) f⋆(X) 扩展为： { f ⋆ ( ω 2 i ) } i = 0 N / 2 − 1 \lbrace f^\star(\omega^{2i})\rbrace_{i=0}^{N/2-1} {f⋆(ω2i)}i=0N/2−1 = { f ( ω i ) + f ( − ω i ) 2 + α ⋅ f ( ω i ) − f ( − ω i ) 2 ω i } i = 0 N / 2 − 1 = \left\lbrace \frac{f(\omega^i) + f(-\omega^i)}{2} + \alpha \cdot \frac{f(\omega^i) - f(-\omega^i)}{2 \omega^i} \right\rbrace_{i=0}^{N/2-1} ={2f(ωi)+f(−ωi)+α⋅2ωif(ωi)−f(−ωi)}i=0N/2−1 = { 2 − 1 ⋅ ( ( 1 + α ⋅ ω − i ) ⋅ f ( ω i ) + ( 1 − α ⋅ ω − i ) ⋅ f ( − ω i ) ) } i = 0 N / 2 − 1 = \lbrace 2^{-1} \cdot \left( ( 1 + \alpha \cdot \omega^{-i} ) \cdot f(\omega^i) + (1 - \alpha \cdot \omega^{-i} ) \cdot f(-\omega^i) \right) \rbrace_{i=0}^{N/2-1} ={2−1⋅((1+α⋅ω−i)⋅f(ωi)+(1−α⋅ω−i)⋅f(−ωi))}i=0N/2−1

由于 ω \omega ω的order为 N N N，因此有 ω N / 2 = − 1 \omega^{N/2}=-1 ωN/2=−1，从而有 f ( − ω i ) = f ( ω N / 2 + i ) f(-\omega^i)=f(\omega^{N/2+i}) f(−ωi)=f(ωN/2+i)。因此，尽管iterate index减半为由 0 0 0到 N / 2 − 1 N/2-1 N/2−1，但是所有的points并未减半，仍为 { f ( ω i ) } i = 0 N − 1 \{f(\omega^i)\}_{i=0}^{N-1} {f(ωi)}i=0N−1。所有的这些points用于派生 { f ⋆ ( ω 2 i ) } i = 0 N / 2 − 1 \lbrace f^\star(\omega^{2i})\rbrace_{i=0}^{N/2-1} {f⋆(ω2i)}i=0N/2−1，尽管派生后的codeword仅有一半length，尽管其polynomial仅有half the degree。

以FRI protocol中的一轮为例：

1）Prover commit to f ( X ) f(X) f(X)：将其codeword { f ( ω i ) } i = 0 N − 1 \lbrace f(\omega^i)\rbrace_{i=0}^{N-1} {f(ωi)}i=0N−1 的merkle root发送给Verifier。
2）Verifier发送challenge α \alpha α。
3）Prover计算并commit to f ⋆ ( X ) f^\star(X) f⋆(X)：将其codeword { f ⋆ ( ω 2 i ) } i = 0 N / 2 − 1 \lbrace f^\star(\omega^{2i})\rbrace_{i=0}^{N/2-1} {f⋆(ω2i)}i=0N/2−1 的merkle root发送给Verifier。
4）Verifier此时有2组polynomial commitments，接下来要验证两者之间的关系是否正确： f ⋆ ( X ) = 2 − 1 ⋅ ( ( 1 + α X − 1 ) ⋅ f ( X ) + ( 1 − α X − 1 ) ⋅ f ( − X ) ) f^\star(X) = 2^{-1} \cdot \left( (1 + \alpha X^{-1}) \cdot f(X) + (1 - \alpha X^{-1} ) \cdot f(-X) \right) f⋆(X)=2−1⋅((1+αX−1)⋅f(X)+(1−αX−1)⋅f(−X)) 为此，Verifier需随机选择一个index i ← R { 0 , … , N / 2 − 1 } i \xleftarrow{R} \lbrace 0, \ldots, N/2-1\rbrace iR {0,…,N/2−1}，【注意，index的选择是与round关联的。如果index的选择与round不相关，则可能会存在fail to catch hybrid codewords的情况。实时上，可在所有轮中复用相同的index，必要时基于codeword length 进行modulo运算。】从而可确定3个point：
- A : ( ω i , f ( ω i ) ) A: (\omega^i, f(\omega^i)) A:(ωi,f(ωi))
- B : ( ω N / 2 + i , f ( ω N / 2 + i ) ) B: (\omega^{N/2+i}, f(\omega^{N/2+i})) B:(ωN/2+i,f(ωN/2+i))
- C : ( α , f ⋆ ( ω 2 i ) ) C: (\alpha, f^\star(\omega^{2i})) C:(α,f⋆(ω2i)) 注意， A 和 B A和B A和B的 x x x坐标为 ω 2 i \omega^{2i} ω2i的平方根。
5）Prover收到Verifier发来的index i i i之后，仅需提供Merkle authentication paths的 y y y坐标。
6）Verifier验证该authentication path与root匹配，同时验证 A , B , C A,B,C A,B,C在同一条直线上（又称为colinearity check）。 colinearity check成立的原因在于：穿过A、B的直线可表示为： y = ∑ i y i ∏ j ≠ i x − x j x i − x j = f ( ω i ) ⋅ x − ω N / 2 + i ω i − ω N / 2 + i + f ( ω N / 2 + i ) ⋅ x − ω i ω N / 2 + i − ω i = f ( ω i ) ⋅ 2 − 1 ⋅ ω − i ⋅ ( x + ω i ) − f ( ω N / 2 + i ) ⋅ 2 − 1 ⋅ ω − i ( x − ω i ) = 2 − 1 ⋅ ( ( 1 + x ⋅ ω − i ) ⋅ f ( ω i ) + ( 1 − x ⋅ ω − i ) ⋅ f ( ω N / 2 + i ) ) . y = \sum_i y_i \prod_{j \neq i} \frac{x - x_j}{x_i - x_j} \\ = f(\omega^i) \cdot \frac{x - \omega^{N/2+i}}{\omega^{i} - \omega^{N/2+i}} + f(\omega^{N/2+i}) \cdot \frac{x - \omega^{i}}{\omega^{N/2+i} - \omega^{i}} \\ = f(\omega^i) \cdot 2^{-1} \cdot \omega^{-i} \cdot (x + \omega^i) - f(\omega^{N/2+i}) \cdot 2^{-1} \cdot \omega^{-i} (x - \omega^i) \\ = 2^{-1} \cdot \left( (1 + x \cdot \omega^{-i}) \cdot f(\omega^i) + (1 - x \cdot \omega^{-i}) \cdot f(\omega^{N/2 + i}) \right) \enspace . y=i∑yij=i∏xi−xjx−xj=f(ωi)⋅ωi−ωN/2+ix−ωN/2+i+f(ωN/2+i)⋅ωN/2+i−ωix−ωi=f(ωi)⋅2−1⋅ω−i⋅(x+ωi)−f(ωN/2+i)⋅2−1⋅ω−i(x−ωi)=2−1⋅((1+x⋅ω−i)⋅f(ωi)+(1−x⋅ω−i)⋅f(ωN/2+i)). 当 x = α x=\alpha x=α时，即有 y = f ⋆ ( ω 2 i ) y= f^\star(\omega^{2i}) y=f⋆(ω2i)，从而说明 C C C也在该直线上。

重复以上round即可。一共需要 log ⁡ 2 ( d + 1 ) − 1 \log_2(d+1)-1 log2(d+1)−1轮，其中 d d d为原始多项式的degree。最终获得的为constant polynomial，其codeword也为constant。最后一轮中，Prover直接将该constant而不是merkle root发送给Verifier即可。在这里插入图片描述

4.1 FRI多项式承诺代码解析

相应的Python伪代码示例为：

1）初始化：

import math
from hashlib import blake2b

class Fri:
    def __init__( self, offset, omega, initial_domain_length, expansion_factor, num_colinearity_tests ):
        self.offset = offset
        self.omega = omega
        self.domain_length = initial_domain_length
        self.field = omega.field
        self.expansion_factor = expansion_factor
        self.num_colinearity_tests = num_colinearity_tests

    def num_rounds( self ):
        codeword_length = self.domain_length
        num_rounds = 0
        while codeword_length > self.expansion_factor and 4*self.num_colinearity_tests

多项式承诺Polynomial commitment方案汇总

最近更新

热门博客

[ 申请 ]友情链接：