Nova: Recursive Zero-Knowledge Arguments from Folding Schemes
诺瓦：折叠方案中的递归零知识论证

Abstract摘要

We introduce a new approach to realize incrementally verifiable computation (IVC), in which the prover recursively proves the correct execution of incremental computations of the form $y=F^{(\ell )}(x)$, where F is a (potentially non-deterministic) computation, x is the input, y is the output, and $\ell >0$. Unlike prior approaches to realize IVC, our approach avoids succinct non-interactive arguments of knowledge (SNARKs) entirely and arguments of knowledge in general. Instead, we introduce and employ folding schemes, a weaker, simpler, and more efficiently-realizable primitive, which reduces the task of checking two instances in some relation to the task of checking a single instance. We construct a folding scheme for a characterization of NP and show that it implies an IVC scheme with improved efficiency characteristics: (1) the “recursion overhead” (i.e., the number of steps that the prover proves in addition to proving the execution of F) is a constant and it is dominated by two group scalar multiplications expressed as a circuit (this is the smallest recursion overhead in the literature), and (2) the prover’s work at each step is dominated by two multiexponentiations of size O(|F|), providing the fastest prover in the literature. The size of a proof is O(|F|) group elements, but we show that using a variant of an existing zkSNARK, the prover can prove the knowledge of a valid proof succinctly and in zero-knowledge with $O(\log |F|)$ group elements. Finally, our approach neither requires a trusted setup nor FFTs, so it can be instantiated efficiently with any cycles of elliptic curves where DLOG is hard.
我们提出了一种实现增量可验证计算（IVC）的新方法，其中证明者递归地证明增量计算的正确执行，计算形式为 $y=F^{(\ell )}(x)$ ，其中 F 是一个（可能非确定性的）计算，x 是输入，y 是输出，以及 $\ell >0$ 。与实现 IVC 的先前方法不同，我们的方法完全避免了简洁非交互式知识论证（SNARKs）以及一般的知识论证。相反，我们引入并采用折叠方案，这是一种更弱、更简单且更高效实现的原始方案，它将检查两个实例在某些关系中的任务简化为检查单个实例的任务。 我们为 NP 的特征描述构建了一种折叠方案，并表明它意味着具有改进效率特性的 IVC 方案：（1）“递归开销”（即证明者在证明 F 的执行之外还需证明的步骤数）是常数，并且它由两个表示为电路的群标量乘法主导（这是文献中最小的递归开销），（2）在每个步骤中，证明者的工作主要由两个大小为 O(|F|)的多指数运算主导，提供了文献中最快的证明者。证明的大小为 O(|F|)个群元素，但我们表明，使用现有 zkSNARK 的一个变体，证明者可以简洁且在零知识下证明有效证明的知识，使用 $O(\log |F|)$ 个群元素。最后，我们的方法既不需要可信设置也不需要 FFT，因此可以在任何 DLOG 困难的椭圆曲线周期中高效实例化。

1 Introduction1 简介

We revisit the problem of realizing incrementally-verifiable computation (IVC) [43]: a cryptographic primitive that enables producing proofs of correct execution of “long running” computations such that a verifier can efficiently verify the correct execution of any prefix of the computation. IVC enables a wide variety of applications including verifiable delay functions [9, 45], succinct blockchains [13, 31], and incrementally-verifiable versions of verifiable state machines [33, 39].
我们重新审视实现增量可验证计算（IVC）[43]的问题：这是一种密码学原语，它能够生成“长时间运行”的计算的正确执行证明，使得验证者可以高效地验证计算任何前缀的正确执行。IVC 能够支持包括可验证延迟函数[9, 45]、简洁区块链[13, 31]以及可验证状态机的增量可验证版本[33, 39]在内的广泛应用。

A well-known approach to construct IVC is to use succinct non-interactive arguments of knowledge (SNARKs) for $\mathsf{N}\mathsf{P}$ [23, 24, 29, 36]: at each incremental step i, the prover produces a SNARK proving that it has applied F correctly to the output of step $i-1$ and that the SNARK verifier represented as a circuit has accepted the SNARK from step $i-1$  [6, 8]. However, it is well-known that this approach is impractical [6, 19]. Alternatively, one can use SNARKs without trusted setup [17, 21, 38, 41] but their verifiers are more expensive than those of SNARKs with trusted setup, both asymptotically and concretely. Recent works [10, 12, 15, 16] aim to address the inefficiency of SNARK-based IVC, with an innovative approach: at each step, the verifier circuit “defers” expensive steps in verifying a SNARK for $\mathsf{N}\mathsf{P}$ instances (e.g., verifying polynomial evaluation proofs) by accumulating those steps into a single instance that is later checked efficiently. However, these works still require the prover to produce a SNARK at each step and the verifier circuit to partially verify that SNARK.
一种构建 IVC 的知名方法是使用简洁的非交互式知识论证（SNARKs）[23, 24, 29, 36]：在每个增量步骤 i 中，证明者生成一个 SNARK，证明它已正确地将 F 应用于步骤 $i-1$ 的输出，并且作为电路表示的 SNARK 验证器已接受步骤 $i-1$ [6, 8]的 SNARK。然而，众所周知，这种方法不切实际[6, 19]。另一种方法是使用无需信任设置的 SNARKs[17, 21, 38, 41]，但它们的验证器比具有信任设置的 SNARKs 更昂贵，无论是从理论上还是从实际应用上。最近的研究[10, 12, 15, 16]旨在解决基于 SNARK 的 IVC 的低效问题，采用了一种创新的方法：在每个步骤中，验证器电路“推迟”验证 SNARK 实例（例如，验证多项式评估证明）中的昂贵步骤，将这些步骤累积到一个单独的实例中，稍后高效地检查。然而，这些研究仍然要求证明者在每个步骤中生成一个 SNARK，并且验证器电路需要部分验证该 SNARK。

We introduce a new approach that avoids SNARKs (and more generally arguments of knowledge) entirely and relies purely on deferral to realize IVC. In a nutshell, instead of accumulating expensive steps of verifying a SNARK for $\mathsf{N}\mathsf{P}$ instances, the verifier circuit in our approach accumulates the $\mathsf{N}\mathsf{P}$ instances themselves. We formalize this technique as a new and minimal primitive, which we refer to as a folding scheme. A folding scheme is weaker, simpler, and far more efficient compared to arguments of knowledge including SNARKs. Indeed, realizing IVC via folding schemes results in improved efficiency over prior work (Fig. 3): (1) the verifier circuit is constant-sized and its size is dominated by two group scalar multiplications; this is the smallest verifier circuit in the literature (in the context of recursive proof composition); and (2) the prover’s work at each step is dominated by two multiexponentiations of size O(|F|), providing the fastest prover in the literature, both asymptotically and concretely. Section 1.4 provides a detailed comparison between our approach and prior work.
我们介绍了一种全新的方法，完全避免了 SNARKs（以及更一般的知识论证）并纯粹依赖于延迟来实现 IVC。简而言之，我们方法中的验证电路不是累积验证 SNARK 的昂贵步骤，而是累积 $\mathsf{N}\mathsf{P}$ 实例本身。我们将这种技术形式化为一种新的最小原始方法，我们称之为折叠方案。与包括 SNARKs 在内的知识论证相比，折叠方案更弱、更简单，且效率更高。确实，通过折叠方案实现 IVC 比以往的工作效率更高（图 3）：（1）验证电路大小恒定，其大小由两个群标量乘法主导；这是文献中最小的验证电路（在递归证明组合的背景下）；（2）在每个步骤中，证明者的工作主要由两个大小为 O(|F|)的多指数运算主导，提供了文献中最快的证明者，无论是从理论上还是从实际角度来看。第 1.4 节提供了我们方法与以往工作的详细比较。

1.1 Folding Schemes1.1 折叠方案

A folding scheme is defined with respect to an $\mathsf{N}\mathsf{P}$ relation, and it is a protocol between an untrusted prover and a verifier. Both entities hold two N-sized $\mathsf{N}\mathsf{P}$ instances, and the prover in addition holds purported witnesses for both instances. The protocol enables the prover and the verifier to output a single N-sized $\mathsf{N}\mathsf{P}$ instance, which we refer to as a folded instance. Furthermore, the prover privately outputs a purported witness to the folded instance using purported witnesses for the original instances. Informally, a folding scheme guarantees that the folded instance is satisfiable only if the original instances are satisfiable. A folding scheme is said to be non-trivial if the verifier’s costs and the communication are lower in the case where the verifier participates in the folding scheme and then verifies a purported $\mathsf{N}\mathsf{P}$ witness for the folded instance than the case where the verifier verifies purported $\mathsf{N}\mathsf{P}$ witnesses for each of the original instances.
折叠方案是根据 $\mathsf{N}\mathsf{P}$ 关系定义的，它是一个不信任的证明者和验证者之间的协议。双方持有两个 N 大小的 $\mathsf{N}\mathsf{P}$ 实例，证明者除此之外还持有这两个实例的所谓证据。该协议使证明者和验证者能够输出一个单一的 N 大小的 $\mathsf{N}\mathsf{P}$ 实例，我们称之为折叠实例。此外，证明者私下使用原始实例的所谓证据输出折叠实例的所谓证据。非正式地说，折叠方案保证只有当原始实例可满足时，折叠实例才是可满足的。如果验证者在参与折叠方案并验证折叠实例的所谓 $\mathsf{N}\mathsf{P}$ 证据的情况下，验证者的成本和通信量低于验证每个原始实例的所谓 $\mathsf{N}\mathsf{P}$ 证据的情况下，则称折叠方案为非平凡的。

Several existing techniques exhibit the two-to-one reduction pattern of folding schemes. Examples include the sumcheck protocol [35] and the split-and-fold techniques in inner product arguments [11]. [30, App. A] provides further details.
现有技术中，一些技术表现出折叠方案的二对一减少模式。例如，求和校验协议[35]和内积论证中的分割折叠技术[11]。[30, 附录 A]提供了更多细节。

Remark 1 (Folding Schemes vs. SNARKs)
备注 1（折叠方案与 SNARKs）

SNARKs for $\mathsf{N}\mathsf{P}$ [7, 23, 24, 29, 36] trivially imply a folding scheme for $\mathsf{N}\mathsf{P}$: given two $\mathsf{N}\mathsf{P}$ instances $u_1$ and $u_2$ and the corresponding witnesses, the prover proves $u_1$ by producing a SNARK. The verifier checks that SNARK and then sets $u_2$ to be the folded instance. However, we construct a folding scheme for $\mathsf{N}\mathsf{P}$ without relying on SNARKs (or more generally arguments of knowledge). Specifically, our folding scheme is weaker than any argument of knowledge (succinct or otherwise) because it merely reduces the satisfiability of two $\mathsf{N}\mathsf{P}$ instances to the satisfiability of a single $\mathsf{N}\mathsf{P}$ instance.¹
SNARKs for $\mathsf{N}\mathsf{P}$ [ 7, 23, 24, 29, 36] trivially imply a folding scheme for $\mathsf{N}\mathsf{P}$ : given two $\mathsf{N}\mathsf{P}$ instances $u_1$ and $u_2$ and the corresponding witnesses, the prover proves $u_1$ by producing a SNARK. The verifier checks that SNARK and then sets $u_2$ to be the folded instance. However, we construct a folding scheme for $\mathsf{N}\mathsf{P}$ without relying on SNARKs (or more generally arguments of knowledge). Specifically, our folding scheme is weaker than any argument of knowledge (succinct or otherwise) because it merely reduces the satisfiability of two $\mathsf{N}\mathsf{P}$ instances to the satisfiability of a single $\mathsf{N}\mathsf{P}$ instance.

To design a folding scheme for $\mathsf{N}\mathsf{P}$, we start with a popular $\mathsf{N}\mathsf{P}$-complete language that generalizes arithmetic circuit satisfiability: R1CS (Definition 10). As we illustrate later, it is difficult to devise a folding scheme for R1CS. To address this, we introduce a variant of R1CS, called relaxed R1CS, which, like R1CS, not only characterizes $\mathsf{N}\mathsf{P}$, but, unlike R1CS, can support a folding scheme. The following theorem captures the cryptographic and efficiency characteristics of our folding scheme for relaxed R1CS.
为了设计一个针对 $\mathsf{N}\mathsf{P}$ 的折叠方案，我们从一个流行的 $\mathsf{N}\mathsf{P}$ -完备语言开始，该语言泛化算术电路可满足性：R1CS（定义 10）。正如我们稍后所展示的，为 R1CS 设计折叠方案是困难的。为了解决这个问题，我们引入了 R1CS 的一个变体，称为放宽的 R1CS，它不仅像 R1CS 一样表征 $\mathsf{N}\mathsf{P}$ ，而且与 R1CS 不同，它可以支持折叠方案。以下定理捕捉了我们为放宽的 R1CS 设计的折叠方案的加密和效率特性。

Theorem 1定理 1

There exists a constant-round, public-coin, zero-knowledge folding scheme for relaxed R1CS where for N-sized relaxed R1CS instances over a finite field $\mathbb{F}$ with the same “structure” (i.e., R1CS coefficient matrices), the prover’s work is $O_{\lambda }(N)$, and the verifier’s work and the communication are both $O_{\lambda }(1)$, assuming the existence of any additively-homomorphic commitment scheme that provides $O_{\lambda }(1)$-sized commitments to N-sized vectors over $\mathbb{F}$ (e.g., Pedersen’s commitments), where $\lambda$ is the security parameter.
存在一个常数轮、公共币、零知识折叠方案，适用于宽松的 R1CS，其中对于大小为 N 的宽松 R1CS 实例，在有限域 $\mathbb{F}$ 上具有相同的“结构”（即 R1CS 系数矩阵），证明者的工作为 $O_{\lambda }(N)$ ，验证者的工作和通信均为 $O_{\lambda }(1)$ ，假设存在任何提供 N 大小向量的 $O_{\lambda }(1)$ -大小承诺的加法同态承诺方案（例如，Pedersen 的承诺），其中 $\lambda$ 是安全参数。

Because our folding scheme is public coin, it can be made non-interactive in the random oracle model using the Fiat-Shamir transform [22], and be instantiated (heuristically) in the standard model using a concrete hash function. We rely on such a non-interactive folding scheme to construct IVC.
因为我们的折叠方案是公开币，它可以在随机预言机模型中使用 Fiat-Shamir 变换[22]进行非交互式处理，并且可以使用具体的哈希函数在标准模型中实例化（启发式）。我们依赖于这种非交互式折叠方案来构建 IVC。

1.2 IVC from Non-interactive Folding Schemes
1.2 非交互折叠方案中的 1.2 IVC

We show how to realize IVC using a non-interactive version of our folding scheme for relaxed R1CS. We refer to our construction as Nova.
我们展示了如何使用我们为宽松 R1CS 设计的非交互式折叠方案来实现 IVC。我们将我们的构造称为 Nova。

Recall that an IVC is an argument of knowledge [29, 36]² for incremental computations of the form $y=F^{(\ell )}(x)$, where F is a (possibly non-deterministic) computation, $\ell >0$, x is a public input, and y is the public output. At each incremental step, the IVC prover produces a proof that the step was computed correctly and it has verified a proof for the prior step. In other words, at each incremental step, the IVC prover produces a proof of satisfiability for an augmented circuit that augments the circuit for F with a “verifier circuit” that verifies the proof of the prior step. Recursively, the final proof proves the correctness of the entire incremental computation. A key aspect of IVC is that neither the IVC verifier’s work nor the IVC proof size depends on the number of steps in the incremental computation. In particular, the IVC verifier only verifies the proof produced at the last step of the incremental computation.
回忆一下，IVC（增量验证计算）是知识的一个论点[29, 36] ² ，用于形式为 $y=F^{(\ell )}(x)$ 的增量计算，其中 F 是（可能非确定性的）计算 $\ell >0$ ，x 是公开输入，y 是公开输出。在每一步增量计算中，IVC 证明者生成一个证明，证明该步骤被正确计算，并且它已验证了前一步的证明。换句话说，在每一步增量计算中，IVC 证明者生成一个增强电路的满足性证明，该电路通过添加一个“验证电路”来增强 F 的电路，以验证前一步的证明。递归地，最终证明证明了整个增量计算的正确性。IVC 的一个关键方面是，IVC 验证者的工作量和 IVC 证明的大小都不依赖于增量计算中的步骤数量。特别是，IVC 验证者只验证增量计算的最后一步产生的证明。

In Nova, we consider incremental computations, where each step of the incremental computation is expressed with R1CS (all the steps in the incremental computation share the same R1CS coefficient matrices). At step i of the incremental computation, as in other approaches to IVC, Nova’s prover proves that the step i was computed correctly. Furthermore, at step i, instead of verifying a proof for step $i-1$ (as in traditional approaches to IVC), Nova’s approach treats the computation at step $i-1$ as an R1CS instance and folds that into a running relaxed R1CS instance. Specifically, at each step, Nova’s prover proves that it has performed the step’s computation and has folded its prior step represented as an R1CS instance into a running relaxed R1CS instance. In other words, the circuit satisfiability instance that the prover proves at each incremental step computes a step of the incremental computation and includes a circuit for the computation of the verifier in the non-interactive folding scheme for relaxed R1CS.
在 Nova 中，我们考虑增量计算，其中增量计算的每一步都使用 R1CS（增量计算中的所有步骤共享相同的 R1CS 系数矩阵）。在增量计算的步骤 i 中，正如其他 IVC 方法一样，Nova 的证明者证明步骤 i 被正确计算。此外，在步骤 i 中，Nova 的方法不是验证步骤 $i-1$ 的证明（如传统 IVC 方法），而是将步骤 $i-1$ 的计算视为 R1CS 实例，并将其折叠到一个运行中的放松 R1CS 实例中。具体来说，在每一步，Nova 的证明者证明它已经执行了该步骤的计算，并将之前步骤表示为 R1CS 实例的内容折叠到一个运行中的放松 R1CS 实例中。换句话说，证明者在每个增量步骤中证明的电路可满足性实例计算了增量计算的一个步骤，并包括一个用于非交互式折叠方案中放松 R1CS 的验证器计算电路。

A distinctive aspect of Nova’s approach to IVC is that it achieves the smallest “verifier circuit” in the literature. Since the verifier’s costs in the non-interactive version of the folding scheme for relaxed R1CS is $O_{\lambda }(1)$, the size of the computation that Nova’s prover proves at each incremental step is $\approx$ $|F|$, assuming N-sized vectors are committed with an $O_{\lambda }(1)$-sized commitments (e.g., Pedersen’s commitments). In particular, the verifier circuit in Nova is constant-sized and its size is dominated by two group scalar multiplications. Furthermore, Nova’s prover’s work at each step is dominated by two multiexponentiations of size $\approx$ $|F|$. Note that Nova’s prover does not perform any FFTs, so it can be instantiated efficiently using any cycles of elliptic curves where DLOG is hard.
诺瓦对 IVC 的方法的一个显著特点是实现了文献中最小的“验证器电路”。由于在非交互式折叠方案中，验证器的成本为 $O_{\lambda }(1)$ ，因此诺瓦的证明者在每个增量步骤中证明的计算大小为 $\approx$ $|F|$ ，假设使用 N 大小的向量与 $O_{\lambda }(1)$ 大小的承诺（例如，Pedersen 的承诺）。特别是，诺瓦中的验证器电路大小恒定，其大小主要由两个群标量乘法决定。此外，诺瓦的证明者在每个步骤的工作主要由两个大小为 $\approx$ $|F|$ 的多指数运算决定。请注意，诺瓦的证明者不执行任何 FFT，因此可以使用任何 DLOG 困难的椭圆曲线周期有效地实例化。

With the description thus far, the size of an IVC proof (which is a purported witness for the running relaxed R1CS instance) is $O_{\lambda }(|F|)$. Instead of sending such a proof to a verifier, at any point in the incremental computation, Nova’s prover can prove the knowledge of a satisfying witness to the running relaxed R1CS instance in zero-knowledge with an $O_{\lambda }(\log |F|)$-sized succinct proof using a zkSNARK that we design by adapting Spartan [38]. The following theorem summarizes our key result.
根据目前的描述，IVC 证明（作为运行中的放松 R1CS 实例的所谓见证）的大小为 $O_{\lambda }(|F|)$ 。在增量计算的任何时刻，Nova 的证明者可以用我们通过适配 Spartan [38]设计的 zkSNARK，以 $O_{\lambda }(\log |F|)$ 大小的简洁证明，在零知识中证明对运行中的放松 R1CS 实例的满足见证的知识，而不是将此类证明发送给验证者。以下定理总结了我们的关键结果。

Theorem 2定理 2

For any incremental function where each step of the incremental function applies a (non-deterministic) function F, there exists an IVC scheme with the following efficiency characteristics, assuming N-sized vectors are committed with an $O_{\lambda }(1)$-sized commitments.
对于任何增量函数，其中增量函数的每一步都应用一个（非确定性）函数 F，存在一个具有以下效率特性的 IVC 方案，假设使用 N 大小的向量与 $O_{\lambda }(1)$ 大小的承诺。

• IVC proof sizes are O(|F|) and the verifier’s work to verify them is $O_{\lambda }(|F|)$. The prover’s work at each incremental step is $\approx$ $|F|$. Specifically, the prover’s work at each step is dominated by two multiexponentiations of size $\approx$ $|F|$.
  IVC 证明大小为 O(|F|)，验证者验证它们的工作量为 $O_{\lambda }(|F|)$ 。在每个增量步骤中，证明者的工作为 $\approx$ $|F|$ 。具体来说，证明者在每一步的工作主要由两个大小为 $\approx$ $|F|$ 的多指数运算主导。

• Succinct zero-knowledge proofs of valid IVC proofs are size $O_{\lambda }(\log |F|)$, and the verifier’s work to verify them is either $O_{\lambda }(\log |F|)$ or $O_{\lambda }(|F|)$ depending on the commitment scheme for vectors. The prover’s work to produce this succinct zero-knowledge proof is $O_{\lambda }(|F|)$.
  简洁的零知识证明有效的 IVC 证明大小为 $O_{\lambda }(\log |F|)$ ，验证者验证这些证明的工作量要么是 $O_{\lambda }(\log |F|)$ ，要么是 $O_{\lambda }(|F|)$ ，具体取决于向量的承诺方案。生成此简洁零知识证明的证明者工作量为 $O_{\lambda }(|F|)$ 。

1.3 Implementation and Performance Evaluation
1.3 实施与性能评估

We implement Nova as a library in about 6,000 lines of Rust [3]. The library is generic over a cycle of elliptic curves and a hash function (used internally as the random oracle). The library provides candidate implementations with the Pasta cycle of elliptic curves [4] and Poseidon [2, 26]. Finally, the library accepts F (i.e., a step of the incremental computation) as a bellperson gadget [1].
我们将 Nova 实现为一个 Rust 库，约 6000 行代码[3]。该库对椭圆曲线周期和哈希函数（作为内部随机预言机使用）进行泛型处理。库提供了椭圆曲线 Pasta 周期[4]和 Poseidon[2, 26]的候选实现。最后，该库接受 F（即增量计算的步骤）作为 bellperson 小工具[1]。

Recursion Overheads. We measure the size of Nova’s verifier circuit, as it determines the recursion overhead: the number of additional constraints that the prover must prove at each incremental step besides proving an invocation of F.
递归开销。我们测量 Nova 验证器电路的大小，因为它决定了递归开销：除了证明 F 的调用外，证明者在每个增量步骤中必须证明的额外约束的数量。

We find that Nova’s verifier circuit is $\approx$20,000 R1CS constraints. This is the smallest verifier circuit in the literature and hence Nova incurs the lowest recursion overhead. Specifically, Nova’s recursion overhead is $>10\times$ lower than in SNARK-based IVC [6] with state-of-the-art per-circuit trusted setup SNARK [27], and over $100\times$ smaller than with a SNARK without trusted setup [21]. Compared to recent works, Nova’s recursion overhead is over $7\times$ lower than Halo’s [12], and over $2\times$ lower than the scheme of Bunz et al. [15] (Fig. 1).
我们发现 Nova 的验证器电路是 $\approx$ 20,000 R1CS 约束。这是文献中最小的验证器电路，因此 Nova 产生的递归开销最低。具体来说，Nova 的递归开销比基于 SNARK 的 IVC[6]中具有最先进每电路可信设置的 SNARK[27]低 $>10\times$ ，并且比没有可信设置的 SNARK[21]低 $100\times$ 。与近期工作相比，Nova 的递归开销比 Halo[12]低 $7\times$ ，比 Bunz 等人[15]的方案低 $2\times$ （图 1）。

Fig. 1.图 1.

A detailed breakdown of sub-routines in Nova’s verifier’s circuit and the associated number of R1CS constraints. The verifier circuit on each of the curves in the cycle are not identical as they have slightly different base cases. We find that a majority of constraints in the verifier circuit step from the group scalar multiplications.
详细解析 Nova 验证器电路中的子程序及其关联的 R1CS 约束数量。循环中每个曲线上的验证器电路并不相同，因为它们有略微不同的基本案例。我们发现验证器电路步骤中的大多数约束来自群标量乘法。

Performance of Nova. We experiment with Nova on an Azure Standard F32s_v2 VM (16 physical CPUs, 2.70 GHz Intel(R) Xeon(R) Platinum 8168, and 64 GB memory). In our experiments, we vary the number of constraints in F. Our performance metrics are: the prover time, the verifier time, and proof sizes. We measure these for Nova’s IVC scheme as well as its Spartan-based zkSNARK to compress IVC proofs. Figure 2 depicts our results, and we find the following.
Nova 性能。我们在 Azure Standard F32s_v2 虚拟机（16 个物理 CPU，2.70 GHz Intel(R) Xeon(R) Platinum 8168，64 GB 内存）上对 Nova 进行实验。在我们的实验中，我们改变 F 中的约束数量。我们的性能指标是：证明者时间、验证者时间和证明大小。我们测量了 Nova 的 IVC 方案以及基于 Spartan 的 zkSNARK 压缩 IVC 证明的情况。图 2 展示了我们的结果，我们发现以下情况。

• The prover’s per-step cost to produce an IVC proof and compress it scale sub-linearly with the size of F (since the cost is dominated by two multiexponentiations, which scale sub-linearly due to the Pippenger algorithm and parallelize better at larger sizes). When $|F|\approx 2^{20}$ constraints, the prover’s per-step cost to produce an IVC proof is $\approx$1 $\text{μ}$s/constraint. For the same F, the cost to produce a compressed IVC proof is $\approx$24 $\text{μ}$s/constraint.³
  证明者在每一步生成 IVC 证明并压缩它的成本随着 F 的大小以亚线性比例增长（因为成本主要由两个多指数运算组成，这些运算由于 Pippenger 算法而以亚线性比例增长，并且在较大尺寸上并行化更好）。当有 $|F|\approx 2^{20}$ 约束时，证明者在每一步生成 IVC 证明的成本是 $\approx$ 1 $\text{μ}$ s/约束。对于相同的 F，生成压缩 IVC 证明的成本是 $\approx$ 24 $\text{μ}$ s/约束。 ³

• Compressed IVC proofs are $\approx 8$–9 KB and are significantly shorter than IVC proofs (e.g., they are $\approx$7,400$\times$ shorter when $|F|\approx 2^{20}$ constraints).
  压缩 IVC 证明为 $\approx 8$ –9 KB，比 IVC 证明显著更短（例如，当 $|F|\approx 2^{20}$ 约束时，它们比 $\approx$ 7,400 $\times$ 短）。

• Verifying a compressed proof is only $\approx$2$\times$ higher costs than verifying a significantly longer IVC proof.
  验证压缩证明的成本仅比验证显著更长的 IVC 证明高 $\approx$ 2 $\times$ 。

Fig. 2.图 2

Performance of Nova as a function of |F|. See the text for details.
性能随|F|的变化而变化。详见文本详情。

1.4 A More Detailed Comparison with Prior Work
1.4 与先前工作的更详细比较

Figure 3 compares Nova with prior approaches. Nova’s approach can be viewed as taking Halo’s approach to the extreme. Specifically:
图 3 比较了 Nova 与先前的方法。Nova 的方法可以看作是将 Halo 的方法推向极致。具体来说：

• At each incremental step, Halo’s verifier circuit verifies a “partial” SNARK. This still requires Halo’s prover to perform |F|-sized FFTs and O(|F|) exponentiations (i.e., not an |F|-sized multiexponentiation). Whereas, in Nova, the verifier circuit folds an entire $\mathsf{N}\mathsf{P}$ instance representing computation at the prior step into a running relaxed R1CS instance. This only requires Nova’s prover to commit to a satisfying assignment of an $\approx$ $|F|$-sized circuit (which computes F and performs the verifier’s computation in a folding scheme for relaxed R1CS), so at each step, Nova’s prover only computes an O(|F|)-sized multiexponentiation and does not compute any FFTs. So, Nova’s prover incurs lower costs than Halo’s prover, both asymptotically and concretely.
  在每一步增量中，Halo 的验证器电路验证一个“部分”SNARK。这仍然需要 Halo 的证明者执行|F|大小的 FFT 和 O(|F|)次幂运算（即不是|F|大小的多指数运算）。而 Nova 中，验证器电路将代表前一步计算的整个 $\mathsf{N}\mathsf{P}$ 实例折叠成一个运行中的放松 R1CS 实例。这只需要 Nova 的证明者对 $\approx$ $|F|$ -大小的电路（该电路计算 F 并在折叠方案中执行验证者的计算）的满足赋值进行承诺，因此，在每一步，Nova 的证明者只需计算 O(|F|)大小的多指数运算，而不需要计算任何 FFT。因此，Nova 的证明者比 Halo 的证明者承担的成本更低，无论是从渐近角度还是具体实现角度。

• The verifier circuit in Halo is of size $O_{\lambda }(\log |F|)$ whereas in Nova, it is $O_{\lambda }(1)$. Concretely, the dominant operations in Halo’s circuit is $O(\log |F|)$ group scalar multiplications, whereas in Nova, it is two group scalar multiplications.
  Halo 中的验证器电路大小为 $O_{\lambda }(\log |F|)$ ，而在 Nova 中为 $O_{\lambda }(1)$ 。具体来说，Halo 电路中的主导操作是 $O(\log |F|)$ 群标量乘法，而在 Nova 中是两次群标量乘法。

• Halo and Nova have the same proof sizes $O_{\lambda }(\log |F|)$ and verifier time $O_{\lambda }(|F|)$.
  Halo 和 Nova 具有相同的证明大小 $O_{\lambda }(\log |F|)$ 以及验证器时间 $O_{\lambda }(|F|)$ 。

Bünz et al. [16] apply Halo’s approach to other polynomial commitment schemes. Halo Infinite [10] generalizes the approach in Halo [12] to any homomorphic polynomial commitment scheme; they also obtain PCD (and hence IVC) even when polynomial commitment schemes do not satisfy succinctness.
Bünz 等人[16]将 Halo 的方法应用于其他多项式承诺方案。Halo Infinite[10]将 Halo[12]中的方法推广到任何同态多项式承诺方案；即使在多项式承诺方案不满足简洁性的情况下，他们也获得了 PCD（从而得到 IVC）。

Fig. 3.图 3

Asymptotic costs of Nova and its baselines to produce and verify a proof for an incremental computation where each incremental step applies a function F. C denotes the size of the computation at each incremental step, i.e., $|F|+|{\mathcal{C}}_{\mathcal{V}}|$, where ${\mathcal{C}}_{\mathcal{V}}$ is the “verifier circuit” in IVC. The “verifier circuit” column depicts the number of dominant operations in ${\mathcal{C}}_{\mathcal{V}}$, where $\mathbb{P}$ denotes a pairing in a pairing-friendly group, $\mathbb{F}$ denotes the number of finite field operations, $\mathbb{H}$ denotes a hash computation, and $\mathbb{G}$ denotes a scalar multiplication in a cryptographic group. The prover column depicts the cost to the prover for each step of the incremental computation, and proof sizes and verifier times refer respectively to the size of the proof of the incremental computation and the associated verification times. For Nova’s proof sizes and verification times, we depict the compressed proof sizes (otherwise, they are $O_{\lambda }(C)$) and the time to verify a compressed proof (otherwise, they are $O_{\lambda }(C)$). Rows with RO require heuristically instantiating the random oracle with a concrete hash function in the standard model.
渐近成本分析：Nova 及其基线在增量计算中生成和验证证明的成本，其中每个增量步骤应用函数 F。C 表示每个增量步骤的计算大小，即 $|F|+|{\mathcal{C}}_{\mathcal{V}}|$ ，其中 ${\mathcal{C}}_{\mathcal{V}}$ 是 IVC 中的“验证器电路”。“验证器电路”列描述了 ${\mathcal{C}}_{\mathcal{V}}$ 中的主导操作数量，其中 $\mathbb{P}$ 表示配对友好群中的配对， $\mathbb{F}$ 表示有限域操作的数量， $\mathbb{H}$ 表示哈希计算， $\mathbb{G}$ 表示密码学群中的标量乘法。证明者列描述了证明者每个增量计算步骤的成本，证明大小和验证时间分别指增量计算的证明大小和相关的验证时间。对于 Nova 的证明大小和验证时间，我们展示了压缩证明大小（否则为 $O_{\lambda }(C)$ ）和验证压缩证明的时间（否则为 $O_{\lambda }(C)$ ）。需要通过启发式方法在标准模型中实例化随机预言机的行 RO。

Bünz et al. [15] propose a variant of the approach in Halo, where they realize PCD (and hence IVC) without relying on succinct arguments. Specifically, they first devise a non-interactive argument of knowledge (NARK) for R1CS with $O_{\lambda }(N)$-sized proofs and $O_{\lambda }(N)$ verification times for N-sized R1CS instances. Then, they show that most of the NARK’s verifier’s computation can be deferred by performing $O_{\lambda }(1)$ work in the verifier circuit. For zero-knowledge, Nova relies on zero-knowledge arguments with succinct proofs, whereas their approach does not rely on succinct arguments. However, Nova’s approach has several conceptual and efficiency advantages over the work of Bünz et al. [15]:
Bünz 等人[15]提出了一种 Halo 方法变体，其中他们实现了 PCD（从而是 IVC），而不依赖于简洁的论证。具体来说，他们首先为 R1CS 设计了一种非交互式知识论证（NARK），具有 $O_{\lambda }(N)$ 大小的证明和 $O_{\lambda }(N)$ 验证时间，用于 N 大小的 R1CS 实例。然后，他们表明，通过在验证器电路中执行 $O_{\lambda }(1)$ 工作，可以推迟 NARK 验证器的大部分计算。对于零知识，Nova 依赖于具有简洁证明的零知识论证，而他们的方法则不依赖于简洁论证。然而，Nova 的方法在概念和效率上比 Bünz 等人[15]的工作具有几个优势：

• Nova introduces a new primitive called a folding scheme, which is conceptually simpler and is easier to realize than prior notions such as (split) accumulation schemes used in prior work [15, 16]. Furthermore, a folding scheme for $\mathsf{N}\mathsf{P}$ directly leads to IVC and is again easier to analyze than with prior notions.
  诺瓦引入了一种名为折叠方案的新原语，它在概念上比先前工作中使用的（分割）累积方案等概念更简单，也更易于实现。此外，针对 $\mathsf{N}\mathsf{P}$ 的折叠方案直接导致 IVC，并且与先前概念相比，分析起来也更加容易。

• At each step, their prover performs an O(|F|)-sized FFT (which costs $O(|F|\log |F|)$ operations over $\mathbb{F}$). Whereas, Nova does not perform any FFTs.
  在每一步，他们的证明者执行一个大小为 O(|F|)的快速傅里叶变换（FFT，在 $\mathbb{F}$ 上需要 $O(|F|\log |F|)$ 次操作）。而 Nova 不执行任何 FFT。

• Their prover’s work for multiexponentitions at each step and the size of their verifier circuit are both higher than in Nova by $\approx$ $4\times$.
  他们的证明者在每一步的多指数运算工作以及验证器电路的大小都高于 Nova 的 $\approx$ $4\times$ 。

• Proof sizes are $O_{\lambda }(|F|)$ in their work, whereas in Nova, they are $O_{\lambda }(\log |F|)$. We believe, in theory, they can also compress their proofs, using a succinct argument, but unlike Nova, they do not specify how to do so in a concretely efficient manner. Furthermore, using succinct arguments is inconsistent with their goal of not employing them.
  证明大小在其工作中为 $O_{\lambda }(|F|)$ ，而在 Nova 中为 $O_{\lambda }(\log |F|)$ 。理论上，我们认为他们也可以使用简洁的论据压缩他们的证明，但与 Nova 不同，他们没有具体说明如何以高效的方式做到这一点。此外，使用简洁的论据与他们的目标——不使用它们——不一致。

Concurrent Work. In an update concurrent with this work, Bünz et al. [15] provide an improved construction of their NARK for R1CS, which leads to an IVC that, like Nova, avoids FFTs. Furthermore, they improve the size of the verifier circuit by $\approx$ $2\times$, which is still larger than Nova’s verifier circuit by $\approx$ $2\times$. The per-step computation of the prover remains $4\times$ higher than Nova.
并发工作。在与这项工作同时更新的一个版本中，Bünz 等人[15]提供了他们针对 R1CS 的 NARK 的改进构造，这导致了一个 IVC，类似于 Nova，避免了 FFT。此外，他们通过 $\approx$ $2\times$ 改进了验证器电路的大小，这仍然比 Nova 的验证器电路 $\approx$ $2\times$ 大。证明者的每步计算仍然比 Nova 高 $4\times$ 。

1.5 An Overview of the Rest of the Paper
1.5 论文其余部分的概述

Section 2 provides the necessary background. Section 3 formally defines folding schemes and their properties. In Sect. 4, we introduce a variant of R1CS called relaxed R1CS for which we provide a folding scheme satisfying Theorem 1. Then, in Sect. 5, we use a non-interactive version of the folding scheme (§4.2) to construct an IVC scheme and a scheme to compress IVC proofs satisfying Theorem 2 by assuming the existence of a zkSNARK for relaxed R1CS with logarithmic-sized proofs. Finally, in Sect. 6, we construct such a zkSNARK.
第 2 节提供必要的背景。第 3 节正式定义折叠方案及其性质。在第 4 节中，我们介绍了一种称为宽松 R1CS 的 R1CS 变体，并为满足定理 1 的折叠方案提供了一种折叠方案。然后，在第 5 节中，我们使用折叠方案的非交互版本（§ 4.2）构建了一个 IVC 方案和一个压缩 IVC 证明的方案，该方案满足定理 2，并假设存在一个针对宽松 R1CS 的对数大小证明的 zkSNARK。最后，在第 6 节中，我们构建了这样的 zkSNARK。

2 Preliminaries2 前言

Let $\mathbb{F}$ denote a finite field with $|\mathbb{F}|=2^{\text{Θ}(\lambda )}$, where $\lambda$ is the security parameter. Let $\cong$ denote computational indistinguishability with respect to a PPT adversary. We globally assume that generator algorithms that produce public parameters are additionally provided appropriate size bounds.
用 $\mathbb{F}$ 表示具有 $|\mathbb{F}|=2^{\text{Θ}(\lambda )}$ 的有限域，其中 $\lambda$ 是安全参数。用 $\cong$ 表示相对于 PPT 攻击者的计算不可区分性。我们全局假设生成公参数的生成算法还提供了适当的大小界限。

2.1 A Commitment Scheme for Vectors over $\mathbb{F}$
2.1 向量上的承诺方案

We require a commitment scheme for vectors over $\mathbb{F}$ that is additively homomorphic and succinct. We formally define these two properties and others noted below in [30, App. F]. Below, we define the syntax for commitment schemes.
我们要求一个针对向量 $\mathbb{F}$ 的承诺方案，该方案是加法同态且简洁的。我们正式定义了这两个属性以及以下所提到的其他属性，见[30, 附录 F]。以下，我们定义了承诺方案的语法。

Definition 1 (A Commitment Scheme for Vectors)
定义 1（向量承诺方案）

A commitment scheme for ${\mathbb{F}}^m$ is a tuple of three protocols with the following interface.
一个针对 ${\mathbb{F}}^m$ 的承诺方案是一个包含以下界面的三个协议的元组。

• $\mathsf{G}\mathsf{e}\mathsf{n}\mathsf{(}{\mathsf{1}}^{\lambda }\mathsf{,}\mathsf{m}\mathsf{)}\to \mathsf{p}\mathsf{p}$: takes length parameter m; produces public parameters $\mathsf{p}\mathsf{p}$.
  $\mathsf{G}\mathsf{e}\mathsf{n}\mathsf{(}{\mathsf{1}}^{\lambda }\mathsf{,}\mathsf{m}\mathsf{)}\to \mathsf{p}\mathsf{p}$ : 接收长度参数 m；生成公共参数 $\mathsf{p}\mathsf{p}$ .

• $\mathsf{C}\mathsf{o}\mathsf{m}\mathsf{(}\mathsf{p}\mathsf{p}\mathsf{,}\mathsf{v}\mathsf{,}\mathsf{r}\mathsf{)}\to \mathsf{C}$: takes vector $v\in {\mathbb{F}}^m$ and $r\in \mathbb{F}$; produces commitment C.
  $\mathsf{C}\mathsf{o}\mathsf{m}\mathsf{(}\mathsf{p}\mathsf{p}\mathsf{,}\mathsf{v}\mathsf{,}\mathsf{r}\mathsf{)}\to \mathsf{C}$ : 取向量 $v\in {\mathbb{F}}^m$ 和 $r\in \mathbb{F}$ ; 生成承诺 C.

• $\mathsf{O}\mathsf{p}\mathsf{e}\mathsf{n}\mathsf{(}\mathsf{p}\mathsf{p}\mathsf{,}\mathsf{C}\mathsf{,}\mathsf{v}\mathsf{,}\mathsf{r}\mathsf{)}\to \{\mathsf{0}\mathsf{,}\mathsf{1}\}$: verifies the opening of commitment C to $v\in {\mathbb{F}}^m$.
  $\mathsf{O}\mathsf{p}\mathsf{e}\mathsf{n}\mathsf{(}\mathsf{p}\mathsf{p}\mathsf{,}\mathsf{C}\mathsf{,}\mathsf{v}\mathsf{,}\mathsf{r}\mathsf{)}\to \{\mathsf{0}\mathsf{,}\mathsf{1}\}$ : 验证对 $v\in {\mathbb{F}}^m$ 的承诺 C 的开启。

A commitment scheme satisfies hiding (the commitment reveals no information), binding (a PPT adversary cannot open a commitment to two different values), and succinctness (the commitment size is logarithmic in the opening size).
一个承诺方案满足隐藏性（承诺不泄露任何信息）、绑定性（PPT 对手不能将承诺打开为两个不同的值）和简洁性（承诺的大小是打开大小的对数）。

2.2 Non-interactive Arguments of Knowledge
2.2 知识的非交互式参数

Definition 2 (Non-Interactive Argument of Knowledge)
定义 2（非交互式知识论辩）

Consider a relation $\mathcal{R}$ over public parameters, structure, instance, and witness tuples. A non-interactive argument of knowledge for $\mathcal{R}$ consists of PPT algorithms $(\mathcal{G},\mathcal{P},\mathcal{V})$ and deterministic $\mathcal{K}$, denoting the generator, the prover, the verifier and the encoder respectively with the following interface.
考虑一个关于公共参数、结构、实例和见证元组的 $\mathcal{R}$ 关系。 $\mathcal{R}$ 的非交互式知识论证由 PPT 算法 $(\mathcal{G},\mathcal{P},\mathcal{V})$ 和确定性 $\mathcal{K}$ 组成，分别表示生成器、验证者、验证者和编码器的接口。

• $\mathcal{G}(1^{\lambda })\to \mathsf{p}\mathsf{p}$: On input security parameter $\lambda$, samples public parameters $\mathsf{p}\mathsf{p}$.
  $\mathcal{G}(1^{\lambda })\to \mathsf{p}\mathsf{p}$ : 在输入安全参数 $\lambda$ 时，采样公共参数 $\mathsf{p}\mathsf{p}$ 。

• $\mathcal{K}(\mathsf{p}\mathsf{p}\mathsf{,}\mathsf{s}\mathsf{)}\to \mathsf{(}\mathsf{p}\mathsf{k}\mathsf{,}\mathsf{v}\mathsf{k}\mathsf{)}$: On input structure $\mathsf{s}$, representing common structure among instances, outputs the prover key $\mathsf{p}\mathsf{k}$ and verifier key $\mathsf{v}\mathsf{k}$.
  $\mathcal{K}(\mathsf{p}\mathsf{p}\mathsf{,}\mathsf{s}\mathsf{)}\to \mathsf{(}\mathsf{p}\mathsf{k}\mathsf{,}\mathsf{v}\mathsf{k}\mathsf{)}$ : 在输入结构 $\mathsf{s}$ 中，表示实例之间的公共结构，输出证明密钥 $\mathsf{p}\mathsf{k}$ 和验证密钥 $\mathsf{v}\mathsf{k}$ 。

• $\mathcal{P}(\mathsf{p}\mathsf{k}\mathsf{,}\mathsf{u}\mathsf{,}\mathsf{w}\mathsf{)}\to \pi$: On input instance u and witness w, outputs a proof $\pi$ proving that $(\mathsf{p}\mathsf{p}\mathsf{,}\mathsf{s}\mathsf{,}\mathsf{u}\mathsf{,}\mathsf{w}\mathsf{)}\in \mathcal{R}$.
  $\mathcal{P}(\mathsf{p}\mathsf{k}\mathsf{,}\mathsf{u}\mathsf{,}\mathsf{w}\mathsf{)}\to \pi$ : 在输入实例 u 和见证者 w 上，输出一个证明 $\pi$ 以证明 $(\mathsf{p}\mathsf{p}\mathsf{,}\mathsf{s}\mathsf{,}\mathsf{u}\mathsf{,}\mathsf{w}\mathsf{)}\in \mathcal{R}$ 。

• $\mathcal{V}(\mathsf{v}\mathsf{k}\mathsf{,}\mathsf{u}\mathsf{,}\pi \mathsf{)}\to \{\mathsf{0}\mathsf{,}\mathsf{1}\}$: Checks instance u given proof $\pi$.
  $\mathcal{V}(\mathsf{v}\mathsf{k}\mathsf{,}\mathsf{u}\mathsf{,}\pi \mathsf{)}\to \{\mathsf{0}\mathsf{,}\mathsf{1}\}$ : 检查实例 u 给定的证明 $\pi$ 。

An argument of knowledge satisfies completeness if for any PPT adversary $\mathcal{A}$
一个知识论点满足完备性，如果对于任何 PPT 对手 $\mathcal{A}$

An argument of knowledge satisfies knowledge soundness if for all PPT adversaries $\mathcal{A}$ there exists a PPT extractor $\mathcal{E}$ such that for all randomness $\rho$
一个知识论据满足知识有效性，如果对于所有 PPT 攻击者 $\mathcal{A}$ ，存在一个 PPT 提取器 $\mathcal{E}$ ，使得对于所有随机性 $\rho$

Definition 3 (Zero-Knowledge)
定义 3（零知识）

An argument of knowledge $(\mathcal{G},\mathcal{K},\mathcal{P},\mathcal{V})$ for relation $\mathcal{R}$ satisfies zero-knowledge if there exists PPT simulator $\mathcal{S}$ such that for all PPT adversaries $\mathcal{A}$
一个关于关系 $\mathcal{R}$ 的知识论据 $(\mathcal{G},\mathcal{K},\mathcal{P},\mathcal{V})$ 满足零知识，如果存在 PPT 模拟器 $\mathcal{S}$ ，使得对于所有 PPT 对手 $\mathcal{A}$

Definition 4 (Succinctness)
定义 4（简洁性）

A non-interactive argument system is succinct if the size of the proof $\pi$ is polylogarithmic in the size of the witness w.
非交互式论证系统在证明 $\pi$ 的大小与见证 w 的大小成对数多项式关系时是简洁的。

2.3 Incrementally Verifiable Computation
2.3 逐步可验证计算

Incrementally verifiable computation (IVC) [43] enables verifiable computation for repeated function application. Intuitively, for a function F, with initial input $z_0$, an IVC scheme allows a prover to produce a proof ${\text{Π}}_i$ for the statement $z_i=F^{(i)}(z_0)$ (i.e., i applications of F on input $z_0$) given a proof ${\text{Π}}_{i-1}$ for the statement $z_{i-1}=F^{(i-1)}(z_0)$. Formally, IVC schemes additionally permit F to take auxiliary input $\omega$. We recall the definition of IVC using notational conventions of modern argument systems.
增量可验证计算（IVC）[43] 允许对重复函数应用进行可验证计算。直观上，对于函数 F，给定初始输入 $z_0$ ，一个 IVC 方案允许证明者针对陈述 $z_i=F^{(i)}(z_0)$ （即对输入 $z_0$ 应用 F 的 i 次）产生证明 ${\text{Π}}_i$ ，前提是针对陈述 $z_{i-1}=F^{(i-1)}(z_0)$ 已有一个证明 ${\text{Π}}_{i-1}$ 。形式上，IVC 方案还允许 F 接收辅助输入 $\omega$ 。我们使用现代论证系统的符号约定来回忆 IVC 的定义。

Definition 5 (IVC)定义 5（IVC）

An incrementally verifiable computation (IVC) scheme is defined by PPT algorithms $(\mathcal{G},\mathcal{P},\mathcal{V})$ and deterministic $\mathcal{K}$ denoting the generator, the prover, the verifier, and the encoder respectively. An IVC scheme $(\mathcal{G},\mathcal{K},\mathcal{P},\mathcal{V})$ satisfies perfect completeness if for any PPT adversary $\mathcal{A}$
增量可验证计算（IVC）方案由 PPT 算法定义，包括生成器、证明者、验证者和编码器，分别表示为 $(\mathcal{G},\mathcal{P},\mathcal{V})$ 和确定性 $\mathcal{K}$ 。一个 IVC 方案 $(\mathcal{G},\mathcal{K},\mathcal{P},\mathcal{V})$ 如果对于任何 PPT 对手 $\mathcal{A}$ 满足完美完备性。

where F is a polynomial time computable function. Likewise, an IVC scheme satisfies knowledge-soundness if for any constant $n\in \mathbb{N}$, and expected polynomial time adversaries ${\mathcal{P}}^{\ast }$ there exists expected polynomial-time extractor $\mathcal{E}$ such that for any input randomness $\rho$
F 是一个多项式时间可计算函数。同样，一个 IVC 方案满足知识一致性，如果对于任何常数 $n\in \mathbb{N}$ ，以及期望的多项式时间对手 ${\mathcal{P}}^{\ast }$ ，存在期望的多项式时间提取器 $\mathcal{E}$ ，使得对于任何输入随机性 $\rho$

An IVC scheme satisfies succinctness if the size of the IVC proof $\text{Π}$ does not grow with the number of applications n.
一个 IVC 方案在 IVC 证明的大小 $\text{Π}$ 不随应用数量 n 增长的情况下满足简洁性。

We note that in the definition above, the number of steps n is treated as a fixed environment variable that characterizes the extractor. This model is required for all known general recursive techniques as they rely on recursive extractors that blowup polynomially for each additional recursive step [10, 13, 15, 16, 21]. Bitansky et al. [8] avoid such a restriction by making non-blackbox assumptions about the extractors runtime with respect to that of the malicious prover. In any case, there are no known attacks on arbitrary depth recursion.
我们注意到，在上面的定义中，步骤数 n 被视为一个固定环境变量，它表征了提取器。所有已知的通用递归技术都需要这个模型，因为它们依赖于递归提取器，每个额外的递归步骤都会以多项式方式爆炸[10, 13, 15, 16, 21]。Bitansky 等人[8]通过关于提取器运行时间和恶意证明者运行时间的非黑盒假设来避免这种限制。无论如何，没有已知针对任意深度递归的攻击。

3 Folding Schemes3 折叠方案

This section formally defines folding schemes. Intuitively, a folding scheme for a relation $\mathcal{R}$ is a protocol that reduces the task of checking two instances in $\mathcal{R}$ to the task of checking a single instance in $\mathcal{R}$.
本节正式定义折叠方案。直观上，对于关系 $\mathcal{R}$ 的折叠方案是一种将检查 $\mathcal{R}$ 中的两个实例的任务简化为检查 $\mathcal{R}$ 中的单个实例的任务的协议。

Definition 6 (Folding Scheme)
定义 6（折叠方案）

Consider a relation $\mathcal{R}$ over public parameters, structure, instance, and witness tuples. A folding scheme for $\mathcal{R}$ consists of a PPT generator algorithm $\mathcal{G}$, a deterministic encoder algorithm $\mathcal{K}$, and a pair of PPT algorithms $\mathcal{P}$ and $\mathcal{V}$ denoting the prover and verifier respectively, with the following interface:
考虑一个在公共参数、结构、实例和见证元组上的关系 $\mathcal{R}$ 。一个折叠方案 $\mathcal{R}$ 包括一个 PPT 生成算法 $\mathcal{G}$ ，一个确定性编码算法 $\mathcal{K}$ ，以及一对 PPT 算法 $\mathcal{P}$ 和 $\mathcal{V}$ ，分别表示证明者和验证者，具有以下接口：

• $\mathcal{G}(1^{\lambda })\to \mathsf{p}\mathsf{p}$: On input security parameter $\lambda$, samples public parameters $\mathsf{p}\mathsf{p}$.
  $\mathcal{G}(1^{\lambda })\to \mathsf{p}\mathsf{p}$ : 在输入安全参数 $\lambda$ 时，采样公共参数 $\mathsf{p}\mathsf{p}$ 。

• $\mathcal{K}(\mathsf{p}\mathsf{p}\mathsf{,}\mathsf{s}\mathsf{)}\to \mathsf{(}\mathsf{p}\mathsf{k}\mathsf{,}\mathsf{v}\mathsf{k}\mathsf{)}$: On input $\mathsf{p}\mathsf{p}$, and a common structure $\mathsf{s}$ between instances to be folded, outputs a prover key $\mathsf{p}\mathsf{k}$ and a verifier key $\mathsf{v}\mathsf{k}$.
  $\mathcal{K}(\mathsf{p}\mathsf{p}\mathsf{,}\mathsf{s}\mathsf{)}\to \mathsf{(}\mathsf{p}\mathsf{k}\mathsf{,}\mathsf{v}\mathsf{k}\mathsf{)}$ : 在输入 $\mathsf{p}\mathsf{p}$ ，以及要折叠的实例之间的常见结构 $\mathsf{s}$ ，输出一个证明密钥 $\mathsf{p}\mathsf{k}$ 和一个验证密钥 $\mathsf{v}\mathsf{k}$ 。

• $\mathcal{P}(\mathsf{p}\mathsf{k}\mathsf{,}\mathsf{(}{\mathsf{u}}_{\mathsf{1}}\mathsf{,}{\mathsf{w}}_{\mathsf{1}}\mathsf{)}\mathsf{,}\mathsf{(}{\mathsf{u}}_{\mathsf{2}}\mathsf{,}{\mathsf{w}}_{\mathsf{2}}\mathsf{)}\mathsf{)}\to \mathsf{(}\mathsf{u}\mathsf{,}\mathsf{w}\mathsf{)}$: On input instance-witness tuples $(u_1,w_1)$ and $(u_2,w_2)$ outputs a new instance-witness tuple (u, w) of the same size.
  $\mathcal{P}(\mathsf{p}\mathsf{k}\mathsf{,}\mathsf{(}{\mathsf{u}}_{\mathsf{1}}\mathsf{,}{\mathsf{w}}_{\mathsf{1}}\mathsf{)}\mathsf{,}\mathsf{(}{\mathsf{u}}_{\mathsf{2}}\mathsf{,}{\mathsf{w}}_{\mathsf{2}}\mathsf{)}\mathsf{)}\to \mathsf{(}\mathsf{u}\mathsf{,}\mathsf{w}\mathsf{)}$ : 在输入实例-见证元组 $(u_1,w_1)$ 和 $(u_2,w_2)$ 的基础上输出相同大小的新实例-见证元组 (u, w)。

• $\mathcal{V}(\mathsf{v}\mathsf{k}\mathsf{,}{\mathsf{u}}_{\mathsf{1}}\mathsf{,}{\mathsf{u}}_{\mathsf{2}}\mathsf{)}\to \mathsf{u}$: On input instances $u_1$ and $u_2$, outputs a new instance u.
  $\mathcal{V}(\mathsf{v}\mathsf{k}\mathsf{,}{\mathsf{u}}_{\mathsf{1}}\mathsf{,}{\mathsf{u}}_{\mathsf{2}}\mathsf{)}\to \mathsf{u}$ : 在输入实例 $u_1$ 和 $u_2$ 上，输出新的实例 u.

Let让我们

$$\begin{array}{r}(u,w)\leftarrow ⟨\mathcal{P}(\mathsf{p}\mathsf{k}\mathsf{,}{\mathsf{w}}_{\mathsf{1}}\mathsf{,}{\mathsf{w}}_{\mathsf{2}}\mathsf{)}\mathsf{,}\mathcal{V}\mathsf{(}\mathsf{v}\mathsf{k}\mathsf{)}⟩\mathsf{(}{\mathsf{u}}_{\mathsf{1}}\mathsf{,}{\mathsf{u}}_{\mathsf{2}}\mathsf{)}\end{array}$$

denote the the verifier’s output instance u and the prover’s output witness w from the interaction of $\mathcal{P}$ and $\mathcal{V}$ on witnesses $(w_1,w_2)$, prover key $\mathsf{p}\mathsf{k}$, verifier key $\mathsf{v}\mathsf{k}$ and instances $(u_1,u_2)$. Likewise, let
表示验证者输出实例 u 和证明者输出见证 w，从 $\mathcal{P}$ 和 $\mathcal{V}$ 与见证 $(w_1,w_2)$ 的交互、证明者密钥 $\mathsf{p}\mathsf{k}$ 、验证者密钥 $\mathsf{v}\mathsf{k}$ 以及实例 $(u_1,u_2)$ 中得出。同样地，让

$$\begin{array}{r}\mathsf{t}\mathsf{r}\mathsf{=}⟨\mathcal{P}\mathsf{(}\mathsf{p}\mathsf{k}\mathsf{,}{\mathsf{w}}_{\mathsf{1}}\mathsf{,}{\mathsf{w}}_{\mathsf{2}}\mathsf{)}\mathsf{,}\mathcal{V}\mathsf{(}\mathsf{v}\mathsf{k}\mathsf{)}⟩\mathsf{(}{\mathsf{u}}_{\mathsf{1}}\mathsf{,}{\mathsf{u}}_{\mathsf{2}}\mathsf{)}\end{array}$$

denote the corresponding interaction transcript. A folding scheme satisfies perfect completeness if for all PPT adversaries $\mathcal{A}$
表示相应的交互记录。一个折叠方案满足完美完备性，如果对于所有 PPT 对手 $\mathcal{A}$

A folding scheme satisfies knowledge soundness if for any expected polynomial-time adversary ${\mathcal{P}}^{\ast }$ there is an expected polynomial-time extractor $\mathcal{E}$ such that
一个折叠方案满足知识一致性，如果对于任何预期的多项式时间对手 ${\mathcal{P}}^{\ast }$ ，存在一个预期的多项式时间提取器 $\mathcal{E}$ ，使得

where $\rho$ denotes arbitrary input randomness for ${\mathcal{P}}^{\ast }$. We call a transcript an accepting transcript if $\mathcal{P}$ outputs a satisfying folded witness w for the folded instance u. We consider a folding scheme non-trivial if the communication costs and $\mathcal{V}$’s computation are lower in the case where $\mathcal{V}$ participates in the folding scheme and then checks a witness sent by $\mathcal{P}$ for the folded instance than the case where $\mathcal{V}$ checks witnesses sent by $\mathcal{P}$ for each of the original instances.
$\rho$ 表示对 ${\mathcal{P}}^{\ast }$ 的任意输入随机性。我们称一个记录为接受记录，如果 $\mathcal{P}$ 输出满足折叠实例 u 的折叠证明 w。我们考虑一个折叠方案是非平凡的，如果参与折叠方案并检查由 $\mathcal{V}$ 发送的折叠实例的证明的成本和 $\mathcal{V}$ 的计算成本，比检查由 $\mathcal{V}$ 为每个原始实例发送的证明的成本要低。

Definition 7 (Non-Interactive)
定义 7（非交互式）

A folding scheme $(\mathcal{G},\mathcal{K},\mathcal{P},\mathcal{V})$ is non-interactive if the interaction between $\mathcal{P}$ and $\mathcal{V}$ consists of a single message from $\mathcal{P}$ to $\mathcal{V}$. This single message is denoted as an output of $\mathcal{P}$, and an input to $\mathcal{V}$.
折叠方案 $(\mathcal{G},\mathcal{K},\mathcal{P},\mathcal{V})$ 在 $\mathcal{P}$ 与 $\mathcal{V}$ 之间的交互仅由 $\mathcal{P}$ 发送给 $\mathcal{V}$ 的单一消息组成时是非交互式的。此单一消息表示为 $\mathcal{P}$ 的输出，以及 $\mathcal{V}$ 的输入。

Definition 8 (Zero-Knowledge)
定义 8（零知识）

A folding scheme $(\mathcal{G},\mathcal{K},\mathcal{P},\mathcal{V})$ satisfies zero-knowledge for relation $\mathcal{R}$ if there exists a PPT simulator $\mathcal{S}$ such that for all PPT adversaries $\mathcal{A}$, and ${\mathcal{V}}^{\ast }$, and input randomness $\rho$
折叠方案 $(\mathcal{G},\mathcal{K},\mathcal{P},\mathcal{V})$ 在存在一个 PPT 模拟器 $\mathcal{S}$ 的情况下，对于所有 PPT 对手 $\mathcal{A}$ ，以及 ${\mathcal{V}}^{\ast }$ ，和输入随机性 $\rho$ ，满足关系 $\mathcal{R}$ 的零知识

Definition 9 (Public Coin)
定义 9（公共币）

A folding scheme $(\mathcal{G},\mathcal{K},\mathcal{P},\mathcal{V})$ is called public coin if all the messages sent from $\mathcal{V}$ to $\mathcal{P}$ are sampled from a uniform distribution.
折叠方案 $(\mathcal{G},\mathcal{K},\mathcal{P},\mathcal{V})$ 如果从 $\mathcal{V}$ 到 $\mathcal{P}$ 发送的所有消息都来自均匀分布，则称为公共币。

Typically, knowledge soundness is difficult to prove directly. To assist these proofs, prior works employ the forking lemma [11], which abstracts away much of the probabilistic reasoning. The original forking lemma shows that to prove knowledge soundness it is sufficient to construct a PPT extractor that takes as input a “tree” of accepting transcripts and outputs a satisfying witness. However, in our setting, this extractor must additionally take as input the prover’s output (i.e., the folded instance and witness) for each of these transcripts, which contains information needed to reconstruct the original witness. So, we introduce a small variant of the forking lemma that captures this modification.
通常，知识的正确性难以直接证明。为了协助这些证明，先前的工作采用了分叉引理[11]，该引理抽象掉了大部分概率推理。原始的分叉引理表明，为了证明知识的正确性，构建一个 PPT 提取器就足够了，该提取器以接受会话的“树”作为输入，并输出一个满足的证人。然而，在我们的设置中，这个提取器还必须以每个这些会话的证明者的输出（即折叠实例和证人）作为输入，这些输出包含重建原始证人的所需信息。因此，我们引入了分叉引理的一个小变体，以捕捉这种修改。

Lemma 1引理 1

(Forking Lemma for Folding Schemes). Consider a $(2\mu +1)$-move folding scheme $\text{Π}=(\mathcal{G},\mathcal{K},\mathcal{P},\mathcal{V})$. $\text{Π}$ satisfies knowledge soundness if there exists a PPT $\mathcal{X}$ such that for all input instance pairs $u_1$, $u_2$, outputs satisfying witnesses $w_1$, $w_2$ with probability $1-\mathsf{n}\mathsf{e}\mathsf{g}\mathsf{l}\mathsf{(}\lambda \mathsf{)}$, given public parameters $\mathsf{p}\mathsf{p}$, structure $\mathsf{s}$, and an $(n_1,\dots ,n_{\mu })$-tree of accepting transcripts and corresponding folded instance-witness pairs (u, w). This tree comprises $n_1$ transcripts (and corresponding instance-witness pairs) with fresh randomness in $\mathcal{V}$’s first message; and for each such transcript, $n_2$ transcripts (and corresponding instance-witness pairs) with fresh randomness in $\mathcal{V}$’s second message; etc., for a total of $\prod _{i=1}^{\mu }{n}_i$ leaves bounded by $\mathsf{p}\mathsf{o}\mathsf{l}\mathsf{y}\mathsf{(}\lambda \mathsf{)}$.
（折叠方案分叉引理）。考虑一个 $(2\mu +1)$ -移动折叠方案 $\text{Π}=(\mathcal{G},\mathcal{K},\mathcal{P},\mathcal{V})$ 。 $\text{Π}$ 满足知识一致性，如果存在一个 PPT $\mathcal{X}$ ，使得对于所有输入实例对 $u_1$ ， $u_2$ ，在给定公共参数 $\mathsf{p}\mathsf{p}$ ，结构 $\mathsf{s}$ ，以及一个 $(n_1,\dots ,n_{\mu })$ -接受转录树和相应的折叠实例-见证对（u, w）的情况下，以概率 $1-\mathsf{n}\mathsf{e}\mathsf{g}\mathsf{l}\mathsf{(}\lambda \mathsf{)}$ 输出满足见证的输出 $w_1$ ， $w_2$ 。此树包含 $n_1$ 转录（以及相应的实例-见证对），在 $\mathcal{V}$ 的第一条消息中具有新鲜随机性；对于每个这样的转录， $n_2$ 转录（以及相应的实例-见证对），在 $\mathcal{V}$ 的第二条消息中具有新鲜随机性；等等，总共有 $\prod _{i=1}^{\mu }{n}_i$ 个叶子，受限于 $\mathsf{p}\mathsf{o}\mathsf{l}\mathsf{y}\mathsf{(}\lambda \mathsf{)}$ 。

Proof Intuition. A proof for our variant of the forking lemma is similar to that of Bootle et al. [11]. We present a formal proof in [30, App. F].    $◻$
证明直觉。我们对分叉引理的变体所提供的证明与 Bootle 等人[11]的类似。我们在[30，附录 F]中提供了一个形式化的证明。 $◻$

4 A Folding Scheme for NP
4 一种 NP 折叠方案

In this section, we describe a public-coin, zero-knowledge interactive folding scheme for $\mathsf{N}\mathsf{P}$. We additionally discuss how to make it non-interactive. We leverage the non-interactivity property to realize IVC in the next section, and the zero-knowledge property to achieve zero-knowledge IVC proof compression.
在这一节中，我们描述了一种针对 $\mathsf{N}\mathsf{P}$ 的公开币、零知识交互折叠方案。此外，我们还讨论了如何使其非交互式。我们利用非交互性属性在下一节实现 IVC，并利用零知识属性实现零知识 IVC 证明压缩。

4.1 A Public-Coin, Zero-Knowledge Folding Scheme
4.1 公共币，零知识折叠方案

To design a folding scheme for $\mathsf{N}\mathsf{P}$, we need an $\mathsf{N}\mathsf{P}$-complete language. While theoretically any $\mathsf{N}\mathsf{P}$-complete language is a viable candidate, we focus on R1CS,⁴ a popular algebraic representation that generalizes arithmetic circuit satisfiability.
为了设计 $\mathsf{N}\mathsf{P}$ 的折叠方案，我们需要一个 $\mathsf{N}\mathsf{P}$ -完备的语言。虽然从理论上讲，任何 $\mathsf{N}\mathsf{P}$ -完备的语言都是可行的候选者，但我们专注于 R1CS， ⁴ 一种流行的代数表示，它泛化了算术电路可满足性。

Definition 10 (R1CS)定义 10（R1CS）

Consider a finite field $\mathbb{F}$. Let the public parameters consist of size bounds $m,n,\ell \in \mathbb{N}$ where $m>\ell$. The R1CS structure consists of sparse matrices $A,B,C\in {\mathbb{F}}^{m\times m}$ with at most $n=\text{Ω}(m)$ non-zero entries in each matrix. An instance $\mathsf{x}\in {\mathbb{F}}^{\ell }$ consists of public inputs and outputs and is satisfied by a witness $W\in {\mathbb{F}}^{m-\ell -1}$ if $(A\cdot Z)\circ (B\cdot Z)=C\cdot Z$, where $Z=(W,\mathsf{x}\mathsf{,}\mathsf{1}\mathsf{)}$.
考虑一个有限域 $\mathbb{F}$ 。公参数由大小界限 $m,n,\ell \in \mathbb{N}$ 组成，其中 $m>\ell$ 。R1CS 结构由稀疏矩阵 $A,B,C\in {\mathbb{F}}^{m\times m}$ 组成，每个矩阵中最多有 $n=\text{Ω}(m)$ 个非零项。一个实例 $\mathsf{x}\in {\mathbb{F}}^{\ell }$ 由公输入和输出组成，并由一个证明者 $W\in {\mathbb{F}}^{m-\ell -1}$ 满足，如果 $(A\cdot Z)\circ (B\cdot Z)=C\cdot Z$ ，其中 $Z=(W,\mathsf{x}\mathsf{,}\mathsf{1}\mathsf{)}$ 。

As we show in the next section, to realize IVC, we only need a folding scheme that can fold two R1CS instances with the same R1CS matrices (A, B, C). Specifically, given R1CS matrices (A, B, C), and two corresponding instance-witness pairs $({\mathsf{x}}_{\mathsf{1}}\mathsf{,}{\mathsf{W}}_{\mathsf{1}}\mathsf{)}$ and $({\mathsf{x}}_{\mathsf{2}}\mathsf{,}{\mathsf{W}}_{\mathsf{2}}\mathsf{)}$, we would like to devise a scheme that reduces the task of checking both instances into the task of checking a single new instance-witness pair $(\mathsf{x}\mathsf{,}\mathsf{W}\mathsf{)}$ against the same R1CS matrices (A, B, C). Unfortunately, as we illustrate now, it is difficult to devise a folding scheme for R1CS such that it satisfies completeness, let alone knowledge soundness.
正如我们在下一节中所示，要实现 IVC，我们只需要一个可以折叠具有相同 R1CS 矩阵（A，B，C）的两个 R1CS 实例的折叠方案。具体来说，给定 R1CS 矩阵（A，B，C）和两个相应的实例-证据对 $({\mathsf{x}}_{\mathsf{1}}\mathsf{,}{\mathsf{W}}_{\mathsf{1}}\mathsf{)}$ 和 $({\mathsf{x}}_{\mathsf{2}}\mathsf{,}{\mathsf{W}}_{\mathsf{2}}\mathsf{)}$ ，我们希望设计一个方案，将检查两个实例的任务简化为检查单个新的实例-证据对 $(\mathsf{x}\mathsf{,}\mathsf{W}\mathsf{)}$ 对相同的 R1CS 矩阵（A，B，C）的任务。不幸的是，正如我们现在所展示的，要设计一个满足完备性，更不用说知识健全性的 R1CS 折叠方案是困难的。

First Attempt. As R1CS is an algebraic system, the most direct approach would be to take a random linear combination. Ignoring efficiency concerns, suppose that the prover sends witnesses $W_1$ and $W_2$ in the first step. The verifier responds with a random $r\in \mathbb{F}$; the prover and the verifier both compute
第一次尝试。由于 R1CS 是一个代数系统，最直接的方法是采用随机线性组合。忽略效率问题，假设验证者在第一步发送了见证 $W_1$ 和 $W_2$ 。验证者响应随机 $r\in \mathbb{F}$ ；验证者和验证者都计算

$$\begin{array}{rl}\mathsf{x}& \leftarrow {\mathsf{x}}_{\mathsf{1}}\mathsf{+}\mathsf{r}\cdot {\mathsf{x}}_{\mathsf{2}}\\ W& \leftarrow W_1+r\cdot W_2,\end{array}$$

and set the new instance-witness pair to be $(\mathsf{x}\mathsf{,}\mathsf{W}\mathsf{)}$. However, for non-trivial $Z_1=(W_1,{\mathsf{x}}_{\mathsf{1}}\mathsf{,}\mathsf{1}\mathsf{)}$ and $Z_2=(W_2,{\mathsf{x}}_{\mathsf{2}}\mathsf{,}\mathsf{1}\mathsf{)}$, and $Z=(W,\mathsf{x}\mathsf{,}\mathsf{1}\mathsf{)}$, we roughly have that
将新实例见证对设置为 $(\mathsf{x}\mathsf{,}\mathsf{W}\mathsf{)}$ 。然而，对于非平凡的 $Z_1=(W_1,{\mathsf{x}}_{\mathsf{1}}\mathsf{,}\mathsf{1}\mathsf{)}$ 和 $Z_2=(W_2,{\mathsf{x}}_{\mathsf{2}}\mathsf{,}\mathsf{1}\mathsf{)}$ ，以及 $Z=(W,\mathsf{x}\mathsf{,}\mathsf{1}\mathsf{)}$ ，我们大致有：

$$\begin{array}{rl}AZ\circ BZ& =A(Z_1+r\cdot Z_2)\circ B(Z_1+r\cdot Z_2)\\ & =A{Z}_1\circ B{Z}_1+r\cdot (A{Z}_1\circ B{Z}_2+A{Z}_2\circ B{Z}_1)+r^2\cdot (A{Z}_2\circ B{Z}_2)\\ & \ne CZ.\end{array}$$

The failed attempt exposes three issues. First, we must account for an additional cross-term, $r\cdot (A{Z}_1\circ B{Z}_2+A{Z}_2\circ B{Z}_1)$. Second, the terms excluding the cross-term combine to produce a term that does not equal CZ:
失败的尝试揭示了三个问题。首先，我们必须考虑一个额外的交叉项， $r\cdot (A{Z}_1\circ B{Z}_2+A{Z}_2\circ B{Z}_1)$ 。其次，排除交叉项的术语组合产生一个不等于 CZ 的术语。

$$\begin{array}{r}A{Z}_1\circ B{Z}_1+r^2\cdot (A{Z}_2\circ B{Z}_2)=C{Z}_1+r^2\cdot C{Z}_2\ne C{Z}_1+r\cdot C{Z}_2=CZ.\end{array}$$

Third, we do not even have that $Z=Z_1+r\cdot Z_2$ because $Z_1+r\cdot Z_2=(W,\mathsf{x}\mathsf{,}\mathsf{1}\mathsf{+}\mathsf{r}\cdot \mathsf{1}\mathsf{)}$.
第三，我们甚至没有那个 $Z=Z_1+r\cdot Z_2$ ，因为 $Z_1+r\cdot Z_2=(W,\mathsf{x}\mathsf{,}\mathsf{1}\mathsf{+}\mathsf{r}\cdot \mathsf{1}\mathsf{)}$ 。

Second Attempt. To handle the first issue, we introduce a “slack” (or error) vector $E\in {\mathbb{F}}^m$ which absorbs the cross terms generated by folding. To handle the second and third issues, we introduce a scalar u, which absorbs an extra factor of r in $C{Z}_1+r^2\cdot C{Z}_2$ and in $Z=(W,\mathsf{x}\mathsf{,}\mathsf{1}\mathsf{+}\mathsf{r}\cdot \mathsf{1}\mathsf{)}$. We refer to a variant of R1CS with these additional terms as relaxed R1CS.
第二次尝试。为了处理第一个问题，我们引入一个“松弛”（或误差）向量 $E\in {\mathbb{F}}^m$ ，它吸收由折叠产生的交叉项。为了处理第二个和第三个问题，我们引入一个标量 u，它在 $C{Z}_1+r^2\cdot C{Z}_2$ 和 $Z=(W,\mathsf{x}\mathsf{,}\mathsf{1}\mathsf{+}\mathsf{r}\cdot \mathsf{1}\mathsf{)}$ 中吸收额外的 r 因子。我们将具有这些附加项的 R1CS 变体称为松弛 R1CS。

Definition 11 (Relaxed R1CS)
定义 11（宽松的 R1CS）

Consider a finite field $\mathbb{F}$. Let the public parameters consist of size bounds $m,n,\ell \in \mathbb{N}$ where $m>\ell$. The relaxed R1CS structure consists of sparse matrices $A,B,C\in {\mathbb{F}}^{m\times m}$ with at most $n=\text{Ω}(m)$ non-zero entries in each matrix. A relaxed R1CS instance consists of an error vector $E\in {\mathbb{F}}^m$, a scalar $u\in \mathbb{F}$, and public inputs and outputs $\mathsf{x}\in {\mathbb{F}}^{\ell }$. An instance $(E,u,\mathsf{x}\mathsf{)}$ is satisfied by a witness $W\in {\mathbb{F}}^{m-\ell -1}$ if $(A\cdot Z)\circ (B\cdot Z)=u\cdot (C\cdot Z)+E$, where $Z=(W,\mathsf{x}\mathsf{,}\mathsf{u}\mathsf{)}$.
考虑一个有限域 $\mathbb{F}$ 。公参数由大小界限 $m,n,\ell \in \mathbb{N}$ 组成，其中 $m>\ell$ 。放宽的 R1CS 结构由稀疏矩阵 $A,B,C\in {\mathbb{F}}^{m\times m}$ 组成，每个矩阵中最多有 $n=\text{Ω}(m)$ 个非零项。一个放宽的 R1CS 实例由一个错误向量 $E\in {\mathbb{F}}^m$ ，一个标量 $u\in \mathbb{F}$ ，以及公输入和输出 $\mathsf{x}\in {\mathbb{F}}^{\ell }$ 组成。如果一个实例 $(E,u,\mathsf{x}\mathsf{)}$ 被一个证人 $W\in {\mathbb{F}}^{m-\ell -1}$ 满足，那么 $(A\cdot Z)\circ (B\cdot Z)=u\cdot (C\cdot Z)+E$ ，其中 $Z=(W,\mathsf{x}\mathsf{,}\mathsf{u}\mathsf{)}$ 。

Note that any R1CS instance can be expressed as a relaxed R1CS instance by augmenting it with $u=1$ and $E=0$, so relaxed R1CS retains $\mathsf{N}\mathsf{P}$-completeness.
请注意，任何 R1CS 实例都可以通过增加 $u=1$ 和 $E=0$ 来表示为放宽的 R1CS 实例，因此放宽的 R1CS 保留了 $\mathsf{N}\mathsf{P}$ -完备性。

Building on the first attempt, the prover and verifier can now use E to accumulate the cross-terms. In particular, for $Z_i=(W_i,{\mathsf{x}}_{\mathsf{i}}\mathsf{,}{\mathsf{u}}_{\mathsf{i}}\mathsf{)}$, the prover and verifier additionally compute
基于第一次尝试，证明者和验证者现在可以使用 E 来累积交叉项。特别是对于 $Z_i=(W_i,{\mathsf{x}}_{\mathsf{i}}\mathsf{,}{\mathsf{u}}_{\mathsf{i}}\mathsf{)}$ ，证明者和验证者还额外计算

$$\begin{array}{rl}u& \leftarrow u_1+r\cdot u_2\\ E& \leftarrow E_1+r\cdot (A{Z}_1\circ B{Z}_2+A{Z}_2\circ B{Z}_1-u_{1}C{Z}_2-u_{2}C{Z}_1)+r^2\cdot E_2,\end{array}$$

and set the new instance-witness pair to be $((E,u,\mathsf{x}\mathsf{)}\mathsf{,}\mathsf{W}\mathsf{)}$. Conveniently, updating u in this manner also keeps track of how the constant term in Z should be updated, which motivates our choice to use u in $Z=(W,\mathsf{x}\mathsf{,}\mathsf{u}\mathsf{)}$ rather than introducing a new variable. Now, for $Z=(W,\mathsf{x}\mathsf{,}\mathsf{u}\mathsf{)}$, and for random $r\in \mathbb{F}$,
将新实例见证对设置为 $((E,u,\mathsf{x}\mathsf{)}\mathsf{,}\mathsf{W}\mathsf{)}$ 。方便的是，以这种方式更新 u 也会跟踪 Z 中的常数项应该如何更新，这促使我们选择在 $Z=(W,\mathsf{x}\mathsf{,}\mathsf{u}\mathsf{)}$ 中使用 u 而不是引入新变量。现在，对于 $Z=(W,\mathsf{x}\mathsf{,}\mathsf{u}\mathsf{)}$ ，以及对于随机 $r\in \mathbb{F}$ ，

$$\begin{array}{rl}AZ\circ BZ& =A{Z}_1\circ B{Z}_1+r\cdot (A{Z}_1\circ B{Z}_2+A{Z}_2\circ B{Z}_1)+r^2\cdot (A{Z}_2\circ B{Z}_2)\\ & =(u_{1}C{Z}_1+E_1)+r\cdot (A{Z}_1\circ B{Z}_2+A{Z}_2\circ B{Z}_1)+r^2\cdot (u_{2}C{Z}_2+E_2)\\ & =(u_1+r\cdot u_2)\cdot C(Z_1+r{Z}_2)+E\\ & =uCZ+E.\end{array}$$

This implies that, for R1CS matrices (A, B, C), the folded witness W is a satisfying witness for the folded instance $(E,u,\mathsf{x}\mathsf{)}$ as promised. A few issues remain: in the above scheme, the prover sends witnesses $(W_1,W_2)$ for the verifier to compute E. As a result, the folding scheme is not non-trivial; it is also not zero-knowledge.
这表明，对于 R1CS 矩阵（A，B，C），折叠的见证 W 是对折叠实例 $(E,u,\mathsf{x}\mathsf{)}$ 的满足见证，正如所承诺的那样。仍有一些问题存在：在上面的方案中，证明者向验证者发送见证 $(W_1,W_2)$ 以计算 E。因此，折叠方案不是平凡的；它也不是零知识。

Final Protocol. To circumvent these issues, we use succinct and hiding additively homomorphic commitments to W and E in the instance, and treat both W and E as the witness. We refer to this variant of relaxed R1CS as committed relaxed R1CS. Below, we describe a folding scheme for committed relaxed R1CS, where the prover sends a single commitment to aid the verifier in computing commitments to the folded witness (W, E).
最终协议。为规避这些问题，我们在实例中使用简洁且隐藏的加法同态承诺来处理 W 和 E，并将 W 和 E 都视为见证。我们将这种放松的 R1CS 的变体称为承诺的放松 R1CS。以下，我们描述了一个针对承诺的放松 R1CS 的折叠方案，其中验证者发送单个承诺以帮助验证者计算折叠见证（W，E）的承诺。

Definition 12 (Committed Relaxed R1CS)
定义 12（承诺宽松 R1CS）

Consider a finite field $\mathbb{F}$ and a commitment scheme $\mathsf{C}\mathsf{o}\mathsf{m}$ over $\mathbb{F}$. Let the public parameters consist of size bounds $m,n,\ell \in \mathbb{N}$ where $m>\ell$, and commitment parameters ${\mathsf{p}\mathsf{p}}_{\mathsf{W}}$ and ${\mathsf{p}\mathsf{p}}_{\mathsf{E}}$ for vectors of size m and $m-\ell -1$ respectively. The committed relaxed R1CS structure consists of sparse matrices $A,B,C\in {\mathbb{F}}^{m\times m}$ with at most $n=\text{Ω}(m)$ non-zero entries in each matrix. A committed relaxed R1CS instance is a tuple $(\overline{E},u,\overline{W},\mathsf{x}\mathsf{)}$, where $\overline{E}$ and $\overline{W}$ are commitments, $u\in \mathbb{F}$, and $\mathsf{x}\in {\mathbb{F}}^{\ell }$ are public inputs and outputs. An instance $(\overline{E},u,\overline{W},\mathsf{x}\mathsf{)}$ is satisfied by a witness $(E,r_E,W,r_W)\in ({\mathbb{F}}^m,\mathbb{F},{\mathbb{F}}^{m-\ell -1},\mathbb{F})$ if $\overline{E}=\mathsf{C}\mathsf{o}\mathsf{m}\mathsf{(}{\mathsf{p}\mathsf{p}}_{\mathsf{E}}\mathsf{,}\mathsf{E}\mathsf{,}{\mathsf{r}}_{\mathsf{E}}\mathsf{)}$, $\overline{W}=\mathsf{C}\mathsf{o}\mathsf{m}\mathsf{(}{\mathsf{p}\mathsf{p}}_{\mathsf{W}}\mathsf{,}\mathsf{W}\mathsf{,}{\mathsf{r}}_{\mathsf{W}}\mathsf{)}$, and $(A\cdot Z)\circ (B\cdot Z)=u\cdot (C\cdot Z)+E$, where $Z=(W,\mathsf{x}\mathsf{,}\mathsf{u}\mathsf{)}$.
考虑一个有限域 $\mathbb{F}$ 和一个在 $\mathbb{F}$ 上的承诺方案 $\mathsf{C}\mathsf{o}\mathsf{m}$ 。公共参数由大小界限 $m,n,\ell \in \mathbb{N}$ 组成，其中 $m>\ell$ ，以及大小为 m 的向量的承诺参数 ${\mathsf{p}\mathsf{p}}_{\mathsf{W}}$ 和大小为 $m-\ell -1$ 的向量的承诺参数 ${\mathsf{p}\mathsf{p}}_{\mathsf{E}}$ 。已承诺的松弛 R1CS 结构由最多有 $n=\text{Ω}(m)$ 个非零元素的稀疏矩阵 $A,B,C\in {\mathbb{F}}^{m\times m}$ 组成。一个已承诺的松弛 R1CS 实例是一个元组 $(\overline{E},u,\overline{W},\mathsf{x}\mathsf{)}$ ，其中 $\overline{E}$ 和 $\overline{W}$ 是承诺， $u\in \mathbb{F}$ 和 $\mathsf{x}\in {\mathbb{F}}^{\ell }$ 是公共输入和输出。一个实例 $(\overline{E},u,\overline{W},\mathsf{x}\mathsf{)}$ 被一个见证 $(E,r_E,W,r_W)\in ({\mathbb{F}}^m,\mathbb{F},{\mathbb{F}}^{m-\ell -1},\mathbb{F})$ 满足，如果 $\overline{E}=\mathsf{C}\mathsf{o}\mathsf{m}\mathsf{(}{\mathsf{p}\mathsf{p}}_{\mathsf{E}}\mathsf{,}\mathsf{E}\mathsf{,}{\mathsf{r}}_{\mathsf{E}}\mathsf{)}$ ， $\overline{W}=\mathsf{C}\mathsf{o}\mathsf{m}\mathsf{(}{\mathsf{p}\mathsf{p}}_{\mathsf{W}}\mathsf{,}\mathsf{W}\mathsf{,}{\mathsf{r}}_{\mathsf{W}}\mathsf{)}$ ，和 $(A\cdot Z)\circ (B\cdot Z)=u\cdot (C\cdot Z)+E$ ，其中 $Z=(W,\mathsf{x}\mathsf{,}\mathsf{u}\mathsf{)}$ 。

Construction 1建设 1

(A Folding Scheme for Committed Relaxed R1CS). Consider a finite field $\mathbb{F}$ and a succinct, hiding, and homomorphic commitment scheme $\mathsf{C}\mathsf{o}\mathsf{m}$ over $\mathbb{F}$. We define the generator and the encoder as follows.
（针对承诺松弛 R1CS 的折叠方案）。考虑一个有限域 $\mathbb{F}$ 和一个简洁、隐藏和同态承诺方案 $\mathsf{C}\mathsf{o}\mathsf{m}$ 在 $\mathbb{F}$ 上。我们如下定义生成器和编码器。

• $\mathcal{G}(1^{\lambda })\to \mathsf{p}\mathsf{p}$: output size bounds $m,n,\ell \in \mathbb{N}$, and commitment parameters ${\mathsf{p}\mathsf{p}}_{\mathsf{W}}$ and ${\mathsf{p}\mathsf{p}}_{\mathsf{E}}$ for vectors of size m and $m-\ell -1$ respectively.
  $\mathcal{G}(1^{\lambda })\to \mathsf{p}\mathsf{p}$ : 输出大小边界 $m,n,\ell \in \mathbb{N}$ ，以及大小为 m 的向量和大小为 $m-\ell -1$ 的承诺参数 ${\mathsf{p}\mathsf{p}}_{\mathsf{W}}$ 和 ${\mathsf{p}\mathsf{p}}_{\mathsf{E}}$ 。

• $\mathcal{K}(\mathsf{p}\mathsf{p}\mathsf{,}\mathsf{(}\mathsf{A}\mathsf{,}\mathsf{B}\mathsf{,}\mathsf{C}\mathsf{)}\mathsf{)}\to \mathsf{(}\mathsf{p}\mathsf{k}\mathsf{,}\mathsf{v}\mathsf{k}\mathsf{)}$: output $\mathsf{p}\mathsf{k}\leftarrow \mathsf{(}\mathsf{p}\mathsf{p}\mathsf{,}\mathsf{(}\mathsf{A}\mathsf{,}\mathsf{B}\mathsf{,}\mathsf{C}\mathsf{)}\mathsf{)}$ and $\mathsf{v}\mathsf{k}\leftarrow \mathrm{\perp }$.
  $\mathcal{K}(\mathsf{p}\mathsf{p}\mathsf{,}\mathsf{(}\mathsf{A}\mathsf{,}\mathsf{B}\mathsf{,}\mathsf{C}\mathsf{)}\mathsf{)}\to \mathsf{(}\mathsf{p}\mathsf{k}\mathsf{,}\mathsf{v}\mathsf{k}\mathsf{)}$ : 输出 $\mathsf{p}\mathsf{k}\leftarrow \mathsf{(}\mathsf{p}\mathsf{p}\mathsf{,}\mathsf{(}\mathsf{A}\mathsf{,}\mathsf{B}\mathsf{,}\mathsf{C}\mathsf{)}\mathsf{)}$ 和 $\mathsf{v}\mathsf{k}\leftarrow \mathrm{\perp }$ 。

The verifier $\mathcal{V}$ takes two committed relaxed R1CS instances $({\overline{E}}_1,u_1,{\overline{W}}_1,{\mathsf{x}}_{\mathsf{1}}\mathsf{)}$ and $({\overline{E}}_2,u_2,{\overline{W}}_2,{\mathsf{x}}_{\mathsf{2}}\mathsf{)}$. The prover $\mathcal{P}$, in addition to the two instances, takes witnesses to both instances, $(E_1,r_{E_1},W_1,r_{W_1})$ and $(E_2,r_{E_2},W_2,r_{W_2})$. Let $Z_1=(W_1,{\mathsf{x}}_{\mathsf{1}}\mathsf{,}{\mathsf{u}}_{\mathsf{1}}\mathsf{)}$ and $Z_2=(W_2,{\mathsf{x}}_{\mathsf{2}}\mathsf{,}{\mathsf{u}}_{\mathsf{2}}\mathsf{)}$. The prover and the verifier proceed as follows.
验证者 $\mathcal{V}$ 接收两个提交的宽松 R1CS 实例 $({\overline{E}}_1,u_1,{\overline{W}}_1,{\mathsf{x}}_{\mathsf{1}}\mathsf{)}$ 和 $({\overline{E}}_2,u_2,{\overline{W}}_2,{\mathsf{x}}_{\mathsf{2}}\mathsf{)}$ 。除了这两个实例，证明者 $\mathcal{P}$ 还接收两个实例的见证， $(E_1,r_{E_1},W_1,r_{W_1})$ 和 $(E_2,r_{E_2},W_2,r_{W_2})$ 。设 $Z_1=(W_1,{\mathsf{x}}_{\mathsf{1}}\mathsf{,}{\mathsf{u}}_{\mathsf{1}}\mathsf{)}$ 和 $Z_2=(W_2,{\mathsf{x}}_{\mathsf{2}}\mathsf{,}{\mathsf{u}}_{\mathsf{2}}\mathsf{)}$ 。证明者和验证者按以下步骤进行。

• 1. $\mathcal{P}$: Send $\overline{T}:=\mathsf{C}\mathsf{o}\mathsf{m}\mathsf{(}{\mathsf{p}\mathsf{p}}_{\mathsf{E}}\mathsf{,}\mathsf{T}\mathsf{,}{\mathsf{r}}_{\mathsf{T}}\mathsf{)}$, where $r_T{\leftarrow }_R\mathbb{F}$ and with cross term
  $\mathcal{P}$ : 发送 $\overline{T}:=\mathsf{C}\mathsf{o}\mathsf{m}\mathsf{(}{\mathsf{p}\mathsf{p}}_{\mathsf{E}}\mathsf{,}\mathsf{T}\mathsf{,}{\mathsf{r}}_{\mathsf{T}}\mathsf{)}$ ，其中 $r_T{\leftarrow }_R\mathbb{F}$ 以及跨项

  $$\begin{array}{r}T=A{Z}_1\circ B{Z}_2+A{Z}_2\circ B{Z}_1-u_1\cdot C{Z}_2-u_2\cdot C{Z}_1.\end{array}$$

• 2. $\mathcal{V}$: Sample and send challenge $r{\leftarrow }_R\mathbb{F}$.
  $\mathcal{V}$ : 样本和发送挑战 $r{\leftarrow }_R\mathbb{F}$ 。

• 3. $\mathcal{V},\mathcal{P}$: Output the folded instance $(\overline{E},u,\overline{W},\mathsf{x}\mathsf{)}$ where
  输出折叠实例 $(\overline{E},u,\overline{W},\mathsf{x}\mathsf{)}$

  $$\begin{array}{r}\begin{array}{lllllll}\overline{E}& \leftarrow & {\overline{E}}_1& +& r\cdot \overline{T}& +& r^2\cdot {\overline{E}}_2\\ u& \leftarrow & u_1& +& r\cdot u_2& & \\ \overline{W}& \leftarrow & {\overline{W}}_1& +& r\cdot {\overline{W}}_2& & \\ \mathsf{x}& \leftarrow & {\mathsf{x}}_{\mathsf{1}}& +& r\cdot {\mathsf{x}}_{\mathsf{2}}& & \end{array}\end{array}$$

• 4. $\mathcal{P}$: Output the folded witness $(E,r_E,W,r_W)$, where
  输出折叠的见证者 $(E,r_E,W,r_W)$ ，其中

  $$\begin{array}{r}\begin{array}{lllllll}E& \leftarrow & E_1& +& r\cdot T& +& r^2\cdot E_2\\ r_E& \leftarrow & r_{E_1}& +& r\cdot r_T& +& r^2\cdot r_{E_2}\\ W& \leftarrow & W_1& +& r\cdot W_2& & \\ r_W& \leftarrow & r_{W_1}& +& r\cdot r_{W_2}& & \end{array}\end{array}$$

Theorem 3定理 3

(A Folding Scheme for Committed Relaxed R1CS). Construction 1 is a public-coin folding scheme for committed relaxed R1CS with perfect completeness, knowledge soundness, and zero-knowledge.
（承诺宽松 R1CS 的折叠方案）。构造 1 是一个具有完美完备性、知识正确性和零知识证明的公共币折叠方案。

Proof Intuition. With textbook algebra, we can show that if witnesses $(E_1,r_{E_1},$ $W_1,r_{W_1})$ and $(E_2,r_{E_2},W_2,r_{W_2})$ are satisfying witnesses, then the folded witness $(E,r_E,W,r_W)$ must be a satisfying witness. We prove knowledge soundness via the forking lemma (Lemma 1) by showing that the extractor can produce the initial witnesses given three accepting transcripts and the corresponding folded witnesses. Specifically, the extractor uses all three transcripts to compute $E_i$ and $r_{E_i}$, and any two transcripts to compute $W_i$ and $r_{W_i}$ for $i\in \{1,2\}$. The choice of which two transcripts does not matter due to the binding property of the commitment scheme. We present a formal proof in [30, App. B].    $◻$
证明直觉。使用教科书中的代数，我们可以证明如果见证者 $(E_1,r_{E_1},$ $W_1,r_{W_1})$ 和 $(E_2,r_{E_2},W_2,r_{W_2})$ 是满足见证者，那么折叠见证者 $(E,r_E,W,r_W)$ 必须是满足见证者。我们通过分叉引理（引理 1）证明知识健全性，通过展示提取器可以基于三个接受会话和相应的折叠见证者产生初始见证者。具体来说，提取器使用所有三个会话来计算 $E_i$ 和 $r_{E_i}$ ，以及任何两个会话来计算 $W_i$ 和 $r_{W_i}$ 以便计算 $i\in \{1,2\}$ 。由于承诺方案的绑定属性，选择哪两个会话并不重要。我们在 [ 30, 附录 B] 中提供了一个形式化的证明。 $◻$

4.2 Achieving Non-interactivity via the Fiat-Shamir Transform
4.2 通过法币-沙米尔变换实现非交互性

To design Nova’s IVC scheme, we require our folding scheme for committed relaxed R1CS to be non-interactive in the standard model. To do so we first achieve non-interactivity in the random oracle model using the (strong) Fiat-Shamir transform [22]. Next, we heuristically instantiate the random oracle using a cryptographic hash function. As a result, we can only heuristically argue the security of the resulting non-interactive folding scheme. Note that all existing IVC constructions in the standard model require instantiating the random oracle with a cryptographic hash function [12, 15, 21, 43].
为了设计 Nova 的 IVC 方案，我们需要我们的针对已提交的松弛 R1CS 的折叠方案在标准模型中是非交互式的。为此，我们首先使用（强）Fiat-Shamir 变换[22]在随机预言模型中实现非交互性。接下来，我们通过密码哈希函数启发式地实例化随机预言。因此，我们只能启发式地论证所得到的非交互式折叠方案的安全性。请注意，所有现有的标准模型中的 IVC 构造都需要使用密码哈希函数实例化随机预言[12, 15, 21, 43]。

Construction 2建设 2

(A Non-Interactive Folding Scheme). We achieve non-interactivity in the random oracle model using the strong Fiat-Shamir transform [22]. Let $\rho$ denote a random oracle sampled during parameter generation and provided to all parties. Let $(\mathsf{G},\mathsf{K}\mathsf{,}\mathsf{P}\mathsf{,}\mathsf{V}\mathsf{)}$ represent our interactive folding scheme (Construction 1). We construct a non-interactive folding scheme $(\mathcal{G},\mathcal{K},\mathcal{P},\mathcal{V})$ as follows:
(非交互式折叠方案)。我们通过使用强大的 Fiat-Shamir 变换[22]在随机预言模型中实现非交互性。令 $\rho$ 表示在参数生成期间采样的随机预言，并将其提供给所有参与者。令 $(\mathsf{G},\mathsf{K}\mathsf{,}\mathsf{P}\mathsf{,}\mathsf{V}\mathsf{)}$ 表示我们的交互式折叠方案（构造 1）。我们如下构造一个非交互式折叠方案 $(\mathcal{G},\mathcal{K},\mathcal{P},\mathcal{V})$ ：

• $\mathcal{G}(1^{\lambda })$: output $\mathsf{p}\mathsf{p}\leftarrow \mathsf{G}\mathsf{(}{\mathsf{1}}^{\lambda }\mathsf{)}$.
  $\mathcal{G}(1^{\lambda })$ : 输出 $\mathsf{p}\mathsf{p}\leftarrow \mathsf{G}\mathsf{(}{\mathsf{1}}^{\lambda }\mathsf{)}$ .

• $\mathcal{K}(\mathsf{p}\mathsf{p}\mathsf{,}\mathsf{(}\mathsf{A}\mathsf{,}\mathsf{B}\mathsf{,}\mathsf{C}\mathsf{)}\mathsf{)}$: $\mathsf{v}\mathsf{k}\leftarrow \rho \mathsf{(}\mathsf{p}\mathsf{p}\mathsf{,}\mathsf{s}\mathsf{)}$ and $\mathsf{p}\mathsf{k}\leftarrow \mathsf{(}\mathsf{p}\mathsf{p}\mathsf{,}\mathsf{(}\mathsf{A}\mathsf{,}\mathsf{B}\mathsf{,}\mathsf{C}\mathsf{)}\mathsf{,}\mathsf{v}\mathsf{k}\mathsf{)}$; output $(\mathsf{v}\mathsf{k}\mathsf{,}\mathsf{p}\mathsf{k}\mathsf{)}$.
  $\mathcal{K}(\mathsf{p}\mathsf{p}\mathsf{,}\mathsf{(}\mathsf{A}\mathsf{,}\mathsf{B}\mathsf{,}\mathsf{C}\mathsf{)}\mathsf{)}$ : $\mathsf{v}\mathsf{k}\leftarrow \rho \mathsf{(}\mathsf{p}\mathsf{p}\mathsf{,}\mathsf{s}\mathsf{)}$ 以及 $\mathsf{p}\mathsf{k}\leftarrow \mathsf{(}\mathsf{p}\mathsf{p}\mathsf{,}\mathsf{(}\mathsf{A}\mathsf{,}\mathsf{B}\mathsf{,}\mathsf{C}\mathsf{)}\mathsf{,}\mathsf{v}\mathsf{k}\mathsf{)}$ ; 输出 $(\mathsf{v}\mathsf{k}\mathsf{,}\mathsf{p}\mathsf{k}\mathsf{)}$ .

• $\mathcal{P}(\mathsf{p}\mathsf{k}\mathsf{,}\mathsf{(}{\mathsf{u}}_{\mathsf{1}}\mathsf{,}{\mathsf{w}}_{\mathsf{1}}\mathsf{)}\mathsf{,}\mathsf{(}{\mathsf{u}}_{\mathsf{2}}\mathsf{,}{\mathsf{w}}_{\mathsf{2}}\mathsf{)}\mathsf{)}$: runs $\mathsf{P}\mathsf{(}\mathsf{(}\mathsf{p}\mathsf{k}\mathsf{.}\mathsf{p}\mathsf{p}\mathsf{,}\mathsf{p}\mathsf{k}\mathsf{.}\mathsf{(}\mathsf{A}\mathsf{,}\mathsf{B}\mathsf{,}\mathsf{C}\mathsf{)}\mathsf{)}$ to retrieve its first message $\overline{T}$, and sends $\overline{T}$ to $\mathcal{V}$; computes $r\leftarrow \rho (\mathsf{v}\mathsf{k}\mathsf{,}{\mathsf{u}}_{\mathsf{1}}\mathsf{,}{\mathsf{u}}_{\mathsf{2}}\mathsf{,}\overline{\mathsf{T}}\mathsf{)}$, forwards this to $\mathsf{P}$, and outputs the resulting output.
  $\mathcal{P}(\mathsf{p}\mathsf{k}\mathsf{,}\mathsf{(}{\mathsf{u}}_{\mathsf{1}}\mathsf{,}{\mathsf{w}}_{\mathsf{1}}\mathsf{)}\mathsf{,}\mathsf{(}{\mathsf{u}}_{\mathsf{2}}\mathsf{,}{\mathsf{w}}_{\mathsf{2}}\mathsf{)}\mathsf{)}$ : 运行 $\mathsf{P}\mathsf{(}\mathsf{(}\mathsf{p}\mathsf{k}\mathsf{.}\mathsf{p}\mathsf{p}\mathsf{,}\mathsf{p}\mathsf{k}\mathsf{.}\mathsf{(}\mathsf{A}\mathsf{,}\mathsf{B}\mathsf{,}\mathsf{C}\mathsf{)}\mathsf{)}$ 以获取其第一条消息 $\overline{T}$ ，并发送 $\overline{T}$ 到 $\mathcal{V}$ ；计算 $r\leftarrow \rho (\mathsf{v}\mathsf{k}\mathsf{,}{\mathsf{u}}_{\mathsf{1}}\mathsf{,}{\mathsf{u}}_{\mathsf{2}}\mathsf{,}\overline{\mathsf{T}}\mathsf{)}$ ，将此转发到 $\mathsf{P}$ ，并输出结果。

• $\mathcal{V}(\mathsf{v}\mathsf{k}\mathsf{,}{\mathsf{u}}_{\mathsf{1}}\mathsf{,}{\mathsf{u}}_{\mathsf{2}}\mathsf{,}\overline{\mathsf{T}}\mathsf{)}$: runs $\mathsf{V}$ with $\overline{T}$ as the message from the prover and with randomness $r\leftarrow \rho (\mathsf{v}\mathsf{k}\mathsf{,}{\mathsf{u}}_{\mathsf{1}}\mathsf{,}{\mathsf{u}}_{\mathsf{2}}\mathsf{,}\overline{\mathsf{T}}\mathsf{)}$, and outputs the resulting output.
  $\mathcal{V}(\mathsf{v}\mathsf{k}\mathsf{,}{\mathsf{u}}_{\mathsf{1}}\mathsf{,}{\mathsf{u}}_{\mathsf{2}}\mathsf{,}\overline{\mathsf{T}}\mathsf{)}$ : 运行 $\mathsf{V}$ ，使用来自验证者的消息 $\overline{T}$ 和随机性 $r\leftarrow \rho (\mathsf{v}\mathsf{k}\mathsf{,}{\mathsf{u}}_{\mathsf{1}}\mathsf{,}{\mathsf{u}}_{\mathsf{2}}\mathsf{,}\overline{\mathsf{T}}\mathsf{)}$ ，并输出结果。

Assumption 1假设 1

(RO instantiation). Construction 2 is a non-interactive folding scheme that satisfies completeness, knowledge soundness, and zero-knowledge in the standard model when $\rho$ is instantiated with a cryptographic hash function.
(RO 实例化). 构造 2 是一种非交互式折叠方案，当使用密码哈希函数实例化 $\rho$ 时，在标准模型中满足完备性、知识正确性和零知识。

5 Nova: An IVC Scheme with Proof Compression
5 新诺瓦：一种带有证明压缩的 IVC 方案

This section describes Nova, an IVC scheme designed from a non-interactive folding scheme, which when instantiated with any additively-homomorphic commitment scheme with succinct commitments achieves the claimed efficiency (Lemma 4). In addition, Nova incorporates an efficient zkSNARK to prove the knowledge of valid IVC proofs succinctly and in zero-knowledge, providing a succinct, zero-knowledge proof of knowledge of a valid IVC proof.
本节描述了 Nova，这是一个非交互式折叠方案设计的 IVC 方案，当与任何具有简洁承诺的加法同态承诺方案实例化时，实现了所声称的效率（引理 4）。此外，Nova 集成了高效的 zkSNARK，用于简洁且零知识地证明有效 IVC 证明的知识，提供了一个有效 IVC 证明知识的简洁、零知识证明。

In Nova, at each incremental step, the prover folds a particular step of the incremental computation (represented as a committed relaxed R1CS instance-witness pair) into a running committed relaxed R1CS instance-witness pair. At any step in the incremental computation, a valid “IVC proof”, in a nutshell, is a satisfying witness of the running committed relaxed R1CS instance (which an honest prover can compute by folding witnesses associated with each step of the incremental computation) along with the running committed relaxed R1CS instance. Furthermore, at any incremental step, Nova’s prover can prove in zero-knowledge and with a succinct proof—using a variant of an existing zkSNARK [38] (Sect. 6)—that it knows a valid IVC proof (i.e., a satisfying witness) to the running committed relaxed R1CS instance (Construction 4).
在 Nova 中，在每一步增量步骤中，验证者将增量计算的一个特定步骤（表示为提交的放松 R1CS 实例-见证对）折叠到一个正在运行的提交的放松 R1CS 实例-见证对中。在增量计算的任何步骤中，一个有效的“IVC 证明”，简而言之，是运行中的提交的放松 R1CS 实例的满足见证（一个诚实的验证者可以通过折叠与增量计算每个步骤相关的见证来计算）以及运行中的提交的放松 R1CS 实例。此外，在任何增量步骤中，Nova 的验证者可以使用现有 zkSNARK [38]（第 6 节）的一个变体，在零知识下并以简洁的证明方式证明它知道一个有效的 IVC 证明（即满足见证）到运行中的提交的放松 R1CS 实例（构造 4）。

Note that Nova is not a zero-knowledge IVC scheme, as that would additionally require an IVC proof to be zero-knowledge (in Nova’s case, an IVC proof does not hide witnesses associated with steps of the incremental computation). This difference is immaterial in the context of a single prover since it can use Nova’s auxiliary zkSNARK to provide a zero-knowledge proof of knowledge of a valid IVC proof; we leave it to future work to achieve zero-knowledge IVC.
请注意，Nova 不是一个零知识 IVC 方案，因为那还需要 IVC 证明是零知识的（在 Nova 的情况下，IVC 证明不会隐藏与增量计算步骤相关的证人）。这种差异在单个证明者的上下文中无关紧要，因为它可以使用 Nova 的辅助 zkSNARK 提供关于有效 IVC 证明的知识零知识证明；我们将实现零知识 IVC 留待未来的工作。

5.1 Constructing IVC from a Folding Scheme for $\mathsf{N}\mathsf{P}$
5.1 从折叠方案构建 IVC

Recall that an IVC scheme allows a prover to show that $z_n=F^{(n)}(z_0)$ for some count n, initial input $z_0$, and output $z_n$. We now show how to construct an IVC scheme for a non-deterministic, polynomial-time computable function F using our non-interactive folding scheme for committed relaxed R1CS (Construction 2).⁵
回忆一下，一个 IVC 方案允许证明者展示对于某个计数 n，初始输入 $z_0$ ，以及输出 $z_n$ ， $z_n=F^{(n)}(z_0)$ 。我们现在展示如何使用我们的非交互式折叠方案为提交的放松 R1CS（构造 2）构造一个非确定性多项式时间可计算函数 F 的 IVC 方案。 ⁵

In our construction, as in a SNARK-based IVC, the prover uses an augmented function $F^{\prime }$ (Fig. 4), which, in addition to invoking F, performs additional bookkeeping to fold proofs of prior invocations of itself.
在我们的构造中，就像基于 SNARK 的 IVC 一样，验证者使用一个增强函数 $F^{\prime }$ （图 4），除了调用 F 之外，还执行额外的簿记操作，以折叠之前自身调用的证明。

We first describe a simplified version of $F^{\prime }$, to provide intuition. $F^{\prime }$ takes as non-deterministic advice two committed relaxed R1CS instances ${\mathsf{u}}_{\mathsf{i}}$ and ${\mathsf{U}}_{\mathsf{i}}$. Suppose that ${\mathsf{U}}_{\mathsf{i}}$ represents the correct execution of invocations $1,\dots ,i-1$ of $F^{\prime }$ so long as ${\mathsf{u}}_{\mathsf{i}}$ represents the correct execution of invocation i of $F^{\prime }$. $F^{\prime }$ performs two tasks. First, it executes a step of the incremental computation: instance ${\mathsf{u}}_{\mathsf{i}}$ contains $z_i$ which $F^{\prime }$ uses to output $z_{i+1}=F(z_i)$. Second, $F^{\prime }$ invokes the verifier of the non-interactive folding scheme to fold the task of checking ${\mathsf{u}}_{\mathsf{i}}$ and ${\mathsf{U}}_{\mathsf{i}}$ into the task of checking a single instance ${\mathsf{U}}_{\mathsf{i}\mathsf{+}\mathsf{1}}$. The IVC prover then computes a new instance ${\mathsf{u}}_{\mathsf{i}\mathsf{+}\mathsf{1}}$ which attests to the correct execution of invocation $i+1$ of $F^{\prime }$, thereby attesting that $z_{i+1}=F(z_i)$ and ${\mathsf{U}}_{\mathsf{i}\mathsf{+}\mathsf{1}}$ is the result of folding ${\mathsf{u}}_{\mathsf{i}}$ and ${\mathsf{U}}_{\mathsf{i}}$. Now, we have that ${\mathsf{U}}_{\mathsf{i}\mathsf{+}\mathsf{1}}$ represents the correct execution of invocations $1,\dots ,i$ of $F^{\prime }$ so long as ${\mathsf{u}}_{\mathsf{i}\mathsf{+}\mathsf{1}}$ represents the correct execution of invocation $i+1$ of $F^{\prime }$.
首先描述了 $F^{\prime }$ 的简化版本，以提供直观感受。 $F^{\prime }$ 将两个提交的宽松 R1CS 实例 ${\mathsf{u}}_{\mathsf{i}}$ 和 ${\mathsf{U}}_{\mathsf{i}}$ 作为非确定性建议。假设 ${\mathsf{U}}_{\mathsf{i}}$ 代表 $1,\dots ,i-1$ 的调用 $F^{\prime }$ 的正确执行，只要 ${\mathsf{u}}_{\mathsf{i}}$ 代表调用 i 的 $F^{\prime }$ 的正确执行。 $F^{\prime }$ 执行两个任务。首先，它执行增量计算的步骤：实例 ${\mathsf{u}}_{\mathsf{i}}$ 包含 $z_i$ ，它使用 $F^{\prime }$ 输出 $z_{i+1}=F(z_i)$ 。其次， $F^{\prime }$ 调用非交互折叠方案的验证器，将检查 ${\mathsf{u}}_{\mathsf{i}}$ 和 ${\mathsf{U}}_{\mathsf{i}}$ 的任务折叠成检查单个实例 ${\mathsf{U}}_{\mathsf{i}\mathsf{+}\mathsf{1}}$ 的任务。IVC 证明器随后计算一个新的实例 ${\mathsf{u}}_{\mathsf{i}\mathsf{+}\mathsf{1}}$ ，证明调用 $i+1$ 的 $F^{\prime }$ 的正确执行，从而证明 $z_{i+1}=F(z_i)$ 和 ${\mathsf{U}}_{\mathsf{i}\mathsf{+}\mathsf{1}}$ 是折叠 ${\mathsf{u}}_{\mathsf{i}}$ 和 ${\mathsf{U}}_{\mathsf{i}}$ 的结果。现在，我们有 ${\mathsf{U}}_{\mathsf{i}\mathsf{+}\mathsf{1}}$ 代表调用 $1,\dots ,i$ 的 $F^{\prime }$ 的正确执行，只要 ${\mathsf{u}}_{\mathsf{i}\mathsf{+}\mathsf{1}}$ 代表调用 $i+1$ 的 $F^{\prime }$ 的正确执行。

The above description glossed over a subtle discrepancy: Because $F^{\prime }$ must output the running instance ${\mathsf{U}}_{\mathsf{i}\mathsf{+}\mathsf{1}}$ for the next invocation to use, it is contained in ${\mathsf{u}}_{\mathsf{i}\mathsf{+}\mathsf{1}}\mathsf{.}\mathsf{x}$ (i.e., the public IO of ${\mathsf{u}}_{\mathsf{i}\mathsf{+}\mathsf{1}}$). But, in the next iteration, $F^{\prime }$ must fold ${\mathsf{u}}_{\mathsf{i}\mathsf{+}\mathsf{1}}\mathsf{.}\mathsf{x}$ into ${\mathsf{U}}_{\mathsf{i}\mathsf{+}\mathsf{1}}\mathsf{.}\mathsf{x}$, meaning that $F^{\prime }$ is stuck trying to squeeze ${\mathsf{U}}_{\mathsf{i}\mathsf{+}\mathsf{1}}$ into ${\mathsf{U}}_{\mathsf{i}\mathsf{+}\mathsf{1}}\mathsf{.}\mathsf{x}$. To handle this inconsistency, we modify $F^{\prime }$ to output a collision-resistant hash of its public IO rather than producing it directly (this ensures that the public IO of $F^{\prime }$ is a constant number of finite field elements). The next invocation of $F^{\prime }$ then additionally takes the preimage of this hash as non-deterministic advice. We assume that the hash function takes an additional random input (which provides hiding) but for notational convenience we do not explicitly depict this.
上述描述略过了细微的差异：因为 $F^{\prime }$ 必须输出运行实例 ${\mathsf{U}}_{\mathsf{i}\mathsf{+}\mathsf{1}}$ 以便下一次调用使用，它包含在 ${\mathsf{u}}_{\mathsf{i}\mathsf{+}\mathsf{1}}\mathsf{.}\mathsf{x}$ （即 ${\mathsf{u}}_{\mathsf{i}\mathsf{+}\mathsf{1}}$ 的公共 IO 中）。但是，在下一次迭代中， $F^{\prime }$ 必须将 ${\mathsf{u}}_{\mathsf{i}\mathsf{+}\mathsf{1}}\mathsf{.}\mathsf{x}$ 折叠到 ${\mathsf{U}}_{\mathsf{i}\mathsf{+}\mathsf{1}}\mathsf{.}\mathsf{x}$ 中，这意味着 $F^{\prime }$ 卡在试图将 ${\mathsf{U}}_{\mathsf{i}\mathsf{+}\mathsf{1}}$ 挤压到 ${\mathsf{U}}_{\mathsf{i}\mathsf{+}\mathsf{1}}\mathsf{.}\mathsf{x}$ 中。为了处理这种不一致性，我们修改 $F^{\prime }$ 以输出其公共 IO 的碰撞抵抗哈希，而不是直接产生它（这确保了 $F^{\prime }$ 的公共 IO 是有限域中的固定数量的元素）。下一次调用 $F^{\prime }$ 时，还额外采用这个哈希的预像作为非确定性建议。我们假设哈希函数接受额外的随机输入（这提供了隐藏），但为了书写方便，我们没有明确表示这一点。

Producing IVC Proofs. Let $({\mathsf{u}}_{\mathrm{\perp }}\mathsf{,}{\mathsf{w}}_{\mathrm{\perp }}\mathsf{)}$ be the trivially satisfying instance-witness pair, where E, W,  and $\mathsf{x}$ are appropriately-sized zero vectors, $r_E=0$, $r_W=0$, and $\overline{E}$ and $\overline{W}$ are commitments of E and W respectively.
生成 IVC 证明。令 $({\mathsf{u}}_{\mathrm{\perp }}\mathsf{,}{\mathsf{w}}_{\mathrm{\perp }}\mathsf{)}$ 为平凡满足的实例-证人对，其中 E、W 和 $\mathsf{x}$ 是适当大小的零向量， $r_E=0$ 、 $r_W=0$ 、 $\overline{E}$ 和 $\overline{W}$ 分别是 E 和 W 的承诺。

Fig. 4.图 4

Overview of $F^{\prime }$. $F^{\prime }$ represented as a committed relaxed R1CS instance ${\mathsf{u}}_{\mathsf{i}\mathsf{+}\mathsf{1}}$ encodes the statement that there exists $((i,z_0,z_i,{\mathsf{u}}_{\mathsf{i}}\mathsf{,}{\mathsf{U}}_{\mathsf{i}}\mathsf{)}\mathsf{,}{\mathsf{U}}_{\mathsf{i}\mathsf{+}\mathsf{1}}\mathsf{,}\overline{\mathsf{T}}\mathsf{)}$ such that ${\mathsf{u}}_{\mathsf{i}}\mathsf{.}\mathsf{x}\mathsf{=}\mathsf{h}\mathsf{a}\mathsf{s}\mathsf{h}\mathsf{(}\mathsf{v}\mathsf{k}\mathsf{,}\mathsf{i}\mathsf{,}{\mathsf{z}}_{\mathsf{0}}\mathsf{,}{\mathsf{z}}_{\mathsf{i}}\mathsf{,}{\mathsf{U}}_{\mathsf{i}}\mathsf{)}$, $h_{i+1}=\mathsf{h}\mathsf{a}\mathsf{s}\mathsf{h}\mathsf{(}\mathsf{v}\mathsf{k}\mathsf{,}\mathsf{i}\mathsf{+}\mathsf{1}\mathsf{,}{\mathsf{z}}_{\mathsf{0}}\mathsf{,}\mathsf{F}\mathsf{(}{\mathsf{z}}_{\mathsf{i}}\mathsf{)}\mathsf{,}{\mathsf{U}}_{\mathsf{i}\mathsf{+}\mathsf{1}}\mathsf{)}$, ${\mathsf{U}}_{\mathsf{i}\mathsf{+}\mathsf{1}}\mathsf{=}\mathsf{N}\mathsf{I}\mathsf{F}\mathsf{S}\mathsf{.}\mathsf{V}\mathsf{(}\mathsf{v}\mathsf{k}\mathsf{,}{\mathsf{U}}_{\mathsf{i}}\mathsf{,}{\mathsf{u}}_{\mathsf{i}}\mathsf{,}\overline{\mathsf{T}}\mathsf{)}$, and that $F^{\prime }$ outputs $h_{i+1}$. The diagram omits depicting $\mathsf{v}\mathsf{k}$, $\omega$, and $\overline{T}$.
概述： $F^{\prime }$ . $F^{\prime }$ 以承诺的松弛 R1CS 实例 ${\mathsf{u}}_{\mathsf{i}\mathsf{+}\mathsf{1}}$ 编码存在 $((i,z_0,z_i,{\mathsf{u}}_{\mathsf{i}}\mathsf{,}{\mathsf{U}}_{\mathsf{i}}\mathsf{)}\mathsf{,}{\mathsf{U}}_{\mathsf{i}\mathsf{+}\mathsf{1}}\mathsf{,}\overline{\mathsf{T}}\mathsf{)}$ 的陈述，使得 ${\mathsf{u}}_{\mathsf{i}}\mathsf{.}\mathsf{x}\mathsf{=}\mathsf{h}\mathsf{a}\mathsf{s}\mathsf{h}\mathsf{(}\mathsf{v}\mathsf{k}\mathsf{,}\mathsf{i}\mathsf{,}{\mathsf{z}}_{\mathsf{0}}\mathsf{,}{\mathsf{z}}_{\mathsf{i}}\mathsf{,}{\mathsf{U}}_{\mathsf{i}}\mathsf{)}$ ， $h_{i+1}=\mathsf{h}\mathsf{a}\mathsf{s}\mathsf{h}\mathsf{(}\mathsf{v}\mathsf{k}\mathsf{,}\mathsf{i}\mathsf{+}\mathsf{1}\mathsf{,}{\mathsf{z}}_{\mathsf{0}}\mathsf{,}\mathsf{F}\mathsf{(}{\mathsf{z}}_{\mathsf{i}}\mathsf{)}\mathsf{,}{\mathsf{U}}_{\mathsf{i}\mathsf{+}\mathsf{1}}\mathsf{)}$ ， ${\mathsf{U}}_{\mathsf{i}\mathsf{+}\mathsf{1}}\mathsf{=}\mathsf{N}\mathsf{I}\mathsf{F}\mathsf{S}\mathsf{.}\mathsf{V}\mathsf{(}\mathsf{v}\mathsf{k}\mathsf{,}{\mathsf{U}}_{\mathsf{i}}\mathsf{,}{\mathsf{u}}_{\mathsf{i}}\mathsf{,}\overline{\mathsf{T}}\mathsf{)}$ ，并且输出 $F^{\prime }$ $h_{i+1}$ 。图例省略了 $\mathsf{v}\mathsf{k}$ ， $\omega$ ，和 $\overline{T}$ 的描述。

Now, in iteration $i+1$, the IVC prover runs $F^{\prime }$ and computes ${\mathsf{u}}_{\mathsf{i}\mathsf{+}\mathsf{1}}$ and ${\mathsf{U}}_{\mathsf{i}\mathsf{+}\mathsf{1}}$ as well as the corresponding witnesses ${\mathsf{w}}_{\mathsf{i}\mathsf{+}\mathsf{1}}$ and ${\mathsf{W}}_{\mathsf{i}\mathsf{+}\mathsf{1}}$. Because ${\mathsf{u}}_{\mathsf{i}\mathsf{+}\mathsf{1}}$ and ${\mathsf{U}}_{\mathsf{i}\mathsf{+}\mathsf{1}}$ together attest to the correctness of $i+1$ invocations of $F^{\prime }$ (which indirectly attests to $i+1$ invocations of F) the IVC proof ${\text{Π}}_{i+1}$ is $(({\mathsf{U}}_{\mathsf{i}\mathsf{+}\mathsf{1}}\mathsf{,}{\mathsf{W}}_{\mathsf{i}\mathsf{+}\mathsf{1}}\mathsf{)}\mathsf{,}\mathsf{(}{\mathsf{u}}_{\mathsf{i}\mathsf{+}\mathsf{1}}\mathsf{,}{\mathsf{w}}_{\mathsf{i}\mathsf{+}\mathsf{1}}\mathsf{)}\mathsf{)}$. Moreover, succinctness is maintained by the properties of the underlying folding scheme. We formally describe our construction below.
现在，在迭代 $i+1$ 中，IVC 证明器运行 $F^{\prime }$ 并计算 ${\mathsf{u}}_{\mathsf{i}\mathsf{+}\mathsf{1}}$ 和 ${\mathsf{U}}_{\mathsf{i}\mathsf{+}\mathsf{1}}$ 以及相应的证人 ${\mathsf{w}}_{\mathsf{i}\mathsf{+}\mathsf{1}}$ 和 ${\mathsf{W}}_{\mathsf{i}\mathsf{+}\mathsf{1}}$ 。因为 ${\mathsf{u}}_{\mathsf{i}\mathsf{+}\mathsf{1}}$ 和 ${\mathsf{U}}_{\mathsf{i}\mathsf{+}\mathsf{1}}$ 共同证明了 $i+1$ 对 $F^{\prime }$ 的调用正确性（这间接证明了 $i+1$ 对 F 的调用正确性），所以 IVC 证明 ${\text{Π}}_{i+1}$ 是 $(({\mathsf{U}}_{\mathsf{i}\mathsf{+}\mathsf{1}}\mathsf{,}{\mathsf{W}}_{\mathsf{i}\mathsf{+}\mathsf{1}}\mathsf{)}\mathsf{,}\mathsf{(}{\mathsf{u}}_{\mathsf{i}\mathsf{+}\mathsf{1}}\mathsf{,}{\mathsf{w}}_{\mathsf{i}\mathsf{+}\mathsf{1}}\mathsf{)}\mathsf{)}$ 。此外，通过底层折叠方案的性质，保持了简洁性。我们下面将正式描述我们的构造。

Construction 3 (IVC)建设 3（IVC）

[IVC] Let $\mathsf{N}\mathsf{I}\mathsf{F}\mathsf{S}\mathsf{=}\mathsf{(}\mathsf{G}\mathsf{,}\mathsf{K}\mathsf{,}\mathsf{P}\mathsf{,}\mathsf{V}\mathsf{)}$ be the non-interactive folding scheme for committed relaxed R1CS (Construction 2). Consider a polynomial-time function F that takes non-deterministic input, and a cryptographic hash function $\mathsf{h}\mathsf{a}\mathsf{s}\mathsf{h}$. We define our augmented function $F^{\prime }$ as follows (all arguments to $F^{\prime }$ are taken as non-deterministic advice):
[IVC] 设 $\mathsf{N}\mathsf{I}\mathsf{F}\mathsf{S}\mathsf{=}\mathsf{(}\mathsf{G}\mathsf{,}\mathsf{K}\mathsf{,}\mathsf{P}\mathsf{,}\mathsf{V}\mathsf{)}$ 为针对提交的宽松 R1CS（构造 2）的非交互折叠方案。考虑一个接受非确定性输入的多项式时间函数 F 和一个密码学哈希函数 $\mathsf{h}\mathsf{a}\mathsf{s}\mathsf{h}$ 。我们定义我们的增强函数 $F^{\prime }$ 如下（所有输入到 $F^{\prime }$ 的参数均视为非确定性建议）：

$\underset{\_}{F^{\prime }(\mathsf{v}\mathsf{k}\mathsf{,}{\mathsf{U}}_{\mathsf{i}}\mathsf{,}{\mathsf{u}}_{\mathsf{i}}\mathsf{,}\mathsf{(}\mathsf{i}\mathsf{,}{\mathsf{z}}_{\mathsf{0}}\mathsf{,}{\mathsf{z}}_{\mathsf{i}}\mathsf{)}\mathsf{,}{\omega }_{\mathsf{i}}\mathsf{,}\overline{\mathsf{T}}\mathsf{)}\to \mathsf{x}}$:

If i is 0, output $\mathsf{h}\mathsf{a}\mathsf{s}\mathsf{h}\mathsf{(}\mathsf{v}\mathsf{k}\mathsf{,}\mathsf{1}\mathsf{,}{\mathsf{z}}_{\mathsf{0}}\mathsf{,}\mathsf{F}\mathsf{(}{\mathsf{z}}_{\mathsf{0}}\mathsf{,}{\omega }_{\mathsf{i}}\mathsf{)}\mathsf{,}{\mathsf{u}}_{\mathrm{\perp }}\mathsf{)}$;
如果 i 为 0，输出 $\mathsf{h}\mathsf{a}\mathsf{s}\mathsf{h}\mathsf{(}\mathsf{v}\mathsf{k}\mathsf{,}\mathsf{1}\mathsf{,}{\mathsf{z}}_{\mathsf{0}}\mathsf{,}\mathsf{F}\mathsf{(}{\mathsf{z}}_{\mathsf{0}}\mathsf{,}{\omega }_{\mathsf{i}}\mathsf{)}\mathsf{,}{\mathsf{u}}_{\mathrm{\perp }}\mathsf{)}$ ;

otherwise, 否则，

• (1) check that ${\mathsf{u}}_{\mathsf{i}}\mathsf{.}\mathsf{x}\mathsf{=}\mathsf{h}\mathsf{a}\mathsf{s}\mathsf{h}\mathsf{(}\mathsf{v}\mathsf{k}\mathsf{,}\mathsf{i}\mathsf{,}{\mathsf{z}}_{\mathsf{0}}\mathsf{,}{\mathsf{z}}_{\mathsf{i}}\mathsf{,}{\mathsf{U}}_{\mathsf{i}}\mathsf{)}$, where ${\mathsf{u}}_{\mathsf{i}}\mathsf{.}\mathsf{x}$ is the public IO of ${\mathsf{u}}_{\mathsf{i}}$,
  检查 ${\mathsf{u}}_{\mathsf{i}}\mathsf{.}\mathsf{x}\mathsf{=}\mathsf{h}\mathsf{a}\mathsf{s}\mathsf{h}\mathsf{(}\mathsf{v}\mathsf{k}\mathsf{,}\mathsf{i}\mathsf{,}{\mathsf{z}}_{\mathsf{0}}\mathsf{,}{\mathsf{z}}_{\mathsf{i}}\mathsf{,}{\mathsf{U}}_{\mathsf{i}}\mathsf{)}$ ，其中 ${\mathsf{u}}_{\mathsf{i}}\mathsf{.}\mathsf{x}$ 是 ${\mathsf{u}}_{\mathsf{i}}$ 的公共 IO

• (2) check that $({\mathsf{u}}_{\mathsf{i}}\mathsf{.}\overline{\mathsf{E}}\mathsf{,}{\mathsf{u}}_{\mathsf{i}}\mathsf{.}\mathsf{u}\mathsf{)}\mathsf{=}\mathsf{(}{\mathsf{u}}_{\mathrm{\perp }}\mathsf{.}\overline{\mathsf{E}}\mathsf{,}\mathsf{1}\mathsf{)}$,
  检查 $({\mathsf{u}}_{\mathsf{i}}\mathsf{.}\overline{\mathsf{E}}\mathsf{,}{\mathsf{u}}_{\mathsf{i}}\mathsf{.}\mathsf{u}\mathsf{)}\mathsf{=}\mathsf{(}{\mathsf{u}}_{\mathrm{\perp }}\mathsf{.}\overline{\mathsf{E}}\mathsf{,}\mathsf{1}\mathsf{)}$ ，

• (3) compute ${\mathsf{U}}_{\mathsf{i}\mathsf{+}\mathsf{1}}\leftarrow \mathsf{N}\mathsf{I}\mathsf{F}\mathsf{S}\mathsf{.}\mathsf{V}\mathsf{(}\mathsf{v}\mathsf{k}\mathsf{,}\mathsf{U}\mathsf{,}\mathsf{u}\mathsf{,}\overline{\mathsf{T}}\mathsf{)}$, and
  计算 ${\mathsf{U}}_{\mathsf{i}\mathsf{+}\mathsf{1}}\leftarrow \mathsf{N}\mathsf{I}\mathsf{F}\mathsf{S}\mathsf{.}\mathsf{V}\mathsf{(}\mathsf{v}\mathsf{k}\mathsf{,}\mathsf{U}\mathsf{,}\mathsf{u}\mathsf{,}\overline{\mathsf{T}}\mathsf{)}$ ，和

• (4) output $\mathsf{h}\mathsf{a}\mathsf{s}\mathsf{h}\mathsf{(}\mathsf{v}\mathsf{k}\mathsf{,}\mathsf{i}\mathsf{+}\mathsf{1}\mathsf{,}{\mathsf{z}}_{\mathsf{0}}\mathsf{,}\mathsf{F}\mathsf{(}{\mathsf{z}}_{\mathsf{i}}\mathsf{,}{\omega }_{\mathsf{i}}\mathsf{)}\mathsf{,}{\mathsf{U}}_{\mathsf{i}\mathsf{+}\mathsf{1}}\mathsf{)}$.输出 $\mathsf{h}\mathsf{a}\mathsf{s}\mathsf{h}\mathsf{(}\mathsf{v}\mathsf{k}\mathsf{,}\mathsf{i}\mathsf{+}\mathsf{1}\mathsf{,}{\mathsf{z}}_{\mathsf{0}}\mathsf{,}\mathsf{F}\mathsf{(}{\mathsf{z}}_{\mathsf{i}}\mathsf{,}{\omega }_{\mathsf{i}}\mathsf{)}\mathsf{,}{\mathsf{U}}_{\mathsf{i}\mathsf{+}\mathsf{1}}\mathsf{)}$ .

Because $F^{\prime }$ can be computed in polynomial time, it can be represented as a committed relaxed R1CS structure ${\mathsf{s}}_{{\mathsf{F}}^{\prime }}$. Let
因为 $F^{\prime }$ 可以在多项式时间内计算，它可以表示为一个承诺的松弛 R1CS 结构 ${\mathsf{s}}_{{\mathsf{F}}^{\prime }}$ 。

$$({\mathsf{u}}_{\mathsf{i}\mathsf{+}\mathsf{1}}\mathsf{,}{\mathsf{w}}_{\mathsf{i}\mathsf{+}\mathsf{1}}\mathsf{)}\leftarrow \mathsf{t}\mathsf{r}\mathsf{a}\mathsf{c}\mathsf{e}\mathsf{(}{\mathsf{F}}^{\prime }\mathsf{,}\mathsf{(}\mathsf{v}\mathsf{k}\mathsf{,}{\mathsf{U}}_{\mathsf{i}}\mathsf{,}{\mathsf{u}}_{\mathsf{i}}\mathsf{,}\mathsf{(}\mathsf{i}\mathsf{,}{\mathsf{z}}_{\mathsf{0}}\mathsf{,}{\mathsf{z}}_{\mathsf{i}}\mathsf{)}\mathsf{,}{\omega }_{\mathsf{i}}\mathsf{,}\overline{\mathsf{T}}\mathsf{)}\mathsf{)}$$

denote the satisfying committed relaxed R1CS instance-witness pair $({\mathsf{u}}_{\mathsf{i}\mathsf{+}\mathsf{1}}\mathsf{,}{\mathsf{w}}_{\mathsf{i}\mathsf{+}\mathsf{1}}\mathsf{)}$ for the execution of $F^{\prime }$ on non-deterministic advice $(\mathsf{v}\mathsf{k}\mathsf{,}{\mathsf{U}}_{\mathsf{i}}\mathsf{,}{\mathsf{u}}_{\mathsf{i}}\mathsf{,}\mathsf{(}\mathsf{i}\mathsf{,}{\mathsf{z}}_{\mathsf{0}}\mathsf{,}{\mathsf{z}}_{\mathsf{i}}\mathsf{)}\mathsf{,}{\omega }_{\mathsf{i}}\mathsf{,}\overline{\mathsf{T}}\mathsf{)}$.
表示满足的、承诺的、放松的 R1CS 实例-证人对 $({\mathsf{u}}_{\mathsf{i}\mathsf{+}\mathsf{1}}\mathsf{,}{\mathsf{w}}_{\mathsf{i}\mathsf{+}\mathsf{1}}\mathsf{)}$ ，用于在非确定性建议 $(\mathsf{v}\mathsf{k}\mathsf{,}{\mathsf{U}}_{\mathsf{i}}\mathsf{,}{\mathsf{u}}_{\mathsf{i}}\mathsf{,}\mathsf{(}\mathsf{i}\mathsf{,}{\mathsf{z}}_{\mathsf{0}}\mathsf{,}{\mathsf{z}}_{\mathsf{i}}\mathsf{)}\mathsf{,}{\omega }_{\mathsf{i}}\mathsf{,}\overline{\mathsf{T}}\mathsf{)}$ 上执行 $F^{\prime }$ 。

We define the IVC scheme $(\mathcal{G},\mathcal{K},\mathcal{P},\mathcal{V})$ as follows.
我们定义了 IVC 方案 $(\mathcal{G},\mathcal{K},\mathcal{P},\mathcal{V})$ 如下。

$\underset{\_}{\mathcal{G}(1^{\lambda })\to \mathsf{p}\mathsf{p}}$: Output $\mathsf{N}\mathsf{I}\mathsf{F}\mathsf{S}\mathsf{.}\mathsf{G}\mathsf{(}{\mathsf{1}}^{\lambda }\mathsf{)}$.
$\underset{\_}{\mathcal{G}(1^{\lambda })\to \mathsf{p}\mathsf{p}}$ : 输出 $\mathsf{N}\mathsf{I}\mathsf{F}\mathsf{S}\mathsf{.}\mathsf{G}\mathsf{(}{\mathsf{1}}^{\lambda }\mathsf{)}$ .

$\underset{\_}{\mathcal{K}(\mathsf{p}\mathsf{p}\mathsf{,}\mathsf{F}\mathsf{)}\to \mathsf{(}\mathsf{p}\mathsf{k}\mathsf{,}\mathsf{v}\mathsf{k}\mathsf{)}}$:

Compute $({\mathsf{p}\mathsf{k}}_{\mathsf{f}\mathsf{s}}\mathsf{,}{\mathsf{v}\mathsf{k}}_{\mathsf{f}\mathsf{s}}\mathsf{)}\leftarrow \mathsf{N}\mathsf{I}\mathsf{F}\mathsf{S}\mathsf{.}\mathsf{K}\mathsf{(}\mathsf{p}\mathsf{p}\mathsf{,}{\mathsf{s}}_{{\mathsf{F}}^{\prime }}\mathsf{)}$ and output $(\mathsf{p}\mathsf{k}\mathsf{,}\mathsf{v}\mathsf{k}\mathsf{)}\leftarrow \mathsf{(}\mathsf{(}\mathsf{F}\mathsf{,}{\mathsf{p}\mathsf{k}}_{\mathsf{f}\mathsf{s}}\mathsf{)}\mathsf{,}\mathsf{(}\mathsf{F}\mathsf{,}{\mathsf{v}\mathsf{k}}_{\mathsf{f}\mathsf{s}}\mathsf{)}\mathsf{)}$.
计算 $({\mathsf{p}\mathsf{k}}_{\mathsf{f}\mathsf{s}}\mathsf{,}{\mathsf{v}\mathsf{k}}_{\mathsf{f}\mathsf{s}}\mathsf{)}\leftarrow \mathsf{N}\mathsf{I}\mathsf{F}\mathsf{S}\mathsf{.}\mathsf{K}\mathsf{(}\mathsf{p}\mathsf{p}\mathsf{,}{\mathsf{s}}_{{\mathsf{F}}^{\prime }}\mathsf{)}$ 并输出 $(\mathsf{p}\mathsf{k}\mathsf{,}\mathsf{v}\mathsf{k}\mathsf{)}\leftarrow \mathsf{(}\mathsf{(}\mathsf{F}\mathsf{,}{\mathsf{p}\mathsf{k}}_{\mathsf{f}\mathsf{s}}\mathsf{)}\mathsf{,}\mathsf{(}\mathsf{F}\mathsf{,}{\mathsf{v}\mathsf{k}}_{\mathsf{f}\mathsf{s}}\mathsf{)}\mathsf{)}$ 。

$\underset{\_}{\mathcal{P}(\mathsf{p}\mathsf{k}\mathsf{,}\mathsf{(}\mathsf{i}\mathsf{,}{\mathsf{z}}_{\mathsf{0}}\mathsf{,}{\mathsf{z}}_{\mathsf{i}}\mathsf{)}\mathsf{,}{\omega }_{\mathsf{i}}\mathsf{,}{\mathsf{\text{Π}}}_{\mathsf{i}}\mathsf{)}\to {\mathsf{\text{Π}}}_{\mathsf{i}\mathsf{+}\mathsf{1}}}$:

Parse ${\text{Π}}_i$ as $(({\mathsf{U}}_{\mathsf{i}}\mathsf{,}{\mathsf{W}}_{\mathsf{i}}\mathsf{)}\mathsf{,}\mathsf{(}{\mathsf{u}}_{\mathsf{i}}\mathsf{,}{\mathsf{w}}_{\mathsf{i}}\mathsf{)}\mathsf{)}$ and then
解析 ${\text{Π}}_i$ 作为 $(({\mathsf{U}}_{\mathsf{i}}\mathsf{,}{\mathsf{W}}_{\mathsf{i}}\mathsf{)}\mathsf{,}\mathsf{(}{\mathsf{u}}_{\mathsf{i}}\mathsf{,}{\mathsf{w}}_{\mathsf{i}}\mathsf{)}\mathsf{)}$ 并然后

(1) if i is 0, compute $({\mathsf{U}}_{\mathsf{i}\mathsf{+}\mathsf{1}}\mathsf{,}{\mathsf{W}}_{\mathsf{i}\mathsf{+}\mathsf{1}}\mathsf{,}\overline{\mathsf{T}}\mathsf{)}\leftarrow \mathsf{(}{\mathsf{u}}_{\mathrm{\perp }}\mathsf{,}{\mathsf{w}}_{\mathrm{\perp }}\mathsf{,}{\mathsf{u}}_{\mathrm{\perp }}\mathsf{.}\overline{\mathsf{E}}\mathsf{)}$;
(1) 如果 i 为 0，计算 $({\mathsf{U}}_{\mathsf{i}\mathsf{+}\mathsf{1}}\mathsf{,}{\mathsf{W}}_{\mathsf{i}\mathsf{+}\mathsf{1}}\mathsf{,}\overline{\mathsf{T}}\mathsf{)}\leftarrow \mathsf{(}{\mathsf{u}}_{\mathrm{\perp }}\mathsf{,}{\mathsf{w}}_{\mathrm{\perp }}\mathsf{,}{\mathsf{u}}_{\mathrm{\perp }}\mathsf{.}\overline{\mathsf{E}}\mathsf{)}$ ;

otherwise, compute $({\mathsf{U}}_{\mathsf{i}\mathsf{+}\mathsf{1}}\mathsf{,}{\mathsf{W}}_{\mathsf{i}\mathsf{+}\mathsf{1}}\mathsf{,}\overline{\mathsf{T}}\mathsf{)}\leftarrow \mathsf{N}\mathsf{I}\mathsf{F}\mathsf{S}\mathsf{.}\mathsf{P}\mathsf{(}\mathsf{p}\mathsf{k}\mathsf{,}\mathsf{(}{\mathsf{U}}_{\mathsf{i}}\mathsf{,}{\mathsf{W}}_{\mathsf{i}}\mathsf{)}\mathsf{,}\mathsf{(}{\mathsf{u}}_{\mathsf{i}}\mathsf{,}{\mathsf{w}}_{\mathsf{i}}\mathsf{)}\mathsf{)}$,
否则，计算 $({\mathsf{U}}_{\mathsf{i}\mathsf{+}\mathsf{1}}\mathsf{,}{\mathsf{W}}_{\mathsf{i}\mathsf{+}\mathsf{1}}\mathsf{,}\overline{\mathsf{T}}\mathsf{)}\leftarrow \mathsf{N}\mathsf{I}\mathsf{F}\mathsf{S}\mathsf{.}\mathsf{P}\mathsf{(}\mathsf{p}\mathsf{k}\mathsf{,}\mathsf{(}{\mathsf{U}}_{\mathsf{i}}\mathsf{,}{\mathsf{W}}_{\mathsf{i}}\mathsf{)}\mathsf{,}\mathsf{(}{\mathsf{u}}_{\mathsf{i}}\mathsf{,}{\mathsf{w}}_{\mathsf{i}}\mathsf{)}\mathsf{)}$

(2) compute $({\mathsf{u}}_{\mathsf{i}\mathsf{+}\mathsf{1}}\mathsf{,}{\mathsf{w}}_{\mathsf{i}\mathsf{+}\mathsf{1}}\mathsf{)}\leftarrow \mathsf{t}\mathsf{r}\mathsf{a}\mathsf{c}\mathsf{e}\mathsf{(}{\mathsf{F}}^{\prime }\mathsf{,}\mathsf{(}\mathsf{v}\mathsf{k}\mathsf{,}{\mathsf{U}}_{\mathsf{i}}\mathsf{,}{\mathsf{u}}_{\mathsf{i}}\mathsf{,}\mathsf{(}\mathsf{i}\mathsf{,}{\mathsf{z}}_{\mathsf{0}}\mathsf{,}{\mathsf{z}}_{\mathsf{i}}\mathsf{)}\mathsf{,}{\omega }_{\mathsf{i}}\mathsf{,}\overline{\mathsf{T}}\mathsf{)}\mathsf{)}$, and
(2) 计算 $({\mathsf{u}}_{\mathsf{i}\mathsf{+}\mathsf{1}}\mathsf{,}{\mathsf{w}}_{\mathsf{i}\mathsf{+}\mathsf{1}}\mathsf{)}\leftarrow \mathsf{t}\mathsf{r}\mathsf{a}\mathsf{c}\mathsf{e}\mathsf{(}{\mathsf{F}}^{\prime }\mathsf{,}\mathsf{(}\mathsf{v}\mathsf{k}\mathsf{,}{\mathsf{U}}_{\mathsf{i}}\mathsf{,}{\mathsf{u}}_{\mathsf{i}}\mathsf{,}\mathsf{(}\mathsf{i}\mathsf{,}{\mathsf{z}}_{\mathsf{0}}\mathsf{,}{\mathsf{z}}_{\mathsf{i}}\mathsf{)}\mathsf{,}{\omega }_{\mathsf{i}}\mathsf{,}\overline{\mathsf{T}}\mathsf{)}\mathsf{)}$ ，和

(3) output ${\text{Π}}_{i+1}\leftarrow (({\mathsf{U}}_{\mathsf{i}\mathsf{+}\mathsf{1}}\mathsf{,}{\mathsf{W}}_{\mathsf{i}\mathsf{+}\mathsf{1}}\mathsf{)}\mathsf{,}\mathsf{(}{\mathsf{u}}_{\mathsf{i}\mathsf{+}\mathsf{1}}\mathsf{,}{\mathsf{w}}_{\mathsf{i}\mathsf{+}\mathsf{1}}\mathsf{)}\mathsf{)}$.
(3) 输出 ${\text{Π}}_{i+1}\leftarrow (({\mathsf{U}}_{\mathsf{i}\mathsf{+}\mathsf{1}}\mathsf{,}{\mathsf{W}}_{\mathsf{i}\mathsf{+}\mathsf{1}}\mathsf{)}\mathsf{,}\mathsf{(}{\mathsf{u}}_{\mathsf{i}\mathsf{+}\mathsf{1}}\mathsf{,}{\mathsf{w}}_{\mathsf{i}\mathsf{+}\mathsf{1}}\mathsf{)}\mathsf{)}$ .

$\underset{\_}{\mathcal{V}(\mathsf{v}\mathsf{k}\mathsf{,}\mathsf{(}\mathsf{i}\mathsf{,}{\mathsf{z}}_{\mathsf{0}}\mathsf{,}{\mathsf{z}}_{\mathsf{i}}\mathsf{)}\mathsf{,}{\mathsf{\text{Π}}}_{\mathsf{i}}\mathsf{)}\to \{\mathsf{0}\mathsf{,}\mathsf{1}\}}$:

If i is 0, check that $z_i=z_0$;
如果 i 为 0，检查 $z_i=z_0$ ；

otherwise, 否则，

• (1) parse ${\text{Π}}_i$ as $(({\mathsf{U}}_{\mathsf{i}}\mathsf{,}{\mathsf{W}}_{\mathsf{i}}\mathsf{)}\mathsf{,}\mathsf{(}{\mathsf{u}}_{\mathsf{i}}\mathsf{,}{\mathsf{w}}_{\mathsf{i}}\mathsf{)}\mathsf{)}$,
  解析 ${\text{Π}}_i$ 为 $(({\mathsf{U}}_{\mathsf{i}}\mathsf{,}{\mathsf{W}}_{\mathsf{i}}\mathsf{)}\mathsf{,}\mathsf{(}{\mathsf{u}}_{\mathsf{i}}\mathsf{,}{\mathsf{w}}_{\mathsf{i}}\mathsf{)}\mathsf{)}$ ，

• (2) check that ${\mathsf{u}}_{\mathsf{i}}\mathsf{.}\mathsf{x}\mathsf{=}\mathsf{h}\mathsf{a}\mathsf{s}\mathsf{h}\mathsf{(}\mathsf{v}\mathsf{k}\mathsf{,}\mathsf{i}\mathsf{,}{\mathsf{z}}_{\mathsf{0}}\mathsf{,}{\mathsf{z}}_{\mathsf{i}}\mathsf{,}{\mathsf{U}}_{\mathsf{i}}\mathsf{)}$,
  检查 ${\mathsf{u}}_{\mathsf{i}}\mathsf{.}\mathsf{x}\mathsf{=}\mathsf{h}\mathsf{a}\mathsf{s}\mathsf{h}\mathsf{(}\mathsf{v}\mathsf{k}\mathsf{,}\mathsf{i}\mathsf{,}{\mathsf{z}}_{\mathsf{0}}\mathsf{,}{\mathsf{z}}_{\mathsf{i}}\mathsf{,}{\mathsf{U}}_{\mathsf{i}}\mathsf{)}$ ，

• (3) check that $({\mathsf{u}}_{\mathsf{i}}\mathsf{.}\overline{\mathsf{E}}\mathsf{,}\mathsf{u}\mathsf{.}\mathsf{u}\mathsf{)}\mathsf{=}\mathsf{(}{\mathsf{u}}_{\mathrm{\perp }}\mathsf{.}\overline{\mathsf{E}}\mathsf{,}\mathsf{1}\mathsf{)}$, and
  检查 $({\mathsf{u}}_{\mathsf{i}}\mathsf{.}\overline{\mathsf{E}}\mathsf{,}\mathsf{u}\mathsf{.}\mathsf{u}\mathsf{)}\mathsf{=}\mathsf{(}{\mathsf{u}}_{\mathrm{\perp }}\mathsf{.}\overline{\mathsf{E}}\mathsf{,}\mathsf{1}\mathsf{)}$ ，并

• (4) check that ${\mathsf{W}}_{\mathsf{i}}$ and ${\mathsf{w}}_{\mathsf{i}}$ are satisfying witnesses to ${\mathsf{U}}_{\mathsf{i}}$ and ${\mathsf{u}}_{\mathsf{i}}$ respectively.
  检查 ${\mathsf{W}}_{\mathsf{i}}$ 和 ${\mathsf{w}}_{\mathsf{i}}$ 分别是 ${\mathsf{U}}_{\mathsf{i}}$ 和 ${\mathsf{u}}_{\mathsf{i}}$ 的满意见证者。

Lemma 2 (Completeness)

Construction 3 is an IVC scheme that satisfies completeness.

Proof Intuition. Given a satisfying IVC proof ${\text{Π}}_i=(({\mathsf{U}}_{\mathsf{i}}\mathsf{,}{\mathsf{W}}_{\mathsf{i}}\mathsf{)}\mathsf{,}\mathsf{(}{\mathsf{u}}_{\mathsf{i}}\mathsf{,}{\mathsf{w}}_{\mathsf{i}}\mathsf{)}\mathsf{)}$ suppose that $\mathcal{P}$ outputs ${\text{Π}}_{i+1}=(({\mathsf{U}}_{\mathsf{i}\mathsf{+}\mathsf{1}}\mathsf{,}{\mathsf{W}}_{\mathsf{i}\mathsf{+}\mathsf{1}}\mathsf{)}\mathsf{,}\mathsf{(}{\mathsf{u}}_{\mathsf{i}\mathsf{+}\mathsf{1}}\mathsf{,}{\mathsf{w}}_{\mathsf{i}\mathsf{+}\mathsf{1}}\mathsf{)}\mathsf{)}$. Because ${\text{Π}}_i$ is a valid IVC proof, $({\mathsf{u}}_{\mathsf{i}}\mathsf{,}{\mathsf{w}}_{\mathsf{i}}\mathsf{)}$ and $({\mathsf{U}}_{\mathsf{i}}\mathsf{,}{\mathsf{W}}_{\mathsf{i}}\mathsf{)}$ are satisfying instance-witness pairs. Because $({\mathsf{U}}_{\mathsf{i}\mathsf{+}\mathsf{1}}\mathsf{,}{\mathsf{W}}_{\mathsf{i}\mathsf{+}\mathsf{1}}\mathsf{)}$ is obtained by folding $({\mathsf{u}}_{\mathsf{i}}\mathsf{,}{\mathsf{w}}_{\mathsf{i}}\mathsf{)}$ and $({\mathsf{U}}_{\mathsf{i}}\mathsf{,}{\mathsf{W}}_{\mathsf{i}}\mathsf{)}$, it must be satisfying by the folding scheme’s completeness. By construction, $({\mathsf{u}}_{\mathsf{i}\mathsf{+}\mathsf{1}}\mathsf{,}{\mathsf{w}}_{\mathsf{i}\mathsf{+}\mathsf{1}}\mathsf{)}$ is satisfying instance-witness pair that satisfies the IVC verifier’s auxiliary checks. Thus, ${\text{Π}}_{i+1}$ is satisfying. [30, App. C] provides a formal proof.    $◻$

Lemma 3 (Knowledge Soundness)

Construction 3 is an IVC scheme that satisfies knowledge soundness.

Proof Intuition. For function F, constant n, $\mathsf{p}\mathsf{p}\leftarrow \mathcal{G}\mathsf{(}{\mathsf{1}}^{\lambda }\mathsf{)}$, and $(\mathsf{p}\mathsf{k}\mathsf{,}\mathsf{v}\mathsf{k}\mathsf{)}\leftarrow \mathcal{K}\mathsf{(}\mathsf{p}\mathsf{p}\mathsf{,}\mathsf{F}\mathsf{)}$, consider an adversary ${\mathcal{P}}^{\ast }$ that outputs $(z_0,z,\text{Π})$ such that $\mathcal{V}(\mathsf{v}\mathsf{k}\mathsf{,}\mathsf{(}\mathsf{n}\mathsf{,}{\mathsf{z}}_{\mathsf{0}}\mathsf{,}\mathsf{z}\mathsf{)}\mathsf{,}\mathsf{\text{Π}}\mathsf{)}\mathsf{=}\mathsf{1}$ with probability $ϵ$. We construct an extractor $\mathcal{E}$ that with input $(\mathsf{p}\mathsf{p}\mathsf{,}{\mathsf{z}}_{\mathsf{0}}\mathsf{,}\mathsf{z}\mathsf{)}$, outputs $({\omega }_0,\dots ,{\omega }_{n-1})$ such that by computing $z_i\leftarrow F(z_{i-1},{\omega }_{i-1})$ for all $i\in \{1,\dots ,n\}$ we have that $z_n=z$ with probability $ϵ-\mathsf{n}\mathsf{e}\mathsf{g}\mathsf{l}\mathsf{(}\lambda \mathsf{)}$. We show inductively that $\mathcal{E}$ can construct an extractor ${\mathcal{E}}_i$ that outputs $(z_i,\dots ,z_{n-1})$, $({\omega }_i,\dots ,{\omega }_{n-1})$, and ${\text{Π}}_i$ such that for all $j\in \{i+1,\dots ,n\}$, $z_j=F(z_{j-1},{\omega }_{j-1})$, $\mathcal{V}(\mathsf{v}\mathsf{k}\mathsf{,}\mathsf{i}\mathsf{,}{\mathsf{z}}_{\mathsf{0}}\mathsf{,}{\mathsf{z}}_{\mathsf{i}}\mathsf{,}{\mathsf{\text{Π}}}_{\mathsf{i}}\mathsf{)}\mathsf{=}\mathsf{1}$, and $z_n=z$ with probability $ϵ-\mathsf{n}\mathsf{e}\mathsf{g}\mathsf{l}\mathsf{(}\lambda \mathsf{)}$. Then, because in the base case when $i=0$, $\mathcal{V}$ checks that $z_0=z_i$, it is sufficient for $\mathcal{E}$ to run ${\mathcal{E}}_0$ to retrieve values $({\omega }_0,\dots ,{\omega }_{n-1})$. Initially, ${\mathcal{E}}_n$ simply runs the assumed ${\mathcal{P}}^{\ast }$ to get a satisfying ${\text{Π}}_n$. Given extractor ${\mathcal{E}}_i$ that satisfies the inductive hypothesis, we can construct extractor ${\mathcal{E}}_{i-1}$. [30, App. C] provides a formal proof.    $◻$
证明直觉。对于函数 F、常数 n、 $\mathsf{p}\mathsf{p}\leftarrow \mathcal{G}\mathsf{(}{\mathsf{1}}^{\lambda }\mathsf{)}$ 和 $(\mathsf{p}\mathsf{k}\mathsf{,}\mathsf{v}\mathsf{k}\mathsf{)}\leftarrow \mathcal{K}\mathsf{(}\mathsf{p}\mathsf{p}\mathsf{,}\mathsf{F}\mathsf{)}$ ，考虑一个敌手 ${\mathcal{P}}^{\ast }$ ，它输出 $(z_0,z,\text{Π})$ ，使得 $\mathcal{V}(\mathsf{v}\mathsf{k}\mathsf{,}\mathsf{(}\mathsf{n}\mathsf{,}{\mathsf{z}}_{\mathsf{0}}\mathsf{,}\mathsf{z}\mathsf{)}\mathsf{,}\mathsf{\text{Π}}\mathsf{)}\mathsf{=}\mathsf{1}$ 的概率为 $ϵ$ 。我们构造一个提取器 $\mathcal{E}$ ，它以输入 $(\mathsf{p}\mathsf{p}\mathsf{,}{\mathsf{z}}_{\mathsf{0}}\mathsf{,}\mathsf{z}\mathsf{)}$ 为条件，输出 $({\omega }_0,\dots ,{\omega }_{n-1})$ ，使得通过计算对于所有 $z_i\leftarrow F(z_{i-1},{\omega }_{i-1})$ ，我们有 $i\in \{1,\dots ,n\}$ 的概率为 $z_n=z$ 。我们通过归纳法证明 $ϵ-\mathsf{n}\mathsf{e}\mathsf{g}\mathsf{l}\mathsf{(}\lambda \mathsf{)}$ 可以构造一个提取器 $\mathcal{E}$ ，它输出 ${\mathcal{E}}_i$ ， $(z_i,\dots ,z_{n-1})$ ， $({\omega }_i,\dots ,{\omega }_{n-1})$ 和 ${\text{Π}}_i$ ，使得对于所有 $j\in \{i+1,\dots ,n\}$ ， $z_j=F(z_{j-1},{\omega }_{j-1})$ ， $\mathcal{V}(\mathsf{v}\mathsf{k}\mathsf{,}\mathsf{i}\mathsf{,}{\mathsf{z}}_{\mathsf{0}}\mathsf{,}{\mathsf{z}}_{\mathsf{i}}\mathsf{,}{\mathsf{\text{Π}}}_{\mathsf{i}}\mathsf{)}\mathsf{=}\mathsf{1}$ 和 $z_n=z$ ，概率为 $ϵ-\mathsf{n}\mathsf{e}\mathsf{g}\mathsf{l}\mathsf{(}\lambda \mathsf{)}$ 。然后，因为在基本情况中当 $i=0$ ， $\mathcal{V}$ 检查 $z_0=z_i$ 时，只需 $\mathcal{E}$ 运行 ${\mathcal{E}}_0$ 以检索值 $({\omega }_0,\dots ,{\omega }_{n-1})$ 即可。最初， ${\mathcal{E}}_n$ 简单地运行假设的 ${\mathcal{P}}^{\ast }$ 以获得令人满意的 ${\text{Π}}_n$ 。给定满足归纳假设的提取器 ${\mathcal{E}}_i$ ，我们可以构造提取器 ${\mathcal{E}}_{i-1}$ 。[ 30, 附录 C] 提供了形式证明。 $◻$

Lemma 4 (Efficiency)引理 4（效率）

When instantiated with the Pedersen commitment scheme, we have that $|F^{\prime }|=|F|+o(2\cdot \mathsf{G}\mathsf{+}\mathsf{2}\cdot \mathsf{H}\mathsf{+}\mathsf{R}\mathsf{)}$, where |F| denotes the number of R1CS constraints to encode a function F, $\mathsf{G}$ is the number of constraints required to encode a group scalar multiplication, $\mathsf{H}$ is the number of constraints required to encode $\mathsf{h}\mathsf{a}\mathsf{s}\mathsf{h}$, and $\mathsf{R}$ is the number of constraints to encode the RO $\rho$.
当使用 Pedersen 承诺方案实例化时，我们有 $|F^{\prime }|=|F|+o(2\cdot \mathsf{G}\mathsf{+}\mathsf{2}\cdot \mathsf{H}\mathsf{+}\mathsf{R}\mathsf{)}$ ，其中|F|表示编码函数 F 所需的 R1CS 约束数量， $\mathsf{G}$ 是编码群标量乘法所需的约束数量， $\mathsf{H}$ 是编码 $\mathsf{h}\mathsf{a}\mathsf{s}\mathsf{h}$ 所需的约束数量， $\mathsf{R}$ 是编码 RO $\rho$ 的约束数量。

Proof证明

On input instances $\mathsf{U}$ and $\mathsf{u}$, $\mathsf{N}\mathsf{I}\mathsf{F}\mathsf{S}\mathsf{.}\mathsf{V}$ computes $\overline{E}\leftarrow \mathsf{U}\mathsf{.}\overline{\mathsf{E}}\mathsf{+}\mathsf{r}\cdot \overline{\mathsf{T}}\mathsf{+}{\mathsf{r}}^{\mathsf{2}}\cdot \mathsf{u}\mathsf{.}\overline{\mathsf{E}}$ and $\overline{W}\leftarrow \mathsf{U}\mathsf{.}\overline{\mathsf{W}}\mathsf{+}\mathsf{r}\cdot \mathsf{u}\mathsf{.}\overline{\mathsf{W}}$. However, by construction, $\mathsf{u}\mathsf{.}\overline{\mathsf{E}}\mathsf{=}{\mathsf{u}}_{\mathrm{\perp }}\mathsf{.}\overline{\mathsf{E}}\mathsf{=}\overline{\mathsf{0}}$. So, $\mathsf{N}\mathsf{I}\mathsf{F}\mathsf{S}\mathsf{.}\mathsf{V}$ computes two group scalar multiplications, as it does not need to compute $r^2\cdot \mathsf{u}\mathsf{.}\overline{\mathsf{E}}$. $\mathsf{N}\mathsf{I}\mathsf{F}\mathsf{S}\mathsf{.}\mathsf{V}$ additionally invokes the RO once to obtain a random scalar. Finally, $F^{\prime }$ makes two additional calls to $\mathsf{h}\mathsf{a}\mathsf{s}\mathsf{h}$ (details are in the description of $F^{\prime }$).    $◻$
在输入实例 $\mathsf{U}$ 和 $\mathsf{u}$ ， $\mathsf{N}\mathsf{I}\mathsf{F}\mathsf{S}\mathsf{.}\mathsf{V}$ 计算出 $\overline{E}\leftarrow \mathsf{U}\mathsf{.}\overline{\mathsf{E}}\mathsf{+}\mathsf{r}\cdot \overline{\mathsf{T}}\mathsf{+}{\mathsf{r}}^{\mathsf{2}}\cdot \mathsf{u}\mathsf{.}\overline{\mathsf{E}}$ 和 $\overline{W}\leftarrow \mathsf{U}\mathsf{.}\overline{\mathsf{W}}\mathsf{+}\mathsf{r}\cdot \mathsf{u}\mathsf{.}\overline{\mathsf{W}}$ 。然而，根据构造， $\mathsf{u}\mathsf{.}\overline{\mathsf{E}}\mathsf{=}{\mathsf{u}}_{\mathrm{\perp }}\mathsf{.}\overline{\mathsf{E}}\mathsf{=}\overline{\mathsf{0}}$ 。因此， $\mathsf{N}\mathsf{I}\mathsf{F}\mathsf{S}\mathsf{.}\mathsf{V}$ 计算两个群标量乘法，因为它不需要计算 $r^2\cdot \mathsf{u}\mathsf{.}\overline{\mathsf{E}}$ 。 $\mathsf{N}\mathsf{I}\mathsf{F}\mathsf{S}\mathsf{.}\mathsf{V}$ 此外调用 RO 一次以获取一个随机标量。最后， $F^{\prime }$ 对 $\mathsf{h}\mathsf{a}\mathsf{s}\mathsf{h}$ 进行两次额外调用（详细信息见 $F^{\prime }$ 的描述）。 $◻$

5.2 Compressing IVC Proofs with zkSNARKs
5.2 使用 zkSNARKs 压缩 IVC 证明

To prove a statement about an incremental computation, the prover can produce an IVC proof using the construction in the prior section and send the IVC proof to the verifier. However, this does not satisfy zero-knowledge (as the IVC proof described in the prior section does not hide the prover’s non-deterministic inputs) and succinctness (as the IVC proof size is linear in the size F). In theory, one can address this problem with any zkSNARK for $\mathsf{N}\mathsf{P}$. Specifically, $\overline{\mathcal{P}}$ can produce a zkSNARK proving that it knows ${\text{Π}}_i$ such that IVC verifier $\mathcal{V}$ accepts for statement $(i,z_0,z_i)$. Naturally, the proof sent to the verifier is succinct and zero-knowledge due to the corresponding properties of the zkSNARK.
为了证明关于增量计算的一个陈述，证明者可以使用前述章节中的构造方法生成一个 IVC 证明，并将 IVC 证明发送给验证者。然而，这并不满足零知识（因为前述章节中描述的 IVC 证明没有隐藏证明者的非确定性输入）和简洁性（因为 IVC 证明的大小与 F 的大小成线性关系）。在理论上，可以使用任何 zkSNARK 来解决此问题。具体来说， $\overline{\mathcal{P}}$ 可以生成一个 zkSNARK，证明它知道 ${\text{Π}}_i$ ，使得 IVC 验证者 $\mathcal{V}$ 接受该陈述 $(i,z_0,z_i)$ 。自然地，由于 zkSNARK 的相应属性，发送给验证者的证明是简洁的和零知识的。

Unfortunately, employing an off-the-shelf zkSNARK makes the overall solution impractical as the zkSNARK prover must prove, among other things, the knowledge of vectors whose commitments equal a particular value; this requires encoding a linear number of group scalar multiplications in the programming model of zkSNARKs (e.g., R1CS or circuits). To address this, we design a zkSNARK tailored for our particular purpose and we describe it in Sect. 6. Below, we describe how to use a zkSNARK to prove the knowledge of a valid IVC proof.
很遗憾，使用现成的 zkSNARK 使得整体解决方案不切实际，因为 zkSNARK 证明者必须证明，包括其他事项在内，知道向量承诺等于特定值的向量；这需要在 zkSNARK 的编程模型（例如 R1CS 或电路）中编码线性数量的群标量乘法。为了解决这个问题，我们设计了一个针对我们特定目的的 zkSNARK，并在第 6 节中描述了它。下面，我们描述了如何使用 zkSNARK 来证明有效 IVC 证明的知识。

Construction 4建设 4

(A zkSNARK of a Valid IVC Proof). Let $\mathsf{I}\mathsf{V}\mathsf{C}$ denote the IVC scheme in Construction 3, let $\mathsf{N}\mathsf{I}\mathsf{F}\mathsf{S}$ denote the non-interactive folding scheme in Construction 2, and let $\mathsf{h}\mathsf{a}\mathsf{s}\mathsf{h}$ denote a randomized cryptographic hash function. Assume a zero-knowledge succinct non-interactive argument of knowledge (Definition 2), $\mathsf{z}\mathsf{k}\mathsf{S}\mathsf{N}\mathsf{A}\mathsf{R}\mathsf{K}$, for committed relaxed R1CS. That is, given public parameters $\mathsf{p}\mathsf{p}$, structure $\mathsf{s}$, and instance $\mathsf{u}$, $\mathsf{z}\mathsf{k}\mathsf{S}\mathsf{N}\mathsf{A}\mathsf{R}\mathsf{K}\mathsf{.}\mathsf{P}$ can convince $\mathsf{z}\mathsf{k}\mathsf{S}\mathsf{N}\mathsf{A}\mathsf{R}\mathsf{K}\mathsf{.}\mathsf{V}$ in zero-knowledge and with a succinct proof (e.g., $O_{\lambda }(\log N)$-sized proof) that it knows a corresponding witness $\mathsf{w}$ such that $(\mathsf{p}\mathsf{p}\mathsf{,}\mathsf{s}\mathsf{,}\mathsf{u}\mathsf{,}\mathsf{w}\mathsf{)}$ is a satisfying committed relaxed R1CS tuple.
(一个有效的 IVC 证明的 zkSNARK)。令 $\mathsf{I}\mathsf{V}\mathsf{C}$ 表示构造 3 中的 IVC 方案，令 $\mathsf{N}\mathsf{I}\mathsf{F}\mathsf{S}$ 表示构造 2 中的非交互式折叠方案，令 $\mathsf{h}\mathsf{a}\mathsf{s}\mathsf{h}$ 表示一个随机的加密哈希函数。假设对于承诺的放松 R1CS，存在一个零知识简洁非交互式知识论证（定义 2）， $\mathsf{z}\mathsf{k}\mathsf{S}\mathsf{N}\mathsf{A}\mathsf{R}\mathsf{K}$ ，即，给定公共参数 $\mathsf{p}\mathsf{p}$ ，结构 $\mathsf{s}$ ，和实例 $\mathsf{u}$ ， $\mathsf{z}\mathsf{k}\mathsf{S}\mathsf{N}\mathsf{A}\mathsf{R}\mathsf{K}\mathsf{.}\mathsf{P}$ 可以在零知识下，并通过一个简洁的证明（例如， $O_{\lambda }(\log N)$ 大小的证明）说服 $\mathsf{z}\mathsf{k}\mathsf{S}\mathsf{N}\mathsf{A}\mathsf{R}\mathsf{K}\mathsf{.}\mathsf{V}$ ，它知道一个相应的证人 $\mathsf{w}$ ，使得 $(\mathsf{p}\mathsf{p}\mathsf{,}\mathsf{s}\mathsf{,}\mathsf{u}\mathsf{,}\mathsf{w}\mathsf{)}$ 是一个满足的承诺的放松 R1CS 元组。

Consider a polynomial-time computable function F. Suppose $\mathsf{p}\mathsf{p}\leftarrow \mathsf{I}\mathsf{V}\mathsf{C}\mathsf{.}\mathsf{G}\mathsf{(}{\mathsf{1}}^{\lambda }\mathsf{)}$ and $(\mathsf{p}\mathsf{k}\mathsf{,}\mathsf{v}\mathsf{k}\mathsf{)}\leftarrow \mathsf{I}\mathsf{V}\mathsf{C}\mathsf{.}\mathsf{K}\mathsf{(}\mathsf{p}\mathsf{p}\mathsf{,}\mathsf{F}\mathsf{)}$. Suppose the prover $\mathcal{P}$ and verifier $\mathcal{V}$ are provided an instance $(i,z_0,z_i)$. We construct a zkSNARK that allows the prover to show that it knows an IVC proof ${\text{Π}}_i$ such that $\mathsf{I}\mathsf{V}\mathsf{C}\mathsf{.}\mathsf{V}\mathsf{(}\mathsf{v}\mathsf{k}\mathsf{,}\mathsf{i}\mathsf{,}{\mathsf{z}}_{\mathsf{0}}\mathsf{,}{\mathsf{z}}_{\mathsf{i}}\mathsf{,}{\mathsf{\text{Π}}}_{\mathsf{i}}\mathsf{)}\mathsf{=}\mathsf{1}$.
考虑一个多项式时间可计算函数 F。假设 $\mathsf{p}\mathsf{p}\leftarrow \mathsf{I}\mathsf{V}\mathsf{C}\mathsf{.}\mathsf{G}\mathsf{(}{\mathsf{1}}^{\lambda }\mathsf{)}$ 和 $(\mathsf{p}\mathsf{k}\mathsf{,}\mathsf{v}\mathsf{k}\mathsf{)}\leftarrow \mathsf{I}\mathsf{V}\mathsf{C}\mathsf{.}\mathsf{K}\mathsf{(}\mathsf{p}\mathsf{p}\mathsf{,}\mathsf{F}\mathsf{)}$ 。假设证明者 $\mathcal{P}$ 和验证者 $\mathcal{V}$ 被提供了一个实例 $(i,z_0,z_i)$ 。我们构建一个零知识证明系统 zkSNARK，允许证明者展示它知道一个 IVC 证明 ${\text{Π}}_i$ ，使得 $\mathsf{I}\mathsf{V}\mathsf{C}\mathsf{.}\mathsf{V}\mathsf{(}\mathsf{v}\mathsf{k}\mathsf{,}\mathsf{i}\mathsf{,}{\mathsf{z}}_{\mathsf{0}}\mathsf{,}{\mathsf{z}}_{\mathsf{i}}\mathsf{,}{\mathsf{\text{Π}}}_{\mathsf{i}}\mathsf{)}\mathsf{=}\mathsf{1}$ 。

In a nutshell, we leverage the fact that $\text{Π}$ is two committed relaxed R1CS instance-witness pairs. So, $\mathcal{P}$ first folds instance-witness pairs $(\mathsf{u}\mathsf{,}\mathsf{w}\mathsf{)}$ and $(\mathsf{U}\mathsf{,}\mathsf{W}\mathsf{)}$ to produce a folded instance-witness pair $({\mathsf{U}}^{\prime }\mathsf{,}{\mathsf{W}}^{\prime }\mathsf{)}$, using $\mathsf{N}\mathsf{I}\mathsf{F}\mathsf{S}\mathsf{.}\mathsf{P}$. Next, $\mathcal{P}$ runs $\mathsf{z}\mathsf{k}\mathsf{S}\mathsf{N}\mathsf{A}\mathsf{R}\mathsf{K}\mathsf{.}\mathsf{P}$ to prove that it knows a valid witness for ${\mathsf{U}}^{\prime }$. In more detail, for polynomial-time computable function F and corresponding function $F^{\prime }$ as defined in Construction 3 (and instantiated with $\mathsf{h}\mathsf{a}\mathsf{s}\mathsf{h}$), we define $(\mathcal{G},\mathcal{K},\mathcal{P},\mathcal{V})$ as follows.
总的来说，我们利用了 $\text{Π}$ 是两个承诺的松弛 R1CS 实例-见证对的事实。因此， $\mathcal{P}$ 首先将实例-见证对 $(\mathsf{u}\mathsf{,}\mathsf{w}\mathsf{)}$ 和 $(\mathsf{U}\mathsf{,}\mathsf{W}\mathsf{)}$ 折叠成折叠后的实例-见证对 $({\mathsf{U}}^{\prime }\mathsf{,}{\mathsf{W}}^{\prime }\mathsf{)}$ ，使用 $\mathsf{N}\mathsf{I}\mathsf{F}\mathsf{S}\mathsf{.}\mathsf{P}$ 。接下来， $\mathcal{P}$ 运行 $\mathsf{z}\mathsf{k}\mathsf{S}\mathsf{N}\mathsf{A}\mathsf{R}\mathsf{K}\mathsf{.}\mathsf{P}$ 来证明它知道 ${\mathsf{U}}^{\prime }$ 的有效见证。更详细地说，对于多项式时间内可计算函数 F 及其在构造 3 中定义的对应函数 $F^{\prime }$ （并使用 $\mathsf{h}\mathsf{a}\mathsf{s}\mathsf{h}$ 实例化），我们如下定义 $(\mathcal{G},\mathcal{K},\mathcal{P},\mathcal{V})$ 。

$\underset{\_}{\mathcal{G}(1^{\lambda })\to \mathsf{p}\mathsf{p}}$:

• (1) Compute ${\mathsf{p}\mathsf{p}}_{\mathsf{N}\mathsf{I}\mathsf{F}\mathsf{S}}\leftarrow \mathsf{N}\mathsf{I}\mathsf{F}\mathsf{S}\mathsf{.}\mathsf{G}\mathsf{(}{\mathsf{1}}^{\lambda }\mathsf{)}$计算 ${\mathsf{p}\mathsf{p}}_{\mathsf{N}\mathsf{I}\mathsf{F}\mathsf{S}}\leftarrow \mathsf{N}\mathsf{I}\mathsf{F}\mathsf{S}\mathsf{.}\mathsf{G}\mathsf{(}{\mathsf{1}}^{\lambda }\mathsf{)}$

• (2) Compute ${\mathsf{p}\mathsf{p}}_{\mathsf{z}\mathsf{k}\mathsf{S}\mathsf{N}\mathsf{A}\mathsf{R}\mathsf{K}}\leftarrow \mathsf{z}\mathsf{k}\mathsf{S}\mathsf{N}\mathsf{A}\mathsf{R}\mathsf{K}\mathsf{.}\mathsf{G}\mathsf{(}{\mathsf{1}}^{\lambda }\mathsf{)}$计算 ${\mathsf{p}\mathsf{p}}_{\mathsf{z}\mathsf{k}\mathsf{S}\mathsf{N}\mathsf{A}\mathsf{R}\mathsf{K}}\leftarrow \mathsf{z}\mathsf{k}\mathsf{S}\mathsf{N}\mathsf{A}\mathsf{R}\mathsf{K}\mathsf{.}\mathsf{G}\mathsf{(}{\mathsf{1}}^{\lambda }\mathsf{)}$

• (3) Output $({\mathsf{p}\mathsf{p}}_{\mathsf{N}\mathsf{I}\mathsf{F}\mathsf{S}}\mathsf{,}{\mathsf{p}\mathsf{p}}_{\mathsf{z}\mathsf{k}\mathsf{S}\mathsf{N}\mathsf{A}\mathsf{R}\mathsf{K}}\mathsf{)}$输出 $({\mathsf{p}\mathsf{p}}_{\mathsf{N}\mathsf{I}\mathsf{F}\mathsf{S}}\mathsf{,}{\mathsf{p}\mathsf{p}}_{\mathsf{z}\mathsf{k}\mathsf{S}\mathsf{N}\mathsf{A}\mathsf{R}\mathsf{K}}\mathsf{)}$

$\underset{\_}{\mathcal{K}(\mathsf{p}\mathsf{p}\mathsf{,}\mathsf{F}\mathsf{)}\to \mathsf{(}\mathsf{p}\mathsf{k}\mathsf{,}\mathsf{v}\mathsf{k}\mathsf{)}}$:

• (1) Compute $({\mathsf{p}\mathsf{k}}_{\mathsf{N}\mathsf{I}\mathsf{F}\mathsf{S}}\mathsf{,}{\mathsf{v}\mathsf{k}}_{\mathsf{N}\mathsf{I}\mathsf{F}\mathsf{S}}\mathsf{)}\leftarrow \mathsf{N}\mathsf{I}\mathsf{F}\mathsf{S}\mathsf{.}\mathsf{K}\mathsf{(}\mathsf{p}\mathsf{p}\mathsf{.}{\mathsf{p}\mathsf{p}}_{\mathsf{N}\mathsf{I}\mathsf{F}\mathsf{S}}\mathsf{,}{\mathsf{s}}_{{\mathsf{F}}^{\prime }}\mathsf{)}$.计算 $({\mathsf{p}\mathsf{k}}_{\mathsf{N}\mathsf{I}\mathsf{F}\mathsf{S}}\mathsf{,}{\mathsf{v}\mathsf{k}}_{\mathsf{N}\mathsf{I}\mathsf{F}\mathsf{S}}\mathsf{)}\leftarrow \mathsf{N}\mathsf{I}\mathsf{F}\mathsf{S}\mathsf{.}\mathsf{K}\mathsf{(}\mathsf{p}\mathsf{p}\mathsf{.}{\mathsf{p}\mathsf{p}}_{\mathsf{N}\mathsf{I}\mathsf{F}\mathsf{S}}\mathsf{,}{\mathsf{s}}_{{\mathsf{F}}^{\prime }}\mathsf{)}$ .

• (2) Compute $({\mathsf{p}\mathsf{k}}_{\mathsf{z}\mathsf{k}\mathsf{S}\mathsf{N}\mathsf{A}\mathsf{R}\mathsf{K}}\mathsf{,}{\mathsf{v}\mathsf{k}}_{\mathsf{z}\mathsf{k}\mathsf{S}\mathsf{N}\mathsf{A}\mathsf{R}\mathsf{K}}\mathsf{)}\leftarrow \mathsf{z}\mathsf{k}\mathsf{S}\mathsf{N}\mathsf{A}\mathsf{R}\mathsf{K}\mathsf{.}\mathsf{K}\mathsf{(}\mathsf{p}\mathsf{p}\mathsf{.}{\mathsf{p}\mathsf{p}}_{\mathsf{z}\mathsf{k}\mathsf{S}\mathsf{N}\mathsf{A}\mathsf{R}\mathsf{K}}\mathsf{,}{\mathsf{s}}_{{\mathsf{F}}^{\prime }}\mathsf{)}$.计算 $({\mathsf{p}\mathsf{k}}_{\mathsf{z}\mathsf{k}\mathsf{S}\mathsf{N}\mathsf{A}\mathsf{R}\mathsf{K}}\mathsf{,}{\mathsf{v}\mathsf{k}}_{\mathsf{z}\mathsf{k}\mathsf{S}\mathsf{N}\mathsf{A}\mathsf{R}\mathsf{K}}\mathsf{)}\leftarrow \mathsf{z}\mathsf{k}\mathsf{S}\mathsf{N}\mathsf{A}\mathsf{R}\mathsf{K}\mathsf{.}\mathsf{K}\mathsf{(}\mathsf{p}\mathsf{p}\mathsf{.}{\mathsf{p}\mathsf{p}}_{\mathsf{z}\mathsf{k}\mathsf{S}\mathsf{N}\mathsf{A}\mathsf{R}\mathsf{K}}\mathsf{,}{\mathsf{s}}_{{\mathsf{F}}^{\prime }}\mathsf{)}$ .

• (3) Output $(({\mathsf{p}\mathsf{k}}_{\mathsf{N}\mathsf{I}\mathsf{F}\mathsf{S}}\mathsf{,}{\mathsf{p}\mathsf{k}}_{\mathsf{z}\mathsf{k}\mathsf{S}\mathsf{N}\mathsf{A}\mathsf{R}\mathsf{K}}\mathsf{)}\mathsf{,}\mathsf{(}{\mathsf{v}\mathsf{k}}_{\mathsf{N}\mathsf{I}\mathsf{F}\mathsf{S}}\mathsf{,}{\mathsf{v}\mathsf{k}}_{\mathsf{z}\mathsf{k}\mathsf{S}\mathsf{N}\mathsf{A}\mathsf{R}\mathsf{K}}\mathsf{)}\mathsf{)}$.输出 $(({\mathsf{p}\mathsf{k}}_{\mathsf{N}\mathsf{I}\mathsf{F}\mathsf{S}}\mathsf{,}{\mathsf{p}\mathsf{k}}_{\mathsf{z}\mathsf{k}\mathsf{S}\mathsf{N}\mathsf{A}\mathsf{R}\mathsf{K}}\mathsf{)}\mathsf{,}\mathsf{(}{\mathsf{v}\mathsf{k}}_{\mathsf{N}\mathsf{I}\mathsf{F}\mathsf{S}}\mathsf{,}{\mathsf{v}\mathsf{k}}_{\mathsf{z}\mathsf{k}\mathsf{S}\mathsf{N}\mathsf{A}\mathsf{R}\mathsf{K}}\mathsf{)}\mathsf{)}$ .

$\underset{\_}{\mathcal{P}(\mathsf{p}\mathsf{k}\mathsf{,}\mathsf{(}\mathsf{i}\mathsf{,}{\mathsf{z}}_{\mathsf{0}}\mathsf{,}{\mathsf{z}}_{\mathsf{i}}\mathsf{)}\mathsf{,}\mathsf{\text{Π}}\mathsf{)}\to \pi }$:

If i is 0, output $\mathrm{\perp }$;
如果 i 为 0，输出 $\mathrm{\perp }$ ;

otherwise, 否则，

• (1) parse $\text{Π}$ as $((\mathsf{U}\mathsf{,}\mathsf{W}\mathsf{)}\mathsf{,}\mathsf{(}\mathsf{u}\mathsf{,}\mathsf{w}\mathsf{)}\mathsf{)}$
  解析 $\text{Π}$ 为 $((\mathsf{U}\mathsf{,}\mathsf{W}\mathsf{)}\mathsf{,}\mathsf{(}\mathsf{u}\mathsf{,}\mathsf{w}\mathsf{)}\mathsf{)}$

• (2) compute $({\mathsf{U}}^{\prime }\mathsf{,}{\mathsf{W}}^{\prime }\mathsf{,}\overline{\mathsf{T}}\mathsf{)}\leftarrow \mathsf{N}\mathsf{I}\mathsf{F}\mathsf{S}\mathsf{.}\mathsf{P}\mathsf{(}{\mathsf{p}\mathsf{k}}_{\mathsf{N}\mathsf{I}\mathsf{F}\mathsf{S}}\mathsf{,}\mathsf{(}\mathsf{U}\mathsf{,}\mathsf{W}\mathsf{)}\mathsf{,}\mathsf{(}\mathsf{u}\mathsf{,}\mathsf{w}\mathsf{)}\mathsf{)}$计算 $({\mathsf{U}}^{\prime }\mathsf{,}{\mathsf{W}}^{\prime }\mathsf{,}\overline{\mathsf{T}}\mathsf{)}\leftarrow \mathsf{N}\mathsf{I}\mathsf{F}\mathsf{S}\mathsf{.}\mathsf{P}\mathsf{(}{\mathsf{p}\mathsf{k}}_{\mathsf{N}\mathsf{I}\mathsf{F}\mathsf{S}}\mathsf{,}\mathsf{(}\mathsf{U}\mathsf{,}\mathsf{W}\mathsf{)}\mathsf{,}\mathsf{(}\mathsf{u}\mathsf{,}\mathsf{w}\mathsf{)}\mathsf{)}$

• (3) compute ${\pi }_{{\mathsf{U}}^{\prime }}\leftarrow \mathsf{z}\mathsf{k}\mathsf{S}\mathsf{N}\mathsf{A}\mathsf{R}\mathsf{K}\mathsf{.}\mathsf{P}\mathsf{(}{\mathsf{p}\mathsf{k}}_{\mathsf{z}\mathsf{k}\mathsf{S}\mathsf{N}\mathsf{A}\mathsf{R}\mathsf{K}}\mathsf{,}{\mathsf{U}}^{\prime }\mathsf{,}{\mathsf{W}}^{\prime }\mathsf{)}$计算 ${\pi }_{{\mathsf{U}}^{\prime }}\leftarrow \mathsf{z}\mathsf{k}\mathsf{S}\mathsf{N}\mathsf{A}\mathsf{R}\mathsf{K}\mathsf{.}\mathsf{P}\mathsf{(}{\mathsf{p}\mathsf{k}}_{\mathsf{z}\mathsf{k}\mathsf{S}\mathsf{N}\mathsf{A}\mathsf{R}\mathsf{K}}\mathsf{,}{\mathsf{U}}^{\prime }\mathsf{,}{\mathsf{W}}^{\prime }\mathsf{)}$

• (4) output $(\mathsf{U}\mathsf{,}\mathsf{u}\mathsf{,}\overline{\mathsf{T}}\mathsf{,}{\pi }_{{\mathsf{U}}^{\prime }}\mathsf{)}$.输出 $(\mathsf{U}\mathsf{,}\mathsf{u}\mathsf{,}\overline{\mathsf{T}}\mathsf{,}{\pi }_{{\mathsf{U}}^{\prime }}\mathsf{)}$ .

$\underset{\_}{\mathcal{V}(\mathsf{v}\mathsf{k}\mathsf{,}\mathsf{(}\mathsf{i}\mathsf{,}{\mathsf{z}}_{\mathsf{0}}\mathsf{,}{\mathsf{z}}_{\mathsf{i}}\mathsf{)}\mathsf{,}\pi \mathsf{)}\to \{\mathsf{0}\mathsf{,}\mathsf{1}\}}$:

If i is 0, check that $z_0=z_i$;
如果 i 为 0，检查 $z_0=z_i$ ；

otherwise, 否则，

• (1) parse $\pi$ as $(\mathsf{U}\mathsf{,}\mathsf{u}\mathsf{,}\overline{\mathsf{T}}\mathsf{,}{\pi }_{{\mathsf{U}}^{\prime }}\mathsf{)}$,
  解析 $\pi$ 为 $(\mathsf{U}\mathsf{,}\mathsf{u}\mathsf{,}\overline{\mathsf{T}}\mathsf{,}{\pi }_{{\mathsf{U}}^{\prime }}\mathsf{)}$ ，

• (2) check that $\mathsf{u}\mathsf{.}\mathsf{x}\mathsf{=}\mathsf{h}\mathsf{a}\mathsf{s}\mathsf{h}\mathsf{(}{\mathsf{v}\mathsf{k}}_{\mathsf{N}\mathsf{I}\mathsf{F}\mathsf{S}}\mathsf{,}\mathsf{i}\mathsf{,}{\mathsf{z}}_{\mathsf{0}}\mathsf{,}{\mathsf{z}}_{\mathsf{i}}\mathsf{,}\mathsf{U}\mathsf{)}$,
  检查 $\mathsf{u}\mathsf{.}\mathsf{x}\mathsf{=}\mathsf{h}\mathsf{a}\mathsf{s}\mathsf{h}\mathsf{(}{\mathsf{v}\mathsf{k}}_{\mathsf{N}\mathsf{I}\mathsf{F}\mathsf{S}}\mathsf{,}\mathsf{i}\mathsf{,}{\mathsf{z}}_{\mathsf{0}}\mathsf{,}{\mathsf{z}}_{\mathsf{i}}\mathsf{,}\mathsf{U}\mathsf{)}$ ，

• (3) check that $(\mathsf{u}\mathsf{.}\overline{\mathsf{E}}\mathsf{,}\mathsf{u}\mathsf{.}\mathsf{u}\mathsf{)}\mathsf{=}\mathsf{(}{\mathsf{u}}_{\mathrm{\perp }}\mathsf{.}\overline{\mathsf{E}}\mathsf{,}\mathsf{1}\mathsf{)}$,
  检查 $(\mathsf{u}\mathsf{.}\overline{\mathsf{E}}\mathsf{,}\mathsf{u}\mathsf{.}\mathsf{u}\mathsf{)}\mathsf{=}\mathsf{(}{\mathsf{u}}_{\mathrm{\perp }}\mathsf{.}\overline{\mathsf{E}}\mathsf{,}\mathsf{1}\mathsf{)}$ ，

• (4) compute ${\mathsf{U}}^{\prime }\leftarrow \mathsf{N}\mathsf{I}\mathsf{F}\mathsf{S}\mathsf{.}\mathsf{V}\mathsf{(}{\mathsf{v}\mathsf{k}}_{\mathsf{N}\mathsf{I}\mathsf{F}\mathsf{S}}\mathsf{,}\mathsf{U}\mathsf{,}\mathsf{u}\mathsf{,}\overline{\mathsf{T}}\mathsf{)}$, and
  计算 ${\mathsf{U}}^{\prime }\leftarrow \mathsf{N}\mathsf{I}\mathsf{F}\mathsf{S}\mathsf{.}\mathsf{V}\mathsf{(}{\mathsf{v}\mathsf{k}}_{\mathsf{N}\mathsf{I}\mathsf{F}\mathsf{S}}\mathsf{,}\mathsf{U}\mathsf{,}\mathsf{u}\mathsf{,}\overline{\mathsf{T}}\mathsf{)}$ ，和

• (5) check that $\mathsf{z}\mathsf{k}\mathsf{S}\mathsf{N}\mathsf{A}\mathsf{R}\mathsf{K}\mathsf{.}\mathsf{V}\mathsf{(}{\mathsf{v}\mathsf{k}}_{\mathsf{z}\mathsf{k}\mathsf{S}\mathsf{N}\mathsf{A}\mathsf{R}\mathsf{K}}\mathsf{,}{\mathsf{U}}^{\prime }\mathsf{,}{\pi }_{{\mathsf{U}}^{\prime }}\mathsf{)}\mathsf{=}\mathsf{1}$.
  检查 $\mathsf{z}\mathsf{k}\mathsf{S}\mathsf{N}\mathsf{A}\mathsf{R}\mathsf{K}\mathsf{.}\mathsf{V}\mathsf{(}{\mathsf{v}\mathsf{k}}_{\mathsf{z}\mathsf{k}\mathsf{S}\mathsf{N}\mathsf{A}\mathsf{R}\mathsf{K}}\mathsf{,}{\mathsf{U}}^{\prime }\mathsf{,}{\pi }_{{\mathsf{U}}^{\prime }}\mathsf{)}\mathsf{=}\mathsf{1}$ 。

Theorem 4定理 4

Construction 4 is a zkSNARK of a valid IVC proof produced by Construction 3.
构造 4 是构造 3 产生的有效 IVC 证明的 zkSNARK。

Proof Intuition. Completeness and knowledge soundness hold due to the completeness and knowledge soundness of the underlying zkSNARK and the non-interactive folding scheme. Assuming the non-interactive folding scheme satisfies succinctness (e.g., by using the Pedersen commitment scheme), succinctness holds due to the fact that $\mathsf{u}$, $\mathsf{U}$, and $\overline{T}$ are succinct, and due to the succinctness of the underling zkSNARK.
证明直觉。完备性和知识一致性由底层 zkSNARK 和非交互折叠方案的性质保证。假设非交互折叠方案满足简洁性（例如，通过使用 Pedersen 承诺方案），由于 $\mathsf{u}$ ， $\mathsf{U}$ ，和 $\overline{T}$ 的简洁性以及底层 zkSNARK 的简洁性，简洁性得以保持。

To prove zero-knowledge, we construct a simulator $\mathcal{S}$ that first iteratively simulates $({\mathsf{U}}_{\mathsf{i}}\mathsf{,}{\mathsf{u}}_{\mathsf{i}}\mathsf{)}$ for all $i\in \{1,\dots ,n\}$. Specifically, given a simulated proof $({\mathsf{U}}_{\mathsf{i}}\mathsf{,}{\mathsf{u}}_{\mathsf{i}}\mathsf{)}$, $\mathcal{S}$ first uses the simulator of the non-interactive folding scheme to simulate ${\overline{T}}_i$. $\mathcal{S}$ then folds ${\mathsf{U}}_{\mathsf{i}}$ and ${\mathsf{u}}_{\mathsf{i}}$ using ${\overline{T}}_i$ to produce ${\mathsf{U}}_{\mathsf{i}\mathsf{+}\mathsf{1}}$. $\mathcal{S}$ simulates ${\mathsf{u}}_{\mathsf{i}}$ using the observation that all terms are randomized. In the final round, $\mathcal{S}$ folds ${\mathsf{u}}_{\mathsf{n}}$ and ${\mathsf{U}}_{\mathsf{n}}$ (again using a simulated ${\overline{T}}_n$) to produce an instance ${\mathsf{U}}^{\prime }$, and then uses the simulator of the zkSNARK to produce ${\pi }_{{\mathsf{U}}^{\prime }}$. $\mathcal{S}$ outputs $({\mathsf{U}}_{\mathsf{n}}\mathsf{,}{\mathsf{u}}_{\mathsf{n}}\mathsf{,}{\overline{\mathsf{T}}}_{\mathsf{n}}\mathsf{,}{\pi }_{{\mathsf{U}}^{\prime }}\mathsf{)}$. We provide a formal proof in [30, App. D].    $◻$
为了证明零知识，我们构建了一个模拟器 $\mathcal{S}$ ，它首先迭代模拟 $({\mathsf{U}}_{\mathsf{i}}\mathsf{,}{\mathsf{u}}_{\mathsf{i}}\mathsf{)}$ 对于所有 $i\in \{1,\dots ,n\}$ 。具体来说，给定一个模拟证明 $({\mathsf{U}}_{\mathsf{i}}\mathsf{,}{\mathsf{u}}_{\mathsf{i}}\mathsf{)}$ ， $\mathcal{S}$ 首先使用非交互折叠方案的模拟器来模拟 ${\overline{T}}_i$ 。 $\mathcal{S}$ 然后使用 ${\overline{T}}_i$ 将 ${\mathsf{U}}_{\mathsf{i}}$ 和 ${\mathsf{u}}_{\mathsf{i}}$ 折叠，以产生 ${\mathsf{U}}_{\mathsf{i}\mathsf{+}\mathsf{1}}$ 。 $\mathcal{S}$ 利用所有项都是随机化的观察来模拟 ${\mathsf{u}}_{\mathsf{i}}$ 。在最后一轮， $\mathcal{S}$ 使用模拟的 ${\overline{T}}_n$ 将 ${\mathsf{u}}_{\mathsf{n}}$ 和 ${\mathsf{U}}_{\mathsf{n}}$ 折叠（再次使用模拟），以产生一个实例 ${\mathsf{U}}^{\prime }$ ，然后使用 zkSNARK 的模拟器来产生 ${\pi }_{{\mathsf{U}}^{\prime }}$ 。 $\mathcal{S}$ 输出 $({\mathsf{U}}_{\mathsf{n}}\mathsf{,}{\mathsf{u}}_{\mathsf{n}}\mathsf{,}{\overline{\mathsf{T}}}_{\mathsf{n}}\mathsf{,}{\pi }_{{\mathsf{U}}^{\prime }}\mathsf{)}$ 。我们在 [30, 附录 D] 中提供了形式化的证明。 $◻$

6 A zkSNARK for Committed Relaxed R1CS
6 一个针对 Committed Relaxed R1CS 的 zkSNARK

As described in Sect. 5.2, Nova needs a zkSNARK for committed relaxed R1CS to prove the knowledge of a valid IVC proof succinctly and in zero-knowledge. This section presents such a zkSNARK by adapting Spartan [38]. We build on Spartan [38] to avoid FFTs and a trusted setup.
如第 5.2 节所述，Nova 需要一个 zkSNARK 来证明对有效的 IVC 证明知识的简洁且零知识证明。本节通过适配 Spartan [38]提出了这样一个 zkSNARK。我们基于 Spartan [38]构建，以避免 FFT 和可信设置。

6.1 Background6.1 背景

We assume familiarity with polynomials. We provide background in [30, App. G].
我们假设读者熟悉多项式。我们提供了背景信息在[30，附录 G]。

Definition 13 (Polynomial Extension)
定义 13（多项式扩展）

Suppose $f:\{0,1{\}}^{\ell }\to \mathbb{F}$ is a function that maps $\ell$-bit strings to an element of $\mathbb{F}$. A polynomial extension of f is a low-degree $\ell$-variate polynomial $\tilde{f}:{\mathbb{F}}^{\ell }\to \mathbb{F}$ such that $\tilde{f}(x)=f(x)$ for all $x\in \{0,1{\}}^{\ell }$. A multilinear extension (MLE) of a function $f:\{0,1{\}}^{\ell }\to \mathbb{F}$ is a low-degree polynomial extension where the extension is a multilinear polynomial.
假设 $f:\{0,1{\}}^{\ell }\to \mathbb{F}$ 是一个将 $\ell$ 位字符串映射到 $\mathbb{F}$ 中一个元素的函数。f 的多项式扩展是一个低度数的 $\ell$ 变元多项式 $\tilde{f}:{\mathbb{F}}^{\ell }\to \mathbb{F}$ ，使得对于所有 $\tilde{f}(x)=f(x)$ 。一个函数 $f:\{0,1{\}}^{\ell }\to \mathbb{F}$ 的多线性扩展（MLE）是一个低度数的多项式扩展，其中扩展是一个多线性多项式。

Every function $f:\{0,1{\}}^{\ell }\to \mathbb{F}$ has a unique MLE, and conversely every $\ell$-variate multilinear polynomial over $\mathbb{F}$ extends a unique function mapping $\{0,1{\}}^{\ell }\to \mathbb{F}$. Below, we use $\tilde{f}$ to denote the unique MLE of f.
每个函数 $f:\{0,1{\}}^{\ell }\to \mathbb{F}$ 都有一个唯一的最大似然估计（MLE），反之，每个 $\ell$ -变元的关于 $\mathbb{F}$ 的多元线性多项式都扩展了一个唯一的函数映射 $\{0,1{\}}^{\ell }\to \mathbb{F}$ 。下面，我们用 $\tilde{f}$ 来表示 f 的唯一 MLE。

Lemma 5引理 5

(The Sum-Check Protocol [35]). For $\ell$-variate polynomial G over $\mathbb{F}$ with degree at most $\mu$ in each variable, there exists a public-coin interactive proof protocol (known as the sum-check protocol) to reduce the task of checking $\sum _{x\in \{0,1{\}}^{\ell }}G(x)=T$ to the task of checking $G(r)=e$ for $r\in {\mathbb{F}}^{\ell }$. The interaction consists of a total of $\ell$ rounds, where in each round the verifier sends a single element of $\mathbb{F}$ and the prover responds with $\mu +1$ elements of $\mathbb{F}$.
（Sum-Check 协议 [35]）。对于在 $\mathbb{F}$ 上定义的、每个变量次数最多为 $\mu$ 的 -变元多项式 G，存在一个公共币交互式证明协议（称为求和校验协议），将检查 $\sum _{x\in \{0,1{\}}^{\ell }}G(x)=T$ 的任务降低为检查 $G(r)=e$ 对于 $r\in {\mathbb{F}}^{\ell }$ 的任务。交互包括总共 $\ell$ 轮，其中在每个轮次中，验证者发送 $\mathbb{F}$ 的单个元素，而证明者响应 $\mu +1$ 个 $\mathbb{F}$ 的元素。

6.2 A Polynomial IOP for Idealized Relaxed R1CS
6.2 理想化松弛 R1CS 的多项式 IOP

Our exposition below is based on Spartan [38] and its recent recapitulation [34]. The theorem below and its proof is a verbatim adaptation of Spartan’s polynomial IOP for R1CS to relaxed R1CS.
以下阐述基于 Spartan [38]及其近期概述[34]。下面的定理及其证明是对 Spartan 的 R1CS 多项式 IOP 的逐字改编，以适应放宽的 R1CS。

Recall that an interactive proof (IP) [25] for a relation $\mathcal{R}$ is an interactive protocol between a prover and a verifier where the prover proves the knowledge of a witness w for a prescribed instance u such that $(u,w)\in \mathcal{R}$. An interactive oracle proof (IOP) [5, 37] generalizes interactive proofs where in each round the prover may send an oracle (e.g., a string) and the verifier may query a previously-sent oracle during the remainder of the protocol. A polynomial IOP [17] is an IOP in which the oracle sent by the prover is a polynomial and the verifier may query for an evaluation of the polynomial at a point in its domain. We consider a (minor) variant of polynomial IOPs, where the verifier has oracle access to polynomials in the R1CS structure and instance.
回忆一下，对于关系 $\mathcal{R}$ 的交互式证明（IP）[25]是一个证明者和验证者之间的交互协议，其中证明者证明了对一个规定的实例 u 的见证 w 的知识，使得 $(u,w)\in \mathcal{R}$ 。交互式预言机证明（IOP）[5, 37]泛化了交互式证明，其中在每个回合中，证明者可以发送一个预言机（例如，一个字符串），验证者可以在协议剩余时间内查询之前发送的预言机。多项式 IOP [17]是一种 IOP，其中证明者发送的预言机是一个多项式，验证者可以查询多项式在其定义域中的某个点的值。我们考虑多项式 IOPs 的一个（较小的）变体，其中验证者可以访问 R1CS 结构和实例中的多项式预言机。

We first construct a polynomial IOP for an idealized version of relaxed R1CS (Definition 14) where the instance contains a purported witness. We then compile it into a zkSNARK for committed relaxed R1CS (Definition 12).
首先，我们为理想化的宽松 R1CS（定义 14）构建一个多项式 IOP，其中实例包含一个所谓的证人。然后，我们将它编译成针对承诺宽松 R1CS（定义 12）的 zkSNARK。

Definition 14 (Idealized Relaxed R1CS)
定义 14（理想化宽松 R1CS）

Consider a finite field $\mathbb{F}$. Let the public parameters consist of size bounds $m,n,\ell \in \mathbb{N}$ where $m>\ell$. The idealized relaxed R1CS structure consists of sparse matrices $A,B,C\in {\mathbb{F}}^{m\times m}$ with at most $n=\text{Ω}(m)$ non-zero entries in each matrix. A idealized relaxed R1CS instance consists of an error vector $E\in {\mathbb{F}}^m$, a scalar $u\in \mathbb{F}$, witness vector $W\in {\mathbb{F}}^m$, and public inputs and outputs $\mathsf{x}\in {\mathbb{F}}^{\ell }$. An instance $(E,u,W,\mathsf{x}\mathsf{)}$ is satisfying if $(A\cdot Z)\circ (B\cdot Z)=u\cdot (C\cdot Z)+E$, where $Z=(W,\mathsf{x}\mathsf{,}\mathsf{u}\mathsf{)}$.
考虑一个有限域 $\mathbb{F}$ 。公参数由大小界限 $m,n,\ell \in \mathbb{N}$ 组成，其中 $m>\ell$ 。理想化的松弛 R1CS 结构由稀疏矩阵 $A,B,C\in {\mathbb{F}}^{m\times m}$ 组成，每个矩阵中最多有 $n=\text{Ω}(m)$ 个非零项。一个理想化的松弛 R1CS 实例由一个错误向量 $E\in {\mathbb{F}}^m$ ，一个标量 $u\in \mathbb{F}$ ，一个见证向量 $W\in {\mathbb{F}}^m$ ，以及公输入和输出 $\mathsf{x}\in {\mathbb{F}}^{\ell }$ 组成。一个实例 $(E,u,W,\mathsf{x}\mathsf{)}$ 如果 $(A\cdot Z)\circ (B\cdot Z)=u\cdot (C\cdot Z)+E$ ，则满足，其中 $Z=(W,\mathsf{x}\mathsf{,}\mathsf{u}\mathsf{)}$ 。

Construction 5建设 5

(Polynomial IOP for Idealized Relaxed R1CS). Consider an idealized relaxed R1CS statement $\text{φ}$ consisting of public parameters $(m,n,\ell )$, structure (A, B, C), and instance $(E,u,W,\mathsf{x}\mathsf{)}$, Without loss of generality, we assume that m and n are powers of 2 and that $m=2\cdot (\ell +1)$.
(多项式 IOP 的理想化松弛 R1CS)。考虑一个由公共参数 $(m,n,\ell )$ 、结构(A, B, C)和实例 $(E,u,W,\mathsf{x}\mathsf{)}$ 组成的理想化松弛 R1CS 语句 $\text{φ}$ ，不失一般性，我们假设 m 和 n 是 2 的幂，并且 $m=2\cdot (\ell +1)$ 。

Let $s=\log m$. We interpret the matrices A, B, C as functions with signature $\{0,1{\}}^{\log m}\times \{0,1{\}}^{\log m}\to \mathbb{F}$ in a natural manner. In particular, an input in $\{0,1{\}}^{\log m}\times \{0,1{\}}^{\log m}$ is interpreted as the binary representation of an index $(i,j)\in [m]\times [m]$, where $[m]:=\{1,\dots ,m\}$ and the function outputs (i, j)th entry of the matrix. As such, let $\tilde{A}$, $\tilde{B}$, and $\tilde{C}$ denote multilinear extensions of A, B, and C interpreted as functions, so they are $2\log m$-variate sparse multilinear polynomials of size n. Similarly, we interpret E and W as functions with respective signatures $\{0,1{\}}^{\log m}\to \mathbb{F}$ and $\{0,1{\}}^{\log m-1}\to \mathbb{F}$. Furthermore, let $\tilde{E}$ and $\tilde{W}$ denote the multilinear extensions of E and W interpreted as functions, so they are multilinear polynomials in $\log m$ and $\log m-1$ variables respectively.
;; 将下一行文本作为纯文本输入，并将其翻译为简体中文，仅输出翻译。如果某些内容无需翻译（如专有名词、代码等），则保持原文不变。不要解释，输入文本: Let $s=\log m$ . 我们将矩阵 A、B、C 解释为具有签名 $\{0,1{\}}^{\log m}\times \{0,1{\}}^{\log m}\to \mathbb{F}$ 的函数，以自然的方式。特别是，输入 $\{0,1{\}}^{\log m}\times \{0,1{\}}^{\log m}$ 被解释为索引 $(i,j)\in [m]\times [m]$ 的二进制表示，其中 $[m]:=\{1,\dots ,m\}$ ，函数输出矩阵的第 (i, j) 个元素。因此，让 $\tilde{A}$ ， $\tilde{B}$ ，和 $\tilde{C}$ 表示 A、B 和 C 的多线性扩展，作为函数，它们是 n 维的 -变量稀疏多线性多项式。同样，我们将 E 和 W 解释为具有相应签名 $\{0,1{\}}^{\log m}\to \mathbb{F}$ 和 $\{0,1{\}}^{\log m-1}\to \mathbb{F}$ 的函数。此外，让 $\tilde{E}$ 和 $\tilde{W}$ 表示 E 和 W 的多线性扩展，作为函数，它们分别是 $\log m$ 和 $\log m-1$ 变量的多线性多项式。

As noted earlier, the verifier has an oracle access to the following polynomials: $\tilde{A}$, $\tilde{B}$, $\tilde{C}$, $\tilde{E}$, and $\tilde{W}$. Additionally, the verifier reads u and $\mathsf{x}$ in entirety.
如前所述，验证者有权访问以下多项式： $\tilde{A}$ ， $\tilde{B}$ ， $\tilde{C}$ ， $\tilde{E}$ ，以及 $\tilde{W}$ 。此外，验证者将 u 和 $\mathsf{x}$ 完整读取。

Let $Z=(W,\mathsf{x}\mathsf{,}\mathsf{u}\mathsf{)}$. Similar to how we interpret matrices as functions, we interpret Z and $(\mathsf{x}\mathsf{,}\mathsf{u}\mathsf{)}$ as functions with the following respective signatures: $\{0,1{\}}^s\to \mathbb{F}$ and $\{0,1{\}}^{s-1}\to \mathbb{F}$. Observe that the MLE $\tilde{Z}$ of Z satisfies
类似我们将矩阵解释为函数的方式，我们将 Z 和 $(\mathsf{x}\mathsf{,}\mathsf{u}\mathsf{)}$ 解释为具有以下相应签名的函数： $\{0,1{\}}^s\to \mathbb{F}$ 和 $\{0,1{\}}^{s-1}\to \mathbb{F}$ 。观察 Z 的最大似然估计（MLE） $\tilde{Z}$ 满足

$$\begin{array}{r}\tilde{Z}(X_1,\dots ,X_s)=(1-X_1)\cdot \tilde{W}(X_2,\dots ,X_s)+X_1\cdot \widetilde{(\mathsf{x}\mathsf{,}\mathsf{u}\mathsf{)}}(X_2,\dots ,X_s)\end{array}$$

(1)

Similar to [38, Theorem 4.1], checking if $\text{φ}$ is satisfiable is equivalent, except for a soundness error of $\log m/|\mathbb{F}|$ over the choice of $\tau \in {\mathbb{F}}^s$, to checking if the following identity holds:
与[38, 定理 4.1]类似，检查 $\text{φ}$ 是否可满足等价于检查以下恒等式成立，除了在 $\log m/|\mathbb{F}|$ 关于 $\tau \in {\mathbb{F}}^s$ 的选择上存在一个正确性错误：

$$\begin{array}{r}0\stackrel{?}{=}\sum _{x\in \{0,1{\}}^s}\widetilde{\mathsf{e}\mathsf{q}}(\tau ,x)\cdot F(x),\end{array}$$

(2)

where哪里

$$\begin{array}{rl}F(x)=& \left(\sum _{y\in \{0,1{\}}^s}\tilde{A}(x,y)\cdot \tilde{Z}(y)\right)\cdot \left(\sum _{y\in \{0,1{\}}^s}\tilde{B}(x,y)\cdot \tilde{Z}(y)\right)\\ & -(u\cdot \sum _{y\in \{0,1{\}}^s}\tilde{C}(x,y)\cdot \tilde{Z}(y)+\tilde{E}(x)),\end{array}$$

and $\widetilde{\mathsf{e}\mathsf{q}}$ is the multilinear extension of $\mathsf{e}\mathsf{q}:\{0,1{\}}^s\times \{0,1{\}}^s\to \mathbb{F}$ where $\mathsf{e}\mathsf{q}(x,e)=1$ if $x=e$ and 0 otherwise.

That is, if $\text{φ}$ is satisfiable, then Eq. (2) holds with probability 1 over the choice of $\tau$, and if not, then Eq. (2) holds with probability at most $O(\log m/|\mathbb{F}|)$ over the random choice of $\tau$.

To compute the right-hand side in Eq. (2), the prover and the verifier apply the sum-check protocol to the following polynomial: $g(x):=\widetilde{\mathsf{e}\mathsf{q}}(\tau ,x)\cdot F(x)$ From the verifier’s perspective, this reduces the task of computing the right-hand side of Eq. (2) to the task of evaluating g at a random input $r_x\in {\mathbb{F}}^s$. Note that the verifier can locally evaluate $\widetilde{\mathsf{e}\mathsf{q}}(\tau ,r_x)$ in $O(\log m)$ field operations via $\widetilde{\mathsf{e}\mathsf{q}}(\tau ,r_x)=\prod _{i=1}^s({\tau }_i{r}_{x,i}+(1-{\tau }_i)(1-r_{x,i}))$. With $\widetilde{\mathsf{e}\mathsf{q}}(\tau ,r_x)$ in hand, $g(r_x)$ can be computed in O(1) time given the four quantities: $\sum _{y\in \{0,1{\}}^s}\tilde{A}(r_x,y)\cdot \tilde{Z}(y)\text{,}$ $\sum _{y\in \{0,1{\}}^s}\tilde{B}(r_x,y)\cdot \tilde{Z}(y)\text{,}$ $\sum _{y\in \{0,1{\}}^s}\tilde{C}(r_x,y)\cdot \tilde{Z}(y)\text{,}$ and $\tilde{E}(r_x)\text{.}$
为了计算方程（2）的右侧，证明者和验证者应用求和校验协议于以下多项式： $g(x):=\widetilde{\mathsf{e}\mathsf{q}}(\tau ,x)\cdot F(x)$ 从验证者的角度来看，这把计算方程（2）右侧的任务简化为在随机输入 $r_x\in {\mathbb{F}}^s$ 上评估 g 的任务。请注意，验证者可以通过 $\widetilde{\mathsf{e}\mathsf{q}}(\tau ,r_x)$ 在 $O(\log m)$ 域中本地评估 $\widetilde{\mathsf{e}\mathsf{q}}(\tau ,r_x)=\prod _{i=1}^s({\tau }_i{r}_{x,i}+(1-{\tau }_i)(1-r_{x,i}))$ 。有了 $\widetilde{\mathsf{e}\mathsf{q}}(\tau ,r_x)$ ，在给定四个数量： $\sum _{y\in \{0,1{\}}^s}\tilde{A}(r_x,y)\cdot \tilde{Z}(y)\text{,}$ $\sum _{y\in \{0,1{\}}^s}\tilde{B}(r_x,y)\cdot \tilde{Z}(y)\text{,}$ $\sum _{y\in \{0,1{\}}^s}\tilde{C}(r_x,y)\cdot \tilde{Z}(y)\text{,}$ 和 $\tilde{E}(r_x)\text{.}$ 的情况下，可以在 O(1)时间内计算 $g(r_x)$ 。

The last quantity can be computed with a single query to polynomial $\tilde{E}$. Furthermore, the first three quantities can be computed by applying the sum-check protocol three more times in parallel, once to each of the following three polynomials (using the same random vector of field elements, $r_y\in {\mathbb{F}}^s$, in each of the three invocations): $\tilde{A}(r_x,y)\cdot \tilde{Z}(y)\text{,}$ $\tilde{B}(r_x,y)\cdot \tilde{Z}(y)\text{,}$ and $\tilde{C}(r_x,y)\cdot \tilde{Z}(y).$
最后这个数量可以通过对多项式 $\tilde{E}$ 进行单次查询来计算。此外，前三个数量可以通过在三个多项式（使用相同的域元素随机向量 $r_y\in {\mathbb{F}}^s$ 在三次调用中）上并行应用求和校验协议三次来计算： $\tilde{A}(r_x,y)\cdot \tilde{Z}(y)\text{,}$ $\tilde{B}(r_x,y)\cdot \tilde{Z}(y)\text{,}$ 和 $\tilde{C}(r_x,y)\cdot \tilde{Z}(y).$ 。

To perform the verifier’s final check in each of these three invocations of the sum-check protocol, it suffices for the verifier to evaluate each of the above three polynomials at the random vector $r_y$, which means it suffices for the verifier to evaluate $\tilde{A}(r_x,r_y)$, $\tilde{B}(r_x,r_y)$, $\tilde{C}(r_x,r_y)$, and $\tilde{Z}(r_y)$. The first three evaluations can be obtained via the verifier’s assumed query access to $(\tilde{A},\tilde{B},\tilde{C})$. $\tilde{Z}(r_y)$ can be computed (via Eq. (1)) from a query to $\tilde{W}$ and from computing $\widetilde{(\mathsf{x}\mathsf{,}\mathsf{u}\mathsf{)}}$.
执行这三个求和校验协议调用中的验证者最终检查，验证者只需评估上述三个多项式在随机向量 $r_y$ 上的每个，这意味着验证者只需评估 $\tilde{A}(r_x,r_y)$ ， $\tilde{B}(r_x,r_y)$ ， $\tilde{C}(r_x,r_y)$ ，和 $\tilde{Z}(r_y)$ 。前三个评估可以通过验证者对 $(\tilde{A},\tilde{B},\tilde{C})$ 的假设查询访问获得。 $\tilde{Z}(r_y)$ 可以通过查询 $\tilde{W}$ 并计算 $\widetilde{(\mathsf{x}\mathsf{,}\mathsf{u}\mathsf{)}}$ （通过公式（1））来获得。

In summary, we have the following polynomial IOP.
总结来说，我们有以下多项式 IOP。

• 1. $\mathcal{V}\to \mathcal{P}$: $\tau {\in }_R{\mathbb{F}}^s$

• 2. $\mathcal{V}\leftrightarrow \mathcal{P}$: run the sum-check protocol to reduce the check in Eq. (2) to checking if the following hold, where $r_x,r_y$ are vectors in ${\mathbb{F}}^s$ chosen at random by the verifier over the course of the sum-check protocol:
  $\mathcal{V}\leftrightarrow \mathcal{P}$ : 运行求和校验协议以将等式（2）中的校验简化为检查以下条件是否成立，其中 $r_x,r_y$ 是在求和校验协议过程中由验证者随机选择的 ${\mathbb{F}}^s$ 中的向量：

  • $\tilde{A}(r_x,r_y)\stackrel{?}{=}{v}_A$, $\tilde{B}(r_x,r_y)\stackrel{?}{=}{v}_B$, and $\tilde{C}(r_x,r_y)\stackrel{?}{=}{v}_C$;
    $\tilde{A}(r_x,r_y)\stackrel{?}{=}{v}_A$ ， $\tilde{B}(r_x,r_y)\stackrel{?}{=}{v}_B$ ，以及 $\tilde{C}(r_x,r_y)\stackrel{?}{=}{v}_C$ ；

  • $\tilde{E}(r_x)\stackrel{?}{=}{v}_E$; and $\tilde{E}(r_x)\stackrel{?}{=}{v}_E$ ; 以及

  • $\tilde{Z}(r_y)\stackrel{?}{=}{v}_Z$.

• 3. $\mathcal{V}$:

  • check if $\tilde{A}(r_x,r_y)\stackrel{?}{=}{v}_A$, $\tilde{B}(r_x,r_y)\stackrel{?}{=}{v}_B$, and $\tilde{C}(r_x,r_y)\stackrel{?}{=}{v}_C$, with a query to $\tilde{A},\tilde{B},\tilde{C}$ at $(r_x,r_y)$;
    检查 $\tilde{A}(r_x,r_y)\stackrel{?}{=}{v}_A$ ， $\tilde{B}(r_x,r_y)\stackrel{?}{=}{v}_B$ ，以及 $\tilde{C}(r_x,r_y)\stackrel{?}{=}{v}_C$ ，在 $(r_x,r_y)$ 处向 $\tilde{A},\tilde{B},\tilde{C}$ 发起查询；

  • check if $\tilde{E}(r_x)\stackrel{?}{=}{v}_E$ with an oracle query to $\tilde{E}$; and
    检查是否使用预言机查询 $\tilde{E}(r_x)\stackrel{?}{=}{v}_E$ 到 $\tilde{E}$ ; 并

  • check if $\tilde{Z}(r_y)\stackrel{?}{=}{v}_Z$ by checking if: $v_Z=(1-r_y[1])\cdot v_W+r_y[1]\cdot \widetilde{(\mathsf{x}\mathsf{,}\mathsf{u}\mathsf{)}}(r_y[\mathrm{2..}])\text{,}$ where $r_y[\mathrm{2..}]$ refers to a slice of $r_y$ without the first element of $r_y$, and $v_W\leftarrow \tilde{W}(r_y[\mathrm{2..}])$ via an oracle query (see Eq. (1)).
    检查是否 $\tilde{Z}(r_y)\stackrel{?}{=}{v}_Z$ 通过检查： $v_Z=(1-r_y[1])\cdot v_W+r_y[1]\cdot \widetilde{(\mathsf{x}\mathsf{,}\mathsf{u}\mathsf{)}}(r_y[\mathrm{2..}])\text{,}$ 其中 $r_y[\mathrm{2..}]$ 指的是 $r_y$ 的一个切片，不包含 $r_y$ 的第一个元素，以及通过预言机查询 $v_W\leftarrow \tilde{W}(r_y[\mathrm{2..}])$ （见公式（1））。

Theorem 5定理 5

Construction 5 is a polynomial IOP for idealized relaxed R1CS defined over a finite field $\mathbb{F}$, with the following parameters, where m denotes the dimension of the R1CS matrices, and n denotes the number of non-zero entries in the matrices: Soundness error is $O(\log m)/|\mathbb{F}|$; round complexity is $O(\log m)$; The verifier has query access to $2\log m$-variate multilinear polynomials $\tilde{A},\tilde{B},\tilde{C}$ in the structure, and $(\log m)$-variate multilinear polynomial $\tilde{E}$, and $(\log m-1)$-variate multilinear polynomial $\tilde{W}$ in the instance; the verifier issues a single query to polynomials $\tilde{A}$, $\tilde{B}$, $\tilde{C}$, and $\tilde{W}$, $\tilde{E}$, and otherwise performs $O(\log m)$ operations over $\mathbb{F}$; the prover performs O(n) operations over $\mathbb{F}$ to compute its messages in the polynomial IOP and to respond to the verifier’s queries to $(\tilde{W},\tilde{E},\tilde{A},\tilde{B},\tilde{C})$.
构造 5 是一个在有限域 $\mathbb{F}$ 上定义的理想化松弛 R1CS 的多项式 IOP，具有以下参数，其中 m 表示 R1CS 矩阵的维度，n 表示矩阵中的非零项数：正确性错误是 $O(\log m)/|\mathbb{F}|$ ；轮复杂度是 $O(\log m)$ ；验证者可以查询结构中的 $2\log m$ -变元多线性多项式 $\tilde{A},\tilde{B},\tilde{C}$ ，以及实例中的 $(\log m)$ -变元多线性多项式 $\tilde{E}$ ，和 $(\log m-1)$ -变元多线性多项式 $\tilde{W}$ ；验证者对多项式 $\tilde{A}$ ， $\tilde{B}$ ， $\tilde{C}$ ，和 $\tilde{W}$ ， $\tilde{E}$ 发起单个查询，否则在 $O(\log m)$ 上执行 $\mathbb{F}$ 操作；证明者对 $\mathbb{F}$ 执行 O(n)操作来计算其在多项式 IOP 中的消息并响应验证者的查询 $(\tilde{W},\tilde{E},\tilde{A},\tilde{B},\tilde{C})$ 。

Proof证明

Perfect completeness follows from perfect completeness of the sum-check protocol and the fact that Eq. (2) holds with probability 1 over the choice of $\tau$ if $\text{φ}$ is satisfiable. Applying a standard union bound to the soundness error introduced by probabilistic check in Eq. (2) with the soundness error of the sum-check protocol [35], we conclude that the soundness error for the depicted polynomial IOP as at most $O(\log m)/|\mathbb{F}|$.
完美完备性源于求和校验协议的完美完备性以及等式（2）在概率 1 下对 $\tau$ 的选择成立的事实，如果 $\text{φ}$ 是可满足的。将标准并集界限应用于等式（2）中由概率校验引入的可靠性错误以及求和校验协议的可靠性错误[35]，我们得出结论，所描述的多项式 IOP 的可靠性错误至多为 $O(\log m)/|\mathbb{F}|$ 。

The sum-check protocol is applied four times (although three of the invocations occur in parallel and in practice combined into one [38]). In each invocation, the polynomial to which the sum-check protocol is applied has degree at most 3 in each variable, and the number of variables is $s=\log m$. Hence, the round complexity of the polynomial IOP is $O(\log m)$. Since each polynomial has degree at most 3 in each variable, the total communication cost is $O(\log m)$ field elements.
协议在四次（尽管三次调用是并行进行的，实际上合并为一次[38]）应用。在每次调用中，应用于求和校验协议的多项式的每个变量的次数最多为 3，变量的数量为 $s=\log m$ 。因此，多项式 IOP 的轮复杂度为 $O(\log m)$ 。由于每个多项式在每个变量上的次数最多为 3，总通信成本为 $O(\log m)$ 域元素。

The claimed verifier runtime is immediate from the verifier’s runtime in the sum-check protocol, and the fact that $\widetilde{\mathsf{e}\mathsf{q}}$ can be evaluated at any input $(\tau ,r_x)\in {\mathbb{F}}^{2s}$ in $O(\log m)$ field operations. As in Spartan [38], the prover’s work in the polynomial IOP in O(n) operations over $\mathbb{F}$ using prior techniques [42, 46].    $◻$
所声称的验证器运行时间是来自验证器运行时的即时性，以及 $\widetilde{\mathsf{e}\mathsf{q}}$ 可以在 $O(\log m)$ 域操作中的任何输入 $(\tau ,r_x)\in {\mathbb{F}}^{2s}$ 处进行评估。正如在 Spartan [38]中，证明者在多项式 IOP 中使用先前技术[42, 46]在 $\mathbb{F}$ 上进行 O(n)操作的工作。 $◻$

6.3 Compiling Polynomial IOPs to zkSNARKs
6.3 编译多项式 IOPs 到 zkSNARKs

As in prior works [17, 20, 38], we compile our polynomial IOP into a zkSNARK using a polynomial commitment scheme [28] and the Fiat-Shamir transform [22].
与先前的工作[17, 20, 38]一样，我们使用多项式承诺方案[28]和 Fiat-Shamir 变换[22]将我们的多项式 IOP 编译成 zkSNARK。

Interpreting Commitments to Vectors as Polynomial Commitments. It is well known that commitments to m-sized vectors over $\mathbb{F}$ are commitments to $\log m$-variate multilinear polynomials represented with evaluations over $\{0,1{\}}^m$ [32, 38, 44, 47]. Furthermore, there is a polynomial commitment scheme for $\log m$-variate multilinear polynomials if there exists an argument protocol to prove an inner product computation between a committed vector and an m-sized public vector $((r_1,1-r_1)\otimes \dots \otimes (r_{\log m},1-r_{\log m}))$, where $r\in {\mathbb{F}}^{\log m}$ is an evaluation point. There are two candidate constructions in the literature. Note that the primary difference between two schemes is in the verifier’s time.
将向量的承诺解释为多项式承诺。众所周知，在 $\mathbb{F}$ 上对 m 大小的向量的承诺是对 $\log m$ -变元的多元线性多项式的承诺，这些多项式通过在 $\{0,1{\}}^m$ [ 32, 38, 44, 47]上的评估来表示。此外，如果存在一个论证协议来证明一个承诺的向量和 m 大小的公共向量 $\log m$ 之间的内积计算，那么就有一个多元线性多项式的多项式承诺方案。文献中有两种候选构造。请注意，两种方案之间的主要区别在于验证者的时间。

• 1. ${\mathsf{P}\mathsf{C}}_{\mathsf{B}\mathsf{P}}$. If the commitment scheme for vectors over $\mathbb{F}$ is Pedersen’s commitments, as in prior work [44], Bulletproofs [14] provides a suitable inner product argument protocol. The polynomial commitment scheme here achieves the following efficiency characteristics, assuming the hardness of the discrete logarithm problem. For a $\log m$-variate multilinear polynomial, committing takes $O_{\lambda }(m)$ time to produce an $O_{\lambda }(1)$-sized commitment; the prover incurs $O_{\lambda }(m)$ costs to produce an evaluation proof of size $O_{\lambda }(\log m)$ that can be verified in $O_{\lambda }(m)$. Note that ${\mathsf{P}\mathsf{C}}_{\mathsf{B}\mathsf{P}}$ is a special case of Hyrax’s polynomial commitment scheme [44].
  ${\mathsf{P}\mathsf{C}}_{\mathsf{B}\mathsf{P}}$ 。如果向量在 $\mathbb{F}$ 上的承诺方案是 Pedersen 的承诺，如先前工作 [44] 中所述，Bulletproofs [14] 提供了一个合适的内积论证协议。这里的多项式承诺方案实现了以下效率特性，假设离散对数问题的难度。对于一个 $\log m$ 变元的多元线性多项式，生成一个 $O_{\lambda }(1)$ 大小的承诺需要 $O_{\lambda }(m)$ 的时间；证明者产生一个大小为 $O_{\lambda }(\log m)$ 的评估证明，该证明可以在 $O_{\lambda }(m)$ 内被验证。请注意， ${\mathsf{P}\mathsf{C}}_{\mathsf{B}\mathsf{P}}$ 是 Hyrax 的多项式承诺方案 [44] 的一个特例。

• 2.  ${\mathsf{P}\mathsf{C}}_{\mathsf{D}\mathsf{o}\mathsf{r}\mathsf{y}}$. If vectors over $\mathbb{F}$ are committed with a two-tiered “matrix” commitment (see for example, [18, 32]), which provides $O_{\lambda }(1)$-sized commitments to m-sized vectors under the SXDH assumption. With this commitment scheme, Dory [32] provides the necessary inner product argument. The polynomial commitment here achieves the following efficiency characteristics, assuming the hardness of SXDH. For a $\log m$-variate multilinear polynomial, committing takes $O_{\lambda }(m)$ time to produce an $O_{\lambda }(1)$-sized commitment; the prover incurs $O_{\lambda }(m)$ costs to produce an evaluation proof of size $O_{\lambda }(\log m)$ that can be verified in $O_{\lambda }(\log m)$.
  ${\mathsf{P}\mathsf{C}}_{\mathsf{D}\mathsf{o}\mathsf{r}\mathsf{y}}$ 。如果向量在 $\mathbb{F}$ 上使用双层“矩阵”承诺（例如参见[ 18, 32]），这为 m 大小的向量提供了 $O_{\lambda }(1)$ 大小的承诺，基于 SXDH 假设。在这种承诺方案中，Dory [ 32] 提供了必要的内积论证。这里的多项式承诺在假设 SXDH 的困难性下实现了以下效率特性，对于一个 $\log m$ 变元的多元线性多项式，承诺需要 $O_{\lambda }(m)$ 的时间来生成一个 $O_{\lambda }(1)$ 大小的承诺；证明者产生一个大小为 $O_{\lambda }(\log m)$ 的评估证明，该证明可以在 $O_{\lambda }(\log m)$ 内被验证。

Polynomial Commitments for Sparse Multilinear Polynomials. In our constructions below, we require polynomial commitment schemes that can efficiently handle sparse multilinear polynomials. Spartan [38, §7] (and its optimization [41, §6]) provides a generic compiler to transform existing polynomial commitment schemes for multilinear polynomials into those that can efficiently handle sparse multilinear polynomials. Specifically, we apply [34, Theorem 5]) (which captures Spartan’s compiler in a generic manner) to ${\mathsf{P}\mathsf{C}}_{\mathsf{B}\mathsf{P}}$ and ${\mathsf{P}\mathsf{C}}_{\mathsf{D}\mathsf{o}\mathsf{r}\mathsf{y}}$ to obtain their variants that can efficiently handle sparse multilinear polynomials; we refer to them as “Sparse-${\mathsf{P}\mathsf{C}}_{\mathsf{B}\mathsf{P}}$” and “Sparse-${\mathsf{P}\mathsf{C}}_{\mathsf{D}\mathsf{o}\mathsf{r}\mathsf{y}}$” respectively.
多项式承诺用于稀疏多线性多项式。在我们下面的构造中，我们需要能够高效处理稀疏多线性多项式的多项式承诺方案。Spartan [38, §7]（及其优化[41, §6]）提供了一个通用的编译器，可以将现有的多线性多项式多项式承诺方案转换为能够高效处理稀疏多线性多项式的方案。具体来说，我们将[34, 定理 5]（以通用方式捕捉 Spartan 编译器）应用于 ${\mathsf{P}\mathsf{C}}_{\mathsf{B}\mathsf{P}}$ 和 ${\mathsf{P}\mathsf{C}}_{\mathsf{D}\mathsf{o}\mathsf{r}\mathsf{y}}$ ，以获得它们各自的变体，这些变体可以高效处理稀疏多线性多项式；我们分别称它们为“Sparse- ${\mathsf{P}\mathsf{C}}_{\mathsf{B}\mathsf{P}}$ ”和“Sparse- ${\mathsf{P}\mathsf{C}}_{\mathsf{D}\mathsf{o}\mathsf{r}\mathsf{y}}$ ”。

Theorem 6定理 6

(A zkSNARK from ${\mathsf{P}\mathsf{C}}_{\mathsf{B}\mathsf{P}}$). Assuming the hardness of the discrete logarithm problem, there exists a zkSNARK in the random oracle model for committed relaxed R1CS with the following efficiency characteristics, where m denotes the dimensions of R1CS matrices and n denotes the number of non-zero entries in the matrices: The encoder runs in time $O_{\lambda }(n)$; The prover runs in time $O_{\lambda }(n)$; The proof length is $O_{\lambda }(\log n)$; and the verifier runs in time $O_{\lambda }(n)$.⁶
(一个来自 ${\mathsf{P}\mathsf{C}}_{\mathsf{B}\mathsf{P}}$ 的 zkSNARK)。假设离散对数问题的难度，在随机预言模型中存在一个针对承诺放松 R1CS 的 zkSNARK，具有以下效率特性，其中 m 表示 R1CS 矩阵的维度，n 表示矩阵中的非零条目数：编码器运行时间为 $O_{\lambda }(n)$ ；验证者运行时间为 $O_{\lambda }(n)$ ；证明长度为 $O_{\lambda }(\log n)$ ；验证者运行时间为 $O_{\lambda }(n)$ 。 ⁶

Proof证明

For R1CS structure (A, B, C), we first have the encoder directly provide $(\tilde{A},\tilde{B},\tilde{C})$ in the prover key, and additionally provide sparse polynomial commitments to $\tilde{A},\tilde{B},\tilde{C}$ using Sparse-${\mathsf{P}\mathsf{C}}_{\mathsf{B}\mathsf{P}}$ in both the prover and verifier keys. Next, we apply the compiler of [17] using ${\mathsf{P}\mathsf{C}}_{\mathsf{B}\mathsf{P}}$ to the polynomial IOP from Construction 5. At a high level, this replaces all of the oracles provided to the verifier with ${\mathsf{P}\mathsf{C}}_{\mathsf{B}\mathsf{P}}$ commitments, which the prover and verifier then use to simulate ideal queries to a committed oracle. By [17, Theorem 6] this provides a public-coin honest-verifier zero-knowledge interactive argument of knowledge. In particular, we can treat the resulting protocol as an argument for committed relaxed R1CS because the verifier is now provided with (polynomial) commitments to E and W. Applying the Fiat-Shamir transform [22] achieves non-interactivity and zero-knowledge in the random oracle model.
对于 R1CS 结构（A，B，C），我们首先在验证者密钥中让编码器直接提供 $(\tilde{A},\tilde{B},\tilde{C})$ ，并在验证者和验证者密钥中额外使用 Sparse- ${\mathsf{P}\mathsf{C}}_{\mathsf{B}\mathsf{P}}$ 对 $\tilde{A},\tilde{B},\tilde{C}$ 提供稀疏多项式承诺。接下来，我们使用[17]中的 ${\mathsf{P}\mathsf{C}}_{\mathsf{B}\mathsf{P}}$ 编译器对构造 5 中的多项式 IOP 进行编译。从高层次来看，这用 ${\mathsf{P}\mathsf{C}}_{\mathsf{B}\mathsf{P}}$ 承诺替换了提供给验证者的所有预言机，验证者和验证者随后使用这些承诺来模拟对已提交预言机的理想查询。根据[17，定理 6]，这提供了一个公钥诚实验证者零知识交互论证。特别是，我们可以将生成的协议视为对提交放松 R1CS 的论证，因为验证者现在提供了对 E 和 W 的（多项式）承诺。应用 Fiat-Shamir 变换[22]在随机预言机模型中实现了非交互性和零知识。

The claimed efficiency follows from the efficiency of the polynomial IOP, ${\mathsf{P}\mathsf{C}}_{\mathsf{B}\mathsf{P}}$, and Sparse-${\mathsf{P}\mathsf{C}}_{\mathsf{B}\mathsf{P}}$. In more detail, using Sparse-${\mathsf{P}\mathsf{C}}_{\mathsf{B}\mathsf{P}}$, the encoder takes $O_{\lambda }(n)$ time to create commitments $2\log m$-variate sparse multilinear polynomials $\tilde{A},\tilde{B},\tilde{C}$. The prover’s costs in the polynomial IOP is O(n). Furthermore, proving the evaluations of two $O(\log m)$-variate multilinear polynomials using ${\mathsf{P}\mathsf{C}}_{\mathsf{B}\mathsf{P}}$, it takes $O_{\lambda }(m)$ time. And, to prove the evaluations of three $2\log m$-variate sparse multilinear polynomials of size n, using Sparse-${\mathsf{P}\mathsf{C}}_{\mathsf{B}\mathsf{P}}$, it takes $O_{\lambda }(n)$ time. In total, the prover time is $O_{\lambda }(n)$. The proof length in the polynomial IOP is $O(\log m)$, and the proof sizes in the polynomial evaluation proofs is $O_{\lambda }(\log n)$, so the proof length is $O_{\lambda }(\log n)$. The verifier’s time in the polynomial IOP is $O(\log m)$. In addition, it verifies five polynomial evaluations, which costs $O_{\lambda }(n)$ time: the two polynomial in the instance take $O_{\lambda }(m)$ time using ${\mathsf{P}\mathsf{C}}_{\mathsf{B}\mathsf{P}}$, and the three polynomials in the structure takes $O_{\lambda }(n)$ time using Sparse-${\mathsf{P}\mathsf{C}}_{\mathsf{B}\mathsf{P}}$. So, in total, the verifier time is $O_{\lambda }(n)$.    $◻$
所声称的效率来源于多项式 IOP 的效率， ${\mathsf{P}\mathsf{C}}_{\mathsf{B}\mathsf{P}}$ ，以及 Sparse- ${\mathsf{P}\mathsf{C}}_{\mathsf{B}\mathsf{P}}$ 。更详细地说，使用 Sparse- ${\mathsf{P}\mathsf{C}}_{\mathsf{B}\mathsf{P}}$ ，编码器需要 $O_{\lambda }(n)$ 时间来创建承诺 $2\log m$ -变元的稀疏多线性多项式 $\tilde{A},\tilde{B},\tilde{C}$ 。在多项式 IOP 中，证明者的成本是 O(n)。此外，使用 ${\mathsf{P}\mathsf{C}}_{\mathsf{B}\mathsf{P}}$ 证明两个 $O(\log m)$ -变元多线性多项式的评估需要 $O_{\lambda }(m)$ 时间。而且，要证明大小为 n 的三个 $2\log m$ -变元稀疏多线性多项式的评估，使用 Sparse- ${\mathsf{P}\mathsf{C}}_{\mathsf{B}\mathsf{P}}$ ，需要 $O_{\lambda }(n)$ 时间。总而言之，证明者的时间是 $O_{\lambda }(n)$ 。在多项式 IOP 中的证明长度是 $O(\log m)$ ，多项式评估证明中的证明大小是 $O_{\lambda }(\log n)$ ，因此证明长度是 $O_{\lambda }(\log n)$ 。在多项式 IOP 中，验证者的时间是 $O(\log m)$ 。此外，它验证了五个多项式评估，这需要 $O_{\lambda }(n)$ 时间：实例中的两个多项式使用 ${\mathsf{P}\mathsf{C}}_{\mathsf{B}\mathsf{P}}$ 需要 $O_{\lambda }(m)$ 时间，结构中的三个多项式使用 Sparse- ${\mathsf{P}\mathsf{C}}_{\mathsf{B}\mathsf{P}}$ 需要 $O_{\lambda }(n)$ 时间。因此，验证者的总时间是 $O_{\lambda }(n)$ 。 $◻$

Corollary 1推论 1

(A zkSNARK from ${\mathsf{P}\mathsf{C}}_{\mathsf{D}\mathsf{o}\mathsf{r}\mathsf{y}}$). Assuming the hardness of the SXDH problem, there exists a zkSNARK in the random oracle model for committed relaxed R1CS with the following efficiency characteristics, where m denotes the dimensions of R1CS matrices and n denotes the number of non-zero entries in the matrices: The encoder runs in time $O_{\lambda }(n)$; The prover runs in time $O_{\lambda }(n)$; The proof length is $O_{\lambda }(\log n)$; and the verifier runs in time $O_{\lambda }(\log n)$.
(一个来自 ${\mathsf{P}\mathsf{C}}_{\mathsf{D}\mathsf{o}\mathsf{r}\mathsf{y}}$ 的 zkSNARK)。假设 SXDH 问题的难度，在随机预言模型中存在一个针对承诺放松 R1CS 的 zkSNARK，具有以下效率特性，其中 m 表示 R1CS 矩阵的维度，n 表示矩阵中的非零条目数：编码器运行时间为 $O_{\lambda }(n)$ ；验证者运行时间为 $O_{\lambda }(n)$ ；证明长度为 $O_{\lambda }(\log n)$ ；验证者运行时间为 $O_{\lambda }(\log n)$ 。