香槟超新星：增量可验证计算

介绍

在之前的文章中，我们一直在撰写关于证明系统和增量可验证计算的内容：

• Pinocchio 虚拟机：近乎实用的可验证计算
• 去中心化私有计算：ZEXE 和 VERI-ZEXE
• 增量可验证计算：NOVA

增量证明系统比传统的证明系统有一些优势：

• 它们不需要对循环迭代进行静态限制，这使得它们更适合具有动态流程控制的程序。
• 它们只需要极小的内存开销，因为证明者只需要与执行步骤所需的空间成比例的空间，而不需要存储整个计算轨迹。
• 它们非常适合证明生成的分配和并行化。

证明者可以运行程序，跟踪输入和输出变量以及状态变化，然后使用 CPU 或 GPU 并行生成计算的每个步骤的证明。更好的是，这些证明可以方便地聚合成一个单一的证明，验证者可以检查这个证明。

增量可验证计算 (IVC) 提供了一种证明机器执行完整性的方法。为了使用 ICV，我们需要设计一个通用电路，它可以执行任何机器支持的指令。在每个步骤中，我们都必须调用这个电路。这是不方便的，因为证明一个步骤的成本与通用电路的大小成正比，即使程序只执行一个成本低得多的受支持指令。解决这个缺点的一种方法是构建具有最小指令集的虚拟机，以限制通用电路的大小。

SuperNova 提供了一个基于虚拟机和程序（设计在该机器上运行）的密码学证明系统（包括证明者和验证者），满足以下属性：

• 简洁性：证明的大小和验证该证明的时间最多与程序的执行时间成多对数关系。
• 零知识：该证明不泄露任何信息，除了问题的正确执行。
• 方便的成本配置：证明程序一个步骤的成本与表示该指令的电路的大小成正比。
• 增量证明生成：证明者可以独立地为程序执行的每个步骤生成一个证明，然后将这些证明合并成一个单一的证明，而不会增加证明的大小。

SuperNova 利用 folding schemes (一种密码学原语，之前被 Nova 使用过)，使用 relaxed-committed R1CS，来实现非均匀 IVC。SuperNova 是 Nova 的一种概括，因为它支持具有丰富指令集的机器（Nova 仅限于一个指令）。在以下部分中，我们将分解 SuperNova 所需的不同组件，以及如何实现非均匀 IVC。

向量的承诺方案

向量的 承诺方案 是三个高效算法的集合：

• 参数生成，Gen(1λ)=ppGen(1λ)=pp：给定一个安全级别参数，λλ，该算法输出公共参数 pppp。
• 提交，commit(pp,x,r)=cmcommit(pp,x,r)=cm：给定公共参数、一个向量和一些随机数 rr，输出一个承诺 cmcm。
• 打开，open(pp,cm,x,r)=0,1open(pp,cm,x,r)=0,1：给定一个承诺、向量、随机数和公共参数，该算法验证给定的承诺是否对应于向量 xx。

承诺方案必须满足以下属性：

• 绑定：给定一个承诺 cmcm，不可能找到两个 x1x1, x2x2 使得 commit(pp,x1,r)=commit(pp,x2,r)commit(pp,x1,r)=commit(pp,x2,r)。简而言之，承诺将我们绑定到我们的原始值 xx。
• 隐藏：承诺不泄露 xx 中的任何信息。

以下两个属性在我们的上下文中很有用，并且被一些承诺方案满足，例如 Pedersen 的承诺方案：

• 加法同态：给定 x1x1, x2x2，如果 commit(pp,x1+x2,r1+r2)=commit(pp,x1,r1)+commit(pp,x2,r2)commit(pp,x1+x2,r1+r2)=commit(pp,x1,r1)+commit(pp,x2,r2)，则承诺是加法同态的。
• 简洁：承诺的大小比相应的向量小得多（例如，commit(pp,x,r)=O(log(x))commit(pp,x,r)=O(log⁡(x))）。

SuperNova 可以使用满足上述四个属性的任何承诺方案进行实例化，例如 Pedersen 的承诺方案、KZG 或 Dory。

非均匀 IVC (NIVC) 的计算模型

我们可以将程序看作是 n+1n+1 个非确定性、多项式时间可计算函数的集合，f1,f2,...,fn,ϕf1,f2,...,fn,ϕ，其中每个函数接收 kk 个输入和 kk 个输出变量；每个 fjfj 也可以接受非确定性输入。函数 ϕϕ 可以接受非确定性输入变量并输出一个元素 j=ϕ(z=(x,w))j=ϕ(z=(x,w))，选择其中一个 fifi。每个函数都表示为一个二次秩 1 约束系统 (R1CS)，这是一个 NP 完全问题。在 IVC 中，证明者在步骤 kk(k,x0,x)(k,x0,x) 处接受输入，并生成一个证明 ΠkΠk，该证明证明了对 witnesses (w0,w1,...,wk−1)(w0,w1,...,wk−1) 的认知，使得

xj+1=F(xj,wj)xj+1=F(xj,wj)

对于所有 j=0,1,...,kj=0,1,...,k，我们有 x=xk+1x=xk+1。换句话说，给定一个证明，表明前一步已正确计算，并且给定当前状态 xkxk，我们得到下一个状态 xk+1xk+1 和一个证明 Πk+1Πk+1，表明我们正确计算了步骤 kk。在 NIVC 设置中，ϕϕ 选择我们要使用的函数，

xj+1=Fϕ(xj,wj)(xj,wj)xj+1=Fϕ(xj,wj)(xj,wj)

在每个步骤中，SuperNova 将一个 R1CS 实例及其 witness，代表程序执行的最后一步，合并到一个运行实例中（它将两个 NN 大小的 NP 实例合并到一个 NN 大小的 NP 实例中）。证明者使用一个增强电路，其中包含一个验证者电路和对应于正在执行的函数 fjfj 的电路。验证者电路包括非交互式 folding scheme 和一个用于计算 ϕϕ 的电路。我们将增强函数表示为 f′jfj′。

folding scheme 的一个问题是，我们有多个指令，每个指令都有其 R1CS 表示。我们可以采用通用电路的路径，但这会让我们为许多廉价指令付出高昂的代价。在 Nova 中，我们避免了这个问题，因为我们只有一种类型的指令。为了处理多个指令，SuperNova 使用 nn 个运行实例 UiUi，其中 Ui(j)Ui(j) 证明了 f′jfj′ 的所有先前执行，直到步骤 i−1i−1。因此，检查所有 UiUi 相当于检查所有 i−1i−1 步骤。每个 f′jfj′ 接收 uiui 作为输入，对应于步骤 ii，并将其 folding 到相应的 UiUi 实例。我们可以将其视为查看我们要执行的函数，并使用与先前执行相关的函数执行实例 folding。通过这样做，我们仅在每次使用指令时才为其付费，但代价是保留更多运行实例并进行相应的更新。

对应于 f′jfj′ 的验证者电路执行以下步骤：

1. 检查 UiUi 和 pci=ϕ(xi−1,wi−1)pci=ϕ(xi−1,wi−1)（先前执行的函数的索引）是否包含在实例 uiui 的公共输出中。这强制要求前一步产生 UiUi 和 pcipci。
2. 运行 folding scheme 的验证者以 folding 一个实例并更新运行实例 Ui+1Ui+1。
3. 调用 ϕ(xi,wi)=pci+1ϕ(xi,wi)=pci+1 以获得要调用的以下函数的索引。

总结

IVC 是一种强大的密码学原语，它允许我们以增量方式证明计算的完整性。这种策略非常适合虚拟机执行和具有动态流程控制的通用程序。我们可以通过使用通用电路来实现这一点，但代价是每个指令都需要相当大的成本，无论它多么便宜。Nova 引入了 folding schemes，允许人们为单个指令实现 IVC。SuperNova 通过添加一个选择器函数 ϕϕ，将 Nova 推广到多个指令，该函数选择要在每个步骤执行的指令。为了支持多个指令，SuperNova 需要为每个函数的执行维护单独的记账。这种构造有许多令人兴奋的应用，因为我们可以实现 IVC，而无需昂贵的任意电路。

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