Constraint Degree Overflow Remediation

Overview

Related Detector: Constraint Degree Overflow

R1CS (Rank-1 Constraint System) only supports constraints of the form A * B = C where A, B, and C are linear combinations of signals. Expressions with degree greater than 2 (e.g., a * b * c) cannot be represented as a single R1CS constraint. The fix is to introduce intermediate signals that decompose high-degree expressions into a chain of degree-2 constraints.

Recommended Fix

Before (Vulnerable)

template CubeCheck() {
    signal input x;
    signal input y;

    // Degree 3 -- invalid R1CS constraint
    y === x * x * x;
}

After (Fixed — Intermediate Signal Decomposition)

template CubeCheck() {
    signal input x;
    signal input y;

    signal x_squared;
    x_squared <== x * x;     // Degree 2 -- valid R1CS
    y === x_squared * x;     // Degree 2 -- valid R1CS
}

After (Fixed — Higher-Degree Example)

For degree-4 or higher expressions, chain multiple intermediates:

template FourthPower() {
    signal input x;
    signal output y;

    signal x2;
    x2 <== x * x;        // x^2
    signal x4;
    x4 <== x2 * x2;      // x^4, each step is degree 2
    y <== x4;
}

Alternative Mitigations

1. Restructure the Computation

Sometimes a high-degree constraint can be avoided by reformulating the problem:

// Instead of checking x^3 == y directly,
// verify via a witness:
signal cube_root;
cube_root <-- y ** (1/3);  // Witness computation
signal cr_sq;
cr_sq <== cube_root * cube_root;
y === cr_sq * cube_root;
cube_root === x;

2. Use circomlib Components

For common operations that involve higher-degree logic (comparisons, range checks, multiplexers), use circomlib components that handle decomposition internally.

// LessThan handles bit decomposition internally
component lt = LessThan(64);
lt.in[0] <== a;
lt.in[1] <== b;

Common Mistakes

Relying on compiler auto-flattening: The Circom compiler may silently decompose high-degree expressions by introducing intermediate signals. These compiler-generated intermediates may not have the constraint properties you expect. Always decompose explicitly.

Forgetting mixed-product expressions: An expression like a * b + c * d === e contains two multiplications that cannot fit in a single R1CS constraint, even though each multiplication is degree 2. Decompose into separate constraints.

Over-decomposing: Only signal-signal multiplications contribute to degree. Multiplying a signal by a constant does not increase the degree because constants are absorbed into the linear combination.

References

• Circom Documentation: Constraint Generation
• R1CS Specification
• circomlib GitHub repository — examples of correct decomposition