Under the hood of zkSNARK Groth16 protocol (part 2)
In the previous article, we briefly covered the first two components of the SNARK protocol: the code and the algebraic circuits. In this article, we will focus on constructing our R1CS (Rank One Constraint System).
Before delving into R1CS, I must introduce two foundational subjects from mathematics:
- Vectors and Matrices from Linear Algebra.
- Galois Fields (GF or finite fields) from Abstract Algebra.
We use matrices and vectors to encode our algebraic circuit. The vector holds values for all the variables we identified previously, while the matrix contains the constants. Put simply, the vector serves as a means to store and encode data, and the matrix encodes data transformation. When a matrix multiplies a vector, data transformation occurs.
Galois theory of finite fields is a specialized area within abstract algebra. For those interested in delving deeper into abstract algebra, I will provide references at the end of this article. Simply put, finite fields involve a set of rules applied to certain number groups. These rules encompass modular arithmetic, operations specific to particular fields, and other related definitions. Understanding finite fields is crucial because all subsequent arithmetic discussed here will be performed within a finite field, specifically in GF(p):
p = 21888242871839275222246405745257275088548364400416034343698204186575808495617
The value p is a prime number, so the set under consideration comprises integers ranging from 0 to p−1. This specific choice is pivotal because of the Elliptic Curve known as BN-128, which we will later employ for encryption. Notably, within the Ethereum blockchain’s framework, BN-128 and secp256k1 are the only supported elliptic curves.
R1CS
How do we transition from constraints to matrix and vector form as illustrated above?
First, we must encode our variables into a vector, w, commonly referred to as the “witness vector”. This vector will encompass:
- Input values, namely x and y,
- Calculated values, such as v1,v2,…v4,
- The resultant output, out.
Constant 1 would have to be used in case if original equation contains an additional term (i.e. + 5).
Matrices serve as encodings for triggers or switches, activating computations for specific variables, such as v1 to v4 and out. Consider first computation:
This computation is characterized by:
- The left operand, highlighted in red,
- The right operand, highlighted in blue, and
- The output, highlighted in green.
Each of these elements must be encoded into three distinct matrices: L for the left operand, R for the right operand, and O for the output.
Note: The first row in each matrix serves as a guide to indicate which column corresponds to which parameter. It’s not an part of the matrix itself.
You can interpret the matrices as follows:
- To compute v1, use x as both the left and right parameters.
- To derive v3, take x multiplied by 5 as the left parameter and v1 as the right parameter.
As you may observe, the coefficients act as transformers of the input value for each specific computation.
You might be puzzled about the presence of negative values, especially since we previously mentioned that computations would occur in a Galois field GF(p) where numbers are confined to the range between 0 and p−1. In GF(p), a negative number, say n, is represented as p−n.
Finally, if we multiply each matrix by witness vector we will get next:
Where Lw, Rw, and Ow are vectors. The element-wise multiplication of Lw and Rw should yield Ow. If this equality holds true, it confirms the correctness of our R1CS defined by the matrices L, R,O and vector w.
Let’s delve into the coding part. Alternatively, you can also find this code on GitHub:
import galois
import numpy as np
p = 21888242871839275222246405745257275088548364400416034343698204186575808495617
FP = galois.GF(p)
# input arguments
x = FP(2)
y = FP(3)
v1 = x * x
v2 = y * y
v3 = 5 * x * v1
v4 = 4 * v1 * v2
out = 5*x**3 - 4*x**2*y**2 + 13*x*y**2 + x**2 - 10*y
w = FP([1, out, x, y, v1, v2, v3, v4])
print("w =", w)
R = FP([[0, 0, 1, 0, 0, 0, 0, 0],
[0, 0, 0, 1, 0, 0, 0, 0],
[0, 0, 5, 0, 0, 0, 0, 0],
[0, 0, 0, 0, 4, 0, 0, 0],
[0, 0, 13, 0, 0, 0, 0, 0]])
L = FP([[0, 0, 1, 0, 0, 0, 0, 0],
[0, 0, 0, 1, 0, 0, 0, 0],
[0, 0, 0, 0, 1, 0, 0, 0],
[0, 0, 0, 0, 0, 1, 0, 0],
[0, 0, 0, 0, 0, 1, 0, 0]])
O = FP([[0, 0, 0, 0, 1, 0, 0, 0],
[0, 0, 0, 0, 0, 1, 0, 0],
[0, 0, 0, 0, 0, 0, 1, 0],
[0, 0, 0, 0, 0, 0, 0, 1],
[0, 1, 0, 10, FP(p - 1), 0, FP(p - 1), 1]])
Lw = np.dot(L, w)
Rw = np.dot(R, w)
Ow = np.dot(O, w)
print("Lw =", Lw)
print("Rw =", Rw)
LwRw = np.multiply(Lw, Rw)
print("Lw * Rw =", LwRw)
print("Ow = ", Ow)
assert np.all(LwRw == Ow)w = [ 1 104 2 3 4 9 40 144]
Lw = [2 3 4 9 9]
Rw = [ 2 3 10 16 26]
Lw * Rw = [ 4 9 40 144 234]
Ow = [ 4 9 40 144 234]In summary, R1CS provides a format to represent our initial program and to evaluate all its intermediate steps. This is foundational when constructing a QAP, which I will discuss in a subsequent article.
Part 3:
There’s a considerable breadth of information, especially mathematical concepts, that I’ll be presenting in this and upcoming articles. Some of these might seem random or appear without comprehensive explanations, particularly when discussing the construction of zero-knowledge proofs. For those truly invested in understanding these core principles, I can’t recommend the zk-bootcamp by rareskills.io enough. Make sure to use the code TARAS23 for a discount. Without this course, I would have spent considerably more time wrestling with these essential foundations.
