symbolically evaluate transition constraints

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\left(X\right)$ be the trace polynomials and $D=⟨\omega ⟩=\left\{{\omega }^i\right|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\left(f\right({\omega }^i),f({\omega }^{i+1}\left)\right)=0$. Another way of saying the same thing is that $C\left(f\right(X),f(\omega ·X\left)\right)$ has to be zero on $X\in D\setminus \left\{{\omega }^{N-1}\right\}$, 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\left(f\right(X),f(\omega ·X\left)\right)$ 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\left(X\right)=\frac{X^N-1}{X-{\omega }^{-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.