Nova

<!--StartFragment-->

• 原文：Incrementally verifiable computation: NOVA
• 作者：Not a Monad Tutorial
• 译者：Kurt Pan

当前的目标之一是以高效的方式实现增量可验证计算（IVC）。 该密码学原语，通过提供每一步的结果都是正确的并且所有先前步的结果都已在每步中正确执行过的证明，允许给定方来展示给定计算机程序执行的完整性。更精确地，给定步骤$N$，我们应用更新状态的函数$ F_N$，将当前状态 $xN$ 和断言所有第$1,2,…N−1$步的正确执行证明$π{N−1}$， 输出新状态 $x{N+1}$ 以及一个正确执行的证明$π{N+1}$。

IVC 有很多应用，例如去中心化隐私计算 (DPC，可以将程序的执行代理给不受信任的第三方）、简洁区块链以及可验证延迟函数（VDF）。

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

1. 计算昂贵的双线性配对操作。
2. 将验证者的算术电路包含到程序中，这并非一个轻量的结构。

VERI-ZEXE 使用累加方案 (AS) 来实现 IVC。关键思想是推迟最终的证明直到账本验证者（将需要计算昂贵的配对操作）。 在计算的每一步中，证明$π_{N−1}$被“添加”到累加器，然后对其进行部分验证：证明者检查累加结果是否正确，但不计算配对操作。 使用随机化因子掩盖累加器中的群元素以保证零知识性。

Nova是一种新协议，提出了一种实现 IVC 的轻量级替代构造。 不用zk-SNARKs，而是用了折叠方案，来对NP实例而不是SNARKs进行累积。 论文作者声称，与那些依赖简洁知识论证的方案相比，可以做到一个更弱、更简单、更高效的方案：

• 验证者电路大小为常数，主要为两个群标量乘法。
• 证明者的工作主要是两个多重指数。

关键点在于折叠起到了将证明验证推迟到最后时刻的作用：想要检验正确应用了给定函数$N$次，只需要检验这$N$步的折叠证明即可。

折叠方案

折叠方案是一个不受信任的证明者和验证者之间的协议。 二者都有两个大小相同（为$N$）的 NP 实例，此外，证明者还拥有这两个实例的见证（在 zk-SNARKs 中，我们称见证为秘密输入/信息）。 该协议输出单个 $N$ 大小的 NP 实例，称为折叠实例。 折叠方案保证折叠实例仅在原始实例有效时才可满足。 如果验证者的计算和通信量相比于其不参与折叠方案时更少，我们称该方案是非平凡的。

折叠方案将两个 NP 实例的可满足性归约到仅一个 NP 实例。 一些展示这种二到一归约（或某种归约）的技术包括和校验协议、批量证明和Bulletproofs。

为了实现这样的构造，我们必须引入松弛（二次）秩一约束系统（松弛R1CS）。

R1CS和松弛R1CS

我们已经知道给定代码的正确执行可以表示为电路可满足性问题，而电路和R1CS是等价的。

R1CS 为下述形式的方程组： $$ A_z×B_z=C_z \qquad\qquad\qquad(1) $$

其中$A,B,C$是稀疏矩阵，×为逐项积。R1CS是二次的，因为方程中的每个变量的次数最高为2（可以有$z^2_1$，但不会有$z^4_1$）。R1CS虽然是一种表示电路的方便方式，但和折叠方案并不完全兼容；换句话说，在R1CS之上构造折叠方案并不容易。

Nova 通过进行增量计算来工作，其中每一步都表示为 R1CS； 约束系统中增加了验证电路，它必须断言上一步执行的正确性。然而，Nova 并没有验证证明 $π_{N−1}$，而是将其视为一个 R1CS 实例，并将其折叠成一个运行中的松弛R1CS。

松弛R1CS引入了错误项$E$和标量$u$，使得： $$ Az×Bz=uCz+E \qquad\,\,(2) $$

R1CS也是松弛R1CS，只需将$E$设置成零向量且$u=1$即可。松弛R1CS保留了NP完全的性质，可以将任意 NP 问题归约过去。

我们希望折叠方案将具有相同矩阵 $A、B、C$ 的两个 R1CS 实例合并为一个。 每个R1CS都有其对应的实例-见证对（即公开和私有数据），$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 \qquad\qquad\qquad\quad(3) $$ 这种变换对于线性方程组是足够的，但由于R1CS是非线性的，不能应用这种简单的策略。 如果我们将其替换为松弛R1CS有： $Az_1×Bz_1+r(Az_1×Bz_2+Az_2×Bz_1)+r^2(A_2z_2×B_2z_2)=Cz_1+rCz_2$

在松弛R1CS中，误差项$E$会吸收由引入线性组合而产生的所有交叉项，$u$则会处理右侧额外的$r$项。 为此有， $$ u=u_1+ru_2 \qquad\qquad\qquad\quad(4) $$ $$ E=E_1+r(Az_1×Bz_2+Az_2×Bz_1−u_1Cz_2−u_2Cz_1)+r_2E_2 \qquad\,\,(5) $$ 且$u,E$ 都被添加到实例-见证对中。 这里存在的主要的问题是证明者必须将见证 $w1,w2$ 发送给验证者，以便他可以计算 $E$。 为解决此问题，我们将$ E $和 $w$ 都视为见证，并使用多项式承诺方案隐藏它们。

多项式承诺方案

Nova使用一个依赖Pedersen承诺的内积证明（IPA），基于离散对数困难假设，且无需可信设置。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)$ 个元素。

对承诺的松弛R1CS的折叠方案

一个对承诺的松弛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×Bz=uCz+E$，其中$z=(w,x,u)$，则称见证（私有变量）$(E,r_E,w,r_w)$满足实例。 简而言之，如果公开变量$cm(E)$ 和 $cm(w)$确实是私有变量 $E,w$分别使用随机数$r_E,r_w$的承诺，且它们满足松弛R1CS方程，则称见证满足了实例。

证明者和验证者可访问两个松弛R1CS实例，$(x_1, cm(w_1),cm(E_1),u_1) $和 $(x_2,cm(w_2),cm(E_2),u_2)$。证明者还额外有$(E1,r{E1},w1,r{w1})$ 和 $(E2,r{E2},w2,r{w2})$。

协议流程如下：

1. 证明者计算$ T=Az_1×Bz_2+Az_2×Bz_1−u_1Cz_2−u_2Cz_1$ 并发送其承诺， $cm(T)=Commit(T,r_T)$
2. 验证者采样随机挑战$r$
3. 证明者和验证者输出折叠实例， $$ cm(E)=cm(E_1)+r^2 cm(E_2)+r cm(T) $$ $$ u=u_1+ru_2 $$ $$ cm(w)=cm(w_1)+r cm(w_2) $$ $$ x=x_1+rx_2 $$
4. 证明者更新见证，

$$ E=E_1+rT+r^2 $$ $$ E_2rE=r{E1}+rrT+r^2r{E2} $$ $$ w=w_1+rw_2 $$ $$ rw=r{w1}+rr_{w2} $$ 通过使用 Fiat-Shamir 转换，可以使协议成为非交互式的。

使用这种策略，我们可以通过在折叠后连续更新参数来实现 IVC。 之后，证明者可以使用 zk-SNARK 以零知识（即不泄漏值）的方式表明他知道对承诺的松弛R1CS的有效见证$ (E,r_E,w,r_w)$ 。

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

多项式交互式预言证明 （PIOP)[**]()

所用的PIOP是Spartan的一个修改版本，基于和校验协议和多线性多项式。

对于将比特串映射到域元素的给定函数$f:0,1^n→\mathbb F$，我们说$p:0,1^n→\mathbb F$是$f$的一个多项式扩展，如果$p$是一个对于所有$x∈0,1^n$，满足$f(x)=p(x)$的低次多项式。 我们称该扩展为多线性的，如果$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^2_1x_2$不是。

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

$$F(t)=(\sum\limitsyA{ML}(t,y)z_{ML}(y))×(∑\limitsyB{ML}(t,y)z_{ML}(y))−(u∑\limitsyC{ML}(t,y)z(y)+E_{ML}(t)) \qquad(6)$$

其中我们对$0,1^s$中的所有值$y$进行求和。

我们只需对于$x∈0,1^s$ 检验对于随机采样的$τ$下述等式是否成立： $\qquad\qquad\qquad\qquad\qquad\qquad\qquad\qquad\qquad\qquad∑\limits_xg(τ,x)F(x)=0\qquad\qquad\qquad\qquad\qquad(7)$

其中对$x=y，g(x,y)=1$，否则等于0。

我们可以通过对多项式$p(t)=g(τ,t)F(t)$应用和校验协议来检验相等性。

优势

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

总结

Nova 是基于一种称为折叠方案的新密码原语实现增量可验证计算的新协议。关键思想是将给定NP语句的两个实例合并为一个。 为此，必须对R1CS进行改变，添加错误项E和标量u以得到松弛R1CS。基于松弛R1CS可以构造高效的折叠方案。还需要加法同态多项式承诺方案，例如 Pedersen 承诺。 由此产生的构造验证者电路很小（R1CS 中约有 20,000 个约束），可实现快速证明生成和验证。 这在公开账本、可验证延迟函数和证明聚合方面都有很多应用。

本文首发于：https://cryptography.land/2023/03/05/nova