Design constraint generation in the Circom compiler for the Ligetron target

[aesilevich]

There is a short description with a proposal for different approaches on how to generate constraints for the Ligetron target:

https://github.com/ligeroinc/circom/blob/ligetron/ligetron-constraints.md

I suggest the following:

1. Implement the runtime approach and ensure it works with large examples like the email verifier while generating a reasonable number of constraints.
2. Design and implement the minimal Ligetron backend API required for Circom: https://github.com/ligeroinc/ligetron/issues/13
3. Gradually implement the compile-time approach step by step:

• Implement basic analysis to detect individual operations for which constraints should be generated.
• Implement generation of both constrained and unconstrained versions of each function and use the appropriate version at each call site.

Alternatively, instead of step 3, we can try reusing constraint information generated by the Circom compiler in the code generator for the Ligetron target. However, I'm not sure if it's easy to implement.

@SuperHex What do you think about this?

[SuperHex]

Hi Alexandr,

Great overview! If I understand correctly, the root cause of all problems is the assignment operator x = <expr>, where you cannot identify the operating mode of <expr>. Besides that, all other translations are pretty straightforward.

I still need some time to read and understand how the Circom compiler and your compiler work, but I prefer to solve the problem in compile time. You mentioned SSA is needed but I don't think it's necessary to address that issue. For example, we can maintain a renaming buffer per function scope and replace variables with fresh names. However, the assignment issue remains.

Again I'm still researching it but what I'm thinking now is to use a two-step compilation. In the first step, we build some kind of IR and tag operating mode information to each variable. The operating mode can be one of public, witness, or unknown. In the second step, we traverse the IR and use the extra information to generate wasm code. The key idea here is we can postpone the instantiation of expression or function calls to the second step where we can query the IR to know precisely what code to generate.

Let me know if that approach makes sense to you and feel free to correct me anything.

[SuperHex]

Wait a second, forget my previous comment, now I'm confused about your issue after reviewing the Circom documentation. In the documentation, it clearly says about function:

Functions cannot declare signals or generate constraints (use templates if you need so). The next function produces the error message: "Template operator found".

which means you should never generate any constraint from a function call.

As for the var a = <expr>, you also should not generate any constraint ever. Simply generate the raw computation and whenever you hit a ===, generate a single equality constraint. So In your example:

var x = expr_1(x_1, ... x_N);
a === x;
x = expr_2(y_1, ..., y_N);
b <-- x;

Only a single asssert_equal(a, x) will be generated.

Constraint generation will only happen in instantiating a template with signal and <==, ==>, and ===.

In short, only the signal type will trigger constraint generation and everything else is either a compile-time constant or public computation.

[aesilevich]

@SuperHex Hi,

I think the Circom documentation is not clear enough in that section. The assignment operator and functions don't generate constraints by themselves. However, constraint operators generate constraints while taking into account the assignment expressions and function bodies.

I've tested the following small example:

pragma circom 2.0.0;

template Mul() {
    signal input a;
    signal input b;
    signal output out;

    var x = a * b;
    out <== x;
}

component main = Mul();

I compiled it with the --r1cs flag to generate constraints in the R1CS format:

circom mul.circom --r1cs

The Circom compiler reports that it generates one non-linear constraint for this example. I then checked the R1CS dump using the following command:

snarkjs r1cs export json mul.r1cs mul.json

The mul.json dump contains the following contents:

{
 "n8": 32,
 "prime": "21888242871839275222246405745257275088548364400416034343698204186575808495617",
 "nVars": 4,
 "nOutputs": 1,
 "nPubInputs": 0,
 "nPrvInputs": 2,
 "nLabels": 4,
 "nConstraints": 1,
 "useCustomGates": false,
 "constraints": [
  [
   {
    "2": "21888242871839275222246405745257275088548364400416034343698204186575808495616"
   },
   {
    "3": "1"
   },
   {
    "1": "21888242871839275222246405745257275088548364400416034343698204186575808495616"
   }
  ]
 ],
 "map": [
  0,
  1,
  2,
  3
 ],
 "customGates": [
 ],
 "customGatesUses": [
 ]
}

If I understand this dump correctly, it contains a single quadratic constraint out === a * b.

If you try to replace var x = a * b with something like var x = a * b * b, the Circom compiler will emit the error: "Non quadratic constraints are not allowed!"

Similarly, the Circom compiler generates the same single quadratic constraint for the following example using a function:

pragma circom 2.0.0;

function mul(a, b) {
    return a * b;
}

template Mul() {
    signal input a;
    signal input b;
    signal output out;

    out <== mul(a, b);
}

component main = Mul();

[aesilevich]

In the previous examples, we could substitute a single assignment expression or function body into the constraint operator. However, this is not always possible.

I think this example is more interesting:

pragma circom 2.0.0;

template Test {
    signal input in[10];
    signal output out;

    var sum = 0;
    var e2 = 1;

    for (var i = 0; i < 10; i++) {
        sum += in[i] * e2;
        e2 = e2 + e2;
    }

    sum === 10;
}

component main = Test();

The Circom compiler generates a single linear constraint for this example:

in[0]​ + 2 * in[1] ​+ 4 * in[2]​ + 8 * in[3] ​+ 16 * in[4] + 32 * in[5] ​+ 64 * in[6] ​+128 * in[7] ​+ 256 * in[8] ​+ 512 * in[9] ​=== 10

So, we can't just substitute an expression to generate constraints at the point where the === operator appears. Instead, we have to generate constraints when executing the assignment operator or perform some form of interpretation at compile time to generate the constraint for this example. (I think this is what the Circom compiler does when generating constraints in the R1CS format)

[SuperHex]

So to verify my theory, I also did some experiments with the original Circom compiler. You can use circom --r1cs --sym mul.circom and snarkjs r1cs print mul.r1cs to get a better constraint structure. Anyway here is the result:

• Case 1: Simple Multiplier

template Multiplier2() {
    signal input a;
    signal input b;
    signal output c;
    c <== a * b;
 }

Result: 1 quadratic constraint c = a * b

• Case 2: Multiplier with variable

template Multiplier2() {
    signal input a;
    signal input b;
    signal output c;
    var d = a * b;
    c <== d;
 }

Result: 1 quadratic constraint c = a * b
Observation: variable does not fold expressions

• Case 3: Multiplier with complex expression

template Multiplier2() {
    signal input a;
    signal input b;
    signal output c;
    var d = a * b + a * b;
    c <== d;
}

Result: error[T3001]: Non quadratic constraints are not allowed!

• Case 4: Function call with public input

function pow3(x) {
    return x * x * x;
}

template Multiplier2(N) {
    signal input a;
    signal input b;
    signal output c;
    c <== pow3(N);
}

component main = Multiplier2(2);

Result: 1 linear constraint c = 8
Observation: function call body with public argument will not generate constraints, no matter where the result is assigned. Value is evaluated in compile time.

• Case 5: Function call with signal

// same circuit above
c <== pow3(a);

Result: error[T3001]: Non quadratic constraints are not allowed!
Observation: Function call with private input (signal) will generate constraints

• Case 6: Example mentioned before

template Test {
    signal input in[10];
    
    var sum = 0;
    var e2 = 1;
    
    for (var i = 0; i < 10; i++) {
        sum += in[i] * e2;
        e2 = e2 + e2;
    }
    
    sum === 15;
}

Result: 1 big r1cs linear constraints sum = in[0] * 1 + ... + in[9] * 10

Conclusion

With all the experiments above, It seems var and function are more like a speculative macro that will evaluate compile-time constant expressions but behave like text replacements for private signals. The rules are pretty straightforward then:

1. tag everything with a tag, private or public.
2. generate constraints for any op(a, b) where a or b is tagged private, tag the result also private
3. var and function are abstract until being instantiated as/with inputs. During instantiation, apply 2 repeatedly
4. generate raw compute for public signals, evaluate all other public expressions at compile time

Overall, I think you can generate constraints solely based on the tag. Circom must already have this information since it can generate correct R1CS.

[aesilevich]

Yes, I can generate constraints this way, but that would require creating some form of an interpreter for Circom programs. We need to iterate through loops, conditional statements, and function calls to build a complete set of constraints for a template.

I think this is what they do in the constraint_generation/src/execute.rs source file, which contains about 4,000 lines of code. It would be great if I could reuse the constraints they calculate, but I'm not sure it would be that easy.

From what I see when looking at the code, the Circom compiler works as follows:

1. First, it parses the Circom program and builds an AST for the entire program. The AST represents the Circom program in almost its original form, without identified variables or subcomponents.

2. The Circom compiler interprets the parsed AST in a way similar to what you suggested, but for the entire program. It performs the following steps:

• Instantiates templates, creating a unique template instance for different template parameters.
• Builds a global component map for the entire program, allocates them in global memory, and assigns unique IDs to each signal.
• Calculates constraints for the entire program using the assigned global signal IDs.

3. For each template instance, the compiler generates a low-level intermediate representation (IR) to compute output signal values from input signals at runtime. It also generates low-level IR for each function.

The low level IR contains very limited information about original program:

• All template signals are stored in a single table.
• All accesses to signals are represented with offset withing this table, with address arithmetic for arrays.
• The same is done for all local variables

4. In the last stage, the code generator produces WASM or C++ code from the low-level IR.

The final stage is where I generate WASM code for the Ligetron target in the Circom compiler. Now, I think this might not have been the best choice, as I’ve encountered many problems with identifying individual signals and variables, converting field variables to 32-bit, and filtering out intermediate signals to reduce global memory usage for subcomponents.

I think I should check whether we can extract the required constraint information generated in Stage 2 and use it for our needs. I need some time to investigate this.

[SuperHex]

So let's forget about all the optimizations for now, i.e. keep all fields as-is and don't worry about memory efficiency. Can you develop an R1CS-based wasm target that evaluates constants and generates constraints as well as the original compiler? Does the difficulty come from the optimizations or the compiler architecture?

[aesilevich]

The difficulty comes from the compiler architecture. We need to pass constraints generated for the high-level IR to the low-level IR. But after taking a closer look at the source code, I now think it's possible to extract constraint information generated by the Circom compiler and propagate it to the low-level IR. I will try to do that in the next few days.

The only problem I see with this solution is increased code size. We have to generate all constraints for a template as a sequence of calls to runtime functions, and it will be generated without loops, so it could increase code size. For example, for this loop:

for (var i = 0; i < 100; i++) {
    in[i] * (1 - in[i]) === 0;
}

our code generator will generate 100 calls to runtime functions for making constraints. I'm not sure how it will imact on code size, we will see it when it will be implemented.

[SuperHex]

Sounds good, I'll investigate the source code in the meantime, keep me posted.

For the problem, why do we have to unroll the loop? Couldn't we simply skip all loop evaluation and generate a wasm loop? I'm fine with not doing the u32 optimization (given we have the raw compute calls) and have a few extra public computations inside the loop.

A few tips that might be useful:

• instead of generating wat/wasm, I think it's easier to work with C/C++ and compile to wasm
• our backend calls don't assume single assignment, it's ok to overwrite a variable and set constraints on it

[aesilevich]

Hi @SuperHex ,

For the problem, why do we have to unroll the loop? Couldn't we simply skip all loop evaluation and generate a wasm loop? I'm fine with not doing the u32 optimization (given we have the raw compute calls) and have a few extra public computations inside the loop.

What I'm trying to do now is reuse constraint information generated by the Circom compiler at Stage 2 (mentioned in the previous post) for the R1CS constraint format. This information is represented as a set of equations for all signals in a template, with distinct equations for each array element. As a result, I can't generate an array loop from it.

So, we can't reuse the results from the existing constraint generator to produce compact code with loops. I think it's possible to write a new constraint generator for the Ligetron target, but this would be a huge task and could probably take weeks. We would have to write code similar to what is in the constraint_generation subfolder (~7,000 lines of code).

So, should I try to write a new constraint generator? What do you think?

[SuperHex]

I'll go over the code before I can give more instructions. Meanwhile, go ahead with your new idea if it's quick, and let's see how bad is it in terms of code size.