Introduction

In this post we will take a look at the Fast Reed-Solomon IOP (FRI) proximity test, which enables an untrusted prover to convince a verifier that a committed vector is close to a Reed-Solomon codeword with communication only poly-logarithmic in the dimension of the code. This is readily used to construct practically efficient zkSNARKs from just cryptographic hash functions (rather random oracles), without the need for a trusted setup.

The reader is assumed to know the basics of group theory and finite fields; without which FRI will seem like a sequence of unmotivated magic equations. The reader is also assumed to be familiar with the basics of interactive oracle proofs (IOPs) and the overall goal/idea of proximity testing. We won’t spend time on the basics of IOPs, but though-out the post the model will always be that of IOPs: the prover can send (long) oracles/messages to the verifier, who can read the oracles/message at any time and at any index.

The original papers on FRI spend relatively little time motivating the construction and instead substantial amount of time on the soundness analysis, understandably so. Additionally, despite the relative simplicity of FRI (as we shall see), soundness is actually surprisingly involved to prove formally, particularly beyond the unique decoding radius.

In this post the focus is different: we will focus on the intuition behind the construction, how to come up with the “folding procedure”, illustrations and why you would intuitively expect the construction to work. In other words, how would you come up with the FRI construction? How would you generalize it?

Personal Note: Some of the intuition relayed in the post was initially provided to me by Daniel Escudero in personal correspondence. I believe it nicely explains the intuition for why FRI works/looks the way it does, how it is actually quite natural and explains underlying algebraic structure required for FRI. I would like to share this with people trying to understand FRI.

Overview of The Fast Reed-Solomon IOP

The Fast Reed-Solomon IOP (FRI) is a proximity test for the Reed-Solomon Code, i.e. the “yes” language of strings which are always accepted is the Reed-Solomon code:

\[ \begin{align*} \language_\texttt{YES}^{(1)} &\coloneqq \mathsf{RS}[\FF, L^{(1)}, d^{(1)}] \\ &= \left\{ \hat{f} \in \FF^n \mid \exists f \in \FF[X] \text{ st. } \begin{matrix} \deg(f) < d^{(1)} \\ \hat{f} = f(L^{(1)}) \end{matrix} \right\} \end{align*} \]

In plain english: vectors of dimension \( n \) which are evaluations of polynomials of degree less than \( d^{(1)} \). The goal of FRI is to distinguish \( \language_\texttt{YES}^{(1)} \), corresponding to honest behavior, from all vectors in \( \FF^n \) which are far from all Reed-Solomon codewords, i.e. the relative Hamming distance is greater than some \( \epsilon \):

\[ \language_\texttt{NO}^{(1)} \coloneqq \left\{ \hat{f} \in \FF^n \mid \forall \hat{g} \in \mathsf{RS}[\FF, L^{(1)}, d^{(1)}] . \delta(\hat{f}, \hat{g}) > \epsilon \right\} \]

Intuitively, this is useful because if \( \epsilon \) is smaller than the unique decoding radius of the Reed-Solomon code, then we can talk uniquely about the “message” encoded in \( \hat{f} \) whenever the verifier accepts, meaning \( \hat{f} \notin \language_\texttt{NO}^{(1)} \). When constructing SNARKs this allows the knowledge extractor to recover a unique polynomial \( f(X) \) of low-degree \( d^{(1)} \).

Promise Problems: Note we do not care about the case where \( \hat{f} \notin \language_\texttt{YES}^{(1)} \cup \language_\texttt{NO}^{(1)} \), namely what happens when \( \hat{f} \) is close to a Reed-Solomon codeword but not a codeword itself, notably: there may be some way to pass the test for \( \hat{f} \) that is not the honest behavior in the protocol. In complexity theory, this generalizations of decision problems is called promise problems and \( \language_\texttt{YES}^{(1)} \cup \language_\texttt{NO}^{(1)} \) is called the promise.

FRI works towards this goal by successively reducing \(\language_\texttt{YES}^{(1)}/\language_\texttt{NO}^{(1)}\) to smaller languages \(\language_\texttt{YES}^{(2)}/\language_\texttt{NO}^{(2)}\) respectively. We will later spend considerable time on this reduction, since it is the core of FRI, but for now let “\( c \)” be a constant determining the “compression factor” and let \( d^{(2)} = d^{(1)} / c \) and \( L^{(2)} \) will be an evaluation domain of size \( |L^{(2)}| = |L^{(1)}| / c = n / c \):

\[ \begin{align*} \language_\texttt{YES}^{(2)} &\coloneqq \mathsf{RS}[\FF, L^{(2)}, d^{(2)}] \\ &= \left\{ \hat{f} \in \FF^{n / c} \mid \exists f \in \FF[X] \text{ st. } \begin{matrix} \deg(f) < d^{(2)} \\ \hat{f} = f(L^{(2)}) \end{matrix} \right\} \end{align*} \]

\[ \language_\texttt{NO}^{(2)} \coloneqq \left\{ \hat{f} \in \FF^{n / c} \mid \forall \hat{g} \in \mathsf{RS}[\FF, L^{(2)}, d^{(2)}] . \delta(\hat{f}, \hat{g}) > \epsilon \right\} \]

The core objective in FRI is probabilistically reducing \( \hat{f}^{(1)} \in \FF^n \) to \( \hat{f}^{(2)} \in \FF^{n / c} \) such that:

• \( \hat{f}^{(1)} \in \language_\texttt{YES}^{(1)} \implies \hat{f}^{(2)} \in \language_\texttt{YES}^{(2)} \).
• \( \hat{f}^{(1)} \in \language_\texttt{NO}^{(1)} \implies \hat{f}^{(2)} \in \language_\texttt{NO}^{(2)} \).
  (except with some small probability).

In order words: if you start with a codeword, you end up with a codeword, on the other hand if you start with something far from a codeword, you end up with something far from a codeword; except with with some small/negligible probability.

After repeating this procedure \( \mathsf{rounds} = \log_c(d^{(1)}) \) times we will have reduced all the way down to code of some constant dimension \( d^{(\mathsf{rounds})} \). At this point \( \hat{f} \in \language_\texttt{YES}^{(\mathsf{rounds})} \) can be verified by simply sending \( f(X) \) to the verifier, who checks \( \forall i. \hat{f}_i = f(L^{(\mathsf{rounds})}_i) \). The soundness error of the overall protocol is bounded by the negligible event, \( \hat{f}^{(i)} \in \language_\texttt{NO}^{(1)} \) however \( \hat{f}^{(i+1)}\notin \language_\texttt{NO}^{(2)} \), occurs in any of the rounds. Therefore, once we understand a single round of FRI, we understand the entire protocol.

Doomed Sets: The sets \( \language_\texttt{NO} \), more or less explicitly shows up directly in the round-by-round soundness proof for FRI, where it is closely related to the general notion of a “doomed set” of transcripts. The formal soundness analysis consists in upper bounding the probability that the prover can leave this doomed set if he starts in it.

So how do we get such a reduction?

That is the crux of this post, so let us dive in.

Ingredients of FRI

To instantiate FRI all we need are the following ingredients:

• A finite field \( \FF \).
• A subgroup \( L \leq \FF \).
• A group homomorphism \( q: L \to L’ \), from \( L \) to some \( L’ \leq \FF \) with a non-trivial kernel.

The compression factor \( c \) is \( c = |\ker(q)| \), and we will want \( c > 1 \) to be small for efficiency reasons. So how do we go about finding these ingredients?

Observations about Homomorphisms and Polynomials

First note that for finite fields any map \( q: \FF \to \FF \) can be written as a polynomial \( q(X) \in \FF[X] \) using Lagrange interpolation. In the case of group homomorphisms over the field, one might naively expect that this could result in a polynomial of up to degree \( |\FF| - 1 \), like for general functions, however this is not the case. Instead the degree of the polynomial \( \deg(q) \) is proportional to the size of the kernel of \( q \), namely: \[\deg(q(X)) = |\ker(q)|\] To see this consider a non-trivial homomorphism (i.e. \( \ker(q) \neq \FF \)), let \( \mathbb{1} \) be the identity element in the group and let \( q(X) \) be the polynomial which agrees with \( q \) on \( \bar\FF \) and note that \( g(X) = q(X) - \mathbb{1} \in \FF[X] \) has \( \deg(g) = \deg(q) = |\ker(q)| \) roots over \( \bar\FF \), each of which correspond to a group element being mapped to \( \mathbb{1} \). Concretely, for the quotient homomorphism \( q : G \to G / \ker(q) \) this is the polynomial for a group homomorphism \( q: \FF \to \FF \):

\[ q(X) = \mathbb{1} + \prod_{e \in \ker(q)} (X - e) \in \FF[X] \]

This is nice, because even though we are ultimately interested in polynomials, it allows us to think more abstractly about group homomorphisms in fields. Because the kernel of a homomorphism is a subgroup and because every subgroup \( Q < G \) is the kernel of some homomorphism, namely \( \phi : G \to G / Q \) and \( G / Q < \FF \) for fields, we can just explore the subgroups of finite fields \( \FF \) and then take the quotient homomorphism to get the polynomial.

Which is much easier than coming up with homomorphism or looking for “nice” polynomials in the first place, so:

1. Pick some elements in the field.
2. Let them generate some subgroup (under \(+\) or \( \times \)).
3. Consider the homomorphism to the quotient group.
4. Generate the polynomial for that homomorphism.

This frame-of-mind enables us to better understand and motivate the underlying structure of FRI and to see why e.g. the squaring map, is a natural choice for some fields, while also allowing us to generalize FRI to other settings.

Yay for group theory!

Constructing L and q.

As outlined above, the easiest way to construct \( L \) and \( q(X) \), is to pick a group \( L \subseteq \FF \), find a subgroup \( H < L \) and letting it define \( q(X) \) as the unique group homomorphism from \( q: \FF \to \FF \) which has \( H \) as kernel. Since \( \deg(q) = |H|\), we want \( |H| \) to be small. Therefore a natural choice is to pick \( g \in L \) and let \( H = \langle g \rangle \); for some choice of \( g \), this will clearly yield the smallest possible non-trivial \( H < L \).

For those who like SageMath, the following code snippet does exactly this, namely computes the polynomial \( q(X) \) for a given generator \( g \) and group operation \( \texttt{op} \):

'''
Takes:
  - g  : generator of ker(q(x)).
  - op : the group operation.
  - X  : indeterminate.
Returns the q(X) polynomial for <g>.
'''
def phi(g, op, X):
    # compute H = <g>
    e = g
    H = []
    while 1:
        H.append(e)
        e = op(e, g)
        if e == g: break

    # find group identity
    one = H[-1]
    assert all([op(one, e) == e for e in H])

    # interpolate homomorphism polynomial
    return prod([(X - e) for e in H]) + one

Naturally finite fields offer two kinds of group structure for us to explore:

• The multiplicative group of the field \( (\FF^*, \cdot) \), which is a cyclic group.
• The additive group of the field \( (\FF, +) \), which is isomorphic to a vector space.

Both of these will work, sometimes one better than the other, depending on the field.

So let us look at each of these in turn…

Cyclic Subgroups

Recall that the group of units \( ( \FF^*, \cdot ) \) of any finite field \( \FF \) is cyclic: \( \FF^* = \langle \omega \rangle\).

For any cyclic group \( G = \langle \omega \rangle \), the subgroup \( L = \langle \omega^r \rangle \), where \( \omega^r \) means applying the group operation \(r\) times, has order \( |L| = \lcm(|G|, r) \). Suppose \( |\langle \omega \rangle| = w \cdot k \cdot r \) where \( w \neq 1, k \neq 1 \), then we can obtain a group \( L \) of order \( w \cdot k \) by letting \( g = \omega^r \) and defining \( L = \langle g \rangle \). Furthermore, \( L \) has a non-trivial subgroup of order \( w \):

\[ L = \langle g \rangle, H = \langle g^k \rangle \]

It might be a little abstract, so let us look at a couple of examples:

Example. F17

Consider the prime field \( \FF_{17} \).

The field \( \FF_{17} \) has \( 17 - 1 = 16 \) units (non-zero elements).

The element \( \omega = 3 \in \FF_{17} \) is a primitive root, i.e. \[ \begin{align*} \FF_{17}^* &= \langle 3 \rangle \\ &= \left\{ \begin{matrix} 3, 9, 10, 13, 5, 15, 11, 16, \\ 14, 8, 7, 4, 12, 2, 6, 1
\end{matrix} \right\} \end{align*} \] If we factor the group order we get \( 16 = 2 \cdot 2 \cdot 2 \cdot 2 \). Therefore we have cyclic subgroups of order \( 1, 2, 4, 8, 16 \): any product of the factors. Suppose we want a group \( L \) of order \( 8 = 2 \cdot 2 \cdot 2 = |\FF_{17}^*| / 2 \) with a subgroup \( H < L \) of order \( 2 \):

Then we pick \( g = \omega^2 = 3^2 = 9 \in \FF_{17} \) which gives us:

\[ L \coloneqq \langle 9 \rangle = \{ 9, 13, 15, 16, 8, 4, 2, 1 \} \]

To obtain a subgroup \( H \) pick an element of order \( 2 \) from \( L \), i.e. \( 16 \in L \):

\[ H \coloneqq \langle 2 \rangle = \{ 16, 1 \} \]

Note in that in this case the identity is \( 1 \in \FF_{17}^* \). Therefore the polynomial \( q(X) \) is:

\[ \begin{align*} q(X) &= \mathbb{1} + \prod_{e \in H} (e - X) \\ &= (X - 16) \cdot (X - 1) + 1 \\ &= X^2 \in \FF_{17}[X] \end{align*} \]

The following SageMath code was used to generate the example:

# pick root of unity
F = GF(17)
w = F.multiplicative_generator()
print(w)

# pick generator order 3 subgroup
m = w.multiplicative_order()
assert m % 2 == 0
g = w^(m / 2)
print(g)

# compute the homomorphism:
# group operation is multiplication.
P.<X> = PolynomialRing(F)
q = phi(g, lambda a,b: a*b, X)
print(q)

As seen above, when picking a multiplicative subgroup \( H \) of order \( |H| = 2 \) a number of the coefficients in \(q(X) \) (mathemagically) cancel and results in the “squaring” map \( q(X) = X^2 \) as used in e.g the radix-2 Cooley-Tukey FFT. However we can also pick other values for \( |H| \). Let us look at another example:

Example. F31

Consider the prime field \( \FF_{31} \).

The field \( \FF_{31} \) has \( 31 - 1 = 30 \) units (non-zero elements).

The element \( \omega = 3 \in \FF_{31} \) is a primitive element, i.e. \[ \FF_{31}^* = \langle 3 \rangle = \left\{ \begin{matrix} 3, 9, 27, 19, 26, 16, 17, 20, 29, 25, \\ 13, 8, 24, 10, 30, 28, 22, 4, 12, 5, \\ 15, 14, 11, 2, 6, 18, 23, 7, 21, 1 \end{matrix} \right\} \] If we factor the group order we get \( 30 = 5 \cdot 3 \cdot 2 \). Therefore we have cyclic subgroups of order \( 1, 2, 3, 5, 6, 10, 15, 30 \): any product of the factors. Suppose we want a group \( L \) of order \( 15 = 3 \cdot 5 = |\FF_{31}^*| / 2 \) and a subgroup \( H < L \) of order \( 3 \):

Then we pick \( g = \omega^2 = 3^2 = 9 \in \FF_{31} \) which gives us:

\[ L \coloneqq \langle 9 \rangle = \left\{ \begin{matrix} 9, 19, 16, 20, 25, \\ 8, 10, 28, 4, 5, \\ 14, 2, 18, 7, 1 \end{matrix} \right\} \]

To obtain a subgroup \( H \) pick an element of order \( 3 \) from \( L \), i.e \( 25 \in L \):

\[ H \coloneqq \langle 25 \rangle = \{ 25, 5, 1 \} \] The polynomial \( q(X) \) is:

\[ \begin{align*} q(X) &= \mathbb{1} + \prod_{e \in H} (e - X) \\ &= (X - 25) \cdot (X - 5) \cdot (X - 1) + 1 \\ &= X^3 \in \FF_{31}[X] \end{align*} \]

And what a surprise: it is the “cubing” map because \( |H| = 3 \).

The following SageMath code was used to generate the example:

# pick root of unity
F = GF(31)
w = F.multiplicative_generator()
print(w)

# pick generator order 3 subgroup
m = w.multiplicative_order()
assert m % 3 == 0
g = w^(m / 3)
print(g)

# compute the homomorphism:
# group operation is multiplication.
P.<X> = PolynomialRing(F)
q = phi(g, lambda a,b: a*b, X)
print(q)

Because we are going to need a sequence of small subgroups for FRI, the approach above works nicely for fields \( \FF_q \) where \( q - 1 \) has many small prime factors. In practice this means picking a prime \( q \) such that \( q - 1 = 2^k \cdot R \) for some number \( R \) and suitably large \( k \).

However in the case of e.g. binary fields \( \FF_{2^k} \) the strategy above is not going to work well since \( 2^k - 1 \) might not be smooth and we do not have may practical choices for \( k \) to try before the field becomes intractably large – unlike picking \( R \) above in the prime field case.

Extension Fields and Vector Spaces.

A natrual choice for fields \( \FF = \FF_{c^e} \) is additive subgroups.

Example. F16

Consider the extension field: \( \FF_{2^4} = \FF_2[z] / (z^4 + z + 1) \). Note that every element of \( \FF \) has order two in the additive group, let \( g \in \FF_{2^4} \) be some non-zero element: \[ g = c_3 \cdot z^3 + c_2 \cdot z^2 + c_1 \cdot z + c_0 \in \FF_{2^4} \] Adding \( g \) to itself yields:

\[ \begin{align*} g + g &= \overline{2} \cdot c_3 \cdot z^3 + \overline{2} \cdot c_2 \cdot z^2 + \overline{2} \cdot c_1 \cdot z + \overline{2} \cdot c_0 \\ g + g &= 0 \cdot c_3 \cdot z^3 + 0 \cdot c_2 \cdot z^2 + 0 \cdot c_1 \cdot z + 0 \cdot c_0 \\ g + g &= 0 \end{align*} \] Hence we can get a group of order \( 2 \) by picking any element \( g \in \FF_{2^4} \) and letting \( L = \langle g \rangle \). Let us pick \( g = z^3 + z + 1 \) for the sake of example, which gives us:

\[ H = \langle z^3 + z + 1 \rangle = \{ z^3 + z + 1, 0 \} < (\FF_{2^4}, +) \]

And the quotient map \( q(X) \) is:

\[ \begin{align*} q(X) &= \mathbb{1} + \prod_{e \in H} (e - X) \\ &= (X - z^3 + z + 1) \cdot (X - 0) + 0 \\ &= X^2 + (z^3 + z + 1) \cdot X \end{align*} \]

For those who like SageMath, the following code was used to generate the example:

# define field
F = GF(2)
R.<z> = PolynomialRing(F)
F2 = F.extension(z^4 + z + 1, 'z')

# pick a generator arbitrarily
g = F2(z^3 + z + 1)

# compute the homomorphism:
# group operation is addition.
P.<X> = PolynomialRing(F2)
q = phi(g, lambda a,b: a + b, X)
print(q)

# sanity check
e1 = F2.random_element()
e2 = F2.random_element()
assert q(e1 + e2) == q(e1) + q(e2)

Subspaces and Linear Maps: Besides being a polynomial over \( \FF_{2^4} \), the map \( q(X) \) is an \( \FF_2 \)-linear map over the vector space \( \FF_2^{4} \). It has a kernel of dimension \( 1 \) and therefore a rank of \( 3 \), it maps the vector \( (1, 0, 1, 1) \in \FF_2^{4} \) corresponding to \( z^3 + z + 1 \in \FF^{2^4} \) to the vector \( (0, 0, 0, 0) \). The corresponding matrix of this linear map can be obtained by evaluating \( q(X) \), as a polynomial, on the standard basis:

\[ \begin{align*} q(1) &= z + z^3 &\sim (0, 1, 0, 1) \in \FF_{2}^4 \\ q(z) &= 1 &\sim (1, 0, 0, 0) \in \FF_{2}^4 \\ q(z^2) &= 1 + z^3 &\sim (1, 0, 0, 1) \in \FF_{2}^4 \\ q(z^3) &= 1 + z + z^3 &\sim (1, 1, 0, 1) \in \FF_{2}^4 \end{align*} \]

Therefore the \( \FF_2\)-linear map \( q(X) \) can be written as the \( 4 \times 4 \)-matrix:

\[ M_q \coloneqq \begin{pmatrix} 0 & 1 & 0 & 1 \\ 1 & 0 & 0 & 0 \\ 1 & 0 & 0 & 1 \\ 1 & 1 & 0 & 1 \end{pmatrix}, \forall e \in \FF_{2^4}. \vec{e} M_q = \vec{q(e)} \]

The matrix above was computed using the following SageMath code:

# evaluate q on standard basis
B = [F2(1), F2(z), F2(z^2), F2(z^3)]
E = [q(e) for e in B]
print(E)

# construct GF(2)-matrix
M = Matrix([vector(e) for e in E])
print(M)

# sanity check
e3 = F2.random_element()
assert vector(e3) * M == vector(q(e3))

It is clear that \( q(X) \) is a linear map, but when are polynomials linear maps?

When we compute \(q(X)\) for linear subspaces, like \( H \) above, it will always result in a Linearized Polynomial in which the only non-zero coefficients are for monomials of degree \( p^i \) where \( p \) is the characteristic of the field, i.e. \( q(X) = \prod_{i = 0}^n c_i \cdot X^{p^i} \). This should not be surprising to the reader: these are exactly the polynomials which are linear combinations of monomials corresponding to \( \FF_p \)-linear operations over the vector space \( \FF_p^{k} \).

Exercise.

Prove the claim above.

Hint: Use that \( \forall e \in \FF_{p}. e^m = e \) if and only if \(m = p^i \).

Hint: Use \( \forall x \in \FF_{p^k}. e \in \FF_{p}. f(e \cdot x) = e \cdot f(x) \) for any \( \FF_p \)-linear map \( f \in \FF_{p^k}[X] \).

In general, we do not want to evaluate over the entire field \( L = \FF^{p^k} \), because the size of the field \( p^k \) might be very large (exponential), additionally the FRI soundness analysis actually requires \( \sqrt{|\FF|} > |L| \) to reach the Johnson bound (giving better concrete parameters) i.e. the field needs to be much larger than the evaluation domain. So a natural idea is to pick \( L \subseteq \FF^{p^k} \) as a linear/affine subspace of \( \FF_p^k \). Let us see an example of this next.

Example. Subspace of F243

Consider the extension field: \( \FF_{3^5} = \FF_3[z] / (z^5 + 1) \) which has \( 3^5 = 243 \) elements.

Note that every element of \( \FF_{3^5} \) has order three in the additive group. We can construct an \( \FF_3 \)-subspace \( L \subseteq \FF_{3^5} \) with \( 3^2 \) elements by picking two \( \FF_3 \)-linearly independent elements \( v_1, v_2 \in \FF_{3}^5 \) and letting \( L = \langle v_1, v_2 \rangle \) : the vector space spanned by \( v_1 \) and \( v_2 \). A natural choice is picking two elements of the standard basis: \( v_1 = 1, v_2 = z \in \FF_{3^5} \). Which gives us a subspace with the following elements:

\[ L = \langle 1, z \rangle = \left\{ \begin{matrix} 0, 1, 2, \\ z, z+1, z+2, \\ 2z, 2z+1, 2z+2 \end{matrix} \right\} < \left(\FF_{3}^5, +\right) \]

To obtain \( q(X) \), we can pick any element \(g \in L \). Again, a natural choice is picking one of our two basis elements, e.g. \( g = v_1 \). In which case we get:

\[ \begin{align*} q(X) &= \mathbb{1} + \prod_{e \in H} (e - X) \\ &= (X - 0) \cdot (X - 1) \cdot (X - 2) + 0 \\ &= X^3 + 2 \cdot X \end{align*} \]

Note that \( q : \FF_{3}^5 \to \FF_{3}^5 \) is just the linear map which sends the “\( v_1 \) coordinate” to zero, i.e. \( q((c_1, c_2, c_3, c_4, c_5)) = (0, c_2, c_3, c_4, c_5) \) because we picked \( g = v_1 \), the first basis vector, as the kernel of the linear map.

So we can satisfy the prerequisites for FRI when either:

• \( \FF^* \) is smooth, e.g. \( |\FF^*| = 2^k \cdot R \).
• \( \FF \) is an extension field of small characteristic.

With all of these preliminaries out of the way, let us cook up the FRI protocol next.

FRI Time!

Before we continue, let us briefly recap the ingredients of FRI.

FRI is parametrized by:

• A finite field \( \FF \).
• A subgroup \( L \subseteq \FF \).
• A group homomorphism \( q: L \to L’ \), where \( \deg(q(X)) = |\ker(q)| \) is small.

And, do not worry, there will be plenty of examples at the end of the post.

The Start of FRI

Let \( f(X) \in \FF[X] \), be the polynomial chosen by the prover. FRI starts by having the prover evaluate \( f(X) \) on \( L \) and sending the evaluations \( \hat{f} = f(L) \in \mathsf{RS}[\FF, L, d] \) to the verifier.

In practice, an FFT is used to compute the evaluations of \( f(X) \) on \( L \) efficiently. Luckily the fields that work for FRI also have efficient FFTs. It is also noteworthy that the quasi-linear complexity required to compute the codeword \( \hat{f} \) is the most expensive part of FRI, namely the only part that has super-linear complexity in the degree.

Consider The Base-q(X) Decomposition

With \( f(X) \) now defined by \( \hat{f} \), consider the unique “base-\( q(X) \)” decomposition of \( f(X) \):

\[ \begin{align*} f(X) &= f_i(X) \cdot q(X)^0 + \ldots + f_{d’}(X) \cdot q(X)^{d’} \\ &= \sum_{i = 0}^{d’} \ f_i(X) \ \cdot \ q(X)^i \end{align*} \]

\[ \text{With } d’ = \left\lceil \frac{\deg(f)}{\deg(q)} \right\rceil \text{ and }
\forall i. \deg(f_i) < \deg(q) \]

This could be computed by repeated polynomial division, however, computing this decomposition explicitly is not necessary: we will only need it as a didactic tool for exposition.

Let us replace \( q(X) \) with an indeterminate \( Y \) and rewrite the decomposition of \( f(X) \) as a bivariate polynomial \( g(X, Y) \in (\FF[X])[Y] \):

\[ \begin{align*} g(X, Y) &= f_i(X) \cdot Y^0 + \ldots + f_{d’}(X) \cdot Y^{d’} \\ &= \sum_{i = 0}^{d’} f_i(X) \ \cdot \ Y^i \end{align*} \]

A few quick observations before we continue:

• Plugging \( q(X) \) back into \( g(X, Y) \), we get \( g(X, q(X)) = f(X) \).
• Therefore \( \forall x \in L \) the evaluation \(g(x, q(x)) = f(x) \) was sent to the verifier.

No magic so far, neither party has done anything yet.

The g(X, Y) Evaluation Table

Actually, there are few more observations about the degrees of partially evaluating \( g(X, Y) \):

• \( \deg g(X, y) \leq \deg q(X) - 1\) for any \( y \in \FF \). Since it is a linear combination of polynomials of degree \( \deg(q) - 1 \) polynomials: \[ g(X, y) = \sum_{i = 0}^{d’} f_i(X) \ \cdot \ y^i \in \FF[ X ] \] Recall that \( \deg(q) = |\ker(q)| \) and is small (constant in the degree of \( f(X) \)).
• \( \deg g(x, Y) \leq d’ \) for any \( x \in \FF \). because when the polynomials \( f_i(X) \) are replaced with their evaluations at \( x \) it is just a univariate polynomial of degree \( d’ \): \[ g(x, Y) = \sum_{i = 0}^{d’} f_i(x) \ \cdot \ Y^i = \sum_{i = 0}^{d’} c_i \cdot Y^i \in \FF[Y] \]

Therefore, if we consider a table of evaluations of \( g(X, Y) \) with each row corresponding to a different \( x \in \FF \), each column corresponding to a different \( y \in q(L) \) and each entry corresponding to the evaluation of \( g(X, Y) \) at \( (x, y) \):

The points on every row of the table lie on a polynomial of degree \( d’ \) and points on every column of the table lie on a polynomial of degree \( \deg(q) - 1 \):

Now a crucial observation: every column of the table contains \( \deg(q) \) elements from \( \hat{f} = f(L) \). This can be seen as follows:

• For every \( y \in q(L) \) the set of preimages \( |q^{-1}(y)| \subseteq L \) has the same cardinality. This is because \( q(X) \) is a group homomorphism on \( L \), therefore each \( |q^{-1}(y)| \) is a coset of the kernel, each of which has \( \deg(q) \) elements. Again, yay for groups!

• Every column \( y \in q(L) \) has \( |q^{-1}(y)| = \deg(q) \) points \( g(x, y) \) contained in \( \hat{f} \). Since for every \( x \in q^{-1}(y) \), meaning that \( y = q(x) \), we had \( g(x, q(x)) = f(x) \) as noted earlier.

As a result, the degree \(\deg(q) - 1 \) “column polynomials” \( g(X, y) \) are actually uniquely defined by the \( \deg(q) \) evaluations \( R_y = \{ g(x, y) \mid x \in L \land q(x) = y \} \) in \( \hat{f} \) e.g. by Lagrange interpolating the unique polynomial of degree \( \deg(q) - 1 \) which agrees with the evaluations in \( R_y \). The points from \( \hat{f} \) are marked with yellow crosses in the figure below with \( \deg(q) = 2 \):

With these observations in mind, the FRI protocol is actually quite simple:

• Pick random row: pick \( x \in \FF \) at random and have the honest prover send the row. i.e. define \( f’(Y) = g(x, Y) \) and send the new codeword \( \hat{f’} = f’(q(L)) \in \mathsf{RS}[\FF, q(L), d’] \).

• Check random columns: to avoid a malicious prover sending something other than \( \hat{f’} = g(x, q(L)) \), the correctly computed row, we check consistency between \( \hat{f’} \) and \( g(X, y) \) at random positions/columns \( y \in q(L) \).

The column consistency check is possible because, again, the points from \( \hat{f} \) uniquely define every column polynomial \( g(X, y) \) for any \( y \in q(L) \). The prover has already sent the points from \( \hat{f} \) to the verifier. Therefore, the verifier can simply evaluate this polynomial at the row \( x \) to check that the position in the row is computed correctly: i.e. check \( g(x, y) = \hat{f}_{y} \). Concretely, the verifier:

1. Samples a column \( y \sample q(L) \) uniformly at random.
2. Reads the elements of \( \hat{f}\) in the \( y \) column: \[ R_y = \{ \hat{f}_{x} \mid x \in q^{-1}(y) \} \]
3. Interpolate column polynomial \( g(X, y) \in \FF[ X] \): \[ \begin{matrix} \deg(g(X, y)) \leq \deg(q) \\ \forall x \in q^{-1}(y). g(x, y) = \hat{f}_{x} \end{matrix} \]
4. Evaluation the column polynomial at the \(x\) row: \[ g(x, y) \overset?= \hat{f’}_{x} \]

Exercise.

Stop and Think: What should the verifier do if the points of \( \hat{f} \) intersect the selected row at the selected column? For instance, in the figure above, what should the verifier do if he queries the \( y_3 \) column?

Solution (Click to Expand)

The verifier should do nothing special:

The verifier opens \( \hat{f} \) at every \( x \in q^{-1}(y) \). Interpolates the unique univariate polynomial \( g(X, y) \) of degree \( \deg(q) - 1 \) which agrees with the evaluations in \( \hat{f} \) at \( q^{-1}(y) \): \( \forall x \in q^{-1}(y). g(x, y) = \hat{f}_x \). Then opens \( \hat{f’}_y \) and checks \( \hat{f’}_y = g(x, y) \).

Sorry about the trick question. ¯\(ツ)/¯

Note: Usually the field \( \FF \) from which \( x \sample \FF \) is much larger than the evaluation domain \( L \) e.g. exponential in the security parameter. So the event above is very unlikely to happen in practice.

Since the row \( \hat{f’} \) should belong to an error correcting code, we do not need to catch the prover if only a few positions are evaluated incorrectly, if it is close we can correct a few errounous positions, i.e. we can still uniquely decode the unique low-degree \( f’(Y) \) which agrees with most of the evaluations. We really only need to catch the prover if he sends something which is far from being the correct evaluations.

Therefore, the strategy of testing just a few columns at random is reasonable. If many positions (e.g a constant fraction) are incorrect, then the prover is caught with high probability. Therefore, conversely, if the check passes with high probability, then the \( \hat{f’} \) must be close to the correct evaluations.

Recursion

The degree of the new polynomial \( f’(Y) \) is \( \deg(f’) = d’ = \deg(f) / \deg(q) \).

To reduce the degree of \( f’(Y) \) further we can repeat the procedure above on \( f’(Y) \). Let:

• The new domain: \( L’ = q(L) \)
• The new polynomial: \( f’(Y) = g(x, Y) \)
• Pick a subgroup \( H’ < L’ \), let it define \( q’(X) \) as for \( q(X) \) above.

Apply the FRI protocol recursively to \( f’(Y) \) with the new parameters \( (L’, H’, q’(X)) \).

Note: To continue the recursion a new subgroup \( H’ < L’ \) is needed, defining a new quotient map \( q’(X) \). Therefore, to recurse many times, we need the original \( L \) to have many small subgroups: so that we can quotient by a new one at each level of recursion.

Note: To improve the round complexity and soundness of FRI, the consistency check is executed only at the end of the folding, i.e. there are no intermediate consistency checks, they are only done at the end of the recursion to check consistency at all levels simultaneously. This is because the folding has a very small soundness error (negligible for exponentially-sized fields), while the consistency check has a constant soundness error regardless of the field size.

Interactive Examples of FRI / FRI Playground

Because it is always easier to understand things by example, this page actually implements the FRI protocol in the browser to visualize what is going on. I spent entirely too much time on this, so please enjoy it. So let us take a look at some examples:

Domain and Quotient Map

Start by selecting a field \( \FF \), an evaluation domain \( L \subseteq \FF \) and a subgroup \( H < L \):

The evaluation domain and field:

Results in the following quotient map \( q(X) \):

The evaluation table \( \hat{q} \) for \(q(X)\) on \( L \) looks as follows:

Selection Polynomial / Commitment Phase

Consider the following (randomly generated) polynomial:

Alternatively you can enter your own polynomial:

The evaluation table \( \hat{f} \) for \(f(X)\) on \( L \) looks as follows:

The prover sends \( \hat{f} \) to the verifier. The \( q(X) \)-decomposition of \( f(X) \) is:

Replace \( q(X) \) with an indeterminate \( Y \), get \( g(X, Y) \in (\FF[X])[Y] \):

Consider the table of evaluations of \( g(X, Y) \) over \( X \in \FF \) and \( Y \in q(L) \) with each row corresponds to a different \( x \in \FF \) and each column corresponds to a different \( y \in q(L) \).

Note: For large fields the rows of the table has been truncated to improve readability.

We color the positions corresponding to \( f(X) = g(X, q(X)) \) in green:

At this point the table only exists in the provers head, except for the green entries which have already been sent to the verifier when committing to \( f(L) \).

Folding

Verifier now picks a random challenge .

Which defines a row (marked in blue) in the table:

This row corresponds to the polynomial

The prover is asked to commit to this row. Of course, he might not do so…

Note: You can click on cells in the blue row above to introduce errors into the message \( \hat{f’} \) sent by the prover – as a corrupted prover might do.

Consistency Check

The verifier runs the column-wise consistency check in an attempt to detect such errors:

The verifier picks the column.

The points in the column (marked in orange) are:

These points lie on the column polynomial:

The verifier evaluates this polynomial at (row marked in blue) to check consistency:

To amplify soundness, the verifier repeats this “security parameter”-times. If it detects an error it knows the prover is corrupt and aborts. After this test, the verifier is convinced that the committed row \( \hat{f’} \) is close to the evaluation of \( g(x, Y) \) on \( q(L) \).

Recursion

For the next round of FRI, we set the new polynomial, now in \( Y \) to:

Which has half the degree of the original \( f(X) \). We define the new domain as:

And pick a subgroup \( H’ < L’ \) to continue.

Note: The codeword \( \hat{f’} = f’(L’) = f’(q(L)) \) is the blue row already sent by the prover.