# DEEP FRI
## Brief recap of FRI
In FRI, our starting point is an input function $$f^{(0)} : \mathcal{L}^{(0)} \rightarrow \mathbb{F}$$ where $$\mathbb{F}$$ is a finite field, $$\mathcal{L}^{(0)} \subset \mathbb{F}$$ is the evaluation domain. The FRI protocol is a two-phase protocol (the two phases are called COMMIT and QUERY) that convinces a verifier that $$f^{(0)}$$ is close to the Reed-Solomon code $$\mathsf{RS}\[\mathbb{F}, \mathcal{L}^{(0)}, \rho]$$.
### COMMIT phase:
1. For $$i = 0$$ to $$r - 1$$:
1. The verifier picks uniformly random $$\beta\_i \in \mathbb{F}$$ and sends it to the prover.
2. The prover sends a merkle proof of a function $$f^{(i+1)} : \mathcal{L}^{(i+1)} \rightarrow \mathbb{F}$$. (In the case of an honest prover, $$f^{(i+1)} = f^{(i)}*{\mathsf{even}} + \beta\_if^{(i)}*{\mathsf{odd}}$$).
2. The prover sends a value $$C \in \mathbb{F}\_q$$. (In the case of an honest prover, $$f^{(r)}$$ is the constant function with value = $$C$$).
### QUERY phase: (executed by the Verifier)
1. Repeat $$l$$ times:
1. Pick $$x\_0 \in \mathcal{L}^{(0)}$$ uniformly at random.
2. For $$i = 0$$ to $$r - 1$$:
1. Define $$x\_{i+1} \in \mathcal{L}^{(i+1)}$$ by $$x\_{i+1} = x\_i^2$$.
2. Query $$f^{(i)}$$ at $$x\_i$$ and $$-x\_i$$ to compute $$f^{(i)}*{\mathsf{even}}(x*{i+1})$$ and $$f^{(i)}*{\mathsf{odd}}(x*{i+1})$$.
3. Query $$f^{(i+1)}(x\_{i+1})$$ and if $$f^{(i)}*{\mathsf{even}}(x*{i+1}) + \beta\_i f^{(i)}*{\mathsf{odd}}(x*{i+1})\neq f^{(i+1)}(x\_{i+1})$$, then REJECT.
2. If $$f^{(r)}(x\_r) \neq C$$, then REJECT.
3. ACCEPT
### Properties
For $$V=\mathsf{RS}\[\mathbb{F}, D, \rho]$$ where $$D$$ is an FFT-friendly domain (subgroup of size $$n=2^k$$),[ BBHR17](https://eccc.weizmann.ac.il/report/2017/134) showed that FRI satisfies the following:
* Prover time $$\leq 6n$$, proof length $$\leq \frac{n}{3}$$
* Verifier time $$\leq 21 \log n$$, query complexity $$\leq 2 \log n$$
* Round complexity = $$\frac{\log n}{2}$$
* Soundness: Rejection probability of $$\delta$$-far words $$\approx\delta-o(1)$$ (which basically means it is a bit smaller but that is ignorable), for sufficiently small $$\delta < \delta\_0$$
* A word $$w$$ is said to be $$\delta$$-far from the code $$\mathcal{C}$$ if its Hamming distance from every codeword in $$\mathcal{C}$$ is at least $$\delta n$$)
* $$\delta\_0$$ is a positive constant that depends mainly on the code rate.
* In other words: Probability of rejecting $$\delta$$-far word is approximately $$\min(\delta, \delta\_0)$$.
### Understanding the Soundness
The soundness of a proximity testing protocol can be described by a soundness function $$s(\cdot)$$ that takes as input a proximity parameter $$\delta$$, and outputs the minimum rejection probability of the verifier, where this minimum is taken over all words that are $$\delta$$-far from the code.
$$
s(\delta)= \min{\forall w \text{ s.t }\Delta(w, \mathcal{C})\geq \delta: \mathsf{Pr}\_{rej}(w)}
$$
where $$Pr\_{rej}(w)$$ is the rejection probability of the word $$w$$.
$$
\min(\delta\_0, \delta) - o(1) \leq s(\delta)\leq \delta
$$
In the case of FRI soundness for a single test, an upper bound $$s(\delta) \leq \delta$$ is easy to establish but the more important part is establishing a lower bound. The initial analysis in[ BBHR18b](https://drops.dagstuhl.de/storage/00lipics/lipics-vol107-icalp2018/LIPIcs.ICALP.2018.14/LIPIcs.ICALP.2018.14.pdf) showed a nearly matching lower bound for sufficiently small values of $$\delta$$. In particular, the bound obtained there gives $$s(\delta) \geq \min{\delta,\delta\_0} - o(1)$$ where $$\delta\_0 \approx \frac{1-3 \rho}{4}$$.
For codes of $$ho \geq 1/3$$, $$\delta\_0$$ becomes non-positive so the FRI protocol becomes meaningless. Even when considering the ideal case of $$ho \rightarrow 0\Rightarrow \delta\_0 \rightarrow 1/4$$. This rather low soundness means that many tests must be applied in order to reach a target soundness error. For example, to achieve a target soundness error of $$2^{-\lambda}$$, then how many tests do we need?
$$
\text{min rejection probability } s(\delta)\geq 1/4 \Rightarrow \text{max acceptance probability after }l \text{ queries } \leq(1-\frac{1}{4})^l
$$
$$
(1-\frac{1}{4})^l \leq 2^{-\lambda}\Rightarrow l\cdot log\_2\frac{3}{4}\leq-\lambda\Rightarrow l \geq-\frac{\lambda}{\log\_2{\frac{3}{4}}}\approx2.4\lambda
$$
This shows that for 128-bit security, we need more than 300 queries. So to reduce this number, we need to have a better soundness lower bound.
## Improvements in the soundness lower bound
Following the limitations of FRI, there were some works that improved upon the $$\delta\_0$$.
1. Original FRI paper \[[BBHR17](https://eccc.weizmann.ac.il/report/2017/134/)]:
$$
\delta\_0 \approx \frac{1-3\rho}{4} \Rightarrow l \geq 2.4\lambda
$$
2. Worst-to-average case reduction \[[BKS18](https://doi.org/10.4230/)]:
$$
\delta\_0 \approx 1-\sqrt\[4]{\rho}\Rightarrow l\geq\frac{4\lambda}{\log\frac{1}{\rho}}
$$
3. Improved bound from Lemma 3.1 of \[BGKS20]:
$$
\delta\_0\approx 1-\sqrt\[3]{\rho}\Rightarrow l\geq \frac{3\lambda}{\log\frac{1}{\rho}}
$$
From the second result, we can see that when $$ho \rightarrow 0$$, $$\delta\_0 \rightarrow 1$$ which is a big improvement for the soundness of FRI. Building on top of that, Lemma 3.1 improved the number of tests required for $$\lambda$$ bit security from $$\frac{4\lambda}{\log\frac{1}{\rho}}$$ to $$\frac{3\lambda}{\log\frac{1}{\rho}}$$ which is \~25% less.
In addition, Lemma 3.1 is shown to be tight under a special case:
1. $$\mathbb{F}$$ is a binary field
2. $$ho = 1/8$$ precisely
3. Evaluation domain $$D$$ equals all of $$\mathbb{F}$$
Therefore, we needed something different to break this soundness barrier and the DEEP (Domain Extension for Eliminating Pretenders) method was introduced.
## DEEP FRI
First, what do we mean by “pretenders”? Let's say a malicious prover has a very large degree polynomial that agrees on all of $$\mathcal{L}^{(0)}$$ with a low-degree polynomial. Then how does the verifier differentiate between such pretenders and an actual low-degree polynomial? If we sample $$x\_0\in \mathcal{L}^{(0)}$$, we won't find any discrepancies. Therefore, we attempt to sample outside the evaluation domain using quotient functions.
### Quotienting
If $$f^{(0)}$$ is indeed evaluations of low-degree polynomial $$P(X)$$ on $$D$$ then verifier should be able to query $$P$$ on an arbitrary $$z\in\mathbb{F}$$. Suppose the prover claims $$P(z)=a$$, then $$P(X) - a$$ is divisible by $$X-z$$ so let's denote it as:
$$
\mathsf{QUOTIENT}(P, z, a) = \frac{P(X) - a}{X-z}
$$
### COMMIT phase:
1. For $$i = 0$$ to $$r - 1$$:
1. The verifier picks uniformly random $$\beta\_i, z\_i \in \mathbb{F}$$.
2. The prover sends $$f^{(i)}*{even}(z\_i) + \beta\_i f^{(i)}*{odd}(z\_i)=a$$.
3. The prover sends a merkle proof of a function $$f^{(i+1)} : L^{(i+1)} \rightarrow \mathbb{F}$$. (In the case of an honest prover, $$f^{(i+1)}(X)=\mathsf{QUOTIENT}(f^{(i)}*{\mathsf{even}}(X) + \beta\_i f^{(i)}*{\mathsf{odd}}(X), z\_i, a))$$.
2. The prover sends a value $$C \in \mathbb{F}\_q$$. (In the case of an honest prover, $$f^{(r)}$$ is the constant function with value = $$C$$).
### QUERY phase: (executed by the Verifier)
1. Repeat $$l$$ times:
1. Pick $$x\_0 \in \mathcal{L}^{(0)}$$ uniformly at random.
2. For $$i = 0$$ to $$r - 1$$:
1. Define $$x\_{i+1} \in \mathcal{L}^{(i+1)}$$ by $$x\_{i+1} = x\_i^2$$.
2. Query $$f^{(i)}$$ at $$x\_i$$ and $$-x\_i$$ to compute $$f^{(i)}*{\mathsf{odd}}(x*{i+1})$$ and $$f^{(i)}*{\mathsf{even}}(x*{i+1})$$.
3. If $$\frac{(f^{(i)}*{\mathsf{even}}(x*{i+1}) + \beta\_i f^{(i)}*{\mathsf{odd}}(x*{i+1})) - a}{(x\_{i+1} - z\_i)}\neq f^{(i+1)}(x\_{i+1})$$, then REJECT.
2. If $$f^{(r)}(x\_r) \neq C$$, then REJECT.
3. ACCEPT
### Resulting soundness
As a result of applying the DEEP technique, the soundness claim was improved to:
$$
\delta\_0 \approx 1-\sqrt{\rho}\Rightarrow l\geq \frac{2\lambda}{\log\frac{1}{\rho}}
$$
## Final Remarks
The special case for tightness of the lower bound in Lemma 3.1 is something we can ignore. If we assume that the length of the code $$n$$ is much smaller than the size of the field $$q$$ (which is the case for practical STARK implementations), this bound can be improved significantly. Investigating this further, the authors of[ BCIKS2023](https://dl.acm.org/doi/10.1145/3614423) figured that when working with RS code over a sufficiently large field—polynomially large in the code’s blocklength—and when $$\delta \in (0, 1 - \sqrt{\rho})$$, the average-case distance is almost the same as the worst-case distance. With this, they claim that FRI can achieve the same soundness as DEEP FRI without its added prover complexities. However, the out-of-domain sampling method introduced in this paper is still used widely to improve the soundness of the underlying protocol (for example STIR).
## References:
| BBHR17 | Eli Ben-Sasson, Iddo Bentov, Ynon Horesh, and Michael Riabzev. 2018. Fast Reed-Solomon interactive oracle proofs of proximity. In Proceedings of the 45th International Colloquium on Automata, Languages, and Programming (ICALP 2018). Retrieved from[ https://eccc.weizmann.ac.il/report/2017/134](https://eccc.weizmann.ac.il/report/2017/134) |
| --------- | ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------- |
| BBHR18b | Eli Ben-Sasson, Iddo Bentov, Ynon Horesh, and Michael Riabzev. Fast Reed-Solomon Interactive Oracle Proofs of Proximity. In Proceedings of the 45th International Colloquium on Automata, Languages, and Programming (ICALP 2018). Retreived from
|
| BKS18 | Eli Ben-Sasson, Swastik Kopparty, and Shubhangi Saraf. 2018. Worst-case to average case reductions for the distance to a code. In Proceedings of the 33rd Computational Complexity Conference. 24:1–24:23. DOI: LIPIcs.CCC.2018.24 |
| BGKS20 | Eli Ben-Sasson, Lior Goldberg, Swastik Kopparty, and Shubhangi Saraf. 2020. DEEP-FRI: Sampling outside the box improves soundness. In Proceedings of the 11th Innovations in Theoretical Computer Science Conference (LIPIcs), Thomas Vidick (Ed.), Vol. 151. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 5:1–5:32. DOI:. ITCS.2020.5 |
| BCIKS2023 | Eli Ben-Sasson, Dan Carmon, Yuval Ishai, Swastik Kopparty, and Shubhangi Saraf. 2023. Proximity Gaps for Reed–Solomon Codes. J. ACM 70, 5, Article 31 (October 2023), 57 pages.[ https://doi.org/10.1145/3614423](https://doi.org/10.1145/3614423) |
> Written by [Batzorig Zorigoo](mailto:undefined) of Fractalyze
---
# Agent Instructions: Querying This Documentation
If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.
Perform an HTTP GET request on the current page URL with the `ask` query parameter:
```
GET https://fractalyze.gitbook.io/intro/zk/stark/deep-fri.md?ask=
```
The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.
Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.