Constraint Degree Overflow

Overview

Remediation Guide: How to Fix Constraint Degree Overflow

The degree overflow detector flags constraint expressions whose multiplicative degree exceeds the limit of the target proof system. R1CS-based systems (Groth16 and similar) accept only quadratic constraints, where each constraint takes the shape (linear) * (linear) = (linear). Custom-gate systems such as PLONK or Halo2 admit higher degrees, but every backend has a ceiling.

When a constraint’s degree exceeds the limit, the compiler must expand it into multiple lower-degree constraints by introducing fresh intermediate signals. The expansion is correct, but it inflates proving cost and, more importantly, hides constraint structure from the developer who wrote the high-degree expression.

Why This Is an Issue

The expanded form is semantically equivalent to the original only when the compiler’s decomposition is correct and complete. In practice, three failure modes are common:

• The intermediate signals introduced during expansion may be left unconstrained in subtle ways, especially when the expansion interacts with <-- assignments elsewhere in the template.
• The expansion multiplies the number of constraints, which can push the circuit over a target gate count and force a redesign late in development.
• Reviewers reading the original source have a different mental model than the circuit that actually runs, which makes audit findings harder to reason about.

For non-R1CS backends, exceeding the custom-gate degree silently shifts the constraint into the expansion path. The circuit still proves correctly, but the cost model breaks.

How to Resolve

Decompose high-degree expressions explicitly. Introduce one named intermediate per multiplication and chain the intermediates with <==.

// Vulnerable: degree-3 constraint
template Cubic() {
    signal input a;
    signal input b;
    signal input c;
    signal output result;

    result <== a * b * c;   // degree 3 — exceeds R1CS limit
}

// Fixed: explicit degree-2 decomposition
template Cubic() {
    signal input a;
    signal input b;
    signal input c;
    signal output result;
    signal ab;

    ab <== a * b;           // degree 2
    result <== ab * c;      // degree 2
}

The same approach handles sums of products such as a*b + c*d === e: split each multiplication into its own intermediate, then sum the intermediates in the final constraint.

Sample Sigvex Output

{
  "detector": "degree-overflow",
  "severity": "medium",
  "confidence": 0.80,
  "title": "Constraint exceeds R1CS quadratic degree in template `Cubic`",
  "template": "Cubic",
  "line": 7,
  "description": "Constraint `result <== a * b * c` has multiplicative degree 3, exceeding the R1CS quadratic limit. The compiler will expand this into auxiliary signals.",
  "recommendation": "Decompose the expression into degree-2 steps using named intermediate signals."
}

Detection Methodology

For each <== and === assignment, the detector parses the right-hand expression into a tree of additions and multiplications. It computes the multiplicative degree by walking the tree: an addition takes the maximum degree of its children, and a multiplication takes the sum. The maximum degree across all terms is compared against two thresholds: 2 (R1CS quadratic limit) and 4 (PLONK custom-gate conservative ceiling). Constraints above 2 are reported at Medium severity; constraints above 4 are reported at High severity.

Limitations

• The expression parser handles +, -, *, and parentheses. Constraints that use division, bit operations, or function calls are skipped, which may produce false negatives.
• The detector does not know which proof system the circuit targets, so it always reports both thresholds. Projects using a high-degree backend can treat the Medium findings as informational.
• The reported degree is the worst-case value across all terms; a constraint with one degree-3 term and many degree-2 terms is reported once.

Related Detectors

• Quadratic Constraint Composition — soundness of multiplicative constraints
• Witness Complexity — costly witness computations
• Trivial Constraint — constraints providing no binding

References

• R1CS Specification (iden3)
• PLONK Paper (IACR)
• Halo2 Book