# Practical notes on the FRI low degree test

## TL;DR
- FRI is a protocol that demonstrates proximity for a linear code to a low-degree polynomial.
- FRI is a round-by-round interactive protocol between a prover and a verifier.
- The prover commits to a Reed-Solomon codeword that evaluates to some low-degree polynomial.
- The verifier makes oracle queries to the alleged codeword at random points and verifies that the result matches the given commitment. If sufficient queries succeed, the verifier is convinced that the committed codeword will pass the low-degree test.

## Overview
***FRI** - **F**ast **R**eed-Solomon **I**OP of Proximity* is a low degree test that allows a **Prover** committing to a low-degree polynomial demonstrating to a **Verifier** that the polynomial has a bounded degree $d$, without revealing the polynomial.

More specifically, the FRI protocol shows an alleged codeword being *close* to a low-degree polynomial $h(x)$ without revealing the entire codeword itself. The values in the codeword are evaluations of $h(x)$ over a fixed size domain $\Omega\subseteq \mathbb{F}$; $\Omega$ is a multiplicative subgroup of a finite field $\mathbb{F_p}$, of order $p$. The degree of the polynomial lasts below a certain threshold $d$.

> The concept of *closeness* has a precise mathematical definition and is parameterized by a *proximity parameter* $0\leq \delta<1$. The smaller is $\delta$, the closer $h(X)$ is to the polynomial (as guaranteed by FRI).

FRI can be turned into a polynomial commitment scheme in which the prover commits to $h(x)$, and the verifier can open any point $z$ verifying that $h(z) = y$ without equivocation.

The following diagram summarises the process of FRI. The next sections provide a detailed explanation of each step.


### Important concepts
- **Codeword**: A codeword is a vector of symbols generated with an error-correcting code. In the FRI IOPP, the prover commits to the codeword and sends the commitment to the verifier; the verifier makes random queries to read specific positions.
- FRI uses Reed-Solomon code as the error-correcting protocol.
- Codeword values represent evaluations of a low-degree polynomial in a list of elements of a finite domain $\Omega\in\mathbb{F_p}$.
- FRI codewords are evaluations for a polynomial of low degree $d-1$.
- The size of $\Omega$ is determined by a factor $\rho^{-1}$ known as the *blowup factor,* multiplied by the codeword’s polynomial degree $d$, s.t. $|\Omega| = (\rho^{-1}*d)$.
- The *blowup* factor is the reciprocal of the code’s rate $\rho$ (e.g. for a code rate $\rho=1/2$ that ensures one parity chunk of data for each original chunk, the *blowup factor* is $2$).
- The domain size $|\Omega| = (\rho^{-1}*d)$ also determines the [$n$-th roots of unity](https://en.wikipedia.org/wiki/Root_of_unity) used to evaluate the polynomial.

- **Folding**: Iterative protocol that reduces the number of polynomial evaluations (codeword) at multiple points into an evaluation of a related polynomial at fewer points (folded codeword). This is done recursively, combining evaluations from previous rounds, ultimately reducing the problem to a small set of points, which is easier to verify.
- The reduction repeats until the final value is of trivial size -- easy to verify.
- For a polynomial of degree $d$ there are at least $log(d)$ rounds of FRI.
- The size of the codeword is (at least) halved.
- A *folding factor* determines the reduction for each folding round[^1].
- The degree bound $d$ of the claimed polynomial decreases at the folding factor ratio.

[^1]: In this document we consider a folding factor of 2.

- **Algebraic considerations**: FRI supports any $2^k$ value for the $n$-th roots of unity, up to $2^{32}$ (the finite field works over $p=2^{64}-2^{32}+1$, therefore $p-1$ is divisible by $2^{32}$). This constraint ensures that, for each chose $n$-th root of unity, there are precisely $n$ representative elements $\mod p$.

- **Merkle tree**: Make sure to be familiar with terms *Merkle leaves,* *Merkle root*, and *Merkle Path* (or authentication path, or Merkle proof -- we use them interchangeably).

## How does FRI work?
The FRI protocol consists of two phases:

1. ***Commit phase*** (or *folding* phase): the prover commits to the folded codewords and sends their Merkle roots to the verifier;
2. ***Query phase:*** the verifier requests openings of random elements $x_i\in\Omega$ from the original codeword, and verifies that the folding has been done correctly.

**Important:** The verifier does not know the function $h(x)$; he receives a Merkle commitment to the polynomial evaluations, and their openings at specific positions.

### Commit Phase

In each folding phase, the prover reduces the length of the codeword, and thus the degree of the polynomial, by folding factor; in this post, we assume a folding factor of `2`. After $log(d)$ phases ($d$ is the degree of the original polynomial), the resulting codeword is equal to a constant value (i.e. polynomial of degree `0`).

**Terminology**

- $h(x)$ a polynomial of low-degree $d$.
- Evaluation domain $\Omega\in\mathbb{F_p}\setminus\{0\}$; there exists $\omega\in\Omega$, a primitive $n$-th root of unity[^2], forming a cyclic multiplicative group $\{\omega^0, \omega^1, \omega^2, .., \omega^{n-1}\}$ of size $n$, such that $|\Omega| = n$.
- $p=2^{64} - 2^{32} +1$, is divisible by $n$. In particular, FRI supports any domain size $n$ power of $2$, up to $2^{32}$.
- The domain size is proportional to the blowup factor and the polynomial degree, in particular $n=\rho^{-1}*d$, where $\rho^{-1}$ is the blowup factor (the inverse of the rate of Reed Solomon code).

> The length of the domain also represents the length of the codeword.

[^2]: The element $\omega$ generates all the $n$-th roots of unity by its powers, and $\omega^n=1\mod p$ while $\omega^k\neq1$ for any $0<k<n$.

The protocol proceeds in phases, that we briefly describe below.

#### Phase 0: From raw data to **$h(x)$**

Raw data (byte array) interpolated into a low degree polynomial using the [Fast Fourier Transform (FFT)](https://decentralizedthoughts.github.io/2023-09-01-FFT/).

> The [Lagrange Polynomial Interpolation](https://en.wikipedia.org/wiki/Lagrange_polynomial) is another technique to achieve this, however it is computationally inefficient.

*How to compute the polynomial $h(x)$ from raw data is out of the scope of this document.*

#### Phase 1: Commit to original codeword

Given the function $h(x)$ of low degree $d$, the **codeword** is the array of evaluations of $h$ over the values in $\Omega$, i.e. $[h(\omega^j)_{j\in\Omega}]$.

The prover computes a Merkle tree where the leaves correspond to the elements in $[h(\omega^j)_{j\in\Omega}]$. The root of this Merkle tree represents the commitment to the polynomial $h(x)$, which we call $root = com(h(x)_{\Omega})$.

#### Phase 2: Folding

Prover and verifier engage with an interactive, multi-round protocol that reduces the original polynomial to a constant sized polynomial of degree $d=0$.

##### Compute the folding function

We need some tricks to compute the folding function $h_{fold}(x)$. The original polynomial $h(x)$ is divided into **even** and **odd** parts. Then use these parts to generate the folded function with halved degree $d/2$. The obtained polynomial will still include all original polynomial points over halved evaluations domain $\Omega/2$. The following equivalence holds:

$$
h(x) = e(x^2) + x*o(x^2)
$$

Therefore, for any root of unity $z\in\Omega/2$ we have $z=x^2$ and a random value $r$, the following random linear combination holds:
$$
h_{fold}(z) = e(z) + r*o(z)
$$

---
Folding repeats $k=log(d)+1$ times. We indicate each folding layer with an index $i=\{1,2, .., k\}$. For each layer the following actions happen:

1. **[Verifier] Send a random value $v_i\in\mathbb{F_p}$ to the prover**
2. **[Prover] Compute the folded polynomial $h_{i}(x)$**, where $i$ indicates the $i$-th folding layer, and $z=x^{2i}$ is the $n/2^i$-th root of unity:

$$
h_{i}(z) = e_{i-1}(z) + v_i*o_{i-1}(z)
$$

$e_{i-1}(z)$ is the *even* part of polynomial $h_{i-1}(x)$, with halved degree $d/2^i$.
$o_{i-1}(z)$ is the *odd* part of polynomial $h_{i-1}(x)$, with halved degree $d/2^i$.

3. **[Prover] Commit to $h_i(x)$**
1. Compute $h_i(x)$ evaluations. The length of the evaluation domain is halved to $\Omega/2^i$, such that the elements in $n/2$-th roots of unity are those in the multiplicative group $\{(\omega^{2i})^0, (\omega^{2i})^1, …, (\omega^{2i})^{n/2^i-1}\}_{\Omega/2^i}$.
2. Commit to $h_i(x)$. Compute the Merkle root from the polynomial evaluations of $h_i(x)$ in $\Omega/2^i$, s.t. $root_i = com((h_i(x))_{\Omega/2^i}$.

> In FRI we pick $n=|\Omega|$ as power of $2$, such that $n$ divides $p-1$ in $\mathbb{F_p}$. Therefore for any $x$, $n$-th root of unity, then $x^2$ is an $n/2$-th root of unity, with $x^2\in\Omega/2$.

4. **[Prover] Send commitment $root_i$ to the verifier**
When folding layer $i=k$:
- The polynomial degree of $h_k(x)$ is $d/2^k = d/2^{log(d)+1}=1/2$ (floor is 0)
- $h_k(x) = c$, is a constant value.
- The prover sends $c$ to the verifier.

### Query Phase

In this phase, the verifier checks that the prover computed FRI properly. To do so, he picks a random value $j$ and requests the evaluation $h(\omega^j)_{j\in\Omega}$ to the prover, for the $n$-th root of unity $\omega^j$.

For each query:

1. **[Verifier] Send a random $j$ to the prover, s.t. $\omega^j\in\Omega$**
2. **[Prover] Compute evaluations for each folding layer $i=\{1, .., k-1\}$:**
1. Compute $h_0(\omega^{j})$ and its Merkle proof in $MP_0(h_0(\omega^{j})) \in root_0$
2. Compute $h_0(-\omega^{j})$ and its Merkle proof in $MP_0(h_0(-\omega^{j})) \in root_0$
3. Compute $h_i((\omega^{j})^{2i})$ and its Merkle proof in $MP_i(h_i((\omega^{j})^{2i})) \in root_i$
4. Compute $h_i((-\omega^{j})^{2i})$ and its Merkle proof in $MP_i(h_i((-\omega^{j})^{2i})) \in root_i$

3. **[Prover] Send openings to verifier for each folding layer:**
1. $[h_0(\omega^j)] + [h_i((\omega^{j})^{2i})]_{i\in\{1, .., (k-1)\}}$ and $[h_0(-\omega^j)]+[h_i((-\omega^{j})^{2i})]_{i\in\{1, .., (k-1)\}}$
2. $[MP_0(h_0(\omega^j))]+[MP_i(h_i((\omega^{j})^{2i}))]_{i\in\{1, .. (k-1)\}}$ and $[MP_0(h_0(-\omega^j))]+[MP_i(h_i((-\omega^{j})^{2i}))]_{i\in\{1, .. (k-1)\}}$
4. **[Verifier] Check the received openings against the commitments $([root_i]_{i\in\{1, .., (k-1)\}}, c)$**
1. Verify first folding:
- Check $MP_0(h_0(\omega^j))$ in $root_0$
- Check $MP_0(h_0(-\omega^j))$ in $root_0$
- Compute first folding $h_1((\omega^j)^2)$ with $h_0(\omega^j)$ and $h_0(-\omega^j)$ and check consistency with received value

2. For each folding layer $i=\{2, .., k-1\}$:
- Compute folded value $h_i((\omega^j)^{2i})$ with $h_{i-1}((\omega^j)^{2(i-1)})$ and $h_{i-1}((-\omega^j)^{2(i-1)})$
- Derive $h_i((-\omega^j)^{2i})$;
- Check that $h_i((\omega^j)^{2i})$ is consistent with the received value
- Check $MP_i(h_i((\omega^j)^{2i}))$ and $MP_i(h_i((-\omega^j)^{2i}))$ wrt $root_i$;
3. Verify last folding with $i=k$:
- Compute the constant value $c$ with $h_{k-1}((\omega^j)^{2(k-1)})$ and $h_{k-1}((-\omega^j)^{2(k-1)})$
- Check that the value is consistent with $c$.

> At this stage we need to explain how the verifier computes the folding without knowing $h(x) = e(x^2) + x*o(x^2)$.
>
> To obtain a folded value for $h_{fold}(z)$ at folding layer $i$, where $z\in\Omega/2^i$ root of unity, we use the linear combination of the polynomial $h(x)$ evaluated at the square root of $z$ and $-z$ (i.e. $\pm\sqrt{z}$), recalling that $z=x^2$ with $x$ root of unity of previous folding layer
>
>$$
>h_{fold}(z) = \frac{(r+x)}{2x}*h(x) + \frac{(r-x)}>{-2x}*h(-x)
>$$
>
>Therefore, if the verifier knows the evaluations $h(x)$ and $h(-x)$ can always derive the folded value $h_{fold}(z)$, without knowing the entire polynomial $h(x)$.

#### How many queries?

The query phase must include a sufficient number of queires[^3], such that the verifier gets convinced that polynomial $h(x)$ is close to a function of low-degree $d$.

We consider the parameter $\lambda$ representing the bits of security that one aims to achieve, in particular:

$$
\lambda\geq min\{log(\rho^{-1})*k, log(|\mathbb{F}|) \} -1
$$

[^3]: One single query gives $log(\rho^{-1})$ bits of security, thus $\lambda/log(\rho^{-1})$ queries give $\lambda$ bits of security.

that represent the logarithm of the amount of work that a cheating prover would have to do to convince the verifier about a false claim in FRI.

## Appendix A - FRI sequence diagram

The following diagram summarises the steps of the FRI protocol.

**Note**: terms in the diagram are aligned with this document, apart from the evaluation domain $\Omega$ represented by the symbol $D$.


([source](https://sequencediagram.org/index.html#initialData=C4S2BsFMAIDECUCS0AKAnA9hgZgKHwIYDGwGa0AROhgG6RoXQEDOquxp5FAavSNiHqMW0bvgB2GYDFr1UALmgALABQAPAJQAaOAB5mIAF6R5ADgB8AB10B6A8fM6AIrknTos8t0UATHbH0jEwtrOyDHaBcAIww1aChsYA9sBQBhDABbSwBXdxsbTClA4zNzAAZbe0hzaABeaCJMlVVNDQAdcWwyaEhiJWg4kHFI-NwUAFpzb3zC4GLg8srw0Zi4tBAAcyUknFFFFBAiAGtoNAJxH0zofJp50oqwh3zobEwMvSrS0KrzXG5JlDyG53CwPH6jXAAYmg6QyGTA0EsShYkFw4CwlmgkPAm22GzQkEgwwQyEacIRSJRL26IFqAG8AIw6AB0zK0RwAvrhVvFIIlkgoAFSC2E5dxdcA+IYbYXyDoM5mRPh0aCGaBDEYAJgAeiBoMxmcBFYZamptZqQB1NYqlCDzCAlg4VIYNLVIHaQOMGY7qs6NNAANTQFS3T4WT3ex7VDQqDAer0+8x+9riYWw+HAWUdWYexN1BpNW1h+2J5PU8i9Ij9NUapw2HUgMaTbynLBzYsOqO-HnrLY7FItg7HU7nS7vYEdxPPV5XALF77hP4AxQToKlTvgmxQgAFABkWEkJVLxBt4gQAJ70XD4jDZTH8dX5o7c2K8-m7QFpjDiZjAc5JSwMHAc9JHhAhwGFaAAHcwH6Hx621E56gZDoizXCwjkTN07SOBMuz9QNg1DdDzFwyMfhjOMOzwn4y3qIgmymRQ0JKDCsIYokfFwTj8GhABFbJ6HPVBkWYVEe1xfs9lQQ4TgIEcLiuKCXjeSIl3MQEoJfOIEikz8RUyMUYAENBfzPS8KxocDsgIUBv1YGDgH6ZTR2gcYoOFDoAG1VCg7RlBUdyNAAXQ6DovyyXIYAAWXoI4oERQpsE88QvOilA7TBcJmhUPz-PSzLS1UIKQuvTA7yxHE+yicBBLgJBoAAR0EtBhMpMTg1pRkWTZaAyI5DRtLfPT5Aioyeis2rbJAezoNg6CmAuNyPMFbyWIWcjsrNTV-NZHR1vXGjsqg7UvM1FQIxCkK1rtTanW23beoO8MjqddzTvOy7guu8RwoMyL3FitB4pgSwkuYFK0oy4s7t9Z7zFhpM8p6nQCuoxHmnjDGTrOi6vSun6oduorifwkqUegNGSIjEn0dLd7ca+jRSomJifNy-z4Yxh6Kfhmn8Jxz78e+0LUuKvz9tJ2ieegPblCx+nBbxhkrtF7yqdYxZ8N85mKY1hZ+dovnXt9JWmcJ-X7iKwLkdl3rLZejHjYxhmhZV77SokvsBW8NMlEgYcMEsIlpQh1bxAVGF-eHB2taNjn-SgtAkhzYssocK1FVSaOTlj9O4Zt5noOT1sijTxMwtTEUc5eEBTKScALzkI9pRSyPRSi+WYdLE6drmpzoEmwTWHZiWAqC0XrSjgOTkaH8QF-IkiGExz+icmACSISAQDoHwu5I7HzUGqFp8D4PxFD6AagZNEMWgAArepNR0ABmCmyKG3tth90bq5n6lJSt3Du3Qynd4b3x7uae+id5pD0gCPcBJskYfRUPfYWnMbYoLQe7H6U9s7-zngYRe4hl79zXv7U4Adt6733prCBAsoEphflnGusd6HxxOioTU0Ci6uTYdbd6XCeGJxLqnEi7DFzcQuLxaA+4zItxPOZK8Xtv67F9n-YchC-ziAAkBECmQQDgTblnUB7h4aYS7GQwe1l4HQB8jhJBuUUFkSuvtTBuMXEi0zqfWe9kF7SBIcJcx7EpFcX+BpeQABBIgW9LDABsPASA98A7ACAA))

## Appendix B - Replace the negative root of unity

Sometimes we do not want to deal with negative values for roots of unity. So considering the $n$-th root of unity $\omega\in\Omega$, and since $\omega$ is in $n=|\Omega|$, we have

$$
\omega^{n/2}=-1
$$

Therefore, we can compute

$$
h(-\omega^j)=h(\omega^{n/2+j})
$$

for each $\omega^j\in\Omega$.

## Resources
- [FRI paper](https://drops.dagstuhl.de/storage/00lipics/lipics-vol107-icalp2018/LIPIcs.ICALP.2018.14/LIPIcs.ICALP.2018.14.pdf) and [soundness analysis for FRI](https://eccc.weizmann.ac.il/report/2020/083/) from Eli-Ben Sasson et al.
- [Summary on the FRI low degree test](https://eprint.iacr.org/2022/1216.pdf) from Ulrich Haböck
- [Comparison of FRI vs. Ligero proof sizes](https://people.cs.georgetown.edu/jthaler/Ligero-FRI-proof-size.pdf) from Justin Thaler
- [Anatomy of a STARK, part 3: FRI](https://aszepieniec.github.io/stark-anatomy/fri)
- Vitalik's [notes on FRI](https://vitalik.eth.limo/general/2017/11/22/starks_part_2.html)
- ZKP MOOC: FRI-based polynomial commitments ([video](https://www.youtube.com/watch?v=A3edAQDPnDY))