6
$\begingroup$

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?

$\endgroup$

1 Answer 1

2
+50
$\begingroup$

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

$\endgroup$
11
  • $\begingroup$ 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. $\endgroup$
    – user93353
    Feb 2, 2023 at 1:41
  • $\begingroup$ Also, you will end up with a different $T(x)$ as I mentioned in the question. How exactly does this not matter? $\endgroup$
    – user93353
    Feb 2, 2023 at 1:42
  • $\begingroup$ 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. $\endgroup$
    – Lev
    Feb 2, 2023 at 2:39
  • $\begingroup$ 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. $\endgroup$
    – Lev
    Feb 2, 2023 at 2:49
  • $\begingroup$ 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)$ $\endgroup$
    – user93353
    Feb 2, 2023 at 3:12

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.