question about STARK transition constraints? thanks.

⚓ Neptune 📅 2024-12-22 👤 wuxiu 👁️ 122

Warning

This post was published 44 days ago. The infomation described in this article may have changed.

I was wondering about the transition polynomials when reading the stark-anatomy source code.

To get dense trace polynomial , subtract the boundary interpolant from the trace polynomial, then divide boundary zerofiers and give rise to boundary quotient.

But for transition polynomial, the transition_quotients are generated by only dividing by transition_zerofiers without subtracting interpolants? So this divding ensure the

Why does the difference exists?

symbolically evaluate transition constraints

    point = [Polynomial([self.field.zero(), self.field.one()])] + trace_polynomials + [tp.scale(self.omicron) for tp in trace_polynomials]
    print("begin symbolic eva:point len=",len(point),",transition_constraints len=",len(transition_constraints))
    transition_polynomials = [a.evaluate_symbolic(point) for a in transition_constraints]
    print("end symbolic eva")

    # divide out zerofier
    transition_quotients = [tp / self.transition_zerofier() for tp in transition_polynomials]

🏷️ STARK AIR

👍 󠁮󠁮󠁮󠁮 👎 󠁮󠁮󠁮󠁮

aszepieniec 2024-12-22 👍 👎

What I think you are missing is the step whereby trace polynomials are transformed into transition polynomials via symbolic evaluation.

Specifically, we have a transition constraint $C (x, y)$ . Let $f (X)$ be the trace polynomials and $D = ⟨ ω ⟩ = {ω^{i} | i \in Z}$ be the trace interpolation domain of length $N$ . If the transition constraint applies to every consecutive pair of rows, then for all $i \in Z$ , $C (f (ω^{i}), f (ω^{i + 1})) = 0$ . Another way of saying the same thing is that $C (f (X), f (ω \cdot X))$ has to be zero on $X \in D ∖ {ω^{N - 1}}$ , where we omit the last element from the domain because we don’t care about transitions covering the (last, first) rows.

You can call $C (f (X), f (ω \cdot X))$ the transition polynomial; it is obtained by symbolic evaluation of the constraint on the trace polynomials. And since its zeros agree with those of the zerofier $Z (X) = \frac{X^{N} - 1}{X - ω^{- 1}}$ (in the honest case), it must be divisible by the zerofier. So if you perform this division, then an unclean division (which manifests as a high-degree quotient) will expose the cheating prover.

In the tutorial I wanted the constraint to take additional arguments, 0 and 1, but this is actually a distraction for the purpose of explaining so please ignore that detail.

wuxiu 2024-12-22 👍 👎 [op]

I’v got it. thanks for you patience.