基于内积定理（Inner Product Argument）实现的多项式承诺方案，为了方便，简称为IPA多项式承诺方案。在阅读承诺方案前，需要掌握Pedersen承诺、内积和 Σ \Sigma Σ协议相关知识，Pedersen承诺在前文已介绍。此外，还需掌握一些常见方法来缩小证明大小。
内积
对于 a = ( a 0 , a 1 , ⋯ , a n − 1 ) \pmb{a}=(a_0,a_1,\cdots,a_{n-1}) a=(a0,a1,⋯,an−1)和 G = ( G 0 , G 1 , ⋯ , G n − 1 ) \pmb{G}=(G_0,G_1,\cdots,G_{n-1}) G=(G0,G1,⋯,Gn−1)的内积计算公式为
< a , G > = a 0 G 0 + a 1 G 1 + ⋯ + a n − 1 G n − 1 <\pmb{a},\pmb{G}>=a_0G_0+a_1G_1+\cdots+a_{n-1}G_{n-1} <a,G>=a0G0+a1G1+⋯+an−1Gn−1
内积满足以下性质
-
乘法交换律： ∀ b ∈ F , < b a , G > = < a , b G > = b < a , G > \forall b \in F,<b\pmb{a},\pmb{G}>=<\pmb{a},b\pmb{G}>=b<\pmb{a},\pmb{G}> ∀b∈F,<ba,G>=<a,bG>=b<a,G>
-
乘法分配律1： ∀ a , b , G ∈ F n \forall\pmb{a,b,G} \in F^{n} ∀a,b,G∈Fn , < a + b , G > = < a , G > + < b , G > <\pmb{a+b} , \pmb{G}>=<\pmb{a},\pmb{G}>+<\pmb{b},\pmb{G}> <a+b,G>=<a,G>+<b,G>
-
乘法分配律2: ∀ a , b , G 1 , G 2 ∈ F n , < a + b , G 1 + G 2 > = < a , G 1 > + < a , G 2 > + < b , G 1 > + < b , G 2 > \forall\pmb{a,b,G_1,G_2} \in F^{n}, <\pmb{a+b},\pmb{G_1+G_2}>=<\pmb{a},\pmb{G_1}>+<\pmb{a},\pmb{G_2}>+<\pmb{b},\pmb{G_1}>+<\pmb{b},\pmb{G_2}> ∀a,b,G1,G2∈Fn,<a+b,G1+G2>=<a,G1>+<a,G2>+<b,G1>+<b,G2>
对于多项式 f ( X ) = a 0 + a 1 X + ⋯ + a n − 1 X n − 1 f(X)=a_0+a_1X+\dots+a_{n-1}X^{n-1} f(X)=a0+a1X+⋯+an−1Xn−1在 z z z点的值为 f ( z ) = a 0 + a 1 z + ⋯ + a n − 1 z n − 1 f(z)=a_0+a_1z+\dots+a_{n-1}z^{n-1} f(z)=a0+a1z+⋯+an−1zn−1，可以写成内积的形式，即 f ( z ) = < a , G > f(z)=<\pmb{a},\pmb{G}> f(z)=<a,G>，其中 a = ( a 0 , a 1 , ⋯ , a n − 1 ) \pmb{a}=(a_0,a_1,\cdots,a_{n-1}) a=(a0,a1,⋯,an−1)， b = ( 1 , z , ⋯ , z n − 1 ) \pmb{b}=(1,z,\cdots,z^{n-1}) b=(1,z,⋯,zn−1)。
如何将多个验证等式合并为一个验证等式？–随机线性化组合
举个例子，假设证明者声明 P 1 , P 2 P_1,P_2 P1,P2由 < a , G > <\pmb{a},\pmb{G}> <a,G>和 < b , G > <\pmb{b},\pmb{G}> <b,G>计算的两个内积，其中 G \pmb{G} G是公开的， a , b \pmb{a,b} a,b只有证明者知道。证明者将 a , b \pmb{a,b} a,b发送给验证方进行如下验证。
P 1 = < a , G > P 2 = < b , G > P_1=<\pmb{a},\pmb{G}>\\ P_2=<\pmb{b},\pmb{G}> P1=<a,G>P2=<b,G>
验证等式成立，则证明 P 1 , P 2 P_1,P_2 P1,P2通过 < a , G > <\pmb{a},\pmb{G}> <a,G>和 < b , G > <\pmb{b},\pmb{G}> <b,G>计算，具体流程如图所示。
如何将两个验证等式合并为一个等式且确保以上等式均成立？考虑两个等式相乘，因无法确保 P 1 P_1 P1和 P 2 P_2 P2是否存在公因数，这是不可行的。考虑两个等式想加，如下
P 1 + P 2 = < a , G > + < b , G > P_1+P_2=<\bm{a},\bm{G}>+<\bm{b},\bm{G}> P1+P2=<a,G>+<b,G>
显而易见，左边两项均由证明方生成，则验证者可以声明两个错误的值 P 1 ′ , P 2 ′ P_1^{\prime},P_2^{\prime} P1′,P2′是由 < a , G > <\pmb{a},\pmb{G}> <a,G>和 < b , G > <\pmb{b},\pmb{G}> <b,G>计算的两个内积，如下所示。
此时验证等式成立，但无法确保原本的两个等式成立，如下。
P 1 ′ ≠ < a , G > P 2 ′ ≠ < b , G > P_1^{\prime}\neq<\bm{a},\bm{G}>\\ P_2^{\prime}\neq<\bm{b},\bm{G}> P1′=<a,G>P2′=<b,G>
为了抵御以上攻击，即验证等式左边任意两项不能均由证明者计算。验证者选择一个随机数 r r r，合并两个验证等式如下
P 1 + r P 2 = < a , G > + r < b , G > P_1+rP_2=<\bm{a},\bm{G}>+r<\bm{b},\bm{G}> P1+rP2=<a,G>+r<b,G>
验证者验证以上等式成立时，可确保等式 P 1 = < a , G > P_1=<\pmb{a},\pmb{G}> P1=<a,G>和 P 2 = < b , G > P_2=<\pmb{b},\pmb{G}> P2=<b,G>同时成立。
目前我们知道了如何将两个验证等式合并为一个验证等式，如何多个验证如何合并为一个验证等式？ 假设有以下 k k k个验证等式
P 1 = < a 1 , G > P 2 = < a 2 , G > … P k = < a k , G > P_1=<\bm{a_1},\bm{G}>\\ P_2=<\bm{a_2},\bm{G}>\\ \dots\\ P_k=<\bm{a_k},\bm{G}>\\ P1=<a1,G>P2=<a2,G>…Pk=<ak,G>
为了确保任意验证等式左边两项不能由证明者独自计算，有两种合并方式。
- 验证者可以选择 k k k个不同的随机数 x 1 , x 2 , … x k x_1,x_2,\dots x_{k} x1,x2,…xk将多个验证等式合并成一个等式，如下所示。
x 1 P 1 + x 2 P 2 + ⋯ + x k P k = x 1 < a 1 , G > + x 2 < a 2 , G > + ⋯ + x k < a k , G > x_1P_1+x_2P_2+\cdots+x_{k}P_k=x_1<\bm{a_1},\bm{G}>+x_2<\bm{a_2},\bm{G}>+\cdots+x_{k}<\bm{a_k},\bm{G}> x1P1+x2P2+⋯+xkPk=x1<a1,G>+x2<a2,G>+⋯+xk<ak,G>
- 验证者选择一个随机数 x x x也可合并成一个等式。
P 1 + x P 2 + ⋯ + x k − 1 P k = < a 1 , G > + x < a 2 , G > + ⋯ + x k − 1 < a k , G > P_1+xP_2+\cdots+x^{k-1}P_k=<\bm{a_1},\bm{G}>+x<\bm{a_2},\bm{G}>+\cdots+x^{k-1}<\bm{a_k},\bm{G}> P1+xP2+⋯+xk−1Pk=<a1,G>+x<a2,G>+⋯+xk−1<ak,G>
相较而言，第一种方式的安全性是强于第二种的。
思考：若合并形式如下可行吗？
x 2 P 1 + x 4 P 2 + ⋯ + x 2 k P k = x 2 < a 1 , G > + x 4 < a 2 , G > + ⋯ + x 2 k < a k , G > x^2P_1+x^{4}P_2+\cdots+x^{2k}P_k=x^2<\bm{a_1},\bm{G}>+x^4<\bm{a_2},\bm{G}>+\cdots+x^{2k}<\bm{a_k},\bm{G}> x2P1+x4P2+⋯+x2kPk=x2<a1,G>+x4<a2,G>+⋯+x2k<ak,G>
答：可行，因为任意两项都不由证明者独立计算。
当前知道验证方如何将多个验证等式合并为一个等式，但还是有些疑惑，随机线性化组合有什么作用呢？
在密码协议中，随机线性化组合发挥着巨大的作用，例如随机线性化组合可以缩小验证时间、减少证明大小或者来实现零知识等。以缩小证明大小为例。
缩小证明大小
若验证等式的右侧项形式相同可以合并同类项，则可以缩小证明的大小。回到两个验证等式合并的等式，其可进行如下合并：
P 1 + r P 2 = < a , G > + r < b , G > = < a + r b , G > P_1+rP_2=<\bm{a},\bm{G}>+r<\bm{b},\bm{G}>=<\bm{a}+r\bm{b},G>\\ P1+rP2=<a,G>+r<b,G>=<a+rb,G>
即验证等式为 P 1 + r P 2 = < a + r b , G > P_1+rP_2=<\pmb{a}+r\pmb{b},G> P1+rP2=<a+rb,G>。 验证者将 r r r发送给证明者，证明者只需要发送证明 a + r b \bm{a}+r\bm{b} a+rb 就能证明原来的两个等式成立，流程如下所示。
可以看出，相较于原本的证明 a , b \bm{a},\pmb{b} a,b，元素为 2 n 2n 2n个，现在仅需发送 n n n个元素，即 a + r b \pmb{a}+r\pmb{b} a+rb。
基于内积分配律和随机线性化组合来缩小证明 a \pmb{a} a的大小（针对验证等式 P = < a , G > P=<\pmb{a},\pmb{G}> P=<a,G>）
上面知道可以通过合并验证等式来缩小证明大小。但针对一个验证等式该如何添加辅助项来缩减证明大小还存在疑问。因此在介绍方法之前，先了解一个内积分配律的特殊情况。
分配律的扩展
已知内积满足分配律，对于长度为 n = 2 k n=2^k n=2k的向量 a = ( a L , a R ) \pmb{a}=(\pmb{a_L},\pmb{a_R}) a=(aL,aR),其中 a L = ( a 0 , ⋯ , a n 2 − 1 ) \pmb{a_L}=(a_0,\cdots,a_{\frac{n}{2}-1}) aL=(a0,⋯,a2n−1) ， a R = ( a n 2 , ⋯ , a n − 1 ) \pmb{a_R}=(a_{\frac{n}{2}},\cdots,a_{n-1}) aR=(a2n,⋯,an−1)，同理 G = ( G L , G R ) \pmb{G}=(\pmb{G_L},\pmb{G_R}) G=(GL,GR)。则 < a , G > = < a L , G L > + < a R , G R > <\pmb{a},\pmb{G}>=<\pmb{a_L},\pmb{G_L}>+<\pmb{a_R},\pmb{G_R}> <a,G>=<aL,GL>+<aR,GR>。
∀ x 1 , x 2 , x 3 , x 4 ∈ F \forall x_1,x_2,x_3,x_4 \in F ∀x1,x2,x3,x4∈F 时，满足
< x 1 a L + x 2 a R , x 3 G L + x 4 G R > = x 1 x 3 < a L , G L > + x 1 x 4 < a L , G R > + x 2 x 3 < a R , G L > + x 2 x 4 < a R , G R > \begin{align*} <x_1\pmb{a_L}+x_2\pmb{a_R},x_3\pmb{G_L}+x_4\pmb{G_R}>=& x_1x_3<\pmb{a_L},\pmb{G_L}> +x_1x_4<\pmb{a_L},\pmb{G_R}>\\ & +x_2x_3<\pmb{a_R},\pmb{G_L}>+x_2x_4<\pmb{a_R},\pmb{G_R}> \end{align*} <x1aL+x2aR,x3GL+x4GR>=x1x3<aL,GL>+x1x4<aL,GR>+x2x3<aR,GL>+x2x4<aR,GR>
当 x 1 x 3 = x 2 x 4 = k x_1x_3=x_2x_4=k x1x3=x2x4=k时，
< x 1 a L + x 2 a R , x 3 G L + x 4 G R > = k < a , G > + k 2 x 2 x 3 < a L , G R > + x 2 x 3 < a R , G L > \begin{equation} \begin{aligned} <x_1\pmb{a_L}+x_2\pmb{a_R},x_3\pmb{G_L}+x_4\pmb{G_R}>=& k<\pmb{a},\pmb{G}> +\frac{k^2}{x_2x_3}<\pmb{a_L},\pmb{G_R}>\\ & +x_2x_3<\pmb{a_R},\pmb{G_L}> \end{aligned} \end{equation} <x1aL+x2aR,x3GL+x4GR>=k<a,G>+x2x3k2<aL,GR>+x2x3<aR,GL>
此时，验证左侧等式的证明为 x 1 a L + x 2 a R x_1\pmb{a_L}+x_2\pmb{a_R} x1aL+x2aR，长度大小为 n 2 \frac{n}{2} 2n；验证右侧等式的证明为 a \pmb{a} a，大小为 n n n；
方法
证明者声明 P P P通过 < a , G > <\pmb{a},\pmb{G}> <a,G>计算得到，其中 G \pmb{G} G是公开的， a \pmb{a} a只有证明者知道。证明者将 a \pmb{a} a发送给验证方进行如下验证。因为 a \pmb{a} a由 n n n个元素组成。
考虑能否增加两项辅助验证等式使其满足公式(1)右侧中的所有项，并且能合并合并成公式(1)等式左侧的形式。首先，证明者计算辅助验证等式的值为
K 1 = < a L , G R > K 2 = < a R , G L > K_1=<\bm{a_L},\bm{G_R}>\\ K_2=<\bm{a_R},\bm{G_L}> K1=<aL,GR>K2=<aR,GL>
将 K 1 , K 2 K_1,K_2 K1,K2和 P P P发送给验证者，验证者验证以下等式。
P = < a , G > K 1 = < a L , G R > K 2 = < a R , G L > P=<\bm{a},\bm{G}>\\ K_1=<\bm{a_L},\bm{G_R}>\\ K_2=<\bm{a_R},\bm{G_L}>\\ P=<a,G>K1=<aL,GR>K2=<aR,GL>
验证者选择三个随机数 r 1 , r 2 , r 3 ∈ F r_1,r_2,r_3\in F r1,r2,r3∈F，将其合并为一个验证等式。
r 1 P + r 2 K 2 + r 3 K 1 = r 1 < a , G > + r 2 < a R , G L > + r 3 < a L , G R > r_1P+r_2K_2+r_3K_1=r_1<\bm{a},\bm{G}>+r_2<\bm{a_R},\bm{G_L}>+r_3<\bm{a_L},\bm{G_R}> r1P+r2K2+r3K1=r1<a,G>+r2<aR,GL>+r3<aL,GR>
此时，当 r 1 , r 2 , r 3 r_1,r_2,r_3 r1,r2,r3满足什么条件时，可以将验证等式右侧合并为一项？
从公式(1)可知，当满足 r 2 = r 1 2 r 3 r_2=\frac{r_1^2}{r_3} r2=r3r12时，验证等式右侧可以合并为一项，即 r 1 P + r 2 K 2 + r 3 K 1 = < x 1 a L + x 2 a R , x 3 G L + x 4 G R > r_1P+r_2K_2+r_3K_1=<x_1\pmb{a_L}+x_2\pmb{a_R},x_3\pmb{G_L}+x_4\pmb{G_R}> r1P+r2K2+r3K1=<x1aL+x2aR,x3GL+x4GR>。
同时 r 1 , r 2 , r 3 r_1,r_2,r_3 r1,r2,r3还需满足合并的条件，即 r 1 ≠ r 2 ≠ r 3 r_1\neq r_2\neq r_3 r1=r2=r3。
使用一个随机数 x x x进行合并，同样需要满足上述条件。举个例子，当 r 1 = 1 r_1=1 r1=1， r 2 = x r_2=x r2=x, r 3 = x − 1 r_3=x^{-1} r3=x−1，验证多项式为 P + x K 2 + x − 1 K 1 = < x − 1 a L + a R , x G L + G R > P+xK_2+x^{-1}K_1=<x^{-1}\pmb{a_L}+\pmb{a_R},x\pmb{G_L}+\pmb{G_R}> P+xK2+x−1K1=<x−1aL+aR,xGL+GR>
若验证者将随机值发送给证明者，证明者发送证明 x − 1 a L + a R x^{-1}\pmb{a_L}+\pmb{a_R} x−1aL+aR，验证等式成立，则证明 P P P 是 < a , G > <\pmb{a},\pmb{G}> <a,G>的值，且证明大小仅为原本的一半。
综上，此时具体流程如图所示。
将左侧验证等式表示为 P ′ = P + x K 2 + x − 1 K 1 P^{\prime}=P+xK_2+x^{-1}K_1 P′=P+xK2+x−1K1 ，右侧验证等式表示为 < a ′ , G ′ > = < x − 1 a L + a R , x G L + G R > <\pmb{a}^{\prime},\pmb{G}^{\prime}>=<x^{-1}\pmb{a_L}+\pmb{a_R},x\pmb{G_L}+\pmb{G_R}> <a′,G′>=<x−1aL+aR,xGL+GR>，验证等式写成 P ′ = < a ′ , G ′ > P^{\prime}=<\pmb{a}^{\prime},\pmb{G}^{\prime}> P′=<a′,G′>，因此可以继续采取措施缩减证明的大小，直至证明大小为1。如图所示。
Σ \Sigma Σ协议
Σ \Sigma Σ协议是一个基础的零知识证明协议，它指的是证明者能够在不向验证者提供任何有用的信息的情况下，使验证者相信某个论断是正确的。
假设存在一个论断 P = a G P=aG P=aG， G G G是一个定义在椭圆曲线上的加法群元素， P P P和 G G G都是都是公开信息。证明者想证明自己知道 a a a，最直接的方式是公开 a a a，让验证者验证等式 P = a G P=aG P=aG。但证明者并不想泄漏 a a a的信息，证明者可以生成一个同形式的随机项 R = r G R=rG R=rG作为辅助验证等式，验证者验证以下两个等式。
R = r G P = a G R=rG\\ P=aG\\ R=rGP=aG
此时，验证者选择一个随机数 x x x将其合并成一个验证等式 R + x P = ( r + x a ) G R+xP=(r+xa)G R+xP=(r+xa)G，证明者只需出示证明 r + x a r+xa r+xa即可证明知道隐私信息 a a a。具体流程如图所示。
