Why and How zk-SNARK Works: Definitive Explanation（2）

引用：https://zhuanlan.zhihu.com/p/103167410

通用的零知识证明

计算

一段用伪代码写的简单程序

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

从高处看，这段程序和我们协议里面的多项式并没有什么关系。现在就需要找到一种方式来将程序转换成多项式。第一步是将程序转换成数学语言，这个相对简单一些，声明可以表达成下面的形式（假定 w 是 0 或 1）：

f(w,a,b) = w(a · b)+(1-w)(a+b)​

执行 calc(1, 4, 2) 和对 f (1, 4, 2) 求值都可以得到相同的结果：8。如果执行 calc(0, 4, 2) 和 f(0,4,2) 也都能够得到 6。其实我们可以用这种方法表达任何形式的有限程序。

接下来（上面的例子）需要我们证明的是,对于表达式 f(w,a,b) ，输入为 (1, 4, 2) 时输出为 8，换句话说，我们要校验多项式：

w(a · b)+(1-w)(a+b) = 8​

单个基本计算

尽管已经将程序转换成了由数学语言表达的一般计算形式，我们还是需要再把它翻译成多项式。我们先来仔细研究一下计算的本质。任何计算的内核都是由以下形式的基本运算组成的： 左操作数 运算操作符 右操作数 = 输出​

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

多项式的算术性质

我们先来看一下如何将多项式和算术运算关联起来。例如有两个多项式f(x)和g(x)，尝试将他们相乘使得h(x) =f(x) ×g(x)，在任意一个 x=r 处 h(x) 的计算结果都是 f(r) 和 g(r) 的乘积。再看一下如下两个多项式 f(x)=2x^2-9x+10 和 g(x)=-4x^2+15x-9 。当 x = 1 时f(1) = 2 – 9 + 10 = 3,g(1) = – 4 + 15 – 9 = 2。把两个多项式相乘： h(x)=f(x)\cdot g(x)=-8x^4+66x^3-193x^2+231x-90 。x = 1 时，计算 f(x) × g(x) 结果为：h(1) = – 8 + 66 – 193 + 231 – 90 = 6，也就是说当 x = 1时，h(x) 就是 f(x) 和 g(x) 相乘的结果 ，在 x 取其它值的时候也一样。

同样的如果我们将 f(x) 和 g(x) 相加，在 x=1 处的计算结果就是 5。

如果我们可以将操作数的值表示为多项式(我们也确实可以这么做)，那么利用算术属性，我们就能够得到操作数的计算结果了。

“任何多项式在任意点的计算结果都可以看做是其唯一身份的表示。”反过来当我们知道某个多项式的时候，是不是也就意味着我们知道多项式上某个点的取值。这就是借助多项式来完成证明的依据。

限制运算

如果 prover 声称具有两个数字相乘的结果，那么 verifier 将如何检查？ 为了证明单个计算的正确性，我们就必须首先确保所提供的操作数的输出（结果）的正确性。我们再来看一下运算的形式：

左操作数 运算符 右操作数 = 输出​

类似得我们也可以将其表示为一个运算多项式

l(x) 运算符 r(x) = o(x)​

在一些选定的取值 a 处的运算:

• l(x) — 表示（运算结果为）左操作数
• r(x) — 表示（运算结果为）右操作数
• o(x) — 表示运算结果（输出）

因而在计算过程中如果操作数和结果都可以用多项式的形式正确地表示出来，那么l(a) operator r(a) = o(a)就能够成立。也就是说假如输出多项式o(x)所代表的值是由运算符在操作数多项式 l(x) 和 r(x) 上进行乘法运算得出的正确结果，那么我们把输出多项式o(x) 放到等式的左边就能够得到：l(a) operator r(a) – o(a) = 0，这也就表明了当取值为a时多项式 l(x) operator r(x) – o(x)计算结果为 0 。那么只要多项式是有效的，运算多项式就一定有一个根a。因此，根据前面的基础这个多项式里面一定包含因式(x-a)（可以看因式分解一节），这就是我们要证明的目标多项式，即t(x) =x – a。

例如，我们来看一个运算：3×2=6。可以用一个简单的多项式表示它： l(x) = 3x, r(x) = 2x, o(x) = 6x，取 a=1 进行计算，即 l(1) = 3；r(1) = 2；o(1) = 6。这个运算多项式就变成了：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^2-4x=0：

这个多项式并没有x=1 的解，因而l(x) ×r(x) –o(x) 就不能被t(x)整除。因而 verifier 不能接受这个不一致的计算结果。

前面的协议中，我们要证明的多项式是 p(x) = t(x)h(x)，这里我们修改 p(x)，使得 p(x) = l(x)r(x)-o(x)。这里t(x)目标多项式的根就是对应能够计算出数学表达式的值的 x。

上面例子里面取 x=1 这个特殊值作为运算编码的位置。当然这里的 1 可以换成任何别的值，比如说换成 x=2，3，或101 等等。在[GGPR]与[PHGR]论文中，这个取值是一个随机值，被称为 “root”。

运算的证明

现在我们来修改一下最新协议使它支持单个乘法计算的证明。回到前面多项式的 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 的验证就可以转换成：

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

• 证明
  • 分配对应的系数给 l(x),r(x),o(x)
  • 计算多项式 h(x)=\frac{l(x)+r(x)-o(x)}{t(x)}
  • 使用 \{g^{s^i}\}_{i\in[d]} 计算加密多项式 g^{l(s)},g^{r(s)},g^{o(s)},g^{h(s)}
  • 使用 \{g^{\alpha s^i}\}_{i\in \{0,...,d \}} 计算加密多项式 g^{\alpha l(s)},g^{\alpha r(s)},g^{\alpha 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)})
• 验证
  • 定义证明 π 为 (g^l,g^r,g^o,g^h,g^{l'},g^{r'},g^{o'})
  • 检查多项式约束 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(g^l,g^r)=e(g^{t(s)},g^h)\cdot e(g^o,g)

这个协议就能够证明两个值相乘的计算结果是正确的了。注意到了在这个新的协议中我们放弃了零知识部分。这么做是为了简化协议的变换。后面的章节我们会再变回零知识。

多个运算

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

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

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

我们再来看一个有三个乘法运算的例子 2 × 1 × 3 × 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)。

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

多项式插值。

为了构造操作数和输出多项式，我们需要一种方法来用给定的一组点去构造一个能经过所有这些点的弯曲多项式，这叫插值。有几种不同的方法可以算出这个多项式：

• 一组未知方程
• 牛顿多项式
• 内维尔算法
• 拉格朗日多项式
• 快速傅里叶变换

我们以第一个方法为例。这个方法的思路是存在一个系数未知 ，阶数至多为 n 的特定的多项式 p(x) 能够经过给定的 n+1 个点，对于每个点 {(xᵢ, yᵢ)}, i ∈ [n+1]来说，多项式在 xᵢ 处的计算结果都等于 yᵢ，即对于所有的 i，p(xᵢ) = yᵢ 。在我们的例子中，三个点就可以变成一个用以下形式所表示的阶数为 2 的多项式：ax2 + bx +c =y。

我们令左运算多项式（绿色标出的）在每个点处与多项式结果值相等，然后对每个系数用其它术语表示出来再计算等式：

因而左操作数多项式就是： {\color{Green}{l(x)}}= 2x^2-6x+6

它和下面的图对应：

我们用相同的方式再计算r(x) 和o(x)：

含有多个运算的多项式

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

第一步将l(x)和r(x)相乘得到结果：

第二步：从l(x) ×r(x) 的结果中将o(x) 减去：

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

通过长除法可以算出 h(x)，代入h(x) = – 3x+ 4，verifier 可以计算t(x)h(x)：

现在显然 l(x) ×r(x) –o(x) =t(x)h(x) ，这就是我们要证明的内容。

变量多项式

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

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

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

然而，因为我们的协议中是允许 prover 为多项式设置任何系数的，所以他可以不受限制得为不同计算（即，用一些x表示的多项式）中的a设置不同的值。这个自由打破了一致性，有空间允许 prover 能去证明了一些并非 verifier 感兴趣的其它无关的程序执行。因而我们必须要确保每一个变量在所有运算中出现的地方都只有一个取值。

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

单个变量的操作数多项式

我们来看一个简单的例子（就是当前的例子），在左操作符多项式 l(x) 表示的所有左操作数中只包含一个变量（即 a）。我们要找出是否有可以确保这个多项式在每一个运算中 a 都相同的方法。prover 可以设置不同值是因为他可以任意控制 x 的每个次幂的系数。因而如果这些系数是固定的，就可以解决问题了。

我们来仔细看看包含相等值的多项式。例如检查一下下面两个多项式，他们分别都表示了有两个相等值对应的运算（即在 x=1 和 x=2 处），这里第一个多项式的值为 1，第二个多项式的值为 2：

注意每个多项式中相应的系数是成比例的，也就是第二个多项式的系数是第一个的两倍大，即：2x^2-6x+6=2(x^2-3x+3)

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

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

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

和限制单个求幂值相似，verfier 可以一次限制完整的多项式。而不只是提供单独的加密 g^{s^1},g^{s^2},...,g^{s^d} 及其它们的α-移位 g^{\alpha s^1},g^{\alpha s^2},...,g^{\alpha s^d} 。

那么协议的过程就是：

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

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

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

然后再让 prover 在其上”分配“一个值 a ：

Remark 4.1 由于 verification key 包含了加密了的 α，所以可以用多项式加（或者减）任意一个值 v'，即：

因而可以修改多项式使其超出 verifier 的预期以及证明一个不同的声明，后面的章节我们将会解决掉这个问题。

多变量的操作数多项式

因为只有当所有的左操作数使用同一个变量的时候我们才可以设置一个值。但是如果左操作数中再多一个值d要怎么做呢：

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

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

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

于是我们就可以将每个变量分开设置值，然后把他们加在一起来计算出操作数多项式，例如当a = 3和d= 2时：

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

现在起我们用大写字母来表示这个复杂的操作符多项式，即 L(x)=al_a(x)+dl_d(x)

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

• Setup
  • 构造 l_a(x) ​， l_d(x)​ ，使得它能够在对应的 “计算 x” 处为 1，在其他地方为 0。
  • 选择随机数 s​，α​
  • 计算并加密未赋值的变量多项式： g^{l_a(s)} ​，​ g^{l_d(s)}
  • 计算变换后的这些多项式： ​ g^{\alpha l_a(s)} ，​ g^{\alpha l_d(s)}
  • 设置 proving key：​ (g^{l_a(s)},g^{l_d(s)},g^{\alpha l_a(s)},g^{\alpha l_d(s)})
  • 设置 verification key：​ (g^\alpha)
• Proving
  • 为变量多项式赋值 a 和 d： (g^{l_a(s)})^a ​，(g^{l_d(s)})^d​
  • 对变换后的变量多项式做同样的赋值： (g^{\alpha l_a(s)})^a ，​ (g^{\alpha l_d(s)})^d
  • 把所有赋值好的变量多项式加起来变成操作数多项式的形式：​ g^{L(s)}=g^{al_a(s)}\cdot g^{dl_d(s)}=g^{al_a(s)+dl_d(s)}
  • 将移位赋值变量多项式相加即可形成移位操作数多项式: g^{\alpha L(s)}=g^{a\alpha l_a(s)}\cdot g^{d\alpha l_d(s)}=g^{\alpha (al_a(s)+dl_d(s))}
  • 提供左操作数的有效证明：​ (g^{L(s)},g^{\alpha L(s)})
• Verification
  • 解析证明为 (g^L,g^{L'})
  • 验证提供的多项式是否是最初提供的多个未赋值的变量多项式 的和： e(g^{L'},g)=e(g^L,g^\alpha) ​ 这里也就是验证了 ​ \alpha al_a(s)+\alpha dl_d(s)=\alpha (al_a(s)+dl_d(s))

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

结果，prover ：

• 除了“分配”值外，不能再修改它们的系数进而来修改变量多项式 了，因为 prover 只拿到了这些多项式的加密值，也因为 s 必要次幂的加密值不能与它们的 α 变换值一起使用。
• 不能通过另一个多项式相加去提供一个结果因为这样 α-比例关系将会被破坏掉。
• 不能通过与其他的一些多项式 u(x) 相乘来修改操作数多项式，这样可能会使得修改后的值不成比例因为在预配对空间中无法进行加密乘法。

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

• 当 prover 决定不加入一些变量多项式 lᵢ(x) 来构造操作符多项式 L(x) 时依然是可以接受的，因为这和为它分配值为 0 是一样的：g^{\alpha l_a(x)}=g^{al_a(x)+0l_d(x)}
• 如果 prover 添加同一个变量多项式多次也是可以接受的因为这和一次分配多个值的和是一样的：g^{al_a(x)}\cdot g^{al_a(x)}\cdot g^{al_a(x)}=g^{3al_a(x)} 这些方法在右操作数和输出操作数 R(x) ，O(x) 上也同样适用。

计算实例

有了一组通用的运算结构，我们就可以将我们原始的程序（上一篇文章中的例子）转换成一组运算，然后再转换成多项式的形式。我们先来想一下算法的数学形式（用变量v表示运算结果） \omega \times(a\times b)+(1-\omega)\times(a+b)=v

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

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

我们还可以再增加一条约束使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)，它必须确保这三个运算都能被正确计算。

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

我们准备通过多项式去证明计算，首先，选择函数的输入值，例如： w= 1, a= 3, b= 2。其次，计算过程中的中间变量值为：

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

我们需要去证明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)是它的因式，假如使用了和它不一致的变量值，情况就不是这样了。

可验证计算协议

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

• Setup
  • 为左操作数 \{l_i(x)\}_{i\in\{1,..,n\}} 构造变量多项式 然后对于所有 j\in\{1,...d\} 的运算都算出其对应的系数，即 l_i(j)=c_{L,i,j} ，对右操作数和输出也做同样的事情。
  • 随机抽取 s，α​
  • 计算 t(x)= (x-1)(x-2)…(x-d) 及其结果 g^{t(s)}
  • 计算 proving key： (\{g^{s^k}\}_{k\in[d]},\{g^{l_i(s)},g^{r_i(s)},g^{o_i(s)},g^{\alpha l_i(s)},g^{\alpha r_i(s)},g^{\alpha o_i(s)}\}_{i\in\{1,......,n\}})
  • 计算 verification key： (g^{t(s)},g^\alpha)
• Proving
  • 计算函数 f(*) 以此计算相应的变量 \{v_i\}_{i\in\{1,..,n\}}
  • 计算 h(x)=\frac{L(x)\times R(x)-O(x)}{t(x)} ​，其中 L(x)=\sum^n_{i=1}v_i\cdot l_i(x) ，R(x)​, O(x)​与之相似
  • 给变量赋值并对操作数多项式求和： g^{L(s)}=(g^{l_1(s)})^{v_1}...(g^{l_n(s)})^{v_n},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}
  • 对变换后的多项式赋值： g^{\alpha L(s)}=\prod^n_{i=1}(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}
  • 使用 s 的幂加密值： \{g^{s^k}\}_{k\in[d]} 计算加密值 ​ g^{h(s)}
  • 生成证明：​ (g^{L(s)},g^{R(s)},g^{O(s)},g^{h(s)},g^{\alpha L(s)},g^{\alpha R(s)},g^{\alpha O(s)})
• Verification
  • 解析证明为 ​ (g^L,g^R,g^O,g^h,g^{L'},g^{R'},g^{O'})
  • 检查可变多项式约束： 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(g^L,g^R)=e(g^t,g^h)\cdot e(g^O,g)

操作数和输出的不可交换性

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

• 使用其它的操作数中的可变多项式，即 L'(s)=o_1(s)+r_1(s)+r_5(s)+...
• 完全交换操作数多项式， 也就是把 O(s) 和 L(s) 换成 O(s) × R(s) = L(s)
• 复用相同的操作数多项式，即 L(s) × L(s) = O(s)

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

• Setup …
  • 选择随机数 \alpha_l,\alpha_r,\alpha_o 来代替 ​α
  • 计算其对应的 “变换” ​ \{g^{\alpha_l l_i(s)},g^{\alpha_rr_i(s)},g^{\alpha_oo_i(s)}\}|_{i\in\{1,...,n\}}
  • proving key：​ (\{g^{s^k}\}_{k\in[d]},\{g^{l_i(s)},g^{r_i(s)},g^{o_i(s)},g^{\alpha_ll_i(s)},g^{\alpha_rr_i(s)},g^{\alpha_oo_i(s)}\}_{i\in\{i,...,n\}})
  • verfication key：​ (g^{t(s)},g^{\alpha_l},g^{\alpha_r},g^{\alpha_o})
• Proving …
  • 为 “变换”的多项式赋值：​ g^{\alpha_l L(s)}=\prod^n_{i=1}(g^{\alpha_l l_i(s)})^{v_i},g^{\alpha_r R(s)}=\prod_{i=1}^n(g^{\alpha_r r_i(s)})^{v_i},g^{\alpha_o O(s)}=\prod_{i=1}^n(g^{\alpha_o o_i(s)})^{v_i}
  • 设置证明：​ (g^{L(s)},g^{R(s)},g^{O(s)},g^{h(s)},g^{\alpha_l L(s)},g^{\alpha_r R(s)},g^{\alpha_o O(s)})
• Verification… …
  • 可变多项式约束验证：​ e(g^{L'},g)=e(g^L,g^{\alpha_l}),e(g^{R'},g)=e(g^R,g^{\alpha_r}),e(g^{O'},g)=e(g^O,g^{\alpha_o})

这样就不能在一个操作数中使用其它操作数的变量多项式了，因为 prover 没有办法去获知 \alpha_l,\alpha_r,\alpha_o 来满足 \alpha_s 变换关系。

通过对l(x),r(x)和o(x) 进行分开 KEA 检查，就解决了上篇文章中提出的第二个缺陷问题——由于 prover 生成的证明中只有计算结果，左操作数，右操作数，输出在计算中混用也不会被发现。

跨操作数的变量一致性

对于任意的变量 vᵢ ，我们都必须将它的值分配到每个相应操作数中的一个与之对应的变量多项式上，即：(g^{l_i(s)})^{v_i},(g^{r_i(s)})^{v_i},(g^{o_i(s)})^{v_i}

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

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

• Setup
  • … 随机数 ​ \beta_l,\beta_r,\beta_o
  • 对变量一致性多项式 进行计算，加密并添加到 proving key中：​ {g^{\beta_ll_i(s)+\beta_rr_i(s)+\beta_oo_i(s)}}_{i\in\{1,...,n\}}
  • 对 ​加密并将其加到 verification key 中：​ (g^{\beta_l},g^{\beta_r},g^{\beta_o})
• Proving
  • …将变量值赋给变量一致性多项式： g^{z_i(s)}=(g^{\beta_ll_i(s)+\beta_rr_i(s)+\beta_oo_i(s)})^{v_i}\ \ \ for \ \ \ i\in \{1,...,n\}
  • =增加分配的多项式到加密空间中: g^{Z(s)}=\prod^n_{i=1}g^{z_i(s)}=g^{\beta_lL(s)+\beta_rR(s)+\beta_oO(s)}
  • 再在证明中加入： g^{Z(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(g,g)^{\beta_lL+\beta_rR+\beta_oO}=e(g,g)^Z

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

  变量非延展性和变量一致性多项式

变量多项式的延展性

看一下下面的两个运算：

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

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

• …Proving：
  • 用分配不成比例的变量 a 来建立左操作数多项式：​ L(x)=a\cdot l_a(x)+1
  • 按照常规的方式构造右操作数多项式和输出多项式： R(x)=r_1(x),O(x)=b\cdot o_b(x)+c\cdot o_c(x) ​
  • 计算除数：​ h(x)=\frac{L(x)\cdot R(x)-O(x)}{t(x)}
  • 计算加密值：g^{L(s)}=(g^{l_a(s)})^a\cdot g^1 ​，并按照常规方式计算 g^{R(s)},g^{O(s)}
  • 计算 α-变换的加密值：​ g^{\alpha L(s)}=(g^{\alpha l_a(s)})^a\cdot g^\alpha ，并按照常规方式计算 ​ g^{\alpha R(s)},g^{\alpha O(s)}
  • 计算变量一致性多项式： g^{Z(s)}=\prod_{i\in\{1,a,b,c\}}(g^{\beta_ll_i(s)+\beta_rr_i(s)+\beta_oo_i(s)})^i\cdot g^{\beta_l}=g^{\beta_l(L(s)+1)+\beta_rR(s)+\beta_oO(s)} ，其中下标 i 代表对应变量的符号；指数 i 代表变量的值；以及未定义的变量多项式的值为 0。
  • 设置证明：​ (g^{L(s)},g^{R(s)},g^{O(s)},g^{h(s)},g^{\alpha_l L(s)},g^{\alpha_r R(s)},g^{\alpha_o O(s)},g^{Z(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)\Longrightarrow e(g,g)^{(a\cdot l_a+1)\beta_l+R\beta_r+O\beta_o}=e(g,g)^{\beta_l(L+1)+\beta_rR+\beta_oO}
  • 有效计算检查：​ e(g^L,g^R)=e(g^t,g^h)\cdot e(g^O,g)

变量一致性多项式的延展性

而且 g^{\beta_l},g^{\beta_r},g^{\beta_o} 的存在允许我们在不同操作数的相同变量上使用不同的值。例如，如果我们有一个运算：a \times a=b

可以用多项式表示：l_a(x)=x,r_a(x)=x,o_a(x)=0\ \ \ \ l_b(x)=0,r_b(x)=0,o_b(x)=x

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

• Proving：
  • …用 a=2 设置左操作数多项式：​ L(x)=2l_a(x)+10l_b(x)
  • 用 a=5 设置右操作数多项式：​ R(x)=2r_a(x)+3+10r_b(x)
  • 用 b=10 设置输出多项式：​ O(x)=2o_a(x)+10o_b(x)
  • …计算加密值： g^{L(s)}=(g^{l_a(s)})^2\cdot (g^{l_b(s)})^{10}=g^{2l_a(s)+10l_b(s)} ，g^{R(s)}=(g^{r_a(s)})^2\cdot (g)^3\cdot(g^{r_b(s)})^{10}=g^{2r_a(s)+3+10r_b(s)}， g^{O(s)}=(g^{O_a(s)})^2\cdot(g^{O_b(s)})^{10}=g^{2o_a(s)+10o_b(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)

注意：多项式 oa(x)，lb(x)，rb(x) 其实可以被忽略掉的，因为这几项对于任何 x 的取值，计算结果都为 0，但是为了保持完整性我们依然要保留这几项。

非延展性

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

相应的这种被修饰过的加密值，就能阻止使得修改加密值 Z(s) 变得不可行了，因为 Z(s) 中没有 γ，即：g^{Z(s)}\cdot g^{v'\cdot \beta_lr}=g^{\beta_l(L(s)+v'r)+\beta_rR(s)+\beta_oO(s)}

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

• Setup：
  • …随机数 \beta_l,\beta_r,\beta_o,\gamma
  • …设置 verification key：​ (...,g^{\beta_l\gamma},g^{\beta_r\gamma},g^{\beta_o\gamma},g^{\gamma})
• Proving：…
• 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)

变量值一致性检查的优化

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

• Setup
  • …选择随机值 \beta,\gamma,\rho_l,\rho_r ​并设置 ​ \rho_o=\rho_l\cdot\rho_r
  • 设置生成元 ​ g_l=g^{\rho_l},g_r=g^{\rho_r},g_o=g^{\rho_o}
  • 设置 proving key：​ (\{g^{s^k}\}_{k\in[d]},\{g_l^{l_i(s)},g_r^{r_i(s)},g_o^{o_i(s)},g_l^{\alpha_ll_i(s)},g_l^{\alpha_rr_i(s)},g_l^{\alpha_oo_i(s)},g_l^{\beta l_i(s)},g_l^{\beta r_i(s)},g_l^{\beta o_i(s)}\}_{i\in[n]})
  • 设置 verification key： (g_o^{t(s)},g^{\alpha_l},g^{\alpha_o},g^{\alpha_\gamma},g^{\beta\gamma},g^{\gamma})
• Proving
  • …分配变量值 g^{Z(s)}=\prod^n_{i=1}(g_l^{\beta l_i(s)}\cdot g_r^{\beta r_i(s)}\cdot g_o^{\beta o_i(s)})^{v_i}

Verification

• …变量多项式约束检查： e(g_l^{L'},g)=e(g_l^L,g^{\alpha_l}) ，对 ​ g_r^R,g_o^O 做同样的检查
• 变量值约束检查： e(g_l^L\cdot g_r^R\cdot g_o^O,g^{\beta\gamma})=e(g^Z,g^\gamma)
• 有效运算检查： e(g_l^L,g_r^R)=e(g_o^t,g^h)e(g_o^O,g)\Longrightarrow e(g,g)^{\rho_l\rho_r LR}=e(g,g)^{\rho_l\rho_rth+\rho_l\rho_rO}

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

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