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

A 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/2023In August 2022, the Office of Foreign Assets Control (OFAC) announced sanctions against Tornado Cash, which directly cast a shadow on protocols aiming to achieve privacy on public blockchains. This led to discouragement in the market towards privacy and raised regulatory concerns. However, Ola, an Ethereum Layer 2 network that supports programmable privacy utilizing its ZK-ZKVM architecture, still recognizes the urgent need for robust privacy across the blockchain space. Ola is not the first project dedicated to bringing privacy to blockchains, nor will it be the last. As a member of the blockchain community, Ola is committed to interpreting the privacy technologies used in most projects and the regulatory compliance issues involved in privacy transactions, in order to help the market understand privacy on top of public blockchains more comprehensively. 1. Why was Tornado Cash banned? The reason for Tornado Cash's blacklisting by OFAC is obvious: its transactions can not be tracked. This has made Tornado Cash widely used for illegal activities. The principle of privacy in Tornado Cash differs from that of Zcash, which is entirely based on ZK technology. Tornado Cash combines coin mixing and ZK technology, with coin mixing making transactions untraceable. As the coin-mixing pool grows larger, the chances of tracking it approach zero. ZK is only used to realize its own asset proof once the coin mixing is complete. Therefore, Tornado Cash is called a haven for hackers and black money, as it is impossible to track the addresses to which non-performing assets are withdrawn after entering the mixing pool. This is also the underlying reason for Tornado Cash's blacklisting. Many articles interpret the principle of coin-mixing in Tornado Cash, which readers can find for themselves.

5/22/2023TL;DR We are working on building the first ZKVM based on a parallel execution architecture and achieving higher TPS through the improvement of ZK-friendly design and ZK algorithms. The technical features are as follows:Fast proof generationZK-friendly: smaller circuit scale and simplified bottom constraint units Fast ZK: further optimization on Plonky2 Fast execution: Utilizing parallel execution to significantly shorten the proof generation time Current progress: In July 2022, we released the OlaVM Whitepaper. November 2022, completed instruction set design and development, and realized the OlaVM execution module of the virtual machine, you can check the link: https://github.com/Sin7Y/olavm to view our code, continuously updated.

1/10/2023Preface This research compares implementation systems similar to Ethereum and analyzes the difficulties and possibilities of achieving parallel execution of transactions. It's worth noting that the chains analyzed for this research are based on the Account model design scheme, not including the UTXO scheme. Research Objects FISCO-BCOS, one of the consortium blockchains that support parallel execution of transaction verification within blocks. Khipu public chain, scala implementation of the Ethereum protocol. Aptos public chain, Move Virtual Machine. Difficulties with Parallel Execution Let's take a look at the traditional transaction execution process.

1/4/2023
Published on ** HackMD**