More efficient remainder verification in FRI about winterfell

[irakliyk]

I think the first part will definitely work. The second part will also kind of work, but I doubt savings would be more than about 500 bytes in most cases.

The reason for the second part is that we still need to send most of the remainder. We can skip only positions which we get from folding. For example, if the remainder size is 128 elements, and and the proof contains 30 queries, then the best we could hope for is that 30 of 128 elements can be skipped. If we are in a 128-bit field, these 30 skipped elements would result in proof size reduction of 30 * 16 = 480 bytes.

[irakliyk]

The first point of this was addressed in #128

[irakliyk]

There is actually another optimization we can do which makes the second point here irrelevant. Specifically, instead of sending the actual codeword for the remainder (which we then need to interpolate into a polynomial in coefficient form), we can just send the polynomial in coefficient form. Then, the verifier would evaluate the polynomial and make sure the resulting evaluations match the commitment.

Depending on the blowup factor, this could result in signifiant savings (i.e.,g 1KB or more).

[Al-Kindi-0]

Yes, but I think that this is exactly the optimization I mentioned at the start of issue https://github.com/0xPolygonMiden/miden-vm/issues/568 . Then, as mentioned there, the iNTT check becomes unnecessary as one can just evaluate at $g^i$, where $g$ is the remainder domain generator and $i$ is the folded index at this domain, and compare to $evaluation$ one gets from the FRI-folding formula at the previous step.

[Al-Kindi-0]

Actually, an NTT on the verifier side might make sense for remainder polynomials of large degree.

[irakliyk]

Closed by #128 and #139.