Arithmetic Circuits to R1CS. Do we consider addition gates or not?

Question

Here is Ariel Gabizon's Blog for the process of converting Arithmetic Circuits into R1CS - https://electriccoin.co/blog/snark-explain5/

Here, he writes

• We assume multiplication gates have exactly two input wires, which we call the left wire and right wire.

• We don’t label the wires going from an addition to multiplication gate, nor the addition gate; we think of the inputs of the addition gate as going directly into the multiplication gate.

Considering this we should have only as many rows in each of the 3 R1CS matrix as there are number of gates.

Gabizon at the end of the Blog references Vitalik Buterin's post on the same - https://medium.com/@VitalikButerin/quadratic-arithmetic-programs-from-zero-to-hero-f6d558cea649

If you go to Vitalik's post, he creates a vector for each of the gates, both the addition gates & the multiplication gates. So each of his matrix ends up with 4 rows.

I assume there is some optimisation which Gabizon is doing by probably moving the addition gate data to the multiplication gate. However, his numerical example isn't as clear or detailed as Buterin's numerical example, so I am unable to figure out where it goes.

Also, by considering a different number of gates, their target polynomial should also be different - i.e. the gates being considered with each correspond to a root which goes into the target polynomial i.e. if there are 3 gates, the target polynomial $T(x) = (x-1)(x-2)(x-3)$. Whereas because of not considering the addition gate, you have only 2 gates, then your target polynomial will end up as $T(x) = (x-1)(x-2)$

Can someone who understands both examples explain how these 2 examples match up?

Answer 1

I've answered a similar question on this here

As you've correctly observed, Buterin's example is simplified and does not account for the optimisations that are possible with R1CS. If you want to express the solution of the cubic equation $x^3 + x + 5 = 35$ in R1CS, you could do it in two constraints.

To clarify this, let's work through this example. We can rearrange the polynomial equation to the following: $$ x(x^2 + 1) = 30 \tag{1}$$ Now, in R1CS, we encode the problem as $$Az \circ Bz = Cz$$ where $z = (1, z_1, z_2, .., z_n)$ corresponds to all input and intermediate variables in the computation; and matrices $A,B,C \in \mathbb{F}^{m \times (n+1)}$ encode the constraints on these variables. $n$ here corresponds to the number of variables, and $m$ the number of constraints.

If you are familiar with linear algebra, you should realise that each constraint here can encode something like this: $$(a_0 + a_1z_1 + ... + a_nz_n)\times(b_0 + b_1z_1 + ... + b_nz_n) = c_0 + c_1z_1 + ... + c_nz_n$$

Where the $a_i$'s, $b_i$'s and $c_i$'s are known constants. You aren't ignoring additions, but they come for free in this representation - in fact, you can encode arbitrary number of additions (or linear combinations) in a single constraint. So in our example, since we have (linear term) * (quadratic term) = (linear term), we can't represent the polynomial above in a single constraint. But we can in two. The first constraint will check that the squaring of $x$ was correctly computed, and the second will do the rest.

Let us call the intermediate variable $y$ such that $y = x^2$. Then we will define our vector $z = (1, x, y)$. Now I claim that our R1CS representation is as follows:

$$A = \pmatrix{0 & 1 & 0\\ 0 & 1 & 0} \qquad B = \pmatrix{0 & 1 & 0\\ 1 & 0 & 1} \qquad C = \pmatrix{0 & 0 & 1\\ 30 & 0 & 0}$$ $$$$

To see why this is the case, observe that if we expand out our system of equations

$$\pmatrix{0 & 1 & 0\\ 0 & 1 & 0}(1, x, y)^T \circ \pmatrix{0 & 1 & 0\\ 1 & 0 & 1}(1, x, y)^T = \pmatrix{0 & 0 & 1\\ 30 & 0 & 0}(1,x,y)^T $$

we get $$\pmatrix{x\\x}\circ \pmatrix{x \\ y +1} = \pmatrix{y\\30}$$ then $$\pmatrix{x^2 \\ x(y+1)} = \pmatrix{y\\30}$$

So our R1CS encodes $x \times x = y$ and $x(y + 1) = 30)$. By substitution, this yields the equation (1).

So in summary:

• R1CS allows you to encode polynomial equations, where each row of the matrices $A, B, C$ correspond to an equation of the form (linear constraint in the variables)*(linear constraint in the variables) = (linear constraint in the variables).
• The number of variables and constraints is closely related to the number of variable multiplications in your arithmetic circuit. Different R1CS representations can correspond to the same arithmetic circuit.

TODO: Add some explanation about QAPs