从零开始学习 zk-SNARK（三）——从程序到多项式的构造

Algorithm 1: Operation depends on an input————————————————————————————————————————————————————————————————————
function calc(w, a, b)           if w then              return a × b           else               return a + b           end if      end function

两个操作数（即值）与一个运算符（即+,–,×,÷）放在一起执行运算。例如操作数是 2 和 3，运算符为乘，那么运算出来就是 2 × 3 = 6。由于任何复杂的计算（或者程序）都是由一系列这样的基本运算组成的，所以首先我们需要知道在多项式中单个运算是怎么表示的。

• l(x) — 表示（运算结果为）左操作数

• r(x) — 表示（运算结果为）右操作数

• o(x) — 表示运算结果（输出）

这个运算多项式就变成了：

l(x) × r(x) = o(x)

3x × 2x =6x

6x² -6x =0

在图上表示为：

注意，这个多项式有一个因子 (x = 1) ：

6x² -6x = 6x(x-1)

因而如果 prover 用 l(x), r(x), o(x) 这些多项式来代替 p(x) ，因为它们依然可以被 t(x) 整除，所以 verifier 就可以认为它们是有效的。相反，如果 prover 尝试用 4 来代替输出值去欺骗 verifier ，即 o(x) = 4x，那么运算多项式就变成了 6x² – 4x= 0：

图中这个多项式并没有 x=1 的解，因而 l(x) × r(x) – o(x)  就不能被 t(x) 整除：

现在我们来修改一下最新协议使它支持单个乘法计算的证明。回到前面多项式的 SNARK一章，我们已经能够证明多项式 p(x) 的知识了，只不过现在要计算的是三个多项式 l(x), r(x), o(x)的知识。我们可以定义 p(x) = l(x) × r(x) – o(x)，但这里存在两个争议点。首先，在我们的协议中证明阶段是不能做加密值乘法计算的（即， l(s) × r(s)），因为配对只能用一次，这个要用在校验多项式的约束上。第二，这里给证明者留下了一个可以修改多项式结构但依然保留有效因式 t(x) 的机会，例如可以令 p(x) = l(x) 或者  p(x) = l(x) – r(x) 甚至是 p(x) = l(x) × r(x) + o(x)，只要这里的 p(x) 还保留着根 a 就可以了。这个修改本质上是让证明的内容变成了别的声明，所以这样是不行的。

所以  prover  必须要分别提供多项式 l(s), r(s), o(s) 值的证明，即协议必须修改要证明的多项式的知识。verifier 在加密空间中要验证的是  l(s) × r(s) – o(s) = t(s)h(s)。verifier 可以使用密码学配对来执行乘法，但还有一个小问题就是做减法(– o(x))是非常昂贵的计算（这需要去找到一个 gᵒ⁽ˢ⁾ 的逆向转换），这里我们可以把 o(x) 移到等式右边来：l(x)r(x) = t(x)h(x) + o(x)。在加密空间中，verifier 的验证就可以转换成：

e(g^l(s), g^r(s)) = e(g^t(s),g^h(s)) · e(g^o(s),g)

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)}

注意：回忆一下加密配对的结果是支持通过乘法实现加密值的相加的，参见 加密值相乘 这一章节

保持 setup 阶段不变，协议更新为：

现在我们已经能够证明单个算术运算了，但是要怎么扩展到多个运算上呢（这是我们的最终目标）？我们来尝试一下增加一个基本运算。想一想计算 a × b × c 乘积的需求，在元素操作模型中，这代表着两个操作：

a × b = r₁

r₁ × c = r₂

前面的讨论中我们通过对运算符多项式在任意取值 x 处 ，例如1，计算一个对应值，来表示一个操作数或者结果。有了这个性质的多项式并不会约束我们在不同 x 取值处用多项式来表示其他值。如示例中的 2，即：

这种独立性允许我们一次同时执行 两个运算并且又不会把这两者搞乱，即相互之间不会妨碍。这个多项式算术的结果就变成了：

我们要把它们表示为操作数多项式，对于由 x ∈ {1, 2, 3}  所表示的计算， l(x) 相应的要等于 2，2 和 6。即通过点 (1, 2), (2, 2), (3, 6)，同样的 r(x) ∋ (1, 1),(2, 3),(3,2) ，o(x) ∋ (1, 2), (2, 6), (3, 12)。

但是，我们要怎么找到经过这些点的多项式呢？对于任何包含超过一个点的例子，就必须要使用特定的数学方法了。

• 一组未知方程

• 牛顿多项式

• 内维尔算法

• 拉格朗日多项式

• 快速傅里叶变换

现在我们有了代表三个运算的操作数多项式，再进一步看一下怎么去校验每个计算的正确性。回到 verifier 寻找等式 l(x) · r(x) – o(x) = t(x)h(x) 的过程。在这个例子中，因为计算是在点 x ∈ {1, 2, 3} 处被表示出来的，所以目标多项式在这些  x_s 点处的计算结果必须为 0，换句话说， t(x)的根必须是 1，2 和 3，它的基本形式就是：

这里就已经可以看出每一个操作数相乘都对应了正确的结果。最后一步 prover 要算出一个有效因式：

通过长除法可以算出：

代入h(x) = – 3x+ 4a，verifer 可以计算 t(x)h(x)：

有了前文介绍的方法来解决证明多个计算多项式的问题，我们就可以一次证明多个运算（如上百万个甚至更多）了，但是这个方案还有一个关键的缺点。

如果证明中执行的“程序”在不同运算中使用了相同的变量作为操作数或输出，例如：

a × b = r₁

a × c = r₂

这里 a 代表两个运算中的左操作符多项式，如：

然而，因为我们的协议中是允许 prover 为多项式设置任何系数的，所以他可以不受限制得为不同计算（即，用一些 x 表示的多项式）中的 a 设置不同的值，即：

这个自由打破了一致性，有空间允许 prover 能去证明了一些并非 verifier 感兴趣的其它无关的程序执行。因而我们必须要确保每一个变量在所有运算中出现的地方都只有一个取值。

注意：文中的变量与常规的计算机科学中变量的定义不同，这里的变量是不可改变的而且每次执行都只赋值一次。