While implementing several application circuits with Winterfell I hit the
"transition constraint degrees didn't match" assertion repeatedly, and
worked out two things that took me a while and are not in the docs. Sharing
in case they're useful for the documentation, or in case I've misunderstood
something.
1. The relationship between the declared degree and the expected value
From comparing the expected and actual arrays across several failures on
a 512-row trace, the expected degree appears to be:
TransitionConstraintDegree::new(d) -> (d - 1) * (n - 1)
TransitionConstraintDegree::with_cycles(d, [n]) -> d * (n - 1)
So a cyclic column effectively contributes one degree. Once I worked this
out I could translate a mismatch directly into the correct declaration
instead of guessing, which saved a lot of iterations.
If that's accurate, having it stated in the docs — or in the assertion
message itself — would help. The current message gives the two arrays but
not the mapping back to the declaration.
2. Constraints over columns that are constant by construction
This one surprised me. Consider:
// y, u, r, c are all transport columns: constant across the whole trace
result[i] = current[COL_Y] - (current[COL_U] + current[COL_R] * current[COL_C]);
I declared this as degree 2, reasoning that it multiplies two trace
columns. Winterfell rejected it: actual degree 0.
The reason is that all four columns are constant — the transport
constraints force them to be — so the product of two constant polynomials
is constant, and the whole expression has degree 0 regardless of its
algebraic form. Declaring new(1) is correct.
The contrast that made it click: a boolean check b * (b - 1) also
multiplies two columns and is degree 2, because the bit varies across
rows.
So the degree depends on whether the columns vary, not on the shape of the
expression. That's obvious in hindsight but I didn't find it stated
anywhere, and it cost me a couple of debugging cycles.
Context
Encountered while building settlement circuits for a comparative study of
five proof systems, and a follow-up on digital euro privacy requirements.
Both are public if the concrete cases are useful:
Happy to open a PR against the docs if either of these is worth writing up
and I've got them right.
While implementing several application circuits with Winterfell I hit the
"transition constraint degrees didn't match" assertion repeatedly, and
worked out two things that took me a while and are not in the docs. Sharing
in case they're useful for the documentation, or in case I've misunderstood
something.
1. The relationship between the declared degree and the expected value
From comparing the
expectedandactualarrays across several failures ona 512-row trace, the expected degree appears to be:
So a cyclic column effectively contributes one degree. Once I worked this
out I could translate a mismatch directly into the correct declaration
instead of guessing, which saved a lot of iterations.
If that's accurate, having it stated in the docs — or in the assertion
message itself — would help. The current message gives the two arrays but
not the mapping back to the declaration.
2. Constraints over columns that are constant by construction
This one surprised me. Consider:
I declared this as degree 2, reasoning that it multiplies two trace
columns. Winterfell rejected it: actual degree 0.
The reason is that all four columns are constant — the transport
constraints force them to be — so the product of two constant polynomials
is constant, and the whole expression has degree 0 regardless of its
algebraic form. Declaring
new(1)is correct.The contrast that made it click: a boolean check
b * (b - 1)alsomultiplies two columns and is degree 2, because the bit varies across
rows.
So the degree depends on whether the columns vary, not on the shape of the
expression. That's obvious in hindsight but I didn't find it stated
anywhere, and it cost me a couple of debugging cycles.
Context
Encountered while building settlement circuits for a comparative study of
five proof systems, and a follow-up on digital euro privacy requirements.
Both are public if the concrete cases are useful:
Happy to open a PR against the docs if either of these is worth writing up
and I've got them right.