Remainder verification in FRI for large codewords

[Al-Kindi-0]

As discussed in #564 , early stopping in FRI verification can lead to substantial savings in the number of cycles used by the FRI Miden assembly verifier.
The way Winterfell implements remainder verification requires that the verifier performs a NTT in order to assert a degree bound on a polynomial. An optimization could be for the prover to send the final polynomial in the clear so that the degree check becomes trivial. This issue aims to discuss other solutions in order to achieve a better cycle count for Fri verification in Miden. More specifically:

1. Using a probabilistic NTT argument, lay out in as precise a manner as possible, the equivalent of the remainder verification procedure as is done in Winterfell in Miden assembly.
2. Discuss the costs of the above for codewords of length 64, 128 or even larger.
3. Put the above in the context of Folding with higher folding factors than 2 #567 so as to achieve the goal of cycle-saving with the smallest amount of new instruction, if any.

The following preliminary plan of action might be useful:

• Implement non-deterministic inversion in the degree 2 extension field #591
• Implement remainder verification procedure using probabilistic argument #592

[Al-Kindi-0]

Here is a more concrete attempt at a solution to the above:

Suppose that the remainder codeword has been processed using adv_pipe at the setup stage for the current FRI verification. Note that the remainder is needed by each query verification even before the low-degree check that is the focus of this issue.
The use of adv_pipe allows us to generate a hash which can be used, together with the hash of the iNTT (will describe this shortly) to avoid malleability attacks, to generate challenges that we can use à la Fiat-Shamir to verify that the iNTT that is provided non-deterministically is the actual iNTT of the remainder. If then this iNTT has a number of non-zero values less than a bound computed by the verifier, the verifier will be able to conclude with high confidence that the remainder is in fact a low-degree polynomial.
To boost the confidence of the verifier (i.e. reduce soundness error), the verifier can repeat the same procedure with a new random challenge.

More concretely, denote by $P$ the claimed iNTT of the remainder codeword where we think of it as the coefficients of a polynomial in the monomial basis i.e. $$P(X) = \sum_{i = 0}^{n-1} p_i X^i$$
where $n$ is the degree bound computed by the verifier. This $P$ can be thought of as the purported remainder polynomial provided the iNTT is done with the appropriate offset.
Denote by $Q$ the remainder codeword where we think of it also as the coefficients of a polynomial in the monomial basis i.e. $$Q(X) = \sum_{i = 0}^{m-1} q_i X^i$$
where $m$ is the length of the remainder codeword.

The Miden verifier will then execute the following:

1. Compute $$\alpha := P(\tau) = \sum\limits_{i = 0}^{n-1} p_i \tau^{i}$$
2. Compute $$\beta := \frac{\sum\limits_{j=0}^{m-1}\frac{\omega_j}{\tau - \omega_j}q_j}{\sum_\limits{j=0}^{m-1}\frac{\omega_j}{\tau - \omega_j}}$$ where $\omega_j$ is $\omega^j$ with $\omega$ the domain generator of the domain of size len(remainder).
3. Assert $$\alpha = \beta$$

A few words regarding immediate optimizations and costs are in place:

1. All of the coefficients are in the extension field and hence it is desirable to minimize the number of multiplications/inversions in the extension field. Thus, reducing the computation of inverses in the extension field to multiplications, using non-determinism, is a worthwhile endeavor.
2. The evaluation $P(\tau)$ is done using Horner's method and this costs $n * (M_e + A_e)$ where $M_e$ is an extension field multiplication and $A_e$ is an extension field addition. In the case of a blowup factor of $8$ and remainder length of $m = 64$, $n$ will be less than or equal to $8$.
3. Computing $\beta$ has an approximate cost of $(A + M_{e} + M_{e} + 2*M) * m + M_{e}$, provided the $\omega_j$'s are precomputed, where $M$ and $A$ are a multiplication, respectively an addition, in the base field.

A companion Rust code illustrating the ideas discussed above can be found here.

[bobbinth]

@Al-Kindi-0 - thank you! this is really cool (and Rust code is super helpful)!

A couple of comments:

• For the inversion in the extension field we should probably add a decorator so that we can compute the value non-deterministically. I'll create an issue for this.
• For soundness, is evaluating at a single point enough? Assuming $\tau$ is in the extension field, how much security do we get from performing this procedure once?

[Al-Kindi-0]

Thank you @bobbinth !

1. Yes, I have assumed in my cost estimations that inversion in the extension field is done using non-determinism and its cost is thus that of a multiplication, approximately.
2. If we choose $\tau$ from the extension field, then we would get enough soundness at the 100bits security level. If we use the base field, then we would need to repeat the argument twice in order to get the same security level. The deciding factor, I believe is the cost of the first approach versus the second one. I will have to double check if we can have $\tau$ in the base field if we want to go this route.

[aszepieniec]

Nice stuff! I think it's correct and sound.

Towards computing concrete soundness: suppose [q_i | 0 <= i < m] does not agree with a polynomial of degree at most n-1 on [ω_i | 0 <= i < m]. Then through the barycentric evaluation formula [q_i] defines a polynomial Q(X) of degree at most m-1 which is evaluated in τ to give β. The number of coefficients bounds the degree of P(X) to at most n-1 whose evaluation in τ is α. So the equation β =?= α is really probing the identity of polynomials P(X) = Q(X) in X = τ. The degree of the difference is bounded by m-1 and so the Schwarz-Zippel lemma tells us that if P(X) =/= Q(X) then P(τ) = Q(τ) with probability at most (m-1)/|F|, where |F| is the size of the field that τ is sampled from. This probability is exactly the soundness error. The construction gives - log_2 Prob bits of security, or 56 bits if m = 256 and |F| = 2^64.

To reach 100 bits security it is better to repeat this protocol twice than to do it over an extension field of degree two. The Schwarz-Zippel lemma does not need either polynomial to be random; it just needs the sample point τ to be random. And if you sample it a second time independently, you get to multiply the probabilities of successfully cheating probabilities – or add the securities when measured in bits.

[Al-Kindi-0]

Thanks!
As you mentioned, performing the test at two independently sampled challenges in the base field gives the same soundness as checking the identity at a challenge in the quadratic extension field. The only deciding factor that I can think of is performance, especially if one can have a special instruction to do multiplication in the extension field.
As for the soundness error, I think one has to take care of the case when the challenge $\tau$ is chosen to be one of the $\omega_j$'s. I think the cleanest approach is to remove the $\omega_j$'s from the challenge space and since the number of such $\omega_j$'s is relatively small, 100 bits of security is achievable with either of the two approaches mentioned in the previous paragraph.
One last thing to add, is that in the Fiat-Shamired version of the above, one has to think of the case when the resulting challenge is one of the $\omega_j$'s. This is a very unlikely event for honest provers but can be conjured by a dishonest one.
Aborting seems to me to be the most reasonable course of action to hedge the latter scenario but maybe one has to think of the case of honest provers as well.
Am I overthinking this?

[aszepieniec]

I think one has to take care of the case when the challenge $\tau$ is chosen to be one of the $\omega_j$'s.

I don't think that this case requires special attention. By treating the evaluations of $P(X)$ and $Q(X)$ as black boxes, we get a result holding for randomly chosen $\tau$, whether it happens to coincide with some $\omega_j$ or not.

[Al-Kindi-0]

So, for $\beta$ at $\tau = \omega_j$ one would return $q_j$?

[aszepieniec]

Yes.

[bobbinth]

Closed by #644