从算术电路中减少R1CS中的约束数

Question

文章Ligero++ (https://dl.acm.org/doi/pdf/10.1145/3372297.3417893)说：“R1CS中的约束数映射到算术电路中乘法门的数目。”但我理解将算术电路映射到R1CS的基本方法也会将添加映射为约束，如Vitalik的博客文章(https://medium.com/@VitalikButerin/quadratic-arithmetic-programs-from-zero-to-hero-f6d558cea649)中所示。是否有一种方法可以将包含加法和乘法门的电路映射到R1CS，以便约束的数目是乘法门的数目？

Answer 1

@lamba已经意识到了这一点，但是我想我应该添加一个答复供将来参考，因为这方面没有太多的资源。

R1CS是一种要求输入v的语言，因此

Av\circ Bv = Cv

其中\circ是坐标乘积，对于给定的矩阵集A,B,C.

本质上，R1CS的每一行都会编码:线性方程*线性方程=线性方程。因此，与天真地将每个乘法和加法转换为一行相比，这允许进行更大的优化。例如，假设您希望检查以下等式：

ax(by+cz) = dx + ey + fz + g

使用常量a,b,c,d,e,f,g和输入x,y,z。

如果我们允许v = (1,x,y,z)^T，我们可以用R1CS表示上面的方程如下：

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

因此，与其对每一个加法和乘法都得到一个约束--这将是~11个约束，我们可以只使用一个限制。