zk-SNARK 为什么以及如何工作（Why and How zk-SNARK Works）简体中文版

注意：本文是在《Why and How zk-SNARK Works》原译文《从零开始学习 zk-SNARK》基础上的重新翻译，原译文的翻译工作由「even@安比实验室」于 2020 年完成。本文中的译者注为原译者所加。

原文作者：Maksym Petkus

原文地址：arXiv / Medium

原译文作者：even@安比实验室

原译文地址：SECBIT Labs

原译文仓库地址：GitHub

构建

• 安装 mdbook

  cargo install mdbook
  

• 运行 mdbook serve

  mdbook serve
  

摘要

不管是原始论文 [Bit+11; Par+13] 还是原理讲解 [Rei16; But16; But17; Gab17]，其实现在已经有大量关于 zk-SNARK 的学习资源了。由于 zk-SNARK 由大量的可变模块组成，对于很多人来说它依然像一个黑盒子一样难懂。这些资料对 zk-SNARK 中的一些技术难题部分做出了解释，但由于缺少了对应的其他环节的解释，大家还是很难通过这些资料了解到 zk-SNARK 的全貌。

当我第一次了解到 zk-SNARK 技术是如何将这些东西完美地融合在一起的时候，就被数学之美震撼到了，并且随着我发现的维度越多，好奇心就越强烈。在这篇文章中，我主要基于一些实例来简洁明了地阐明 zk-SNARK，对其中的很多问题做出解释，并利用这种方式来分享我的经验，进而让更多人也能够欣赏到这项最先进的技术以及它的创新之处，最终欣赏到数学之美。

这篇文章的主要贡献是比较简洁明了地解释了 zk-SNARK 中相当复杂的技术，这些简单的解释对于在不具备任何与之相关先决知识（比如密码学和高等数学）的前提下理解 zk-SNARK 是很有必要的。文章不仅解释了 zk-SNARK 是如何工作的，还解释了为什么这样就可以工作，以及为什么选择了这样的工作方式。

前言

尽管最初计划写短一些，但现在已经写了几十页了，不过这篇文章读起来几乎不需要什么预备知识，并且你也可以随意跳过熟悉的部分。

如果你不熟悉文中使用的某些数学符号也不需要担心，文中将会对这些符号逐个进行介绍。

简介

零知识简洁的非交互式知识论证（Zero-Knowledge Succinct Non-Interactive Arguments of Knowledge，zk-SNARK）真的是一种非常精妙的方法，它可以在不揭示任何信息的前提下证明某个论断为真。但首要问题是，它为什么有用？

其实零知识证明在无数的应用中都具备优势，包括：

1）证明关于隐私数据的声明：

• 一个人 A 的银行账户金额多于 X
• 去年，一家银行未与实体 Y 进行交易
• 在不暴露全部 DNA 数据的前提下匹配 DNA
• 一个人的信用评分高于 Z

2）匿名认证：

• 在不揭露身份的情况下（比如登录密码），证明请求者 R 有权访问网站的受限区域
• 证明一个人来自一组被允许的国家 / 地区列表中的某个国家 / 地区，但不暴露具体是哪个
• 证明一个人持有地铁月票，而不透露卡号

3）匿名支付：

• 付款完全脱离任何一种身份 [Ben+14]
• 纳税而不透露收入

4）外包计算

• 将昂贵的计算外包，并在不重新执行的情况下验证结果是否正确；它开辟了一种零信任计算的类别
• 改进区块链模型，从所有节点做同样的计算，到只需一方计算，然后其他节点进行验证

和「零知识证明」这个伟大的名词一样，其背后的方法可以说是数学和密码学的奇迹。自 1985 年零知识证明这个概念在《交互式证明系统的知识复杂性》[GMR85] 一文中被引入以来，至今已经进入到第四个十年的研究。还有随后出现的非交互式零知识证明 [BFM88]，在区块链环境中尤其重要。

在任意的零知识证明（Zero-knowledge Proof）系统中，都有一个证明者（Prover）在不泄漏任何额外信息的前提下要让验证者（Verifier）确信某些陈述（Statement）是正确的。例如验证者仅能知道证明者的银行账户金额超过 X（也就是不披露实际金额）。协议应当满足下面三个性质：

• 完整性——只要陈述是正确的，证明者就可以让验证者确信
• 可靠性——如果陈述是错误的，那么作弊的证明者就没有办法让验证者相信
• 零知识——协议的交互仅仅揭露陈述是否正确而不泄漏任何其他的信息

zk-SNARK 这个术语本身是在 [Bit+11] 中引入的，它在 [Gro10] 的基础上，又遵循了匹诺曹协议（Pinocchio Protocol）[Gen+12; Par+13] 使其能够适用于通用的计算。

证明的媒介

这里我们先不去管零知识、非交互性其形式和适用性这些概念，就从尝试证明一些简单的东西开始。

想象一下我们有一个长度为 10 的位数组，现在要向验证者（例如程序）证明这样一个陈述：所有的位都被设置成了 1（即我们知道一个每个元素都等于 1 的数组）。

$$b = [\ \boxed{?}, \boxed{?}, \boxed{?}, \boxed{?}, \boxed{?}, \boxed{?}, \boxed{?}, \boxed{?}, \boxed{?}, \boxed{?}\ ]$$

验证者一次只能检查（也就是读取）一位。为了验证这个陈述，我们以某种任意的顺序读取元素并检查其是否确实等于 1。如果第一次抽样检查的结果是 1，就设置陈述的可信度为 \(\displaystyle \frac{1}{10} = 10%\)，否则，如果等于 0，就说明陈述是错误的。验证者继续进行下一轮验证，直到获得足够的可信度为止。假如在一些场景下要信任证明者需要至少 50% 的可信度，那就意味着必须执行 5 次校验。但假如在其他一些场景下需要 95% 的可信度，就需要检查所有的元素。很明显这个证明协议的缺点是必须要根据元素的数量进行检查，如果我们处理数百万个元素的数组，这么做是不现实的。

现在我们来看一下由数学方程式表示的多项式，它可以被画成坐标系上的一条曲线：

上面的曲线对应多项式：\(f(x) = x^3 -6x^2 + 11x - 6\)。多项式的阶数取决于 \(x\) 的最大指数，当前多项式的阶数是 3。

多项式有一个非常好的特性，就是如果我们有两个阶为 \(d\) 的不相等多项式，它们相交的点数不会超过 \(d\)。例如，稍微修改一下原来的多项式为 \(x^3 - 6x^2 + \mathbf{10}x - \mathbf{5}\) 并在图上用绿色标出：

这一点微小的修改就产生了变化很大的曲线。事实上，我们不可能找到两条不同的曲线，它们会在某段区域内重合（它们只会相交于一些点）。

这是从找多项式共同点的方法中得出的性质。如果要找到两个多项式的交点，就要先令它们相等。例如，要找到多项式与 \(x\) 轴的交点（即 \(f(x) = 0\)），我们就要令 \(x^3 - 6x^2 + 11x - 6 = 0\)，等式的解就是共同点：\(x = 1\)、\(x = 2\) 和 \(x = 3\)。在上面图中也可以很清晰地看出这些解，也就是图上蓝色曲线和 \(x\) 轴相交的地方。

同样，我们也可以令上文中原始的多项式和修改后的多项式相等，找到它们的交点。

$$x^3 - 6x^2 + 11x - 6 = x^3 - 6x^2 + \mathbf{10}x - \mathbf{5}$$

$$x - 1 = 0$$

多项式化简后的结果阶数为 1，它有一个很明显的解 \(x = 1\)。因此这两个多项式有一个交点。

任意一个由阶数为 \(d\) 的多项式组成的等式，最后都会被化简为另外一个阶数至多为 \(d\) 的多项式，这是因为等式中没有能用来构造更高阶数的乘法。例如：\(5x^3 + 7x^2 - x + 2 = 3x^3 - x^2 + 2x - 5\)，化简为 \(2x^3 + 8x^2 - 3x + 7 = 0\)。另外代数的基本原理也告诉我们，对于一个阶数为 \(d\) 的多项式至多有 \(d\) 个解（3.2 节将对此进行详细介绍），因此也就至多有 \(d\) 个共同点。

所以我们可以得出结论，任何多项式在任意点的计算结果（更多关于多项式求值可以参考：[Pik13]）都可以看做是其唯一身份的表示。我们来计算一下当 \(x = 10\) 时，示例多项式的结果。

$$ x^3 - 6x^2 + 11x - 6 = 504 $$

$$ x^3 - 6x^2 + 10x - 5 = 495 $$

事实上，在 \(x\) 可以选择的所有值中，至多只有三个值能够使这些多项式相等，其他的值都是不相等的。

这也是为什么如果一个证明者声称他知道一些验证者也知道的多项式（无论多项式的阶数有多大）时，他们就可以按照一个简单的协议去验证：

• 验证者选择一个随机值 \(x\) 并在本地计算多项式结果
• 验证者将 \(x\) 值提供给证明者，并让他计算相关的多项式结果
• 证明者代入 \(x\) 到多项式计算并将结果提供给验证者
• 验证者检查本地的计算结果和证明者的计算结果是否相等，如果相等就说明证明者的陈述具有较高的可信度

例如，我们把 \(x\) 的取值范围定在 1 到 \(10^{77}\)，那么计算结果不同的点的数量就有 \(10^{77} - d\) 个。因而 \(x\) 偶然「撞到」这 \(d\) 个结果相同的点中任意一个的概率就等于：\(\displaystyle \frac{d}{10^{77}}\)（几乎可以认为是不可能）。

注：与低效的位检查协议相比，新的协议只需要一轮验证就可以让声明具有非常高的可信度（如果假设 \(d\) 远小于其取值范围的上限，就几乎是 \(100%\) 了）

这也是为什么即使可能存在其他的证明媒介，多项式依然是 zk-SNARK 相对核心的部分。

译者注：这一节告诉了我们多项式的一个重要性质：我们不可能找到共享连续段的两条不相等曲线，任何多项式在任意点的计算结果都可以看做是其唯一身份的标识。也就是说只要能证明知道某个随机点对应的多项式上的值就可以证明知道这个多项式（只有知道了多项式，才能算出这个点对应的值），这个性质是下面所有证明的核心。

这就是 Schwartz–Zippel 定理，它可以扩展到多变量多项式，即在一个多维空间内形成的一个曲面。这个定理会在多个零知识证明方案的证明中反复出现。

多项式的非交互式零知识

证明多项式的知识

我们的讨论从证明多项式的知识开始，再将证明协议逐步转换成一种通用的方法，在这个过程中我们也将发现多项式的很多其他性质。

但是到目前为止，我们的协议还只是一个很弱的证明，因为协议中并没有采取任何措施去保证参与方必须按照协议的规则生成证明，所以参与方只能互相信任。例如，证明者并不需要知道多项式，也可能通过其他方式得到正确的答案。而且，如果验证者要验证的多项式的解的取值范围不够大，比如我们前文说的 10，那么就可以去猜一个数字，猜对答案的概率并不是可以忽略不计的。因而我们必须要解决协议中的这个缺陷，但在解决问题之前首先要思考一下，知道多项式意味着什么呢？一个多项式可以用下面的形式来表示（其中 \(n\) 指的是多项式的阶）：

$$c_n x^n + ... + c_1 x^1 + c_0 x^0$$

如果一个人说他或她知道一个一阶多项式（即：\(c_1 x^1 + c_0\)），那么这就意味着他或她一定知道系数 \(c_0, c_1\) 的值。这个系数可以是包括 \(0\) 在内的任意值。

假设证明者声称他知道一个包含 \(x = 1\) 和 \(x = 2\) 两个解的三阶多项式。满足此条件的一个有效的多项式就是 \(x^3 - 3x^2 + 2x = 0\)。因为对于 \(x = 1\)：\(1 - 3 + 2 = 0\)，对于 \(x = 2\)：\(8 - 12 + 4 = 0\)。

让我们先来仔细研究一下这个解的结构。

译者注：这一节告诉了我们多项式的一个本质——多项式的「知识」就是多项式的系数。所谓「知道」多项式就是指「知道」多项式的系数。

因式分解

代数的基本定理表明了任意的一个多项式只要有解，就可以将它分解成线性多项式（即一个阶数为 1 的多项式代表一条线），因此，我们可以把任意有效的多项式看成是其因式的乘积：

$$(x - a_0)(x - a_1)...(x - a_n) = 0$$

也就是说如果任意一个因式为零，那么整个等式都为零，式子中所有的 \(a\) 就是多项式的所有解。

事实上，我们的例子可以分解为以下多项式：

$$x^3 - 3x^2 + 2x = (x - 0)(x - 1)(x - 2)$$

所以这个多项式的解（\(x\) 的值）就是：\(0, 1, 2\)，在任何形式下多项式的解都可以很轻松地被验证，只不过因式的形式可以让我们一眼就看出这些解（也称为根）。

我们再回到前面的问题，证明者宣称他知道一个阶数为 3，其中两个根分别为 1 和 2 的多项式，也就是说这个多项式的形式为：

$$(x - 1)(x - 2) \cdot \ldots$$

换句话说 \((x - 1)\) 和 \((x - 2)\) 是问题中多项式的两个因式。因而如果证明者想要在不揭示多项式的前提下证明他的多项式确实有这两个根，那么他就需要去证明他的多项式 \(p(x)\) 是 \(t(x) = (x - 1)(x - 2)\)（也称为目标多项式）和一些任意多项式 \(h(x)\)（也就是我们的例子里面的 \((x - 0)\)）的乘积，即：

$$p(x) = t(x) \cdot h(x)$$

换句话说，存在一些多项式 \(h(x)\) 能够使得 \(t(x)\) 与之相乘后等于 \(p(x)\)，由此得出，\(p(x)\) 中包含 \(t(x)\)，所以 \(p(x)\) 的根中也包含 \(t(x)\) 的所有根，这也就是我们要证明的东西。

自然地算出 \(h(x)\) 的方式就是直接相除：\(h(x) = \frac{p(x)}{t(x)}\)。如果一个证明者不能找到这样一个 \(h(x)\) 也就意味着 \(p(x)\) 中不包含因式 \(t(x)\)，那么多项式相除就会有余数。

例如我们用 \(p(x) = x^3 - 3x^2 + 2x\) 除以 \(t(x) = (x - 1)(x - 2) = x^2 - 3x + 2\)：

注：左边的式子是分母，右上角的是计算结果。底部是余数（多项式相除的解释及示例可以参考 [Pik14]）。

我们算出结果 \(h(x) = x\)，没有余数。

注：为了简化起见，后面我们会用多项式的字母变量来代替计算结果值，例如：\(p = p(r)\)。

译者注：多项式可以被因式分解成它的根的因式的乘积。这个性质就意味着，如果一个多项式有某些解，那么它被因式分解后的式子中一定包含这些解的因式。

有了这个性质，我们就可以进行一些证明了。

利用多项式一致性检查协议我们就可以比较多项式 \(p(x)\) 和 \(t(x) \cdot h(x)\)：

• 验证者挑选一个随机值 \(r\), 计算 \(t = t(r)\)（也就是求值），然后将 \(r\) 发送给证明者
• 证明者计算 \(h(x) = \frac{p(x)}{t(x)}\)，并对 \(p(r)\) 和 \(h(r)\) 进行求值，将计算结果 \(p, h\) 提供给验证者
• 验证者验证 \(p = t \cdot h\) ，如果多项式相等，就意味着 \(t(x)\) 是 \(p(x)\) 的因式

实践一下，用下面的例子来执行这个协议：

$$p(x) = x^3 - 3x^2 + 2x$$

$$t(x) = (x - 1)(x - 2)$$

• 验证者选一个随机数 23，并计算 \(t = t(23) = (23 - 1)(23 - 2) = 462\)，然后将 23 发送给证明者
• 证明者计算 \(h(x) = \frac{p(x)}{t(x)} = x\), 并对 \(p(r)\) 和 \(h(r)\) 进行求值，\(p = p(23) = 10626\)，\(h = h(23) = 23\)，将 \(p, h\) 提供给验证者
• 验证者再验证 \(p = t \cdot h\)：\(10626 = 462 \cdot 23\) 是正确的，这样陈述就被证明了

相反，如果证明者使用一个并不包含必要因式的不同 \(p'(x)\)，例如 \(p'(x) = {\color{red}2}x^3 - 3x^2 + 2x\), 那么：

我们算出结果 \(2x + 3\) 和余数 \(7x - 6\)，即：\(p(x) = t(x) \times (2x + 3) + 7x - 6\)。这就意味着验证者为了计算出结果不得不用余数除以 \(t(x)\)，\(h(x) = 2x + 3 + \frac{7x - 6}{t(x)}\)。不过由于 \(x\) 是验证者随机选择的，所以余数 \(7x - 6\) 最终可以被 \(t(x)\) 整除的概率非常低（但仍然不可忽略）。如果后面验证者要另外再检查 \(p\) 和 \(h\) 必须是整数的话，这个证明就会被拒绝。

不过这个校验同时也要求多项式系数也是整数，这对协议产生了极大的限制。

这就是为什么接下来我们要介绍能够使余数不被整除的密码学原理的原因，尽管这个原始值是有可能被整除的。

注：虽然为了简化而尽可能少地使用数学符号，但如果忽视这个无处不在的基本符号「\('\)（上撇）」的话将不利于理解。这个符号的目的是为了强调一个经过初始变量变换或者推导得到的新变量。例如，如果我们想要将 \(v\) 乘以 \(2\) 并给将它赋值给一个新的变量，我们可以使用：\(v' = 2 \cdot v\)。

备注 3.1 现在我们就可以在不知道多项式的前提下根据特定的性质来检查多项式了，这就已经给了我们一些零知识和简明性的特性。但是，这个结构中还存在很多问题：

• 证明者可能并不知道他所声称的 \(p(x)\)，他可以计算 \(t = t(r)\)，然后选择一个随机值 \(h\)，由此计算出 \(p = t \cdot h\)。因为等式是成立的，所以也能通过验证者的校验。
• 因为证明者知道随机点 \(x = r\) ，所以他可以构造出一个任意的多项式，这个任意多项式与 \(t(r) \cdot h(r)\) 在 \(r\) 处有共同点。
• 在前面的陈述中，证明者声称他知道一个特定阶数的多项式，但现在的协议对阶数并没有明确的要求。因而证明者完全可以用一个满足因式校验的更高阶数的多项式来欺骗验证者。

下面我们就要逐一解决这些问题。

译者注：利用因式的性质构造出了一个证明协议，但这个协议存在一些缺陷，主要是由于：

1. 证明者知道了 \(t(r)\)，他就可以反过来任意构造一个可以整除 \(t(r)\) 的 \(p(r)\)
2. 证明者知道了点 \((r,\ t(r) \cdot h(r))\) 的值，就可以构造经过这一点的任意多项式，同样满足校验
3. 协议并没有对证明者的多项式阶数进行约束

模糊求值

备注 3.1 中的前两个问题是由于暴露了原始值而导致的，也就是证明者知道了 \(r\) 和 \(t(r)\)。但如果验证者给出的这个值像放在黑盒里一样不可见的话就完美了，也就是一个人在不破坏协议的前提下也依然可以在这些模糊的值上完成计算。这一点类似于散列函数，从计算结果很难推测出原始值。

同态加密

这也就是要设计同态加密的原因。它允许加密一个值并在密文上进行算术运算。获取加密的同态性质的方法有多种，我们来介绍一个简单的方法。

总体思路就是我们选择一个基础的（基数需要具有某些特定的属性）的自然数 \(g\)（例如 5），然后我们以要加密的值为指数对 \(g\) 进行求幂。例如，如果我们要对 3 进行加密：

$$5^3 = 125$$

这里 125 就是 3 对应的密文。如果我们想要对被加密的值乘 2，我们可以以 2 为指数来对这个密文进行计算。

$$125^2 = 15625 = \left(5^3\right)^2 = 5^{2 \times 3} = 5^6$$

我们不仅可以用 2 来乘以一个未知的值并保持密文的有效性，还可以通过密文相乘来使两个值相加，例如 3 + 2：

$$5^3 \cdot 5^2 = 5^{3 + 2} = 5^5 = 3125$$

同样的，我们还可以通过相除提取加密的数字，例如 5 - 3

$$\frac{5^5}{5^3} = 5^5 \cdot 5^{-3} = 5^{5 - 3} = 5 ^ 2 = 25$$

不过由于基数 5 是公开的，很容易就可以找到被加密的数字。只要将密文一直除以 5，直到结果为 1，那么做除法的次数也就是被加密的值。

模运算

这里就到了模运算发挥作用的地方了。模运算的思路如下：除了我们所选择的组成有限集合的前 \(n\) 个自然数（即 \(0, 1, \ldots, n - 1\)）以外，任何超出此范围的给定整数，我们就将它「缠绕」起来。例如，我们选择前六个数。为了说明这一点，可以把它看作一个有六个单位大小相等刻度的圆；这就是我们所说的范围（通常指的是有限域）。

现在我们看一下数字八应该在哪里。打个比方，我们可以把它看成一条长度为八的绳子：

如果我们将绳子固定在圆圈的开头

然后用绳子缠绕圆圈，我们在缠完一圈后还剩下一部分的绳子：

然后我们继续缠绕，这根绳子将在刻度 #2 的地方终止。

这就是模运算的结果。无论这根绳子多长，它最终都会在圆圈一个刻度处终止。因而模运算结果将保持在一定范围内（例子中是 0 到 5）。长度为 15 的绳子将会在刻度 3 的地方终止，即 6 + 6 + 3（缠两个完整的圈并剩下 3 个单位长的部分）。负数运算类似，唯一不同的地方就是它是沿相反方向缠绕的，如 -8 的取模结果是 4。

我们执行算术运算，结果都将落在这个 \(n\) 的范围内。现在开始我们将用符号「\(\mathrm{mod}\ n\)」来表示数字的范围。

$$3 \times 5 = 3 \ (\mathrm{mod}\ {6})$$

$$5 + 2 = 1 \ (\mathrm{mod}\ {6})$$

另外，模运算最重要的性质就是运算顺序无所谓。例如，我们可以先做完所有的运算，然后再取模，或者每运算完一步都去取模。例如 \((2 \times 4 - 1) \times 3 = 3 \ (\mathrm{mod}\ {6})\) 就等于：

$$2 \times 4 = 2 \ (\mathrm{mod}\ {6})$$

$$2 - 1 = 1 \ (\mathrm{mod}\ {6})$$

$$1 \times 3 = 3 \ (\mathrm{mod}\ {6})$$

那么模运算到底有什么用呢？如果我们使用模运算，从运算结果再回到原始值并不容易，因为很多不同的组合会产生同样的运算结果：

$$5 \times 4 = 2 \ (\mathrm{mod}\ {6})$$

$$4 \times 2 = 2 \ (\mathrm{mod}\ {6})$$

$$2 \times 1 = 2 \ (\mathrm{mod}\ {6})$$

$$\ldots$$

没有模运算的话，计算结果的大小会给找出原始值提供一些线索。模运算既能把这一信息隐藏起来，又可以保留常见的算术属性。

强同态加密

我们再回到同态加密上，使用模运算，例如取模 7，我们可以得到：

$$5^1 = 5 \ (\mathrm{mod}\ {7})$$

$$5^2 = 4 \ (\mathrm{mod}\ {7})$$

$$5^3 = 6 \ (\mathrm{mod}\ {7})$$

$$\ldots$$

不同指数下运算将会得到同样的结果：

$$5^5 = 3 \ (\mathrm{mod}\ {7})$$

$$5^{11} = 3 \ (\mathrm{mod}\ {7})$$

$$5^{17} = 3 \ (\mathrm{mod}\ {7})$$

$$\ldots$$

这样就很难知道指数是多少了。事实上，如果模取得相当大，从运算结果倒推指数运算就不可行了，现代密码学很大程度上就是基于这个问题的困难程度。

方案中所有的同态性质都在模运算中保留了下来：

$$\mathrm{加密：} 5^3 = 6 \ (\mathrm{mod}\ {7})$$

$$\mathrm{乘法：} 6^2 = {(5^3)}^2 = 5^6 = 1 \ (\mathrm{mod}\ {7})$$

$$\mathrm{加法：} 5^3 \cdot 5^2 = 5^5 = 3 \ (\mathrm{mod}\ {7})$$

注：模相除有点难，已经超出范围了。

我们来明确地说明一下加密函数：\(E(v) = g^v \ (\mathrm{mod}\ {n})\)，这里 \(v\) 就是我们要加密的值。

备注 3.2 这个同态加密模式有一个限制，我们可以把一个加密的值和一个未加密的值相乘，但我们不能将两个加密的值相乘（或者相除），也就是说我们不能对加密值取幂。虽然这些性质第一感觉看上去很不友好，但是却构成了 zk-SNARK 的基础。这个限制将在 3.6.1 节中讲到。

译者注：通过模运算形成的集合被称为有限域，而通过计算指数再进行模运算形成的集合构成循环群。常见的同态加密方式除了整数幂取模之外，还有椭圆曲线上的倍乘。

加密多项式

配合这些工具，我们现在就可以在加密的随机数 \(x\) 上做运算并相应地修改零知识协议了。

我们来看一下如何计算多项式 \(p(x) = x^3 - 3x^2 + 2x\)。前面已经明确了，知道一个多项式就是知道它的系数，在这个例子中也就是知道：1，-3，2。因为同态加密并不允许再对加密值求幂，所以我们必须要给出 \(x\) 的 1 到 3 次幂的加密值：\(E(x), E(x^2), E(x^3)\)，那么我们要计算的加密多项式就是：

$${E\left(x^3\right)}^1 \cdot {E\left(x^2\right)}^{-3} \cdot {E\left(x\right)}^{2} =$$

$${\left(g^{x^3}\right)}^1 \cdot {\left(g^{x^2}\right)}^{-3} \cdot {\Big( g^{x} \Big)}^2 =$$

$$g^{1x^3} \cdot g^{-3x^2} \cdot g^{2x} =$$

$$g^{x^3 - 3x^2 + 2x}$$

通过这些运算，我们就获得了多项式在一些未知数 \(x\) 处的加密计算结果。这确实是一个很强大的机制，因为同态的性质，同一个多项式的加密运算在加密空间中始终是相同的。

我们现在就可以更新前一个版本的协议了，比如对于阶数为 \(d\) 的多项式：

• 验证者

  • 取一个随机数 \(s\)，也就是秘密值
  • 令指数 \(i\) 取值为 \(0, 1, ..., d\) 时分别计算对 \(s\) 求幂的加密结果，即：\(E(s^i) = g^{s^i}\)
  • 代入 \(s\) 计算未加密的目标多项式：\(t(s)\)
  • 把对 \(s\) 求幂的加密结果提供给证明者：\(E(s^0), E(s^1), ..., E(s^d)\)

• 证明者

  • 计算多项式 \(h(x) = \frac{p(x)}{t(x)}\)

  • 使用加密值 \(g^{s^0}, g^{s^1}, \ldots, g^{s^d}\) 和系数 \(c_0, c_1, \ldots, c_n\) 计算

    $$E\left( p(s) \right) = g^{p(s)} = \left(g^{s^d}\right)^{c_d} \cdots \left(g^{s^1}\right)^{c_1} \cdot \left(g^{s^0}\right)^{c_0}$$

    然后同样计算

    $$E\left( h(s) \right) = g^{h(s)}$$

  • 将结果 \(g^p\) 和 \(g^h\) 提供给验证者

• 验证者

  • 最后一步是验证者在加密空间内检查 \(p = t(s) \cdot h\)：

  $$g^p = \left(g^h\right)^{t(s)} \quad \Rightarrow \quad g^p = g^{t(s) \cdot h}$$

注：因为证明者并不知道与 \(s\) 相关的任何信息，所以很难提出不合法但能匹配验证的计算结果。

尽管这个协议中证明者的灵活性有限，他依然可以通过其他的方式来伪造证明，无需实际使用验证者提供的 \(s\) 的幂的加密值。例如，如果证明者声称有一个满足条件的多项式，但只使用了 2 个幂值 \(s^3\) 和 \(s^1\)，这在当前协议中是不能验证的。

译者注：本节利用强同态加密这个工具，构造了一个相对较强的零知识证明协议。但是如上文所述，这里还是存在一些问题——无法验证证明者是否是真的使用了验证者提供的值来构造证明。

下一节中将会展示如何构造一个完备的多项式零知识证明协议。

限制多项式

前文提到，多项式的知识其实就是它的系数 \(c_0, c_1, \ldots, c_i\) 的知识。协议中我们是通过对秘密值 \(s\) 的幂的加密值再进行求幂来对系数进行「赋值」的（例如 \(E\left(s^i\right)^{c_i} = g^{c_i \cdot s^i}\)）。我们已经限制了证明者对 \(s\) 幂的加密值的选择，但是这个限制并不是强制的，也就是说，证明者可以使用任何可能的方法找到满足 \(z_p = \left(z_h\right)^{t(s)}\) 的值 \(z_p\) 和 \(z_h\)，再用这两个值来代替 \(g^p\) 和 \(g^h\) 交给验证者。例如随机选定的 \(r\)、\(z_h = g^r\) 和 \(z_p = \left(g^{t(s)}\right)^r\)，其中 \(g^{t(s)}\) 可以从已知的 \(s\) 的加密幂中计算出来。所以验证者需要证明者证明，他给出的 \(g^p\) 和 \(g^h\) 就是用 \(s\) 幂的加密值而不是其他值计算出来的。

我们看一个由一个变量和一个系数组成的一阶多项式 \(f(x) = c \cdot x\) 的简单例子，对应的 \(s\) 的加密值为 \(E(s) = g^s\)。这里我们要做的就是确保证明者是使用 \(s\) 的加密值，即 \(g^s\)，而不是其他值与系数 \(c\) 做同态相乘的。所以结果一定是 \(\left(g^s\right)^c\) 的形式（\(c\) 为任意值）。

解决这个问题的一种方法就是对另一个移位（Shift）的加密值做同样的运算，充当「校验和（Checksum）」的算术模拟，以确保结果是原始值的求幂值。

这是通过指数知识假设（Knowledge-of-Exponent Assumption，KEA）方法来实现的，在 [Dam91] 中有介绍，更精准地说：

• Alice 有一个值 \(a\)，她想要 Bob 对其进行任意指数的求幂（这里 \(a\) 是一个有限域群的生成元），唯一的要求是只能对 \(a\) 进行求幂，为了确保这一点，她要：

  • 选择一个随机数 \(\alpha\)
  • 计算 \(a' = a^\alpha \ (\mathrm{mod}\ {n})\)
  • 提供一个元组 \((a, a')\) 给 Bob，然后让他对这两个值执行任意的求幂运算，返回结果元组 \((b, b')\)，同时保持这里的指数「\(\alpha\)-移位」不变，即 \(b^\alpha = b' \ (\mathrm{mod}\ {n})\)

• 因为 Bob 无法从元组 \((a, a')\) 中提取 \(\alpha\) 的值，通过暴力破解也难以实现，因此就可以推断 Bob 生成有效元组的唯一方法就是执行下面的步骤：

  • 选择一个值 \(c\)
  • 计算 \(b = (a)^c \ (\mathrm{mod}\ {n})\) 和 \(b' = {(a')}^c \ (\mathrm{mod}\ {n})\)
  • 回复 \((b, b')\)

• 有了回复的元组和 \(\alpha\)，Alice 就可以验证等式：

  $$(b)^\alpha = b'$$

  $$\left(a^c\right)^\alpha = {(a')}^c$$

  $$a^{c \cdot \alpha} = {\left(a^\alpha\right)}^c$$

• 结论：

  • Bob 在元组的两个值的计算上都用了同一个指数（即 \(c\)）
  • Bob 只能用 Alice 原本的元组来保持 \(\alpha\) 关系
  • Bob 知道指数 \(c\)，因为构造有效 \((b, b')\) 的唯一方式是使用同一个指数
  • Alice 并不知道 \(c\)，这和 Bob 不知道 \(\alpha\) 的原因一样（尽管 \(c\) 是被加密的，但它的可能取值范围并没有足够大到可以保持零知识的性质，这个问题我们将在 3.5 节解决）

最后这个协议提供了一个证明给 Alice，Bob 确实是用他知道的某个值对 \(a\) 进行求幂的，而且他也不能做其他的任何操作，例如乘法、加法，因为这样就会破坏 \(\alpha\)-移位关系。

在同态加密中，求幂是对被加密值进行乘法运算。我们可以应用这个结构到一个简单的单一系数多项式 \(f(x) = c \cdot x\) 的例子中：

• 验证者选择随机值 \(s, \alpha\)，然后提供令 \(x = s\) 的一阶及其「移位」的计算值：\(\left(g^s, g^{\alpha \cdot s}\right)\)

• 证明者代入系数 \(c\) 计算：\(\left( \left(g^s\right)^c, \left(g^{\alpha \cdot s}\right)^c \right) = \left(g^{c \cdot s}, g^{\alpha \cdot c \cdot s}\right)\)

• 验证者验证：\(\left(g^{c \cdot s}\right)^\alpha = g^{\alpha \cdot c \cdot s}\)

这个结构可以限制证明者只能用验证者提供的加密的 \(s\) 进行计算，因而证明者只能将系数 \(c\) 赋给验证者提供的多项式。现在我们可以扩展这种单项式上的方法到多项式上，因为计算是将每个项的系数赋值分别计算后再同态地「相加」在一起的（这个方法是 Jens Groth 在 [Gro10] 中介绍的）。所以如果给定证明者一个指数为 \(s\) 的幂以及它们的移位的加密值，他就可以计算原始的和移位后的多项式，可以满足同样的校验。对于阶数为 \(d\) 的多项式：

• 验证者提供加密值 \(g^{s^0}, g^{s^1}, \ldots, g^{s^d}\) 和他们的变换 \(g^{\alpha s^0}, g^{\alpha s^1}, \ldots, g^{\alpha s^d}\)

• 证明者：

  • 计算给定的带有 \(s\) 的幂的加密多项式：

    $$g^{p(s)} = \left(g^{s^0}\right)^{c_0} \cdot \left(g^{s^1}\right)^{c_1} \cdot \ldots \cdot \left(g^{s^d}\right)^{c_d} = g^{c_0 s^0 + c_1 s^1 + \ldots + c_d s^d}$$

  • 计算给定的带有 \(s\) 的幂的 \(\alpha\)-移位的加密「移位」多项式：

    $$ g^{\alpha p(s)} = \left(g^{\alpha s^0}\right)^{c_0} \cdot \left(g^{\alpha s^1}\right)^{c_1} \cdot \ldots \cdot \left(g^{\alpha s^d}\right)^{c_d} = g^{c_0 \alpha s^0 + c_1 \alpha s^1 + \ldots + c_d \alpha s^d} = g^{\alpha (c_0 s^0 + c_1 s^1 + \ldots + c_d s^d)}$$

  • 将计算结果 \(g^p, g^{p'}\) 提供给验证者

• 验证者校验：\({\left(g^p\right)}^\alpha = g^{p'}\)

前面的多项式例子 \(p(x) = x^3 - 3x^2 + 2x\) 就变成了：

• 验证者提供 \(E(s^3), E(s^2), E(s)\) 和它们的变换 \(E(\alpha s^3), E(\alpha s^2), E(\alpha s)\)

• 证明者计算：

  $$g^p = g^{p(s)} = \left(g^{s^3}\right)^1 \cdot \left(g^{s^2}\right)^{-3} \cdot \Big(g^s\Big)^2 = g^{s^3} \cdot g^{-3s^2} \cdot g^{2s} = g^{s^3 - 3s^2 + 2s}$$

  $$g^{p'} = g^{\alpha p(s)} = \left(g^{\alpha s^3}\right)^1 \cdot \left(g^{\alpha s^2}\right)^{-3} \cdot \Big(g^{\alpha s}\Big)^2 = g^{\alpha s^3} \cdot g^{-3 \alpha s^2} \cdot g^{2 \alpha s} = g^{\alpha(s^3 - 3 s^2 + 2s)}$$

• 验证者校验：\({\left(g^p\right)}^\alpha = g^{p'}\)：

  $${\left(g^{s^3 - 3s^2 + 2s}\right)}^\alpha = g^{\alpha(s^3 - 3 s^2 + 2s)}$$

  $$g^{\alpha(s^3 - 3 s^2 + 2s)} = g^{\alpha(s^3 - 3 s^2 + 2s)}$$

现在我们就可以确保证明者是用了验证者提供的多项式而不是其他值做了计算，因为别的方法不能够保持 \(\alpha\)-移位。当然如果验证者想要确保在证明者的多项式中排除了 \(s\) 的某些次幂，比如 \(j\)，他可以不提供对应的密文 \(g^{s^j}\) 及其移位 \(g^{\alpha s^j}\)。

与前面的协议相比，我们现在已经有了一个健壮的协议。然而，虽然已经做了加密，但在零知识性质上也还依然存在一个很明显的缺陷：理论上多项式参数 \(c_i\) 是一个很广的取值范围内的值，但实际上这个范围可能很有限（比如前面例子中的 6），这就意味着验证者可以在有限范围的系数组合中进行暴力破解，最终计算出一个与证明者的答案相等的结果。比如我们将每个系数的取值范围定为 100，多项式阶数为 2，那么会有 100 万种不同的组合，可以认为暴力破解只需要少于 100 万次的迭代。更重要的是，即使只有一个系数，且系数值为 1 的例子中，安全协议也应该能够保证其安全。

译者注：有了 KEA，就可以约束证明者只能使用验证者提供的加密值去构造证明了。严格地说，这里是用的是 KEA 的扩展版本，叫做指数假设的 q-幂知识（The q-Power Knowledge of Exponent Assumption，q-PKE）。

零知识

由于验证者能够从证明者发送的数据中提取未知多项式 \(p(x)\) 的知识，我们就来看一下这些被提供的值（也就是证明）：\(g^p, g^{p'}, g^h\)。它们参与了下面的验证：

$$g^p = \left(g^h\right)^{t(s)} \text{（多项式 $p(x)$ 有根 $t(x)$）}$$

$$\left(g^p\right)^\alpha = g^{p'} \text{（使用了正确形式的多项式）}$$

问题是我们如何改变证明可以使检查仍然有效，但无法提取任何知识？前面的章节给了我们一个答案：我们可以使用随机值 \(\delta\)（Delta）来「移位」这些值，例如 \(\left(g^{p}\right)^\delta\)。现在，为了提取知识，首先需要找到无法得知的值 \(\delta\)。此外，这种随机化在统计学上与随机值无法区分。

为了保持这种关系，我们在验证者的检查中验证一下。等式的每一边都有一个证明者提供的值。所以如果我们用同一个 \(\delta\) 来「移位」每一个值，那么等式一定保持相等。

具体来讲，就是证明者选择一个随机值 \(\delta\)，并使用它对证明中的值进行求幂 \(\left(g^{p(s)}\right)^\delta\)，\(\left(g^{h(s)}\right)^\delta\)，\(\left(g^{\alpha p(s)}\right)^\delta\)，然后提供验证内容给验证者：

$$\left(g^p\right)^\delta = \left(\left(g^h\right)^\delta\right)^{t(s)}$$

$$\left(\left(g^p\right)^\delta\right)^\alpha = \left(g^{p'}\right)^\delta$$

再合并一下我们就可以看到校验的等式依然成立：

$$g^{\delta \cdot p} = g^{\delta \cdot t(s) h}$$

$$g^{\delta \cdot \alpha p} = g^{\delta \cdot p'}$$

注：零知识可以轻而易举地融入到这个结构之中，这通常也被称为「无成本」的零知识。

译者注：借助这个「无成本」的技巧，就可以轻松实现零知识了。但是这里实现零知识的方法和实际中的 Pinocchio 协议还有 Groth16 方案略有不同。实际方案中是用乘法乘以 \(g^{δ \cdot t(s)}\)。

非交互性

到现在为止，我们已经有了一个交互式的零知识方案。但为什么我们还需要有非交互式的呢？因为交互式证明只对原始的验证者有效，其他任何人（其他的验证者）都不能信任这个证明，因为：

• 验证者可以和证明者串通，告诉他秘密参数 \(s, \alpha\)，有了这些参数，证明者就可以伪造证明，就像前面备注 3.1 提到的那样
• 验证者也可以使用同样的方法自己伪造证明
• 验证者在所有相关证明被验证完毕之前必须保存 \(\alpha\) 和 \(t(s)\)，这就带来了一个可能造成秘密参数泄漏的额外攻击面

因此，为了证明一个陈述（在这种情况下是多项式知识），需要与每个验证者进行单独的交互。

尽管交互式证明也有它的用处，例如一个证明者只想让一个特定的验证者（称为指定验证者，即 Designated Verifier，更多信息参见 [JSI96]）确信，就不能再重复利用同一个证明去向别人证明这个声明了，但是当一个证明者想让众多的参与者同时（例如在区块链等分布式系统中）或者永久地确信的话，这种方法就很低效了。证明者需要一直保持在线并对每一个验证者执行相同的计算。

因而，我们就需要一个可以被重复使用、公开、可信，又不会被滥用的秘密参数。

我们先来思考一下如何在构造出秘密值（\(t(s), \alpha\)）之后保证它们的安全性。我们可以像验证者在发送给证明者之前加密 \(s\) 的幂一样对它们进行加密。但是备注 3.2 中提到，我们使用的同态加密并不支持两个秘密值相乘，这一点对 \(t(s)\) 和 \(h\) 的加密值相乘以及 \(p\) 和 \(\alpha\) 的加密值相乘的验证都很重要。这正是密码学配对（Cryptographic Pairing）适用的地方。

译者注：这里的非交互证明协议将对参数加密，但引入了两个问题：

1. 同态加密无法对两个加密值做乘法，如何验证加密后的参数？
2. 加密值一旦泄露，协议的信任关系将无法保证，如何确保参数的安全性？

加密值的乘法

密码学配对（双线性映射）是一种数学结构，表示为函数 \(e(g^*, g^*)\)，给定一个数集中的两个加密的输入（例如 \(g^a, g^b\)），可以将他们确定性地映射到另一组不同的输出数集上的它们的乘积，即 \(e(g^a, g^b) = e(g,g)^{ab}\)：

因为源数集和输出数集（通常被称为一个群）是不同的，所以一个配对的结果不能用作其他配对计算的输入。我们可以将输出集（也称为「目标集」）视为「不同的宇宙」。因而我们不能用另一个加密值乘以结果，而且「配对」这个名称本身也表明了，我们一次只能将两个加密值相乘。

译者注：换句话说，配对只支持 \(x \cdot y\) 这种两个值的乘法，不支持三个或以上的值相乘，例如不支持 \(x \cdot y \cdot z\)。

在某种意义上，它类似于一个散列函数，将所有可能的输入值映射到可能的输出值的集合中的一个元素上，通常情况下这个过程是不可逆的。

注：乍一看这个限制可能会阻碍相关功能的实现，但在 zk-SNARK 中这反而是保证安全模式的最重要性质，参见备注 3.3。

配对函数 \(e(g^*, g^*)\) 可以初步（严格来说并不正确）地类比成「交换」每一个输入的基数和指数，使得基数 \(g\) 在被转换成指数形式的过程中被修改，即 \(g^a \rightarrow a^{\mathbf{g}}\)。接下来将两个被「交换」的输入相乘，这样原始值 \(a\) 和 \(b\) 就在同一个指数下相乘了，即：

$$e(g^a, g^b) = a^{\mathbf{g}} \cdot b^{\mathbf{g}} = \left( ab \right)^{\mathbf{g}}$$

由于基数在「交换」中被修改了，所以在另一个配对中不能再使用这个结果 \(\left( ab \right)^{\mathbf{g}}\)（例如：\(e\left(\left( ab \right)^{\mathbf{g}}, g^c\right)\)）构造出想要的加密乘积 \(abc\) 了。

配对的核心性质可以表示成下面的等式：

$$e(g^a, g^b) = e(g^b, g^a) = e(g^{ab}, g^1) = e(g^1, g^{ab}) = {e(g^1, g^a)}^b = {e(g^1, g^1)}^{ab} = \ldots$$

严格来讲一个配对的结果是在目标集的一个不同生成元 \(\mathbf{g}\) 下对原始值乘积的加密，即 \(e(g^a, g^b) = \mathbf{g}^{ab}\)。因而它具备同态加密的性质，也就是说我们可以把乘法配对的加密乘积加在一起：

$$e(g^a, g^b) \cdot e(g^c, g^d) = \mathbf{g}^{ab} \cdot \mathbf{g}^{cd} = \mathbf{g}^{ab + cd} = e(g, g)^{ab + cd}$$

注意：密码学配对是利用椭圆曲线来实现这些性质的，从现在开始我们用的符号 \(g^n\) 就代表曲线上一个由生成元自相加了 \(n\) 次的点，而不是我们前面用到的乘法群生成元。

[DBS04] 提供了学习密码学配对的起点。

可信任参与方设置

有了密码学配对，我们现在就准备去设置安全公开且可复用的参数了。假定我们让一个诚实的参与方来生成秘密值 \(s\) 和 \(\alpha\)。当 \(\alpha\) 和所有必要的 \(s\) 的幂及其对应的 \(\alpha\)-移位 \(g^\alpha, g^{s^i}, g^{\alpha s^i}\)（\(i\) 为 \(0, 1, \ldots, d\)）被加密完成后，原始数据就必须要被删除。

这些参数通常被称为公共参考字符串（Common Reference String，CRS）。CRS 被生成后，任何证明者和任何验证者都可以使用它来构造非交互式的零知识证明协议。虽然不重要，但 CRS 的优化版本将包含目标多项式的加密值 \(g^{t(s)}\)。

接着，把 CRS 分成两组（\(i\) 为 \(0, 1, \ldots, d\)）：

• 证明密钥（Proving Key，也被称为求值密钥 Evaluation Key）：\((g^{s^i}, g^{\alpha s^i})\)
• 验证密钥（Verification Key）：\((g^{t(s)}, g^{\alpha})\)

只要能将加密值相乘，验证者就可以在协议的最后一步检查多项式了：

• 有了验证密钥，验证者就可以处理从证明者那里得到的加密多项式 \(g^p, g^h, g^{p'}\) 的值：

  • 在加密空间中检查 \(p = t \cdot h\)：

    $$e\left(g^p, g^1\right) = e\left(g^t, g^h\right) \quad\text{等效于}\quad e\left(g, g\right)^{p} = e\left(g, g\right)^{t \cdot h}$$

  • 检查多项式限制：

    $$e\left(g^p, g^\alpha\right) = e\left(g^{p'}, g\right)$$

信任多个参与方中的一个

尽管可信任设置很有效率，但众多 CRS 用户也必须要相信生成者确实删除了 \(\alpha\) 和 \(s\)，这一点没有办法证明（无知证明，即 Proof of Ignorance，是一个正在积极研究的领域 [DK18]），所以这种方法依然是无效率的。很有必要去最小化或者消除这种信任。否则一个不诚实的参与方就可以构造假证明而不被发现。

一种解决办法就是由多个参与方使用前面小节中介绍的数学工具来生成一个复合 CRS，这样这些参与方就都不知道秘密了。这里是一个实现方案，我们假设有三个参与者 Alice，Bob 和 Carol ，对应为 A、B 和 C，其中 \(i\) 为 \(1, 2, \ldots, d\)：

• Alice 选择随机值 \(s_A\) 和 \(\alpha_A\)，然后公开她的 CRS：

  $$\left( g^{s^i_A}, g^{\alpha_A}, g^{\alpha_A s^i_A} \right)$$

• Bob 选择他的随机数 \(s_B\) 和 \(\alpha_B\)，然后通过同态乘法结合 Alice 的 CRS：

  $$\left( \left(g^{s^i_A}\right)^{s^i_B}, \left(g^{\alpha_A}\right)^{\alpha_B}, \left(g^{\alpha_A s^i_A}\right)^{\alpha_B s^i_B} \right) = \left(g^{{(s_A s_B)}^i}, g^{\alpha_A \alpha_B}, g^{\alpha_A \alpha_B {(s_A s_B)}^i}\right)$$

  然后公开两方 Alice-Bob 的 CRS 结果：

  $$\left(g^{s_{\mathsf{AB}}^i}, g^{\alpha_{\mathsf{AB}}}, g^{\alpha_{\mathsf{AB}}\ s_{\mathsf{AB}}^i}\right)$$

• Carol 用她的随机数 \(s_C\) 和 \(\alpha_C\) 做同样的事：

  $$\left(\left( g^{s_{\mathsf{AB}}^i} \right)^{s^i_C}, \Big( g^{\alpha_{\mathsf{AB}}} \Big)^{\alpha_C}, \left( g^{\alpha_{\mathsf{AB}}\ s_{\mathsf{AB}}^i} \right)^{\alpha_C s^i_C}\right) = \left(g^{\left(s_A s_B s_C \right)^i}, g^{\alpha_A \alpha_B \alpha_C}, g^{\alpha_A \alpha_B \alpha_C {(s_A s_B s_C)}^i}\right)$$

  然后公开 Alice-Bob-Carol 的 CRS:

  $$\left(g^{s_{\mathsf{ABC}}^i}, g^{\alpha_{\mathsf{ABC}}}, g^{\alpha_{\mathsf{ABC}}\ s_{\mathsf{ABC}}^i}\right)$$

这个协议的结果是，我们获得了一个复合的 \(s^i = s^i_A s^i_B s^i_C\) 和 \(\alpha = \alpha_A \alpha_B \alpha_C\)，除非他们串谋，否则参与者们互相之间并不知道其他人的秘密参数。事实上，一个参与者必须要和其他所有的参与者串谋才能得到 \(s\) 和 \(\alpha\)。因此在所有的参与者中只要有一个是诚实的，就没有办法伪造证明。

注：可以根据需要为尽可能多的参与者重复此过程。

可能会遇到的问题是如何验证参与者在每个 CRS 中使用了一致的值，因为对手可以将不对应的 \(s_1, s_2, \ldots\) 和 \(\alpha_1, \alpha_2, \ldots\) 相乘，并将它们随机用于不同的 \(s\) 幂（或提供随机数作为结合的公共参考字符串），使 CRS 无效且不可用。

幸运的是，因为我们可以使用配对来乘以加密值，所以我们就可以从第一个参数开始逐一执行一致性校验，并确保每下一个参数都是从它派生的。参与者发布的每个 CRS 都可以检查如下：

• 我们用 \(s\) 的 1 次幂作为标准来校验每一个其他次幂的值是否与之保持一致：

  $$\left. e\left(g^{s^i}, g\right) = e\left(g^{s^1}, g^{s^{i-1}}\right) \right|_{i \in \{2, \ldots, d\}}$$

  例如：

  • 2 次幂：\(e\left(g^{s^2}, g\right) = e\left(g^{s^1}, g^{s^{1}}\right) \Rightarrow {e(g,g)}^{s^2} = {e(g,g)}^{s^{1+1}}\)
  • 3 次幂：\(e\left(g^{s^3}, g\right) = e\left(g^{s^1}, g^{s^{2}}\right) \Rightarrow {e(g,g)}^{s^3} = {e(g,g)}^{s^{1+2}}\) 等

• 我们现在再验证一下前面步骤中 \(\alpha\)-移位后的值是否正确：

  $$\left. e\left(g^{s^i}, g^{\alpha}\right) = e\left(g^{\alpha s^i}, g\right)\right|_{i \in [d]}$$

  例如：

  • 3 次幂：\(e\left(g^{s^3}, g^{\alpha}\right) = e\left(g^{\alpha s^3}, g\right) \Rightarrow {e(g,g)}^{s^3 \cdot \alpha} = {e(g,g)}^{\alpha s^3}\) 等

  这里 \(i \in \{2, \ldots, d\}\) 是「\(i\) 值分别为 \(2, 3, \ldots, d\)」的缩写形式，\([d]\) 是 \(1, 2, \ldots, d\) 这个范围的缩写形式，在后面的章节这种表示方式更为常见

当我们在验证每一个参与者秘密参数的一致性时，要注意参与者生成 CRS 的过程并没有强制后一个参与者（就是我们例子中的 Bob 和 Carol）都要使用前面已经公开的 CRS。因此当一个攻击者是链上的最后一个参与者时，他就可以像链上的第一个参与者一样忽略前面的 CRS 随便构造一个有效的 CRS，这样他就变成了唯一一个知道秘密 \(s\) 和 \(\alpha\) 的人。

为了解决这个问题，我们可以额外再要求除了第一个以外的每一个参与者去加密然后公开他的参数。例如，Bob 同样公开了：

$$\left. \left(g^{s^i_B}, g^{\alpha_B}, g^{\alpha_B s^i_B}\right) \right|_{i \in [d]}$$

这就可以去验证 Bob 的 CRS 是乘以了 Alice 的参数后正常获得的，这里 \(i\) 为 \(1, 2, \ldots, d\)：

• \(e\left({g^{s^i_{\mathsf{AB}}}, g}\right) = e\left({g^{s^i_A}, g^{s^i_B}}\right)\)
• \(e\left({g^{\alpha_{\mathsf{AB}}}, g}\right) = e\left({g^{\alpha_A}, g^{\alpha_B}}\right)\)
• \(e\left({g^{\alpha_{\mathsf{AB}}\ s^i_{\mathsf{AB}}}, g}\right) = e\left({g^{\alpha_A s^i_A}, g^{\alpha_B s^i_B}}\right)\)

同样，Carol 必须证明她的 CRS 是 Alice-Bob 的 CRS 的适当倍数。

这是一个健壮的 CRS 设置模式，并不完全依赖于任何一方。事实上，即使其他所有的参与者都串谋了，只要有一个参与者是诚实的，删除并且永远不共享他的秘密参数，这个 CRS 就是有效的。所以在 CRS 设置（有时被称为仪式，即 Ceremony [Wil16]）的时候不相关的参与者越多，伪造证明的可能性就越小。当有相互竞争的参与方参与的时候，就几乎不可能伪造证明了。该方案允许涉及对设置的易读性有疑问的其他不受信任的参与方，因为验证步骤确保他们不会破坏（这里也包括很弱的 \(\alpha\) 和 \(s\) 的使用）最终的公共参考字符串。

译者注：现在有一些 zk-SNARK 方案支持可升级的 CRS，任何怀疑 CRS 的参与方都可以对 CRS 进行更新。此外还有一些 zk-SNARK 方案支持通用 CRS（Universal CRS），不需要对每一个电路进行受信任设置，只需要全局完成一次即可。除此之外，大量无需 Trusted Setup 的方案也正在被研究之中。

多项式知识的简洁非交互式论证

我们现在可以整合这个逐步演化出来的多项式知识的简洁非交互式论证（Succinct Non-Interactive Argument of Knowledge of Polynomial，zk-SNARKOP）协议了。为简洁起见，我们将使用大括号来表示由旁边的下标填充的一组元素，例如 \(\left\{ s^i \right\}_{i \in [d]}\) 表示集合 \(s^1, s^2, \ldots, s^d\)。

我们已经明确了目标多项式 \(t(x)\) 和证明者的多项式阶数 \(d\)：

• 设置
  • 选择随机值 \(s, \alpha\)
  • 计算加密值 \(g^\alpha\) 和 \(\left\lbrace g^{s^i} \right\rbrace_{i \in [d]}, \left\lbrace g^{\alpha s^i} \right\rbrace_{i \in \{0, \ldots, d\}}\)
  • 生成证明密钥：\(\left( \left\lbrace g^{s^i} \right\rbrace_{i \in [d]}, \left\lbrace g^{\alpha s^i} \right\rbrace_{i \in \{0, \ldots, d\}} \right)\)
  • 生成验证密钥：\(\left( g^\alpha, g^{t(s)} \right)\)
• 证明
  • 赋值系数 \(\left\{ c_i \right\}_{i \in \{0,\ldots, d\}}\)（即知识）得 \(p(x) = c_d x^d + \cdots + c_1 x^1 + c_0 x^0\)
  • 求多项式 \(h(x) = \frac{p(x)}{t(x)}\)
  • 代入 \(\left\lbrace g^{s^i} \right\rbrace_{i \in [d]}\) 计算多项式 \(g^{ p(s)}\) 和 \(g^{ h(s)}\) 的值
  • 代入 \(\left\lbrace g^{\alpha s^i} \right\rbrace_{i \in \{0, \ldots, d\}}\) 计算移位多项式 \(g^{ \alpha p(s)}\) 的值
  • 选择随机值 \(\delta\)
  • 构造随机化的证明 \(\pi = \left(g^{\delta p(s)}, g^{\delta h(s)}, g^{\delta \alpha p(s)} \right)\)
• 验证
  • 映射证明 \(\pi\) 为 \(\left(g^{p}, g^{h}, g^{p'} \right)\)
  • 检查多项式限制：\(e\left(g^{p'}, g\right) = e\left(g^{p}, g^\alpha\right)\)
  • 检查多项式系数：\(e\left(g^p, g\right) = e\left(g^{t(s)}, g^h\right)\)

备注 3.3 如果可以将配对结果重用于另一个乘法，那么这样的协议将是完全不安全的，因为这样的话证明者就可以构造 \(g^{p'} = e\left(g^{p}, g^\alpha\right)\)，这样也可以通过「多项式限制」的检查：

$$e\left(e\left(g^{p}, g^\alpha\right), g\right) = e\left(g^{p}, g^\alpha\right)$$

结论

我们得出了用来解决多项式问题知识的零知识简洁非交互式论证协议，不过这只是一个有局限的例子。虽然大家可以说证明者只要用另外一个有界的多项式去乘以 \(t(x)\) 就可以很容易地构造出一个能够通过测试的多项式 \(p(x)\)，但这种结构仍然有用。

验证者知道证明者有一个有效的多项式，但是并不知道是哪一个。我们可以添加多项式其他属性的额外证明，例如：被多个多项式整除、是某个多项式的平方。可能会有一种服务能够接受、存储和奖励所有经过证明的多项式，或者有一个加密计算某种形式的未知多项式的需求。然而，如果有通用方案就可以支撑起无数的应用。

译者注：总结一下，这篇文章逐步解决了以下几个问题：

• 保证证明者的证明是按照规则正确构造的：KEA
• 保证知识的零知性：「无成本」的 \(\delta\) 变换
• 可复用证明：非交互式
• 非交互式的同时设置安全公开且可复用的参数：参数加密，验证者借助密码学配对进行验证
• 保证参数的生成者不泄密：多方的设置

至此，一个用来证明多项式知识的完整 zk-SNARK 协议就被构造出来了，不过现在的协议在通用性上依然还有很多限制，后面的文章将继续介绍如何构造通用的 zk-SNARK。

通用零知识证明

我们已经用一个简单而充分的例子铺平了道路，它包含了大部分 zk-SNARK 的内在机制，现在我们继续完善该方案，使它能执行零知识程序。

计算

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

算法 1：运算取决于输入

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 \times 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 \times b) + (1 - w) (a + b) = 8$$

译者注：猜想一下，只要是能用多项式表示的程序都可以做证明吗？

单一运算

尽管已经将程序转换成了由数学语言表达的一般计算形式，我们还是需要再把它翻译成多项式。让我们来仔细看看简单来说什么是计算。任何计算的内核都是由以下形式的基本运算组成的：

$$\mathsf{左操作数}\quad \mathbf{运算符}\quad \mathsf{右操作数}\quad =\quad \mathsf{输出}$$

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

多项式的算术性质

我们先来看一下如何将多项式和算术运算关联起来。例如，有两个多项式 \(f(x)\) 和 \(g(x)\)，尝试将他们相乘得到 \(h(x) = f(x) \times g(x)\)，在任意一个 \(x = r\) 处 \(h(x)\) 的计算结果都是 \(f(r)\) 和 \(g(r)\) 的乘积。考虑下面两个多项式 \(f(x) = 2x^2 - 9x + 10\) 和 \(g(x) = -4x^2 + 15 x -9\)。以图形的形式可视化：

当 \(x = 1\) 时 \(f(1) = 2 -9 + 10 = 3\)，\(g(1) = -4 + 15 -9 = 2\)。

把两个多项式相乘：\(h(x) = f(x) \times g(x) =-8 x^4 + 66 x^3 - 193 x^2 + 231 x -90\)。从图中可以看出相乘的结果：

\(x = 1\) 时，计算 \(f(x) \times g(x)\) 结果为：\(h(1) = -8 + 66 -193 + 231 - 90 = 6\)，也就是说当 \(x = 1\) 时，\(h(x)\) 就是 \(f(x)\) 和 \(g(x)\) 相乘的结果 ，在 \(x\) 取其他值的时候也一样。

同样，如果我们将 \(f(x)\) 和 \(g(x)\) 相加，会得到 \(-2x^2 + 6x + 1\)，在 \(x = 1\) 处的计算结果就是 5。

注：在其他 \(x\) 的取值处，多项式相加的计算结果也是将两个多项式的值加在一起的结果，例如可以验证一下 \(x = 2\)、\(x = 3\) 处的结果。

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

译者注：回忆一下，在「证明的媒介」一节中，我们曾提到过：任何多项式在任意点的计算结果都可以看做是其唯一身份的标识。

反过来，当我们知道某个多项式的时候，也就意味着我们知道多项式上某个点的取值了。这就是借助多项式来完成证明的依据。

执行运算

如果一个证明者声称拥有某两个数字的乘积，验证者要怎样去验证呢？为了证明单个计算的正确性，我们必须确保提供的操作数的输出（结果）的正确性。我们再来看一下运算的形式：

$$\mathsf{左操作数}\quad \mathbf{运算符}\quad \mathsf{右操作数}\quad =\quad \mathsf{输出}$$

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

$$ l(x) \ \mathbf{运算符} \ r(x) = o(x) $$

对于选定的值 \(a\):

• \(l(x)\) - 在 \(a\) 处表示（求值为）左操作数的值
• \(r(x)\) - 在 \(a\) 处表示右操作数的值
• \(o(x)\) - 在 \(a\) 处表示运算的结果（输出）

因此，如果这些多项式的运算正确地表示了操作数和输出，那么 \(l(a) \ \mathbf{运算符} \ r(a) = o(a)\) 就应该成立。将输出多项式 \(o(x)\) 移动到等式的左侧 \(l(a) \ \mathbf{运算符} \ r(a) - o(a) = 0\)，如果输出多项式 \(o(x)\) 表示的值是 \(\mathbf{运算符}\) 对操作数多项式 \(l(x)\) 和 \(r(x)\) 表示的值产生的正确结果，这表示运算多项式 \(l(x) \ \mathbf{运算符} \ r(x) - o(x) = 0\) 必须在 \(a\) 处计算为 0。那么只要运算多项式有效，就一定有一个根 \(a\)，因此，根据前面的基础（参见 3.2 节的因式分解），它必须包含辅因子 \((x - a)\)，这也就是我们要证明的目标多项式，即 \(t(x) = x - a\)。

例如，我们来看一个运算：\(3 \times 2 = 6\)

可以用一个简单的多项式表示它：\(l(x) = 3x\)，\(r(x) = 2x\)，\(o(x) = 6x\)，取 \(a = 1\) 进行计算，即 \(l(1) = 3;\ r(1) = 2;\ o(1) = 6\)。

注：\(a\) 的值可以是任意的。

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

$$l(x) \times r(x) = o(x)$$

$$3x \times 2x = 6x$$

$$6x^2 - 6x = 0$$

在图上表示为：

值得注意的是，操作多项式有一个辅因子 \((x-1)\)：

$$6x^2 - 6x = 6x (x - 1)$$

因此，如果证明者提供这样的多项式 \(l(x), r(x), o(x)\) 而不是以前的 \(p(x)\)，那么验证者将接受它为有效的，因为它可以被 \(t(x)\) 整除。相反，如果证明者试图作弊并将输出值替换为 4，例如 \(o(x) = 4x\)，则运算多项式就会变成 \(6x^2 - 4x = 0\)：

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

因此，验证者不会接受这种不一致的计算结果（就像 3.2 节描述的那样）。

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

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

运算证明

现在我们来修改一下最新协议，使它支持单个乘法计算的证明。回想一下，我们已经有多项式 \(p(x)\) 的知识证明了，但现在要处理三个多项式 \(l(x), r(x), o(x)\)。虽然我们可以定义 \(p(x) = l(x) \times r(x) - o(x)\)，但这里存在两个争议点。首先，在我们的协议中证明阶段是不能做加密值乘法计算的（即 \(l(s) \times r(s)\)），因为配对只能使用一次，要用在多项式限制的检查上。第二，这里给证明者留下了一个可以修改多项式结构但依然保留有效辅因子 \(t(x)\) 的机会，例如可以令 \(p(x) = l(x)\) 或者 \(p(x) = l(x) - r(x)\) 甚至是 \(p(x) = l(x) \times r(x) + o(x)\)，只要这里的 \(p(x)\) 还保留着根 \(a\) 就可以。这种修改本质上是让证明的内容变成了别的陈述，这当然是我们不希望发生的。

所以证明者必须要分别提供多项式 \(l(s)\)、\(r(s)\)、\(o(s)\) 的求值。这意味着必须调整多项式的知识。本质上，验证者需要在加密空间中检查的是 \(l(s) \times r(s) - o(s) = t(s) h(s)\)。虽然验证者可以使用密码学配对执行乘法，但减法（\(-o(x)\)）是一项昂贵的操作（需要找到 \(g^{o(s)}\) 的逆元），这就是我们要将 \(o(x)\) 移到等式右侧的原因：\(l(x) r(x) = t(x) h(x) + o(x)\)。在加密空间中，验证者的检查就可以转换为：

$$e\left(g^{l(s)}, g^{r(s)}\right) = e\left(g^{t(s)}, g^{h(s)}\right) \cdot e\left(g^{o(s)}, g\right)$$

$$e(g, g)^{l(s) r(s)} = e(g,g)^{t(s)h(s)} \cdot e(g,g)^{o(s)}$$

$$e(g, g)^{l(s) r(s)} = e(g,g)^{t(s)h(s) + o(s)}$$

注：回想一下，密码学配对的结果是支持通过乘法实现加密值加法的，参见 3.6.1 节。

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

• 证明
  • 将相应的系数赋值给 \(l(x)\)、\(r(x)\)、\(o(x)\)
  • 求多项式 \(h(x) = \frac{l(x) \times r(x) - o(x)}{t(x)}\)
  • 代入 \(\left\lbrace g^{s^i} \right\rbrace_{i \in [d]}\) 计算多项式 \(g^{l(s)}\)、\(g^{r(s)}\)、\(g^{o(s)}\) 和 \(g^{h(s)}\) 的值
  • 代入 \(\left\lbrace g^{\alpha s^i} \right\rbrace_{i \in \{0, \ldots, d\}}\) 计算移位多项式 \(g^{\alpha l(s)}\)、\(g^{\alpha r(s)}\)、\(g^{\alpha o(s)}\) 的值
  • 构造证明 \(\pi = \left( g^{l(s)}, g^{r(s)}, g^{o(s)}, g^{h(s)}, g^{\alpha l(s)}, g^{\alpha r(s)}, g^{\alpha o(s)} \right)\)
• 验证
  • 将证明 \(\pi\) 解析为 \(\left( g^l, g^r, g^o, g^h, g^{l'}, g^{r'}, g^{o'} \right)\)
  • 检查多项式限制： $$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\left(g^{l}, g^{r}\right) = e\left(g^{t(s)}, g^{h}\right) \cdot e\left(g^{o}, g\right)\)

这样的协议就能证明两个值相乘的结果是正确计算的了。

你可能会注意到，在更新后的协议中我们放弃了零知识组件。这样做是为了让过渡更加简单。我们将在后面的部分将它添加回协议中。

多个运算

现在我们已经能证明单个运算了，但要怎样扩展才能证明多个运算（这是我们的最终目标）呢？让我们尝试添加另一个运算。假如需要计算乘积：\(a \times b \times c\)。在基本运算模型中，这意味着两个运算：

$$\color{ForestGreen}{a}\quad \times \quad\color{blue}{b}\quad = \quad\color{red}{r_1}$$

$$\color{ForestGreen}{r_1}\quad \times \quad\color{blue}{c}\quad = \quad\color{red}{r_2}$$

在前面的讨论中，我们可以通过使操作数多项式计算为某个任意 \(x\) 处（例如 \(1\)）的相应值来表示此类运算。有了这个方法，多项式的属性并不会限制我们在不同的 \(x\) 处（例如 \(2\)）表示其他值，即：

这种独立性允许我们一次执行两个运算而不会将它们「混合」在一起，也就是说相互之间没有干扰。这个多项式算术的结果就变成了：

可以看出，运算多项式有两个根 \(x = 1\) 和 \(x = 2\)。因此，这两次计算都被正确执行了。

译者注：这里的示例为了方便理解，选择了 \(x = 1\) 和 \(x = 2\) 两个位置。在完整的 zk-SNARK 方案中，这些「root」值必须为有限域内的随机数，否则就会引入安全漏洞。

我们再来看一个有三个乘法运算的例子 \(2 \times 1 \times 3 \times 2\)，它按照下面的步骤执行：

$$\color{ForestGreen}{2}\quad \times \quad\color{blue}{1}\quad = \quad\color{red}{2}$$

$$\color{ForestGreen}{2}\quad \times \quad\color{blue}{3}\quad = \quad\color{red}{6}$$

$$\color{ForestGreen}{6}\quad \times \quad\color{blue}{2}\quad = \quad\color{red}{12}$$

我们需要将它们表示为操作数多项式，对于由 \(x \in \{1, 2, 3\}\) 所表示的计算，\(l(x)\) 相应地经过 \(\color{ForestGreen}{2, 2}\) 和 \(\color{ForestGreen}{6}\)（即经过点 \((1, \color{ForestGreen}{2}), (2, \color{ForestGreen}{2}), (3, \color{ForestGreen}{6})\)），同样 \(r(x) \ni (1, \color{blue}{1}), (2, \color{blue}{3}), (3, \color{blue}{2})\)，以及 \(o(x) \ni (1,\color{red}{2}), (2, \color{red}{6}), (3, \color{red}{12})\)。

但是，我们如何找到经过这些点的多项式呢？对于任何超过一个点的情况，都必须使用特定的数学方法。

多项式插值

为了构造操作数和输出多项式，我们需要一种方法，对于给定的一组点可以产生通过所有这些点的弯曲多项式，这种方法被称为插值。有几种不同的方法可以得到这个多项式：

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

我们以第一个方法为例。这个方法的思路是存在一个系数未知、阶数至多为 \(n\) 的唯一多项式能够经过给定的 \(n + 1\) 个点，对于每个点 \(\left\{ \left(x_i, y_i\right) \right\}_{i \in [n + 1]}\)，多项式在 \(x_i\) 处的计算结果都等于 \(y_i\)。在我们的例子中，三个点对应阶数为 2 的多项式，表示为：

$$ax^2 + bx + c = y$$

让我们令左操作数多项式（绿色）在每个点的多项式求值相等，并通过用其他系数表达每个系数来求解方程组：

因此左操作数多项式为：

$$\color{ForestGreen}{l(x)} = 2x^2 - 6x + 6$$

对应于下图：

我们可以用同样的方法找到 \(r(x)\) 和 \(o(x)\)：

$$\color{blue}{r(x)} = \frac{-3x^2 + 13x - 8}{2}; \quad \color{red}{o(x)} = x^2 + x$$

多运算多项式

现在我们有了代表三个运算的操作数多项式，让我们一步一步地看看如何验证每个运算的正确性。回想一下，验证者正在寻找等式 \(l(x) \times r(x) - o(x) = t(x)h(x)\)。在这种情况下，由于运算在点 \(x \in \{1,2,3\}\) 处表示，因此目标多项式必须在这些 \(x\) 处计算为 \(0\)，换句话说，\(t(x)\) 的根必须是 1、2 和 3，其基本形式为：

首先，将 \(l(x)\) 和 \(r(x)\) 相乘，得到：

接着，从 \(l(x) \times r(x)\) 的结果中减去 \(o(x)\)：

已经可以看出，每个操作数的乘法都对应一个正确的结果。对于最后一步，证明者需要提供一个有效的辅因子：

$$h(x) = \frac{l(x) \times r(x) - o(x)}{t(x)} = \frac{-3x^4 + 22x^3 - 57x^2 + 62x - 24}{(x - 1)(x - 2)(x - 3)}$$

使用长除法我们得到：

使用 \(h(x) = -3x + 4\)，验证者可以计算 \(t(x)h(x)\)：

现在很明显 \(l(x) \times r(x) - o(x) = t(x) h(x)\)，这就是我们要证明的内容。

译者注：这里只需要一组多项式 \(l(x)\)、\(r(x)\)、\(o(x)\) 就可以表示出所有计算的约束关系，计算的数量与目标多项式 \(t(x)\) 的根的数量相同。

当前的协议似乎存在一些缺陷，只能证明证明者拥有一组多项式 \(l(x)\)、\(r(x)\)、\(o(x)\) 在 \(t(x)\) 几个根的取值处 \(l(x) \times r(x) = o(x)\)，无法证明这组多项式符合我们要证明的数学表达式：

1. 多个计算关系是分开表示的，这些算式之间的关系也无法进行约束

2. 由于证明者生成的证明中只有计算结果，左操作数、右操作数、输出在计算中混用也不会被发现

3. 由于左操作数、右操作数、输出是分开表示的，相互之间的关系无法进行约束

变量多项式

使用这种方法，我们可以一次证明许多运算（例如数百万甚至更多），但它有一个严重的缺点。

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

$$\color{ForestGreen}{a}\quad \times \quad\color{blue}{b}\quad = \quad\color{red}{r_1}$$

$$\color{ForestGreen}{a}\quad \times \quad\color{blue}{c}\quad = \quad\color{red}{r_2}$$

对于这两个运算，\(\color{ForestGreen}{a}\) 必须在左操作数多项式中表示：

尽管如此，由于我们的协议允许证明者为多项式设置任何系数，所以他为不同的运算（由一些 \(x\) 表示）设置不同的 \(a\) 值是不受限制的，例如：

这种自由破坏了一致性，并允许证明者证明验证者不感兴趣的其他程序的执行。因此，我们必须确保任何变量在它被使用的每个运算中只能有一个值。

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

译者注：请务必注意「变量」的定义，它是程序中的变量，但又不可改变，其实是指示例伪代码中那些不会被修改的变量。在 zk-SNARK 论文中，这个「变量」其实有一个对应的名词叫做 Assignment，是算术电路的「赋值」。而所有的 Assignment 是一个算术电路可满足性问题的解，包含了算术电路的输入值以及电路运算过程中输出的中间结果值。

单变量操作数多项式

我们来看一个简单的例子（与当前示例一样），在由左操作数多项式 \(l(x)\) 表示的所有左操作数中仅使用一个变量（例如 \(a\)）。我们要找出是否可以确保这个多项式在每个运算中都表示相同的 \(a\) 值。证明者可以设置不同值的原因是他可以控制 \(x\) 的每次幂的每个系数。因此，如果这些系数是固定的，这个可变性问题就被解决了。

让我们仔细观察包含相等值的多项式。例如，分别检查两个表示两个运算相等值的多项式（即，在 \(x = 1\) 和 \(x = 2\) 处），其中第一个多项式包含值 \(1\)，第二个包含值 \(2\)：

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

$$2x^2 - 6x + 6 = 2 \times (x^2 - 3x + 3)$$

当我们想要同时改变多项式中的所有值时，我们需要改变它的比例，由于多项式的算术特性，如果我们将多项式乘以一个数字，每个可能的 \(x\) 的求值也将乘以这个数字（即按比例缩放）。要验证这一点，可以尝试将第一个多项式乘以 3 或任何其他数字。

因此，如果验证者需要强制证明者在所有运算中设置相同的值，那么应该限制证明者只能修改比例而不是单个系数。

那么如何保持系数比例呢？我们可以先考虑为左操作数多项式提供了什么作为证明。它是在某个秘密 \(s\) 处对 \(l(x)\) 的加密求值：\(g^{l(s)}\)，也就是说它是一个加密数字。从 3.4 节中我们已经知道如何通过 \(\alpha\)-移位来限制验证者仅使用提供的 \(s\) 的指数，因此同态乘法是唯一可用的运算。

与限制单个指数类似，验证者可以一次限制整个多项式。不提供单独的加密值 \(g^{s^1}, g^{s^2}, \ldots, g^{s^d}\) 和它们的 \(\alpha\)-移位 \(g^{\alpha s^1}, g^{\alpha s^2}, \ldots, g^{\alpha s^d}\)，协议的过程就是：

• 设置
  • 用对应的系数构造相应的操作数多项式 \(l(x)\)
  • 选择随机值 \(\alpha\) 和 \(s\)
  • 用加密的 \(l(s)\) 生成证明密钥，它是「移位」对：\(\left( g^{l(s)}, g^{\alpha l(s)} \right)\)
  • 生成验证密钥：\(\left( g^\alpha \right)\)
• 证明
  • 对于操作数的值 \(v\)
    • 乘以操作数多项式：\(\left( g^{l(s)} \right)^v\)
    • 乘以移位的操作数多项式：\(\left( g^{\alpha l(s)} \right)^v\)
  • 提供操作数多项式的乘法证明：\(\left( g^{v\ l(s)}, g^{v\ \alpha l(s)} \right)\)
• 验证
  • 将证明解析为 \(\left( g^{l}, g^{l'} \right)\)
  • 验证比例：\(e\left( g^{l'}, g \right) = e\left( g^{l}, g^\alpha \right)\)

证明者需要以相同的 \(\alpha\)-移位进行响应，由于他无法从证明密钥中恢复出 \(\alpha\)，所以保持该移位的唯一方法就是用相同的值乘以加密值 \(g^{l(s)}\) 和 \(g^{\alpha l(s)}\)。这样一来证明者就不能修改 \(l(x)\) 的单个系数，例如，如果 \(l(x) = ax^2 + bx + c\)，他只能一次将整个多项式乘以某个值 \(v\)：\(v(ax^2 + bx + c)= vax^2 + vbx + vc\)。由于配对，不能将多项式与另一个多项式相乘，\(s\) 的各个指数的 \(\alpha\)-移位会不可用。证明者既不能加也不能减，因为 \(g^{\alpha(l(x) + a'x^2 + c')} \neq g^{\alpha l(x)} \cdot g^{a' x^2} \cdot g^{c'}\)（这同样需要未加密的 \(\alpha\) 的知识）。

我们现在有了协议，但应该如何构造操作数多项式 \(l(x)\) 呢？由于任何整数都可以通过乘以 \(1\) 得到它本身，因此对于每个相应的运算，多项式的计算结果都应为 \(1\)，例如：

这允许证明者为 \(a\) 赋值：

备注 4.1 由于验证密钥包含 \(g^\alpha\)，因此可以对多项式加上（或减去）任意值 \(v'\)，即：

$$g^{v l(s)} \cdot g^{v'} = g^{v l(s) + v'}$$

$$g^{\alpha v l(s)} \cdot \left(g^{\alpha}\right)^{v'} = g^{\alpha (v l(s) + v')}$$

$$e\left( g^{\alpha (v l(s) + v')}, g \right) = e\left( g^{v l(s) + v'}, g^\alpha \right)$$

因此，可以修改多项式使其超出验证者的预期并证明一个不同的陈述。我们将在 4.9.3 节中解决这个问题。

译者注：这一节解决的问题是，算术电路中一个 Input Wire 或 Output Wire 可能会同时作为多个门的输入 Wire，如何才能确保约束这些公用 Wire。

由于要证明的数学表达式是公开的，那么各个算式之间的约束关系也就是公开的，我们就可以把构造多项式的工作交给设置环节，这样证明者只需要填上对应的数值就可以了。

上文的方法限制了在同一个操作数多项式上，不同的算式中使用同一个值时的约束关系。同样，如果一个操作数多项式中用到了多个值，也可以将这些值全部加起来，下面将会介绍。

多变量操作数多项式

现在，只有当所有左操作数都使用相同的变量时，我们才能单独设置值。如果我们再添加一个 \(d\) 呢：

如果使用相同的方法，我们将无法为每个变量单独设置值，并且每个不同的变量都将全部乘在一起。因此，这种受限多项式只能支持一个变量。如果检查多项式的性质，我们将看到把多项式相加也会让这些多项式的不同求值相加。因此，我们可以将操作数多项式 \(l(x)\) 分成操作数变量多项式 \(l_a(x)\) 和 \(l_d(x)\)（注意下标），从而用与上一节类似的方法分别赋值和限制变量 \(a\) 和 \(d\)，然后将它们加在一起以表示所有左操作数的变量。因为我们将操作数变量多项式相加，所以我们需要确保对于每个运算，操作数多项式只表示所有变量中的一个。

使用这个算术性质，我们可以构造每个操作数变量多项式，如果变量被用作相应运算中的操作数，则它的计算结果置为 \(1\)，否则就置为 \(0\)。\(0\) 乘以任何值都将保持为零，加在一起时将被忽略。对于我们的例子 \(l_a(x)\) 必须符合 \(l_a(1) = 1\)、\(l_a(2) = 1\) 和 \(l_a(3) = 0\) 并且 \(l_d(x)\) 在 1 和 2 处为零，但在 \(x = 3\) 处为 \(1\)：

因此，我们可以分别设置每个变量的值，然后将它们相加得到操作数多项式，例如，如果 \(a = 3\) 且 \(d = 2\)：

注：我们在一个值旁边使用下标来指示它代表哪个变量，例如，\(3_a\)是一个用值 \(3\) 实例化的变量 \(a\)。

让我们从现在开始用大写字母表示这样的复合操作数多项式，例如，\(L(x) = a\ l_a(x) + d\ l_d(x)\)，其求值为 \(L\)，即 \(L = L(s)\)。这种结构只有在每个操作数变量多项式都受验证者限制时才有效，有关左操作数的交互应该相应更改：

• 设置
  • 构造 \(l_a(x)\)、\(l_d(x)\) 使其在使用它的「运算 \(x\)」处经过 1，在所有其他运算中经过 0
  • 选择随机值 \(s\)、\(\alpha\)
  • 计算并加密未赋值的变量多项式： $$g^{l_a(s)}, g^{l_d(s)}$$
  • 计算这些多项式的移位： $$g^{\alpha l_a(s)}, g^{\alpha l_d(s)}$$
  • 生成证明密钥： $$\left( g^{l_a(s)}, g^{l_d(s)}, g^{\alpha l_a(s)}, g^{\alpha l_d(s)} \right)$$
  • 生成验证密钥： $$\left( g^\alpha \right)$$
• 证明
  • 将 \(a\) 和 \(d\) 赋值给变量多项式： $$\left(g^{l_a(s)}\right)^a, \left( g^{l_d(s)} \right)^d$$
  • 为移位的多项式赋相同的值： $$\left(g^{\alpha l_a(s)}\right)^a, \left( g^{\alpha l_d(s)} \right)^d$$
  • 将所有赋值的变量多项式相加，形成一个操作数多项式的形式： $$g^{L(s)} = g^{a l_a(s)} \cdot g^{d l_d(s)} = g^{a l_a(s) + d l_d(s)}$$
  • 将移位并赋值的变量多项式相加，形成一个移位的操作数多项式的形式： $$g^{\alpha L(s)} = g^{a \alpha l_a(s)} \cdot g^{d \alpha l_d(s)} = g^{\alpha \left(a l_a(s) + d l_d(s) \right)}$$
  • 提供左操作数有效赋值的证明： $$\left( g^{L(s)}, g^{\alpha L(s)} \right)$$
• 验证
  • 将证明解析为 \(\left( g^L, g^{L'} \right)\)
  • 检查提供的多项式是否是最初提供的未赋值的变量多项式的倍数之和： $$e\left( g^{L'}, g \right) = e\left( g^{L}, g^\alpha \right)$$ 也就是检查了 $$\alpha\ a l_a(s) + \alpha\ d l_d(s) = \alpha \times (a l_a(s) + d l_d(s))$$

注：\(L(s)\) 和 \(\alpha L(s)\) 一次表示所有变量多项式，由于 \(\alpha\) 仅用于变量多项式的求值，因此证明者别无选择，只能使用提供的加密值并给原始和移位的变量多项式赋值相同的系数。

结果，证明者：

• 除了「赋」值以外，不能通过改变系数来修改提供的变量多项式，因为证明者只提供这些多项式的加密值，也因为 \(s\) 的必要加密幂不能与它们的 \(\alpha\)-移位分开
• 无法对提供的多项式加上另一个多项式，因为 \(\alpha\)-比率将会被破坏
• 不能通过乘以其他多项式 \(u(x)\) 来修改操作数多项式，这可能让修改的值不成比例，因为在预配对空间中无法进行加密乘法

注：如果我们将一个多项式（例如 \(l_a(x)\)）与另一个多项式（例如 \(l_d'(x) = c_{d} \cdot l_d(x) + c_{a}' \cdot l_a(x)\)）相加（或相减），这并不是对多项式 \(l_d(x)\) 的真正修改，而是对 \(l_a(x)\) 的结果系数的改变，因为它们最后会被加到一起： $$L(x) = c_{a} \cdot l_a(x) + l_d'(x) = \left(c_a + c_a'\right) \cdot l_a(x) + c_d \cdot l_d(x)$$

虽然证明者限制了多项式的使用，但仍然存在一些可允许范围内的自由：

• 如果证明者决定不加入一些赋值的变量多项式 \(l_i(x)\) 来形成操作数多项式 \(L(x)\) 也是可以接受的，因为这种情况与赋值为 \(0\) 时相同：\(g^{a l_a(x)} = g^{a l_a(x) + 0 l_d(x)}\)
• 如果证明者多次加入相同的变量多项式也是可以接受的，因为它与一次赋值该值的倍数次时相同，例如 \(g^{a l_a(x)}\cdot g^{a l_a(x)} \cdot g^{a l_a(x)} = g^{3a l_a(x)}\)

这种方法在右操作数和输出多项式 \(R(x)\)、\(O(x)\) 上也同样适用。

译者注：目前证明协议的大致思路为：

1. 将要证明的程序转换为用数学语言表达的形式（即加减乘除的计算）
2. 用多项式在某处的取值来进行计算以表示数学运算，进而进行证明
3. 用多项式在多处的取值来进行计算以表示多个数学运算，进而进行证明
4. 对证明的「程序」在不同计算中使用的相同变量进行约束

当前的协议约束只解决了部分问题，还有许多可以改进的地方，下一节中将会展开讨论这些改进，并对证明协议进行优化。

结构属性

这种修改还带来了许多额外的有用特性。

常数系数

在上面的结构中，我们一直在使用未赋值的变量多项式 \(1\) 或 \(0\) 的求值来表示变量是否在运算中被使用。自然，我们也可以使用包括负系数在内的其他系数，因为我们可以对多项式进行插值来经过任何必要的点（假设没有两个运算占用相同的 \(x\)）。此类运算的示例如下：

$$\color{ForestGreen}{2a}\quad \times \quad\color{blue}{1b}\quad = \quad\color{red}{3r}$$

$$\color{ForestGreen}{-3a}\quad \times \quad\color{blue}{1b}\quad = \quad\color{red}{-2r}$$

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

算法 2：常数系数

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

这些系数将在设置阶段「硬编码」，类似于 \(1\) 或 \(0\) 而且是不可变的。我们可以相应修改运算的形式：

$$\color{ForestGreen}{c_a \cdot a}\quad \times \quad\color{blue}{c_b \cdot b}\quad = \quad\color{red}{c_r \cdot r}$$

或者更正式地说，对于变量 \(v_i \in \{v_1, v_2, ..., v_n\}\)：

$$\color{ForestGreen}{c_l \cdot v_l}\quad \times \quad\color{blue}{c_r \cdot v_r}\quad = \quad\color{red}{c_o \cdot v_o}$$

其中 \(l, r, o\) 是运算中使用的变量的索引。

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

无成本加法

看一下更新后的结构，很明显在多项式表示中，由一些不同的 \(x\) 表示的每个操作数都是所有操作数变量多项式的总和，因此只有单个使用的变量可以具有非零值，而所有其他变量都为零。下图很好地说明了这一点：

我们可以利用这种结构，并允许为运算中的每个操作数添加任意数量的必要变量。例如在第一个运算中，我们可以先做加法 \(a + c\)，然后再乘以其他操作数，例如 \(\color{ForestGreen}{(a + c)} \times \color{blue}{b} = \color{red}{r}\)，这可以表示为：

因此，可以在单个操作数中添加任意数量的当前变量，对它们中的每一个使用任意系数，这样可以根据各个程序的需要来生成将在相应运算中使用的操作数的值。这种特性有效地允许将运算结构更改为：

$$\color{ForestGreen}{(c_{\textrm{l},a} \cdot a + c_{\textrm{l},b} \cdot b + \ldots)}\quad \times \quad\color{blue}{(c_{\textrm{r},a} \cdot a + c_{\textrm{r},b} \cdot b + \ldots)}\quad = \quad\color{red}{(c_{\textrm{o},a} \cdot a + c_{\textrm{o},b} \cdot b + \ldots)}$$

或更正式地说，对于变量 \(v_i \in \{v_1, v_2, ..., v_n\}\) 和操作数变量系数 \(c_{\textrm{l},i} \in \{c_{\textrm{l},1}, c_{\textrm{l},2}, ..., c_{\textrm{r},n}\}\)，\(c_{\textrm{r},i} \in \{c_{\textrm{r},1}, c_{\textrm{r},2}, ..., c_{\textrm{r},n}\}\)，\(c_{\textrm{o},i} \in \{c_{\textrm{o},1}, c_{\textrm{o},2}, ..., c_{\textrm{o},n}\}\)：

$$\color{ForestGreen}{\sum_{i=1}^{n} c_{\textrm{l},i} \cdot v_i}\quad \times \quad\color{blue}{\sum_{i=1}^{n} c_{\textrm{r},i} \cdot v_i}\quad = \quad\color{red}{\sum_{i=1}^{n} c_{\textrm{o},i} \cdot v_i}$$

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

译者注：乘法运算是关键，而加法运算可以被合并到一个更大的乘法运算里。

加法、减法和除法

到目前为止，我们一直专注于乘法运算。然而，为了能够执行通用计算，真实环境下的程序还需要加法、除法和减法。

加法： 在上一节中，我们已经确定可以在单个操作数的情况下添加变量，然后将其乘以另一个操作数，例如 \(\color{ForestGreen}{(3a + b)} \times \color{blue}{d} = \color{red}{r}\)，但是如果我们只需要加法而不需要乘法，例如，如果一个程序需要计算 \(\mathrm{a} + \mathrm{b}\)，我们可以将其表示为：

$$\color{ForestGreen}{(a + b)}\quad \times \quad\color{blue}{1}\quad = \quad\color{red}{r}$$

注：由于我们的结构对每个操作数都需要一个常数系数和一个变量（\(\color{blue}{c \cdot v}\)），所以 \(\color{blue}{1}\) 的值被表示为 \(c_{one} \cdot v_{one}\)，虽然 \(c_{one} = 1\) 可以被「硬编码」到对应的多项式中，但 \(v_{one}\) 是一个变量，可以被赋任何值，因此我们必须通过 4.10 节中解释的约束来限制 \(v_{one}\) 的值。

减法： 减法几乎与加法相同，唯一的区别是一个负系数，例如，对于 \(\mathrm{a - b}\)：

$$\color{ForestGreen}{(a + -1 \cdot b)}\quad \times \quad\color{blue}{1}\quad = \quad\color{red}{r}$$

除法： 如果我们观察除法运算 \(\mathsf{\frac{因子}{除数} = 结果}\)，可以发现将除法的 \(\mathsf{结果}\) 乘以 \(\mathsf{除数}\) 就能得到 \(\mathsf{因子}\)。因此我们可以用乘法表达相同的含义：\(\mathsf{除数 \times 结果 = 因子}\)。如果我们要证明除法运算 \(\mathrm{\frac{a}{b} = r}\)，可以将其表示为：

$$\color{ForestGreen}{b}\quad \times \quad\color{blue}{r}\quad = \quad\color{red}{a}$$

注：运算的结构也被称为「约束（Constraint）」，由多项式结构表示的运算本身并非是为了计算结果，而是检查证明者是否已经知道变量（包括结果），并且它们对运算来说是有效的，也就是说，无论这些值是什么，证明者都必须提供一致的值。

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

译者注：约束和运算有一定的关联性。算术电路的目的是实现计算的验证，而非计算的过程。

上文中，我们提出了一种方法：把构造多项式的工作交给设置环节，证明者只需要填上对应的数值就可以了。这个方法不仅解决了同一个操作数的运算符不一致的问题，同时还带来了额外的便利：

1. 允许执行计算的表达式中包含静态系数。

2. 虽然 \(l(x) \times r(x) = o(x)\) 的关系中只有乘法，但利用这个方法也能轻松地执行加法运算，同时也解决了减法和除法的问题。

示例计算

有了通用运算的结构，我们就可以将原来的算法 1 转换为一组运算，并进一步转换为多项式形式。算法的数学形式是（我们将使用变量 \(v\) 来表示运算结果）：

$$w \times (a \times b) + (1 - w) \times (a + b) = v$$

它有三个乘法，由于运算结构只支持一个乘法，所以至少会有 3 个运算。但是，我们可以简化方程：

$$w \times (a \times b) + a + b - w \times (a + b) = v$$

$$w \times (a \times b - a - b) = v - a - b$$

现在要保持同样的关系只需要两个乘法。运算的完整形式是：

$$1:\quad\color{ForestGreen}{1\cdot a}\quad \times \quad\color{blue}{1\cdot b}\quad = \quad\color{red}{1 \cdot m}$$

$$2:\quad\color{ForestGreen}{1\cdot w}\quad \times \quad\color{blue}{1\cdot m\ +\ -1\cdot a\ + \ -1\cdot b}\quad = \quad\color{red}{1 \cdot v\ +\ -1 \cdot a\ +\ -1 \cdot b}$$

我们还可以添加一个要求 \(w\) 必须是二进制的约束，否则证明者就可以使用其他的 \(w\) 取值去执行一个不正确的运算：

$$3:\quad\color{ForestGreen}{1\cdot w}\quad \times \quad\color{blue}{1\cdot w}\quad = \quad\color{red}{1\cdot w}$$

要说明为什么 \(w\) 只能是 0 或 1，我们可以将方程表示为 \(w^2 - w = 0\)，然后进一步表示为 \((w - 0)(w - 1) = 0\)，其中 0 和 1 是唯一的解。

这里总共有 5 个变量，其中 2 个在左操作数中，4 个在右操作数中，5 个在输出中。操作数多项式为：

$$\color{ForestGreen}{L(x)} = \color{ForestGreen}{ a \cdot l_a(x) + w \cdot l_w(x) }$$

$$\color{blue}{R(x)} = \color{blue}{ m \cdot r_{m}(x) + a \cdot r_a(x) + b \cdot r_b(x) + w\cdot r_w(x) }$$

$$\color{red}{O(x)} = \color{red}{ m \cdot o_{m}(x) + v \cdot o_v(x) + a \cdot o_a(x) + b \cdot o_b(x) + w\cdot o_w(x) }$$

其中每个变量多项式必须为 3 个运算中的每一个运算计算出一个相应的系数，如果变量不存在于运算的操作数或输出中，则计算为 0：

因此，辅因子多项式是 \(t(x) = (x-1)(x-2)(x-3)\)，这可以确保所有三个运算都已经被正确计算。

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

绘制出来就是：

现在我们就可以通过多项式来证明计算了。首先，我们为函数选择输入值，例如 \(w = 1, a = 3, b = 2\)。接着，从运算中计算中间变量的值：

$$m = a \times b = 6$$

$$v = w(m - a - b) + a + b = 6$$

之后，我们将计算结果所涉及的所有值赋给相应的变量多项式，并将它们相加，形成操作数和输出多项式的形式：

$$\color{ForestGreen}{L(x)} = \color{ForestGreen}{ 3 \cdot l_a(x) + 1 \cdot l_w(x) } = x^2 - 5x + 7$$

$$\color{blue}{R(x)} = \color{blue}{ 6 \cdot r_{m}(x) + 3 \cdot r_a(x) + 2 \cdot r_b(x) + 1\cdot r_w(x) } = \frac{1}{2} x^2 - 2\frac{1}{2}x + 4$$

$$\color{red}{O(x)} = \color{red}{ 6 \cdot o_{m}(x) + 6 \cdot o_v(x) + 3 \cdot o_a(x) + 2 \cdot o_b(x) + 1\cdot o_w(x) } = 2\frac{1}{2} x^2 - 12\frac{1}{2}x + 16$$

在图中表示为：

加起来表示相应运算中的操作数和输出值：

我们需要证明 \(L(x) \times R(x) - O(x) = t(x)\ h(x)\)，因此要找出 \(h(x)\)：

$$h(x) = \frac{L(x) \times R(x) - O(x)}{t(x)} = \frac{\frac{1}{2}x^4 - 5x^3 + \frac{35}{2} x^2 - 25x + 12}{(x-1)(x-2)(x-3)} = \frac{1}{2}x - 2$$

在图中表示为：

可见多项式 \(L(x)\times R(x) - O(x)\) 有解 \(x = 1\)、\(x = 2\) 和 \(x = 3\)，因此 \(t(x)\) 是它的辅因子，如果我们使用不一致的变量值，情况就不是这样了。

这就是正确计算执行的变量值的知识在多项式层面上证明的方法。下面证明者还要继续处理协议的密码学部分。

可验证计算协议

我们对多项式知识协议（3.7 节）做了许多重要的修改来让它更具有通用性，让我们看看它现在是如何定义的。假设函数 \(f(*)\) 的计算结果是证明的主体，运算的数量为 \(d\)，变量的数量为 \(n\)，对应的系数为 \(\left\{ c_{L,i,j}, c_{R,i,j}, c_{O,i,j} \right\}_{i \in \{1, \ldots, n\}, j \in \{1, \ldots, d\}}\)：

• 设置
  • 为左操作数 \(\left\{ l_i(x) \right\}_{i \in \{1, \ldots, n\}}\) 构造变量多项式，使得对于 \(j \in \{1, \ldots, d\}\) 的所有运算都求值为相应的系数，即 \(l_i(j) = c_{L,i,j}\)，右操作数和输出同理
  • 选择随机值 \(s, \alpha\)
  • 计算 \(t(x) = (x-1)(x-2)\ldots(x-d)\) 以及 \(g^{t(s)}\)
  • 计算证明密钥：\(\left( \left\{ g^{s^k} \right\}_{k \in [d]}, \left\{ 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)} \right\}_{i \in \{1,\ldots,n\}} \right)\)
  • 计算验证密钥：\(\left(g^{t(s)}, g^{\alpha}\right)\)
• 证明
  • 计算函数 \(f(*)\) 和相应的变量值 \(\left\{ v_i \right\}_{i \in \{1,\ldots,n\}}\)
  • 计算 \(h(x) = \frac{L(x) \times R(x) - O(x)}{t(x)}\)，其中 \(L(x) = \sum_{i=1}^n v_i \cdot l_i(x)\)，\(R(x), O(x)\) 同理
  • 给变量赋值并求和来得到操作数多项式： $$g^{L(s)} = \left(g^{l_1(s)}\right)^{v_1} \cdots \left(g^{l_n(s)}\right)^{v_n},\ g^{R(s)} = \prod_{i=1}^{n} \left(g^{r_i(s)}\right)^{v_i},\ g^{O(s)} = \prod_{i=1}^{n} \left(g^{o_i(s)}\right)^{v_i}$$
  • 将变量值赋给移位的多项式： $$g^{\alpha L(s)} = \prod_{i=1}^{n} \left(g^{\alpha l_i(s)}\right)^{v_i},\ g^{\alpha R(s)} = \prod_{i=1}^{n} \left(g^{\alpha r_i(s)}\right)^{v_i},\ g^{\alpha O(s)} = \prod_{i=1}^{n} \left(g^{\alpha o_i(s)}\right)^{v_i}$$
  • 使用提供的 \(s\) 的幂计算加密值 \(g^{h(s)}\)：\(\left\{ g^{s^k} \right\}_{k \in [d]}\)
  • 构造证明：\(\left( g^{L(s)}, g^{R(s)}, g^{O(s)}, g^{\alpha L(s)}, g^{\alpha R(s)}, g^{\alpha O(s)}, g^{h(s)} \right)\)
• 验证
  • 将证明解析为：\(\left( g^L, g^R, g^O, g^{L'}, g^{R'}, g^{O'}, g^h \right)\)
  • 检查变量多项式限制： $$e(g^{L}, g^\alpha) = e(g^{L'}, g),\quad e(g^{R}, g^\alpha) = e(g^{R'}, g), \quad e(g^{O}, g^\alpha) = e(g^{O'}, g)$$
  • 检查运算的有效性： $$e(g^{L}, g^{R}) = e(g^{t}, g^{h}) \cdot e(g^{O}, g)$$

注：使用符号 \(\prod\) 可以简洁地表达多个元素的乘积，即 \(\prod_{i=1}^n v_i = v_1 \cdot v_2 \cdot \ldots \cdot v_n\)。

所有变量多项式 \(\{l_i(x), r_i(x), o_i(x)\}_{i \in \{1, \ldots, n\}}\) 和目标多项式 \(t(x)\) 的集合被称为二次算术程序（Quadratic Arithmetic Program，QAP，参见 [Gen+12]）。

虽然这个协议足够健壮，可以进行一般计算验证，但还有两个必须要解决的安全问题。

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

由于我们对变量多项式限制的所有操作数都使用相同的 \(\alpha\)，所以无法阻止证明者：

• 使用来自其他操作数的变量多项式，例如 \(L'(s) = o_1(s) + r_1(s) + r_5(s) + \ldots\)
• 完全交换操作数多项式，例如交换 \(O(s)\) 与 \(L(s)\) 得到运算 \(\color{ForestGreen}{O(s)}\ {\times}\ \color{blue}{R(s)}\ =\ \color{red}{L(s)}\)
• 重复使用相同的操作数多项式，例如 \(\color{ForestGreen}{L(s)}\ {\times}\ \color{blue}{L(s)}\ =\ \color{red}{O(s)}\)

这种可互换性意味着证明者可以改变执行并有效地证明一些其他的计算。阻止这种行为的一个很明显的方法是对不同的操作数使用不同的 \(\alpha\)，具体来说我们修改为：

• 设置
  • \(\ldots\)
  • 选择随机值 \(\alpha_{l}, \alpha_{r}, \alpha_{o}\) 而不是 \(\alpha\)
  • 计算相应的「移位」\(\left\{g^{\alpha_{l} l_i(s)}, g^{\alpha_{r} r_i(s)}, g^{\alpha_{o} o_i(s)}\right\}_{i \in \{1 \ldots n\}}\)
  • 证明密钥：\(\left(\left\{ g^{s^k} \right\}_{k \in [d]}, \left\{g^{l_i(s)}, g^{r_i(s)}, g^{o_i(s)}, g^{\alpha_{l} l_i(s)}, g^{\alpha_{r} r_i(s)}, g^{\alpha_{o} o_i(s)} \right\}_{i \in \{1 \ldots n\}} \right)\)
  • 验证密钥：\(\left( g^{t(s)}, g^{\alpha_{l}}, g^{\alpha_{r}}, g^{\alpha_{o}} \right)\)
• 证明
  • \(\ldots\)
  • 将变量值赋给「移位」的多项式 $$g^{\alpha_{l} L(s)} = \prod_{i=1}^{n} \left( g^{\alpha_{l} l_i(s)} \right)^{v_i},\ g^{\alpha_{r} R(s)} = \prod_{i=1}^{n} \left(g^{\alpha_{r} r_i(s)} \right)^{v_i},\ g^{\alpha_{o} O(s)} = \prod_{i=1}^{n} \left(g^{\alpha_{o} o_i(s)} \right)^{v_i}$$
  • 构造证明：\(\left(g^{L(s)}, g^{R(s)}, g^{O(s)}, g^{\alpha_{l} L(s)}, g^{\alpha_{r} R(s)}, g^{\alpha_{o} O(s)}, g^{h(s)} \right)\)
• 验证
  • \(\ldots\)
  • 检查变量多项式限制： $$e\left( g^{L}, g^{\alpha_{l}} \right) = e\left( g^{L'}, g \right), \quad e\left( g^{R}, g^{\alpha_{r}} \right) = e\left( g^{R'}, g \right), \quad e\left( g^{O}, g^{\alpha_{o}} \right) = e\left( g^{O'}, g \right)$$

现在就不能使用来自其他操作数的变量多项式了，因为证明者不知道 \(\alpha_{l}, \alpha_{r}, \alpha_{o}\)。

译者注：这里通过对 \(L(x)\)、\(R(x)\) 和 \(O(x)\) 分别进行 KEA 检查，解决了上文中提到的第二个缺陷——由于证明者生成的证明中只有计算结果，左操作数、右操作数、输出在计算中混用也不会被发现。

下节将会解决上文中提到的第三个缺陷——由于左操作数、右操作数、输出是分开表示的，相互之间的关系无法进行约束。

跨操作数的变量一致性

对于任何变量 \(v_i\)，我们必须将其值赋给每个对应操作数的变量多项式，即 \(\left(g^{l_i(s)}\right)^{v_i}, \left(g^{r_i(s)}\right)^{v_i}, \left(g^{o_i(s)}\right)^{v_i}\)。因为每个操作数多项式的有效性都是单独检查的，所以没有强制要求在相应的变量多项式中使用相同的变量值。这意味着左操作数中变量 \(v_i\) 的值可能与右操作数或输出中变量 \(v_i\) 的值不同。

我们可以使用已经熟悉的限制多项式的方法来强制跨操作数的变量值相等（就像我们对变量多项式所做的那样）。如果我们可以在所有操作数上创建一个「移位校验和」变量多项式，就可以限制证明者只能赋相同的值。验证者可以将每个变量的多项式组合成一个，例如 \(g^{l_i(s) + r_i(s) + o_i(s)}\)，并将其移位一些另外的随机值 \(\beta\)，即 \(g^{\beta\left(l_i(s) + r_i(s) + o_i(s)\right)}\)。这个移位的多项式会被提供给证明者，来将变量与变量多项式一起赋值：

$$\left(g^{l_i(s)}\right)^{v_{L,i}}, \left(g^{r_i(s)}\right)^{v_{R,i}}, \left(g^{o_i(s)}\right)^{v_{O,i}}, \left(g^{\beta(l_i(s) + r_i(s) + o_i(s))}\right)^{v_{\beta,i}}$$

接着 \(\beta\) 被加密为 \(g^\beta\) 并添加到验证密钥中。现在，如果所有 \(v_i\) 的值都相同（即 \(v_{L,i} = v_{R,i} = v_{O,i} = v_{\beta,i}\)，其中 \(i \in \{1, \ldots, n\}\)），则下面的等式应成立：

$$e\left( g^{v_{L,i} \cdot l_i(s)} \cdot g^{v_{R,i} \cdot r_i(s)} \cdot g^{v_{O,i} \cdot o_i(s)}, g^\beta \right) = e\left( g^{v_{\beta,i} \cdot \beta(l_i(s) + r_i(s) + o_i(s))}, g \right)$$

尽管这个一致性校验很有用，但由于 \(l(s), r(s), o(s)\) 中的至少两个可能具有相同的计算值、一个多项式可被另一个整除等等发生的概率不可忽略，这将允许证明者将值 \(v_{L,i}, v_{R,i}, v_{O,i}, v_{\beta,i}\) 分解为至少其中两个不相等但保持等式成立，从而使检查无效：

$$\left(v_{L,i} \cdot l_i(s) + v_{R,i} \cdot r_i(s) + v_{O,i} \cdot o_i(s)\right) \cdot \beta = v_{\beta,i} \cdot \beta\cdot\left(l_i(s) + r_i(s) + o_i(s)\right)$$

例如，让我们考虑一个单一运算，其中 \(l(x) = r(x)\)。我们把这两个的值表示为 \(w = l(s) = r(s)\) 和 \(y = o(x)\)。等式将如下所示：

$$\beta (v_{L}\ w + v_{R}\ w + v_{O}\ y) = v_{\beta} \cdot \beta (w + w + y)$$

对于任意的 \(v_{R}\) 和 \(v_{O}\)，这种形式允许令 \(v_{\beta} = v_{O}\)，\(v_{L} = 2 v_{O} - v_{R}\)，此时转化为：

$$\beta (2 v_O\ w - v_{R}\ w + v_{R}\ w + v_{O}\ y) = v_O \cdot \beta (2w + y)$$

因此，这种一致性策略是无效的。缓解这种情况的一种方法是对每个操作数使用不同的 \(\beta\)，确保操作数的变量多项式具有不可预测的值。以下是协议的修改：

• 设置
  • \(\ldots\) 选择随机值 \(\beta_{l}, \beta_{r}, \beta_{o}\)
  • 计算、加密变量一致性多项式并添加到证明密钥： $$\left\{ g^{\beta_{l} l_i(s) + \beta_{r} r_i(s) + \beta_{o} o_i(s)} \right\}_{i \in \{1,\ldots,n\}}$$
  • 加密 \(\beta\) 并添加到验证密钥：\(\left( g^{\beta_{l}}, g^{\beta_{r}}, g^{\beta_{o}} \right)\)
• 证明
  • \(\ldots\) 将变量值赋给变量一致性多项式： $$g^{z_i(s)} = \left( g^{\beta_{l} l_i(s) + \beta_{r} r_i(s) + \beta_{o} o_i(s)} \right)^{v_i}\quad 其中 \ i \in \{1,\ldots,n\}$$
  • 在加密空间中添加赋值的多项式： $$g^{Z(s)} = \prod_{i=1}^n g^{z_i(s)} = g^{\beta_{l} L(s) + \beta_{r} R(s) + \beta_{o} O(s)}$$
  • 添加到证明中：\(g^{Z(s)}\)
• 验证
  • \(\ldots\) 检查提供的操作数多项式和「校验和」多项式之间的一致性： $$e\left( g^{L}, g^{\beta_{l}} \right) \cdot e\left( g^{R}, g^{\beta_{r}} \right) \cdot e\left( g^{O}, g^{\beta_{o}} \right) = e\left( g^{Z}, g \right)$$ 这相当于： $${e\left( g,g \right)}^{\beta_{l} L + \beta_{r} R + \beta_{o} O} = {e\left( g,g \right)}^{Z}$$

使用相同的变量值来中和的技术将在这种结构中失败，因为不同的 \(\beta\) 使相同的多项式不适合操纵。然而，还有一个类似于备注 4.1 的缺陷，具体来说，由于 \(g^{\beta_l}, g^{\beta_r}, g^{\beta_o}\) 项是公开可用的，所以对手可以修改任何变量多项式的零指数系数，因为它不依赖于 \(s\)，即 \(g^{\beta_l s^0} = g^{\beta_l}\)。

译者注：上文我们通过在设置阶段设置数学表达式的约束关系解决了一些问题，但这里似乎又引入了新问题：如何保证证明者构造的证明是遵循这些约束关系计算出来的呢？

KEA 其实已经解决了这个问题，但似乎并不完美，这就是下面要讨论的变量延展性问题。

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

变量多项式的延展性

让我们用以下两个运算作为例子来说明备注 4.1：

$$\color{ForestGreen}{a}\quad \times \quad\color{blue}{1}\quad = \quad\color{red}{b}$$

$$\color{ForestGreen}{3a}\quad \times \quad\color{blue}{1}\quad = \quad\color{red}{c}$$

预期结果是 \(b = a\) 和 \(c = 3a\)，有明确的 \(c = 3b\) 的关系。这意味着左操作数的变量多项式的求值为 \(l_a(1) = 1\) 和 \(l_a(2) = 3\)。无论 \(l_a(x)\) 的形式如何，证明者都可以通过提供修改的多项式 \(l'_a(x) = a l_a(x) + 1\) 来不成比例地赋 \(a\) 的值。因此求值将会变成 \(l'_a(1) = a + 1\) 和 \(l'_a(2) = 3a + 1\)，结果 \(b = a + 1\)，\(c = 3a + 1\)，其中 \(c \neq 3b\)，实际上意味着 \(a\) 的值在不同的运算中是不一样的。

因为证明者已知 \(g^{\alpha_l}\) 和 \(g^{\beta_l}\)，所以他可以同时满足正确的操作数多项式和变量值一致性检查：

• \(\ldots\) 证明
  • 通过不成比例地赋值变量 \(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)} = \left( g^{l_a(s)} \right)^a \cdot g^1\)，用常规方式计算 \(g^{R(s)}, g^{O(s)}\)
  • 计算 \(\alpha\)-移位：\(g^{\alpha L(s)} = \left( g^{\alpha l_a(s)} \right)^a \cdot g^\alpha\)，用常规方式计算 \(g^{\alpha R(s)}, g^{\alpha O(s)}\)
  • 计算变量一致性多项式： $$g^{Z(s)} = \prod_{i \in \{1, a, b, c\}} \left( g^{\beta_l l_i(s) + \beta_r r_i(s) + \beta_o o_i(s)} \right)^i \ \cdot g^{\beta_l} = g^{\beta_l (L(s) + 1) + \beta_r R(s) + \beta_o O(s)}$$ （其中下标 \(_i\) 代表对应变量的符号，指数 \(^i\) 代表变量的值；此外，未定义的变量多项式等于零。）
  • 构造证明：\(\left( g^{L(s)}, g^{R(s)}, g^{O(s)}, g^{\alpha_l L(s)}, g^{\alpha_r R(s)}, g^{\alpha_o O(s)}, g^{Z(s)}, g^{h(s)} \right)\)
• 验证
  • 检查变量多项式限制： $$e\left( g^{L'}, g \right) = e\left( g^{L}, g^\alpha \right) \ \ \Rightarrow \ \ e\left( g^{\alpha a \cdot l_a(s) + \alpha}, g \right) = e\left( g^{a l_a(s) + 1}, g^\alpha \right)$$ 用常规方式计算 \(g^{R'}, g^{O'}\)
  • 检查变量值一致性 $$e\left( g^{L}, g^{\beta_l} \right) \cdot e\left( g^{R}, g^{\beta_r} \right) \cdot e\left( g^{O}, g^{\beta_o} \right) = e\left( g^{Z}, g \right) \Rightarrow$$ $${e\left( g, g \right)}^{(a\cdot l_a + 1) \beta_l + R\beta_r + O\beta_o} = e\left( g, g \right)^{\beta_l (L + 1) + \beta_r R + \beta_o O}$$
  • 检查运算的有效性 \(e(g^{L}, g^{R}) = e(g^{t}, g^{h}) \cdot e(g^{O}, g)\)

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

此外，可以使用 \(g^{\beta_l}, g^{\beta_r}, g^{\beta_o}\) 就允许在不同的操作数中使用相同变量的不同值。例如，如果我们有一个运算：

$$\color{ForestGreen}{a}\quad \times \quad\color{blue}{a}\quad = \quad\color{red}{b}$$

可以用变量多项式表示：

$${\color{ForestGreen}{l_a(x) = x}},\quad {\color{blue}{r_a(x) = x}},\quad {\color{red}{o_a(x) = 0}}$$

$${\color{ForestGreen}{l_b(x) = 0}},\quad {\color{blue}{r_b(x) = 0}},\quad {\color{red}{o_b(x) = x}}$$

虽然我们预期的输出是 \(b = a^2\)，但我们可以设置不同的 \(a\) 值，例如 \({\color{ForestGreen}{a = 2}}\)，\({\color{blue}{a = 5}}\) 如下：

• 证明
  • \(\ldots\) 用 \(a = 2\) 构造左操作数多项式：\(L(x) = 2 l_a(x) + 10 l_b(x)\)
  • 用 \(a = 5\) 构造右操作数多项式：\(R(x) = 2 r_a(x) + 3 + 10 r_b(x)\)
  • 用 \(b = 10\) 构造输出多项式：\(O(x) = 2 o_a(x) + 10 o_b(x)\)
  • \(\ldots\) 计算加密值： $$g^{L(s)} = \left( g^{l_a(s)} \right)^2 \cdot \left( g^{l_b(s)} \right)^{10} = g^{2l_a(s) + 10 l_b(s)}$$ $$g^{R(s)} = \left( g^{r_a(s)} \right)^2 \cdot (g)^3 \cdot \left( g^{r_b(s)} \right)^{10} = g^{2r_a(s) + 3 + 10 r_b(s)}$$ $$g^{O(s)} = \left( g^{o_a(s)} \right)^2 \cdot \left( g^{o_b(s)} \right)^{10} = g^{2 o_a(s) + 10 o_b(s)}$$
  • 计算变量一致性多项式： $$g^{Z(s)} = \left( g^{\beta_l l_a(s) + \beta_r r_a(s) + \beta_o o_a(s)} \right)^{2} \ \cdot \left( g^{\beta_r} \right)^{3} \cdot \left( g^{\beta_l l_b(s) + \beta_r r_b(s) + \beta_o o_b(s)} \right)^{10} = $$ $$g^{\beta_l \left(2 l_a(s) + 10 l_b(s) \right)\ +\ \beta_r (2 r_a(s) + 3 + 10 r_b(s))\ +\ \beta_o (2 o_a(s) + 10 o_b(s))}$$
• 验证
  • \(\ldots\) 检查变量值一致性，应满足： $$e\left( g^{L}, g^{\beta_l} \right) \cdot e\left( g^{R}, g^{\beta_r} \right) \cdot e\left( g^{O}, g^{\beta_o} \right) = e\left( g^{Z}, g \right)$$

注：多项式 \(o_a(x), l_b(x), r_b(x)\) 其实可以忽略不计，因为它们对于任何 \(x\) 的计算结果都为 0，但是为了完整性，我们仍然保留它们。

这种能力破坏了证明的可靠性（Soundness）。很明显，不应该将加密的 \(\beta\) 提供给证明者。

非延展性

解决延展性的一种方法是在设置阶段将 \(g^{\beta_l},\ g^{\beta_r},\ g^{\beta_o}\) 在加密空间中乘以随机秘密值 \(\gamma\)（Gamma）来使验证密钥中的 \(g^{\beta_l},\ g^{\beta_r},\ g^{\beta_o}\) 与 \(g^{Z(s)}\) 不兼容：\(g^{\beta_l \gamma},\ g^{\beta_r \gamma},\ g^{\beta_o \gamma}\)。这种屏蔽（Mask）加密不允许用有意义的方式修改 \(g^{Z(s)}\)，因为 \(Z(s)\) 不是 \(\gamma\) 的倍数，即 \(g^{Z(s)} \cdot g^{v'\cdot\beta_l \gamma} = g^{\beta_l (L(s) + \color{yellow}{v' \gamma} ) + \beta_r R(s) + \beta_o O(s)}\)。因为证明者不知道 \(\gamma\)，所以更改将会是随机的。修改要求我们将 \(Z(s)\) 乘以 \(\gamma\) 来平衡协议中的变量值一致性检查方程：

• 设置
  • 选择随机值 \(\beta_l, \beta_r, \beta_o, \gamma\)
  • 生成验证密钥：\(\left(\ldots, g^{\beta_l \gamma}, g^{\beta_r \gamma}, g^{\beta_o \gamma}, g^{\gamma} \right)\)
• 证明 \(\ldots\)
• 验证
  • \(\ldots\) 检查变量值一致性，应满足： $$e\left( g^{L}, g^{\beta_l \gamma} \right) \cdot e\left( g^{R}, g^{\beta_r \gamma} \right) \cdot e\left( g^{O}, g^{\beta_o \gamma} \right) = e\left( g^{Z}, g^\gamma \right)$$

需要注意的是，我们排除了变量多项式为 0 阶的情况（例如 \(l_1(x) = 1x^0\)），否则在任何两个操作数 / 输出为零的情况下，将允许在证明密钥 \(\left\{ g^{\beta_l l_i(s) + \beta_r r_i(s) + \beta_o o_i(s)} \right\}_{i \in \{1,\ldots,n\}}\) 的变量一致性多项式中暴露 \(\beta\) 的加密，例如，对于 \(l_1(x) = 1,\ r_1(s) = 0,\ o_1(s) = 0\)，这将导致 \(g^{\beta_l l_1(s) + \beta_r r_1(s) + \beta_o o_1(s)} = g^{\beta_l}\)。

我们也可以用类似的方法屏蔽 \(\alpha\) 来解决变量多项式的延展性。但这并不是必需的，因为对变量多项式的任何修改都需要被反映在无法修改的变量一致性多项式中。

变量值一致性检查的优化

变量值一致性检查现在是有效的，但它在验证密钥中增加了 4 个昂贵的配对运算和 4 个新术语。Pinocchio 协议 [Par+13] 通过为每个操作数巧妙地选择生成元 \(g\) 来固化（Ingrain）「移位」：

• 设置
  • \(\ldots\) 选择随机值 \(\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}\)
  • 生成证明密钥： $$\left(\left\{ g^{s^k} \right\}_{k \in [d]}, \left\{g_l^{l_i(s)}, g_r^{r_i(s)}, g_o^{o_i(s)}, g_l^{\alpha_l l_i(s)}, g_r^{\alpha_r r_i(s)}, g_o^{\alpha_o o_i(s)}, g_l^{\beta l_i(s)} \cdot g_r^{\beta r_i(s)} \cdot g_o^{\beta o_i(s)} \right\}\right)$$
  • 生成验证密钥：\(\left(g_o^{t(s)}, g^{\alpha_l}, g^{\alpha_r}, g^{\alpha_o}, g^{\beta \gamma}, g^\gamma \right)\)
• 证明
  • \(\ldots\) 赋变量值 $$g^{Z(s)} = \prod_{i=1}^n \left( g_l^{\beta l_i(s)} \cdot g_r^{\beta r_i(s)} \cdot g_o^{\beta o_i(s)} \right)^{v_i}$$
• 验证
  • \(\ldots\) 检查变量多项式限制： $$e\left( g_l^{L'}, g \right) = e\left( g_l^{L}, g^{\alpha_l} \right)，g_r^{R}, g_o^{O} \ 同理$$
  • 检查变量值一致性： $$e\left( g_l^{L} \cdot g_r^{R} \cdot g_o^{O}, g^{\beta \gamma} \right) = e\left( g^{Z}, g^\gamma \right)$$
  • 检查运算的有效性： $$e\left( g_l^{L} \cdot g_r^{R} \right) = e\left( g_o^t, g^h \right) e\left( g_o^O, g \right) \Rightarrow$$ $${e\left( g, g \right)}^{\rho_l \rho_r L R} = {e\left( g, g \right)}^{\rho_l \rho_r th + \rho_l \rho_r O}$$

生成元的这种随机化进一步增加了安全性，使变量多项式的延展性（在备注 4.1 中描述）无效，因为对于有意的更改，它必须是 \(\rho_l\)、\(\rho_r\) 或 \(\rho_o\) 的倍数，原始或加密的版本是不可用的（假设，如上文所述我们不处理可能暴露加密版本的 0 阶变量多项式）。

这个优化使验证密钥小了两个元素，并消除了验证步骤中的两个配对运算。

注：Jens Groth 的 2016 年论文 [Gro16] 中有进一步的协议改进。

译者注：至此，通用 zk-SNARK 协议几乎已经构造完成了，可以归纳为以下几点：

• 如何增加变量系数、如何做加减乘除运算

• 如何保证操作数和输出的不可互换性

• 如何保证跨操作数的变量一致性

• 如何处理变量和变量一致性多项式的非延展性

• 变量值一致性检查的优化

约束

我们的分析主要集中在运算的概念上。然而，该协议实际上并不是要「计算」，而是要检查输出值是否是操作数值的运算的正确结果。这就它被称为约束的原因，即验证者约束证明者为预定义的「程序」提供有效值，无论这个「程序」是什么。多个约束被称为约束系统（Constraint System）（在我们的例子中，它是一个一阶约束系统，Rank 1 Constraint System 或 R1CS）。

注：这意味着找到所有正确解决方案的一种方法是对所有可能的值组合执行暴力破解并仅选择「有效」的组合，或者使用更复杂的约束满足技术 [con18]。

译者注：这个约束定义在算术电路或布尔电路上，因为这两类电路的可满足性问题是 NP 完全问题。

我们也可以使用约束来确保其他关系。例如，如果我们想确保变量 \(a\) 的值只能是 \(0\) 或 \(1\)（即二进制），我们可以使用简单的约束来做到这一点：

$$\color{ForestGreen}{a}\quad \times \quad\color{blue}{a}\quad = \quad\color{red}{a}$$

我们也可以约束 \(a\) 只能为 \(2\)：

$$\color{ForestGreen}{(a - 2)}\quad \times \quad\color{blue}{1}\quad = \quad\color{red}{0}$$

一个更复杂的例子是确保数字 \(a\) 是一个 4 位（Bit）数字（也称为半字节），换句话说，可以用 4 位来表示 \(a\)。我们也可以称之为「确保数字范围」，因为 4 位数字可以表示 \(2^4\) 种组合，0 到 15 范围内有 16 个数字。在十进制数字系统中，任何数都可以表示为以 10（即我们手上手指的数量）为底的幂以及相应的系数的和，例如，\(123 = 1\cdot 10^2 + 2\cdot 10^1 + 3\cdot 10^0\)。同样，二进制数可以表示为以 2 为底的幂以及相应系数的和，例如，\(1011\ \text{(二进制)} = 1\cdot 2^3 + 0\cdot 2^2 + 1\cdot 2^1 + 1\cdot 2^0 = 11\ \text{(十进制)}\)。

因此，如果 \(a\) 是一个 4 位数字，那么对于某些布尔值 \(b_0, b_1, b_2, b_3\)，\(a = b_3\cdot 2^3 + b_2\cdot 2^2 + b_1\cdot 2^1 + b_0\cdot 2^0\)。约束可以如下：

$$1:\quad\color{ForestGreen}{a}\quad \times \quad\color{blue}{1}\quad = \quad\color{red}{8\cdot b_3 + 4\cdot b_2 + 2\cdot b_1 + 1\cdot b_0}$$

为了确保 \(b_0, b_1, b_2, b_3\) 只能是二进制，我们需要添加：

$$2:\quad\color{ForestGreen}{b_0}\quad \times \quad\color{blue}{b_0}\quad = \quad\color{red}{b_0}$$

$$3:\quad\color{ForestGreen}{b_1}\quad \times \quad\color{blue}{b_1}\quad = \quad\color{red}{b_1}$$

$$4:\quad\color{ForestGreen}{b_2}\quad \times \quad\color{blue}{b_2}\quad = \quad\color{red}{b_2}$$

$$5:\quad\color{ForestGreen}{b_3}\quad \times \quad\color{blue}{b_3}\quad = \quad\color{red}{b_3}$$

可以通过这种方式应用相当复杂的约束，以此来确保使用的值符合规则。需要注意的是，上述约束 1 在当前运算的结构中是不可能的：

$$\color{ForestGreen}{\sum_{i=1}^{n} c_{\textrm{l},i} \cdot v_i}\quad \times \quad\color{blue}{\sum_{i=1}^{n} c_{\textrm{r},i} \cdot v_i}\quad = \quad\color{red}{\sum_{i=1}^{n} c_{\textrm{o},i} \cdot v_i}$$

因为值 \(\color{blue}{1}\)（以及来自前一个约束的 \(\color{ForestGreen}{2}\)）必须通过 \(\color{blue}{c \cdot v_{one}}\) 来表示，其中 \(\color{blue}{c}\) 可以被固化在证明密钥中，但 \(\color{blue}{v_{one}}\) 可能为任何值，因为它是证明者提供的。虽然我们可以通过设置 \(c = 0\) 来强制 \(c \cdot v\) 为 \(0\)，但在我们受限的结构中很难找到一个约束来强制 \(v_{one}\) 为 \(1\)。因此，验证者应该有一种方法来设置 \(v_{one}\) 的值。

译者注：我们前文中提到的表达式的约束关系就被称为 R1CS。

公开输入和一

如果无法根据验证者的输入检查证明，那么证明的可用性将会受到限制，例如，知道证明者在不知道结果和 / 或值是什么的情况下将两个值相乘。虽然可以在证明密钥中「硬编码」要检查的值（例如，乘法的结果必须始终为 12），但这就需要为每个所需的「验证者的输入」生成单独的密钥对。

译者注：这样会严重限制实用性，电路需要支持参数。

因此，如果可以由验证者而不是证明者为计算指定一些值（输入或 / 和输出），包括 \(v_{one}\)，就可以变得更加通用了。

首先，让我们考虑证明值 \(\color{ForestGreen}{g^{L(s)}}, \color{blue}{g^{R(s)}}, \color{red}{g^{O(s)}}\)。由于我们使用的是同态加密，所以可以增加这些值，例如，我们可以添加另一个加密多项式求值 \(g^{L(s)} \cdot g^{l_v(s)} = g^{L(s) + l_v(s)}\)，这意味着验证者可以将其他变量多项式添加到已经提供的多项式中。因此，如果我们可以从证明者可用的变量多项式中排除必要的变量多项式，验证者将能够在这些变量上设置他的值，而计算检查应该仍然能够匹配。

这很容易实现，因为验证者已经在选择多项式时限制了证明者，他可以使用 \(\alpha\)-移位。因此，这些变量多项式可以从证明密钥移动到验证密钥，同时消除在 \(\alpha\) 和 \(\beta\) 校验和中的对应项。

必要的协议更新：

• 设置
  • \(\ldots\) 将所有 \(n\) 变量多项式分成两组：
    • 验证者的 \(m + 1\)： $$L_v(x) = l_0(x) + l_1(x) + \ldots + l_m，R_v(x) \ 和 \ O_v(x) \ 同理$$ 其中索引 \(0\) 为 \(v_{one} = 1\) 的值保留
    • 证明者的 \(n - m\)： $$L_p(x) = l_{m+1}(x) + \ldots+ l_n(x)，R_p(x) \ 和 \ O_p(x) \ 同理$$
  • 生成证明密钥： $$\left( \left\{ g^{s^k} \right\}_{k \in [d]}, \left\{ g_l^{l_i(s)}, g_r^{r_i(s)}, g_o^{o_i(s)}, g_l^{\alpha_l l_i(s)}, g_r^{\alpha_r r_i(s)}, g_o^{\alpha_o o_i(s)}, g_l^{\beta l_i(s)} \cdot g_r^{\beta r_i(s)} \cdot g_o^{\beta o_i(s)} \right\}_{i \in \{m + 1, \ldots, n\}} \right)$$
  • 添加到验证密钥： $$\left( \ldots, \left\{ g_l^{l_i(s)}, g_r^{r_i(s)}, g_o^{o_i(s)} \right\}_{i \in \{0, \ldots, m\}} \right)$$
• 证明
  • \(\ldots\) 根据验证者的多项式计算 \(h(x)\)：\(\displaystyle h(x) = \frac{L(x)\cdot R(x) - O(x)}{t(x)}\)，其中 \(L(x) = L_v(x) + L_p(x)\)，\(R(x), O(x)\) 同理
  • 提供证明： $$\left( g_l^{L_p(s)}, g_r^{R_p(s)}, g_o^{O_p(s)}, g_l^{\alpha_l L_p(s)}, g_r^{\alpha_r R_p(s)}, g_o^{\alpha_o O_p(s)}, g^{Z(s)}, g^{h(s)} \right)$$
• 验证
  • 为验证者的变量多项式赋值并与 1 相加： $$g_l^{L_v(s)} = g_l^{l_0(s)} \cdot \prod_{i=1}^m \left( g_l^{l_i(s)} \right)^{v_i}，g_r^{R_v(s)} \ 和 \ g_o^{O_v(s)} \ 同理$$
  • 检查变量多项式限制： $$e\left( g_l^{L_p}, g^{\alpha_l} \right) = e\left( g_l^{L'_p}, g \right)，g_r^{R_p} \ 和 \ g_o^{O_p} \ 同理$$
  • 检查变量值一致性： $$e\left( g_l^{L_p} g_r^{R_p} g_o^{O_p}, g^{\beta \gamma} \right) = e\left( g^{Z}, g^{\gamma} \right)$$
  • 检查运算的有效性： $$e\left( g_l^{L_v(s)} g_l^{L_p}, g_r^{R_v(s)} g_r^{R_p} \right) = e\left( g_o^{t}, g^{h} \right) \cdot e\left( g_o^{O_v(s)} g_o^{O_p}, g \right)$$

注：根据协议属性（4.6.1 节），由多项式 \(l_0(x), r_0(x), o_0(x)\) 表示的 \(1\) 在相应的运算中已经具有了适当的值，因此不需要再赋值。

注：验证者将不得不在验证步骤中做额外的工作，这与他赋值的变量数量成正比。

实际上，这将证明者的一些变量交到了验证者的手中，同时仍然保持等式的平衡。因此，运算的有效性检查应该仍然成立，但前提是证明者使用的值与验证者用于输入的值相同。

\(1\) 这个值是必不可少的，它允许通过乘以常数项来派生任何数字（在所选的有限域中），例如，将 \(a\) 乘以 \(123\)：

$$\color{ForestGreen}{1 \cdot a}\quad \times \quad\color{blue}{123 \cdot v_{one}}\quad = \quad\color{red}{1 \cdot r}$$

译者注：这里将原本由证明者赋值的一些变量改为由验证者赋值，使得证明者不得不与验证者保持相同的输入。这不仅解决了验证者参数输入的问题，也间接解决了常数赋值的问题。

计算的零知识证明

自从引入通用计算协议（4.4 节运算证明）以来，我们不得不放弃零知识属性来让过渡更加简单。现在，我们已经构建了一个可验证计算协议。

以前为了构造多项式的零知识证明，我们使用了随机 \(\delta\)-移位，这使得证明与随机无法区分（3.5 节）：

$$\delta p(s) = t(s) \cdot \delta h(s)$$

通过计算，我们证明：

$$L(s) \cdot R(s) - O(s) = t(s)h(s)$$

虽然我们可以使用相同的 \(\delta\) 将这种方法应用于多个多项式，即提供随机值 \(\delta L(s), \delta R(s), \delta^2 O(s), \delta^2 h(s)\)，这将通过配对满足运算的有效性检查：

$$e\left(g, g \right)^{\delta^2 L(s) R(s)} = e(g,g)^{\delta^2 \left(t(s) h(s) + O(s) \right)}$$

问题是相同的 \(\delta\) 会妨碍安全性，因为我们在证明中分别提供了这些值：

• 可以很容易地识别两个不同多项式的值是否相同（例如，\(g^{\delta L(s)} = g^{\delta R(s)}\) 等等），也就是可以学习到一些知识
• \(L(s)\) 和 \(R(s)\) 值之间的潜在微小差异可以允许通过暴力破解来分解，例如，如果 \(L(s) = 5R(s)\)，迭代检查 \(g^{L(s)} = \left( g^{R(s)} \right)^i\)，其中 \(i \in \{1 ... N\}\) 只需 5 步即可揭示 \(5\times\) 的差异。可以对加密的加法运算执行相同的暴力破解，例如，\(g^{L(s)} = g^{R(s) + 5}\)
• 可以发现证明中元素之间的其他相关性，例如，如果 \(e(g^{\delta L(s)}, g^{\delta R(s)}) = e(g^{\delta^2 O(s)}, g)\) 则 \(L(x) \cdot R(x) = O(x)\) 等等

注：优化 4.9.4 使此类数据挖掘变得更加困难，但仍然允许发现其中的关系，除了验证者可以用有助于揭示知识的特定方式选择 \(\rho_l, \rho_r\)（只要它不是一种多元化的设置）这一事实。

因此，我们需要让每个多项式的值具有不同的随机性（\(\delta\)），例如：

$$\delta_l L(s) \cdot \delta_r R(s) - \delta_o O(s) = t(s) \cdot (\Delta\ \ \unicode{x003F}\unicode{x2009}\unicode{x20DD}\ h(s))$$

为了解决右侧的不相等，我们修改证明的值 \(h(s)\) 相比更改协议显得更为可取。这里的 Delta（\(\Delta\)）代表我们需要应用到 \(h(s)\) 来抵消等式另一边的随机性的差异，\(\ \unicode{x003F}\unicode{x2009}\unicode{x20DD}\) 代表乘法或加法运算（反过来也适应除法和减法）。如果我们选择通过乘法（\(\ \unicode{x003F}\unicode{x2009}\unicode{x20DD} = \times\)）应用 \(\Delta\)，这意味着不可能以压倒性的概率找到 \(\Delta\)，因为存在随机性：

$$\Delta = \frac{\delta_l L(s) \cdot \delta_r R(s) - \delta_o O(s)}{t(s) h(s)}$$

我们可以设置 \(\delta_o = \delta_l \cdot \delta_r\)，于是转换为：

$$\Delta = \frac{\delta_l \delta_r( L(s) \cdot R(s) - O(s))}{t(s) h(s)} = \delta_l \delta_r$$

然而，如上文所述，这阻碍了零知识属性，更重要的是，这种结构将不会适应验证者的输入多项式，因为它们必须是相应 \(\delta\) 的倍数，这将需要交互。

我们可以尝试在求值中添加随机性：

$$(L(s) + \delta_l) \cdot (R(s) + \delta_r) - (O(s) + \delta_o) = t(s) \cdot (\Delta \times h(s))$$

$$\Delta = \frac{ \overbrace{L(s) R(s) - O(s)}^{t(s) h(s)} + \delta_r L(s) + \delta_l R(s) + \delta_l \delta_r - \delta_o }{t(s) h(s)} = 1 + \frac{\delta_r L(s) + \delta_l R(s) + \delta_l \delta_r - \delta_o}{t(s) h(s)}$$

但是由于随机性，它是不能被整除的。即使我们通过将每个 \(\delta\) 乘以 \(t(s)h(s)\) 来解决这个问题，由于我们通过 \(h(s)\) 的乘法来应用 \(\Delta\)，并且 \(\Delta\) 将包含加密的求值（即 \(g^{L(s)}\) 等等），如果不使用配对，就不可能计算 \(g^{\Delta h(s)}\)（结果在另一个数字空间中）。同样，通过使用加密幂 \(\left\{ g^{s^i} \right\}_{i \in [d]}\) 对 \(\Delta h(x)\) 进行加密求值是不可能的，因为 \(h(x)\) 和 \(\Delta\) 的阶数是 \(d\)，因此 \(\Delta h(x)\) 的阶数高达 \(2d\)。此外，出于同样的原因，不可能计算这种随机操作数多项式求值 \(g^{L(s) + \delta_l t(s)h(s)}\)。

因此，我们应该尝试通过加法（\(\ \unicode{x003F}\unicode{x2009}\unicode{x20DD} = +\)）应用 \(\Delta\)，因为它可以用于同态加密的值。

$$(L(s) + \delta_l) \cdot (R(s) + \delta_r) - (O(s) + \delta_o) = t(s) \cdot (\Delta + h(s))$$

$$\Delta = \frac{ L(s) R(s) - O(s) + \delta_r L(s) + \delta_l R(s) + \delta_l \delta_r - \delta_o - t(s) h(s)}{t(s)} \Rightarrow$$

$$\Delta = \frac{ \delta_r L(s) + \delta_l R(s) + \delta_l \delta_r - \delta_o}{t(s)}$$

分子中的每一项都是 \(\delta\) 的倍数，因此我们可以将每个 \(\delta\) 与 \(t(s)\) 相乘来让它可以被整除：

$$(L(s) + \delta_l t(s)) \cdot (R(s) + \delta_r t(s)) - (O(s) + \delta_o t(s)) = t(s) \cdot (\Delta + h(s))$$

$$\color{yellow}{L(s) R(s) - O(s)} + t(s) (\delta_r L(s) + \delta_l R(s) + \delta_l \delta_r t(s) - \delta_o) = t(s) \Delta + \color{yellow}{t(s) h(s)}$$

$$t(s) (\delta_r L(s) + \delta_l R(s) + \delta_l \delta_r t(s) - \delta_o) = t(s) \Delta$$

$$\Delta = \delta_r L(s) + \delta_l R(s) + \delta_l \delta_r t(s) - \delta_o$$

这样就可以在加密空间中有效地计算了：

$$g^{L(s) + \delta_l t(s)} = g^{L(s)} \cdot \left( g^{t(s)} \right)^{\delta_l} \ ,\quad 等等$$

$$g^\Delta = \left( g^{L(s)} \right)^{\delta_r} \cdot \left( g^{R(s)} \right)^{\delta_l} \cdot \left( g^{t(s)} \right)^{\delta_l \delta_r} g^{-\delta_o}$$

这样既可以通过运算的有效性检查，又可以隐藏加密值。

$${L\cdot R - O} + {\color{magenta}{t(\delta_r L + \delta_l R + \delta_l \delta_r t - \delta_o)}} = t(s) h + {\color{magenta}{t(s) (\delta_r L + \delta_l R + \delta_l \delta_r t - \delta_o)}}$$

由于添加了 \(\delta_l, \delta_r, \delta_o\) 的均匀随机倍数，该结构在统计上是零知识的（参见 [Gen+12] 的定理 13）。

注：这种方法也与验证者的操作数一致，例如 \(g_l^{L_p + \delta_l t} \cdot g_l^{L_v} = g_l^{L_p + L_v + \delta_l t}\)，因此运算的有效性检查仍然成立，但仅当证明者使用验证者的值来构造证明时才成立（即 \(\Delta = \delta_r (L_p + L_v) + \delta_l (R_p + R_v) + \delta_l \delta_r t - \delta_o\)），请参阅下一节了解更多详细信息。

为了使「变量多项式限制」和「变量值一致性」检查与零知识更改一致，有必要将以下参数添加到证明密钥中：

$$g_l^{t(s)}, g_r^{t(s)}, g_o^{t(s)}, g_l^{\alpha_l t(s)}, g_r^{\alpha_r t(s)}, g_o^{\alpha_o t(s)}, g_l^{\beta t(s)}, g_r^{\beta t(s)}, g_o^{\beta t(s)}$$

非常奇怪的是，最初的 Pinocchio 协议 [Par+13] 主要关注可验证计算，很少关注零知识属性，但这只是一个小的修改，几乎是无成本的。

译者注：与前文的零知识方案不同，这里通过相加而不是相乘的方式来确保证明者知识的零知识性。

Pinocchio 协议是针对 [GGPR] 论文的改进，在 3.1 节中也提到了实现零知识只需要沿用 [GGPR] 论文的方法即可，并不是这篇论文的贡献。另外，Pinocchio 协议的论文侧重工程实践，在 2013 年时，零知识证明还没有得到应用，真正的应用还是从匿名币 Zcash 开始的。

zk-SNARK 协议

在所有的逐步改进之后，最终的零知识简洁的非交互式知识论证如下（零知识组件是可选的，并以\(\color{Magenta}{不同的颜色}\)突出显示）：

• 设置
  • 选择一个生成元 \(g\) 和一个密码学配对 \(e\)
  • 对于变量总数为 \(n\) 的函数 \(f(u) = y\)，其中 \(m\) 是输入 / 输出变量，转换为阶数为 \(d\)，大小为 \(n + 1\) 的多项式形式（一个二次算术程序）\(\left( \{l_i(x), r_i(x), o_i(x)\}_{i \in \{0, \ldots, n\}}, t(x) \right)\)
  • 选择随机值 \(s, \rho_l, \rho_r, \alpha_l, \alpha_r, \alpha_o, \beta, \gamma\)
  • 设置 \(\rho_o = \rho_l \cdot \rho_r\) 和操作数生成元 \(g_l = g^{\rho_l}, g_r = g^{\rho_r}, g_o = g^{\rho_o}\)
  • 生成证明密钥： $$\bigg( \left\{ g^{s^k} \right\}_{k \in [d]}, \left\{ g_l^{l_i(s)}, g_r^{r_i(s)}, g_o^{o_i(s)} \right\}_{i \in \{0, \ldots, n\}},$$ $$\left\{ g_l^{\alpha_l l_i(s)}, g_r^{\alpha_r r_i(s)}, g_o^{\alpha_o o_i(s)}, g_l^{\beta l_i(s)} g_r^{\beta r_i(s)} g_o^{\beta o_i(s)} \right\}_{i \in \{m + 1, \ldots, n\}},$$ $$\color{Magenta}{ g_l^{t(s)}, g_r^{t(s)}, g_o^{t(s)}, g_l^{\alpha_l t(s)}, g_r^{\alpha_r t(s)}, g_o^{\alpha_o t(s)}, g_l^{\beta t(s)}, g_r^{\beta t(s)}, g_o^{\beta t(s)} } \bigg)$$
  • 生成验证密钥： $$\left( g^1, g_o^{t(s)}, \left\{ g_l^{l_i(s)}, g_r^{r_i(s)}, g_o^{o_i(s)} \right\}_{i \in \{0, \ldots, m\}}, g^{\alpha_l}, g^{\alpha_r}, g^{\alpha_o}, g^{\gamma}, g^{\beta \gamma} \right)$$
• 证明
  • 对于输入 \(u\)，执行 \(f(u)\) 的计算，获取所有中间变量的值 \(\{v_i\}_{i \in \{m+1, \dots, n\}}\)
  • 将所有值赋值给未加密的变量多项式 \(L(x) = l_0(x) + \sum_{i = 1}^n v_i \cdot l_i(x)\)，\(R(x), O(x)\) 同理
  • \(\color{Magenta}{选择随机值 \ \delta_l, \delta_r \ 和 \ \delta_o}\)
  • 找到 \(\displaystyle h(x) = \frac{L(x) R(x) - O(x)}{t(x)} \color{Magenta}{\ +\ \delta_r L(x) + \delta_l R(x) + \delta_l \delta_r t(x) - \delta_o }\)
  • 将证明者的变量值赋值给加密的变量多项式 \(\color{Magenta}{并应用零知识 \ \delta\text{-}移位}\) $$\displaystyle g_l^{L_p(s)} = \color{Magenta}{ \left(g_l^{t(s)}\right)^{\delta_l} } \cdot \prod_{i = m+1}^n \left( g_l^{l_i(s)} \right)^{v_i}，g_r^{R_p(s)}, g_o^{O_p(s)} \ 同理$$
  • 为它的 \(\alpha\)-移位的配对赋值 $$\displaystyle g_l^{L'_p(s)} = \color{Magenta}{ \left(g_l^{\alpha_l t(s)}\right)^{\delta_l} } \cdot \prod_{i = m+1}^n \left( g_l^{\alpha_l l_i(s)} \right)^{v_i}，g_r^{R'_p(s)}, g_o^{O'_p(s)} \ 同理$$
  • 为变量值一致性多项式赋值 $$g^{Z(s)} = \color{Magenta}{ \left(g_l^{\beta t(s)}\right)^{\delta_l} \left(g_r^{\beta t(s)}\right)^{\delta_r} \left(g_o^{\beta t(s)}\right)^{\delta_o} } \cdot \prod_{i=m+1}^n \left( g_l^{\beta l_i(s)} g_r^{\beta r_i(s)} g_o^{\beta o_i(s)} \right)^{v_i}$$
  • 计算证明 $$\left( g_l^{L_p(s)}, g_r^{R_p(s)}, g_o^{O_p(s)}, g^{h(s)}, g_l^{L'_p(s)}, g_r^{R'_p(s)}, g_o^{O'_p(s)}, g^{Z(s)} \right)$$
• 验证
  • 将证明解析为 \(\left( g_l^{L_p}, g_r^{R_p}, g_o^{O_p}, g^{h}, g_l^{L'_p}, g_r^{R'_p}, g_o^{O'_p}, g^{Z} \right)\)
  • 将输入 / 输出值赋值给验证者的加密多项式并与 \(1\) 相加： $$\displaystyle g_l^{L_v(s)} = g_l^{l_0(s)} \cdot \prod_{i=1}^m \left( g_l^{l_i(s)} \right)^{v_i}，g_r^{R_v(s)} \ 和 \ g_o^{O_v(s)} \ 同理$$
  • 检查变量多项式限制： $$e\left( g_l^{L_p}, g^{\alpha_l} \right) = e\left( g_l^{L'_p}, g \right)，g_r^{R_p} \ 和 \ g_o^{O_p} \ 同理$$
  • 检查变量值一致性： $$e\left( g_l^{L_p} g_r^{R_p} g_o^{O_p}, g^{\beta \gamma} \right) = e\left( g^{Z}, g^{\gamma} \right)$$
  • 检查运算的有效性： $$e\left( g_l^{L_p} g_l^{L_v(s)}, g_r^{R_p} g_r^{R_v(s)} \right) = e\left( g_o^{t(s)}, g^{h} \right) \cdot e\left( g_o^{O_p} g_o^{O_v(s)}, g \right)$$

结论

我们最终得到了一个允许证明计算的有效协议：

• 简洁（Succinctly）——与计算量无关，证明的大小是恒定且小的
• 非交互式（Non-Interactively）——只要计算出证明，就可以用来说服任意数量的验证者，他们无需与证明者直接交互
• 有论证的知识（With Argumented Knowledge）——陈述正确的概率不可忽略，即假证明是不可行的；此外，证明者知道真实陈述的相应值（即证据），例如，如果陈述是「\(B\) 是 \(\mathrm{sha256}(a)\) 的结果」，那么就说明证明者知道某个 \(a\) 使得 \(B = \mathrm{sha256}(a)\) 成立，这一点很有用，因为 \(B\) 只能根据 \(a\) 的知识计算出来，并且仅从 \(B\) 计算出 \(a\) 是不可行的（假设 \(a\) 有足够的熵）
• 在零知识中（In Zero-Knowledge）——从证明中提取任何知识都是不可行的，即它与随机无法区分

译者注：论证（Argument）与证明（Proof）不同，Pinocchio 协议是论证而非证明。这是因为 Pinocchio 的可靠性是计算可靠性（Computational Soundness）、统计零知识（Statistical Zero-Knowledge），这一类的证明系统被称为论证。计算可靠性暗示了一个事实：如果证明者的计算能力足够强，可以破坏可靠性。

由于多项式的独特性质、模算术、同态加密、椭圆曲线密码学、密码学配对和发明者的独创性，这个协议才得以实现。

该协议证明了唯一的有限执行机计算的正确性，它在一次运算中可以将几乎任意数量的变量相加，但只能执行一次乘法。因此，有机会优化程序来有效利用这种特殊性，以及使用最小化运算数量的结构。

重要的是，验证者不必知道任何秘密数据来验证证明，任何人都可以用非交互的方式发布和使用正确构造的验证密钥。这与证明只能说服一方的「指定验证者」方案相反，后者是不可转让的。在 zk-SNARK 中，我们可以在不可信或单方生成密钥对的情况下实现可转让属性。

零知识证明结构领域正在不断发展，包括优化（[Ben+13; Gro16; GM17]）、可更新的证明和验证密钥等改进（[Gro+18]），以及新的结构（Bulletproofs [Bün+17]，ZK-STARK [Ben+18]，Sonic [Mal+19]）。

致谢

我们感谢 Mary Maller 和 Andrew Miller 对这篇文章提出的宝贵意见。

参考文献

[Bit+11] — Nir Bitansky, Ran Canetti, Alessandro Chiesa, and Eran Tromer. From Extractable Collision Resistance to Succinct Non-Interactive Arguments of Knowledge, and Back Again. Cryptology ePrint Archive, Report 2011/443. https://eprint.iacr.org/2011/443. 2011

[Par+13] — Bryan Parno, Craig Gentry, Jon Howell, and Mariana Raykova. Pinocchio: Nearly Practical Verifiable Computation. Cryptology ePrint Archive, Report 2013/279. https://eprint.iacr.org/2013/279. 2013

[Rei16] — Christian Reitwiessner. zkSNARKs in a Nutshell. 2016. url: https://blog.ethereum.org/2016/12/05/zksnarks-in-a-nutshell/

[But16] — Vitalik Buterin. Quadratic Arithmetic Programs: from Zero to Hero. 2016. url: https://medium.com/@VitalikButerin/quadratic-arithmetic-programs-from-zero-to-hero-f6d558cea649

[But17] — Vitalik Buterin. zk-SNARKs: Under the Hood. 2017. url: https://medium.com/@VitalikButerin/zk-snarks-under-the-hood-b33151a013f6

[Gab17] — Ariel Gabizon. Explaining SNARKs. 2017. url: https://z.cash/blog/snark-explain/

[Ben+14] — Eli Ben-Sasson, Alessandro Chiesa, Christina Garman, Matthew Green, Ian Miers, Eran Tromer, and Madars Virza. Zerocash: Decentralized Anonymous Payments from Bitcoin. Cryptology ePrint Archive, Report 2014/349. https://eprint.iacr.org/2014/349. 2014

[GMR85] — S Goldwasser, S Micali, and C Rackoff. “The Knowledge Complexity of Interactive Proof-systems”. In: Proceedings of the Seventeenth Annual ACM Symposium on Theory of Computing. STOC ’85. Providence, Rhode Island, USA: ACM, 1985, pp. 291–304. isbn: 0–89791–151–2. doi: 10.1145/22145.22178. url: http://doi.acm.org/10.1145/22145.22178

[BFM88] — Manuel Blum, Paul Feldman, and Silvio Micali. “Non-interactive Zero-knowledge and Its Applications”. In: Proceedings of the Twentieth Annual ACM Symposium on Theory of Computing. STOC ’88. Chicago, Illinois, USA: ACM, 1988, pp. 103–112. isbn: 0–89791–264–0. doi: 10.1145/62212.62222. url: http://doi.acm.org/10.1145/62212.62222

[Gro10] — Jens Groth. “Short pairing-based non-interactive zero-knowledge arguments”. In: International Conference on the Theory and Application of Cryptology and Information Security. Springer. 2010, pp. 321–340

[Gen+12] — Rosario Gennaro, Craig Gentry, Bryan Parno, and Mariana Raykova. Quadratic Span Programs and Succinct NIZKs without PCPs. Cryptology ePrint Archive, Report 2012/215. https://eprint.iacr.org/2012/215. 2012

[Pik13] — Scott Pike. Evaluating Polynomial Functions. 2013. url: http://www.mesacc.edu/~scotz47781/mat120/notes/polynomials/evaluating/evaluating.html

[Pik14] — Scott Pike. Dividing by a Polynomial. 2014. url: http://www.mesacc.edu/~scotz47781/mat120/notes/divide_poly/long_division/long_division.html

[Dam91] — Ivan Damgård. “Towards practical public key systems secure against chosen ciphertext attacks”. In: Annual International Cryptology Conference. Springer. 1991, pp. 445–456.

[JSI96] — Markus Jakobsson, Kazue Sako, and Russell Impagliazzo. “Designated verifier proofs and their applications”. In: International Conference on the Theory and Applications of Cryptographic Techniques. Springer. 1996, pp. 143–154.

[DBS04] — Ratna Dutta, Rana Barua, and Palash Sarkar. Pairing-Based Cryptographic Protocols: A Survey. Cryptology ePrint Archive, Report 2004/064. https://eprint.iacr.org/2004/064. 2004.

[DK18] — Apoorvaa Deshpande and Yael Kalai. Proofs of Ignorance and Applications to 2-Message Witness Hiding. Cryptology ePrint Archive, Report 2018/896. https://eprint.iacr.org/2018/896. 2018.

[Wil16] — Zooko Wilcox. The Design of the Ceremony. 2016. url: https://z.cash/blog/the-design-of-the-ceremony/

[Gro16] — Jens Groth. On the Size of Pairing-based Non-interactive Arguments. Cryptology ePrint Archive, Report 2016/260. https://eprint.iacr.org/2016/260. 2016.

[con18] — Wikipedia contributors. Constraint satisfaction. Wikipedia, The Free Encyclopedia. 2018.

[Ben+13] — Eli Ben-Sasson, Alessandro Chiesa, Eran Tromer, Madars Virza. Succinct Non-Interactive Zero Knowledge for a von Neumann Architecture. Cryptology ePrint Archive, Report 2013/879. https://eprint.iacr.org/2013/879. 2013.

[GM17] — Jens Groth, Mary Maller. Snarky Signatures: Minimal Signatures of Knowledge from Simulation-Extractable SNARKs. Cryptology ePrint Archive, Report 2017/540. https://eprint.iacr.org/2017/540. 2017.

[Gro+18] — Jens Groth, Markulf Kohlweiss, Mary Maller, Sarah Meiklejohn, and Ian Miers. Updatable and Universal Common Reference Strings with Applications to zk-SNARKs. Cryptology ePrint Archive, Report 2018/280. https://eprint.iacr.org/2018/280. 2018.

[Bün+17] — Benedikt Bünz, Jonathan Bootle, Dan Boneh, Andrew Poelstra, Pieter Wuille, and Greg Maxwell. Bulletproofs: Short Proofs for Confidential Transactions and More. Cryptology ePrint Archive, Report 2017/1066. https://eprint.iacr.org/2017/1066. 2017.

[Ben+18] — Eli Ben-Sasson, Iddo Bentov, Yinon Horesh, and Michael Riabzev. Scalable, transparent, and post-quantum secure computational integrity. Cryptology ePrint Archive, Report 2018/046. https://eprint.iacr.org/2018/046. 2018.

[Mal+19] — Mary Maller, Sean Bowe, Markulf Kohlweiss, and Sarah Meiklejohn. Sonic: Zero-Knowledge SNARKs from Linear-Size Universal and Updateable Structured Reference Strings. Cryptology ePrint Archive, Report 2019/099. https://eprint.iacr.org/2019/099. 2019.