# FRI FRI is a protocol proves that a polynomial is **close** to a polynomial of **low** degree. The FRI protocol operates by recursively reducing the problem of verifying a low-degree polynomial on a large domain into smaller subproblems, reducing the domain size at each step. It consists two phases: **commit** and **query** 0. **Initial Setup**: Prover: Holds a codeword $f_0(D)$, which is a sequence of evaluations of some function $f_0(X)$ on a large domain $D=<\omega>$. 1. **Commit phase (r rounds)** 1.1. **Merkle Commitments**: To ensure that the prover can't cheat, each codeword is committed by sending its Merkle root to the verifier. 1.2. **Domain Halving**: The verifier responds with the random folding challenge $\alpha$. The prover computes a new codeword by the split-and-fold method, and commits to it by sending its Merkle root to the verifier. This process is repeated over several rounds. In each round, the prover "folds" the previous codeword into a smaller codeword. - In the first round, the prover commits to $\{f_0(\omega^i)\}$. - In the second round, the prover commits to $\{f_1(\omega^{2i})\}$. - In the third round, the prover commits to $\{f_2(\omega^{4i})\}$ - ... 1.3. **Last Round Check**: The prover sends the final codeword, and the verifier checks that it matches the committed values from the last round. 2. **Query phase**: the verifier selects specific leaf indices, and the prover is required to reveal the corresponding codeword values along with the Merkle tree authentication paths for those indices. This allows the verifier to verify the consistency of the revealed values. - Assume $j$ is a queried indice, the revealed codewords are: - $f_0(\omega^j), f_0(-\omega^j)$ - $f_1(\omega^{2j}), f_1(-\omega^{2j})$ - $f_2(\omega^{4j}), f_2(-\omega^{4j})$ - ... - The verifier checks the evaluations for all i that: - $f_{i+1}(x^2)=2^{-1}\cdot\big((1+\alpha_i\cdot x^{-1})\cdot f_{i}(x) + (1-\alpha_i\cdot x^{-1})\cdot f_{i}(-x)\big)$, where $x=\omega^{2^ij}$ ![FRI](https://neptune.cash/learn/stark-anatomy/graphics/fri-overview.svg) ## Supporting Materials ### Reed-Solomon codes [Reed-Solomon codes](https://dev.risczero.com/reference-docs/about-rs-codes) have strong error-detection and error-correction capabilities, which provides soundness (any error in the execution trace can be simply identified). RS expenstion rate = d/|D| FRI blow-up factor = 1/ RS expenstion rate In the query phase, a dishonest prover may pass the verification with a probability that depends on the FRI blow-up factor. For a more detailed security analysis, refer to the soundness error in [this work](https://eprint.iacr.org/2022/1216). ### Split-and-Fold Divided a polynomial $f(X)$ into even and odd terms: $f(X)= f_E(X^2) + X\cdot f_O(X^2)$ The key step of the protocol derives a codeword for $f^*(X)=f_E(X) + \alpha\cdot f_O(X)$ from the codeword for $f(X)$, where $\alpha$ is a **folding challenge**. Let domain $D=<\omega>$, let $\{f(\omega^i)\}_{i=0}^{N-1}$ be the codeword for $f(X)$, $N$ be the length of the codeword. The split-and-fold output is the derived codeword $\{f^*(\omega^{2i})\}_{i=0}^{N/2-1}$. **Collinearity Checks**. The following three points fall on a straight line: - A: $(\omega^i,f(\omega^i))$ - B: $(\omega^{N/2+i},f(\omega^{N/2+i}))$ - C: $(\alpha,f^*(\omega^{2i}))$ **Why?** Define $q(X,Y)=f_E(Y) + X\cdot f_O(Y)$. For any $y\in D^*=<\omega^2>$, there exists $x\in D$ such that $y=x^2=(-x)^2$. Suppose $x=\omega^i$, then $-x=\omega^{N/2+i}$. - Note that $f(x)=q(x,y)$, which indicates that the point $(x,f(x))$ lies on the line $Y=q(X,y)$. - Note that $f(-x)=q(-x,y)$, which indicates that the point $(-x,f(-x))$ lies on the line $Y=q(X,y)$ - Note that $f^*(y)=q(\alpha,y)$, which indicates that the point $(\alpha,f^*(y))$ lies on the line $Y=q(X,y)$. which is equivalent to check the following equation: $f^*(\omega^{2i})=2^{-1}\cdot\big((1+\alpha\cdot \omega^{-i})\cdot f(\omega^{i}) + (1-\alpha\cdot \omega^{-i})\cdot f(-\omega^{i})\big)$. ### FFT Decomposition Please review my blog [Applications of FFT](https://hackmd.io/@YaoGalteland/r1Y5nJaQ1l#Folding). When $d=2$, it corresponds to the above split-and-fold case. <!-- comment ### Based on the FFT Recursion Require a specific finite field $\mathbb{F}_q$ such that $D= \{1,\omega,...,\omega^{n-1}\}\subseteq \mathbb{F}_q$, where $n=2^k|q-1$. - In the first round, the domain is $D_0=D =<2^k\text{-th roots of }1>$ - In the second round, the domain is $D_1=D =<2^{k-1}\text{-th roots of }1>$ - ... - In the last round, the domain is $D_k=D =<1>$ --> ### Merkle Tree from the Codeword for f(x) ![merkle_tree](https://i.imgur.com/eCKgiOx.png) ## References 1. [Anatomy of a STARK. Part 3: FRI](https://neptune.cash/learn/stark-anatomy/fri/) 2. [Reed Solomon Codes](https://dev.risczero.com/reference-docs/about-rs-codes) 3. [A summary on the FRI low degree test](https://eprint.iacr.org/2022/1216). 4. [Fast Reed-Solomon Interactive Oracle Proofs of Proximity](https://drops.dagstuhl.de/storage/00lipics/lipics-vol107-icalp2018/LIPIcs.ICALP.2018.14/LIPIcs.ICALP.2018.14.pdf)