Question about TransitionConstraintDegree in examples about winterfell

[Nashtare]

The degree of equation 4 is not 6.
Denoting $m_i = \sum\limits_{j=0}^{m-1} 2^j \cdot A_{i,j}$, we have that $m_i$ is of degree 1, and we can rewrite the eq. 4 as
$\forall i < n-1: A_{i,0} \cdot \left[ 3\cdot m_i + 1 - m_{i+1} \right] + (1 - A_{i,0}) \cdot \left[ m_i - 2 \cdot m_{i+1} \right] = 0$
This is an equation of degree 2, the maximum between

1. degree of temporary variable $m_i$ + degree of cell $A_{i,0}$
2. degree of temporary variable $m_{i+1}$ + degree of cell $A_{i,0}$

(note that both are of same degree)

[Nashtare]

In your evaluate_transition function, you wrote

        if num_from_state(current) == E::ONE {
            return;
        }

You cannot return early while evaluating the constraints, this doesn't mean anything valid algebraically speaking. When the prover constructs the original execution trace, it fills it with the actual values of the program. Here, it consists on the different number of the Collatz sequence, plus some additional variables like binary values.
To prove consistency of this trace without explicitly disclosing it, among other things (I insist on this), the prover will allow the verifier to check correctness of the constraints on two consecutive rows of an extended trace, defined over the LDE domain. On this domain, the relations look rubbish, i.e. you'll never (with high probability) get a cell element that equals to one, as you expect it in your code.

If you want your statement to be "I want to prove to you that starting number N reaches 1 under Collatz conjecture after k steps", you may want to include the number of steps k in your public inputs, and define a trace exemption (you can see how it is done in vdf/exempt/air.rs example), to define which rows should be ignored. This will maintain the algebraic properties when extending the trace to a larger domain (but I won't cover the details on how this works here) and should make your example work.

[Nashtare]

I found there are rescue::enforce_round constraints which have degree of 3 for the above first six terms

Merkle example uses the Rescue implementation over the 128 bit field implemented here. The degree of the forward s-box is 5 (the value by which we exponentiate each element). Hence the degree is 5, and not 3.

Hashing is applied when the periodic column hash_flag is on. When it is not, (i.e. hash_init_flag is on), we do not compute any Rescue permutation, but just ensure we placed the previously computed hash into the correct position. This is reflected by:

result.agg_constraint(0, hash_init_flag, not_bit * are_equal(current[0], next[0]));
result.agg_constraint(1, hash_init_flag, not_bit * are_equal(current[1], next[1]));
result.agg_constraint(2, hash_init_flag, bit * are_equal(current[0], next[2]));
result.agg_constraint(3, hash_init_flag, bit * are_equal(current[1], next[3]));

Here, current[i] and next[j] are both of degree 1. are_equal does not increase the degree (only subtraction, no multiplication). Hence the total degree is 2 (ignoring the periodic flag), as we multiply by either bit or not_bit. Because this degree is lower than the Rescue permutation degree, we indicate 5 when defining the transition contraint degrees.

[Nashtare]

You may want to familiarize yourself with the Degree of a polynomial, especially section Behavior under polynomial operations.

[wangtsiao]

Thank @Nashtare for the helpful answer! What a friendly community!

Finally, I completed my first STARK try using winterfell. Here is the fixed version collatz sequence example, I update it for people who are interested.

Confusion was resolved, so I close the issue.

[wangtsiao]

@Nashtare Thank you, sir. I got your explanation about the merkle tree example. But I am still confused about the rule of setting constraint degree. For example, I try to implement The Collatz Sequence Execution Trace example in the Starkware Arithmization I blog for study.

Take 52 as the input, the trace table is shown below.

It is noted that the trace table has a length of 12, which is not a power of 2. So I just pad the trace table using zero, so that it has a length of 16. I am not sure whether this will have a pact on constraints' degrees.

The collatz sequence CI statement has 4 constraints, the first two are boundary constraints, which will be expressed in get_assertions using a vector of winterfell::Assertion. The other two are normal constraints, which should correspond to a Vec<TransitionConstraintDegree>. Here I write the third constraint as a sum of is_binary. Since the sum operation does not increase the degree, we only consider the square operation in is_binary, then I determine the degree is 2.

// TransitionConstraintDegree::new(2)
for i in 0..TRACE_WIDTH {
    result[0] += is_binary(current[i]);
}

For the fourth constraint, the first column multiplies every six columns in the trace table, so I think the degree is 6. But it did not work. I am not sure whether the pad impacts the degree or if I made a false degree.

What's the right degree here, or should I pad the trace table? what's the right way to implement the collatz sequence example?

[wangtsiao]

Thank you, sir, you mentioned the behavior under polynomial operations, and I suddenly understood.

Now, I am sure the degree of the fourth constraint is 2. I changed it in my implementation code, however, it still panics with the below error. Seems I got something else wrong.

set assertion for initial number BaseElement(52) and step BaseElement(11)
thread 'main' panicked at 'assertion failed: `(left == right)`
  left: `[15, 15]`,
 right: `[15, 31]`: transition constraint degrees didn't match
expected: [ 15,  15]
actual:   [ 15,  31]', D:\devnow\paper-2023\winterfell\prover\src\constraints\evaluation_table.rs:221:9
note: run with `RUST_BACKTRACE=1` environment variable to display a backtrace

[wangtsiao]

I upload my buggy code of the above example. Here is diff.