Score:6

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

et flag

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?

Score:2
jp flag
Lev

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

et flag
I don't understand your other answer at all. You have a full equation $ax(by+cz) = dx + ey + fz + g$ & you seem to be able to represent A, B & C as vectors rather than as matrices. The answer doesn't say at all how you were able to ignore the addition gates.
et flag
Also, you will end up with a different $T(x)$ as I mentioned in the question. How exactly does this not matter?
Lev avatar
jp flag
Lev
In the example, the matrix has 1 row. This is because you can represent equations of the form (linear term in v) * (linear term in v) = (linear term in v) in a single constraint. Addition gates are not 'ignored', but incorporated into the constraints. I'll update my answer here with a fleshed out example.
Lev avatar
jp flag
Lev
The target polynomial is related to a different representation. Quadratic Arithmetic Programs slightly differ from R1CS. I have not worked with them before, but I'll see if I can answer that too.
et flag
`Quadratic Arithmetic Programs slightly differ from R1CS` - yes, my point here is that in both Gabizon's & Buterin's examples, it's the R1CS which gets converted to the QAP. And the number of gates considered in the R1CS is equal to the degree of the target polynomial $T(x)$
et flag
I think I understand what you mean by not ignoring the addition gates. In the full flattening of the program, each of A, B & C have only 1 non-zero variable in the their representation of a gate. While in the semi-flattening (where you don't flatten the addition separately but put them as part of the multiplication), you have multiple non-zero values in each representation of a multiplication gate
Lev avatar
jp flag
Lev
Let me know if my fleshed out example is helpful. I've used R1CS in a recent paper which applies zkSNARKs, but not QAPs. Yes I think you are correct, the degree of the target polynomial corresponds to the number of *constraints* in the R1CS representation. This target polynomial may change with a different representation of the arithmetic circuit.
et flag
Yes, your explanation of getting A, B & C matrices for $x(x^2 +1) = 30$ is very clear.
et flag
Actually your answer to the other question is also clear but I got confused because of the long equation & also use of constants like a, b etc rather than actual numbers :-(
Lev avatar
jp flag
Lev
Glad to hear it. I had similar issues understanding R1CS until I played around with some examples. Would you mind accepting my answer for the bounty? :)
et flag
I have accepted & given the bounty - thank you very much for your help. If you are able to figure of the target polynomial thing, do fill it in when you get the time.
I sit in a Tesla and translated this thread with Ai:

mangohost

Post an answer

Most people don’t grasp that asking a lot of questions unlocks learning and improves interpersonal bonding. In Alison’s studies, for example, though people could accurately recall how many questions had been asked in their conversations, they didn’t intuit the link between questions and liking. Across four studies, in which participants were engaged in conversations themselves or read transcripts of others’ conversations, people tended not to realize that question asking would influence—or had influenced—the level of amity between the conversationalists.