1. Arithmetization

SNARKs

Commonly known SNARKs are Groth16 and Plonk. Their end-to-end processes share a lot of similarities, although there are some key differences, which we will explore in a difference article.

Process

1. Arithmetization

2. R1CS representation

3. R1CS to QAP

4. Encrypting QAP

5. Salting

We will explore the process above through the example function of $out = y^2 + 4x^2y -2$

In this scenario, the user claims to know the solution for the function. This means he claims to know some value of x, y and out that fulfils the relationship described by the function.

This can also be expressed as a program:

def someProblem(x, y, out):
		res = y^2 + 4*(x^2)*y -2 
		**assert out == res, "incorrect inputs";**

Arithmetization: Flattening of computations

Arithmetization is just a fancy way of saying we want to flatten our problem into a series of simple computational steps.

The objective is to flatten the equation or program into a series of intermediate steps, where each intermediate step only contains only a single multiplication between unknown variables (in this case x and y):

1. ($y^2$): v1 = y * y

2. ($x^2$): v2 = x * x

3.        out = v1 + 4v2y - 2  —>   out - v1  + 2 = 4v2 * y

We keep the RHS a multiplication between 2 unknown variables, and move everything else to the LHS.

As a consequence of this process, we introduce intermediate variables.

Notice that we have obtained a system of equations, which serve as a system of constraints:

v1  == y * y
v2  == x * x 
out == v1 + (4v2 * y) - 2

For now, a simple way to think of this is that the user inputs must serve to honour this system of constraints to be the correct answer for the initial problem.

The purpose of this step is to obtain a set of polynomial constraints, which would be used in the next section for R1CS representation.

At this point it should be clear what our witness is: [1 out x y v1 v2]. You will notice that the ordering is somewhat different from the earlier section, and we have introduced 1 as part of the line-up; this is will be made apparent in later sections.