Sin7y Tech Review (34): Is SuperNova's Folding Scheme the Endgame for ZK?

This article is the 34th series of the Sin7y Tech Review and will mainly interpret SuperNova, which is 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:

1. instances -> 1 instance: We need a random number r, for linear combination, which can come from the verifier or an oracle
2. Given two instances:
   
   $$A{Z}_1\circ B{Z}_1=C{Z}_1$$
   
   $$A{Z}_2\circ B{Z}_2=C{Z}_2$$
3. Let
   $$Z=Z_1+r\cdot Z_2$$
4. Given two instances:
   
   $$\begin{gathered} AZ\circ BZ \\ =A(Z_1+r\cdot Z_2)\circ B(Z_1+r\cdot Z_2) \\ =(A{Z}_1+r\cdot A{Z}_2)\circ (B{Z}_1+r\cdot B{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) \end{gathered}$$
   
   $$\begin{gathered} CZ \\ =C(Z_1+r\cdot Z_2) \\ =C{Z}_1+r\cdot C{Z}_2 \\ =A{Z}_1\circ B{Z}_1+r\cdot (A{Z}_2\circ B{Z}_2) \end{gathered}$$
5. Therefore, after simple folding, the new instance Z does not satisfy the relation:
   $$AZ\circ BZ=CZ$$
6. Upon careful observation, it can be seen that, apart from the difference in the number of addition terms, some coefficients of the addition terms are also different. Therefore, two elements need to be added: an expansion coefficient and a correction vector
7. Thus, a relaxed R1CS model is defined as follows:
   
   $$AZ\circ BZ=\mu \cdot CZ+E$$For a native R1CS instance, we have
   $\mu =1,E=0$, and for a folded R1CS instance, we have
   $\mu ={\mu }_1+r{\mu }_2,E=\ast \ast$
8. Continuing from step 5, to make them equal, the following processing is required:
   
   $$\begin{gathered} CZ+r\cdot CZ+r\cdot (A{Z}_1\circ B{Z}_2+A{Z}_2\circ B{Z}_1)-r\cdot (A{Z}_1\circ B{Z}_1+A{Z}_2\circ B{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) \\ =AZ\circ BZ \\ =(1+r)\cdot CZ+r\cdot (A{Z}_1\circ B{Z}_2+A{Z}_2\circ B{Z}_1-C{Z}_1-C{Z}_2) \end{gathered}$$
9. Therefore, the merged R1CS instance satisfies:
   a.
   $\mu ={\mu }_1+r\cdot {\mu }_2$，for native R1CS instances, it always holds that:
   $\mu =1,E=0$$
   b.
   $E=r\cdot (A{Z}_1\circ B{Z}_2+A{Z}_2\circ B{Z}_1-{\mu }_{2}C{Z}_1-{\mu }_{1}C{Z}_2)+E_1+r^2\cdot E^2$

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):

In the given context:

1. $C$: The circuit corresponding to the computation,
   $F^{\prime }(z_i)=z_{i+1}$
2. $u_i$: native R1CS instance,
   $F^{\prime }(z_{i-1})=z_i$
3. $U_i$: Relaxed R1CS instance,
   $(F^{\prime }{)}^{i-1}(z_0)=z_{i-1}$
4. $U_{i+1}$: New relaxed R1CS instance,
   $(F^{\prime }{)}^i(z_0)=z_i$

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
   $\phi$, 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:

1. It introduces additional constraint logic for the selection function
   $\phi$, which takes inputs
   $(w_i,z_i)$ 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
   $p{c}_i$ it updates the corresponding running claims instance running claims
   $U_{p{c}_i}$.

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) - YouTube 43:16s
   b. Refer to Section 4.4 of the research paper
3. Is it possible to execute proof generation in parallel for improved performance?
   a. For example, can we perform parallel proofs for
   $(F^{\prime }{)}^{i/2-1}(z_0)=z_{i/2-1}$ and
   $(F^{\prime }{)}^{i/2}(z_{i/2-1})=z_{i-1}$?
   b. Related discussions can be found at: https://twitter.com/0xevevm/status/1657055222793895937

---

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 [e-mail] if you’d like to join or partner with us.

Stay Tuned

Website | Whitepaper |GitHub | Twitter | Discord | LinkedIn | YouTube | HackMD | Medium | HackerNoon