zk-SNARK 是如何实现零知识证明的？从技术角度详细解读。

原文标题：《彻底读懂零知识证明及其实现方法：解析 zk-SNARK》
撰文：李画
致谢：东泽、even
参考：Maksym Petkus，Why and How zk-SNARK Works: Definitive Explanation

我们已经越来越频繁地见到 zk-SNARK，我们还会更多地遇到它。

大家都知道它是一种实现零知识证明的方法，也知道它是扩容和隐私方向的利器，但究竟什么是零知识证明，zk-SNARK 是如何实现零知识证明的？这便是本文试着去回答的问题。

阅读这篇文章需要保持较高的专注度，以及适当思考；但本文尽力做到没有含混和晦涩之处，所以如果你保持专注，看完就能理解零知识证明究竟是如何通过 zk-SNARK 做到的，而不是停留在只知道概念的阶段。

那么现在，开始吧。

第一阶段：为使用 zk-SNARK 做准备工作

把零知识证明的需求转换为数学运算电路

保险机构需要知道用户的一个体检数据是否达标，用户只想让保险机构知道数据是否达标，但不透露具体的数据给他们。怎么去做？

假设这个体检的隐私数据是 x，x 的值在 0~7 之间（包含 0 和 7）为达标，否则为不达标。那要做首先是把这个需求转换为一个可计算的问题，即有一个程序，其输入为 x，当 x 在 0~7 之间时，输出「真」，当 x 不在该区间时，输出「假」。

该程序的计算过程可以被表达为如下一组方程的验证过程。当输入 x 后，如果这 4 个方程都能被满足，也就是方程左边的计算结果都为 0，就能证明 x 在 0~7 之间，那么就输出「真」，否则输出「假」。这 4 个方程为：

b0 * (b0-1)= 0 

b1 * (b1-1)= 0

b2 * (b2-1)= 0

2^0 * b0 + 2^1 * b1+2^2 * b2 – x = 0

注：b0、b1、b2 的值由 x 确定，它们也是输入；前 3 个方程约束 b0、b1、b2 的值为 0 或 1；最后 1 个方程验证 x 的取值在 0~7 之间。

可以把这样的一组方程表达为一个数学运算电路。以 b0 * (b0-1) 为例，它这一部分的电路如下图所示。

而整个程序的计算过程可以抽象表达为下图：

如此一来，零知识证明的问题就被转化为「输入+用作证明的数学运算电路+输出」；如果输出为真，就可以相信输入为真。在本文的例子中，如果输出为 0，就可以相信用户的体检数据达标。

把数学运算电路转换为多项式

在把零知识证明的需求转换为数学运算电路后，我们能够把验证者和证明者这两个角色分开。而当验证者不是证明者时，就创造了一个可以隐藏输入（原始数据）的机会。

随之而来问题只有一个：验证者凭什么相信这个「输出」是「输入」通过「用作证明的数学运算电路」计算出来的？最简单的办法就是验证者看着证明者输入和计算，但这样就无法隐藏输入了。

所以我们要在数学运算电路的基础上接着做转换，把输入、用作证明的数学运算电路、输出这三者绑定到一起，也就是说，能够通过某种方式验证「输出」是否为「输入」通过「用作证明的数学运算电路」计算出来的。

这样一来，在输出为真的前提下，只要该验证通过，证明者就可以相信输入为真。

为了完成这种绑定，需要把数学运算电路转换为多项式。

(以下为数学转换过程，若无兴趣可跳至下一张图片下方的段落)

首先要把数学运算电路转换为一阶约束系统（RICS）。

Vitalik 在《Quadratic Arithmetic Programs: from Zero to Hero》一文中详细介绍了这个转换过程，本文为省略细节描述，将直接引用 Vitalik 使用的例子。

这是一个数学的过程，我们只需要知道这种转换是等价的即可，若希望知晓细节，可阅读 Vitalik 的文章。

Vitalik 的那组方程为：




x * x - sym_1 = 0  


sym_1 * x – y = 0

(y + x) * 1 - sym_2 = 0

(sym_2 + 5) * 1 - ~out = 0

以其中的第一个方程 x * x - sym_1 = 0 为例，它被转换为 R1CS 后的形式如下所示：

a = [0, 1, 0, 0, 0, 0]  


b = [0, 1, 0, 0, 0, 0]

c = [0, 0, 0, 1, 0, 0]

s = [~one,x,~out,sym_1,y,sym_2]

R1CS 是由上方 3 个向量（a, b, c）组成的序列，解向量为 s，且满足 s. a * s.b - s.c = 0，这也被称作一个约束。可以试着计算一下，你会发现 s.a * s.b - s.c = x * x - sym_1，它们是等价的。

Vitalik 的例子包含 4 个拍平后的方程，每个方程对应一个 RICS 约束，因此一共有 4 个约束。

接下来是把 R1CS 转换为多项式。依然不需要深入理解如何转换，只需要知道转换是等价的。转换过程如下：

一共有 4 个 RICS 约束，每个约束中都包含一个向量 a，因此一共有 4 个向量 a，它们分别是：

a = [0, 1, 0, 0, 0, 0]  


a = [0, 0, 0, 1, 0, 0]

a = [0, 1, 0, 0, 1, 0]

a = [5, 0, 0, 0, 0, 1]

通过拉格朗日插值法，可以把这 4 个向量转换为 6 个多项式（因为每个向量包含 6 个值），它们分别是：

–5+ 9.166* x- 5* x^2+0.833* x^3  


8- 11.333 * x + 5 * x^2-0.666 * x^3

0 + 0 * x + 0 * x^2 + 0 * x^3

–6 + 9.5 * x - 4 * x^2 + 0.5 * x^3

4 - 7 * x + 3.5 * x^2 - 0.5 * x^3

–1+ 1.833 * x- 1 * x^2+ 0.166 * x^3

可以试着把 x= 1 代入这 6 个多项式计算，将得到 [0、1、0、0、0、0] 这 6 个值，你会发现它们正是第一个约束下的向量 a；把 x 等于 2、3、4 分别带入这 6 个多项式，将得到其他 3 个约束下的向量 a。

向量 a 对应 6 个多项式，向量 b 和向量 c 也是如此，因此一共会有 18 个多项式。当 x=1 时，这 18 个多项式的 18 个解正是第一个约束；当 x 等于 2、3、4 时，分别得到第 2、3、4 个约束。多项式与 RICS 是等价的。

到此就完成了从数学运算电路到多项式的转换：

• 通过 RICS 转换，把证明多个原方程转换为证明多个 s.a * s.b - s.c = 0 ；

• 通过多项式转换，把证明多个 s.a * s.b - s.c = 0 转换为证明在 x=1、x=2、x=3、x=4 时，A(x) * B(x) – C(x) = 0，其中 A(x) = s.a，B(x) = s.b，C(x) = s.c。如下图所示。

图中最左边一行数字 [1, 3, 35, 9, 27, 30] 为 Vitalik 例子中的解向量 s。A1(x) 为 a 的第 1 个多项式在 x 处的取值，比如 A1(1)=0；A1(x)~A6(x) 构成第 x 个约束的向量 a，比如 x=1 时，a=[0、1、0、0、0、0]；其他同理。

(若跳过转换，可从此处接着阅读)

我们似乎是在通过一个繁琐的步骤，把本来简单的证明变成了复杂的证明，为什么？如果你仔细观察，就会发现一件神奇的事情发生了：

本来验证者需要验证的是：输入通过用作证明的数学运算电路，输出为真；但现在验证者需要验证的是，当 x=1、x=2、x=3、x=4 时，A(x) * B(x)–C(x) = 0。

A(x) * B(x)–C(x) 中包含了解向量 s，它是把输入、输出、电路绑定在一起的；验证 A(x) * B(x)–C(x) = 0，就是在验证输入和输出是否满足用作证明的数学运算电路。

这便解决了本节开始时提出的问题：验证者凭什么相信「输出」是「输入」通过「用作证明的数学运算电路」计算出来的。

如此一来，验证者就不需要关注具体的输入和计算过程，只需要验证 A(x) * B(x) – C(x) = 0 本身是否成立。这让我们真正有了机会去隐藏输入。

到此处可以长舒一口气了，虽然还没开始进入 zk-SNARK，但我们已经完成了最艰难的部分。如果转换部分没有理解清楚也没关系，你只需要知道：

通过 zk-SNARK 实现零知识证明，实际上是要在 zk-SNARK 的帮助下，验证当 x= 1、2、3、……、n 时，A(x) * B(x)–C(x) = 0，其中 n 是 RICS 约束的个数；而不同的零知识证明问题，区别只在于它们的 A(x)、B(x)、C(x) 不同。

把多次验证转换为一次验证

对于包含 n 个约束的零知识证明问题，需要进行 n 次 A(x) * B(x)–C(x) 是否为零的验证。可不可以把 n 次验证变为一次验证？可以。

• 定义 t(x) = (x-1) * (x-2) * …… * ( x-n)，t(x) 在 x=1、x=2、…… 、x=n 处必然等于零；

• 那么如果有一个多项式 h(x)，使得 A(x) * B(x)–C(x) = t(x) * h(x) 成立，便意味着 A(x) * B(x)–C(x) 这个多项式可以被 t(x) 整除，那么这个多项式在 x=1、x=2、…… 、x=n 处也必然等于零。

也就是说，验证 A(x) * B(x)–C(x) = t(x) * h(x) ，就能够一次完成全部 RICS 约束的验证；而一旦这个验证通过，就可以相信输入为真。

现在终于可以把接力棒交给 zk-SNARK 了，它要做的工作就是帮助验证 A(x) * B(x)–C(x) = t(x) * h(x)。

验证的过程是怎样的？很简单。verifier （验证者）选择一个随机数 x 发起挑战，prover （证明者）证明在这个 x 处， A(x) * B(x)–C(x) = t(x) * h(x)。

在不知不觉中，一件关键又有趣的事情发生了：

证明者本来需要证明在 x=1、x=2、…… 、x=n 时，A(x) * B(x)–C(x) = 0，这是一种推理式证明，就像我们解数学题，需要一步步地推导和计算，在这种证明过程中，要隐藏解题的知识是困难的。

但现在，推理式证明变成了交互式证明：verifier 在一个随机点上提出挑战，prover 给出这个点上的解响应挑战；prover 需要有「知识」才能计算出随机点上的解，但这个解本身不会泄露「知识」。

而这，就是零知识证明得以成立的前提，或者说，如果没有交互式证明这种证明方法，零知识证明这个领域便不会存在。

接下来只剩下一个问题：为什么能通过验证多项式上的一个点来确定两个多项式 A(x) * B(x)–C(x) 与 t(x) * h(x) 是否相等？

这是由多项式的特性决定的，「一个多项式在任意点的计算结果都可以看做是其唯一身份的表示」。（引自 Maksym）

用图形说明更为直观。下图是两个多项式，蓝色曲线是 f(x) = x^3– 6 * x^2+ 11 * x– 6，绿色曲线是 f(x) = x^3– 6 * x^2+ 10 * x– 5，不难发现，两个多项式只有微小的不同，但它们的曲线却是迥异的。

就像世界上没有两片相同的树叶，世界上也没有会在某个区域重合的两条不同曲线，它们只会在有限的点上相交。对于两个阶数为 d （x 的最大指数）的多项式，它们相交的点数不会超过 d。

在本文的应用中，有一个多项式 A(x) * B(x)–C(x)，一个多项式 t(x) * h(x)，如果它们不相等，它们只会在最多 d 个点上相交，也就是在 d 个点上的解相同。

这意味着只有当验证者选择的随机挑战点 x 恰好是这 d 个点中的一个时，才有可能发生误判，即在 A(x) * B(x)–C(x) 与 t(x) * h(x) 不相同的情况下误以为它们相同。

误判的概率存在，但我们不用为此担心，比较 d 个点和 x 的取值范围，这件事发生的概率极低；结合后续在 zk-SNARK 协议中使用的密码学方法，这件事可以被认为几乎不可能发生。

那么现在，在全部的准备工作完成后，本文进入下一个阶段。对第一阶段的抽象总结就是：零知识证明的问题就是验证计算满足多个约束的问题，而多项式可以一个点验证多个约束。

第二阶段：使用 zk-SNARK 完成零知识证明

得益于交互式证明和多项式的特性，我们可以通过验证挑战点 x 上多项式 A(x) * B(x)–C(x) 的解与 t(x) * h(x) 的解是否相等来验证 A(x) * B(x)–C(x) = t(x) * h(x) 是否成立，这种方式是可以隐藏 A(x) * B(x)–C(x) 这个多项式的系数的。

多项式的系数就是零知识证明中的「知识 」，最明显的，这个系数里是包含了想要隐藏的秘密输入（解向量 s）的。

使用 zk-SNARK 完成零知识证明，就是完成 verifier 给出随机点进行挑战的工作和 prover 给出随机点上的解完成证明的工作，这实际上是_互不信任的 verifier 和 prover 之间的一场攻防战，他们使用的武器是密码学_。

verifier 加密挑战点

分析需要被验证的 A(x) * B(x)–C(x) = t(x) * h(x)：

• t(x) 是 verifier 和 prover 双方都知道的一个多项式，t(x) = (x-1) * (x-2) * …… * ( x-n)；

• A(x) * B(x) – C(x) 只有 prover 知道，它的系数包含着知识；

• h(x) 也只有 prover 知道，是用 A(x) * B(x) – C(x) 除以 t(x) 计算出来的，h(x) 不能被 verifier 知道，因为可以通过 t(x) 和 h(x) 计算出 A(x) * B(x) – C(x)。

为了清晰起见，先把 A(x) * B(x)–C(x) 写为 p(x)，把要证明的问题简化为证明 p(x) = t(x) * h(x)。

其证明过程包含如下 3 步：

• verifier 选择随机挑战点 x，假设 x= r；

• prover 收到 r 后，计算 p(r) 和 h(r)，并把这两个值给 verifier；

• verifier 计算 t(r)，然后计算 t(r) * h(r)，并判断 t(r) * h(r) = p(r) 是否成立，若成立，则验证通过。

这实际上就是 zk-SNARK 的基础工作流程，但直接这样做会有一个问题：

prover 是知道 t(x) 的，如果把 r 给他，他就能够计算出 t(r)，那么他完全可以构造出一对假的 p(x) 和 h(x)，使得 p(r)= t(r) * h(r)，结果就是他虽然不知道真正的 p(x)，却能骗过 verifier。

解决这一问题的办法就是对 r 加密，使得 prover 可以计算某种形式下 p(r) 和 h(r)，但却不能通过该形式下的 t(r) 构造假的满足验证要求的 p(x) 和 h(x)。

观察 prover 的证明过程，他需要计算 p(x) 和 h(x) 这两个多项式，但不管哪一个，其形式均为：c0+ c1*x^1+ ……+ cn*x^n；prover 本身知道 c0、c1 等等全部系数。

如果 verifier 把 x 给 prover，假设 x= s，prover 就能完成全部计算；但如果 verifier 把加密后的 s 给 prover，prover 是不能完成计算的，因为他无法用加密后的 s 计算出 s^2、……、s^n。

所以当 verifier 确定随机点 s 后，需要把加密后的 s、s^2、……、s^n 全部给 prover，这样 prover 才能完成计算。

在实际应用中，verifier 是把 E(s)、E(s^2)、……、E(s^n) 给到 prover，其中 E(s) 是 s 的加密值，E(s) = g^s (mod n)，这是一种同态加密方法。

同态加密有一个性质，就是先加密后计算的解与先计算后加密的解与是相同的。也就是说：

• c0+ c1*E(s)+ ……+ cnE(s^n) = g^(c0+ c1s^1+ ……+ cn*s^n）；

• 即，p(E(s)) = E(p(s)) = g^p(s)，h(E(s)) = E(h(s)) =g^h(s)；

• 那么，prover 就能通过计算 p(E(s)) 和 h(E(s))，得到 g^p(s) 和 g^h(s)。

此处只需要知道这种计算确实可行即可，如果想了解密码学部分的工作原理，可看我之前的一篇文章，《一文读懂零知识证明背后的简单逻辑》。

所以现在，证明过程变成了如下 3 步：

• verifier 选择随机挑战点 x，假设 x= s，然后把一整套 s 的加密值给 prover；

• prover 收到后，计算 g^p(s) 和 g^h(s)，并把这两个值给 verifier；

• verifier 计算 t(s)，然后计算 (g^h(s))^ t(s)，并判断 (g^h(s))^t(s) = g^p(s) 是否成立，若成立，则验证通过，因为这意味着 h(s) * t(s) = p(s)。

通过对随机点 s 加密，可以避免 prover 作弊，但 prover 还有一个漏洞可钻，即他不使用 verifier 给出的挑战点 s 计算 h(s) 和 t(s)，而是用其他值计算并欺骗 verifier。

所以 verifier 还需要一个方法，该方法能够证明 prover 给出的值确实是用 s 计算出来的。

本文将不具体展开这一部分，简单而言就是 verifier 除了选择随机数 s 外，还要选择一个随机数α，prover 给出的解需要维持 s 和α 之间的关系，如果这个关系被破坏了，则证明他没有用 s 在计算。

该方法被称作指数知识假设，若想了解具体内容，可阅读 Maksym 的文章。

在 verifier 完成了他的防守战后，轮到 prover 了。

prover 加密计算结果

虽然 prover 只把多项式在挑战点 x 上的解给了 verifier，但如果多项式系数的取值范围较小，verifier 是有可能通过暴力破解从解计算出多项式系数，即知识的。因此，prover 需要对解加密。

证明过程变成如下 3 步：

• verifier 选择随机挑战点 x，假设 x= s，以及随机数α，然后把一整套 s 的加密值、以及一整套α * s 的加密值给 prover；

• prover 收到后，计算 g^p(s)、g^h(s)、g^(α*p(s))；选择随机数δ 对解加密，变为 (g^p(s))^δ、(g^h(s))^δ、(g^(α*p(s)))^δ；然后把这 3 个加密值给 verifier；

• verifier 计算 t(s)，然后计算 ((g^h(s))^δ)^t(s)，并判断 ((g^h(s))^δ)^t(s) = (g^p(s))^δ是否成立，若成立，则意味着 h(s) * t(s) = p(s)；

• 与此同时，verifier 还需要验证 ((g^p(s))^δ)^α = (g^(α*p(s)))^δ是否成立，若成立，则证明 prover 给出的解是用 s 计算出来的。

如此一来，prover 也就完成了自己的攻防战。

从交互变为非交互

zk-SNARK 的 N 是指 Non-Interactive，即非交互，但不难发现在上述的证明过程中，是需要 verifier 和 prover 交互的，而且我们都知道，交互式证明本身是零知识证明得以成立的前提。那非交互是指什么？

很简单，所谓的非交互只不过是把 verifier 选择随机数的工作交给了「可信设置」来完成，也就是由一个可信任的第三方在证明开始前选择随机挑战点 x。

这种改变对 prover 没什么影响，因为他需要的始终是一组与 x 相关的加密值，而不用管这些加密值来自 verifier，还是来自可信第三方。但这种改变对 verifier 有影响，因为他本来知道 x，可以用 x 计算 t(x)，但现在他不知道了。

所以从交互到非交互，最主要的改变就是要在可信设置中把 t(x) 给到 verifier，以便他能完成验证工作。

t(x) 需要被加密，因为 prover 可以利用 t(x) 的值做弊；但加密后的 t(x) 又要能被用于计算，因为 verifier 需要计算 h(x) * t(x)。这便是这一部分的难点所在：h(x) 和 t(x) 都是加密值，但之前使用的同态加密方法不支持两个加密值的乘法。

zk-SNARK 使用配对操作解决这一问题，用公式表达就是 e(g^a, g^b)= a^g * b^g=（a * b）^g，其中 g^a 和 g^b 是加密值。配对操作可以把两个加密值映射为它们的乘积。

可信设置通过该方法把 t(x) 给到 verifier。于是，证明过程变为如下 3 步：

• 可信设置：可信第三方选择随机挑战点 x，假设 x= s，以及随机数α，然后把一整套 s 的加密值、以及一整套α * s 的加密值给 prover；再把 t(s) 的加密值 g^t(s) 和α 的加密值 g^α 给 verifier；

• prover 收到后，计算 g^p(s)、g^h(s)、g^(α*p(s))；选择随机数δ 对解加密，变为 (g^p(s))^δ、(g^h(s))^δ、(g^(α*p(s)))^δ；然后把这 3 个加密值给 verifier；

• verifier 计算并判断 e(g^p, g) = e(g^t(s), g^h) 是否成立，若成立，则意味着 h(s) * t(s) = p(s)；g^p、g^h、g^p′ 为 prover 提供的 3 个加密值的简写。

• 与此同时，verifier 还需要验证 e(g^p′ , g) = e(g^p, g^α) 是否成立，若成立，则证明 prover 给出的解是用 s 计算出来的。

到这一步，我们就基本完成了 zk-SNARK 协议的构造工作，它可以在不泄露多项式系数的情况下证明多项式，即实现零知识证明。

额外一提，在可信设置阶段为 prover 和 verifier 准备的加密值被称作 CRS （common reference string），用以生成 CRS 的随机数是要被销毁的，它们可用于作弊；可信设置需要可信第三方，通过什么机制选择可信第三方是一个议题。

可信设置影响 zk-SNARK 的通用性，因此也发展出了不需要可信设置的 zk-SNARK，其意义重大但理解起来并不难：只不过是换了一种方式提供随机挑战点 x。

不管有多少种 zk-SNARK，我们需要知道的是：零知识证明是一种交互式的证明系统，对它而言重要的、也是与安全和资源相关的一个工作就是，以什么样的方式提供随机挑战点。

把 p(x) 还原为 A(x) * B(x)–C(x)

zk-SNARK 协议需要证明的多项式是 A(x) * B(x)–C(x)，如果把 p(x) 还原为 A(x) * B(x)–C(x)，相较于 p(x) 时的协议，主要区别在于：

• prover 需要分别提供 A(s)、B(s)、C(s) 的加密值；

• verifier 需要验证 A(s) * B(s) = h(s) * t(s)+ C(s)；

• 在对 prover 的计算进行约束时（比如必须用 s 计算），需要有 3 个不同的α 分别对应于 A(s)、B(s)、C(s)；当 prover 对计算结果加密时，需要有 3 个不同的δ分别加密 A(s)、B(s)、C(s)。

在具体的 zk-SNARK 协议中，还会通过一些设计来改进协议，本文不再一一论述，zk-SNARK 的探秘之旅到这里就全部结束啦。

在旅程结束之际，有几点说明：

1.zk-SNARK 有不同的组合实现方法，本文主要是以 Pinocchio 协议为线索；密码学所涉甚广，文章难免会有疏漏和理解不当之处，请不要尽信，深入研究需以论文为参考。
2. 本文在构建 zk-SNARK 协议部分（第二部分）采用了 Maksym 文章的框架；Maksym 的文章极有条理地介绍了 zk-SNARK，但可能对于不太具备相关背景知识的读者来说仍有一定的理解难度，这也是我写这篇文章的原因所在。

那么，如果你读到了这里，谢谢你；如果你在知晓零知识证明的整个实现过程后，被其中的数学之美打动，那我太开心了。

参考：

1. 东泽；浅谈零知识证明：背景与起源

2. Vitalik Buterin；《Quadratic Arithmetic Programs: from Zero to Hero》，

3. Maksym Petkus；《Why and How zk-SNARK Works: Definitive Explanation》，https://arxiv.org/pdf/1906.07221.pdf；

中文版本：从零开始学习 zk-SNARK （一）——多项式的性质与证明，翻译：even@ 安比实验室，校对：valuka@ 安比实验室

4. 李画；一文读懂零知识证明背后的简单逻辑

来源链接：mp.weixin.qq.com