In the stwo-constraint-framework, calculating the degree of an expression often requires knowing the degrees of intermediate expressions or parameters. The NamedExprs struct acts as a registry that allows you to look up the degree of named expressions (both BaseExpr and ExtExpr) to correctly compute the total degree bound of complex expressions.
Key Behaviors and Caveats
- Degree Calculation Logic: The degree is computed with respect to columns treated as variables.
- Constant 0: The constant
0 is treated as having degree 0 (rather than $-\infty$). Consequently, an expression like 0 * expr will return the degree of expr. It is recommended to use simplification to mitigate this. - Cancellation: The degree calculation does not account for algebraic cancellation. For example,
(x^2 + 1) - (x^2 + x) will return a degree of 2 because the $x^2$ terms are not symbolically canceled during the bound computation. - Inverses: Computing the degree of an
Inv (inverse) expression will panic! unless the expression being inverted is a constant or a parameter with degree 0. - Missing Names: If a name is not found in the registry and does not start with
preprocessed., it is assumed to be an external variable (effectively a constant) with degree 0.
// Example of registering intermediate expressions to compute complex degree bounds
let intermediate = (felt!(12) + col!(1, 1, 0)) * var!("a") * col!(1, 0, 0);
let qintermediate = secure_col!(intermediate.clone(), felt!(12), var!("b"), felt!(0));
let named_exprs = NamedExprs::new(
[("intermediate".to_string(), intermediate.clone())].into(),
[("qintermediate".to_string(), qintermediate.clone())].into(),
);
// Now you can look up the degree of these named expressions
let deg = named_exprs.degree_bound("intermediate".to_string());
