# Sin7y Tech Review (34): Is SuperNova's Folding Scheme the Endgame for ZK?![](https://hackmd.io/_uploads/rkLrzROBh.png)
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 ](https://eprint.iacr.org/2022/1758.pdf)itself.
## What is folding?
First, let's look at the definition in the paper:![](https://hackmd.io/_uploads/rkU-ieFSn.png)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](https://www.youtube.com/watch?v=ilrvqajkrYY&t=1096s)):![reference link](https://hackmd.io/_uploads/HkW4hgKHh.png)
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:![](https://hackmd.io/_uploads/ry6P2gFH2.png)
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:
$$AZ_1 \circ BZ_1 = CZ_1$$
$$AZ_2 \circ BZ_2 = CZ_2$$
3. Let $$Z = Z_1 + r \cdot Z_2$$
4. Given two instances:
$$AZ \circ BZ \\
= A(Z_1 + r \cdot Z_2) \circ B (Z_1 + r \cdot Z_2) \\
= (AZ_1 + r \cdot AZ_2) \circ (BZ_1 + r \cdot BZ_2)\\
= AZ_1 \circ BZ_1 + r \cdot (AZ_1 \circ BZ_2 + AZ_2 \circ BZ_1) + r^2 \cdot (AZ_2 \circ BZ_2)$$
$$CZ\\
= C(Z_1 + r \cdot Z_2)\\
= CZ_1 + r \cdot CZ_2\\
= AZ_1 \circ BZ_1 + r \cdot (AZ_2 \circ BZ_2)$$
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 =**$
8. Continuing from step 5, to make them equal, the following processing is required:
$$CZ + r \cdot CZ + r \cdot (AZ_1 \circ BZ_2 + AZ_2 \circ BZ_1) - r \cdot (AZ_1 \circ BZ_1 + AZ_2 \circ BZ_2)\\
=AZ_1 \circ BZ_1 + r \cdot (AZ_1 \circ BZ_2 + AZ_2 \circ BZ_1) + r^2 \cdot (AZ_2 \circ BZ_2) \\
=AZ \circ BZ \\
=(1 + r)\cdot CZ + r \cdot (AZ_1 \circ BZ_2 + AZ_2 \circ BZ_1 - CZ_1 - CZ_2)
$$
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 (AZ_1 \circ BZ_2 + AZ_2 \circ BZ_1 - \mu_2CZ_1 - \mu_1CZ_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](https://www.youtube.com/watch?v=ilrvqajkrYY&t=1096s)):
![reference link](https://hackmd.io/_uploads/B1GUJbKB2.png)
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](https://www.youtube.com/watch?v=ilrvqajkrYY&t=1096s)):
![reference link](https://hackmd.io/_uploads/SyJjJWKSn.png)
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.](https://eprint.iacr.org/2023/573.pdf)
## Nova: NIVC for a single instruction
NIVC(Non-uniform incrementally verifiable computation), NIVC (Non-uniform incrementally verifiable computation) is a generalization of [IVC](https://iacr.org/archive/tcc2008/49480001/49480001.pdf) , as defined in the paper:
![reference link](https://hackmd.io/_uploads/rkGl-ZtS2.png)
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](https://www.youtube.com/watch?v=ilrvqajkrYY&t=1096s)):![reference link](https://hackmd.io/_uploads/ByWEbWFS2.png)
In the given context:
1. $C$: The circuit corresponding to the computation, $F'(z_i) = z_{i+1}$
2. $u_i$: native R1CS instance, $F'(z_{i-1}) = z_{i}$
3. $U_i$: Relaxed R1CS instance, $(F')^{i-1}(z_0) = z_{i-1}$
4. $U_{i+1}$: New relaxed R1CS instance, $(F')^{i}(z_0) = z_{i}$
## SuperNova: NIVC for multiple instructions(ZKVM)
As defined in the paper:![reference link](https://hackmd.io/_uploads/BkRcb-tSh.png)
1. Compared to IVC, which corresponds to a single function, NIVC corresponds to multiple functions.
2. It introduces an additional selection polynomial $\varphi$, 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](https://www.youtube.com/watch?v=ilrvqajkrYY&t=1096s)):![reference link](https://hackmd.io/_uploads/r1aRWZYr3.png)
Compared to Nova:
1. It introduces additional constraint logic for the selection function $\varphi$, 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 $pc_i$ it updates the corresponding running claims instance running claims $U_{pc_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](https://www.youtube.com/watch?v=0LW-qeVe6QI)):![reference link](https://hackmd.io/_uploads/r1WNGWFH2.png)
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](https://www.youtube.com/watch?v=ilrvqajkrYY&t=1096s) 43:16s
[b. Refer to Section 4.4 of the research paper](https://eprint.iacr.org/2022/1758.pdf)
3. Is it possible to [execute proof generation in parallel](https://eprint.iacr.org/2012/095.pdf) for improved performance?
a. For example, can we perform parallel proofs for $(F')^{i/2-1}(z_0) = z_{i/2-1}$ and $(F')^{i/2}(z_{i/2 - 1}) = z_{i-1}$?
b. Related discussions can be found at: [https://twitter.com/0xevevm/status/1657055222793895937](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 <contact@sin7y.org> if you’d like to join or partner with us.
### Stay Tuned
[Website ](https://sin7y.org/)| [Whitepaper](https://olavm.org/) |[GitHub](https://github.com/Sin7Y) | [Twitter](https://twitter.com/Sin7Y_Labs) | [Discord](https://discord.com/invite/vDFy7YEG6j) | [LinkedIn](https://www.linkedin.com/company/olavm-technology-ltd/) | [YouTube](https://www.youtube.com/@Ola_Sin7y) | [HackMD](https://hackmd.io/team/sin7y?nav=overview) | [Medium](https://medium.com/@sin7y) | [HackerNoon](https://hackernoon.com/u/sin7y)

Traditional STARK systems require cyclic groups within the field with a smooth order for efficient processing. FFT (Fast Fourier Transform) is leveraged for efficient calculation of polynomial interpolation points, taking advantage of unit roots with smooth orders in fields. Such fields must have the property of being a power of n to be considered efficient for these operations. However, the efficiency is compromised for fields without this property. Consequently, performing FFT on such fields becomes less efficient. To address this issue, Eli Ben-Sasson and others introduced a fast algorithm for polynomial computations over large finite fields, known as ECFFT (Elliptic Curve Fast Fourier Transform). This algorithm, inspired by Lenstra's methods, extends the applicability of FFT to all prime fields, dramatically enhancing computational capabilities.

4/11/2024During DevConnect Istanbul, I had the privilege of engaging with various project teams and researchers dedicated to privacy-oriented initiatives. We discussed a range of privacy-related topics. To my surprise, I found that the concept of ‘privacy’ is interpreted quite differently by different people, generally falling into two distinct categories:

11/29/2023At Ola, we strongly agree with a16z’s statement in their article “Achieving Crypto Privacy and Regulatory Compliance” about web3:

11/29/2023A comparative study of Aztec, Miden, and Ola In this article, we delve into the concept of "Hybrid Rollup," examining how projects Aztec, Miden, and Ola approach this technology. We investigate their unique smart contract languages, explore state tree designs, and consider the trade-offs in privacy designs. Our objective is to provide a comprehensive overview of Hybrid Rollup technologies, helping you understand their key components and envision their future trajectory. What is Hybrid Rollup? We are delighted to see that our recent initiatives have been garnering an increasing amount of attention in the market. "Hybrid Rollup" is the most accurate summary of what we at Ola have been working on: Rollup: a. It operates at Layer 2, but it also has the flexibility to function at Layer 3, depending on the platform utilized for the verification contract deployment.b. It's a scalability solution.c. It has programmability - "Rollup" doesn't specifically indicate this feature; "Programmable Rollup" is more accurate. Hybrid: a. It supports public, private, and hybrid contract types.b. Developers can freely choose the contract type based on their needs.c. Users can freely choose the transaction type in hybrid contracts.

6/13/2023
Published on ** HackMD**

or

By clicking below, you agree to our terms of service.

Sign in via Facebook
Sign in via Twitter
Sign in via GitHub
Sign in via Dropbox
Sign in with Wallet

Wallet
(
)

Connect another wallet
New to HackMD? Sign up