Preamble
In the previous part, we learned about the mathematical and cryptographic basis behind zk-SNARK in a basic way. Now I will continue to delve into newer and quite complex concepts, so that you can understand more deeply the technology behind zk-SNARK !
Arithmetic Circuit (Arithmetic Circuit)
Concept of arithmetic circuit
An arithmetic circuit is a Directed Acyclic Graph (DAG), or simply put, a directed acyclic graph consisting of:
The nodes act as addition and multiplication gates.
The edges represent conductors, established on a finite field Fp. A wire connects the output of one port to the input of another port. Each port has two inputs and one output.
The arithmetic circuit finishes with a final output. The figure above illustrates an example of an arithmetic circuit where we can see how data is processed and passed through each gate to produce the final result.
The arithmetic circuit tells us about how zk-SNARKs process and prove computations without revealing any information. An arithmetic circuit can be described as a diagram, which contains systematically arranged arithmetic operations.
Operation of Arithmetic Circuits
Considering the figure above, the arithmetic circuit allows us to calculate
Looking at the image above, we see that the process starts from the first kernel gate which receives s1 and s2 as input and produces s4 as output. Next, s4 and s3 are fed into the second kernel gate to produce the final output s5.
For an m port, n wire circuit, we will determine
witness s = (s1, s2, s3,…, sn)
to assign to the n wires of the circuit such that the input and output of each gate will satisfy the constraint determined by the gate's operation.
An m gate, n wire arithmetic circuit determines the relationship across the witnesses
s = (s1, s2, …, sn)
such that for a constant
then
The above constraints belong to a set of m rank-1 constraints, whose purpose is to simulate the relationship between the input and output of a multiplier gate in an arithmetic circuit
An example of a specific rank-1 constraint is Eq
s1 . s2 – s3 = 0.
This equation describes a multiplier gate in the circuit, which takes two inputs, s1 and s2, and then produces an output of s3. Thus, the product of s1 and s2 must equal s3 for the equation to be satisfied.
A set of m of rank-1 constraints like this can be generalized into a Quadratic Arithmetic Program.
QAPs are tools to convert and reduce arithmetic circuits to a form that makes it easier to verify the operations without re-rendering the entire circuit.
Quadratic Arithmetic Program
The core of zk-SNARK lies in Quadratic Arithmetic Programs (QAPs). A QAP can represent any arithmetic circuit, including addition and multiplication gates. Based on a QAP, the prover can produce a proof that he knows the input values without revealing anything about that value or the internal behavior of the program.
zk-SNARK researcher Eran Tromer drew the zk-SNARK construction process from basic mathematical principles as follows:
The steps above can be divided into two halves. In this article, the “first half” of the process will be explained in depth. The “first half” of the process can be considered as the steps from “Computation” to “QAP”, this is the part where the initial computation is converted into a mathematical form that can be used to establish a zk-SNARK.
I will explain in the easiest way to understand like this:
Before we can use zk-SNARK for any computational problem, we must convert the problem into a suitable “form”. This form is called QAP, or “quadratic arithmetic program”.
Once we have converted our problem into a QAP, we will proceed to solve it with some specific inputs. The solution found is called “witness”. This is like when we finish solving a puzzle and know the answer.
Now that we have the answer, we need to create a way to prove we know the answer without revealing it. This process creates a “non-revealing proof,” meaning it allows us to prove that we know the answer without having to say it.
Finally, someone else can use a separate process to check the evidence we have created, to confirm that we actually know the answer without knowing what the answer actually is!
For example: We have the following equation:
x**3 + x + 5 == 37 (suggested answer is 3)
We will prove that we know the solution to the above mathematical equation without having to reveal the solution by writing a simple computer program as follows:
The qevel function will calculate the value of the equation x**3 + x + 5. When we substitute the number 3 into x, the function will return 35, which is the result we want.
However, we will see the limitations of programming languages in this case. This language only supports basic arithmetic operations (+, -, *, /) and powers with fixed exponents (x**7, not x**y). It does not support division with remainder (%) or comparison (>, <, ≤, ≥), because there is no efficient way to perform modulo or comparison directly in finite cyclic group arithmetic.
The solution here is that we can extend this language to support additional operations such as division with remainder and comparison
For example:
if x < 5: y = 7; else: y = 9
by converting them to arithmetic:
y = 7 * (x < 5) + 9 * (x >= 5)
You can refer to a compiler that can be used to convert the code into a usable form for zk-SNARK implemented by vbuterin (for educational purposes only; not yet ready to create QAP for zk- SNARK in practice)
Flattening
The first step to convert to this form of QAP is the "flattening" step, in simple terms, this is the step of transforming the programming code to make it simpler, each line only performs one action. basic.
In the example above, the initial computer program has a complex mathematical expression. The “flattening” process splits this expression into small parts, each part doing just one simple calculation:
sym_1 = x * x
Multiply x by itself to create an intermediate value, called sym_1
y = sym_1 * x
Then multiply the intermediate value sym_1 by x again to produce y, following the exact calculation x^3
sym_2 = y + x
Add y just calculated with x
~out = sym_2 + 5
Finally, add 5 to sym_2 to get the final result and place a ~ before out to indicate that this is the final result of the program.
Extremely easy to understand! This “flattening” process helps prepare the code to be processed by zk-SNARK, because zk-SNARK requires programming code to be in a simple form that can be easily converted into mathematical forms that it can work with. Okay.
Gates to R1CS
Next, we will perform a series of calculations to convert them into a slightly more complex form, called (rank-1 constraint system), abbreviated R1CS.
R1CS is a sequence of groups of three vectors (a, b, c), and the solution to R1CS is a vector s, where s must satisfy the equation:
s . a * s . b – s . c = 0
This checks whether the output value is the correct product of two input values. If all these conditions are satisfied, we have an exact solution vector for the system.
We can see the image below to understand R1CS better:
First of all, we will define the variables used in the system, I will provide the step to map the variables as follows:
“~one” (first subscript represents number 1)
“x” (input variable)
“~out” (output variable)
“sym_1”, “y”, “sym_2” (intermediate variables)
Vector “s” will contain values for all of these variables, in the order defined.
#We will give (a, b, c) the triple for the first gate (for x * x multiplication):
Vectors a and b both contain the value [0, 1, 0, 0, 0, 0] . The number 1 in the second position in each of these vectors represents that the value of the variable x will be used in the calculation. Specifically, this value is multiplied by itself because both a and b place weights at position x
Vector c has the value [0, 0, 0, 1, 0, 0] , with the number 1 in the fourth position, indicating that the value calculated from a and b will be compared with the variable sym_1 in vector s
a = [0, 1, 0, 0, 0, 0] : specifies that the variable “x” will participate in the calculation.
b = [0, 1, 0, 0, 0, 0] : again specifies that “x” will be multiplied by itself.
c = [0, 0, 0, 1, 0, 0] : the result will be stored in the variable “sym_1”
When “x = 3”, the calculation will be “3 * 3 = 9”, which satisfies the constraint “sym_1 = x * x”
#Next is the Second gate (for sym_1 * x multiplication):
Similarly, a = [0, 0, 0, 1, 0, 0] : specify “sym_1” (9 if “x = 3”)
b = [0, 1, 0, 0, 0, 0] : specify “x” (3 if “x = 3”)
c = [0, 0, 0, 0, 1, 0] : result will be saved in “y”
The calculation is “9 * 3 = 27”, which satisfies the constraint
#Next is the Third gate (for x + y addition)
Similar,
a = [0, 1, 0, 0, 1, 0] : specify “x” and “y”
b = [1, 0, 0, 0, 0, 0] : use the value “1” (representing “~one”) so that the addition is performed correctly.
c = [0, 0, 0, 0, 0, 1] : result is saved to “sym_2”
The calculation is “3 + 27 = 30”, which satisfies the constraint “sym_2 = x + y”
#Finally the Fourth gate (for sym_2 + 5 addition):
Similar,
a = [5, 0, 0, 0, 0, 1] : use value “5” from “~one” and value “1” from “sym_2”
b = [1, 0, 0, 0, 0, 0] : again “~one” so that the addition is performed correctly.
c = [0, 0, 1, 0, 0, 0] : result is saved to “~out”
The calculation is “30 + (5*1) = 35”, which satisfies the constraint “~out = sym_2 + 5”
The three columns A, B, and C correspond to vectors “a”, “b”, and “c”. The number “35” at the bottom of column C is the final result (“~out”)
Compare (s . a) * (s . b) and (s . c), they must be equal (their difference must be 0)
At this point, vector “s” will contain the following values:
1: This is the value for the dummy variable ~one, which is always 1 to represent the constant 1.
3: This is the value for the input variable x.
35: This is the desired value, the final result of the program (variable ~out).
9: Result of x * x, stored in sym_1.
27: Result of sym_1 * x, stored in y.
30: Result of y + x, stored in sym_2.
Finally, the complete R1CS is put together as shown below:
R1CS to QAP
The next step is to take this R1CS and convert it into QAP form, but instead of using vectors and dot products like in R1CS
QAP uses “polynomials” because they have special mathematical properties that make the testing process easier.
Lagrange interpolation is a method for drawing a curve (polynomial) passing through a series of known points. If you have a specific number of points and you want a curve (polynomial) that touches all of those points, Lagrange interpolation will help you find that curve.
For example: Suppose we want a polynomial that goes through (1, 3), (2, 2) and (3, 4). We start by creating a polynomial passing through (1, 3), (2, 0) and (3, 0).
A simple way to do this is to take the product of (x-2) and (x-3). This function will have a curvy shape, rising at x=1 and cutting the horizontal axis at x=2 and x=3.
as below:
Now, we just need to “adjust” it so that the height at x=1 is correct:
This makes the polynomial and the graph will display as below:
Then we do the same with the remaining two points and get two more polynomials, add all three together and get:
The original algorithm takes O(n^3) time to calculate because each of the n points requires O(n^2) to multiply the polynomials. However, by thinking smarter, we can reduce this time to O(n^2).
Applying algorithms such as FFT transform, we can reduce the computation time even faster, which is important in applications like zk-SNARK with thousands of gates.
We will apply Lagrange interpolation to transform R1CS, by taking the first value of each vector a, then using this interpolation to create a polynomial for each vector, so that when evaluating the polynomial at an index specific number, we get the first value of the corresponding vector.
Do the same for the first values of vectors b and c, then apply this method to the next elements of each vector in turn.
We will have the result as below:
The algorithm uses a series of increasing coefficients to create a polynomial:
This polynomial is part of the parameters for the QAP (Quadratic Arithmetic Program) version under consideration.
It should be noted that setting these parameters only needs to be done once for each function verified with zk-SNARK; Once set up, they are reusable.
When evaluating all polynomials at x=1, the process is very simple because you just add up all the coefficients (since 1^k is always equal to 1 for all values of k). We will get the results following result:
Polynomial A when evaluated at x = 1 gives all outcomes 0 except the second outcome which is 1
Polynomial B when evaluated at x = 1 also gives all results 0, except the second result which is 1.
Polynomial C when evaluated at x = 1 gives all outcomes 0, except the fourth outcome which is 1.
We see what we have here is exactly the same vector triplet(a, b, c) for the first logic gate we created above.
Article source: Team Tech/Research AlphaTrue
Reference source:
Chen, T., Lu, H., Kunpittaya, T., & Luo, A. (2022). A review of zk-snarks. arXiv preprint arXiv:2202.06877. https://arxiv.org/pdf/2202.06877.pdf
https://medium.com/@VitalikButerin/quadratic-arithmetic-programs-from-zero-to-hero-f6d558cea649
https://eprint.iacr.org/2012/215.pd
