多项式承诺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)$ 的degree bound为$d-1$，则：

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

然后可将$(Setup,Open,VerifyOpen)$看成是a PSHVZK (perfect special honest-verifier zero knowledge) argument of knowledge for the relation：
$\{((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})>\}$
以上relation 可用于证明 the polynomial contained “inside” the commitment $P$ evaluates to $v$ at $x$，甚至 the committed polynomial has maximum degree $d-1$。

基本信息展开为：

• public info：$P\in \mathbb{G},x,v\in {\mathbb{F}}_p$
• private info：$\vec{a}\in {\mathbb{F}}_p^n,r\in {\mathbb{F}}_p$
• relation：$P=<\vec{a},\vec{G}>+[r]H\wedge v=<\vec{a},(1,x,x^2,\cdots ,x^{d-1})>$

详细的思路为：

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

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

• public info：commitment $P^{\prime }$，generators $\vec{G},\vec{H}\in {\mathbb{G}}^d,U\in \mathbb{G}$。
• private info：$\vec{a},\vec{b}\in {\mathbb{F}}^d$。
• relation：$P^{\prime }=<\vec{a},\vec{G}>+<\vec{b},\vec{H}>+[<\vec{a},\vec{b}>]U$

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

• public info：commitment $P^{\prime }$，generators $\vec{G}\in {\mathbb{G}}^d,H,U\in \mathbb{G}$ 和$\vec{b}\in {\mathbb{F}}^d$。
• private info：$\vec{a}\in {\mathbb{F}}^d$和blinding $r\in \mathbb{F}$。
• relation：$P^{\prime }=<\vec{a},\vec{G}>+rH+[<\vec{a},\vec{b}>]U$。

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

• Prover：引入Prover私有blinding随机数$d,r_{\delta },r_{\beta }\leftarrow \mathbb{F}$，计算$\delta =d{G}^{\prime }+r_{\delta }H,\beta =dU+r_{\delta }H$，将$\delta ,\beta \in \mathbb{G}$发送给Verifier。
• Verifier：发送challenge $c\leftarrow \mathbb{F}$ 给Prover。
• Prover：计算$z_1=d+c\cdot a^{\prime }{b}^{\prime },z_2=b^{\prime }(c\cdot r+r_{\beta })+r_{\delta }$，将$z_1,z_2\in \mathbb{F}$发送给Verifier。
• Verifier：验证$b^{\prime }(cP+\beta )+\delta =z_1(G^{\prime }+b^{\prime }U)+z_{2}H$是否成立即可。

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

• Prover：引入Prover私有blinding随机数$d,r_{\delta }\leftarrow \mathbb{F}$，计算$\delta =d(G^{\prime }+b^{\prime }U)+r_{\delta }H$，将$\delta \in \mathbb{G}$发送给Verifier。
• Verifier：发送challenge $c\leftarrow \mathbb{F}$ 给Prover。
• Prover：计算$z_1=d+a^{\prime }c,z_2=r_{\delta }+rc$，将$z_1,z_2\in \mathbb{F}$发送给Verifier。
• Verifier：验证$cP+\delta =z_1(G^{\prime }+b^{\prime }U)+z_{2}H$是否成立即可。

2）若$d>1$，则$j={\log }_{2}d,d^{\prime }=\frac{d}{2}$，有：

• Prover：计算：
  $d^{\prime }=d/2$。
  引入Prover私有blinding随机数$l_j,r_j\leftarrow \mathbb{F}$，计算$L_j=<{\vec{a}}_{lo}^{\prime },{\vec{G}}_{hi}^{\prime }>+[l_j]H+[<{\vec{a}}_{lo}^{\prime },{\vec{b}}_{hi}^{\prime }>]U$，$R_j=<{\vec{a}}_{hi}^{\prime },{\vec{G}}_{lo}^{\prime }>+[r_j]H+[<{\vec{a}}_{hi}^{\prime },{\vec{b}}_{lo}^{\prime }>]U$。
  将$L_j,R_j\in \mathbb{G}$发送给Verifier。

• Verifier：发送random challenge $u_j\in \mathbb{F}$ 给Prover。

• Prover：计算：
  ${\vec{a}}^{\prime }={\vec{a}}_{hi}^{\prime }\cdot u_j^{-1}+{\vec{a}}_{lo}^{\prime }\cdot u_j$
  $r^{\prime }=l_j{u}_j^2+r+r_j{u}_j^{-2}$

• Prover和Verifier：计算：
  ${\vec{b}}^{\prime }={\vec{b}}_{lo}^{\prime }\cdot u_j^{-1}+{\vec{b}}_{hi}^{\prime }\cdot u_j$
  ${\vec{G}}^{\prime }={\vec{G}}_{lo}^{\prime }\cdot u_j^{-1}+{\vec{G}}_{hi}^{\prime }\cdot u_j$
  $P^{\prime }=[u_j^2]L_j+P+[u_j^{-2}]R_j$

• 设置$d=d^{\prime },P=P^{\prime },r=r^{\prime }$，继续从步骤1）开始执行。

在以上证明过程中，关注Prover在每轮递归调用时计算的内容：
${\vec{a}}^{\prime }={\vec{a}}_{hi}^{\prime }\cdot u_j^{-1}+{\vec{a}}_{lo}^{\prime }\cdot u_j$
${\vec{b}}^{\prime }={\vec{b}}_{lo}^{\prime }\cdot u_j^{-1}+{\vec{b}}_{hi}^{\prime }\cdot u_j$
${\vec{G}}^{\prime }={\vec{G}}_{lo}^{\prime }\cdot u_j^{-1}+{\vec{G}}_{hi}^{\prime }\cdot u_j$

• 与最后一轮$d=1$时的$G^{\prime }\in \mathbb{G},b^{\prime }\in \mathbb{F}$之间的关系为$G^{\prime }=<\vec{s},\vec{G}>,b^{\prime }=<\vec{s},\vec{b}>$，其中$\vec{s}$为：
  $$\begin{gathered} \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}_1{u}_2\cdots u_k^{-1}, \\ ⋮ \\ {u}_1{u}_2\cdots u_k) \end{gathered}$$
• Verifier在最后一轮收到的commitment $P^{\prime }$，满足以下公式：
  $P^{\prime }={\sum }_{j=1}^k([u_j^2]L_j)+P+{\sum }_{j=1}^k([u_j^{-2}]R_j)$
• Prover在最后一轮的blinding值$r^{\prime }$满足如下公式：
  $r^{\prime }={\sum }_{j=1}^k(l_j{u}_j^2)+r+{\sum }_{j=1}^k(r_j{u}_j^{-2})$

3.1 Amortization Strategy摊销策略

以上polynomial commitment，尽管其communication complexity为$O({\log }_2(d))$，其中$d-1$为多项式的degree bound，但是Verifier必须在验证时计算$G^{\prime }=<\vec{s},\vec{G}>,b^{\prime }=<\vec{s},\vec{b}>$，其中$$\begin{gathered} \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}_1{u}_2\cdots u_k^{-1}, \\ ⋮ \\ {u}_1{u}_2\cdots u_k) \end{gathered}$$。

注意，本文针对的情况是$\vec{b}=(1,x,x^2,\cdots ,x^{n-1})$为public info的情况，其中的$<\vec{s},\vec{b}>$可看成对多项式：【注意，感觉论文的$g(X,u_1,u_2,\cdots ,u_k)$公式有点问题，但是作者说木问题。。。】
$g(X,u_1,u_2,\cdots ,u_k)={\prod }_{i=1}^k(u_i^{-1}+u_i{X}^{2^{i-1}})$
在point $x$的evaluation值，即$b^{\prime }=<\vec{s},\vec{b}>=g(x,u_1,u_2,\cdots ,u_k)$。Verifier可计算该evaluation值in logarithmic time。
但是，对于$G^{\prime }=<\vec{s},\vec{G}>$计算，仍然需要a linear-time multiscalar multiplication。但是仔细观察，可将$G^{\prime }$看成是对多项式$g(X,u_1,u_2,\cdots ,u_k)$系数的commitment值：
$G^{\prime }=Commit(\sigma ,g(X,u_1,u_2,\cdots ,u_k))$
所以 与其让Verifier为$m$个（independent）arguments 自己计算$G_i^{\prime }$，不如将该计算外包给不可信的第三方“helper“ ，”helper”在提供$G_1^{\prime },G_2^{\prime },\cdots ,G_m^{\prime }$ (for $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))$。基于Schwartz-Zippel Lemma，”helper“可让Verifier信服其结果是正确计算的（其伪造成功的概率不高于$\frac{d-1}{p-1}$）。
也就是说，此时，Verifier需调用“helper“运行对$g(X,u_1,u_2,\cdots ,u_k)$的polynomial commitment opening protocol，最终Verifier仍需要进行一次linear-time operation，但是通过此操作，the verifier has traded $m$ linear-time operations for one, with a marginal cost that is logarithmic in the degree bound。

4. FRI多项式承诺