[IVC basic] R1CS and QAP

 There are zk-SNARKs that is able to prove relations for arithmetic circuit satisfiability. The relation can be expressed as some form, for example, R1CS/QAP form. We are recently studying about the papers for IVC construction and some papers considered the relation expressed as R1CS/QAP form. In this post, we explain R1CS and QAP which are background for studying IVC, hoping to help the readers.

We are studying about the papers for IVC construction, and some papers considered IVC construction by converting the relation for circuit satisfiability into R1CS/QAP form. We hope that this post help studying the papers.

Background

-Arithmetic circuit

-Lagrange interpolation

Reference

-Jonathan Bootle, Andrea Cerulli, Pyrros Chaidos, Jens Groth, and Christophe Petit, Efficient Zero-Knowledge Arguments for Arithmetic Circuits in the Discrete Log Setting, Eurocrypt 2016

-Srinath Setty, Justin Thaler, and Riad Wahby, Customizable constraint systems for succinct arguments

Rank-1 Constraint system 

Suppose there is an arithmetic circuit, which is consists of fan-in-2 gates. Each gate is either addition gate or multiplication gate. For example,

[Efficient Zero-Knowledge Arguments for Arithmetic Circuits in the Discrete Log Setting,p.35]

The circuit can be represented as some equations :

Each equation corresponds to an addition gate or a multiplication gate or a consistency equation. The consistency equation means the relation between the wires.

For instance, c1 is an output of multiplication gate, but also an input of other gate. So we should contain the relation c1 = a4, considering the representation.

Then the equations can be converted into a R1CS, Rank-1 Constraint System. The R1CS structure (A, B, C) is consists of three matrices 

,where m and n are natural numbers. 

Each equation is represented as 

with a sequence of three vectors $( \alpha, \beta, \gamma )$ , and let z be a vector called 'value vector'. ('value vector' is informal expression, just for understanding. And ● means inner product. )

Suppose

and z contains all value of wires and 1.

Then the equation $a_1 \times b_1 = c_1 $ can be expressed as follows :

$\alpha = ( 1, 0, ..., 0), \beta = ( 0, 0, 0, 0, 0, 0, 1, 0, ..., 0), \gamma = (0, ..., 0, 1, 0, 0, 0, 0, 0, 0)$

$4c_3 + c_4 = b_5$ also can expressed by letting the vectors be 

Then we can construct the matrices A, B, C by putting $\alpha, \beta, \gamma$ in the matrices A, B, C, respectively. 

We know that m = (the number of equations), n = |z|

Formal R1CS format
A R1CS instance consists of public input x $\in F^l$ and a R1CS witness consist of a vector w $\in F^{n-1-l}$ .

Recall that z consists of elements of x and w. Actually, the formal R1CS format uses a little different value vector, which will be denoted as Z. 

We define Z as a vector (x, 1, w) $\in F^n$, which is a rearrangement of z.

Usually, the public input contains the inputs/outputs of circuit, and the witness contains the intermediate values. 

Since we change z to Z, structure (A, B, C) should be changed as well.

 Then they satisfies the following by using the same mechanism. :

( ○ means Hadamard product.) 

Quadratic Arithmetic Program

Now, we get R1CS form for an arithmetic circuit, so we can convert it into QAP. The QAP applies the same logic with R1CS, but not using inner product. it uses some polynomials. For example, 

(The above equations are  irrelevant to R1CS example.)

By using Lagrange interpolation, we can construct a polynomial for 1st column of matrix A. In detail, we can take m points. (In this case, m=6) : (1, 0), (2, 0), (3, 0), (4, 1), (5, 0), (6, 1) 

i.e. { (i, j) : j is the value of ith row. } Then we can generate a polynomial $A_1 (x)$ by using Lagrange interpolation. : $A_1 (4) = A_1 (6) = 1 , A_1 (i) = 0 $  for  $ i = 1, 2, 3, 5$

Thus we can generate n polynomials for matrix A and similarly for matrices B, C.

[ $A_1 (x), A_2 (x), ..., A_n (x)$ ],

[ $B_1 (x), B_2 (x), ..., B_n (x)$ ],

[ $C_1 (x), C_2 (x), ..., C_n (x)$ ]

Then we can know that 

( $\sum_{i=1} ^n$  $z_i A_i (x)$ )( $\sum_{i=1} ^n$  $z_i B_i (x)$ ) - ( $\sum_{i=1} ^n$  $z_i C_i (x)$ ) $= 0$ for $ x = 1, ..., 6 $

The QAP form of the circuit is

( $\sum_{i=1} ^n$  $z_i A_i (x)$ )( $\sum_{i=1} ^n$  $z_i B_i (x)$ ) - ( $\sum_{i=1} ^n$  $z_i C_i (x)$ ) $= H(x) \prod_{j=1} ^m$  $(x-x_j)$

, where $Z=(z_1, z_2, ..., z_n)$ and $x_j = j$

The equation means the left term has solutions { $x_j$ } ,and  the reason why I wrote $(x-x_j)$ instead of $(x-j)$ is to express general QAP form.