3
$\begingroup$

The article Ligero++ (https://dl.acm.org/doi/pdf/10.1145/3372297.3417893) says "The number of constraints in R1CS maps to the number of multiplication gates in arithmetic circuits." But I understand the basic way to map an arithmetic circuit to R1CS will also map additions as constraints as shown in Vitalik Buterin's blog post (https://medium.com/@VitalikButerin/quadratic-arithmetic-programs-from-zero-to-hero-f6d558cea649). Is there a way to map a circuit containing addition and multiplication gates to R1CS such that the number of constraints is the number of multiplication gates?

$\endgroup$

1 Answer 1

1
$\begingroup$

@lamba is already aware of this, but I thought I'd add a response for future reference as there is not a lot of resources on this.

R1CS is a language which asks for an input $v$ such that $$Av\circ Bv = Cv$$ Where $\circ$ is coordinate-wise product, for a given set of matrices $A,B,C$.

Essentially, each row of a R1CS will encode: linear equation * linear equation = linear equation. So this allows for much greater optimisation than naively converting each multiplication and addition into a single row. For instance, suppose you wish to check the following equation holds: $$ax(by+cz) = dx + ey + fz + g$$

With constants $a,b,c,d,e,f,g$ and inputs $x,y,z$.

If we let $v = (1,x,y,z)^T$, we can represent the equation above in R1CS as follows:

$$A = (0,a,0,0), B=(0,0,b,c), C =(g,d,e,f)$$

So rather than getting a constraint for every addition and multiplication - which would be ~11 constraints, we can do it with just one.

$\endgroup$
2
  • $\begingroup$ is there a name for this trick? It's omitted from Ben-Sasson 2013, for instance (specifically, consult Definition E2 from eprint.iacr.org/2013/507.pdf). $\endgroup$
    – jmcph4
    Nov 20, 2022 at 7:43
  • $\begingroup$ I don't think there is any name for this, it's just using the definition of R1CS to optimise the constraints. The definition given is equivalent to R1CS, but expressed as equations. I'm assuming you're talking about the paragraph below the definition. It seems like they are describing a generic reduction from arithmetic circuits to R1CS, but it is possible to do better if you know the circuit as above. $\endgroup$
    – Lev
    Nov 22, 2022 at 0:19

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.