question about FRI?

โš“ Neptune    ๐Ÿ“… 2025-01-01    ๐Ÿ‘ค wuxiu    ๐Ÿ‘๏ธ 28      

wuxiu

I am wondering about the necessary of FRI to test the low degree of boundary quotient. (boundary_quotient_codewords).

As for https://neptune.cash/learn/stark-anatomy/stark/ In the verify side, the last check of verify procedure has ensured the link between boundary quotient and transition quotient. โ€œVerify the link between boundary quotients and transition quotient. To do thisโ€

According to the stark_anatomy source code, the verify functions check the following equation: verifier_accepts = verifier_accepts and (combination == values[i])

So does this check include the correctness of boundary quotient ? I think boundary quotient should be correct if the above check is successful.

Thanks.

๐Ÿท๏ธ STARK AIR

aszepieniec    2025-01-01 ๐Ÿ‘ ๐Ÿ‘Ž

So does this check include the correctness of boundary quotient ?

Yes. But it took me a while to parse my own tutorial and convince myself of this fact. So youโ€™re not the only one who is confused ;-) If you can think of a better way to present this, then please consider making a pull request.

Whatโ€™s going on is that we make nonlinear1 random combination of all quotient polynomials2 and pass this codeword into FRI. This combination covers both transition quotients and boundary quotients.

1

The non-linearity comes from the shift induced by the factor Xs, which guarantees that the shifted polynomial has exactly the right degree. Since writing this tutorial, we determined that no soundness is lost if the shifted polynomial is dropped, making the combination into a linear one.

2

People have pointed out that the trace polynomials themselves also ought to be included into the random linear combination. While I cannot attack the system that does not include them (i.e., the one presented in the tutorial), it costs very little to err on the side of safety so in Triton VM we do include the trace polynomials.

1