增量可验证计算：NOVA

介绍

当前的目标之一是以高效的方式实现增量可验证计算 (IVC)。这个密码学原语允许给定的参与方通过提供证明来展示给定计算机程序执行的完整性，证明每个步骤的结果都是正确的，并且所有之前的步骤都已在每个步骤中被适当执行。更准确地说，给定步骤 $N$，我们应用一个函数 $F_N$，它更新状态，将当前状态 $xN$ 和断言所有步骤 $1,2,...N-1$ 的正确执行的证明 $\pi{N-1}$ 作为输入，并输出新状态 $x{N+1}$ 及其正确执行的证明 $\pi{N+1}$。IVC 有许多应用，例如允许去中心化私有计算 (DPC)，你可以在其中将程序的执行委托给不受信任的第三方，简洁的区块链和可验证的延迟函数。

在之前的文章中，我们讨论了 DPC 的问题以及与其相关的两个协议，ZEXE 和 VERI-ZEXE。ZEXE 讨论了使用 proof-carrying data (PCD) 来验证任意计算的可能性，但这在计算上可能非常昂贵，因为在每个步骤中，我们都需要验证上一步的证明，为此我们需要：

1. 计算昂贵的双线性配对运算。
2. 将验证者的算术电路包含到我们的程序中，这不是一个轻量级的构造。

VERI-ZEXE 利用累积方案 (AS) 来提供 IVC。关键思想是将最终证明延迟到账本验证器（我们将在那里需要计算昂贵的配对运算）。在计算的每个步骤中，证明 $\pi_{N-1}$ 被“添加”到累加器中，然后进行部分验证：证明者检查累积的结果是否正确，但不计算配对运算。我们使用随机数来屏蔽累加器中的群元素，以确保零知识。

Nova 是一种新的协议，提出了另一种使用轻量级构造来实现 IVC 的方法。他们没有使用 zk-SNARKs，而是利用 折叠方案，累积 NP 实例而不是 SNARK。作者声称，与那些依赖于简洁的知识论证的方案相比，它产生了一个更弱、更简单、更有效的方案：

• 验证者电路的大小是恒定的，并且由两个群标量乘法运算主导。
• 证明者的工作由两个多重指数运算主导。

关键点是，折叠 充当了将证明验证推迟到最后一点的行为：为了检查给定函数应用 $N$ 次的正确性，我们只需要检查 $N$ 步骤的 折叠 证明。

折叠方案

折叠方案 是一个不受信任的证明者和验证者之间的协议。他们每个人都有一个大小相等的 $N$ 大小的 NP 实例，并且证明者另外拥有两个实例的 witness（回想一下，在 zk-SNARKs 的上下文中，我们将 witness 称为秘密输入/信息）。该协议使他们能够输出单个 $N$ 大小的 NP 实例，称为 折叠实例。折叠方案 保证 折叠实例 只有在原始实例有效时才能满足。如果验证者的工作和通信少于他没有参与 折叠方案 的情况，我们称该方案为非平凡的。折叠方案 将两个 NP 实例的可满足性简化为一个 NP 实例。一些展示这种二合一简化（或一些简化）的技术是 sum check 协议、批量证明和 bulletproofs。为了实现这样的构造，我们必须引入放松的（二次）秩 1 约束系统（relaxed R1CS）。

R1CS 和 relaxed R1CS

我们看到给定代码的正确执行可以表示为一个 电路满足性问题。电路相当于 R1CS，它是以下形式的方程组：

$Az \times Bz = Cz$

其中 $A, B, C$ 是稀疏矩阵，$\times$ 表示按分量乘积。它是二次的，因为每个方程中的每个变量最多具有 2 次（我们可以有 $z_1^2$ 但不能有 $z_1^4$）。即使 R1CS 是表达电路的一种便捷方式，但它们与 折叠方案 并不完全兼容。换句话说，在 R1CS 之上构建 折叠方案 并不容易。

Nova 的工作方式是进行增量计算，其中每个步骤都表示为一个 R1CS；约束系统通过验证电路来扩充，该电路必须断言上一步执行的正确性。但是，Nova 没有验证证明 $\pi_{N-1}$，而是将其视为 R1CS 的一个实例，并将其 折叠 到正在运行的 relaxed R1CS 中。

relaxed R1CS 引入了一个误差 $E$ 和一个标量 $u$，使得

$Az \times Bz = uCz + E$

请注意，任何 R1CS 也是 relaxed R1CS，其中 $E$ 是零向量，$u=1$。Relaxed R1CS 保留了它是 NP 完全的性质，这意味着我们可以将任何 NP 问题简化为它。

我们希望 折叠方案 将具有相同矩阵 $A, B, C$ 的两个 R1CS 实例合并为一个实例。每个 R1CS 都有其对应的实例-witness 对（即，公共和私有数据），$z_i = (w_i, x_i)$，并且我们想要创建一个新的 $z = (w, x)$，使用 $A, B, C$ 满足 R1CS 方程组，使得这也意味着每个 $z_i = (w_i, x_i)$ 都能做到。一种方法是让验证者选择一个随机数 $r$ 并执行以下转换：

$z = z_1 + rz_2$

此转换足以用于线性方程组，但由于 R1CS 是非线性的，因此我们无法应用此简单策略。如果我们将其替换为 R1CS

$Az_1 \times Bz_1 + r(Az_1 \times Bz_2 + Az_2 \times Bz_1) + r^2(A_2z_2 \times B_2z_2) = Cz_1 + rCz_2$

在 relaxed R1CS 中，误差项 $E$ 将吸收由引入线性组合产生的所有交叉项，并且 $u$ 将在右手边取额外的 $r$ 项。为此，

$u = u_1 + ru_2$

$E = E_1 + r(Az_1 \times Bz_2 + Az_2 \times Bz_1 - u_1Cz_2 - u_2Cz_1) + r^2E_2$

并且 $u, E$ 都被添加到实例-witness 对中。主要问题是证明者必须将 witness $w_1, w_2$ 发送给验证者，以便他可以计算 $E$。为此，我们将 $E$ 和 $w$ 都视为 witness，并使用多项式承诺方案隐藏它们。

多项式承诺方案

Nova 使用内积论证（IPA），它依赖于 Pedersen 承诺。这些都基于离散对数难以求解的假设，并且不需要可信设置。IPA 与其他流行的承诺方案（如 KZG）不同，后者依赖于椭圆曲线配对并且需要可信设置。关于证明大小和验证时间，KZG 更好，因为使用 Pedersen 承诺的 IPA 需要验证者的线性工作，并且证明大小取决于输入（KZG 的证明和验证时间是恒定的）。但是，我们可以在 Halo 等系统中解决这些弱点。

验证者的轻量级构造与多项式承诺方案相关。在这种情况下，最高的成本是两个 群标量乘法。Nova 的验证者电路大约有 20,000 个约束。

多项式承诺方案必须满足的基本属性是它是加法同态的：给定两个变量 $a, b$，我们说如果 $cm(a+b) = cm(a) + cm(b)$，则承诺是加法同态的，其中 $cm(x)$ 是 $x$ 的承诺。KZG 和 Pedersen 的承诺都满足此属性。使用此方法，验证者的通信和工作量都是恒定的。

另一个必要的属性是简洁性：承诺大小必须是开放大小的对数。例如，如果我们有一个 $n$ 次多项式，则其承诺最多应包含 $\log(n)$ 个元素。

提交 relaxed R1CS 的 折叠方案

提交 relaxed R1CS 的一个实例（即，公共变量）由 $x$（公共输入和输出变量）、$u$ 以及对 $E$ 的承诺 $cm(E)$ 和 $cm(w)$ 给出。我们可以将它们分组在元组 $(x, cm(w), cm(E), u)$ 中。如果 $cm(E) = Commit(E, r_E)$、$cm(w) = Commit(w, r_w)$ 并且 $Az \times Bz = uCz + E$，则该实例由 witness（秘密变量）$(E, r_E, w, r_w)$ 满足，其中 $z = (w, x, u)$。简单来说，如果公共变量 $cm(E)$ 和 $cm(w)$ 确实分别是使用随机数 $r_E, r_w$ 对私有变量 $E, w$ 的承诺，并且它们满足 relaxed R1CS 方程，则该 witness 满足该实例。

证明者和验证者可以访问两个 relaxed R1CS 实例 $(x_1, cm(w_1), cm(E_1), u_1)$ 和 $(x_2, cm(w_2), cm(E_2), u_2)$。此外，证明者具有 $(E1, r{E_1}, w1, r{w_1})$ 和 $(E2, r{E_2}, w2, r{w_2})$。该协议的进行方式如下：

1. 证明者计算 $T = Az_1 \times Bz_2 + Az_2 \times Bz_1 - u_1Cz_2 - u_2Cz_1$，并将其承诺 $cm(T) = Commit(T, r_T)$ 发送给验证者。

2. 验证者对随机挑战 $r$ 进行采样。

3. 证明者和验证者输出 折叠实例，

$cm(E) = cm(E_1) + r^2cm(E_2) + rcm(T)$

$u = u_1 + ru_2$

$cm(w) = cm(w_1) + rcm(w_2)$

$x = x_1 + rx_2$

4. 证明者更新 witness

$E = E_1 + rT + r^2E_2$

$rE = r{E_1} + rrT + r^2r{E_2}$

$w = w_1 + rw_2$

$rw = r{w1} + rr{w_2}$

可以使用 Fiat-Shamir 变换使该协议成为非交互式的。

使用此策略，我们可以通过在 折叠 后连续更新参数来实现 IVC。然后，证明者可以使用 zk-SNARK 来证明他知道提交的 relaxed R1CS 的有效 witness $(E, r_E, w, r_w)$ 的零知识，即不显示其值。

使用一些常见的 SNARK 的问题是，证明者必须证明他知道承诺等于给定值的有效向量。这意味着在 SNARK 的模型中对线性数量的群标量乘法进行编码。因此，我们需要一种新的构造来解决这个问题。

多项式交互式预言证明 (PIOP)

PIOP 是 Spartan 的修改版本。它基于 sum-check 协议和多线性多项式。对于给定的将位串映射到域元素的函数 $f:{0,1}^n \rightarrow F$，我们说如果 $p$ 是一个低阶多项式，并且对于 ${0,1}^n$ 中的所有 $x$ 满足 $f(x) = p(x)$，则 $p:{0,1}^n \rightarrow F$ 是 $f$ 的多项式扩展。如果 $p$ 是一个多线性多项式，使得 $f(x) = p(x)$，则我们称该扩展为多线性的。多线性多项式是多个变量的多项式，使得每个变量在每个项中的次数最多为 1。例如，$p(x_1, x_2, x_3) = x_1 + x_1x_2x_3 + x_2x_3$ 是多线性的（在每一项中，我们最多有 $x_i$），但 $p(x_1, x_2) = x_1^2x_2$ 不是。

R1CS 矩阵 $A, B, C$ 可以被认为是以自然的方式从 ${0,1}^m \times {0,1}^m$ 到某个有限域 $Fp$ 的函数。因此，我们也可以对它们进行多线性扩展 $A{ML}, B{ML}, C{ML}$，即 $2\log(m)$ 个多线性多项式。由于 R1CS 矩阵是稀疏的，因此对应的多线性多项式也是稀疏的（简单来说，它们几乎没有非零系数）。向量 $E$ 和 $w$ 也可以解释为多项式 $E{ML}$ 和 $w{ML}$。向量 $z = (w, x, u)$ 和 $y = (x, u)$ 也具有它们的多线性扩展 $z{ML}, y{ML}$。我们有以下函数，

$F(t) = (\sumy A{ML}(t, y)z_{ML}(y)) \times (\sumy B{ML}(t, y)z_{ML}(y)) - (u\sumy C{ML}(t, y)z(y) + E_{ML}(t))$

我们在这里对 ${0,1}^s$ 中 $y$ 的所有值求和。我们只需要检查以下恒等式是否对随机采样的 $\tau$ 成立

$\sum_x g(\tau, x)F(x) = 0$

对于 ${0,1}^s$ 中的 $x$， 对于 $x = y$，$g(x, y) = 1$，否则为零。 我们可以通过将 sum-check 协议应用于多项式 $p(t) = g(\tau, t)F(t)$ 来检查该等式。

优点

• 验证者电路是轻量级的，只有 20,000 多个约束。
• 它不需要执行 FFT，因此不需要特殊的椭圆曲线。唯一的条件是它足够安全（即，离散对数问题必须难以解决）。
• 验证不是基于椭圆曲线配对的，因此不需要昂贵的操作和配对友好的曲线。

总结

Nova 是一种新的协议，用于实现基于称为 折叠方案 的新密码学原语的增量可验证计算。关键思想是将给定 NP 语句的两个实例合并为一个实例。为了能够做到这一点，我们必须更改 R1CS 以包括一个误差项 $E$ 和一个标量 $u$，以获得一个 relaxed R1CS，我们可以在其上构建一个高效的 折叠方案。我们还需要加法同态多项式承诺方案，例如 Pedersen 承诺。产生的构造具有一个小的验证者电路（在 R1CS 中大约有 20,000 个约束），从而获得快速的证明生成和验证。这在公共账本、可验证延迟函数和证明聚合方面有许多应用。

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