2.7. Constraints generation

Algebraic expressions

We define the following type of expressions:

  • Constant values: only a constant value is allowed.

  • Linear expression: an expression where only addition is used. These expressions can also be written in short using multiplication of variables by constants. For instance, the expression 2*x + 3*y + 2 is linear, as it is equivalent to x + x + y + y + y + 2.

  • Quadratic expression: it is obtained by allowing a multiplication between two linear expressions and an addition of a linear expression: A*B + C, where A, B and C are linear expressions. For instance, the expression (2*x + 3*y + 2) * (x+y) + 6*x + y – 2 is quadratic.

  • Non-quadratic expressions: any arithmetic expression which is not of the previous kind.

Constraint forms

When designing a circuit, programmers must define explicitly the constraints that define their arithmetic circuit. All constraints must be quadratic expressions of the form A*B + C = 0, where A, B and C are linear combinations of signals. For example:

  • The condition ( 3*a - 2*b ) * ( -5*a + 8 ) + ( 7*a - 7*c ) = 0 is a valid constraint for the signals a, b and c. Note that in this case we are taking the following linear combinations:

    • A = 3*a - 2*b

    • B = -5*a + 8

    • C = 7*a - 7*c

  • The condition 3*a^2 - 7 = 0 is also a valid constraint for the variable a, since it is equivalent to the expression ( 3*a ) * ( a ) - 7 = 0, that uses the linear combinations:

    • A = 3*a

    • B = a

    • C = - 7

  • The condition ( 6*a^2 - c ) * ( b - 7 ) + 9 = 0 is not a valid constraint, since the first term A = 6*a^2 - b is not a linear combination of signals (because it has the quadratic term a^2).

  • The condition ( a - 1 ) * ( b*c + 6 ) + c = 0 is not a valid constraint, since the second term B = b*c + 6 is not a linear combination of signals (because it has the quadratic term b*c).

👉 In some cases, the circom compiler may apply minor transformations to the constraints defined in the circuit in order to meet the format A*B + C = 0. The transformations are only the following ones:

  • Move from one side of the equality to the other.

    • For example, the constraint a*b = 7 would be transformed into a*b - 7 = 0.

  • Multiplication (or divisions) by constants.

    • For example, the constraint 6*a - 6*b = 0 would be transformed into a - b = 0.

In general, circom does not interfere in the definition of constraints and it is the developers' job to make sure all constraints are correct and properly define the circuit's logic. Note that any transformation applied on a constraint by the compiler results in an equivalent constraint.

Imposing constraints

The operator ===

Constraints are imposed with the operator ===, as in the following examples:

a*(a-1) === 0;
(3*a)*(b-3) + 5 === 0;

The constraints added in the code are included as assert statements in the witness code generation.

The operators ==> and <==

A constraint can be defined together with a signal assignment using the operators <== and ==>. With the operator <== the signal being assigned must be on the left hand side of the operator and with ==> , the signal must be on the right hand side. See the following example:

out <== 1 - a*b;

This line of code does two things at the same time:

  1. On one side, it forces the constraint out = 1 - a*b. Note that the constraint has the right form A*B + C = 0 . Following the notation above, we are taking A = a, B = b and C = out - 1.

  2. On the other side, it assigns to the signal out the result of the operation 1 - a*b.

The operation

out <== 1 - a*b;

is equivalent to the following piece of code:

out === 1 – a*b;
out <-- 1 - a*b;

You can read more about the different operators of circom in the section Signals and Variables > Signals > Assignment to signals.