#2.1 Circom: Quadratic Constraints

This article serves as a quick review on constraints.

Circom constraints

While Circom at present can compile into either Groth16 or PLONK proving systems, they must expressed quadratically. That means a maximum of 1 multiplication per constraint.

• Constraints are created with === notation.

• Only * , + , - operators are allowed.

• Constraints must be of quadratic form: Ua * Vb + Wc :

  • there can only be 1 multiplicative operations between signals in a single constraint

  • U,V,W must be integer values

  • U,V,W cannot be signals

• The number of addition operations per constraint definition have no restrictions:

  • for example a * b + c + d + e is allowed

The following forms are all accepted:

a * b === c;

2a * 3b === 4c;               // integer coefficients allowed

a * b + c === d;

a * b + c === d + e + f;      // no restrictions on addition

The following forms are not accepted:

// 2 multiplicative operations between signals
a * b * c === d;

a * b === c * d;

// other operators besides: +,-,*
a / c === d;
a % b === d;

Constraints can look like either:

a * b + c === d;

// or

d === a * b + c;

In either variation, the outcome is the same, the value of the LHS must be equivalent to that of the RHS.

To recap, per constraint definition, the following must be adhered:

• no restriction on number of addition, integer or signal.

• no restriction on number of integer multiplication operations.

• only 1 multiplication operation between signals.

• order around the constraint operator (LHS vs RHS), is irrelevant.

The following code does not compile:

templage Mul3() {

		signal input a;
		signal input b;
		signal input c;
		signal input res;

		// not allowed
		res === a * b * c;
} 

The following code will compile:

templage Mul3() {

		signal input a;
		signal input b;
		signal input c;
		signal input res;

		
		// all allowed
		c === a * b;
		c === a * b + res;
		
} 

This should be familiar to the reader, from their understanding of arithmetization and R1CS.

Quadratic form and R1CS

Recall that in arithmetization, we flatten our verification program into a series of intermediate steps, where each intermediate step only contains only a single multiplication between unknown variables.

Consider the following verification example:

def someProblem(x, y, out):
		res = y^2 + 4*(x^2)*y -2 
		assert out == res, "incorrect inputs";

Arithmetization would yield us:

v1  === y * y
v2  === x * x 
out === v1 + (4v2 * y) - 2

• Arithmetization requires us to restructure the problem into intermediate steps that only have 1 multiplication operation between signals.

• This creates our system of constraints.

Consequently, the R1CS representation would be:

Since we previously ensured that there was only 1 multiplication per constraint, we are able to express the system of constraints in vector form, which is essentially R1CS.