# Incrementally Verifiable Computation: NOVA

## Understanding R1CS: Rank-One Constraint Systems

R1CS or Rank-One Constraint System, is a mathematical construct used to encode polynomial equations in matrices 𝐴, 𝐵, and 𝐶, where each row of the matrices corresponds to a system of equations of the form:

Az×Bz=Cz

, where 𝐴, 𝐵, 𝐶 are matrices with few nonzero entries and the product symbol (×) means that the matrices are multiplied entry-wise. The variables in each equation have a maximum degree of two. Moreover, any bounded computation can be expressed as an R1CS, and the same arithmetic circuits can be represented by different R1CSs.

### Application of R1CS

R1CS has numerous applications, including in zero-knowledge proof systems such as zkSNARKs constructions. It allows for efficient verification of computations without revealing any sensitive information. Additionally, R1CS can be used in cryptographic protocols for secure communication.

### Limitations of R1CS

While R1CS is a powerful tool, it has some limitations. One of the main limitations is that it does not work well with folding schemes. A folding scheme is a cryptographic protocol that allows for the efficient verification of multiple computations with a single proof. However, R1CS is not well-suited for this purpose.

### Overcoming these limitations

Folding protocols, leveraging vector and polynomial commitments, offer a solution to these limitations by enabling efficient verification of multiple computations with a single proof. The following section describes the workings of Folding protocols and presents their advantages.

## Vector and KZG Polynomial Commitments
In cryptography, various primitives exist that enable one to commit to a value and subsequently prove its properties without revealing the value itself. One such primitive is vector commitment. In this section, we will explore vector commitments and their homomorphic variant, KZG polynomial commitments, including their applications in cryptographic protocols such as zkSNARKs and secure multiparty computation.

### What are Vector Commitments?
Vector commitments enable a user to commit to a vector of values and subsequently prove properties about the vector, such as its length or the value at a specific index, without revealing the entire vector. A homomorphic vector commitment allows for operations to be performed on the committed vector, such as addition or scalar multiplication. Polynomial commitment schemes, such as Pedersen commitments, support addition homomorphically, making them well-suited for performing operations on committed vectors.

### What are KZG Polynomial Commitments?

A polynomial commitment scheme is a cryptographic primitive that allows one to commit to a given polynomial while keeping it hidden from others, with the ability to reveal the committed polynomial later. Additionally, it enables the verification of claimed evaluations of the committed polynomial without disclosing the entire polynomial.

KZG polynomial commitments are a specific type of polynomial commitment scheme that utilizes pairings and polynomial commitments to verify the validity of a degree 𝑛 polynomial using 𝑛 queries. They are built upon vector commitments and can be viewed as a special case of them. The final construction boasts a small verifier circuit (approximately 20,000 constraints in R1CS), facilitating fast proof generation and verification.

### Additive Homomorphism and Succinctness

A polynomial commitment scheme requires additive homomorphism to support operations on committed vectors.

Additive homomorphism means that given two variables 𝑎 and 𝑏, the commitment satisfies the property:

com(𝑎 + 𝑏) = com(𝑎) + com(𝑏)

, where com(𝑥) represents the commitment of 𝑥.

Both KZG and Pedersen commitments exhibit additive homomorphism. Additionally, they offer constant communication and computation costs for the verifier, enabling blockchain nodes to operate without additional burden.

Another essential property of a polynomial commitment scheme is succinctness, which dictates that the commitment size should be logarithmic in the size of the opened polynomial. For instance, if we have a degree 𝑛 polynomial, its commitment should utilize at most 𝑙𝑜𝑔(𝑛) elements.

## High-level Overview of Nova

Nova is another technique for Incrementally Verifiable Computation (IVC) that utilizes a cryptographic primitive called a Folding scheme. Simply put, it is a proving system that employs Folding schemes and KZG polynomial commitments to achieve IVC. This allows for proving that a function 𝐹 was repeatedly applied to some initial state 𝑧, resulting in a sequence of states 𝑧, 𝐹(𝑧), 𝐹(𝐹(𝑧)), and so on.

This section will offer a high-level description of the Nova technique and how it operates.

Understanding Incrementally Verifiable Computation (IVC)
To gain a better understanding of Nova, it is crucial to grasp the concept of IVC. IVC is a technique that facilitates proving that a function was iteratively applied to an initial state, generating a sequence of states. The primary objective of IVC is to merge two instances of a given NP problem into a single case.

### How Nova Works

Nova takes incremental computations, where each step is an R1CS; the constraint system includes a verification circuit, which has to check the correctness of the execution of the last step. However, instead of verifying the proof $∏{_N}{_-}{_1}$ , Nova sees it as an R1CS case and folds it into a current relaxed R1CS. To do this, we have to modify the R1CS to add an error term 𝐸 and a scalar 𝑢 to get a relaxed R1CS, which we can use to make an efficient folding scheme:

${Az}$ x ${Bz = uCz + E}$

If 𝐸 is the zero vector and 𝑢 = 1, then we have 𝐴𝑧 × 𝐵𝑧 = 𝐶𝑧. Namely, any R1CS can also be seen as a relaxed R1CS. Relaxed R1CS keeps the property that it is NP-complete, which means that we can change any NP problem to it. We want the folding scheme to combine two cases of R1CS with the same matrices 𝐴, 𝐵, 𝐶 into one case. Each R1CS has its own instance-witness pairs (that is, public and private data), 𝑧𝑖 = (𝑤𝑖 , 𝑥𝑖), and we want to make a new 𝑧 = (𝑤, 𝑥) that meets the R1CS system of equations with 𝐴, 𝐵, 𝐶, such that this also means that each 𝑧𝑖 = (𝑤𝑖 , 𝑥𝑖) does so. One way to do this is by having the verifier pick a random 𝑟 and do the following change:

${z}$ = ${z{_1} + rz{_2}}$

This change would work for linear systems of equations, however since the R1CS is nonlinear, we cannot use this simple method. If we put this into the R1CS then we have the following:

Az${_1}$ x Bz${_1}$ + r(Az${_1}$ x Bz${_2}$ + Az${_2}$ x Bz${_1}$) + r$^2$