Quadratic Constraint Composition Remediation

Overview

Related Detector: Quadratic Constraint Composition

R1CS requires every constraint to have the form (linear_combination) * (linear_combination) = (linear_combination). Expressions containing multiple signal multiplications (e.g., a * b + c * d === e) cannot be expressed as a single R1CS constraint. The fix is to manually decompose complex expressions into individual degree-2 constraints using intermediate signals.

Recommended Fix

Before (Vulnerable)

template Mixer() {
    signal input a, b, c, d;
    signal output e;

    // Two multiplications -- not a valid single R1CS constraint
    a * b + c * d === e;
}

After (Fixed – Explicit Decomposition)

template Mixer() {
    signal input a, b, c, d;
    signal output e;

    signal ab;
    ab <== a * b;       // Single multiplication -- valid R1CS
    signal cd;
    cd <== c * d;       // Single multiplication -- valid R1CS
    e <== ab + cd;      // Linear combination only -- valid R1CS
}

After (Fixed – Complex Expression)

For expressions with three or more multiplications:

// Before: a*b + c*d + e*f === g (three multiplications)
signal ab;
ab <== a * b;
signal cd;
cd <== c * d;
signal ef;
ef <== e * f;
g === ab + cd + ef;   // All linear -- valid single R1CS constraint

Alternative Mitigations

1. Rearrange to Reduce Multiplications

Sometimes algebraic rearrangement reduces the number of multiplications:

// Before: (a + b) * (c + d) + a * c === result
// This has two multiplications. But expanding:
// a*c + a*d + b*c + b*d + a*c = 2*a*c + a*d + b*c + b*d
// Still multiple multiplications. Use intermediates instead.

signal sum1;
sum1 <== (a + b) * (c + d);  // Single multiplication
result === sum1 + a * c;      // ERROR: still two total
// Must decompose further:
signal ac;
ac <== a * c;
result === sum1 + ac;         // Now each constraint has one multiplication

2. Factor Common Subexpressions

If the same product appears in multiple constraints, compute it once:

signal ab;
ab <== a * b;  // Compute once
constraint1 === ab + c;
constraint2 === ab * d;  // Reuse ab

Common Mistakes

Assuming addition of products is a single constraint: a * b + c * d === e looks like one constraint, but it contains two multiplications and must be split. Only one multiplication is allowed per R1CS constraint.

Forgetting that <== with multiplication counts as a constraint: The expression x <== a * b generates a constraint. If you then write y === x * c, that is a second constraint. Both are valid individually.

Not constraining intermediate signals: When decomposing, use <== (not <--) for intermediate signals. Writing ab <-- a * b without ab === a * b leaves the intermediate unconstrained.