The core of FRI IOP

  1. prover commit to \(f(x)\)

$$f(X)=f_E(X^2)+X\cdot f_O(X^2)$$

if we take an intermediate variant \(Y\) to replace the \(X^2\)

With a fixed \(Y\), then \(f(x)\) can be considered as one degree polynomial for \(X\), as

$$f(X)=f_E(Y)+X\cdot f_O(Y)$$

and for a given \(y\), it determineds a unique line (one degree polynomial)

and the point \((\sqrt{y},f(\sqrt{y}))\) should also be on this line.

thus, for a given \(y\), two points on the original polynomial \((-\sqrt{y},f(\sqrt{y}))\) , \((-\sqrt{y},f(-\sqrt{y}))\) can already interpolate the unique one degree polynomial, the line \(f(X)=f_E(Y)+X\cdot f_O(Y)\) .

2. verifier send a randomness \(\alpha\), here, what the verifier does is actually equivalent to choose a thrid point, \((\alpha, f_E(y)+\alpha\cdot f_O(y))\) to test if it is on the line. (but now the line is not fix yet, as the \(y\) is not fixed yet. )

3. verifier verifys the consistant, which mean, verifier choose, lets say \(x_0\) and \(-x_0\), this fix the line, and then verify if \((\alpha, f_E(x_0^2)+X\cdot f_O(x_0^2))\) is on the line.

Leave a Reply

Your email address will not be published. Required fields are marked *