原文：<Why and How zk-SNARK Works 5: Variable Polynomials>

翻译：Scroller 中文社区

这是一个系列文章。

zkSNARK 证明原理及机制 #1：入门介绍和证明的媒介

zkSNARK 证明原理及机制 #2：多项式证明

zkSNARK 证明原理及机制 #3：非交互性和分布式可信设置

zkSNARK 证明原理及机制 #4：通用计算

变量多项式

使用第 4 部分中介绍的证明多步运算的多项式方法，我们可以一次证明许多步运算（例如百万级别甚至更多），但它有一个严重的缺陷。

对于这两步运算， a 在左运算数多项式中必须表示为：

尽管如此，因为我们的协议允许证明者为多项式设置任意系数，所以他为不同运算设置不同的 a 值时并不会受到约束，例如：

这种自由度打破了一致性，允许证明者生成验证者所不关心的其他程序的证明。因此，我们必须确保任何变量在其使用的每步运算中只能具有一个值。

注意：这里的变量不同于常规的计算机科学的定义，因为它是不可变的并且每次执行仅赋值一次。

单变量运算数多项式

请注意，对应的系数在每个多项式中成比例，因此第二个系数是第一个系数的两倍，即：

该协议如下：

证明者需要用相同的α位移来响应，因为他无法从证明密钥中恢复出α，所以保证这种位移的唯一方法是对两个加密值同时乘以相同的值。

因此证明者不能修改 l(x) 的单个系数，例如如果 l(x) = ax² + bx + c，他只能一次性将整个多项式乘以某个值 v: v ⋅ ( ax² + bx + c ) = v⋅ax² + v⋅bx + v⋅c。而乘以另一个多项式是不可行的，因为没有提供 s 的单个指数的配对和α位移。证明者不能相加或相减，因为：

我们现在有了协议，但是应该如何构建运算数多项式 l(x) 呢？由于任何整数都可以通过乘以 1 得到，因此对于相应的每步运算，多项式求值的结果应为 1，例如：

多变量运算数多项式

如果我们使用相同的方法，我们将无法为每个变量单独赋值，并且每个不同的变量将一起相乘。因此这种多项式约束只能支持一个变量。如果我们检查多项式的性质，我们会看到将多项式加在一起会得出这些多项式的不同求值。因此我们可以将运算数多项式 l ( x ) 分离为运算数变量多项式

让我们从现在开始用大写字母表示这样的复合运算数多项式，例如，

注意：L(s) 和 αL(s) 一次性表示所有变量多项式，并且由于α仅用于变量多项式的求值，因此证明者别无选择，只能使用提供的随机点求值并将相同的系数分配给原始和位移后的变量多项式。

• 除了“赋”值，证明者不能通过改变系数来修改所提供的变量多项式，因为仅提供了这些多项式的加密求值，并且无法单独使用所需的加密的 s 幂值和α位移

• 无法在所提供的多项式之上加上另一个多项式，因为α比率将被破坏

• 无法通过乘以一些其他的多项式 u(x) 来修改运算数多项式，这可能会不成比例地修改值，因为在预配对空间中无法进行加密乘法

注意：如果我们将一个多项式（例如 lₐ(x) ）加上（或减去）另一个多项式，例如，

这实际上并不是对多项式 ld(x) 的修改，而是对 la(x) 的结果系数的更改，因为它们最终会被相加起来：

• 如果证明者决定不加上某些赋值的变量多项式 lᵢ(x) 来计算运算数多项式 L(x) 是可以接受的，因为它等价于赋值 0：

• 如果证明者累加多次相同的变量多项式是可以接受的，因为它与一次性赋值若干倍数是等价的，例如：

结构特性

常数系数

算法 2：常数系数
——————————————————————————————————————————————
function calc ( w , a , b ) 
    if w then 
        return 3 a × b 
    else  
        return 5 a × 2 b 
    end  if  
end function

这些系数将在设置阶段“硬编码”，与 1 或 0 类似，将是不可变的。我们可以相应地修改运算形式：

或者更正式地说，对于变量 vᵢ ∈ {v₁ , v₂, …, vₙ }：

注意：同一变量的常数系数在不同的运算和运算数 / 输出中可能不同。

自由相加

查看更新后的结构，很明显在多项式表示中，由特定的 x 所表示的每个运算数都是所有运算数变量多项式的总和，因此只有单个用到的变量可以赋非零值，而所有其他变量均为零。下图最能形象得说明这一点：

我们可以利用这种结构，并允许为每个运算数 / 输出添加任意数量的所需变量。例如在第一步运算中，我们可以先相加 a + c， 然后再乘以其他运算数，例如 ( a + c ) × b = r，这可以表示为：

因此，可以在单个运算数中添加任意数量的变量，为其中的每一个赋值任意系数，然后相加生成在相应程序运算中使用的运算数。这种特性可以高效地将运算结构更改为：

或者按更规范的说法，对于变量 vᵢ ∈ { v₁ , v₂, …, vₙ } 和运算数变量系数

结构如下：

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

加法、减法和除法

加法：在上一小节中我们已经构建了可以在单个运算数中添加变量的结构，然后将其乘以另一个运算数，例如 (3a + b ) × d = r，但是如果我们只需要加法而不需要乘法怎么办，例如，如果程序需要计算 a + b，我们可以将其表示为：

注意：因为我们的结构对于每个运算数都有一个常数系数和一个变量 (c ⋅ v)，所以运算数 1 表示为 c₁ ⋅ v₁，而 c₁ = 1 可以“硬编码”到对应的多项式中，v₁是一个变量，可以赋任何值，因此我们必须约束 v₁的值，如下一节所述。

减法：减法几乎与加法相同，唯一的区别是负系数，例如对于 a – b：

我们会看到除法的结果是我们需要与除数相乘以产生因数的数字。因此我们可以通过乘法表示相同的意思： divisor x result = factor 。因此，如果我们要证明除法运算 a / b= r ，可以表示为：

注意：这样构建运算也称为“约束”，因为多项式构造表示的运算本身并不计算结果，而是检验证明者是否已经知道变量（包括结果），并且它们在运算中有效，即证明者必须提供一致的值，无论它们是什么。

注意：所有这些算术运算都已经存在；因此不需要修改运算的结构。

计算示例

有了通用运算的结构，我们可以将我们的原始算法 1转换为一组运算，并进一步转换为多项式形式。让我们考虑算法的数学形式（我们将使用变量 v 来代表计算结果）：

它有三个乘法，因为一步运算结构只支持一个，所以至少会有三步运算。但是，我们可以简化等式：

现在它只需要两次乘法，同时计算逻辑保持不变。完整形式的运算如下：

我们还可以添加一个约束，要求 w 是二进制的，否则证明者可以使用任何值 w 从而导致计算不正确：

我们需要证明 L(x) × R(x) – O(x) = t(x) h(x)，因此我们找到 h(x) 满足：