1-Polynomial-Interaction-and-Proof

作者：Maksym Petkus

翻译 & 注解：even@安比实验室（even@secbit.io）

校对：valuka@安比实验室

本系列文章已获作者中文翻译授权

翻译原链接

核心要点
证明的媒介
- 问题 :
- 因式分解
模糊计算
协议过程

核心要点

加密函数： $E (v) = g^{v} (m o d p)$

在同态加密中:

模数 $p$ 是双方都知道的。它通常是写在加密代码中的

生成元 $g$ 是一个整数，作为一个基用来生成一系列的数字(密钥，用来对数据进行加密)

$v$ 就是我们要加密的值

如果上述核心要点已经模糊/忘记的话, 就通读全文

证明的媒介

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

想象一下我们 (Prover) 有一个长度为10 的位数组，现在要向 verifier（例如，程序）证明这样一个陈述：我的所有的位都被设置成了 1

verifier 一次只能检查（读）一位。为了验证 Prover 的这个陈述，verifier 以某种任意的顺序读取元素并检查其是否确实等于 1 。如果第一次抽样检查的结果是 1，就设置「陈述」的可信度为 ⅒= 10％，否则，如果等于 0，就说明「陈述」是错误的。

验证者继续进行下一轮验证，直到获得足够的可信度为止。假如在一些场景下要信任 prover 需要至少 50% 的可信度，那就意味着必须执行 5 次校验。但假如在其它一些场景下需要 95% 的可信度，就需要检查所有的元素。很明显这个证明协议的缺点是: 必须要根据元素的数量进行检查，如果我们处理数百万个元素的数组，这么做是不现实的。

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

上面的曲线对应多项式: f(x) = x³ – 6x² +11x– 6。多项式的阶数取决于 x 的最大指数，当前多项式的阶数是 3

多项式有一个非常好的特性，就是如果我们有两个阶为 d (比如 3 ) 的不相等多项式，他们相交的点数不会超过 d ( 3 个)。例如，稍微修改一下原来的多项式为 x³ – 6x² + 10x– 5 （注意 , 修改了多项式的最后一个系数，6 改成了 5 ）并在图上用绿色标出：

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

要找到多项式与 x 轴的交点（即 f(x) = 0），我们就要令 x³ – 6x² + 11x – 6 = 0，等式的解就是和 x 轴的交点： x= 1 ，x= 2 和 x= 3。即图上蓝色曲线和 x 轴相交的地方。

同样，我们也可以令上文中原始的多项式和修改后的多项式相等，找到它们的交点:
联立 : x³ – 6x² + 11x – 6 = x³ – 6x² + 10x – 5 , 得到: $x - 1 = 0$

即这两个多项式有一个交点。

任意一个由阶数为 d 的多项式组成的等式，最后都会被化简为另外一个阶数至多为 d 的多项式，这是因为等式中没有能够用来构造更高阶数的乘法。例如：5x³ + 7x² – x + 2 = 3x³ – x² + 2x– 5，简化为 2x³ + 8x² – 3x + 7 = 0。阶数最多就是 3 (次方)

另外代数的基本原理也告诉我们，对于一个阶数为 d 的多项式最多有 d 个解，至多有 d 个共同点。

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

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

verifier 选择一个随机值 $x$ 并在本地计算多项式结果
verifier 将 $x$ 值丢给 prover，让他计算该多项式的结果
prover 代入 x 到多项式计算并将结果给到 verifier
verifier 检查本地的计算结果和 prover 的计算结果是否相等，如果相等那就说明 prover 的陈述具有较高的可信度

例如，对于一个 $d$ 阶多项式 , prover 如果不知道该多项式的 d 个解 , 如果把 x 的取值范围定在 1 到 $1 0^{77}$ , 那么 x 偶然“撞到”这 d 个结果相同的点中任意一个的概率就等于： $\frac{d}{1 0 ^{77}}$ （可认为不可能）

与低效的位检查协议相比，新的协议只需要一轮验证就可以让声明具有非常高的可信度（前提是假设 $d$ 远小于 x 取值范围的上限 (是低阶多项式)，可信度几乎是 100%）

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

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

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

问题 :

到目前为止，我们的协议还只是一个很弱的证明，因为协议中并没有采取任何措施去保证参与方必须按照协议的规则生成证明，所以参与方只能互相信任。

例如，prover 并不需要知道多项式，也可能通过其它方式得到正确的答案 (比如偷一个答案)。

而且，如果 verifier 要验证的多项式的解的取值范围不够大，比如我们前文说的 10，那个就可以去猜一个数字，猜对答案的概率是不可忽略不计的。因而我们必须要解决协议中的这个缺陷，在解决问题之前首先来想一下，知道多项式意味着什么呢？

多项式可以用下面的形式来表示（其中 n 指的是多项式的阶）： $c_{n} x^{n} + \dots\dots + c_{1} x^{1} + c_{0} x^{0}$ 假设证明者声称他知道一个包含 x=1 和 x=2 两个解的三阶多项式 , 满足此条件的一个有效的多项式就是 $x^{3} - 3 x^{2} + 2^{x} = 0$ 。

多项式的「知识」就是多项式的系数。所谓「知道」多项式就是指「知道」多项式的系数

因式分解

代数的基本定理表明了任意的一个多项式只要它有解，就可以将它分解成线性多项式（即，一个阶数为 1 的多项式代表一条线），因此，我们可以把任意有效的多项式看成是其因式的乘积： $(x - a_{0}) (x - a_{1}) \dots (x - a_{n}) = 0$

也就是说如果任意一个因式为 0，那么整个等式都为 0，也就是说式子中所有的 $a_{s}$ 就是多项式的所有解 $x^{3} - 3 x^{2} + 2 x = (x - 0) (x - 1) (x - 2)$

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

我们再回到前面的问题， prover 宣称他知道一个阶数为 3，其中两个根分别为 1 和 2 的多项式，也就是说这个多项式的形式为： $(x - 1) (x - 2) \cdot \dots (x - 1) (x - 2) \cdot \dots$ 换句话说 $(x - 1)$ 和 $(x - 2)$ 是问题中多项式的两个因式。

因而如果 prover 想要在不揭示多项式的前提下证明他的多项式确实有这两个根，那么他就需要去证明他的多项式 $p (x)$ 是 $t (x) = (x - 1) (x - 2)$ 和一些任意多项式 $h (x)$ （例子中 $x - 0$ ）的乘积，即： $p (x) = t (x) \cdot h (x)$

$t (x) = (x - 1) (x - 2)$ 也称为目标多项式 target polynomial

换句话说，存在一些多项式 $h (x)$ 能使 $t (x)$ 与之相乘后等于 $p (x)$ ，并由此得出， $p (x)$ 中包含 $t (x)$ ，所以 $p (x)$ 的根中也包含 $t (x)$ 的所有根，这也就是我们要证明的东西. 算出 $h (x)$ 的方式最自然的就是直接相除： $h (x) = \frac{p ( x )}{t ( x )}$

如果一个 prover 不能找到这样一个 $h (x)$ 也就意味着 $p (x)$ 中不包含因式 $t (x)$ ，那么多项式相除就会有余数

例如我们用 p(x) = x³ – 3x² + 2x 除以 t(x) = (x – 1)(x – 2) (即 x² – 3x+ 2 )

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

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

_注意：为简化起见，后面我们会用多项式的字母来代替计算结果，如： $p = p (r)$

多项式可以被因式分解成它的根的因式的乘积。这个性质就意味着，如果一个多项式有某些解，那么它被因式分解后的式子中一定包含这些解的因式。有了这个性质，我们就可以愉快地去做一些证明啦。

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

verifier 挑选一个随机值 $r$ , 计算 $t = t (r)$ (即，求值) ，然后将 $r$ 发送给 prover。
prover 计算 $h (x) = p (x) / t (x)$ ，并对 p(r) 和 h(r) 进行求值，将计算结果 p, h 提供给 verifier。
verifier 验证 $p = t \cdot h$ ，如果多项式相等，就意味着 t(x) 是 p(x) 的因式。

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

verifier 选一个随机数 23，并计算 t = t(23) = (23 – 1)(23 – 2) = 462，然后将 23 发给 prover
prover 计算 $h (x) = p (x) / t (x) = x$ , 并对 p(r) 和 h(r) 进行求值，p= p(23) = 10626，h = h(23) = 23，将 p 和 h 提供给 verifier
verifier 再验证 $p = t \cdot h$ ：10626 = 462 ⋅ 23 是正确的，这样陈述就被证明了。

相反，如果 prover 其实不知道真正的 $p (x)$ , 而是使用了一个不相干的 $p^{'} (x)$ ，如 p′(x) = 2x³ – 3x² + 2x ，它并不包含必需的因式, 那么：

prover 计算 $h (x) = p^{'} (x) / t (x)$ , 运算出结果 $2 x + 3$ 和余数 $7 x -6$ ： $p (x) = t (x) \cdot (2 x + 3) + 7 x - 6$
为了计算出结果 , prover 不得不冒险用余数除以 $t (x)$ ，即
$\frac{p ( x )}{t ( x )} = h (x) = \frac{t ( x ) \cdot ( 2 x + 3 ) + 7 x -6}{t ( x )} = 2 x + 3 + \frac{7 x - 6}{t ( x )}$

不过由于 x 是 verifier 随机选择的，只有极低的概率余数 $7 x -6$ 可以被 $t (x)$ 整除。如果后面 verifier 要另外再检查 p 和 h 必须是整数的话，这个证明就会被拒绝。

如此校验就同时要求多项式系数也是整数，这对协议产生了极大的限制

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

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

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

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

even@安比实验室：利用因式的性质构造出了一个证明协议，但这个协议存在一些缺陷，主要是由于

一旦 prover 知道了 $t (r)$ ，他就可以反过来任意构造任何一个可以整除 $t (r)$ 的 $p (r)$

有的公司的 $t (r)$ 就直接写在开源代码里面 …. 作死 ….

prover 知道了点 $(r, t (r) \cdot h (r))$ 的值，就可以构造经过这一点的任意(高次)多项式，同样满足校验

协议并没有对 prover 的多项式阶数(次数)进行约束

模糊计算

Remark 3.1 中的前 2 个问题是由于 暴露了原始值 而导致的，即 $P$ 知道了 $r$ 和 $t (r)$ 但如果 verifier 给出的这个 $r$ 值像放在黑盒里一样不可见的话就完美了，也就是一个人即使不破坏协议，也依然能在这些模糊的值上面完成计算。有点类似哈希函数，从计算结果就很难再回到原始值上

同态加密

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

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

$5^{3} = 125$

这里 125 就是 3 对应的密文。如果我们想要对被加密的值乘 2，我们可以以 2 为指数来对这个密文进行计算。 $12 5^{2} = 15625 = (5^{3})^{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，那么做除法的次数也就是被加密值的数。

比如有一段密文是 125 , 那么 $125/5/5/5 = 1$ , 除了 3 次得到 1 , hacker 自然知道加密值是 3 , 这毫无加密可言, 所以我们需要 Mod 模运算

模运算

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

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

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

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

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

这就是模运算操作的结果。无论这根绳子多长，它最终都会在圆圈一个刻度处终止。因而模运算结果将保持在一定范围内（例子中是 0 到 5）。长度为 15 的绳子将会在刻度 3 的地方终止，即 6 + 6 + 3 （缠 2 个完整的圈并剩下 3 个单位长的部分）。

负数运算类似，唯一不同的地方就是它是沿相反方向缠绕的，如 -8 的取模结果是 4。

我们执行算术运算，结果都将落在这 n 的范围内。现在开始我们将用符号 “mod n” 来表示这个范围内的数。

3 × 5 = 3 mod 6

5 + 2 = 1 mod 6

另外，模运算最重要的性质就是运算顺序无所谓。

例如，我们可以先做完所有的操作，然后再取模，或者每操作完一步都去取模。例如 (2 × 4 – 1) × 3 = 3 (mod 6) 就等于：

2 × 4 = 2 mod 6

2 - 1 = 1 mod 6

1 × 3 = 3 mod 6

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

5 × 4 = 2 mod 6

4 × 2 = 2 mod 6

2 × 1 = 2 mod 6

……

设想一下 , 如果没有模运算的话，计算结果的大小会给找出原始值提供一些线索。

除非这里既能把信息隐藏起来，又可以保留常见的算术属性。

强同态加密

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

$5^{1} = 5 (5 m o d 7 = 5)$

$5^{2} = 4 (25 m o d 7 = 4)$

$5^{3} = 6 (125 m o d 7 = 6)$ …………

其中在某些不同的指数下运算得到了同样的结果 , 比如 $5^{5} / 5^{11} / 5^{17}$ 模7 的运算结果都是 3 ：

$5^{5} = 3 (m o d 7)$

$5^{11} = 3 (m o d 7)$

$5^{17} = 3 (m o d 7)$ ……

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

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

$e n cry pt i o n : 5^{3} = 6 (m o d 7)$
- 根据密文 6 , 不能推出原文 3
$m u lt i pl i c a t i o n : 6^{2} = (5^{3})^{2} == 5^{6} = 1 (m o d 7)$
$a dd i t i o n : 5^{3} \cdot 5^{2} = 5^{5} = 3 (m o d 7)$
- 根据密文 3 , 无法推出私钥

(原文)注意：模相除有点难 , 超出范围了, 这里不表。

我们来明确地说明一下加密函数： $E (v) = g^{v} (m o d n)$

$v$ 是想要加密的值

模数 $n$ 是双方都知道的, 它通常写在加密代码中

生成元 $g$ 是一个整数，作为一个基用来生成一系列的数字比如 $g^{v}$

$g^{v}$ 通常称为密钥，用来对数据进行加密

Remark 3.2 : 这个同态加密模式有一个限制，我们可以将 加密值 乘以 未加密值 ，但不能将两个已经加密的值相乘( we cannot exponentiate an encrypted value)（或者相除），也就是说我们不能对加密值取幂。

在同态加密中，求幂运算会破坏同态的性质，导致加密后的数据无法被正确解密。因此，同态加密不允许对已经加密值进行再次的求幂运算。 Besides, 密文之间的乘法操作可能会泄露有关明文的信息。特别是在某些强同态加密方案中，如果不小心执行操作，可能会导致信息泄露。

虽然这些性质第一感觉看起来很不友好，但是这却构成了 zk-SNARK 的基础。这个限制后面将在“加密值乘法 (Multiplication of Encrypted Values) ”一节中讲到。

通过模运算形成的集合被称为「有限域」，

通过计算指数再进行模运算形成的集合构成「循环群」。

常见的同态加密方式除了整数幂取模之外，还有椭圆曲线上的倍乘。

加密多项式

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

我们来看一下如何计算多项式 p(x) = x³ – 3x² + 2x。

我们前面明确了，知道一个多项式就是知道它的系数，也就是这个例子中知道：1, -3, 2。

因为同态加密并不允许再对加密值求幂，所以我们必须要给出 x 的 1 到 3 次幂取加密值：E(x)，E(x²)，E(x³)，那么我们要计算的加密多项式就是：

$E (x^{3})^{1} \cdot E (x^{2})^{- 3} \cdot E (x)^{2} = (g^{x^{3}})^{1} \cdot (g^{x^{2}})^{- 3} \cdot (g^{x})^{2} = g^{1 x^{3}} \cdot g^{- 3 x^{2}} \cdot g^{2 x} = g^{x^{3} - 3 x^{2} + 2 x}$

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

我们现在就可以更新前面版本的协议了，比如对于阶数为 d 的多项式： $E (v) = g^{v} (m o d n) (放着备用)$

协议过程

前面提到 : Prover 想要在不揭示多项式的前提下证明他的多项式确实有这两个根，他需要去证明他的多项式 $p (x)$ 是 $t (x) = (x - 1) (x - 2)$ 和一些任意多项式 $h (x)$ 的乘积，即： $p (x) = t (x) \cdot h (x)$ $t (x) = (x - 1) (x - 2)$ 也称为 target polynomial

协议过程如下 :

Verifier

Verifier 自己取一个随机数 $s$ ，作为秘密值
多项式指数 $i$ ( $x^{i}$ )取值为 0，1，…，d 时分别计算出 $s$ 的 $i$ 次幂的加密结果，即： $E (s^{i}) = g^{s}^{i}, i \in (0.. d)$ (注意是 $g^{s}$ 的 $i$ 次方)
代入 $s$ 自己计算未加密的 target poly $t (x)$ , $t (s)$ 留作验证备用
将对 $s$ 的幂的加密值丢给 prover: $E (s^{0}), E (s^{1}), .., E (s^{d})$ , 即 $g^{s^{0}}, g^{s^{1}}, \dots, g^{s^{d}}$
- 看起来, 目前 Verifier 知道 $P (x)$ 的阶数 $d$

Prover :

Prover 想证明它确实有这 2 个根 ( 即有 $t (x)$ 因式) :
Prover 自己计算多项式 $h (x) = p (x) / t (x)$
使用 Verifier 给的加密值 $g^{s^{0}}, g^{s^{1}}, \dots, g^{s^{d}}$ , 和自己的 $p (x)$ 的系数 $c_{0}, c_{1}, .., c_{n}$ 计算 $E (p (s))$ :
$E (p (s)) = g^{p (s)} = (g^{s^{d}})^{c_{d}} * \dots * (g^{s^{1}})^{c_{1}} * (g^{s^{0}})^{c_{0}} = g^{(s^{d} \cdot c_{d} + \dots + s^{1} \cdot c_{1} + s^{0} \cdot c_{0})}$
同样计算 $E (h (s)) = g^{h (s)}$
将结果 $g^{p}$ (即 $g^{p (s)}$ ) 和 $g^{h}$ (即 $g^{h (s)}$ )提供给 verifier

注: $E (v) = g^{v} mod n$ 是加密函数

Verifier

最后一步是 Verifier 校验 $p g^{p} g^{p} = ? t (s) \cdot h 即 = ? (g^{h})^{t (s)} => = ? g^{t (s) \cdot h}$ 就能知道 Prover 到底是否有根 ; 为什么呢 ?
- 注 : $g^{p}$ 和 $g^{h}$ 是 Prover 传的 , $t (s)$ 是 Verifier 自己算的 ;
因为如果 $g^{p} = (g^{h})^{t (s)}$ 成立 (即 $g^{p} = g^{t (s) \cdot h}$ 成立) , 根据同态性质 , 即 $p (x) = t (s) \cdot h$ 成立 , 就说明 Prover 真的有多项式的解

问题: Prover 计算 $E (h (s)) = g^{h (s)}$ , s 是 Prover 不知道的, 那如何计算 $h (s)$ 呢 ?
1. 郭师: $s^{0}, s^{1}, s^{2}$ 是一组 mod 过的 key-value , 是双方都知道的 2. 使用的是 $g^{s^{0}}, g^{s^{1}}, \dots, g^{s^{d}}$ 而不是 $s$ 原值 3. ∵ $h (x) = h_{0} + h_{1} x + h_{2} x^{2} + \dots + h_{n} x^{n}$
4. ∴ $h (s) = h_{0} \cdot [s^{0}] + h_{1} \cdot [s^{1}] + h_{2} \cdot [s^{2}] + \dots + h_{n} [s^{n}]$

注意：g 是公开的, 双方都知道的因为证明者并不知道跟 s 相关的任何信息，这就使得他很难提出不合法但是能够匹配验证的计算结果。

尽管这个协议中 prover 的灵活性有限，他依然可以在实际不使用 verifier 所提供的加密值进行计算，而是通过其它的方式来伪造证明。例如，如果 prover 声称有一个满足条件的多项式它只使用了 2 个求幂值 $s^{3}$ 和 $s^{1}$ ，这个在当前协议中是不能验证的

even@安比实验室: 利用强同态加密这个工具，构造了一个相对较强的零知识证明协议。但是如上文所述，这里还是存在一些问题—— 无法验证 prover 是否是真的使用了 verifier 提供的值 $g^{s^{0}}, g^{s^{1}}, \dots, g^{s^{d}}$ 来构造证明的。

ref (IF 图挂了)

https://secbit.io/blog/2019/12/25/learn-zk-snark-from-zero-part-one/
https://learnblockchain.cn/article/287

World of Z2O-K7E