多项式承诺Polynomial commitment方案汇总-USB迷|专注于互联网分享

多项式承诺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)=<\vec{a},\vec{G}>+[r]H Commit(σ,p(X);r)=<a ,G >+[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=<\vec{a},\vec{G}>+[r]H\wedge v=<\vec{a},(1,x,x^2,\cdots,x^{d-1})>\} {((P,x,v):(a ,r)):P=<a ,G >+[r]H∧v=<a ,(1,x,x2,⋯,xd−1)>}
以上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=<\vec{a},\vec{G}>+[r]H\wedge v=<\vec{a},(1,x,x^2,\cdots,x^{d-1})> P=<a ,G >+[r]H∧v=<a ,(1,x,x2,⋯,xd−1)>

详细的思路为：

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'=<\vec{a},\vec{G}>+[r]H+[v']U P′=<a ,G >+[r]H+[v′]U成立，其中 v ′ = < a ⃗ , ( 1 , x , x 2 , ⋯ , x d − 1 ) > v'=<\vec{a},(1,x,x^2,\cdots,x^{d-1})> v′=<a ,(1,x,x2,⋯,xd−1)>。若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 ⃗ > + P=<\vec{a},\vec{G}>+<\vec{b},\vec{H}> P=<a ,G >+后，发送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 ⃗ > + + [ < a ⃗ , b ⃗ > ] U P'=<\vec{a},\vec{G}>+<\vec{b},\vec{H}>+[<\vec{a},\vec{b}>]U P′=<a ,G >++[<a ,b >]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'=<\vec{a},\vec{G}>+rH+[<\vec{a},\vec{b}>]U P′=<a ,G >+rH+[<a ,b >]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=<\vec{a}'_{lo},\vec{G}'_{hi}>+[l_j]H+[<\vec{a}'_{lo},\vec{b}'_{hi}>]U Lj=<a lo′,G hi′>+[lj]H+[<a lo′,b hi′>]U， R j = < a ⃗ h i ′ , G ⃗ l o ′ > + [ r j ] H + [ < a ⃗ h i ′ , b ⃗ l o ′ > ] U R_j=<\vec{a}'_{hi},\vec{G}'_{lo}>+[r_j]H+[<\vec{a}'_{hi},\vec{b}'_{lo}>]U Rj=<a hi′,G lo′>+[rj]H+[<a hi′,b lo′>]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'=<\vec{s},\vec{G}>,b'=<\vec{s},\vec{b}> G′=<s ,G >,b′=<s ,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'=<\vec{s},\vec{G}>,b'=<\vec{s},\vec{b}> G′=<s ,G >,b′=<s ,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 ⃗ > <\vec{s},\vec{b}> <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'=<\vec{s},\vec{b}>=g(x,u_1,u_2,\cdots,u_k) b′=<s ,b >=g(x,u1,u2,⋯,uk)。Verifier可计算该evaluation值in logarithmic time。
但是，对于 G ′ = < s ⃗ , G ⃗ > G'=<\vec{s},\vec{G}> G′=<s ,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 < codeword_length:
            codeword_length /= 2
            num_rounds += 1
        return num_rounds

    def eval_domain( self ):
        return [self.offset * (self.omega^i) for i in range(self.domain_length)]

2）证明：

def prove( self, codeword, proof_stream ):
    assert(self.domain_length == len(codeword)), "initial codeword length does not match length of initial codeword"

    # commit phase
    codewords = self.commit(codeword, proof_stream)

    # get indices
    top_level_indices = self.sample_indices(proof_stream.prover_fiat_shamir(), len(codewords[1]), len(codewords[-1]), self.num_colinearity_tests)
    indices = [index for index in top_level_indices]

    # query phase
    for i in range(len(codewords)-1):
        indices = [index % (len(codewords[i])//2) for index in indices] # fold
        self.query(codewords[i], codewords[i+1], indices, proof_stream)

    return top_level_indices

其中Prover在commit阶段包含了多轮，在每一轮中，会：

计算the working codeword的Merkle root；
将该Merkle root发送给Verifier；
Verifier提供随机challenge α \alpha α；
Prover运用split-and-fold共识来派生a codeword for the next round；
Prover对offset g g g和generator ω \omega ω求平方，使得 { g ⋅ ω i ∣ i ∈ Z } \{g\cdot \omega^i|i\in\mathbb{Z}\} {g⋅ωi∣i∈Z}总是对应working codeword的evaluation domain。【为避免与STARK协议中的evaluation domain有交集，此处引入了offset g g g以实现Coset-FRI。】

commit阶段最后一轮运行完成后，Prover仅有一个codeword，将该codeword以明文形式发送给Verifier。最后，Prover需要跟踪每一轮所计算的codewords，以便在Query阶段中可open相应的Merkle tree proof。
详细的commit示例代码为：

 def commit( self, codeword, proof_stream, round_index=0 ):
    one = self.field.one()
    two = FieldElement(2, self.field)
    omega = self.omega
    offset = self.offset
    codewords = []

    # for each round
    for r in range(self.num_rounds()):

        # compute and send Merkle root
        root = Merkle.commit(codeword)
        proof_stream.push(root)

        # prepare next round, if necessary
        if r == self.num_rounds() - 1:
            break

        # get challenge
        alpha = self.field.sample(proof_stream.prover_fiat_shamir())

        # collect codeword
        codewords += [codeword]

        # split and fold
        codeword = [two.inverse() * ( (one + alpha / (offset * (omega^i)) ) * codeword[i] + (one - alpha / (offset * (omega^i)) ) * codeword[len(codeword)//2 + i] ) for i in range(len(codeword)//2)]
        omega = omega^2
        offset = offset^2

    # send last codeword
    proof_stream.push(codeword)

    # collect last codeword too
    codewords = codewords + [codeword]

    return codewords

commit阶段还包含具有相同迭代次数的另一个循环：

A点和B点的x坐标的indices均派生自 C点x坐标的indices，即共用相同的 i i i。
会将indices所指定的codeword值以及相应的authentication paths 发送给Verifier。

具体获取indices见sample_indices函数，基于seed和counter调用blake2b来获得伪随机indices：

def sample_index( byte_array, size ):
    acc = 0
    for b in byte_array:
        acc = (acc << 8) ^ int(b)
    return acc % size

def sample_indices( self, seed, size, reduced_size, number ):
    assert(number <= reduced_size), f"cannot sample more indices than available in last codeword; requested: {number}, available: {reduced_size}"
    assert(number <= 2*reduced_size), "not enough entropy in indices wrt last codeword"

    indices = []
    reduced_indices = []
    counter = 0
    while len(indices) < number:
        index = Fri.sample_index(blake2b(seed + bytes(counter)).digest(), size)
        reduced_index = index % reduced_size
        counter += 1
        if reduced_index not in reduced_indices:
            indices += [index]
            reduced_indices += [reduced_index]

    return indices

Query阶段，为

def query( self, current_codeword, next_codeword, c_indices, proof_stream ):
    # infer a and b indices
    a_indices = [index for index in c_indices]
    b_indices = [index + len(current_codeword)//2 for index in c_indices]

    # reveal leafs
    for s in range(self.num_colinearity_tests):
        proof_stream.push((current_codeword[a_indices[s]], current_codeword[b_indices[s]], next_codeword[c_indices[s]]))

    # reveal authentication paths
    for s in range(self.num_colinearity_tests):
        proof_stream.push(Merkle.open(a_indices[s], current_codeword))
        proof_stream.push(Merkle.open(b_indices[s], current_codeword))
        proof_stream.push(Merkle.open(c_indices[s], next_codeword))

    return a_indices + b_indices

3）验证：Verifier验证过程中：

3.1）从proof stream中读取Merkle roots，借助Fiat-Shamir重构出每轮的random scalar α \alpha α；
3.2）从proof sream中读取最后一轮的codewords，检查其是否与a low degree polynomial匹配，同时检查是否与最后一个Merkle root匹配；
3.3）借助Fiat-Shamir，重构出master list of random indices，然后推断出colinearity checks所需的indices；
3.4）从proof stream中读取Merkle leaves及其authentication paths，并验证their authenticity against the indices；
3.5）为每组相邻codewords运行colinearity checks。

def verify( self, proof_stream, polynomial_values ):
    omega = self.omega
    offset = self.offset

    # extract all roots and alphas
    roots = []
    alphas = []
    for r in range(self.num_rounds()):
        roots += [proof_stream.pull()]
        alphas += [self.field.sample(proof_stream.verifier_fiat_shamir())]

    # extract last codeword
    last_codeword = proof_stream.pull()

    # check if it matches the given root
    if roots[-1] != Merkle.commit(last_codeword):
        print("last codeword is not well formed")
        return False

    # check if it is low degree
    degree = (len(last_codeword) // self.expansion_factor) - 1
    last_omega = omega
    last_offset = offset
    for r in range(self.num_rounds()-1):
        last_omega = last_omega^2
        last_offset = last_offset^2

    # assert that last_omega has the right order
    assert(last_omega.inverse() == last_omega^(len(last_codeword)-1)), "omega does not have right order"

    # compute interpolant
    last_domain = [last_offset * (last_omega^i) for i in range(len(last_codeword))]
    poly = Polynomial.interpolate_domain(last_domain, last_codeword)
    #coefficients = intt(last_omega, last_codeword)
    #poly = Polynomial(coefficients).scale(last_offset.inverse())

    # verify by  evaluating
    assert(poly.evaluate_domain(last_domain) == last_codeword), "re-evaluated codeword does not match original!"
    if poly.degree() > degree:
        print("last codeword does not correspond to polynomial of low enough degree")
        print("observed degree:", poly.degree())
        print("but should be:", degree)
        return False

    # get indices
    top_level_indices = self.sample_indices(proof_stream.verifier_fiat_shamir(), self.domain_length >> 1, self.domain_length >> (self.num_rounds()-1), self.num_colinearity_tests)

    # for every round, check consistency of subsequent layers
    for r in range(0, self.num_rounds()-1):

        # fold c indices
        c_indices = [index % (self.domain_length >> (r+1)) for index in top_level_indices]

        # infer a and b indices
        a_indices = [index for index in c_indices]
        b_indices = [index + (self.domain_length >> (r+1)) for index in a_indices]

        # read values and check colinearity
        aa = []
        bb = []
        cc = []
        for s in range(self.num_colinearity_tests):
            (ay, by, cy) = proof_stream.pull()
            aa += [ay]
            bb += [by]
            cc += [cy]

            # record top-layer values for later verification
            if r == 0:
                polynomial_values += [(a_indices[s], ay), (b_indices[s], by)]
            
            # colinearity check
            ax = offset * (omega^a_indices[s])
            bx = offset * (omega^b_indices[s])
            cx = alphas[r]
            if test_colinearity([(ax, ay), (bx, by), (cx, cy)]) == False:
                print("colinearity check failure")
                return False

        # verify authentication paths
        for i in range(self.num_colinearity_tests):
            path = proof_stream.pull()
            if Merkle.verify(roots[r], a_indices[i], path, aa[i]) == False:
                print("merkle authentication path verification fails for aa")
                return False
            path = proof_stream.pull()
            if Merkle.verify(roots[r], b_indices[i], path, bb[i]) == False:
                print("merkle authentication path verification fails for bb")
                return False
            path = proof_stream.pull()
            if Merkle.verify(roots[r+1], c_indices[i], path, cc[i]) == False:
                print("merkle authentication path verification fails for cc")
                return False

        # square omega and offset to prepare for next round
        omega = omega^2
        offset = offset^2

    # all checks passed
    return True