binius_core/protocols/fri/mod.rs
1// Copyright 2024-2025 Irreducible Inc.
2
3//! Implementation of the Fast Reed–Solomon IOPP (FRI) over binary fields.
4//!
5//! FRI is an IOP of Proximity for Reed–Solomon codes. The original protocol was introduced in
6//! [BBHR17], and this implementation uses a special instantiation described in [DP24] Section 3.
7//!
8//! This protocol implement FRI for an interleaved Reed–Solomon code, rather than a regular
9//! Reed–Solomon code. Codewords in an interleaved code have the form of being a batch of
10//! Reed–Solomon codewords, interleaved element-wise. For example, an interleaved codeword with a
11//! batch size of 4 would have the form `a0, b0, c0, d0, a1, b1, c1, d1, ...`, where `a0, a1, ...`
12//! is a Reed–Solomon codeword, `b0, b1, ...` is another Reed–Solomon codeword, and so on. The
13//! batch size of the interleaved code is required to be a power of 2.
14//!
15//! The folding phase begins with the verifier having oracle access to an initial, purported
16//! interleaved codeword. In each round the prover receives a challenge and folds the interleaved
17//! codeword in half until it reaches a single codeword, mixing adjacent codewords as a linear
18//! interpolation. Then in each subsequent round, the prover receives a challenge and folds the
19//! codeword in half using the FRI folding procedure and may or may not send a new oracle to the
20//! verifier. The last oracle the prover sends, they send entirely in the clear to the verifier,
21//! rather than sending with oracle access.
22//!
23//! [BBHR17]: <https://eccc.weizmann.ac.il/report/2017/134/>
24//! [DP24]: <https://eprint.iacr.org/2024/504>
25
26mod common;
27mod error;
28mod prove;
29#[cfg(test)]
30mod tests;
31mod verify;
32
33pub use common::{calculate_n_test_queries, estimate_optimal_arity, FRIParams, TerminateCodeword};
34pub use error::*;
35pub use prove::*;
36pub use verify::*;