# Translating FRI Soundness to Unique Decoding Radius
Version 2 -- January 2024

This note aims to articulate the soundness of the batched FRI protocol in the unique decoding radius. We begin with a naive approach and will worry about details later.

### Setup
The Prover runs *BATCHED FRI* on $f_1,\ldots,f_t$, where $f_i$ are polynomials over $\mathbb{F}_q$.

We use a single random element for batching, which we denote $z_B$, and we write $f^{(0)}$ to refer to the result of batching $f_1,\ldots,f_t$

We use a single random element for folding in each round of *FRI COMMIT*. We denote these as $z_0,\ldots,z_{i-1}$.

We assume $r$ rounds of *FRI COMMIT*, indexed $1,...,r$. In Round $i$ of *FRI COMMIT*, the Prover uses Verifier randomness $z_{i-1}$ to construct $f^{(i)}$.

### Assumption
We assume the inter-leaved distance of $f_1,\ldots,f_t$ to $V$ is large, where $V$ is the set of valid Reed-Solomon codewords.[^interleaved]

### Claim
We want to show that with $s$ queries, the Verifier is very unlikely to accept the result of *BATCHED FRI*.

### Sketch
We'll be doing $s$ queries, and we hope that this will be sufficient to reach 100 bits of security.

We define $\epsilon_\mathsf{Q}$ as the likelihood the Verifier accepts a single invocation of *FRI QUERY*. As long as $\epsilon_\mathsf{Q}$ is small enough, $s$ queries will be sufficient to reach 100 bits.

Then, we just need to bound the probability that $\epsilon_\mathsf{Q}$ is too large.

### Bounding the probability that $\epsilon_\mathsf{Q}$ is large
We want to show that it's very unlikely that $\epsilon_\mathsf{Q}$ is large.

The only reason $\epsilon_\mathsf{Q}$ will be large is if we get a "bad randomness" during the initial batching or during one of the rounds of *FRI COMMIT*. This is expressed formally in Equation (8.5) of the Proximity Gaps paper.[^8.5]:

We use $E^{(0)}$ to denote the probability of "bad batching" and $E^{(i)}$ to denote the probability of "bad folding" in Round $i$ for $i=1,...,r$.

### Bounding $E^{(0)}$
$E^{(0)}$ is the probability of "bad randomness" during *FRI BATCHING*.

We bound $E^{(0)}$ by $\frac{|D^{(0)}|t}{q}$, where
- $|D^{(0)}|$ is the size of the initial FRI domain,
- $t$ is the number of polynomials being batched, and
- $q$ is the size of the field.

This is a direct application of Theorem 4.1 in the Proximity Gaps paper.

### Bounding $E^{(i)}$ for $i=1,...,n$
$E^{(i)}$ is the probability of "bad randomness" in Round $i$ of *FRI COMMIT*.

In Round $i$, we split $f^{(i-1)}$ into $l^{(i-1)}$ pieces and we combine them using $z^{(0)}$.

We bound $E^{(i)}$ by $\frac{\left(\left|D^{(0)}\right|+1\right)\left(l^{(i-1)}-1\right)}{q}$.[^folding_error]

We continue using the assumption that the FRI folding factor is equal to $l$ at all rounds. This gives the simpler bound $\frac{\left(\left|D^{(0)}\right|+1\right)\left(l-1\right)}{q}$.

### The Full FRI Commit Error
Combining the bounds from the previous section, we can write the following bound on the error bound $\epsilon_C$.
$$\epsilon_C=E^{(0)}+E^{(1)}+...+E^{(r)}\leq\frac{|D^{(0)}|t}{q}+
\frac{\left(\left|D^{(0)}\right|+1\right)\left(l-1\right)}{q}\cdot r$$
$$ < \frac{(|D^{(0)}|+1)t}{q}+
\frac{\left(\left|D^{(0)}\right|+1\right)\left(l-1\right)}{q}\cdot r$$
$$ = \frac{\left(\left|D^{(0)}\right|+1\right)\left(t+(l-1)\cdot r\right)}{q}$$

To write the analogue of Theorem 8.3 from Proximity Gaps, we replace $\epsilon_\mathsf{C}$ with this expression.

### Next Steps
- It remains to integrate this into the context of a DEEP-ALI+FRI soundness argument, as in Theorem 8 from the *Summary on the FRI Low-Degree Test.* In particular, the details around $m+$ and $\rho+$ have yet to be integrated. The numerical impact here will be minimal.
- A more formal analysis of what's presented here is available in an unpublished manuscript written by Al from Polygon Miden.

[^interleaved]: In other words, we assume the correlated agreement density of $F=\text{span}{(f_1,...,f_t)}$ to $V$ is not too large. 

[^3]: Here the $l^{(i)}-1$ term is the soundness degradation for parametric batching of $l^{(i)}$ functions.

[^8.5]: 

[^folding_error]: For $i=1,...,n$, the Proximity Gap paper uses Theorem 7.4 to bound $E^{(i)}$, resulting in a bound of  </br>We make the following observations that support translating this result into the unique decoding regime. </br> $\hspace{1pt} \bullet \hspace{6pt}$ The `max()` in Theorem 7.4 turns into the sum in the expression for $E^{(i)}$. In the unique decoding regime, the first term of the `max()` argument simplifies to $\frac{n}{q}$, which is strictly less than the second term in the `max()` argument. The absence of $\epsilon^{(i)}$ in our analysis follows from this observation. </br> $\bullet \hspace{6pt}$ The $\frac{2m+1}{\sqrt{p}}$ term is not necessary in the unique decoding radius. We refer readers to Section 7.1 of the Proximity Gaps paper for details on this point. </br> $\bullet \hspace{6pt}$ The $l^{(i)}-1$ term counts the soundness degradation for combining $l^{(i)}$ polynomials. </br> $\bullet \hspace{6pt}$ The term $|D^{(0)}|$ comes from the product of $|D^{(0)}|=|D^{(i)}|\cdot M_i$. We refer readers to Section 8.3 of the Proximity Gaps paper for details on this point. </br>