binius_ntt::fri

Function fold_chunk

Source 
pub fn fold_chunk<F, FS, NTT>(
    ntt: &NTT,
    log_len: usize,
    chunk_index: usize,
    values: &mut [F],
    challenges: &[F],
) -> F
where
    F: BinaryField + ExtensionField<FS>,
    FS: BinaryField,
    NTT: AdditiveNTT<FS>,
Expand description

Calculate FRI fold of values at a chunk_index with random folding challenges.

Folds a coset of a Reed–Solomon codeword into a single value using the FRI folding algorithm. The coset has size $2^n$, where $n$ is the number of challenges.

See DP24, Def. 3.6 and Lemma 3.9 for more details.

NB: This method is on a hot path and does not perform any allocations or precondition checks.

§Arguments

  • ntt - the NTT instance, used to look up the twiddle values.
  • log_len - the binary logarithm of the code length.
  • chunk_index - the index of the chunk, of size $2^n$, in the full codeword.
  • values - mutable slice of values to fold, modified in place.
  • challenges - the sequence of folding challenges, with length $n$.

§Pre-conditions

  • challenges.len() <= log_len.
  • log_len <= ntt.log_domain_size(), so that the NTT domain is large enough.
  • values.len() == 1 << challenges.len().