This article will mainly interpret , a new recursive proof system for incrementally producing succinct proofs of correct execution of programs on a stateful machine with a particular instruction set. SuperNova 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 itself. paper What is folding? First, let’s look at the definition in the paper: As shown by the green marker in the figure: input: two (instance, witness) pairs output: a new (instance, witness) pair the same size: the size of the input tuples needs to be the same, which also means they correspond to . The diagram below expresses the folding concept very well (source: ): the same computation 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: m: the number of variables, i.e., the size of vector Z n: the number of non-zero elements in the matrix l: the number of public I/Os A, B, C: coefficient matrices, each corresponds to a calculation Z.W: private input Z.x: public I/O 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: Introduce a commitment scheme to ensure the effectiveness of folding. 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 , as defined in the paper: IVC In the image, the green and red markers represent the following: Standard IVC: It applies to a single constraint type, such as VDF, where there is only one type of computation. 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: Compared to IVC, which corresponds to a single function, NIVC corresponds to multiple functions. 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 It introduces additional constraint logic for the selection function φ, which takes inputs ( ) and outputs the index of the next instruction. wi,zi It maintains a running claims list where the number of elements is equal to the number of instructions. U Based on the instruction index it updates the corresponding running claims instance running claims . pci 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 The first recursion approach: . The circuit implements all the verification processes, similar to the recursive structure in Plonky2 and Plonk. without delay The second recursion approach: . The circuit implements partial verification processes and ultimately achieves one-time verification, as seen in Halo’s Accumulator scheme. part-verify delay The third recursion approach: . It utilizes the folding scheme to continuously compress instances and generates the proof at the end. prover delay Questions 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. Does the size of the running claims need to match the number of instructions? EVM has 140+ instructions. 43:16s a. Refer to the video: ZK Study Club: Supernova (Srinath Setty - MS Research) - YouTube b. Refer to Section 4.4 of the research paper Is it possible to for 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 found . execute proof generation in parallel here 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 if you’d like to join or partner with us. contact@sin7y.org Also published . here

This writer has a vested interested be it monetary, business, or otherwise, with 1 or more of the products or companies mentioned within.

Is SuperNova’s Folding Scheme the Endgame for ZK?

About Author

Comments

TOPICS

THIS ARTICLE WAS FEATURED IN

Related Stories

A Study on Parallel Execution: Everything You Need to Know

(1/100) Crypto Countdown: Golem

A Research Report on the Trader $JOE DeFi Platform

07/03/2018: Biggest Stories in the Cryptosphere

05/02/2018: Biggest Stories in the Cryptosphere

01/06/2018: Biggest Stories in the Cryptosphere

A Study on Parallel Execution: Everything You Need to Know

(1/100) Crypto Countdown: Golem

A Research Report on the Trader $JOE DeFi Platform

07/03/2018: Biggest Stories in the Cryptosphere

05/02/2018: Biggest Stories in the Cryptosphere

01/06/2018: Biggest Stories in the Cryptosphere

Light-Mode

Classic

Newspaper

Dark-Mode

Neon Noir

Minty

HN StartUps