# ZK-SNARKs 的缺失解释：第 1 部分

By [numbers3333](https://paragraph.com/@numbers3333) · 2022-06-05

---

问题的第一部分很容易回答。ZK-SNARKs，无论他们的有趣名字可能暗示什么，都只是零知识证明，即：

请注意，本文是 Real-World Cryptography一书的一部分。

什么是 ZK-SNARK，它们是如何工作的？这是我多年来一直有的一个问题，并且一直觉得我找到的资源并没有给出关于所有这些东西如何工作的清晰直觉。所以今天，在我自己的理解有了突破之后，我觉得还是把我学到的东西重新分享给一个更容易理解的图景就好了。这篇文章的目的是让您以直观的方式思考这些事情，并注意您可以自己填补的空白（如果您愿意的话）。

让术语不碍事 问题的第一部分很容易回答。ZK-SNARKs 不管他们的有趣名字可能暗示什么，都是简单 的零知识证明，即：

非交互式 一般用途 简洁 “咦，这些都是什么字？” 你问，被他们的含糊吓倒了。

首先， 零知识证明 是加密证明你知道某事，而不透露某事（零知识）。那个“东西”通常被称为 见证人，但这个细节并不重要。有很多关于零知识证明的资源，所以我不会解释它们是如何工作的，或者它们的确切密码属性是什么（完整性、可靠性、零知识）。零知识证明经常被用来证明你知道某个组元素的某个底的离散对数（例如 g ˣ mod p中的x 是 什么），或类似的有限陈述。

“有限是的，但仍然有用！” Schnorr 大喊道，Schnorr 签名方案的发明者是通过对离散对数的知识进行零知识证明并使其 非交互来制造的. 零知识证明（或 ZKP）是证明者（知道证人）和验证者（必须被说服）之间的交互协议。交互式协议在现实世界中很糟糕，因为它通常会限制原语的潜在用例数量，并且会根据证明者和验证者之间需要发生的往返次数来减慢协议的速度。幸运的是，一些 ZKP 可以在不与验证者交互的情况下构建。换句话说，证明者可以简单地创建一个证明，并且该证明可以在以后的任何时间点被任何人验证，而无需证明者的进一步帮助。当 ZKP 变成非交互式时，我们简单地称它们为非交互式零知识证明或 NIZK。我在这里更多地谈论签名和零知识证明之间的联系 .

ZKP 和 NIZK 也可以构建在更一般的语句上，例如“我知道某个函数的输入，因此执行会给出一些输出”，或者更具体地说，“我知道 f( a , b) = c中的 a ”。如果这仍然没有意义，请考虑为说明通用 ZKP 而给出的常见示例：“我知道一些特定数独难题的解决方案”。

我们快到了： ZK-SNARK 是通用的非交互式零知识证明，等等！它们也很 简洁，这意味着它们产生的证明体积小，验证速度快，这使得它们如此特别，值得被称为 ZK-SNARK。并非每个现代证明系统都值得这种特殊分类，例如 STARKs 不🙁

回顾一下：

零知识证明：加密证明你知道某事，但不透露某事 非交互式：在没有验证者帮助的情况下构建的证明 通用目的：更通用陈述的证明，例如程序的秘密输入或输出的知识 简洁：快速验证的小证明 实际的东西 但您不仅问了“什么是 ZK-SNARK？”，还问了“它们是如何工作的？”

哦，男孩，这是一个复杂的问题。首先，有很多很多的方案，太多了，所以我不确定如何回答这个问题。但我对它们中的一些如何工作有一些了解，所以我想它们中的大多数都遵循这种模式，或者改进它。所以让我解释一下……

首先，有很多很多 zk-SNARK 方案，真的太多了。

但大多数都建立在这种类型的结构上：

一个证明系统，允许证明者向验证者证明某些东西，我将在这篇文章中解释。 将程序翻译或编译成证明系统可以证明的东西，我将在本文的第 2 部分中解释。 第一部分并不难理解，而第二部分则需要研究生课程。

所以我们先来看看第一部分。

证明你对约束多项式的了解 zk-SNARKs 的主要思想是，它们都是关于 证明你知道一些 具有一些根的多项式f(x)。

根我的意思是验证者心中有一些值（例如， 1和 2）并且证明者必须证明他们心中的秘密多项式对于这些值的计算结果为 0 （例如， f(1) = f( 2) = 0 )。

顺便说一句， 对于某些多项式 h(x) ，以1 和 2 作为根的多项式（在我们的示例中）可以写为 f(x)=(x-1)(x-2)h( x) 。

（如果您不相信，请尝试在 x=1 和 x=2处进行评估。）

所以我们说证明者必须证明他们知道 f(x) 和 h(x) 使得 f(x) = t(x)h(x) 对于某些目标多项式 t(x) = (x-1) (x-2) （在示例中， 1 和 2 是验证者想要检查的根）。

但就是这样，这就是 zk-SNARKs 证明系统通常提供的东西：证明你知道一些多项式的东西。

我重复这一点是因为我第一次了解到这对我来说毫无意义：如果你能证明的只是你知道一个多项式，你怎么能证明你知道某个程序的秘密输入。

嗯，这就是 zk-SNARK 的第二部分如此困难的原因：它是关于将程序转换为多项式。但稍后会详细介绍。

回到我们的证明系统，如何证明他们知道这样一个函数 f(x)？

好吧，他们只需要证明他们知道 h(x) ，这样您就可以将 f(x)写 为 f(x) = t(x)h(x)。呃……这里没那么快。

我们在谈论 零知识 证明，对吗？

我们如何在不给出 f(x)的情况下证明这一点？

答案在于以下三个技巧：

同态承诺。类似于我们在其他零知识证明中看到的承诺方案。 双线性对。一种具有一些有趣特性的数学结构，稍后会详细介绍。 不同的多项式在大多数情况下计算出不同的值这一事实 。 那么让我们逐一介绍吧？

隐藏部分证明的同态承诺 第一个技巧是使用 承诺 来隐藏我们发送给证明者的值。

但是我们不仅要隐藏它们，我们还希望允许 验证者 对它们执行一些操作，以便他们可以验证证明。具体验证如果证明者提交了他们的多项式 f(x) 以及 h(x)，那么我们有

com(f(x)) = com(t(x)) com(h(x)) = com(t(x)h(x))

其中承诺 com(t(x)) 由验证者计算，作为对多项式的约定约束。

这些操作称为 同态操作 ，如果我们使用散列函数作为提交机制，我们就无法执行它们。

由于这些同态承诺，我们可以“隐藏指数中的值”（例如，对于值 v 然后发送承诺 gv mod p）并执行有用的计算，如相等：观察如果 a = bc 那么 g ᵃ = g ᵇ gᶜ = gᵇ⁺ᶜ 。

等等，这不是我们想要的……我们想要 g ᵃ = g ᵇᶜ。

双线性对改善我们的同态承诺 g ᵃ = (g ᵇ ) ᶜ = g ᵇᶜ 让我们到达那里，但前提是 c 是已知值而不是承诺（例如， g ᶜ）。不幸的是，这是我们的证明协议的一个限制，因为承诺之间会有乘法运算。这就是 双线性对 可以用来解除阻塞的地方，这也是 我们在 zk-SNARK 中使用双线性对的唯一原因（实际上只是为了能够将承诺中的值相乘）。

我不想深入探讨什么是双线性配对，但只要知道它只是我们工具包中的另一个工具：

取我们组的两个值（由 g产生的值以不同的幂模 p形成）并将它们放在另一个组中。 允许通过将东西从一组移动到另一组来进行乘法运算， 我们可以将以前无法相乘的东西相乘。 因此，使用 e 作为编写双线性对的典型方式，我们有 e(g ₁ , g ₂ ) = h ₃，我们可以使用它通过以下一个方程执行隐藏在指数中的乘法：

e(g ᵇ , g ᶜ ) = e(g) ᵇᶜ

同样，我们使用双线性对来使我们的承诺不仅对于加法是同态的，而且对于乘法也是同态的。

请注意，双线性对在密码学的其他地方也有使用，并且正在慢慢成为更常见的构建块：它们可以在同态加密方案中看到（这在我们在这里看到的情况之后是有意义的），也可以在签名方案中看到劳工统计局。

简洁从何而来？ 最后，zk-SNARKs 的 简洁 性来自于这样一个事实，即两个不同的函数将在大多数时间评估不同的点。

这对我们来说意味着如果我的 f(x) 不等于 t(x)h(x)，这意味着我没有一个 真正具有我们选择的根的多项式f(x)验证者，然后 在随机点 r处评估 f(x) 和 t(x)h(x)大部分时间 不会给出相同的结果 。换句话说，对于几乎所有 r，我们有 f(r) ≠ t(r)h(r)。这被称为 Schwartz-Zippel 引理，我在下图中描绘了它。

Schwartz-Zippel 引理说两个不同的 n 次多项式最多可以在 n 个点相交。换句话说，两个不同的多项式在大多数点上会有所不同。

知道了这一点，就足以证明 com(f(r)) = com(t(r)h(r)) 对于某个随机点 r。这就是 zk-SNARK 证明如此之小的原因：通过比较组中的点，您最终会比较更大的多项式！

但这也是大多数 zk-SNARK 结构所需的“可信设置”背后的原因。

如果证明者知道将用于检查等式的随机点 r ，那么他们可以伪造一个仍将验证等式的无效多项式。

因此，受信任的设置是关于：

1.  创建一个随机值 r。
    
2.  提交不同的幂运算
    

以便证明者可以在不知道点r的情况下使用它们来计算它们的多项式 。

1.  破坏值 r。
    

第二点有意义吗？

如果我作为证明者的多项式是 f(x) = 3x ² + x 那么我所要做的就是计算

获得在该随机点 r评估的多项式的承诺（不知道 r）。

从程序到多项式 到目前为止，证明者必须找到的多项式的约束是它有一些根（一些值用我们的多项式计算为 0）。

但是我们如何将更一般的陈述转化为多项式知识证明呢？

加密货币中的典型语句（这些是目前最常使用 zk-SNARK 的应用程序）的形式如下：

证明一个值在 \[0, 264\] 范围内（这称为范围证明） 证明一个（秘密）值包含在某个给定的（公共）默克尔树中 证明某些值之和等于某些其他值之和 等等… 这就是困难的部分。

正如我之前所说，将程序执行转换为多项式的知识“有点需要研究生课程进入该学科”。

接下来会发生的是：

1.  我们的程序首先会被转换成一个算术电路，一个由数学构成的电路！
    
2.  该算术电路将被转换为具有某种形式的方程组（称为 rank-1 约束系统或 R1CS）。
    
3.  然后我们将使用一个技巧将我们的方程组转换为多项式。
    

这将是本系列的第 2 部分。

---

*Originally published on [numbers3333](https://paragraph.com/@numbers3333/zk-snarks-1)*