Building zk-SNARKs (volume 3)
Introducing QAPs and, subliminally, R1CS
Introduction
This post closes our series on the construction of zero-knowledge SNARKs. It will revolve around the concepts of QAP and R1CS.
In our previous posts, we learnt the basic definitions and properties and also how to build SNARKs to prove knowledge of a polynomial. In this last post, we will learn how to reduce any computation to a polynomial, so one can run the SNARK protocol learnt in post 2.
Quadratic Arithmetic Programs
Definition
Up to this point, we have explored how to build zk-SNARKS to prove knowledge about a polynomial. Nevertheless, our objective is to prove the integrity of any computation. To do so, we need to convert a program into a polynomial. The tool we need to perform this conversion is the Quadratic Arithmetic Program (QAP), which we present in this section.
A Quadratic Arithmetic Program (QAP) over a field 𝔉 is a tuple of polynomials defined on 𝔉[x]:
together with a target polynomial t(x) ∈ 𝔉[x].
Let’s assume that F is a function taking n elements in 𝔉 as inputs and outputting n’ elements in 𝔉. Let’s denote N = n + n’ the total number of elements, counting inputs and outputs.
We say that a QAP, denoted Q, computes F if (c_1, …, c_N) ∈ 𝔉^N is a valid assignation of inputs and outputs for F, equivalently: if there exist coefficients (c_{N+1}, …, c_m) such that t(x) divides the polynomial
In other words, Q computes F if one can find a polynomial h(x) such that p(x) = h(x) · t(x). The size of Q is m, and the degree of Q is the degree of the target polynomial t(x).
It is possible to prove that any arithmetic circuit with d products and N inputs and outputs yields a QAP of degree d and size d + N.
QAPs for product circuits
Remark: for the rest of this document we will assume that 𝔉 = ℤ_13.
Let’s consider the circuit below, composed of n = 3 inputs, d = 2 product gates m_1 and m_2, an intermediate gate and n’ = 1 outputs. Therefore, for the circuit below, m = 5
The basic idea behind defining a QAP is to keep track of the variables coming from the left, and right of each of the product gates. In the figure, gate m_1 receives variable c_1 from the left and variable c_2 from the right, and gate m_2 receives variable c4 from the left and variable c3 from the right.
With this information, we generate 3 matrices, namely R, L and O summarising the information of variables on the right and on the left and the outputs, respectively. Each matrix has as many rows as incoming, intermediate and outgoing variables, and as many columns as product gates involved in the circuit. For example, in the circuit above, R, L and O will be matrices of size m x d = 5 x 2.
How we fill these matrices depends on the role of each variable with respect to the product gate. For instance, our matrix L is
Each column corresponds to a product gate: 1st column for m_1 and 2nd column for m_2. On the other hand, the i-th row corresponds to variable c_i. We read the matrix like this: the first one informs that m_1 only gets c_1 from the left (that is why the rest of the column is filled with 0s) whereas the other one informs that m_2 only gets c_4 from the left. Similarly, we can create matrices R and O for elements on the right and outputs, respectively:
Observe that O must be read as follows: m1 outputs the variable c_4 and m_2 outputs the variable c_5.
These matrices lead to the definition of the sets of polynomials defining a QAP. To be precise: L is used to define the set V, R is used to define the set W and O is used to define the set Y.
To define these polynomials we need to choose d random values, called roots and denoted r_1, …, r_d. In our situation, d = 2, so we choose the values {2, 3} and the matrices L, R and O become:
Now is the time to build equalities, using the information given by the circuit:
Observe that the above equalities indicate that v_1(2) = 1 and v_1(3) = 0, and so on. We can use polynomial interpolation to get v_1(x) = 12x + 3. Likewise, v_4(x) = x + 11 and v_2(x) = v_3(x) = v_5(x) = 0. So the set V used in the definition of QAPs is
Repeating the above protocol we get the other two sets:
We are almost done computing the polynomial p(x). The only thing left to do is find values c_1, …, c_m corresponding to valid inputs and outputs for the circuit. This can be done by taking random values for the inputs c_1, c_2 and c_3 and computing c_4 and c_5 by following the rules of the circuit. Let us consider c_1 = 2, c_2 = 3 and c_3 = 4. Then
c_4 = m_1(c1, c2) = c_1 · c_2 = 6 and
c_5 = m_2(c_4, c_3) = c_4 · c_3 = 6 · 4 = 24 ≡ 11 (mod 13)
So the set of valid inputs and outputs is {2, 3, 4, 6, 11}. Therefore:
Lastly, we need to find the target polynomial dividing p(x). Let’s keep in mind the polynomials v_i(x), w_i(x) and y_i(x), since they were used for the definition of p(x) therefore evaluating p(x) on the values r_1 = 2 and r_2 = 3 will yield 0, meaning that:
QAPs for arithmetic circuits
So far we have learnt how to build the QAP associated with a circuit involving just products. In this section, we will extend the techniques to “arithmetic” circuits, involving products and additions.
From now on, we will work on the following circuit with n = 5 inputs, d = 5 product gates, 4 intermediate gates and n’ = 1 output. Therefore, in this case, m = 10.
We observe that, as in the previous section, the only elements that count for labelling and deducing the value of m are the “external” input gates and the outputs of the product gates.
Remark: since the idea behind the generation of the QAP is the same as in the previous section, some of the computations will be skipped.
Now we take into consideration the variables coming from the left, the right and the outputs to build the matrices L, R and O. We observe that the matrices’ size is m x d = 10 x 5.
Now we need to consider not just the variables coming from the right or the left, but also the “weight” of each variable. We observe that m1 receives from the right the result of doing c_1 + 2c_2, therefore m_1 gets one c_1 and two c_2 from the right
Similarly, we can compute the matrices corresponding to the left and the outputs:
Now it’s the turn to take d = 5 random values, for instance {0, 1, 2, 3, 4} and consider the matrices:
If we now consider the equalities between left matrices, right matrices and output matrices we can then take interpolation to obtain each polynomial:
We now can compute the polynomial p(x). As done in the previous section, we will compute the values c_i by choosing random values for c_1, c_2, c_3, c_4, c_5 and computing the values c_6, c_7, c_8, c_9, c_10 by replacing the formers on the circuit. Doing so we obtain the set {c_1, …, c_10} = {2, 3, 5, 6, 7, 3, 7, 3, 8, 11} so the polynomial p(x) is:
To finish the protocol, we need to build the polynomial h(x). Since p(x) has roots {0, 1, 2, 3, 4}, the polynomial t(x) will be:
Conclusions
Zero-knowledge SNARKs are a type of cryptographic proof that enables the verification of the authenticity of computations without revealing its inputs. If this computation represents the verification of blockchain transactions, we can process blockchain transactions without revealing their details. This provides a high degree of privacy and security in blockchain systems.
We presented a self-contained guide to zk-SNARKs which begins with the concept itself and ends with the step-by-step procedure to build the zk-SNARK of an arbitrary arithmetic circuit. The main motivation for creating this guide was to create a handbook for a topic which is ubiquitous in blockchain. It is also quite challenging to address since individuals tend to articulate their comprehension of a field that is, for the most part, a mathematical craft.
In blockchain, zk-SNARKs are also used to enable anonymous transactions, where the identity of the transacting parties remains hidden, while at the same time allowing the network to verify that the transactions are valid.
Furthermore, zk-SNARKs allow for increased blockchain scalability by reducing the computational and storage requirements of blockchain systems, which is a significant challenge for traditional blockchain protocols.
Overall, zk-SNARKs play a crucial role in the development and implementation of privacy-preserving and scalable blockchain systems, and they are a critical tool for enabling the future of decentralised finance and other blockchain-based applications.
References
- Rosario Gennaro, Craig Gentry, Bryan Parno, and Mariana Raykova, Quadratic Span Programs and Succinct NIZKs without PCPs, Cryptology ePrint Archive, Paper 2012/215.
- Jordi Herrera Joancomartí, Cristina Pérez Solà, Criptografia avançada. Lecture notes. Open University of Catalonia, 2022.
