从零开始学习 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 感兴趣的其它无关的程序执行。因而我们必须要确保每一个变量在所有运算中出现的地方都只有一个取值。

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

注意每个多项式中相应的系数是成比例的，也就是第二个多项式的系数是第一个的两倍大，即：

2x²-6x+6=2×(x² -3x+3)

那么由于多项式的算术性质，如果我们想要同时地改变多项式中所有的值我们就需要改变它的比例，如果我们用一个数字乘以多项式，那么在每一个可能的 x 处的计算结果也要和相同的数字相乘（即，等比例变换）。为了验证这一点，我们尝试用 3 或者其它数字来乘第一个多项式。

因此，如果 verifier 需要在所有计算中强制 prover 设置相同的值，他就要限制 prover 只能修改比例而不是单个系数。

所以怎么保持系数比例不变呢？对于这个问题我们可以先思考一下在左运算多项式 中我们提供的证明是什么。是 l(x) 在一些秘密值 s 处的加密值：g^l(s)，即，一个被加密了的数。我们已经从 限制多项式 这一节中知道了怎样通过一个α-变换去限制 prover 只能使用 verifier 提供的 s 的幂做计算，来使得单个运算能够满足同态乘法。

和限制单个求幂值相似，verfier 可以一次限制完整的多项式。而不只是提供单独的加密及其 α-移位 g^s1,g^s2,…,g^sd,g^αs1,g^αs2,…,g^αsd。

那么协议的过程就是：

• Setup
• 使用对应的系数构造相应的操作符多项式 l(x)
• 选择随机数 α 和 s
• 使用加密的 l(s) 和它的”转换“： 来设置 proving key
• 设置 verification key：
• proving
• 乘以操作数多项式：
• 乘以变换后的操作数多项式：
• 对于操作数值 v
• 提供 操作数多项式 的乘法证明： 
• verification
• 解析证明为 
• 验证比例：

prover 需要返回同样的α-转换关系，因为无法从 proving key 中恢复出 α 所以保持这个变换的唯一方法就是用同一个值去分别乘以这两个加密值：g^l(s) 和 g^αl(s)。这个 prover 就无法修改 l(x) 的单个系数了，例如如果多项式为 l(x) = ax² + bx+ c ，prover 只可以用一个值 v 去修改整个多项式：v⋅(ax² + bx+ c) = v⋅ax² + v⋅bx+ v⋅c。配对 使其不能与另一个多项式做乘法，所以也就无法提供 s 的单个求幂值的 α-变换。prover 不能做加法或者减法因为：

这里也同样需要未加密的 α 的知识。

现在有了这个协议，不过怎么去构造操作数多项式 l(x) 呢？由于任何整数都可以通过乘以 1 得到它本身，所以多项式中对应的每个计算结果都应该为 1，即：

假如我们还使用相同的方法，我们无法分别得为每一个变量设置值，并且让这些变量乘到一起去。也就是说这个受限的多项式只能支持一个变量的情况。我们可以把操作数多项式 l(x) 分成操作数的变量多项式

这与上一节的方法一致，变量 a 和 b 可以被赋值 并分别进行约束，然后加在一起就可以表示所有的左操作数变量了。因为我们将操作数的变量多项式 加在了一起，所以我们就要能够确保在每次计算中相加后的结果只表示所有操作符多项式 中的一个。

有了这个算术性质我们就可以逐一构造操作数变量多项式 了，这样如果变量 多项式在一个对应运算中被用做操作数，那么这一项就置为 1，否则就置为 0。0 跟任何值相乘结果都是零，当把他们相加在一起的时候也就可以忽略掉这一项。在我们的例子中这些变量多项式必须满足以下计算：

l_a(1) =1,  l_a(2)=1,  l_a(3)=0

l_d(x)=0,  l_d(2)=0,  l_d(3)=1

图中表示为：

注意：我们在一个值的后面使用下标表示它代表的变量，如, 3a 是一个用 3 实例化的变量 a。

现在起我们用大写字母来表示这个复杂的 操作符多项式，即

L(x) = al_a(x) + dl_d(x)

计算结果为 L，也就是 L=L(s)。仅当每一个操作数的变量多项式 是由 verifier 约束的，结果才有效，与左多项式相关的交互应该相应得更改为：

注意：L(s) 和 αL(s) 代表所有的变量多项式并且由于 α 只用在计算变量多项式中，所以 prover 没有别的选择只能在 setup 提供的原始加密值和变换后的加密值上赋予相同的系数做计算。

结果，prover ：

• 除了“分配”值外，不能再修改它们的系数进而来修改变量多项式 了，因为 prover 只拿到了这些多项式的加密值，也因为 s 必要次幂的加密值不能与它们的 α 变换值一起使用

• 不能通过另一个多项式相加去提供一个结果因为这样 α-比例关系将会被破坏掉

• 不能通过与其他的一些多项式 u(x) 相乘来修改操作数多项式，这样可能会使得修改后的值不成比例因为在预配对空间中无法进行加密乘法

注意：如果我们加（或者减）一个多项式，如 l_a(x)，就变成了另一个的多项式，即

l'_d(x) = c_d·l_d(x)+c'_a·l_a(x)

这并非是多项式 l_d(x)  的修改，而是 l_a(x) 结果系数的变化，因为他们最终会被加到一起：

L(x)=c_a·l_a(x)+l'_d(x) =(c_a+c'_a)·l_a(x)+c_d·l_d(x)

不过尽管 prover 被限制了多项式的使用，他还有拥有一些可允许范围内的自由度：

• 当 prover 决定不加入一些变量多项式 lᵢ(x) 来构造操作符多项式 L(x) 时依然是可以接受的，因为这和为它分配值为 0 是一样的：

  g^al_a(x) = g^{al_a(x)+0l_d(x)}

• 如果 prover 添加同一个变量多项式多次也是可以接受的因为这和一次分配多个值的和是一样的：

  g^al_a(x) · g^al_a(x) · g^al_a(x)= g^3al_a(x)

这些方法在右操作数和输出操作数 R(x) ，O(x) 上也同样适用。