# What is FRI in a STARK?

FRI is the low-degree test used in STARKs. It checks that committed values come from a polynomial of low degree by halving the problem round after round and testing a few random points, and it rests only on hash functions.

Also called Fast Reed-Solomon Interactive Oracle Proofs of Proximity.

## What problem it solves

A verifier cannot read every value a prover commits to. It needs a cheap way to test whether those values lie on a polynomial of low degree, and FRI provides that test with a few random checks.

The formal name describes the test. FRI checks whether a function is close to a Reed-Solomon code, which is the set of evaluations of polynomials of low degree. The name comes from its resemblance to the fast Fourier transform.

## How the rounds work

- The prover commits to the values of the polynomial, as the root of a Merkle tree.
- In each round, the verifier sends a random challenge, and the prover folds the polynomial into one of half the degree and commits to the result.
- The verifier checks that each round agrees with the previous one at a few random points, using the Merkle paths the prover supplies.
- After enough rounds, the remaining function is small enough for the verifier to check directly.

## Why it matters

The FRI paper shows that the verifier's arithmetic grows strictly logarithmically with the input size. That is what keeps a STARK's check fast.

FRI rests on hash functions and public randomness, so it needs no trusted setup.

## Related terms

- [STARK](https://redacted.gg/glossary/stark.md): A STARK is a short proof that a long computation was done correctly, which anyone can check quickly. It is built from hash functions alone, so it needs no trusted setup and no elliptic curves, and it can keep the inputs secret.
- [Polynomial commitment](https://redacted.gg/glossary/polynomial-commitment.md): A polynomial commitment is a short value that binds a prover to one polynomial. Later the prover can prove the polynomial's value at any chosen point, and the verifier checks that proof against the short value.
- [Merkle proof](https://redacted.gg/glossary/merkle-proof.md): A Merkle proof shows that an item belongs to a Merkle tree. It is the item together with a short list of sibling hashes, which lets anyone recompute the tree's root and compare it with the root they already trust.
- [Fiat-Shamir transform](https://redacted.gg/glossary/fiat-shamir.md): The Fiat-Shamir transform turns an interactive proof, where the verifier sends random challenges, into a single message. The prover computes each challenge as a hash of everything sent so far, so no back-and-forth is needed.
- [Finite field](https://redacted.gg/glossary/finite-field.md): A finite field is a set with a fixed number of elements, where addition, subtraction, multiplication and division by a nonzero element always stay inside the set. STARKs do their arithmetic in one.
- [Hash function](https://redacted.gg/glossary/hash-function.md): A hash function turns any input into a short fingerprint of fixed size. The same input always gives the same fingerprint, and nobody can work back from it or find two inputs that share one.

Sources: [Fast Reed-Solomon Interactive Oracle Proofs of Proximity, ECCC 2017](https://eccc.weizmann.ac.il/report/2017/134/), [The Cambrian explosion of cryptographic proofs, StarkWare](https://starkware.co/integrity-matters-blog/cambrian-explosion-of-cryptographic-proofs/)
---

Page: https://redacted.gg/glossary/fri/