Fox is an Ethereum zkRollup using ZK-EVM and its original ZK-FOAKS technology. ZK-STARKS comes from Zero Knowledge - Fast Objective Argument of Knowledges that is faster than Stark with linear proof time, sublinear verification time, transparent, and proof recursion inside.

FRI is an IOPP constructed for the RPT problem, which is executed interactively by both the Prover and the Verifier. At the beginning of the protocol, Verifier has learned the complete encoding f(S), but has not read this encoding, it can query any part of the encoding at any time during the execution of the protocol.

The aim of this section is to expound on how to verify the polynomial efficiently and correctly.

During the execution of the protocol, the Prover and the Verifier interact multiple times. In each interaction, the Prover sends a string to the Verifier, and the Verifier can randomly read any bits of the string without reading the entire string.

Now, let us recall our motivation. Initially, we want to prove that we certainly finished the computation correctly. Subsequently, we translate the original computation problem into a series of constraints expressed by wires and gates, which are actually so-called circuits. Next, it is known now that the circuits could be compressed to a set of polynomials, which can be verified by some methods. Consequently, if the polynomials are verified correctly, the verifier could believe that the procedure of the computation is precisely correct and we did not cheat.

In fact, there are several ways to implement this verification, for example, KZG. The reason why we choose FRI is that FRI does not need a trusted setup, which is an indispensable part of KZG.

For the FRI protocol, the complexity of the verification satisfies the logarithmic relationship. The algorithm ensures that the round consistency verifications can be passed if and only if the initial polynomial satisfies. The actual implementation may vary slightly.