A Review of Folding Schemes

1. Introduction

A folding scheme, applicable to NP relations, involves a protocol between an untrusted prover and a verifier, each possessing two NP instances of size N. The prover also has purported witnesses for these instances. This protocol results in a single N-sized NP instance, called the folded instance, and a corresponding witness generated privately by the prover. The essence of the scheme is that the folded instance is satisfiable only if the original instances are. It’s considered non-trivial if it reduces the verifier’s costs and communication compared to verify witnesses for each original instance separately. Unlike techniques in protocols like Bulletproofs, which divide and combine inner product instances, a folding scheme specifically folds NP relations.

2. Folding Schemes

Nova: Nova, a significant innovation in zero-knowledge proofs, utilizes a unique folding scheme based on relaxed R1CS statements. Specifically, a relaxed R1CS instance consists of an error vector E, a scalar u, and public inputs and outputs x. An instance (E, u, x) is satisfied by a witness W, if

where Z = (W, x, u). Its main feature is the ability to merge two instances of the same NP problem into one while keeping the problem type intact. This process is more than just layering one problem over another; it intricately combines them, ensuring the new, single instance upholds the complexity and attributes of both original problems. As a result, the problem becomes more efficient to solve or verify, yet retains its original depth and integrity. This aspect is particularly vital in cryptography, where maintaining problem integrity is essential. Nova thus represents a sophisticated method in problem consolidation, enhancing efficiency without compromising complexity, a notable advancement in zero-knowledge proofs.

SuperNova: SuperNova is an innovative recursive proof system designed for succinctly verifying the correct execution of programs on stateful machines with specific instruction sets, such as EVM or RISC-V. A key feature of SuperNova is that the cost of proving a single step in a program is directly proportional to the size of the circuit representing the instruction executed in that step. This approach marks a significant departure from previous methods that rely on universal circuits, where the proving cost for a program step is at least equal to the combined sizes of circuits for each supported instruction, even if only one instruction is invoked in that step. As a result, SuperNova can accommodate a comprehensive instruction set without increasing the proving costs for individual steps.

Sangria: In a similar vein to Nova, which employs a folding scheme based on relaxed R1CS statements, Sangria utilizes folding based on a variant of the PLONK arithmetization. More precisely, for a standard PLONK gate

the relaxed PLONK gate equation imports a scalar u and error e:

Besides, Sangria extends the relaxed PLONK arithmetization to accept custom gates of degree 2 and circuits with higher gate arity. Let q_G be a selector vector. The gate equation can be written as

Therefore, the degree 2 custom gates can be written as

CCS: Customizable Constraint System (CCS) is a generalization of R1CS that can simultaneously capture R1CS, Plonkish, and AIR without overheads. A CCS instance consists of public input x. A CCS witness consists of a vector w. A CCS structure-instance tuple (S, x) is satisfied by a CCS witness w if

where z = (w,1,x), M_j · z denotes matrix-vector multiplication, denotes the Hadamard product between vectors, and is a m-sized vector with entries equal to the additive identity in F.

Representing R1CS with CCS: Let t = 3; q = 2; d = 2, M_0 = A, M_1 = B, M_2 = C, S_1 = {0, 1}, S_2 = {2}, c_0 = 1, c_1 = −1, then the CCS equation becomes

Representing Plonkish with CCS: According to Hadamard production, we have the following equations:

and

Therefore, the standard plonk gate

can be converted to a CCS expression

Representing AIR with CCS: Let l=2 and n = m · t/2.

• Unless set to a specific value below, any entry in M_0,…, M_{t−1} equals 0.
• There is a CCS row for each of the m constraints in AIR, so, if we index the CCS rows by {0,…,m-1}, it suffices to specify how the i-th row of these matrices is set, for i = 0,…,m-1. For all j∈{0,1,…,t — 1}, let k_j = i · t=2 + j, and we have such setups: 1) If i = 0 and j < t/2, set M_j[i][j+|w|] = 1; 2) If i = m-1 and j ≥ t/2, set M_j[i][j+|w|+t/2] = 1; 3) Otherwise, we set M_j[i][k_j] = 1.

HyperNova: HyperNova represents a highly efficient and recursive ZK-SNARK designed for proving incremental computations, where each computational step is represented using committed CCS (Constraint Composition Systems). It leverages an early iteration of SuperSpartan, a framework for constructing new folding schemes adaptable to various constraints. The core concept behind HyperNova is the creation of a polynomial that encapsulates claims about high-degree constraints along with previous claims. When subjected to a sum check, this polynomial yields claims formatted suitably for folding, eliminating the need for cross-terms.

HyperNova can be implemented through two distinct methodologies:

• Direct Approach: This method builds directly upon the non-interactive multi-folding scheme tailored for CCS. It focuses on straightforwardly applying the principles of multi-folding to the constraints represented within the CCS framework.
• Alternative Approach: This strategy combines the multi-folding scheme with the use of Nova as a ‘black box’. By integrating Nova’s capabilities, this approach potentially enhances the versatility and efficiency of HyperNova, especially in contexts where Nova’s specific folding strategies are advantageous.

These methodologies underscore HyperNova’s versatility and its potential to advance the field of cryptographic proofs, particularly in scenarios requiring efficient and scalable verification of complex computations.

ProtoStar: ProtoStar, instead of conducting a traditional sum-check reduction, simplifies an instance into a randomized sum of itself and then applies a folding process to this randomized sum. The folding primarily involves merging random coefficients from the new sum with the existing accumulator, and validating these coefficients’ structure, specifically their formation as consecutive powers of a challenge β. This necessitates committing to the vector of β’s powers, introducing group operations in the folding verifier, which performs scalar multiplications on these commitments.

ProtoGalaxy: ProtoGalaxy, building on ProtoStar concepts, offers a folding scheme where the recursive verifier’s additional work is minimal, involving only logarithmic field operations and a constant number of hashes. This efficiency is further amplified when folding multiple instances in one step, reducing the verifier’s field operations per instance to a constant. Additionally, ProtoGalaxy enhances the accumulator claim process by using a new challenge, which avoids the commitment to power vectors and ensures a concise (log N length) coefficient representation for a polynomial of degree log(N). This approach enables recursive computation in O(n) operations, bypassing the more complex O(Nlog(N)) requirement.

CycleFold: CycleFold enhances folding-scheme-based recursive arguments by efficiently employing a cycle of elliptic curves, reducing the necessity for multiple scalar multiplications in verifiers (2 in Nova, 1 in HyperNova, and 3 in ProtoStar). It utilizes the second curve in the cycle to represent a single scalar multiplication, significantly reducing circuit sizes compared to previous methods. This is especially advantageous in “half pairing” cycles like BN254/Grumpkin, keeping circuits minimal on the non-pairing-friendly curve. The argument includes instances on both curves, provable using a zkSNARK over the first curve’s scalar field, optimizing efficiency and circuit complexity.

KiloNova: KiloNova is a non-uniform Proof-carrying Data (PCD) system with zero-knowledge features, inspired by HyperNova. It utilizes a variant of the CCS with linear claims on circuits and inputs to avoid cross items. A generic folding scheme for handling multiple circuit instances was developed, ensuring zero-knowledge properties through various methods. The system incorporates optimization techniques like circuit aggregation and decoupling, enhancing the performance of this non-uniform ZK-PCD scheme.

BaseFold: BaseFold generalizes the Fast Reed Solomon Interactive Oracle Proof of Proximity (FRI IOPP) to a wider range of linear codes, termed foldable linear codes. This involves constructing a new family of these codes, specifically a type of randomly punctured Reed-Muller code, and establishing tight bounds on their minimum distance. Additionally, BaseFold introduces a multilinear Polynomial Constraint System (PCS) from any foldable linear code, combining BaseFold with the sum-check protocol for multilinear polynomial evaluation. This includes a new multilinear PCS derived from FRI. Practically, BaseFold with the new codes offers a balanced tradeoff between prover time, proof size, and verifier time, compared to previous methods.

3. Applications

Incrementally-Verifiable Computation (IVC) utilizes non-interactive folding schemes for verifying sequential computations expressed as y=F^l(x), where F is the computation, l is the number of steps, x is the public input, and y is the output. In IVC, each step’s proof is generated by the prover, building upon the previous step’s verified proof. This involves proving an expanded circuit that combines F’s circuit with a verifier circuit. The process is recursive, with the final proof validating the entire computation. Importantly, the verifier’s workload and proof size are independent of the number of steps, focusing only on the final step’s proof.

4. Conclusion

The overarching aim of the zero-knowledge industry we try to achieve: significantly reducing proof generation costs, maintaining small proof sizes, and efficient verification. This has been pursued through prover optimization and data compression techniques. In recent years, significant advancements in folding scheme techniques have been made, revolutionizing incrementally verifiable computation (IVC) in Zero-Knowledge Proofs. This paper provides a comprehensive overview of the prevailing folding scheme in the zero-knowledge proof, outlining its principles and advantages. It also discusses the application of folding schemes in IVC, highlighting their role in enhancing the efficiency and accuracy of computational processes within Zero-Knowledge Proofs. However, these schemes are not the final solution, and their integration into existing ZK protocols remains an ongoing endeavor.