zk-SNARK: QAP
2023 August 5
See all posts
Special thanks to Vitalik Buterin and his articles about zk-SNARK. This article is made for the purpose of 1. me understanding zkSNARKs and 2. acknowledging my apprentices who visit this website about zk-SNARKS.
The AI will reshape the world. However, it can only be done with the help of adjacent industries, such as the crypto industry. The latter is based on *surprise* cryptography, particularly zk-SNARKs, which Ethereum uses. Of course, many articles describe how these beings work, but the explanations are wether too complex or too superficial. This post will go deeper into mathematics and tinkering behind the algorithm and explain the first half of the sequence:
Algebraic circuit
First of all, to apply zk-SNARK, you have to convert the problem into the “right form”. Let’s consider equation \(x^2+x+1=7\) and let's prove we know the answer is 3. To do any further computations with left side polynomial, we have to construct something called “algebraic circuit” for this polynomial. Its bulk is a directed acyclic graph, or a graph that consists of vertices and edges, and each vertex is visited only after all its dependencies are visited; every vertex with inbound zero is called input gate ,and every other vertex is a gate labeled “+” or “-“. Here’s an example of algebraic circuit for our example:
You can easily iterate this computation yourself to see that our directed acyclic graph produces the polynomial.
Then, we have to make a finite field 𝔽𝕢: set a multitude \(S\) and define "+" and "*" operations:
\(\mathrm{I}. \: \forall a,b \in S \: a+b=b+a\)
\(\mathrm{II}. \: \forall a,b \in S \: (a+b)+c=a+(b+c)\)
\(\mathrm{III}. \: \) There exists such an element \(0\) that \(a+0=a \: \forall a\)
\( \mathrm{IV}. \: \forall a \in S \, \exists b \, \: a+b=0\); element \(b\) is noted as "\(-a\)"
\(\mathrm{V}. \: \forall a,b \in S \: a*b=b*a\)
\(\mathrm{VI}. \: \forall a,b,c \in S \: (a*b)*c=a*(b*c)\)
\(\mathrm{VII}.\: \) There exists such an element 1 that \(\forall a \in S \: a*1=a\) and \(1 \neq 0\)
\(\mathrm{VIII}. \: \forall a \neq 0 \: \exists b\) that \(a*b=1\); \(b\) is noted as \(\frac{1}{a}\)
\(\mathrm{IX}. \: a*(b+c)=a*b+a*c \: \: \forall a,b,c \)
After we set the rules called axioms, let's make an actual field. There are many ways how to define it, and the easiest one is to select a prime number p>2 and any computation is made relative to its modulo; let \(p = 11\) and our field \(\mathbb{F} = (0,1,2...10)\). For example, \(7*2=3\) because \(7*2=14\) in \( \mathbb{N}\) and 14%11=3.
R1CS
Now, we convert into something called R1CS, an acronym for a fancy compound Rank-1 Constraint System, but it's not so hard. R1CS is a group of three vectors \((a,b,c)\) and a solution to a R1CS is a vector \(s\) that satisfies the equation \(\vec{a}.\vec{s}*\vec{b}.\vec{s}=\vec{c}. \vec{s}\), where "."" is a scalar or dot product.
We will have a R1CS for each gate. These are all variables in the system: \(1, x, x^2, x+1, x^2+x+1\), so to be clear let's denote \(x^2\) as \(y\), \(x+1\) as \(sum1\), and \(x^2+x+1\) as \(out\). Our ordered variables: \(1, x, y, sum1, out\). The length of every R1CS vector will be 5 and they will consist of corresponding slots of the variables for each gate
These are \(a,b,c\) for our first gate:
a = [0, 1, 0, 0, 0]
b = [0, 1, 0, 0, 0]
c = [0, 0, 1, 0, 0]
There are a lot of solutions vectors to this R1CS since there are a lot of zeros, so we will select \(s\) later.
Our second gate is \(x+1\), which equals \((x+1)*1\); the \(a,b,c\) will be these:
a = [1, 1, 0, 0, 0]
b = [1, 0, 0, 0, 0]
c = [0, 0, 0, 1, 0]
Finally, our third gate:
a = [0, 0, 1, 1, 0]
b = [1, 0, 0, 0, 0]
c = [0, 0, 0, 0, 1]
There are many solutions, but I will choose:
s = [1, 3, 9, 4, 13]
You can check it my simply doing all the stuff for each gate.
The complete R1CS together is:
A
[0, 1, 0, 0, 0]
[1, 1, 0, 0, 0]
[0, 0, 1, 1, 0]
B
[0, 1, 0, 0, 0]
[1, 0, 0, 0, 0]
[1, 0, 0, 0, 0]
C
[0, 0, 1, 0, 0]
[0, 0, 0, 1, 0]
[0, 0, 0, 0, 1]
R1CS to QAP
Now we have to convert our R1CS into the Quadratic Arithmetic Program. The logic is similar, but we will be translating the vectors into polynomials. From three groups of three vectors of length five we will go to three groups of five polynomials. Evaluating polynomials at \(x=1\) gives us constraints at the first gate, at \(x=2\) - at the second gate, and so on.
We will make this transformation using Langrange interpolation, which helps constructs a polynomial that passes through all of the points you have.
Let's do a simple example: suppose we have a set of points \((3,3),(1,4),(2,4)\) and we want to construct a polynomial that passes through all these points.
To start with, we construct a polynomial that passes through \((3,3),(1,0),(2,0)\).
Obviously, we need to rescale \(f(x)=(x-1)(x-2)\). Since \(f(3)=2 \: \Rightarrow f(x)=7*(x-1)(x-2)\) as we are in our field with base 11.
Similarly, we do this for other two points and get: \(g(x)=-4(x-1)(x-3)\) and \(h(x)=2(x-2)(x-3)\), so by summing up we get: \(f(x)=5x^2-4x+3\)
In our case, we need to do this for 15 sets of three points - 5 columns for each A,B, and C for 3 points. So the first set of points will be \((1,0),(2,1),(3,0)\) - and this will be our first polynomial.
For your convinience, here's the list of polynomials:
A:
[-3.00, 4.00, -1.00]
[0.00, 1.50, -0.50]
[1.00, -1.50, 0.50]
[1.00, -1.50, 0.50]
[0.00, 0.00, 0.00]
B:
[-2.00, 2.50, -0.50]
[3.00, -2.50, 0.50]
[0.00, 0.00, 0.00]
[0.00, 0.00, 0.00]
[0.00, 0.00, 0.00]
C:
[0.00, 0.00, 0.00]
[0.00, 0.00, 0.00]
[3.00, -2.50, 0.50]
[-3.00, 4.00, -1.00]
[1.00, -1.50, 0.50]
The coefficients presented in ascending form, so first polynomial is \(-x^2 + 2x\)
Checking the QAP
The point of the whole process above is that instead of checking the constraints in the R1CS individually, we can now check all of the constraints at the same time by doing the dot product check on the polynomials.
In this case, the result of dot product is a polynomial, rather than a some integer number. If resulting polynomial is zero at every \(x=1,2,3\), our system works. But, to check correctness, we won't actually calculate the polynomial \(A.s*B.s-C.s\); instead, we will divide it by another polynomial \(\mathbb{Z}\) and look if there's no remaineder, \(\mathbb{Z}\) is defined as \((x-1)(x-2)...(x-n)\), where in our case \(n=3\).
At this point, let's check the intermediate polynomials:
A.s = [10, -11, 4]
B.s = [7, -5, 1]
C.s = [28, -26, 7]
Therefore, \(t\) equals:
t = [42, -101, 86, -31, 4]
And Z equals:
Z = [-6, 11, -6, 1]
In \(R\) the \(t/Z\) would give us [-7, 4] and zero remainer. This outcome will be the same in our field of 11. as t = [9, 9, 9, 4, 2] and Z = [-6, 0, -6, 1]. \(t/Z\) = 4x - 18 = 4x + (-2 * 11) + 4 = 4x+4. The remainer would be \(99x^2 -11x + 99\), which in our field equals zero.
However, in the real world, the algebraic circuit has billion of gates and the finite field are usually made of prime higher than \(2^{256}\), which is an extremely big number.
zk-SNARK: QAP
2023 August 5 See all posts
Special thanks to Vitalik Buterin and his articles about zk-SNARK. This article is made for the purpose of 1. me understanding zkSNARKs and 2. acknowledging my apprentices who visit this website about zk-SNARKS.
The AI will reshape the world. However, it can only be done with the help of adjacent industries, such as the crypto industry. The latter is based on *surprise* cryptography, particularly zk-SNARKs, which Ethereum uses. Of course, many articles describe how these beings work, but the explanations are wether too complex or too superficial. This post will go deeper into mathematics and tinkering behind the algorithm and explain the first half of the sequence:
Algebraic circuit
First of all, to apply zk-SNARK, you have to convert the problem into the “right form”. Let’s consider equation \(x^2+x+1=7\) and let's prove we know the answer is 3. To do any further computations with left side polynomial, we have to construct something called “algebraic circuit” for this polynomial. Its bulk is a directed acyclic graph, or a graph that consists of vertices and edges, and each vertex is visited only after all its dependencies are visited; every vertex with inbound zero is called input gate ,and every other vertex is a gate labeled “+” or “-“. Here’s an example of algebraic circuit for our example:
You can easily iterate this computation yourself to see that our directed acyclic graph produces the polynomial.
Then, we have to make a finite field 𝔽𝕢: set a multitude \(S\) and define "+" and "*" operations:
\(\mathrm{I}. \: \forall a,b \in S \: a+b=b+a\)
\(\mathrm{II}. \: \forall a,b \in S \: (a+b)+c=a+(b+c)\)
\(\mathrm{III}. \: \) There exists such an element \(0\) that \(a+0=a \: \forall a\)
\( \mathrm{IV}. \: \forall a \in S \, \exists b \, \: a+b=0\); element \(b\) is noted as "\(-a\)"
\(\mathrm{V}. \: \forall a,b \in S \: a*b=b*a\)
\(\mathrm{VI}. \: \forall a,b,c \in S \: (a*b)*c=a*(b*c)\)
\(\mathrm{VII}.\: \) There exists such an element 1 that \(\forall a \in S \: a*1=a\) and \(1 \neq 0\)
\(\mathrm{VIII}. \: \forall a \neq 0 \: \exists b\) that \(a*b=1\); \(b\) is noted as \(\frac{1}{a}\)
\(\mathrm{IX}. \: a*(b+c)=a*b+a*c \: \: \forall a,b,c \)
After we set the rules called axioms, let's make an actual field. There are many ways how to define it, and the easiest one is to select a prime number p>2 and any computation is made relative to its modulo; let \(p = 11\) and our field \(\mathbb{F} = (0,1,2...10)\). For example, \(7*2=3\) because \(7*2=14\) in \( \mathbb{N}\) and 14%11=3.
R1CS
Now, we convert into something called R1CS, an acronym for a fancy compound Rank-1 Constraint System, but it's not so hard. R1CS is a group of three vectors \((a,b,c)\) and a solution to a R1CS is a vector \(s\) that satisfies the equation \(\vec{a}.\vec{s}*\vec{b}.\vec{s}=\vec{c}. \vec{s}\), where "."" is a scalar or dot product.
We will have a R1CS for each gate. These are all variables in the system: \(1, x, x^2, x+1, x^2+x+1\), so to be clear let's denote \(x^2\) as \(y\), \(x+1\) as \(sum1\), and \(x^2+x+1\) as \(out\). Our ordered variables: \(1, x, y, sum1, out\). The length of every R1CS vector will be 5 and they will consist of corresponding slots of the variables for each gate
These are \(a,b,c\) for our first gate:
There are a lot of solutions vectors to this R1CS since there are a lot of zeros, so we will select \(s\) later.
Our second gate is \(x+1\), which equals \((x+1)*1\); the \(a,b,c\) will be these:
Finally, our third gate:
There are many solutions, but I will choose:
s = [1, 3, 9, 4, 13]You can check it my simply doing all the stuff for each gate.
The complete R1CS together is:
R1CS to QAP
Now we have to convert our R1CS into the Quadratic Arithmetic Program. The logic is similar, but we will be translating the vectors into polynomials. From three groups of three vectors of length five we will go to three groups of five polynomials. Evaluating polynomials at \(x=1\) gives us constraints at the first gate, at \(x=2\) - at the second gate, and so on.
We will make this transformation using Langrange interpolation, which helps constructs a polynomial that passes through all of the points you have.
Let's do a simple example: suppose we have a set of points \((3,3),(1,4),(2,4)\) and we want to construct a polynomial that passes through all these points.
To start with, we construct a polynomial that passes through \((3,3),(1,0),(2,0)\).
Obviously, we need to rescale \(f(x)=(x-1)(x-2)\). Since \(f(3)=2 \: \Rightarrow f(x)=7*(x-1)(x-2)\) as we are in our field with base 11.
Similarly, we do this for other two points and get: \(g(x)=-4(x-1)(x-3)\) and \(h(x)=2(x-2)(x-3)\), so by summing up we get: \(f(x)=5x^2-4x+3\)
In our case, we need to do this for 15 sets of three points - 5 columns for each A,B, and C for 3 points. So the first set of points will be \((1,0),(2,1),(3,0)\) - and this will be our first polynomial.
For your convinience, here's the list of polynomials:
The coefficients presented in ascending form, so first polynomial is \(-x^2 + 2x\)
Checking the QAP
The point of the whole process above is that instead of checking the constraints in the R1CS individually, we can now check all of the constraints at the same time by doing the dot product check on the polynomials.
In this case, the result of dot product is a polynomial, rather than a some integer number. If resulting polynomial is zero at every \(x=1,2,3\), our system works. But, to check correctness, we won't actually calculate the polynomial \(A.s*B.s-C.s\); instead, we will divide it by another polynomial \(\mathbb{Z}\) and look if there's no remaineder, \(\mathbb{Z}\) is defined as \((x-1)(x-2)...(x-n)\), where in our case \(n=3\).
At this point, let's check the intermediate polynomials:
Therefore, \(t\) equals:
And Z equals:
In \(R\) the \(t/Z\) would give us [-7, 4] and zero remainer. This outcome will be the same in our field of 11. as t = [9, 9, 9, 4, 2] and Z = [-6, 0, -6, 1]. \(t/Z\) = 4x - 18 = 4x + (-2 * 11) + 4 = 4x+4. The remainer would be \(99x^2 -11x + 99\), which in our field equals zero.
However, in the real world, the algebraic circuit has billion of gates and the finite field are usually made of prime higher than \(2^{256}\), which is an extremely big number.