年度零知识攻击可能已经发生，或者Nova是如何被攻破的 - ZKSECURITY

上周，一篇奇怪的论文 (由 Wilson Nguyen 等人撰写) 发表了：重新审视曲线循环上的 Nova 证明系统。其良性的标题可能没有引起很多人的注意，但在其页面中，隐藏着我们见过的对零知识证明 (ZKP) 系统最令人印象深刻和最具破坏性的攻击之一。由于 ZKP 系统的目的是创建一种加密证明，以证明计算结果的正确性，该论文演示了一个错误的计算结果，并附带了一个有效的证明。

为了说明情况，我们一个月前刚刚推出了 zkSecurity（本博客背后的公司），基于我们观察到许多构建在 ZKP 框架之上的用户应用程序都存在缺陷。但我们很少看到框架和系统本身被完全破坏的情况。曾经有 00 攻击（由 Nguyen Thoi Minh Quan 发起），但它针对的是一个糟糕的（plonk）实现（它始终接受值 0 作为有效证明）。2018 年还发现了 Zcash 上的伪造漏洞，由于原始论文设置阶段的漏洞，该漏洞可能允许任何人为其电路生成虚假证明。

但从那以后，什么也没有发生。然后就在上周，一个最重要的 ZKP 系统实现，Nova（来自微软），被随意地破坏了。2023 年已经过半，但我们非常有信心，很难超越这个 ZK 年度攻击。

请注意，Nova 已经修复，并且该攻击附带了修复的安全证明。此外，Nova 是最简洁的 ZK 实现之一，并附有该领域写得最好的论文之一。如果说有什么收获的话，那就是这些系统很复杂，没有人能免受错误的影响。

但是 Nova 是什么？

Nova 是一种 增量可验证计算 (IVC) 方案。用外行的话来说，它允许你无限期地重复相同的计算，然后在你想为整个计算创建一个证明时停止。我们为什么要这样做？通常有两个原因。首先，它允许我们为长时间运行（或永无止境）的计算在不同的时间点创建证明（例如，在斐波那契数列的不同时间点创建证明，或在区块链之上添加区块）。其次，我们的 ZKP 系统目前通常非常有限，需要限制它们可以证明的程序的大小。将它们分解为可重复的部分（相信我，这是可能的），并使用这个 IVC 的东西似乎是可行的方法。

更正式地说，这篇新论文有一个出色的图表，可以直观地概括 IVC 的外观：

正如你所看到的，第一个状态是 z0，它被反复地作为输入提供给某个函数 F（在不同的步骤中使用一些其他的辅助输入 auxi），以最终返回 zi。Nova 或一般的 IVC 方案，允许我们创建整个计算的证明。

Nova 的核心在于一个 folding scheme

Nova 的特殊之处，以及许多遵循相同技术（例如 Protostar 和 Hypernova）的最新方案的特殊之处，在于 IVC 在生成任何实际的 ZKP 之前执行。这意味着这个递归过程通常非常便宜，因为你避免了在每个步骤中创建和验证实际的证明。

更重要的是，所有这些方案的构造方式都大致相同：

1. 它们首先构造一个 folding scheme（也被其他人称为 分割累加器）
2. 然后他们在 ZKP 电路中使用它来构造这个 IVC 的东西

为了理解攻击（或 IVC），没有必要理解 folding / 累加器，因此我们可以在本文中简化和抽象它。你应该这样理解它：一个 folding scheme 接受两个东西（我称之为累加器）并将它们简化为一个东西（一个新的累加器）。

如果你好奇，我们在 ZKP 系统中到处都这样做，而且通常以相同的方式进行：通过对这些东西进行随机线性组合。

Folding scheme 通常分为两个部分：证明者部分和验证者部分，其中验证者处理累加器的较短描述/摘要（通常使用承诺生成）。

将 folding 分为两个部分，允许大部分繁重的工作在电路外部完成（通过运行证明者部分），而电路仅验证工作是否已正确完成（通过运行验证者部分）。这也是为什么其他论文将此方案称为“分割累加器”方案的原因。

但是从现在开始，我们将使用简单的累加器，这些累加器不会分成证明者和验证者部分。如果我们只想理解攻击，这个细节并不重要。

从 folding scheme 到 IVC

一旦你有了累加或 folding scheme，你就可以将其与你的应用程序逻辑 F 组合到以下电路中：

fn circuit(state, aux, acc1, acc2) -> (new_state, new_acc) {
  new_state = F(state, aux);
  new_acc = FOLD(acc1, acc2);
}

本质上，电路相对简单：它只是通过调用函数 F 来推进状态（以及一些可以任意的辅助 aux 值，例如，用于在区块链中构造新区块的交易），然后将两个先前的累加器 folding 成一个。

现在，这是神奇的部分，它将使用所有这些来创建 IVC！

有一件事我没有告诉你，你可以查看该电路的执行，并将其解释为它自己的累加器（本质上是因为你可以对它的 witness 进行承诺）。这是一个“严格”的累加器，它不是通过 folding 任何东西获得的，而是直接来自执行电路。

无论如何，我们喜欢对累加器做什么？我们喜欢累加它们！

看一下这张图，它向你展示了如何使用这个新的洞察力，在每次评估 F 时将电路压缩到自身之上。

实际上，正如我之前所说，这个 summarize 函数是对电路的执行跟踪或 witness 的承诺。（在 protostar 中，它不仅仅是这样，它是包含挑战的证明的记录。）这是因为承诺将值向量压缩为单个椭圆曲线点（这就是为什么在实践中我们希望有一个在线路中的验证器，它只处理小的椭圆曲线点，而不是巨大的 witness 值向量）。

欠规范的曲线循环

Nova 看起来不像前面的图，因为那样效率太低了。相反，Nova 使用两个电路而不是一个，并且这两个电路是在两个不同的域上定义的。

这样做的原因可以追溯到 通过椭圆曲线循环实现可扩展的零知识（更正式地称为 BCTV14），它引入了曲线循环的概念。该论文说，处理电路的证明（即承诺）意味着你必须处理不同域中的值。

为什么会这样？ZKP 系统通常在椭圆曲线上实例化，其中椭圆曲线可以看作是 基域 上的一组点。我们称之为 Fq。因此，如果 P=(x,y) 是椭圆曲线上的一个点，我们有 x,y∈Fq。

我们通常寻找素数阶曲线，这意味着该曲线中存在一个素数 r 个点，这意味着曲线算术（和标量）存在于另一个称为 标量域 的域中。我们称之为 Fr。因此，例如，如果 a 和 b 是标量，则 (a⋅b)P=(a⋅bmodr)P。我们也有 rP=O，其中 O 表示曲线群的 0 点。

如果 ZKP 系统是在这样的曲线上实例化的（即 E(Fq)），那么电路必须用标量域 Fr 编写。这也意味着执行跟踪或 witness 将采用相同域 Fr 中的值，但是承诺这些值会将它们转换为另一个基域 Fq。（这是因为为了承诺，我们通常使用 Pedersen 承诺 并使用这些值作为标量来缩放椭圆曲线点。）

回到我们的递归 ZKP 系统。它们的问题在于，一旦它们承诺了 Fr 中的 witness 值（通过创建证明，或通过像 Nova 中那样“summarize”事物），这些值就会移动到不同的域 Fq（如上所述）。由于电路是用 Fr 编写的，因此它实际上是自然地设计为仅处理 Fr 中的算术。因此，处理 Fr 域上曲线的承诺会很好，但是在我们的例子中，我们现在被要求处理 Fq 域上曲线的承诺。

存在“模拟”非原生算术的方法，但是它们通常非常繁重，我们希望避免它们（我们真的希望电路的 folding 部分与我们的应用程序逻辑相比，占用最少的空间）。

BCTV14 提出的想法是找到两条椭圆曲线，其中一条曲线的基域是另一条曲线的标量域，反之亦然。然后，你在这两个曲线上实例化的两个证明系统之间交替进行，以便来自一个证明系统的承诺（在基域中）可以很容易地被另一个曲线的电路（在标量域中）处理，直到无穷。

现在，大多数递归 ZKP 系统使用由 Zcash 发现和指定的 Pasta 曲线。Pasta 曲线包含两条曲线：Pallas 和 Vesta，其中 Pallas 的标量域是 Vesta 的基域，而 Vesta 的标量域是 Pallas 的基域。

到目前为止，所有这些基于循环的递归 ZKP 系统都没有严格地指定它们对曲线循环的使用，这实际上在实践中非常复杂。正如我们将看到的，这是 Nova 令人着迷的漏洞的根源。

Nova 的曲线循环

在我看来，理解曲线循环如何工作是理解这些系统的主要难题。这是一个图表，说明了你如何在两个不同的曲线上实例化的两个不同的证明系统或电路之间交替进行。绿色表示你的值在一个域中，红色表示你的值在另一个域中。如果箭头突然改变颜色，你可以想象这些值被 summarize/承诺到椭圆曲线点中，因此更改了域。

正如你所看到的，这变得有点难以推理，我们得到了两种状态（一种绿色，一种红色）。并且，最后，我们还得到了一个累加器。

攻击 Nova 的新论文通过基本上将整个系统表示为系统的元组，从而漂亮地介绍了曲线循环的第一个严格的形式化，每个系统都有自己的应用程序逻辑 F:=(F1,F2)，每个系统都有自己的状态 zi:=(zi(1),zi(2))，每个系统都有自己的电路 R1CS:=(R1CS(1),R1CS(2))，等等。

验证电路之间的消息

这篇文章越来越长了，但是如果你已经读到现在，那么你可能从中获得了一些东西。很好 :) 下一个部分是你应该尝试理解的另一个重要概念：电路之间的消息未经身份验证，除非你对它们进行身份验证。

当我在上一个图中将绿色箭头从一个 circuit 1 指向下一个 circuit 1（传递新状态和新累加器）时，这些箭头实际上意味着“这些值是在第一个电路中计算的，可能是作为私有输出，并用作下一个电路的输入（可能再次是私有的）”。因此，它们是未约束的值，直到电路决定约束它们。

强制值不能更改的简单方法是，让电路在其公共输入中公开见证这些值的身份验证标签（这意味着，如果你使用不同的公共输入，电路将无法生成有效的证明）。

顺便说一句，在没有曲线循环的版本中也需要这样做。但是现在我们有了一个新问题：我们试图将此标签传递到下一个电路（在不同的曲线上实例化，它不关心我们的累加器或状态），而是传递到下下一个电路。

诀窍是将我们的公共输入分成两部分：

1. 一部分包含身份验证标签，下一个电路将忽略它，但会传递它
2. 一个来自前一个电路的不透明部分，我们将只传递它

我在下面的图中说明了这一点：

在论文中是什么样的？

这是同一张图，但带有 Nova 中使用的符号：

正如你所看到的，他们用一个大的“U”表示累加器，用一个小写的“u”表示这些直接来自对电路的执行跟踪进行承诺的严格累加器。

另请注意，早在 2014 年，BCTV14 就表示你可能不应该在第二个电路中包含任何应用程序逻辑，因为在两个不同的域中维护和拥有有用的应用程序逻辑将会很困难。因此，在实践中，实现往往看起来更像这样：

对 Nova 论文的攻击实际上有一个漂亮的页面列出了两个不同的关系（或电路）。我将在此处粘贴它，供想要查看本文此时看起来如何的好奇读者。请注意，他们使用不同的符号，因此如果不阅读本文，很难理解（你可能想要跳过此部分，以免过于分心）。

要理解攻击，你应该关注以下几点：

1. 请注意，关系的公共输入（或实例部分）被拆分为 (x0,x1)。
2. 请注意，两种关系都将 x1 计算为对重要值的哈希，包括新状态 zi+1 和新累加器 Ui+1。
3. 请注意，两种关系都将 x0 计算为上一个电路的身份验证标签 (𝕦upreviousother.x1)，就像它是一个不透明的值一样。
4. 最后，请注意，传递给我们的身份验证标签 (在 𝕦upreviousother.x0 中) 最终被用于检查电路的重要输入的真实性 (例如，输入状态 zi 和我们的输入累加器 Ui)。

漏洞

现在你已经有足够的知识来理解 Nova 实现中存在的问题。还要提醒自己，尽管实现已损坏，但 Nova 论文本身从未提供曲线循环规范。它只是抽象了这个问题，并将其留给实现者练习。因此，从某种意义上说，方案 Nova 仍然屹立不倒。

现在让我们看一下我们之前的图，但简化并仅查看其结尾。如果你没记错的话，结尾有两个累加器，以及一个直接来自第二个电路的最后一次执行的“严格”累加器。

Nova 的问题在于，它们包含了一个额外的和不必要的“严格”累加器（下图中的 ui−1(2)），并检查了它的一个身份验证标签（包含在其公共输入中），而不是另一个“严格”累加器（下图中的 ui(1)）中的正确标签。

修复非常简单，删除不必要的累加器，并确保验证最终“严格”累加器的公共输入中的两个标签。正如我经常说的那样，不必要的输入导致不必要的错误。

在我看来，另一个收获是，当规范很薄弱时，错误就会潜入。最后，在 Nova 的实现发布 2 年后，所实现方案的可靠公式浮出水面，并由于它，该错误也浮出水面。

• 原文链接： blog.zksecurity.xyz/post...
• 登链社区 AI 助手，为大家转译优秀英文文章，如有翻译不通的地方，还请包涵～