零知识证明 - 基于多项式构造零知识证明

理解为什么以及如何基于多项式构造零知识证明，这篇文章讲的比较清楚。虽然文章只讲到了皮诺曹协议，但是足够理解基于多项式构造零知识证明的本质。想深入零知识证明的小伙伴都建议看看。

http://petkus.info/papers/WhyAndHowZkSnarkWorks.pdf

以下是我对这篇文章的理解和总结。原文由浅入深地从一个个简单版本，慢慢推导出实用的证明协议。

协议0 - 直观版本

随机抽查，随机提供样本，对照结果。这种协议，需要通过设定随机抽查的次数，确定安全系数。

协议1 - 从多项式的系数证明开始

最简单的d阶多项式，可以随机选择一个点x，让prover通过多项式计算生成y，verifier可以查看y是否正确。不同的多项式，最多有d个相交的点（相等的点）。

如果x/y的取值范围很大（设为n），在不知道原始多项式的情况下，能正确给出证明的概率比较低：d/n。多项式，能在一次交互，就能获取比较好的安全系数（如果n远大于d的话，将近100%）。比版本0，优秀不少。

这种协议还是比较简单和原始。证明建立在双方还是相互信任的基础上。本质上，prover并没有证明他/她知道多项式。证明本身并不能推出他/她知道一个确定的多项式。知道一个值，并不代表知道一个多项式。而且，如果多项式的值范围不大的话，证明者可以随机选择一个值撞概率。

协议2 - 基于多项式因式分解改进

假设一个多项式可以分解成：p(x) = t(x)h(x)。t(x)是目标多项式，是由p(x)的部分解组成的多项式：$t(x) = (x-x_0)(x-x_1) ... (x-x_{d-1})$t(x)=(x−x0​)(x−x1​)...(x−xd−1​)。也就是说，证明者需要证明的一部分，证明者知道一个多项式的部分解。从验证者的角度看，既然你知道一个多项式的部分解，那你知道的多项式一定能整除t(x)。在随机挑选x的情况下，你都能给出正确的证明，即可认定你知道这个满足条件的多项式。

• 验证者，随机生成r，并计算出t®，将r发送给证明者

• 证明者，计算h(x) = p(x)/t(x)，并给出p®以及h®

• 验证者验证，是否p®=t®h®

该版本要求证明者，知道一个能整除t(x)的多项式。但比较容易发现，该协议存在如下的问题：

1/ 证明者，可以自己计算出t®，随机生成h®，并构造出p® = t®h®

2/ 即使不像1，证明者不考虑多项式，直接通过结果伪造证明。证明者，因为知道随机数r，证明者可以使用任何一个多项式，保证存在相同点(r, t®h®)。这样，证明的p®和h®虽然和正确的证明是一样的，但是，证明者却不需要知道正确的多项式。

3/ 证明者，可以自己构造多项式，只要满足h(x)=p(x)/t(x)即可。

版本3 - 引入同态加密

协议2中的问题1/2，都是因为证明者知道随机数r以及t®。引入同态加密解决。数据是加密的，在加密数据的基础上可以进行计算，能和原始数据计算具有同样的“形态”。

在模运算基础上的幂次计算，是同态加密的一种方式，表示为: $E(v) = g^v(mod\ n)$E(v)=gv(mod n)，其中v是需要加密的数据。在同态加密的基础上，可以定义运算：

加法：加密结果相乘，加密结果相乘等于原始数据相加后的加密结果

乘法：幂次运算，一个加密结果进行幂次计算等于两个原始数据乘法的加密结果（注意不是同态乘法）

除法：相对复杂，不深究

不要被加法（相乘），乘法（幂次）迷惑了。你可以认为，加密结果加法是通过加密结果的乘法实现的。

注意，乘法不支持两个加密结果乘法。也就是说，只支持一个原始数据和一个同态加密结果进行乘法操作。

有了同态加密，一个多项式的加密结果，可以通过多项式的各个项的加密结果计算。

比如说，一个多项式$p(x) = x^3 - 3x^2 + 2x$p(x)=x3−3x2+2x。p(x)的加密结果可以通过如下的方式计算：

$E(X^3)^1\cdot E(x^2)^{-3}\cdot E(x)^2 = (g^{x^3})^1 \cdot (g^{x^2})^{-3} \cdot (g^{x})^2 = g^{x^3-3x^2+2x}$E(X3)1⋅E(x2)−3⋅E(x)2=(gx3)1⋅(gx2)−3⋅(gx)2=gx3−3x2+2x

显而易见，一个多项式的值，可以通过各项的加密结果乘上各项的系数，计算出多项式的加密结果。

• 验证者，随机挑选s，计算出多项式各项的加密结果$E(s^0), E(s^1), ... E(s^d)$E(s0),E(s1),...E(sd)，并将这些值发给证明者。同时计算出目标多项式的加密值t(s)
• 证明者先计算出h(x) = p(x)/t(x)，并通过多项式加密计算的方法计算出E(p(s)) 和 E(h(s))
• 验证者验证：E(p(s)) = E(h(s))*t(s)是否成立

这个协议，验证者没有暴露随机值s，证明者只能通过多项式计算出h，从而计算出证明。这个协议，也有问题，证明者有可能只用验证者提供的各项加密结果中的几项来构造证明。并且，聪明的证明者可以自己通过多项式的各项的加密结果计算出t(s)。在知道t(s)的情况下，要构造一个证明非常容易，只需要满足幂次计算即可。

版本4 - KEA（Knowledge-of-Exponent Assumption)

假设Alice想获得a的幂次结果，具体的幂次不关心。为了限制幂次结果的提供者Bob只在a上进行幂次操作，Alice提供$a$a以及$a^{\alpha}$aα。Bob选择一个幂次$c$c，计算$b = a^c mod \ n$b=acmod n以及$b' = (a')^c mod\ n$b′=(a′)cmod n，并发送给Alice。Alice通过检查$b^\alpha = b'$bα=b′确定是否b是在a基础上的幂次计算。

$(a, a^\alpha)$(a,aα)就是“$\alpha$α对"。通过一个“$\alpha$α对"，数据进行同样的幂次操作。

在上述同态加密的情况下，幂次计算，是同态加密后的乘法操作。举个例子，有个简单的多项式$f(x)=c\cdot x$f(x)=c⋅x，验证者为了保证证明者在随机选择的s的加密结果上都“乘以”c，提供$(g^s, g^{\alpha\cdot s})$(gs,gα⋅s)。证明者，通过提供$((g^{s})^{c},(g^{\alpha\cdot s})^{c})$((gs)c,(gα⋅s)c)，证明计算是对同一个加密结果进行了乘法操作。

因为同态加法成立，该方法可以从简单的多项式可以扩展到一半多项式。

• 验证者提供$g^{s^0}, g^{s^1}, ... , g^{s^d}$gs0,gs1,...,gsd以及$g^{\alpha\cdot s^0}, g^{\alpha\cdot s^1}, ... , g^{\alpha\cdot s^d}$gα⋅s0,gα⋅s1,...,gα⋅sd
• 证明者分别计算两组值：
  • $g^p = g^{p(s)} = (g^{s^0})^{c_0}\cdot (g^{s^1})^{c_1} \cdot... \cdot (g^{s^d})^{c_d}$gp=gp(s)=(gs0)c0​⋅(gs1)c1​⋅...⋅(gsd)cd​
  • $g^{p'} = g^{\alpha p(s)} = (g^{\alpha s^0})^{c_0}\cdot (g^{\alpha s^1})^{c_1} \cdot ... \cdot (g^{\alpha s^d})^{c_d}$gp′=gαp(s)=(gαs0)c0​⋅(gαs1)c1​⋅...⋅(gαsd)cd​
• 验证者验证：$(g^p)^{\alpha} = g ^ {p'}$(gp)α=gp′

从证明可以推导出：$g^{p'} = g^{c_0 \alpha s^0 + c_1 \alpha s^1+ ... + c_d \alpha s^d} = g^{\alpha(c_0 s^0 + c_1 s^1+ ... + c_d s^d)}$gp′=gc0​αs0+c1​αs1+...+cd​αsd=gα(c0​s0+c1​s1+...+cd​sd)。

该协议很好的限制证明者必须在多项式的计算下，每个系数都正确“计算”。但是，这个协议并没有保护证明者的知识：验证者可以从证明信息中暴力反推多项式系数（毕竟现实场景下系数的组合还不算多）。

版本5 - ZK（零知识）

为了保护证明信息，也就是保护$c_0, c_1 ... c_d$c0​,c1​...cd​信息。还是利用“偏移”，在$g^p 和 g^{p'}$gp和gp′都“乘”上一个随机系数$\delta$δ。即使验证者能枚举出$(\delta c_0, \delta c_1, \delta c_2 ... \delta c_d)$(δc0​,δc1​,δc2​...δcd​)，也非常难获取$(c_0, c_1, ... c_d)$(c0​,c1​,...cd​)。

版本6 - 无交互

之前所有的协议都是交互式的。交互式协议有些问题：

• 验证者可以和证明者串通，伪造证明
• 验证者，自己生成证明
• 在整个交互过程中，验证者必须保存$\alpha$α和$t(s)$t(s)。可能会造成其他攻击的可能。

配对函数和双线性映射

到目前为止，验证者需要验证如下的两个等式：

$g^p = (g^{h})^{t(s)}$gp=(gh)t(s)

$(g^p)^\alpha = g^{p'}$(gp)α=gp′

假设，验证者不存储$\alpha$α和$t(s)$t(s)，而存储对应的加密数据。这样在验证的时候，$g^h$gh和$g^{t(s)}$gt(s)两个加密结果“相乘“，$g^p$gp和$g^\alpha$gα”相乘“。从同态加密的定义，我们发现两个加密结果不能相乘。于是引入了新的计算特性：双线性映射。

$e(g^a, g^b) = e(g, g)^{ab}$e(ga,gb)=e(g,g)ab

双线性映射的核心性质，可以表达成如下的等式：

$e(g^a, g^b) = e(g^b, g^a) = e(g^{ab}, g^1) = e(g^1, g^{ab}) = e(g^1, g^a)^b = e(g^1, g^1)^{ab}$e(ga,gb)=e(gb,ga)=e(gab,g1)=e(g1,gab)=e(g1,ga)b=e(g1,g1)ab

值的一提的是，e配对函数也具有加法同态：

$e(g^a, g^b)\cdot e(g^c, g^d) = e(g^1, g^1)^{ab} \cdot e(g^1, g^1)^{cd} = e(g^1, g^1)^{ab+cd}$e(ga,gb)⋅e(gc,gd)=e(g1,g1)ab⋅e(g1,g1)cd=e(g1,g1)ab+cd

到此，一个zk-SNARK的协议样子就出来了：

• Setup
  • 随机产生$s$s和$\alpha$α
  • 计算生成$g^\alpha$gα以及$g^{s^i},g^{\alpha s^i} i\in d$gsi,gαsii∈d，其中$(g^{s^i},g^{\alpha s^i} i\in d)$(gsi,gαsii∈d)为生成**，$(g^\alpha, g^{t(s)})$(gα,gt(s))为验证**
• Prove
  • 计算h(x) = p(x)/t(x)
  • 利用$g^{s^i}$gsi计算$g^{p(s)}$gp(s)和$g^{h(s)}$gh(s)
  • 利用$g^{\alpha s^i}$gαsi计算$g^{\alpha p(s)}$gαp(s)
  • 随机生成$\delta$δ
  • 生成证明$\pi = (g^{\delta p(s)}, g^{\delta h(s)}, g^{\delta \alpha p(s)})$π=(gδp(s),gδh(s),gδαp(s))
• Verification
  • 假设证明$\pi = (g^p, g^h, g^{p'})$π=(gp,gh,gp′)
  • 检查等式$e(g^{p'}, g) = e(g^p, g^{\alpha})$e(gp′,g)=e(gp,gα)
  • 检查等式$e(g^p, g) = e(g^{t(s)}, g^h)$e(gp,g)=e(gt(s),gh)

扩展到一般计算

如果把一个算子的左右两个输入和输出，都看作多项式的话：

$l(x)\ operator\ r(x) = o(x)$l(x) operator r(x)=o(x)

也就是说，$l(x)\ operator\ r(x) - o(x)=0$l(x) operator r(x)−o(x)=0

可以把$l(x)\ operator\ r(x) - o(x)$l(x) operator r(x)−o(x)看成一个多项式，类似上述的p(x)。通过之前的协议，可以证明证明者知道一个多项式，但是，并没有证明这个多项式的组成方式（不一定具有$l(x)\ operator\ r(x) - o(x)$l(x) operator r(x)−o(x)的形式）。

通用版本0 - 支持乘法算子

如果这个算子是乘法的话，并且如果随机数为s的话，$l(s)\cdot r(s) - o(s) = t(s)h(s)$l(s)⋅r(s)−o(s)=t(s)h(s)。也就是说，验证者除了需要验证l，r以及o是多项式外，还需要在加密空间验证等式成立。因为在加密空间做“减”法相对麻烦，需要算逆，可以将等式稍稍变形：

$l(s)\cdot r(s)= t(s)h(s) + o(s)$l(s)⋅r(s)=t(s)h(s)+o(s)

这样，加密空间就能用配对函数进行验证：

$e(g^{l(s)}, g^{r(s)}) = e(g^{t(s)}, g^{h(s)})\cdot e(g^{o(s)}, g)$e(gl(s),gr(s))=e(gt(s),gh(s))⋅e(go(s),g)

$e(g,g)^{l(s)r(s)} = e(g,g)^{t(s)h(s)}\cdot e(g, g)^{o(s)}$e(g,g)l(s)r(s)=e(g,g)t(s)h(s)⋅e(g,g)o(s)

$e(g,g)^{l(s)r(s)} = e(g,g)^{t(s)h(s)+o(s)}$e(g,g)l(s)r(s)=e(g,g)t(s)h(s)+o(s)

这样，在之前的协议基础上，可以扩展为：

• Prove
  • 计算$h(x) = \frac{l(x)r(x)-o(x)}{t(x)}$h(x)=t(x)l(x)r(x)−o(x)​
  • 利用$g^{s^i}$gsi计算$g^{l(s)}$gl(s)，$g^{r(s)}$gr(s)，$g^{o(s)}$go(s)和$g^{h(s)}$gh(s)
  • 利用$g^{\alpha s^i}$gαsi计算$g^{\alpha l(s)}$gαl(s)，$g^{\alpha r(s)}$gαr(s)和$g^{\alpha o(s)}$gαo(s)
  • 生成证明$\pi = (g^{l(s)}, g^{r(s)}, g^{o(s)}, g^{h(s)},g^{\alpha l(s)}, g^{\alpha r(s)}, g^{\alpha o(s)})$π=(gl(s),gr(s),go(s),gh(s),gαl(s),gαr(s),gαo(s))
• Verification
  • 假设证明$\pi = (g^l,g^r,g^o, g^h, g^{l'},g^{r'},g^{o'})$π=(gl,gr,go,gh,gl′,gr′,go′)
  • 检查等式$e(g^{l'}, g) = e(g^l, g^{\alpha})$e(gl′,g)=e(gl,gα)
  • 检查等式$e(g^{r'}, g) = e(g^r, g^{\alpha})$e(gr′,g)=e(gr,gα)
  • 检查等式$e(g^{o'}, g) = e(g^o, g^{\alpha})$e(go′,g)=e(go,gα)
  • 检查等式$e(g^l, g^r) = e(g^{t(s)}, g^h)\cdot e(g^o, g)$e(gl,gr)=e(gt(s),gh)⋅e(go,g)

多个乘法，可以采用中间变量，分解成多个乘法操作。比如a*b*c，可以分解成：

$a*b = r_1$a∗b=r1​

$r_1*c=r_2$r1​∗c=r2​

多个乘法表达式，同样可以表达成$l(x)\cdot r(x) = o(x)$l(x)⋅r(x)=o(x)。和前一个例子不同的是，需要选择两个x，保证等式成立。可以通过差值计算出l(x), r(x)以及o(x)。通过通用版本0的协议，可以进行证明（扩展t(x) ）。

通用版本1 - 多项式$\alpha$α对

之前讲的$\alpha$α对，都是针对多项式中的某一个项。整个多项式，也可以实现$\alpha$α 对，保证某个多项式乘以一个系数。

• Setup
  • 随机产生$s$s和$\alpha$α
  • 计算生成$g^\alpha$gα以及$g^{l(s)}$gl(s) 和$g^{\alpha l(s)}$gαl(s)
• Prove
  • 如果多项式的系数为$v$v
  • 计算生成$(g^{vl(s)}, g^{v \alpha l(s)})$(gvl(s),gvαl(s))
• Verification
  • 假设证明$\pi = (g^l, g^{l'})$π=(gl,gl′)
  • 检查等式$e(g^{l'}, g) = e(g^l, g^{\alpha})$e(gl′,g)=e(gl,gα)

这个协议有个问题，在多项式上做任何偏移，也能让验证等式成立。

$g^{vl(s)}\cdot g^{v'} = g^{vl(s)+v'}$gvl(s)⋅gv′=gvl(s)+v′

$g^{\alpha v l(s)} \cdot (g^{\alpha})^{v'} = g^{\alpha (vl(s) + v')}$gαvl(s)⋅(gα)v′=gα(vl(s)+v′)

$e(g^{\alpha(vl(s)+v')}, g) = e(g^{vl(s)+v'}, g^{\alpha})$e(gα(vl(s)+v′),g)=e(gvl(s)+v′,gα)

在多个计算情况下，某个算子的输入可能是由多个变量组成：

$a \times b = r_1$a×b=r1​

$a \times c = r_2$a×c=r2​

$d \times c = r_3$d×c=r3​

可以用如下的多项式来表达左输入：

$L(x) = al_a(x) + d l_d(x)$L(x)=ala​(x)+dld​(x)

$l_a(x)$la​(x)在x=1，2的时候为1， x=2的时候为0。

$l_d(x)$ld​(x)在x=1，2的时候为0， x=2的时候为1。

$\alpha$α对，不仅对单个多项式有限制作用，对多项式的组合同样有用：

• Setup
  • 随机产生$s$s和$\alpha$α
  • 计算生成$g^\alpha$gα以及$g^{l_a(s)}, g^{l_d(s)}$gla​(s),gld​(s) 和$g^{\alpha l_a(s)},g^{\alpha l_d(s)}$gαla​(s),gαld​(s)
• Prove
  • 计算生成$g^{L(s)} = g^{al_a(x) + dl_d(x)} = (g^{l_a(s)})^{a}\cdot(g^{l_d(s)})^{d}$gL(s)=gala​(x)+dld​(x)=(gla​(s))a⋅(gld​(s))d
  • 计算生成$g^{\alpha L(s)} = g^{\alpha al_a(x) + \alpha dl_d(x)} = (g^{\alpha l_a(s)})^{a}\cdot(g^{\alpha l_d(s)})^{d}$gαL(s)=gαala​(x)+αdld​(x)=(gαla​(s))a⋅(gαld​(s))d
• Verification
  • 假设证明$\pi = (g^L, g^{L'})$π=(gL,gL′)
  • 检查等式$e(g^{L'}, g) = e(g^L, g^{\alpha})$e(gL′,g)=e(gL,gα)

也就是说，$\alpha$α对能保证一种计算结构，加密数据乘上系数的结构。加密数据本身具有加法同态，所以，可以从多项式的一项，扩展为多项式，再扩展为多个多项式。

通用版本2 - 通用计算

计算表达也进一步延伸，每个算子的输入和输出都可以是多个变量的累积。

$\sum_{i=1}^n c_{l,i}\cdot v_i \times \sum_{i=1}^n c_{r, i}\cdot v_i = \sum_{i=1}^{n} c_{o,i}\cdot v_i$i=1∑n​cl,i​⋅vi​×i=1∑n​cr,i​⋅vi​=i=1∑n​co,i​⋅vi​

其中，$v_i$vi​是各个变量（包括临时变量）。

假设存在d 个计算表达式，变量个数是n，相应的系数是：$C_{L,i,j}, C_{R,i,j}, C_{O,i,j} \ i\in {1...n}, j\in {1...d}$CL,i,j​,CR,i,j​,CO,i,j​ i∈1...n,j∈1...d

• Setup
  • 通过插值，计算出$l_i(x)，r_i(x), o_i(x), i\in{1...n}$li​(x)，ri​(x),oi​(x),i∈1...n
  • 随机产生$s$s和$\alpha$α
  • 计算生成$g^\alpha, g^{s^k} k \in {1...d}$gα,gskk∈1...d以及$g^{l_i(s)}, g^{r_i(s)}, g^{o_i(s)}$gli​(s),gri​(s),goi​(s) 和$g^{\alpha l_i(s)},g^{\alpha r_i(s)},g^{\alpha o_i(s)}$gαli​(s),gαri​(s),gαoi​(s)
• Prove
  • 计算$h(x) = \frac{L(x)\times R(x)-O(x)}{t(x)}$h(x)=t(x)L(x)×R(x)−O(x)​，其中$L(x) = \sum_{i=1}^n v_i\cdot li(x)$L(x)=∑i=1n​vi​⋅li(x)，R(x)/O(x)类似
  • 计算生成$g^{L(s)} = \prod_{i=1}^n (g^{l_i(s)})^{v_i},g^{R(s)} = \prod_{i=1}^n (g^{r_i(s)})^{v_i},g^{O(s)} = \prod_{i=1}^n (g^{o_i(s)})^{v_i}$gL(s)=∏i=1n​(gli​(s))vi​,gR(s)=∏i=1n​(gri​(s))vi​,gO(s)=∏i=1n​(goi​(s))vi​
  • 计算生成$g^{\alpha L(s)} = \prod_{i=1}^n (g^{\alpha l_i(s)})^{v_i},g^{\alpha R(s)} = \prod_{i=1}^n (g^{\alpha r_i(s)})^{v_i},g^{\alpha O(s)} = \prod_{i=1}^n (g^{\alpha o_i(s)})^{v_i}$gαL(s)=∏i=1n​(gαli​(s))vi​,gαR(s)=∏i=1n​(gαri​(s))vi​,gαO(s)=∏i=1n​(gαoi​(s))vi​
  • 计算生成$g^{h(s)}$gh(s)
• Verification
  • 假设证明$\pi = (g^L, g^{R}, g^{O}, g^{L'}, g^{R'}, g^{O'}, g^{h})$π=(gL,gR,gO,gL′,gR′,gO′,gh)
  • 检查等式$e(g^{L'}, g) = e(g^L, g^{\alpha}),e(g^{R'}, g) = e(g^R, g^{\alpha}),e(g^{O'}, g) = e(g^O, g^{\alpha})$e(gL′,g)=e(gL,gα),e(gR′,g)=e(gR,gα),e(gO′,g)=e(gO,gα)
  • 检查等式$e(g^L, g^R) = e(g^t, g^h)\cdot e(g^O, g)$e(gL,gR)=e(gt,gh)⋅e(gO,g)

通用版本3 - 固定输入和输出

上述的协议因为对l，r，以及o使用的是同一个$\alpha$α值，存在如下的问题：

1. L(x)的计算采用R(x)/O(x)中的多项式：$L'(s) = o_1(s) + r_1(s) + r_5(s)+ ...$L′(s)=o1​(s)+r1​(s)+r5​(s)+...

2. 输入/输出，换位 ：$O(s) \times R(s) = L(s)$O(s)×R(s)=L(s) （证明者，提供证明时，只是交换O/L的位置，同样能通过验证）

3. 重用同样的输入: $L(s) \times L(s) = O(s)$L(s)×L(s)=O(s) （证明者，提供证明时，用L(s)代替R(s) ，同样能通过验证）

解决上述问题的简单的做法，分别对L(x)/R(x)/O(x)使用不同的$\alpha$α对。

通用版本4 - 限定变量

细心一点会发现，之前的协议并没有限制证明者使用“一致”的变量的取值。也就是说，证明者，可以在计算L(x), R(x), O(x)的时候，使用不同的$v_i$vi​。

如何限制证明者使用同样的变量值？还是采用"$\alpha$α对"的思想，将多项式“累积”在一起，先用统一一个偏移进行限制。

$e(g^{v_{L,i}\cdot l_i(s)}\cdot g^{v_{R,i} \cdot r_i(s)}\cdot g^{v_{O,i}\cdot o_i(s)}, g^\beta) = e (g^{v_{\beta, i}\cdot \beta (l_i(s)+r_i(s)+o_i(s))}, g)$e(gvL,i​⋅li​(s)⋅gvR,i​⋅ri​(s)⋅gvO,i​⋅oi​(s),gβ)=e(gvβ,i​⋅β(li​(s)+ri​(s)+oi​(s)),g)

如果$v_{L,i}=v_{R,i}=v_{O,i}=v_{\beta, i}$vL,i​=vR,i​=vO,i​=vβ,i​的话，显然表达式成立。但是，在一些场景下，比如证明者知道L(x)=R(x)的情况下，不需要变量相等，等式也能成立。

$(V_{L,i}\cdot l_i(s) + V_{R,i}\cdot r_i(s) + V_{O,i}\cdot o_i(s))\cdot \beta = V_{\beta, i}\cdot \beta \cdot (l_i(s) + r_i(s) + o_i(s))$(VL,i​⋅li​(s)+VR,i​⋅ri​(s)+VO,i​⋅oi​(s))⋅β=Vβ,i​⋅β⋅(li​(s)+ri​(s)+oi​(s))

假设$w=l(s)=r(s)$w=l(s)=r(s)，并且$y=o(s)$y=o(s)：

$\beta(v_L w+ v_R w + v_O y) = v_{\beta}\cdot \beta(w+w+y)$β(vL​w+vR​w+vO​y)=vβ​⋅β(w+w+y)

证明者，知道这些信息，要让等式成立，可以让$v_{\beta} = v_{O}, v_{L} = 2v_O - v_R$vβ​=vO​,vL​=2vO​−vR​。也就是存在可能性，不同的变量值，验证等式依然成立。

进一步优化验证等式，让每个变量采用不同的偏移，记为$\beta$β对：

• Setup
  • 额外随机生成$\beta_l, \beta_r, \beta_o$βl​,βr​,βo​
  • 额外计算$\{g^{\beta_l l_i(s)+\beta_r r_i(s)+\beta_o o_i(s)}\} i\in \{1...n\}${gβl​li​(s)+βr​ri​(s)+βo​oi​(s)}i∈{1...n}
• Prove
  • 额外计算$g^{Z(s)} = \sum_{i=1}^{n}g^{z_i(s)} = g^{\beta_l L(s) + \beta_r R(s) + \beta_o O(s)}$gZ(s)=∑i=1n​gzi​(s)=gβl​L(s)+βr​R(s)+βo​O(s)
• Verification
  • 验证等式：$e(g^L, g^{\beta_l})\cdot e(g^R, g^{\beta_r}) \cdot e(g^O, g^{\beta_o}) = e(g^Z, g)$e(gL,gβl​)⋅e(gR,gβr​)⋅e(gO,gβo​)=e(gZ,g)

因为:

$L\cdot \beta_l + R\cdot \beta_r + O\cdot \beta_o = \sum_{i=0}^n v_il_i(s)\beta_l + v_i r_i(s) \beta_r + v_i o_i(s) \beta_o$L⋅βl​+R⋅βr​+O⋅βo​=i=0∑n​vi​li​(s)βl​+vi​ri​(s)βr​+vi​oi​(s)βo​

$= \sum_{i=0}^n v_i(l_i(s)\beta_l + r_i(s) \beta_r + o_i(s) \beta_o)$=i=0∑n​vi​(li​(s)βl​+ri​(s)βr​+oi​(s)βo​)

既然，L/R/O采用通用的变量值v，则L+R+O，可以看成合并的一个多项式。为了避免证明者利用L/R/O的关系，伪造证明，使用多个$\beta$β对。

也就是说，$\alpha$α对限制计算是按照指定的多项式乘加，$\beta$β对限制计算采用同样的变量值。

通用版本5 - 不可变形

上述的协议还存在两种变形问题：

1/ 变量的多项式变形：$\alpha$α对限制了计算是按照指定的多项式乘加。比如说，L是多个$l_i(x)$li​(x)乘加。但是因为证明者知道$g^{l_i(x)}$gli​(x)和$g^{\alpha}$gα，可以从验证者提供的信息构造$g^{l_i(x)+1}$gli​(x)+1。

2/ 变量取值变形：$\beta$β对虽然限制了计算需要是$l_i(x) + r_i(x) + o_i(x)$li​(x)+ri​(x)+oi​(x)的形式，但并没有限制在证明数据上同时偏移。

这些变形的问题，因为证明者完全知道$\beta$β的加密结果。解决的办法是：引入$\gamma$γ，进一步隐藏$\beta$β的加密结果。

• Setup
  • 额外随机生成$\beta_l, \beta_r, \beta_o, \gamma$βl​,βr​,βo​,γ
  • 额外设置验证**：$g^{\beta_l \gamma},g^{\beta_r \gamma},g^{\beta_o \gamma},g^{\gamma}$gβl​γ,gβr​γ,gβo​γ,gγ
• Prove
  • 额外计算$g^{Z(s)} = \sum_{i=1}^{n}g^{z_i(s)} = g^{\beta_l \gamma L(s) + \beta_r \gamma R(s) + \beta_o \gamma O(s)}$gZ(s)=∑i=1n​gzi​(s)=gβl​γL(s)+βr​γR(s)+βo​γO(s)
• Verification
  • 验证等式：$e(g^L, g^{\beta_l \gamma})\cdot e(g^R, g^{\beta_r \gamma}) \cdot e(g^O, g^{\beta_o \gamma}) = e(g^Z, g^{\gamma})$e(gL,gβl​γ)⋅e(gR,gβr​γ)⋅e(gO,gβo​γ)=e(gZ,gγ)

通用版本6 - 优化配对计算个数

上一个协议需要4个配对函数的计算。皮诺曹协议（Pinocchio protocol ）通过对L/R/O，使用不同的生成元，减少了配对函数的计算。

• Setup
  • 随机生成$\alpha_l,\alpha_r, \alpha_o, \beta, \gamma，\rho_l, \rho_r$αl​,αr​,αo​,β,γ，ρl​,ρr​，并设置$\rho_o = \rho_l \cdot \rho_r$ρo​=ρl​⋅ρr​
  • 生成三个生成元：$g_l=g^{\rho_l}, g_r=g^{\rho_r}, g_o=g^{\rho_o}$gl​=gρl​,gr​=gρr​,go​=gρo​
  • 设置证明**：$\{g^{s^k}\}_{k\in d}, \{g_l^{l_i(s)},g_r^{r_i(s)}, g_o^{o_i(s)}, g_l^{\alpha_l l_i(s)},g_r^{\alpha_r r_i(s)}, g_o^{\alpha_o o_i(s)},g_l^{\beta l_i(s)},g_r^{\beta r_i(s)}, g_o^{\beta o_i(s)}\}${gsk}k∈d​,{glli​(s)​,grri​(s)​,gooi​(s)​,glαl​li​(s)​,grαr​ri​(s)​,goαo​oi​(s)​,glβli​(s)​,grβri​(s)​,goβoi​(s)​}
  • 设置验证**：$g_o^{t(s)}, g^{a_l}, g^{a_r}, g^{a_o}, g^{\beta \gamma},g^{\gamma}$got(s)​,gal​,gar​,gao​,gβγ,gγ
• Prove
  • 额外计算$g^{Z(s)} = \prod_{i=1}^n(g_l^{\beta l_i(s)}\cdot g_r^{\beta r_i(s)}\cdot g_o^{\beta o_i(s)})^{v_i}$gZ(s)=∏i=1n​(glβli​(s)​⋅grβri​(s)​⋅goβoi​(s)​)vi​
• Verification
  • 验证是否采用指定的多项式：$e(g_l^{L'},g) = e(g_l^L, g^{\alpha_l})$e(glL′​,g)=e(glL​,gαl​)，同样检查R和O
  • 验证是否采用一致的变量值：$e(g_l^L \cdot g_r^R \cdot g_o^O, g^{\beta \gamma}) = e(g^Z, g^{\gamma})$e(glL​⋅grR​⋅goO​,gβγ)=e(gZ,gγ)
  • 验证计算是否成立：$e(g_l^L, g_r^R) = e(g_o^t, g^h)\cdot e(g_o^O, g)$e(glL​,grR​)=e(got​,gh)⋅e(goO​,g)

在理解了皮诺曹协议的基础上，再看Groth16算法，就比较简单了。

总结：

1. 协议都是建立在多项式基础上。
2. 多项式分解，提供了一个能证明证明者知道一个满足一定条件多项式的方法。为了能让这种方法工作需要其他一些条件：
   1. 同态加密：随机数以及对应多项式的各个项都能加密的同时，还能进行乘法和加法的计算。同态加密的作用是防止证明者能反推随机数，直接伪造证明。同时还能在加密数据的基础上提供证明者需要的计算。
   2. "$\alpha$α对"保证证明者的计算都是在加密数据乘法和加法的基础。也就是说，证明者的计算是基于多项式的。
   3. 双线性映射，能让两个加密数据映射成原始数据乘积的加密结果。
3. zk的实现反倒简单。在证明数据上进行一个偏移。保证证明者的原始数据不泄漏。
4. Trusted Setup生成初始的参数。
5. $\alpha$α参数限制多项式形式。$\beta$β参数保证多个多项式采用同样的系数。$\gamma$γ参数防止多项式偏移。