从零开始学习 zk-SNARK（四）——多项式的约束

在上文的构造中，我们通过对 未赋值的变量多项式 的计算得到 0 或者 1 ，以此表示在运算中是否要用到这个变量。自然地想，我们也可以使用其它系数值，包括负数值，因为我们可以插值 计算出经过任何必要的点（前提是没有两个计算使用了同一个 x）的多项式。如下是这种运算的一些例子：

现在我们的程序就可以使用静态系数了，例如：

Algorithm 2: Constant coefficients
—————————————————————————————————————————————————————

function calc(w, a, b)
    if w then
        return 3a × b
    else
        return 5a × 2b
    end if
end function

在 setup 阶段这些系数类似于 0 或者 1 将被“硬编码”进去，之后就不能再修改了。现在我们将运算形式修改为：

或者更正式得用参数 vn ∈ {v1, v2, …, vn} 表示：

看一下这个新结构，很显然在多项式的表示中，每一个不同 x 所要代表的操作数都是所有操作数变量多项式 的总和，其中只有一个被用到的变量是非零值而其它都为 0，下图就很好得表达了这个意思：

我们可以利用这一个结构，加任何数量必要的变量 到每一个运算的操作符/输出中。例如在第一个运算中，我们可以首先做加法 a+c，然后就只需要用别的操作数与之相乘了，即 (a+ c) × b = r，可以表示为下图：

因而也可以将这些变量中任意个，对它们先乘以任意的系数再一并加入到一起作为单个操作数中，以此来根据相应程序的需要构造一个操作数值。这个特性实际上就允许将运算结构改为：

或者更正式一些用变量 vᵢ ∈ {v₁, v₂, …, vₙ} 和操作数变量系数

注意 ：每一个运算的操作数都有自己的一组系数 c。

到目前为止，我们一直专注于乘法操作。但是为了能够执行通用计算，真实环境下的程序也需要加法，加法和除法。

加法 在前面的章节中，我们已经确定了可以在单个操作数的内容中将变量加起来，然后和另一个操作数相乘，即(3a + b) × d = r ，但是如果我们只是想做加法，没有乘法，例如一个程序中需要做 a + b 的计算，我们可以按照下面的方式来表示：(a+b) × 1 = r

@Maksym（作者）：因为我们的结构中对于每一个操作数我们既需要常量系数也需要变量 (c ⋅ v) ，1 这个值可以表示为 c₁ ⋅ v₁，其中 c₁ = 1 可以被“硬编码”到对应的多项式中， v₁ 是一个变量可以给它分配任何值，那么我们就必须通过一些约束来限制 v₁ 的值，这个在后面的章节中将会讲到。

减法 减法与加法几乎一致，唯一的不同就是负系数， a-b 也就是：

除法 如果我们检查除法运算

可以看到除法的结果是就是我们要得到一个结果值使其乘以 divisor 能够得到 factor。所以我们也可以用乘法来表示出同一个意思：divisor × result = factor。这样就是说如果我们想要去证明除法运算 a / b= r，我们就可以把它表示为：

@Maksym（作者）：运算的结构也称为 “约束” ，因为多项式结构代表的运算，并非是为了计算出结果，而是在 prover 已经知晓的变量赋值的情况下，检验这个运算的过程是否正确。换句话说，即约束 prover 必须提供一致的值，无论这些值是什么。

所有的算术计算（加减乘除）都已经有了，于是运算结构不再需要修改。

这里有三个乘法，但是由于运算结构只支持一个乘法操作，所以这里至少就要做三次运算。但是，我们可以将它简化为:

现在要包含同样的关系只需要两个乘法。这种运算的完整形式就是：

我们还可以再增加一条约束使 w 必须为二进制数，否则 prover 就可以代入任何值去执行一个错误的运算了：

要了解为什么 w 只能为 0 或者 1，我们可以把等式表示为 w² – w = 0，也就是 (w – 0)(w – 1) = 0 这里 0 和 1 是唯一解。

现在一共有 5 个变量，以及 2 个左操作符， 4 个右操作符和 5 个输出。操作符多项式为：

在三次运算中必须为每个变量多项式都分别算出一个对应的系数或者如果这个多项式在计算的操作数或者输出中没有被用到的话系数就置为 0。

结果因式多项式就是 t(x) = (x – 1)(x –2)(x –3)，它必须确保这三个运算都能被正确计算。

接下来，我们利用多项式插值法来找到每个变量多项式：

绘制出来就是：

然后，我们把所有计算结果中的值赋值到 变量多项式 中，然后相加得到操作数或者输出多项式的形式：

把他们相加成对应运算中的操作数和输出值：

我们需要去证明 L(x) × R(x) – O(x) = t(x)h(x)，因而我们先找出 h(x)：

以图的形式表示为：

这里很明显多项式 L(x) × R(x) – O(x) 的解为 x= 1， x= 2 和 x= 3，因而 t(x) 是它的因式，假如使用了和它不一致的变量值，情况就不是这样了。

这就是一组能够正确计算的变量值，如何在多项式层面上证明出来的。下面 prover 还要再继续处理协议的密码学部分。

我们基于前文中多项式知识协议 做了很多重要的修改使它变得更通用，我们再来看一下它现在的定义。假定函数 f(*) 是要证明的问题中的计算结果，其中操作数的数量为 d ，变量的数量 n ，以及它们对应的系数为：

虽然协议足够健壮，可以进行常规的计算验证，但这里依然还有两个安全考虑需要去解决。

因为在 变量多项式约束检查 中的所有操作数上我们使用了同一个 α，所以就没有办法阻止 prover 做下面的欺骗行为：

• 使用其它的操作数中的可变多项式，即 L′(s) = o₁(s) + r₁(s) + r₁(s) + …

• 完全交换 操作数多项式， 也就是把 O(s) 和 L(s) 换成 O(s) × R(s) = L(s)

• 复用相同的操作数多项式，即 L(s) × L(s) = O(s)

可交换性就是指 prover 可以修改计算过程，并有效证明一些其它无关的计算结果。防止这种行为的一个很显然的方式就是在不同的操作数上使用不同的 α_s ，具体协议就可以修改为：

• Setup

  …
• 选择随机数 ，， 来代替 
• 计算其对应的“变换” 
• proving key：
• verfication key：
• Proving

  …
• 为 “变换”的多项式赋值：
• 设置证明：
• Verification

  …
• 可变多项式约束验证：

对于任意的变量 vᵢ，我们都必须将它的值分配 到每个相应操作数中的一个与之对应的变量多项式上，即：

因为每一个操作数运算符 的有效性是分开校验的，并不强制要求我们在对应的变量多项式 中使用相同的变量值。这就意味着在左操作数中变量 v₁ 的值可以与右操作数或输出中的变量值 v₁ 不同。

我们可以通过熟悉的限制多项式的方法（也就是限制变量多项式的方法）在操作数之间强制变量值相等。如果我们能够在所有的操作数之间创造一个作为“变换的校验和”的变量多项式，那么就可以限制 prover 使其只能够赋予相同的值。verifier 可以将这些每个变量的多项式加起来，即：

然后乘以一个额外的随机数 β，即

提供这些变换后的多项式给 prover，与变量多项式一起给它赋上变量值：

例如，一个以 l(x) = r(x) 为例的单个运算。我们用 w 来表示这两个值同时 y = o(s)。这个等式看起来就是：

因而这样一个一致性策略是无效的。缓解这种情况的一种方法是对每个操作数都使用不同的 β，确保操作数的变量多项式 中包含无法预测的值。以下就是修改后的协议：

• Setup
• … 随机数 ， ， 
• 对变量一致性多项式 进行计算，加密并添加到 proving key 中：
• 对  加密并将其加到 verification key 中：
• Proving
• …将变量值赋给变量一致性多项式：
• 增加分配的多项式到加密空间中:
• 再在证明中加入：
• Verification
• …校验提供的操作数多项式 和 “校验和”多项式之间的一致性：

  这相当于：

这个构造中同一个变量值就无法乱用了，因为不同的 β_s 使得相同多项式无法兼容，但是这里还存在与 remark 4.1 相同的缺陷，由于g^β_l，g^β_r，g^β_o是公开可见的，攻击者可以修改任意变量多项式的零索引系数，因为它并不依赖于 s，即，g^β_ls0= g^β_l。

变量多项式的延展性

预期的结果 b = a 和 c = 3a , 再进一步就是  c = 3b。这就是说左操作数的变量 多项式的计算结果为 la(1) = 1 和 la(2) = 3。先不管  la(x) 的形式， prover 都可以不按照上述的比例用另一个修改了的多项式 lₐ′(x) = ala(x) + 1 来给 a 赋值。这样运算就变成了  la′(1) = a+ 1 和 la′(2) = 3a+ 1, 结果也就是 b = a + 1 和 c = 3a + 1，其中 c≠3b，这意味着 a 的取值的实际意义在不同运算中是不一样的。

但是因为 prover 已经拿到了 g^α_l 和 g^β_l ，所以他依然能够通过正确的操作符多项式和变量值一致性的校验：

而且 gβl，gβr，gβo的存在允许我们在不同操作数的相同变量上使用不同的值。例如，如果我们有一个运算：

可以用多项式表示：

尽管我们期待的输出是 b= a²，但我们可以设置不同的 a 值，例如：设置 a= 2 （左操作数中）, a= 5（右操作数中）如下：

解决延展性问题的一个方法就是，在 setup 阶段将 verification key 中加密的 βs 项与随机秘密值 γ(gamma) 相乘使其与加密值 Z(s) 不兼容：

相应的这种被修饰过的加密值，就能阻止使得修改加密值 Z(s) 变得不可行了，因为 Z(s) 中没有 γ，即：

因为变值 γ 是随机的 prover 并不知道它的值。所以这个修改就需要我们用 Z(s) 乘以 γ 来平衡协议中的变量值一致性校验等式：

• Setup：
• …随机数 ，，，
• …设置 verification key：
• Proving：…
• Verification：
• …变量值一致性检查应满足：

这里很重要的一点是我们排除了变量多项式为 0-阶的例子（即，l₁(x) = 1x⁰），否则就可以从 proving key 的变量一致性多项式 中揭露出加了密的 β 值

这个例子中当操作数/输出中的任意两项为 0 时，即，对于 l₁(x) = 1, r₁(s) = 0, o₁(s) = 0 的例子，结果就是

我们同样也可以通过修饰 α_s 项来解决变量多项式 的延展性问题。但是这就没有必要了，因为对于变量多项式 的任何修改，都需要被映射到变量的一致性多项式 中，而一致性多项式是无法修改的。

现在变量值一致性 检查是有效的，但是这里在 verification key 中增加了 4 个昂贵的配对操作和 4 个新的项。文献 [Par+13[2]] 中的 Pinocchio 协议用了一个很聪明的方法优化，通过选择不同的生成元 g ，从而对每个操作数实行“移位”：

生成元的这种随机化进一步增加了安全性，使得如 remark 4.1中描述的可变多项式 延展性无效。因为对于故意的修改，它必须要么是ρ_l, ρ_r 或者ρ_o 原始值的倍数要么就是不可直接用的加密值的倍数（假定,如上文所述我们不去处理可能曝光加密后的值的 0 阶可变多项式）。

这个优化使得 verification key 减少了两个项，并且去除了 verification 步骤中的两个配对运算。

注意：在 Jens Groth 2016 年的 paper [Gro16[3]] 中有更进一步的改进。

https://arxiv.org/pdf/1906.07221.pdf

https://medium.com/@imolfar/why-and-how-zk-snark-works-5-variable-polynomials-3b4e06859e30

https://medium.com/@imolfar/why-and-how-zk-snark-works-6-verifiable-computation-protocol-1aa19f95a5cc

长按二维码添加微信进群讨论零知识证明

info@secbit.io

安比（SECBIT）实验室