Revolutionary progress in zero-knowledge proof technology: an in-depth exploration of the Nova algorithm

Some time ago I was translating a book on zero-knowledge proof technology. The basic content was translated at the end of last month. The translation took much longer than I expected. We are currently discussing some clerical errors in the book with the author and preparing for the final draft.

Anyway, I finally have some time to look at something new. Let’s start with the Nova algorithm~

Nova algorithm related information

Three pieces of information can help understand the Nova algorithm:

1. Nova paper:
2. Nova potential attacks and corresponding corrections:
3. Summary of understanding of Nova’s potential attacks:

This article is an understanding and summary of the above information. **Some of the pictures in this article come from the above information and will not be labeled one by one in this article. **

Start with IVC

The Nova algorithm is a new zero-knowledge proof algorithm for IVC (Incrementally Verifiable Computation). IVC, that is, the same function iteratively calculates the previous output as the next input. The iterative calculation process of the F function is as follows:

z0 is the initial input, and the result generated by the F function calculation is used as the input of the next F function.

Relax R1CS and Slack Commitment R1CS

As we all know, R1CS is a representation of circuit constraints in zero-knowledge proof technology. Relaxed R1CS can be seen as an extended form of R1CS. On the basis of R1CS, a scalar u and an error vector E are added. An instance of relaxed R1CS is represented by (E, u, x).

The relaxed commitment R1CS commits the E and W vectors based on the relaxed R1CS. An instance of a slack commitment R1CS is represented by (\bar{E}, u, \bar{W}, x), where x and u are public variables.

Extension from R1CS to relaxed R1CS for folding scheme. Note that from the perspective of relaxed R1CS, R1CS is a special case of it. In other words, R1CS is also a "special" slack R1CS.

Folding Scheme

Intuitively speaking, a folding scheme for a relation R is to "collapse" two instances conforming to the relation R into a new instance of the composite relation R. Slack R1CS/Relax Commitment R1CS can perform similar folds. The folding process is similar for both. The folding scheme of Slack Commitment R1CS is as follows:

The entire folding scheme consists of 4 steps. In the first step, the prover P sends a commitment \bar{T} of the cross item T to the verifier. In the second step, the verifier sends a random challenge r to the prover. The third step is the folding of the commitment that both the prover and the verifier need to perform. In the fourth step, the prover performs alone and folds the E and W vectors of the two instances.

Augmented function F' (Argumented Function)

Collapse scheme, the collapsed R1CS instance is relaxed. So what are the calculations proved by these relaxed R1CS examples? Obviously, these calculations include folding calculations. These calculations are not just the F function in IVC calculations, they are also called augmented functions F'. The calculation of the augmented function F' mainly consists of two parts:

1/ F function in IVC

2/ Folding calculation of R1CS instance

Ideal look

With the above understanding, you can imagine the folding process:

Among them, circuit is the circuit corresponding to the augmented function F'. acc{1,2,3,4,5,6} is a slack commitment R1CS instance. The circuit has two calculations: 1/Relax the folding of the commitment R1CS instance, such as acc1+acc2->acc3. 2/Calculate the F function, changing the state from state1 to state2, and then from state2 to state3, etc.

Note that the circuit corresponding to the augmented function F' is itself an R1CS instance, which can be expressed as a relaxed R1CS instance. That is acc4 and acc6 in the picture. "summarize" is to convert a slack R1CS instance into a slack committed R1CS instance.

Looking carefully at the input of the second circuit, acc3 is the relaxed commitment R1CS instance after folding, and acc4 is the relaxed commitment R1CS instance that proves acc3 is the correct folding result. These two instances will enter the next folding and generate acc5. You can imagine that if acc3 and acc4 are satisfiable slack commitment R1CS instances, it means that acc3 is folded from two satisfiable slack commitment R1CS instances. In other words, acc1 and acc2 are satisfiable slack commitments. R1CS instance. This kind of reliability can be deduced "forward" step by step, thus proving that the F function calculation in each circuit is correct. In general, through the satisfiability of two slack commitment R1CS instances corresponding to a certain circuit, all previous IVC calculations can be proven to be correct.

Real look

Friends who are familiar with zero-knowledge proofs know that elliptic curves are often used in polynomial commitment schemes. The corresponding polynomial commitment on the scalar domain is represented by the base domain of the elliptic curve. R1CS circuits are usually represented by the scalar domain. Look carefully, the "summarize" in the above picture involves domain conversion. That is, if you want to fold the slack commitment R1CS instance corresponding to a circuit, you must "fold" it in another circuit. At this time, an elliptic curve cycle needs to be introduced. Between two or more elliptic curves, the scalar domain of one curve is the same as the base domain of the other curve. Coincidentally, the scalar domain of this curve is the same as the base domain of the previous curve. Using such an elliptic curve loop, the "ideal look" can be realized:

The entire folding process is divided into two circuits for folding. The upper part can be called the fold of Circuit 1, and the lower part can be called the fold of Circuit 2. A formal representation of the relationship between the two circuits is on page 8 of the paper "Potential Attacks on Nova and Corresponding Corrections". U represents the folded instance, and u represents the relaxed instance corresponding to an R1CS instance. Note that Circuit 1 collapses the slack commitment R1CS instance corresponding to Circuit 2, while Circuit 2 collapses the slack commitment R1CS instance corresponding to Circuit 1. The main purpose of Circuit 2 is to collapse the slack commitment R1CS instance corresponding to Circuit1, and the function calculation in its circuit is meaningless. Instead, the F function is implemented in Circuit 1. Combined with the "ideal appearance", we can roughly guess the satisfiability of U{i+2}^2, u{i+2}^1, u{i+2}^2, U{i+2}^1 is an important part of the proof.

Because the "circuit" is cut into two parts, and the respective circuit is folded in the other circuit. There are several binding issues between instances: the binding between u and U instances and the binding of u instances passing between two circuits. In order to solve these binding problems, x_0/x_1 public variables are introduced in the circuit, where x_1 specifies the circuit output U instance bound to the u instance and the output of the current F function (in order to simplify the circuit structure , not reflected in the figure). You think, if the H_1 result of the U instance is introduced in the circuit, if the u instance is satisfiable, x_0/x_1 is both real and reliable, that is, it is "bound" to U. x_0 establishes the binding relationship between input u and U, and x_1 establishes the binding relationship between output u and U.

For example, when u{i+1}^1 is used as the input of the second half of the circuit, it passes through Circuit 2, and its output u{i+1}^2.x0 = u{i+1}^1.x1, so , when input to the upper part of the circuit, if u{i+1}^2 can be satisfied, then its x_0 should be equal to the result of H1 of U_{i+1}^2. This is checked in Circuit 1. This way, it is guaranteed that the correct instance is passed between the two circuits.

Proof of IVC

In order to prove that IVC is calculated correctly in a certain iteration, the following information needs to be proved logically:

In addition to proving that four instances can be satisfied, it is also necessary to prove the binding relationship between two x1, as shown in the following figure:

Whether this information is correct requires additional proof circuit implementation. That is, the proof of the IVC calculation is a proof of the circuit. It is conceivable that if it is a calculation with many iterations, these iterations originally need to be carried out in the circuit one by one, but now only four circuit instances need to be verified for satisfiability and binding relationships. The performance improvement is huge.

Attack and Algorithm Correction

Seeing the picture above, I have an intuition. I feel that the instances of the upper and lower circuits are "separated" and have no binding. In fact, this is how the attack is structured.

Forged U_i^1 and U{i+1}^2, although they are forged, are satisfiable instances. Forge u{i+1}^1, modify x_0 and x_1 to correspond to the forged U instance. Obviously, the u{i+1}^1 instance is not satisfied. Although it is not satisfied, the circuit of Circuit 2 can still be satisfied, but the output U{i+1}^1 instance is not satisfied. If u{i+1}^2 is successfully constructed, Circuit 1 can construct satisfactory u{i+2}^1 and U_{i+2}^2, and satisfy the binding relationship of x1. In this way, half of the final forgery proof is constructed first. Through symmetry, the output instance of the lower half can be constructed. By "splicing" the results of the two constructions, the proof of the IVC calculation can be forged.

The revised check logic is as follows:

Chapter 6 of the paper "Potential Attacks on Nova and Corresponding Fixes" provides a detailed security analysis. Interested friends can check the original paper by themselves.

The basic idea of Nova is to fold circuit instances through a folding scheme. The logic is rather convoluted and requires careful thinking about the circuit folding process and the binding relationships in the circuit.

One word to describe it: Absolute~