Is SuperNova’s Folding Scheme the Endgame for ZK?

This article will mainly interpret SuperNova, a new recursive proof system for incrementally producing succinct proofs of correct execution of programs on a stateful machine with a particular instruction set.

These seem to be fantastic features. This article will mainly interpret how these features are implemented.

For easy understanding, all interpretations are based on the paper itself.

What is folding?

First, let’s look at the definition in the paper:

As shown by the green marker in the figure:

1. input: two (instance, witness) pairs

2. output: a new (instance, witness) pair

3. the same size: the size of the input tuples needs to be the same, which also means they correspond to the same computation. The diagram below expresses the folding concept very well (source: ZK Study Club: Supernova (Srinath Setty - MS Research) - YouTube):

   Each gate’s input and output form pairs of (instance, witness), and the same computation represents the same circuit structure and (instance, witness) size.

Represent computation with R1CS

First, let’s look at the definition in the paper:

Here:

1. m: the number of variables, i.e., the size of vector Z
2. n: the number of non-zero elements in the matrix
3. l: the number of public I/Os
4. A, B, C: coefficient matrices, each corresponds to a calculation
5. Z.W: private input
6. Z.x: public I/O
7. Z.1: constant information

Previously, we mentioned that to achieve the folding scheme, it must be the same computation. This way, the coefficient matrix of the corresponding constraint system (R1CS) remains unchanged, thereby achieving the superposition of two computation instances in the constraint system. Let’s try folding:

The following diagram effectively illustrates the settlement process of folded Relaxed R1CS instances (source: ZK Study Club: Supernova (Srinath Setty - MS Research) - YouTube):

From the perspective of preventing malicious behavior by the prover and improving verifier succinctness, the following additions are necessary:

1. Introduce a commitment scheme to ensure the effectiveness of folding.

2. Delegate the processing of E to the prover, while the verifier only verifies the equivalence under the commitment, achieving succinctness for the verifier.
   The complete process is depicted in the following diagram: (Source：ZK Study Club: Supernova (Srinath Setty - MS Research) - YouTube):

Please note that the verifier needs to perform additional calculations on commitments, which requires the adoption of a commitment scheme that supports homomorphic addition calculations.

Note: For relaxed schemes in other constraint systems, you can refer to the paper HyperNova: : Recursive arguments for customizable constraint systems.

Nova: NIVC for a single instruction

NIVC(Non-uniform incrementally verifiable computation), NIVC (Non-uniform incrementally verifiable computation) is a generalization of IVC , as defined in the paper:

In the image, the green and red markers represent the following:

1. Standard IVC: It applies to a single constraint type, such as VDF, where there is only one type of computation.
2. Non-uniform IVC: It applies to multiple constraint types, such as ZKVM, where different instructions lead to different computations and, therefore, different constraints.

The following diagram effectively illustrates the process of Nova (NIVC) (source: ZK Study Club: Supernova (Srinath Setty - MS Research) - YouTube):

SuperNova: NIVC for multiple instructions(ZKVM)

As defined in the paper:

1. Compared to IVC, which corresponds to a single function, NIVC corresponds to multiple functions.
2. It introduces an additional selection polynomial φ, to indicate the function corresponding to each step.

The following diagram effectively represents the process of SuperNova (NIVC for multiple instructions) (source: ZK Study Club: Supernova (Srinath Setty - MS Research) - YouTube):

Compared to Nova:

Comment

1. It introduces additional constraint logic for the selection function φ, which takes inputs (wi,zi) and outputs the index of the next instruction.
2. It maintains a running claims list U where the number of elements is equal to the number of instructions.
3. Based on the instruction index pci it updates the corresponding running claims instance running claims Upci.

Different with other Recursion

A comparison of various recursion approaches is shown in the following image (source: ZKP MOOC Lecture 10: Recursive SNARKs - YouTube):

1. The first recursion approach: without delay. The circuit implements all the verification processes, similar to the recursive structure in Plonky2 and Plonk.
2. The second recursion approach: part-verify delay. The circuit implements partial verification processes and ultimately achieves one-time verification, as seen in Halo’s Accumulator scheme.
3. The third recursion approach: prover delay. It utilizes the folding scheme to continuously compress instances and generates the proof at the end.

Questions

1. Is it possible to define a computation that covers all computations? This way, we wouldn’t need to separately maintain a running list.

This is the current implementation approach in ZKVM and ZKEVM, where a universal circuit is designed to cover the processing logic for all instructions. However, for specific computations like Keccak and ECDSA, separate sub-circuits are used, similar to the idea of adding a running claim instance in the above-mentioned approaches.

2. Does the size of the running claims need to match the number of instructions? EVM has 140+ instructions.
   a. Refer to the video: ZK Study Club: Supernova (Srinath Setty - MS Research) - YouTube43:16s
   b. Refer to Section 4.4 of the research paper

3. Is it possible to execute proof generation in parallelfor improved performance?
   a. For example, can we perform parallel proofs for**(F′)i/2−1(z0) = zi/2−1 and (F′)i/2(zi/2−1)=zi−1**?
   b. Related discussions can be foundhere.

About

This weekly report aims to provide an update on the latest developments and news related to Sin7y - Ola and zero-knowledge cryptography, which has the potential to revolutionize the way we approach privacy and security in the digital age. We will continue to monitor and report on the latest developments in this field. Please write to [email protected] if you’d like to join or partner with us.