Module fri

Implementation of the Fast Reed–Solomon IOPP (FRI) over binary fields.

FRI is an IOP of Proximity for Reed–Solomon codes. The original protocol was introduced in BBHR17, and this implementation uses a special instantiation described in DP24 Section 3.

This protocol implement FRI for an interleaved Reed–Solomon code, rather than a regular Reed–Solomon code. Codewords in an interleaved code have the form of being a batch of Reed–Solomon codewords, interleaved element-wise. For example, an interleaved codeword with a batch size of 4 would have the form a0, b0, c0, d0, a1, b1, c1, d1, ..., where a0, a1, ... is a Reed–Solomon codeword, b0, b1, ... is another Reed–Solomon codeword, and so on. The batch size of the interleaved code is required to be a power of 2.

The folding phase begins with the verifier having oracle access to an initial, purported interleaved codeword. In each round the prover receives a challenge and folds the interleaved codeword in half until it reaches a single codeword, mixing adjacent codewords as a linear interpolation. Then in each subsequent round, the prover receives a challenge and folds the codeword in half using the FRI folding procedure and may or may not send a new oracle to the verifier. The last oracle the prover sends, they send entirely in the clear to the verifier, rather than sending with oracle access.

Structs

• CommitOutput
• FRIFolder
  A stateful prover for the FRI fold phase.
• FRIParams
  Parameters for an FRI interleaved code proximity protocol.
• FRIProof
• FRIQueryProver
  A prover for the FRI query phase.
• FRIVerifier
  A verifier for the FRI query phase.
• QueryRoundProof
  The values and vector commitment opening proofs for a coset.

Enums

• Error
• FoldRoundOutput
• VerificationError

Functions

• calculate_n_test_queries
  Calculates the number of test queries required to achieve a target security level.
• commit_interleaved
  Encodes and commits the input message.
• fold_codeword
• to_par_scalar_big_chunks
  Creates a parallel iterator over scalars of subfield elementsAssumes chunk_size to be a power of two
• to_par_scalar_small_chunks

Type Aliases

• QueryProof
  A proof for a single FRI consistency query.
• TerminateCodeword
  The type of the termination round codeword in the FRI protocol.