对 zk-SNARKs 如何可能的大致介绍

2021 年 1 月 26 日查看所有帖子


特别感谢 Dankrad Feist、Karl Floersch 和 Hsiao-wei Wang 的反馈和审阅。

也许过去十年中出现的最强大的密码技术是通用的简洁零知识证明，通常称为 zk-SNARKs（“知识的零知识简洁论证”）。zk-SNARK 允许您生成某些计算具有某些特定输出的证明，这样即使底层计算需要很长时间运行，也可以极快地验证证明。“ZK”（“零知识”）部分增加了一个附加功能：证明可以隐藏计算的一些输入。

例如，您可以为语句“我知道一个秘密数字，如果您将‘牛’这个词添加到末尾，并 SHA256 对其进行 1 亿次哈希运算，输出以0x57d00485aa”开头，则可以对其进行证明。验证者可以比他们自己运行 1 亿个散列更快地验证证明，而且证明也不会透露秘密数字是什么。

在区块链的背景下，这有两个非常强大的应用：

  1. 可扩展性：如果一个区块需要很长时间来验证，一个人可以验证它并生成一个证明，其他人可以快速验证这个证明
  2. 隐私：您可以证明您有权转让某些资产（您收到了它，但您尚未转让），而无需透露您收到的资产的链接。这确保了安全性，而不会向公众过度泄露有关谁与谁进行交易的信息。

但是 zk-SNARK 非常复杂；事实上，就在 2014-17 年，它们仍然经常被称为“月球数学”。好消息是，从那时起，协议变得更简单，我们对它们的理解也变得更好了。这篇文章将尝试解释 ZK-SNARKs 是如何工作的，以一种对数学有中等水平理解的人应该可以理解的方式。

请注意，我们将专注于可扩展性；一旦具有可扩展性，这些协议的隐私实际上相对容易，因此我们将在最后回到该主题。

为什么 ZK-SNARKs“应该”很难

让我们以我们开始的例子为例：我们有一个数字（我们可以将“cow”后跟秘密输入编码为整数），我们取该数字的 SHA256 哈希值，然后我们再重复 99,999,999 次，我们得到输出，我们检查它的起始数字是什么。这是一个巨大的计算。

“简洁”的证明是证明的大小和验证它所需的时间都比要验证的计算增长得慢得多的证明。如果我们想要一个“简洁”的证明，我们不能要求验证者在每轮散列中做一些工作（因为这样验证时间将与计算成正比）。相反，验证者必须以某种方式检查整个计算，而无需查看计算的每个单独部分。

一种自然的技术是随机抽样：我们让验证者查看 500 个不同位置的计算，检查这些部分是否正确，如果所有 500 个检查都通过，那么假设其余的计算很可能没问题， 也？

这样的过程甚至可以变成使用Fiat-Shamir 启发式的非交互式证明：证明者计算计算的默克尔根，使用默克尔根伪随机选择 500 个索引，并提供数据的 500 个对应的默克尔分支. 关键思想是证明者不知道他们需要揭示哪些分支，直到他们已经“承诺”了数据。如果恶意证明者在了解将要检查哪些索引后试图伪造数据，这将改变 Merkle 根，这将导致一组新的随机索引，这将需要再次伪造数据......证明者在无休止的循环中。

但不幸的是，以这种方式天真地应用随机抽样来抽查计算存在一个致命的缺陷：计算本质上是脆弱的。如果恶意证明者在计算过程中的某个地方翻转了一位，他们可以使其给出完全不同的结果，而随机抽样验证者几乎永远不会发现。



只需要一个故意插入的错误，随机检查几乎永远不会发现，使计算给出完全错误的结果。

 

如果要解决提出 zk-SNARK 协议的问题，许多人会走到这一步，然后陷入困境并放弃。验证者如何在不单独查看计算的每个部分的情况下检查计算的每个部分？但事实证明，有一个聪明的解决方案。

多项式

多项式是一类特殊的代数表达式，其形式如下：

  • X+5
  • X4
  • X3+3X2+3X+1
  • 628X271+318X270+530X269+...+69X+381

即它们是任何（有限！）形式的项的总和 CX克.

多项式有很多令人着迷的地方。但在这里我们将放大一个特定的：多项式是一个单一的数学对象，可以包含无限量的信息（将它们视为整数列表，这是显而易见的）。上面的第四个例子包含 816 位tau，很容易想象一个包含更多的多项式。

此外，多项式之间的单个方程可以表示数字之间无限数量的方程。例如，考虑方程一种(X)+乙(X)=C(X). 如果这个等式成立，那么以下事实也成立：

  • 一种(0)+乙(0)=C(0)
  • 一种(1)+乙(1)=C(1)
  • 一种(2)+乙(2)=C(2)
  • 一种(3)+乙(3)=C(3)

对于每个可能的坐标，依此类推。您甚至可以构建多项式来特意表示一组数字，这样您就可以一次检查多个方程。例如，假设您想检查：

  • 12 + 1 = 13
  • 10 + 8 = 18
  • 15 + 8 = 23
  • 15 + 13 = 28

您可以使用称为拉格朗日插值的过程来构造多项式一种(X)(12, 10, 15, 15)在某些特定的坐标集（例如(0, 1, 2, 3)）上作为输出给出，乙(X)(1, 8, 8, 13)这些相同坐标上的输出，依此类推。事实上，这里是多项式：

  • 一种(X)=-2X3+192X2-192X+12
  • 乙(X)=2X3-192X2+292X+1
  • C(X)=5X+13

检查方程 一种(X)+乙(X)=C(X) 使用这些多项式同时检查上述所有四个方程。

多项式与自身的比较

您甚至可以使用简单的多项式方程来检查同一多项式的大量相邻评估之间的关系。这稍微先进一些。假设您要检查，对于给定的多项式F, F(X+2)=F(X)+F(X+1) 整数范围内 {0,1...98}（所以如果你也检查F(0)=F(1)=1， 然后 F(100)将是第 100 个斐波那契数）。

作为多项式， F(X+2)-F(X+1)-F(X)不会完全为零，因为它可能会给出超出范围的任意答案X={0,1...98}. 但是我们可以做一些聪明的事情。一般来说，有一个规则，如果多项式磷 在某个集合中为零 秒={X1,X2...Xn} 那么它可以表示为 磷(X)=Z(X)＊H(X)， 在哪里 Z(X)= (X-X1)＊(X-X2)＊...＊(X-Xn) 和 H(X)也是多项式。换句话说，任何在某个集合上为零的多项式都是在同一集合上为零的最简单（最低阶）多项式的（多项式）倍数。

为什么会这样？这是多项式长除法的一个很好的推论：因子定理。我们知道，划分时磷(X) 经过 Z(X)，我们会得到一个商 问(X) 和剩下的 电阻(X) 满足 磷(X)=Z(X)＊问(X)+电阻(X)，其中余数的程度 电阻(X) 严格小于 Z(X). 既然我们知道磷 全部为零 秒， 这意味着 电阻 所有的都必须为零 秒以及。所以我们可以简单地计算电阻(X) 通过多项式插值，因为它最多是一个多项式 n-1 我们知道 n 值（零点在 秒）。用全零插入多项式给出零多项式，因此电阻(X)=0 和 H(X)=问(X).

回到我们的例子，如果我们有一个多项式 F 编码斐波那契数（所以 F(X+2)=F(X)+F(X+1) 穿过 X={0,1...98})，那么我可以说服你 F 通过证明多项式实际上满足这个条件磷(X)= F(X+2)-F(X+1)-F(X) 通过给您商数，在该范围内为零：

H(X)=F(X+2)-F(X+1)-F(X)Z(X)

在哪里 Z(X)=(X-0)＊(X-1)＊...＊(X-98).

你可以计算 Z(X) 你自己（理想情况下你会预先计算它），检查方程，如果检查通过然后 F(X) 满足条件！

现在，退后一步，注意我们在这里做了什么。我们将一个 100 步长的计算（计算第 100 个斐波那契数）转换为具有多项式的单个方程。当然，证明第 N 个斐波那契数并不是一项特别有用的任务，尤其是因为斐波那契数具有封闭形式。但是你可以使用完全相同的基本技术，只是使用一些额外的多项式和一些更复杂的方程，用任意大量的步骤对任意计算进行编码。

现在，如果只有一种方法可以用多项式验证方程，这比检查每个系数要快得多……

多项式承诺

再一次，事实证明有一个答案：多项式承诺。多项式承诺最好被视为对多项式进行“散列”的一种特殊方式，其中散列具有附加属性，您可以通过检查多项式之间的散列之间的方程来检查多项式之间的方程。不同的多项式承诺方案在您可以检查的方程类型方面具有不同的属性。

以下是您可以使用各种多项式承诺方案执行的一些常见示例（我们使用 C○米(磷) 意思是“对多项式的承诺 磷”）：

  • 添加它们：给定C○米(磷), C○米(问) 和 C○米(电阻) 检查是否 磷+问=电阻
  • 乘以它们：给定C○米(磷), C○米(问) 和 C○米(电阻) 检查是否 磷＊问=电阻
  • 在某一点评估：给定磷, 瓦, z 和补充证明（或“证人”） 问, 验证 磷(瓦)=z

值得注意的是，这些原语可以相互构造。如果你可以加法和乘法，那么你可以评估：证明磷(瓦)=z，你可以构造 问(X)=磷(X)-zX-瓦, 并且验证者可以检查是否 问(X)＊(X-瓦)+z=?磷(X). 这是有效的，因为如果这样的多项式问(X) 存在，那么磷(X)-z=问(X)＊(X-瓦)， 意思就是 磷(X)-z 等于零 瓦 （作为 X-瓦 等于零 瓦） 所以 磷(X) 等于 z 在 瓦.

如果你能评估，你就可以做各种检查。这是因为有一个数学定理，大致说，如果一些涉及多项式的方程在随机选择的坐标处成立，那么它几乎肯定对整个多项式成立。因此，如果我们拥有的只是证明评估的机制，我们可以检查例如。我们的方程式磷(X+2)-磷(X+1)-磷(X)=Z(X)＊H(X) 使用互动游戏：



正如我之前提到的，我们可以使用Fiat-Shamir 启发式方法使这种非交互式：证明者可以通过设置（其中是任何加密哈希函数；它不需要任何特殊属性）来计算自己。证明者不能通过挑选来“欺骗”并且“适合”在那个特定而不是其他地方，因为他们当时不知道他们正在挑选和！rr = hash(com(P), com(H))hashPHrrPH

到目前为止的快速回顾

  • ZK-SNARK 很难，因为验证者需要以某种方式检查计算中的数百万步，而无需直接检查每个单独的步骤（因为这会花费太长时间）。
  • 我们通过将计算编码为多项式来解决这个问题。
  • 单个多项式可以包含无限大的信息量和单个多项式表达式（例如 磷(X+2)-磷(X+1)-磷(X)=Z(X)＊H(X)) 可以“代替”无限大量的数字之间的方程。
  • 如果你可以用多项式验证方程，你就隐含地验证了所有的数字方程（替换 X 与任何实际的 x 坐标）同时进行。
  • 我们使用一种特殊类型的多项式“散列”，称为多项式承诺，使我们能够在很短的时间内实际验证多项式之间的方程，即使基础多项式非常大。

那么，这些花哨的多项式哈希是如何工作的呢？

目前广泛使用的主要有3种方案：防弹、Kate和FRI。

老实说，他们没那么简单。所有这些数学直到 2015 年左右才真正起飞是有原因的。

请？

在我看来，最容易完全理解的是 FRI（如果你愿意接受椭圆曲线配对作为“黑匣子”，Kate 会更容易一些，但配对真的很复杂，所以总的来说我觉得 FRI 更简单）。

以下是 FRI 的简化版本的工作原理（为了简单起见，真正的协议有许多技巧和优化，这里没有）。假设你有一个多项式磷 有学位 <n. 承诺磷 是一组评估的默克尔根 磷 在一些预先选择的坐标集（例如。 {0,1....8n-1}，尽管这不是最有效的选择）。现在，我们需要添加一些额外的东西来证明这组评估实际上是一个学位<n 多项式。

让 问 是仅包含偶数系数的多项式 磷， 和 电阻 是仅包含奇数系数的多项式 磷. 因此，如果磷(X)=X4+4X3+6X2+4X+1， 然后 问(X)=X2+6X+1 和 电阻(X)=4X+4 （请注意，系数的度数会“折叠”到范围 [0...n2)）。

请注意 磷(X)=问(X2)+X＊电阻(X2) （如果这对您来说不是很明显，请停下来思考并查看上面的示例，直到明显为止）。

我们要求证明者提供默克尔根 问(X) 和 电阻(X). 然后我们生成一个随机数r 并要求证明者提供“随机线性组合” 秒(X)=问(X)+r＊电阻(X).

我们伪随机地对大量索引进行采样（像以前一样使用已经提供的 Merkle 根作为随机性的种子），并要求证明者提供 Merkle 分支 磷, 问, 电阻 和 秒在这些指数。在每个提供的坐标中，我们检查：

  • 磷(X) 实际上是相等的 问(X2)+X＊电阻(X2)
  • 秒(X) 实际上是相等的 问(X)+r＊电阻(X)

如果我们进行足够的检查，那么我们可以确信 秒(X) 在最多 1% 的情况下与“提供的”值不同。

请注意 问 和 电阻 都有学位 <n2. 因为秒 是一个线性组合 问 和 电阻, 秒 也有学位<n2. 这反过来起作用：如果我们能证明秒 有学位 <n2，那么它是随机选择的组合这一事实可以防止证明者选择恶意 问 和 电阻 具有“抵消”的隐藏高度系数，所以 问 和 电阻 都必须是学位 <n2，并且因为 磷(X)=问(X2)+X＊电阻(X2)， 我们知道 磷 必须有学位 <n.

从这里，我们简单地重复游戏 秒，逐渐将我们关心的多项式“减少”到越来越低的程度，直到它的程度足够低，我们可以直接检查它。



和前面的例子一样，这里的“Bob”是一个抽象，对于密码学家在心理上推理协议很有用。实际上，Alice 自己生成整个证明，为了防止她作弊，我们使用 Fiat-Shamir：我们r根据直到那时为止在证明中生成的数据的哈希值来选择每个随机样本坐标或值。

完整的“FRI 承诺” 磷 （在这个简化的协议中）将包括：

  1. 评估的默克尔根 磷
  2. 评估的默克尔根 问, 电阻, 秒1
  3. 随机选择的分支 磷, 问, 电阻, 秒1 去检查 秒1 正确地“减少自” 磷
  4. Merkle 根和随机选择的分支，就像在步骤 (2) 和 (3) 中一样，用于连续降低度数 秒2 从减少 秒1, 秒3 从减少 秒2，一直下降到低度 秒克 （这被重复 ≈升○G2(n) 总次数）
  5. 评估的完整默克尔树 秒克 （所以我们可以直接检查）

过程中的每一步都会引入一些“错误”，但是如果添加足够的检查，那么总错误将足够低，您可以证明 磷(X) 等于一个学位 <n多项式至少在 80% 的位置上。这对于我们的用例来说已经足够了：如果你想在 zk-SNARK 中作弊，你需要对一个分数进行多项式承诺，并且任何分数表达式的评估集将不同于任何实数的评估程度<n 多项式在如此多的位置上，以致于对它们做出 FRI 承诺的任何尝试都将失败。

此外，您可以仔细检查 FRI 承诺中对象的总数和大小在次数上是对数的，因此对于大型多项式，承诺确实比多项式本身小得多。

检查这种类型的不同多项式承诺之间的方程（例如检查 一种(X)+乙(X)=C(X) 鉴于 FRI 承诺 一种, 乙 和 C)，只需随机选择许多索引，向证明者询问每个多项式的每个索引处的 Merkle 分支，并验证该等式在每个位置上实际上是否成立。

上面的描述是一个非常低效的协议；有一整套代数技巧可以将其效率提高大约一百倍，如果您想要一个实际上可行的协议，例如，在区块链交易中使用，则您需要这些技巧。特别是，例如，问 和 电阻 实际上并不是必须的，因为如果你非常巧妙地选择你的评价点，你可以重构对 问 和 电阻 你需要直接从评估 磷. 但是上面的描述应该足以让您相信多项式承诺从根本上是可能的。

有限域

在上面的描述中，有一个隐藏的假设：多项式的每个单独“评估”都很小。但是当我们处理很大的多项式时，这显然不是真的。如果我们以上面的例子为例，628X271+318X270+530X269+...+69X+381，对 816 位 tau 进行编码，并在 X=1000，你会得到......一个包含所有 tau 数字的 816 位数字。因此，我们还需要添加一件事。在实际实现中，我们在这里所做的所有算术都不会使用实数上的“常规”算术来完成。相反，它将使用模块化算法来完成。

我们重新定义我们所有的算术运算如下。我们选择一些素数“模数” p。% 运算符的意思是“取余数”：15 % 7=1, 53 % 10=3等（请注意，答案总是非否定的，例如 -1 % 10=9）。我们重新定义

X+是⇒(X+是) % 磷

X＊是⇒(X＊是) % 磷

X是⇒(X是) % 磷

X-是⇒(X-是) % 磷

X/是⇒(X＊是磷-2) % 磷

以上规则都是自洽的。例如，如果磷=7， 然后：

  • 5+3=1 （作为 8 % 7=1)
  • 1-3=5 （作为 -2 % 7=5)
  • 2⋅5=3
  • 3/5=2 （作为 （3⋅55) % 7=9375 % 7=2)

更复杂的恒等式，例如分配律也成立： (2+4)⋅3 和 2⋅3+4⋅3 两者都评估为 4. 甚至像这样的公式(一种2-乙2) = (一种-乙)⋅(一种+乙) 在这种新的算术中仍然是正确的。

分工是最难的部分；我们不能使用正则除法，因为我们希望值始终保持整数，而正则除法通常会给出非整数结果（如3/5）。我们使用费马小定理来解决这个问题，它指出对于任何非零X<磷，它认为 X磷-1 % 磷=1. 这意味着X磷-2 给出一个数字，如果乘以 X 再一次，给 1，所以我们可以说 X磷-2 （这是一个整数）等于 1X. 一种更复杂但更快速的评估这个模除法运算符的方法是扩展的欧几里得算法，在这里用 python 实现。



由于数字如何“环绕”，模算术有时被称为“时钟数学”

 

通过模块化数学，我们创建了一个全新的算术系统，它以传统算术自洽的所有相同方式自洽。因此，我们可以讨论该领域中所有相同类型的结构，包括多项式，我们在“常规数学”中讨论过。密码学家喜欢在模块化数学（或更一般地说，“有限域”）中工作，因为任何模块化数学计算都可能导致数字的大小受到限制 - 无论您做什么，这些值都不会“逃脱”集合{0,1,2...磷-1}. 即使在有限域中计算 100 万次多项式也永远不会给出该集合之外的答案。

将计算转换为一组多项式方程的更有用的例子是什么？

假设我们想证明，对于一些多项式 磷, 0≤磷(n)<264, 没有透露确切的价值 磷(n). 这是区块链交易中的一个常见用例，您希望证明交易的余额为非负值，而无需透露余额是多少。

我们可以使用以下多项式方程（为简单起见假设 n=64)：

  • 磷(0)=0
  • 磷(X+1)=磷(X)＊2+电阻(X) 整个范围 {0...63}
  • 电阻(X)∈{0,1} 整个范围 {0...63}

后两个陈述可以重新表述为“纯”多项式方程如下（在这种情况下 Z(X)=(X-0)＊(X-1)＊...＊(X-63))：

  • 磷(X+1)-磷(X)＊2-电阻(X)=Z(X)＊H1(X)
  • 电阻(X)＊(1-电阻(X))=Z(X)＊H2(X) （注意巧妙的技巧： 是＊(1-是)=0 当且仅当 是∈{0,1})

这个想法是连续评估 磷(一世) 逐位建立数字：如果 磷(4)=13，那么到该点的评估序列将是： {0,1,3,6,13}. 在二进制中，1 是1，3 是11，6 是110，13 是1101；注意如何磷(X+1)=磷(X)＊2+电阻(X) 一直在最后添加一位 电阻(X)是零还是一。范围内的任何数字0≤X<264 可以通过这种方式建立超过 64 个步骤，超出该范围的任何数字都不能。

隐私

但是有一个问题：我们怎么知道对 磷(X) 和 电阻(X) 不要“泄露”使我们能够发现确切价值的信息 磷(64)，我们试图隐藏？

有一些好消息：这些证明是小证明，可以对大量数据和计算做出陈述。因此，一般来说，证明通常不会大到足以泄露一点点信息。但是我们可以从“一点点”到“零”吗？幸运的是，我们可以。

在这里，一个相当普遍的技巧是在多项式中添加一些“捏造因子”。当我们选择磷, 加上一个很小的倍数 Z(X) 到多项式中（即设置 磷′(X)=磷(X)+Z(X)＊乙(X) 对于一些随机 乙(X)）。这并不影响语句的正确性（实际上，磷′ 评估为相同的值 磷在“计算正在进行”的坐标上，所以它仍然是一个有效的成绩单），但它可以在承诺中添加足够的额外“噪音”，使任何剩余的信息无法恢复。此外，在 FRI 的情况下，重要的是不要对发生计算的域内的随机点进行采样（在这种情况下{0...64}）。

我们可以再重述一遍吗？？

  • 三种最突出的多项式承诺类型是 FRI、Kate 和防弹。
  • 凯特在概念上是最简单的，但取决于椭圆曲线配对的真正复杂的“黑匣子”。
  • FRI 很酷，因为它只依赖于哈希；它的工作原理是连续将多项式减少到更低次和更低次的多项式，并使用 Merkle 分支进行随机样本检查以证明每一步的等价性。
  • 为了防止单个数字的大小爆炸，我们不是对整数进行算术和多项式运算，而是在有限域上进行所有操作（通常是整数以某个素数为模p）
  • 多项式承诺自然适用于隐私保护，因为证明已经比多项式小得多，因此多项式承诺无论如何也不能透露多项式中的一点信息。但是我们可以为我们承诺的多项式添加一些随机性，以将显示的信息从“一点点”减少到“零”。

哪些研究问题仍在进行中？

  • 优化 FRI：已经有很多优化涉及精心挑选的评估域，“ DEEP-FRI ”，以及许多其他使 FRI 更有效的技巧。Starkware 和其他公司正在为此努力。
  • 将计算编码为多项式的更好方法：找出将涉及哈希函数、内存访问和其他特征的复杂计算编码为多项式方程的最有效方法仍然是一个挑战。这方面已经取得了很大进展（例如参见PLOOKUP），但我们仍然需要更多，特别是如果我们想将通用虚拟机执行编码为多项式。
  • 增量可验证的计算：能够在计算继续的同时有效地保持“扩展”证明会很好。这在“单一证明者”的情况下很有价值，但在“多证明者”的情况下也很有价值，特别是在不同参与者创建每个块的区块链中。有关最近的一些工作，请参阅Halo。

我想了解更多！

我的材料

别人的材料