The FRI Toolbox in Twelve Cards — The Definitions to Memorise
The first half of the ZK Whiteboard Sessions lecture on FRI by Dan Boneh builds a toolbox before it builds the protocol: coding theory, interactive oracle proofs, a trick for turning evaluation claims into proximity claims, and two lemmas about random linear combinations. This deck is for someone who has watched that half, or read its companion article, and wants to fix it in memory.
Twelve cards, each with a plain-words definition, a precise one, and one thing to remember, plus a table at the end to revise from. The cards define; they do not derive. The full vocabulary, thirty terms in three levels, is in FRI and Proximity Proofs — The Vocabulary, From Beginner to Advanced; the protocol itself, which the lecture builds in its second half, has its own deck in FRI in Twelve Cards — The Definitions to Memorise.
This article has been made with the help of Claude Code and several custom skills
The twelve cards
Reed-Solomon code
In plain words: A Reed-Solomon code turns a short formula into a long list by writing down the formula’s answer at many points.
Precisely: The code whose codewords are the values of a polynomial of degree less than \(d\) at every point of a fixed domain \(L\) of size \(n\). Two distinct codewords agree in fewer than \(d\) positions.
Remember: polynomial → evaluations; different polynomials rarely agree
Rate
In plain words: The rate compares the length of the formula with the length of the list it produces; a rate of one quarter means the list is four times longer.
Precisely: The ratio \(\rho = d/n\) of message length to codeword length for a Reed-Solomon code. Every decoding radius that follows is a function of \(\rho\) alone.
Remember: \(\rho = d/n\); every bound is a function of it
Delta-far
In plain words: A list is delta-far from the code when more than a set share of its entries disagree with every valid list.
Precisely: A word is \(\delta\)-far from a code if every codeword differs from it in more than a \(\delta\) fraction of positions, and \(\delta\)-close if some codeword is within that fraction.
Remember: far = wrong in more than a \(\delta\) fraction
Unique decoding distance
In plain words: The unique decoding distance is the number of errors a list can contain while only one formula could still have produced it.
Precisely: The radius \(\mu/2\), about \((1-\rho)/2\) for Reed-Solomon, within which a word has at most one codeword; two would contradict the minimum distance by the triangle inequality.
Remember: below \((1-\rho)/2\), exactly one candidate
Johnson bound
In plain words: The Johnson bound is the larger error level below which only a few formulas can fit a list; past it, nobody knows how many could.
Precisely: The radius \(1 - \sqrt\rho\) below which the number of Reed-Solomon codewords within \(\delta\) of any word is provably bounded. Between it and \(1 - \rho\) the list size for structured domains is unknown.
Remember: \(1 - \sqrt\rho\); few candidates; the proofs stop here
Interactive oracle proof (IOP)
In plain words: In an interactive oracle proof, the prover sends long lists, the verifier answers with random numbers, and at the end the verifier reads only a few entries.
Precisely: A proof system in which the prover sends strings, the verifier answers with random challenges, and the verifier’s decision algorithm reads only a few cells of the strings (oracle access) rather than the strings themselves.
Remember: strings sent, dice rolled, a few cells read
IOP of proximity (IOPP)
In plain words: An IOP of proximity proves that a sealed list is close to a valid one; lists with many errors are rejected and valid lists are always accepted.
Precisely: An IOP whose instance includes a committed word and whose soundness is required only against words \(\delta\)-far from the relation: codewords are always accepted, \(\delta\)-far words rejected with overwhelming probability, and nothing is promised in between.
Remember: accept codewords, reject the far, promise nothing between
BCS compiler
In plain words: The BCS compiler turns the interactive game into one short proof by replacing each list with a hash fingerprint and each random number with a hash.
Precisely: The transformation of an IOP into a hash-based SNARK: strings become Merkle roots, cell reads become Merkle authentication paths, and challenges become hashes of the transcript (Fiat-Shamir). Proof size is driven by the number of cell reads.
Remember: Merkle roots + Fiat-Shamir turn an IOP into a SNARK
Quotienting
In plain words: Quotienting checks one claimed value by subtracting it from every entry and dividing; the result is a tidy list if the claim is true and a mess if it is false.
Precisely: Turning the claim “\(f(a) = b\)” about a committed word \(u\) into a proximity claim: if true, the quotient is a codeword of degree one less; if false for every polynomial near \(u\), it is \(\delta\)-far.
[\begin{aligned} q(x) = \frac{u(x) - b}{x - a} \end{aligned}]
Remember: \((u - b)/(x - a)\): evaluation claim → proximity claim
DEEP
In plain words: DEEP makes the verifier ask for the formula’s value at one random far-away point first, so the prover can no longer switch between formulas.
Precisely: An out-of-domain sample: before any evaluation query the verifier picks a random \(r\) outside \(L\), the prover answers \(s = f(r)\), and every later quotient includes \((r, s)\). Below the Johnson bound this binds the prover to one polynomial in the list.
Remember: one random \((r, s)\) outside the domain pins one polynomial
Proximity gap theorem
In plain words: The proximity gap theorem says that if you mix several lists with random weights and even one of them is a mess, the mix is almost always a mess too.
Precisely: For \(\delta\) below the Johnson bound, the combination \(\sum_j r^j u_j\) is \(\delta\)-close either for a negligible fraction of \(r\) or for all \(r\); in the second case every \(u_j\) agrees with a codeword on one common set of positions.
Remember: a far word cannot hide in a random blend
Folding
In plain words: Folding blends each entry of a list with its mirror entry, producing a list half as long that comes from a formula half as big.
Precisely: Splitting a word on \(L\) into even and odd parts and recombining them with a random \(r\) on the halved domain \(L^2\); degree bound and domain halve, the rate is unchanged, and below the Johnson bound distance is preserved.
[\begin{aligned} u_{\mathrm{fold}}(x^2) = \frac{u(x) + u(-x)}{2} + r\,\frac{u(x) - u(-x)}{2x} \end{aligned}]
Remember: even + \(r\) · odd; half the degree, distance kept
Flashcard table
| # | Term | In plain words | One thing to remember |
|---|---|---|---|
| 1 | Reed-Solomon code | A Reed-Solomon code turns a short formula into a long list by writing down the formula’s answer at many points. | polynomial → evaluations; different polynomials rarely agree |
| 2 | Rate | The rate compares the length of the formula with the length of the list it produces; a rate of one quarter means the list is four times longer. | \(\rho = d/n\); every bound is a function of it |
| 3 | Delta-far | A list is delta-far from the code when more than a set share of its entries disagree with every valid list. | far = wrong in more than a \(\delta\) fraction |
| 4 | Unique decoding distance | The unique decoding distance is the number of errors a list can contain while only one formula could still have produced it. | below \((1-\rho)/2\), exactly one candidate |
| 5 | Johnson bound | The Johnson bound is the larger error level below which only a few formulas can fit a list; past it, nobody knows how many could. | \(1 - \sqrt\rho\); few candidates; the proofs stop here |
| 6 | Interactive oracle proof (IOP) | In an interactive oracle proof, the prover sends long lists, the verifier answers with random numbers, and at the end the verifier reads only a few entries. | strings sent, dice rolled, a few cells read |
| 7 | IOP of proximity (IOPP) | An IOP of proximity proves that a sealed list is close to a valid one; lists with many errors are rejected and valid lists are always accepted. | accept codewords, reject the far, promise nothing between |
| 8 | BCS compiler | The BCS compiler turns the interactive game into one short proof by replacing each list with a hash fingerprint and each random number with a hash. | Merkle roots + Fiat-Shamir turn an IOP into a SNARK |
| 9 | Quotienting | Quotienting checks one claimed value by subtracting it from every entry and dividing; the result is a tidy list if the claim is true and a mess if it is false. | \((u - b)/(x - a)\): evaluation claim → proximity claim |
| 10 | DEEP | DEEP makes the verifier ask for the formula’s value at one random far-away point first, so the prover can no longer switch between formulas. | one random \((r, s)\) outside the domain pins one polynomial |
| 11 | Proximity gap theorem | The proximity gap theorem says that if you mix several lists with random weights and even one of them is a mess, the mix is almost always a mess too. | a far word cannot hide in a random blend |
| 12 | Folding | Folding blends each entry of a list with its mirror entry, producing a list half as long that comes from a formula half as big. | even + \(r\) · odd; half the degree, distance kept |
Conclusion
Three cards carry the deck. The Johnson bound is the line every other guarantee is stated below; quotienting is how a proximity test becomes an evaluation proof; and folding is the operation FRI repeats. The rest of the cards are what those three need in order to be stated: a code, a rate, a notion of far, an oracle model, and the theorem that says random blends preserve distance.
The next step is the second half of the lecture, where the folding card becomes a protocol. Its deck, FRI in Twelve Cards, picks up where this one ends.
Frequently Asked Questions
Q: Which card explains why the verifier only checks “close” and not “equal”?
IOP of proximity, together with Delta-far. A verifier reading a few cells cannot see a single wrong position, so the only promise it can keep is to reject words that are wrong in more than a \(\delta\) fraction of positions. Everything closer than that is left unpromised.
Q: What is the difference between the unique decoding distance and the Johnson bound?
Below the unique decoding distance a word has at most one nearby codeword. Below the Johnson bound it may have several, but provably few. The second radius is larger, about \(1/2\) against \(3/8\) at rate \(1/4\), and a bounded list is enough for every argument in the deck, so the Johnson bound is the working limit.
Q: What does the Remember line of quotienting leave out?
Two things. The evaluation point \(a\) must lie outside the domain, or the division is by zero and the quotient has to be defined through exact polynomial division instead. And the “false” direction is conditional: the quotient is far only when the claim is wrong for every polynomial near \(u\), which is exactly why DEEP is needed when the list has more than one member.
Q: Put Reed-Solomon code, DEEP, BCS compiler and quotienting in the order the compiled protocol uses them.
Reed-Solomon code first: the prover encodes its polynomial as a codeword. DEEP second: the out-of-domain sample is taken before any evaluation query. Quotienting third: each evaluation query becomes a proximity test on a quotient that includes the DEEP point. BCS compiler last: the whole interactive oracle proof is turned into a hash-based proof.
Q: Which card is wrong if the field is small?
| None becomes false, but two need their fallback. DEEP bounds the bad event by $$ | \mathrm{List} | ^2 \cdot d / ( | \mathbb F | - | L | )\(, and the [proximity gap theorem](#proximity-gap-theorem) has an error term with the field size in the denominator. In a small field both are handled by sampling several values of\)r$$ instead of one. |
Q: Why does folding not change the rate?
The degree bound halves because the even and odd parts each hold half the coefficients, and the domain halves because squaring on a set of roots of unity is two-to-one. Both terms of \(\rho = d/n\) halve, so the ratio is unchanged, and a \(\delta\) chosen below the Johnson bound stays below it after every fold.
References
- ZK Whiteboard Sessions — S2M7: FRI and Proximity Proofs (Part 1), with Dan Boneh, the lecture this deck compresses
- Eli Ben-Sasson, Iddo Bentov, Yinon Horesh, Michael Riabzev, Fast Reed-Solomon Interactive Oracle Proofs of Proximity, 2017
- Eli Ben-Sasson, Alessandro Chiesa, Nicholas Spooner, Interactive Oracle Proofs, 2016
- Eli Ben-Sasson, Lior Goldberg, Swastik Kopparty, Shubhangi Saraf, DEEP-FRI: Sampling Outside the Box Improves Soundness, 2019
- Eli Ben-Sasson, Dan Carmon, Yuval Ishai, Swastik Kopparty, Shubhangi Saraf, Proximity Gaps for Reed-Solomon Codes, 2020
Related articles
- FRI and Proximity Proofs, Part 1 — Reed-Solomon Codes, IOPs of Proximity, Quotienting and Folding
- FRI and Proximity Proofs — The Vocabulary, From Beginner to Advanced
- FRI in Twelve Cards — The Definitions to Memorise
- FRI Explained Like I’m Ten — How to Check a Million Numbers by Peeking at Twenty
You might also enjoy
