p3-binary-pcs 0.8.0

//! Prover side: commit the stacked polynomial as one codeword column, then fold that codeword
//! in lockstep with the residual sumcheck.
//!
//! The layout commits at no preprocessing depth, so its commit phase produces one column.
//! That column is the whole committed polynomial, Reed-Solomon encoded.
//!
//! No preprocessing round is consumed either.
//! Every committed variable is therefore a folding round.
//!
//! Each round's challenge is used twice.
//! It binds one multilinear variable through the layout's evaluation-basis suffix binding.
//!
//! It also folds the codeword, a Reed-Solomon codeword fold in the same basis.
//! The two stay in correspondence throughout, which the tests below drive and check.
//!
//! # Two fields, one schedule
//!
//! ```text
//!     base word       the committed alphabet, committed through the base scheme
//!     folded words    the challenge field, committed through the folded scheme
//! ```
//!
//! The first fold of the first batch is the only one that crosses between them.

use alloc::vec::Vec;

use p3_challenger::fs::TranscriptField;
use p3_challenger::{CanObserve, CanSampleUniformBits, FieldChallenger, GrindingChallenger};
use p3_commit::{Encoder, Mmcs};
use p3_field::{ExtensionField, Field};
use p3_matrix::dense::{DenseMatrix, RowMajorMatrix};
use p3_multilinear_util::point::Point;
use p3_sumcheck::SumcheckData;
use p3_sumcheck::layout::{Layout, SuffixResidualProver, Table, Witness};

use crate::PcsLayout;
use crate::fold::{ChallengeField, FoldAlphabet, fold_codeword_batch};
use crate::params::BinaryPcsConfig;
use crate::proof::RoundProof;
use crate::transcript::BinaryPcsProverTranscript;
use crate::verifier::flat_coset_indices;

/// Preprocessing depth the commit phase lays out inside a committed row.
///
/// Zero, so the codeword is a single column and every variable is folded rather than bound
/// across a row. Binding a prefix inside the row is the deferred head collapse, which needs
/// its own eq-weighted column combination before it composes with the folds below.
const FOLDING: usize = 0;

/// Fewest rounds a batch folds for its codeword to be encoded from the bound message rather than
/// folded from the previous codeword.
///
/// Below it, folding the previous codeword is the cheaper of the two at every codeword length.
const MIN_ENCODED_ARITY: usize = 4;

/// Data produced by committing the base codeword: the layout used to build the residual
/// sumcheck, and the base commitment's Merkle prover data.
///
/// Retains the source tables for AIR evaluation between commitment and opening.
/// Cloning reuses the encoding and Merkle tree for another opening of the commitment.
#[derive(Clone)]
pub struct BinaryPcsProverData<F: Field, EF: ExtensionField<F>, MT: Mmcs<F>> {
    /// The layout that ran the commit phase, carried forward to build the residual sumcheck
    /// and, later, to evaluate opening claims against the committed polynomial.
    pub(crate) layout: PcsLayout<F, EF>,
    /// The base codeword's Merkle prover data, needed to open base-round queries once the
    /// query phase samples its indices.
    pub(crate) merkle_data: MT::ProverData<DenseMatrix<F>>,
}

impl<F, EF, MT> BinaryPcsProverData<F, EF, MT>
where
    F: TranscriptField,
    EF: ExtensionField<F>,
    MT: Mmcs<F>,
{
    /// Returns source table `id` retained by the committed layout.
    pub fn table(&self, id: usize) -> &Table<F> {
        self.layout.table(id)
    }
}

/// One folding round's prover-side output.
pub(crate) struct RoundCommitment<EF: Field, MX: Mmcs<EF>> {
    /// Merkle root of this round's folded codeword.
    pub commitment: MX::Commitment,
    /// Merkle prover data for this round's folded codeword, needed to open its queries.
    pub merkle_data: MX::ProverData<DenseMatrix<EF>>,
}

/// Commits `witness`'s stacked polynomial and returns the base commitment alongside the data
/// needed to run the residual sumcheck and later open the base codeword's queries.
///
/// Nothing is bound here.
///
/// The root is returned instead, and the caller binds it.
///
/// `witness` must have the configured number of variables, at zero preprocessing depth.
#[tracing::instrument(name = "binary pcs commit", skip_all)]
pub(crate) fn commit<F, EF, E, MT>(
    config: &BinaryPcsConfig,
    encoder: &E,
    mmcs: &MT,
    witness: Witness<F>,
) -> (MT::Commitment, BinaryPcsProverData<F, EF, MT>)
where
    F: TranscriptField,
    EF: ExtensionField<F>,
    E: Encoder<F>,
    MT: Mmcs<F>,
{
    assert_eq!(
        witness.num_variables(),
        config.num_variables(),
        "witness arity must match the config it is committed against"
    );

    let (layout, commitment, merkle_data) =
        PcsLayout::<F, EF>::commit(encoder, mmcs, witness, FOLDING, config.log_inv_rate());

    (
        commitment,
        BinaryPcsProverData {
            layout,
            merkle_data,
        },
    )
}

/// Runs each residual sumcheck round before consuming its challenge in a codeword fold.
/// Consecutive folds are fused into configured batches, with one commitment per batch except
/// the last, whose entire codeword travels in the clear.
///
/// The single grinding budget is spent once before the query phase, not here.
/// Every round below therefore runs at zero difficulty.
///
/// # Returns
///
/// - The base commitment's Merkle prover data, so base-round queries can still open.
/// - The sumcheck transcript.
/// - One round commitment per fold batch except the last.
/// - The folding randomness, in round order.
/// - The final folded codeword.
///
/// `BIND_EACH_ROUND` picks when each round's challenge is applied to the sumcheck tables:
///
/// ```text
///     false: left outstanding, so the next round's measuring pass absorbs it
///            one pass per round
///     true : applied on the spot, so the next round measures in a pass of its own
///            two passes per round
/// ```
///
/// The two produce the same round polynomials, so one can be pinned against the other.
///
/// The choice is a const parameter, so a build that never asks for the two-pass route
/// never compiles one.
///
/// This is the only seam between the two routes.
#[allow(clippy::type_complexity)]
#[tracing::instrument(name = "binary pcs fold rounds", skip_all)]
pub(crate) fn fold_rounds_with<const BIND_EACH_ROUND: bool, F, EF, MT, MX, Ch>(
    prover_data: BinaryPcsProverData<F, EF, MT>,
    config: &BinaryPcsConfig,
    mmcs: &MT,
    round_mmcs: &MX,
    transcript: &mut BinaryPcsProverTranscript<'_, F, EF, Ch>,
) -> (
    MT::ProverData<DenseMatrix<F>>,
    SumcheckData<F, EF>,
    Vec<RoundCommitment<EF, MX>>,
    Point<EF>,
    Vec<EF>,
)
where
    F: TranscriptField + FoldAlphabet<EF>,
    EF: ChallengeField<F> + ExtensionField<F> + FoldAlphabet<EF>,
    MT: Mmcs<F>,
    MX: Mmcs<EF>,
    Ch: FieldChallenger<F>
        + GrindingChallenger<Witness = F>
        + CanSampleUniformBits<F>
        + CanObserve<MX::Commitment>,
{
    let BinaryPcsProverData {
        layout,
        merkle_data,
    } = prover_data;

    let mut sumcheck_data = SumcheckData::default();

    // Each challenge width uses its carryless-multiply representation for round arithmetic.
    // The transcript carries tower elements in both cases.
    let (mut sumcheck, mut randomness) = transcript.fold_batch(|challenger| {
        layout.into_sumcheck_in::<<EF as ChallengeField<F>>::SumcheckRepr, _>(
            &mut sumcheck_data,
            0,
            challenger,
        )
    });
    assert_eq!(
        randomness.num_variables(),
        0,
        "the commit phase runs at zero preprocessing depth, so the sumcheck consumes no head rounds"
    );

    assert_eq!(
        mmcs.get_matrices(&merkle_data)[0].width,
        1,
        "zero preprocessing depth commits a width-1 codeword"
    );

    // Sumcheck messages/challenges remain sequential. Only batch boundaries materialize
    // codewords and observe roots; the final batch is returned in the clear.
    let num_batches = config.num_fold_batches();
    let mut rounds: Vec<RoundCommitment<EF, MX>> = Vec::with_capacity(num_batches - 1);
    let mut final_codeword = Vec::new();
    for (batch, (start, arity)) in config.fold_batches().enumerate() {
        let _batch_span = tracing::info_span!("fold batch", batch, start, arity).entered();
        let mut challenges = Vec::with_capacity(arity);
        for round in start..start + arity {
            let challenge = tracing::debug_span!("sumcheck round", round).in_scope(|| {
                // A sumcheck round seeds a sub-transcript of its own.
                transcript.fold_batch(|challenger| {
                    sumcheck.compute_sumcheck_polynomials(&mut sumcheck_data, challenger, 1, 0)
                })
            });
            challenges.push(challenge.as_slice()[0]);
            randomness.extend(&challenge);

            // The reference route applies this round's binding now.
            //
            // The fused route instead lets the next round's measuring pass absorb it.
            if BIND_EACH_ROUND {
                sumcheck.settle();
            }
        }

        // A batch's folded codeword is also the encoding of the message its rounds bound.
        //
        //     fold     one pass per round over the previous codeword, halving it each time,
        //              so its cost is set by the codeword it reads, whatever the arity
        //     encode   one transform of the folded codeword, a product per symbol per bit of
        //              its length, so its cost halves with every round the batch folds
        //
        // Encoding is therefore the cheaper one only for a batch of enough rounds, and it needs
        // the sumcheck to hold the bound message at the batch's end.
        //
        // Otherwise fold out of the previous batch's Merkle leaves, never out of a copy of them.
        // The commitment scheme already owns every codeword it committed.
        //
        // The first batch reads the committed alphabet, every later one the challenge field.
        // The two arms therefore differ in the type of the codeword they load.
        let folded = tracing::info_span!("fold codeword").in_scope(|| {
            let encoded = (arity >= MIN_ENCODED_ARITY)
                .then(|| encode_bound_message(&mut sumcheck, config.log_inv_rate()))
                .flatten();
            encoded.unwrap_or_else(|| {
                if batch == 0 {
                    fold_codeword_batch(&mmcs.get_matrices(&merkle_data)[0].values, &challenges)
                } else {
                    let source = &rounds[batch - 1].merkle_data;
                    fold_codeword_batch(&round_mmcs.get_matrices(source)[0].values, &challenges)
                }
            })
        });
        if batch + 1 < num_batches {
            let (commitment, round_data) = tracing::info_span!("commit folded codeword")
                .in_scope(|| round_mmcs.commit_matrix(RowMajorMatrix::new(folded, 1)));
            transcript.oracle_commitment(commitment.clone());
            rounds.push(RoundCommitment {
                commitment,
                merkle_data: round_data,
            });
        } else {
            final_codeword = folded;
        }
    }

    // A challenge the sumcheck still holds after the last round is never applied.
    //
    // The last batch's codeword, not the sumcheck tables, carries the folded message forward.
    // The returned tuple holds no sumcheck state, so nothing downstream can read the tables.
    // A final binding pass would only produce a table nobody looks at.
    //
    // A last codeword encoded from the bound message has applied it already, and holds none.
    //
    // A debug build applies a held one anyway, purely to check the claim against the pair it
    // binds. That is the last held binding's only validation, in any profile.
    #[cfg(debug_assertions)]
    sumcheck.settle();

    (
        merkle_data,
        sumcheck_data,
        rounds,
        randomness,
        final_codeword,
    )
}

/// Encodes the message the rounds played so far bound, when the sumcheck holds it.
///
/// Folding a codeword binds its message's lowest variable, so this is the codeword that folding
/// the base codeword by every challenge played so far produces, symbol for symbol.
///
/// `None` when the sumcheck does not hold that message.
fn encode_bound_message<F, EF>(
    sumcheck: &mut SuffixResidualProver<F, EF, <EF as ChallengeField<F>>::SumcheckRepr>,
    log_inv_rate: usize,
) -> Option<Vec<EF>>
where
    F: Field,
    EF: ChallengeField<F> + ExtensionField<F>,
{
    let column = sumcheck.bound_column()?;

    // The tail past the message stays zero, which is the padding the encoding reads it as.
    let mut message = EF::zero_vec(column.len() << log_inv_rate);
    EF::from_sumcheck_repr(column, &mut message[..column.len()]);
    let codeword = tracing::info_span!("encode bound message").in_scope(|| {
        EF::Encoder::default().encode_batch_padded(RowMajorMatrix::new(message, 1), log_inv_rate)
    });
    Some(codeword.values)
}

/// The query phase's prover-side output.
/// Every opening the verifier's path check needs, plus the grinding witness.
pub(crate) struct QueryProofs<F: Field, EF: Field, MT: Mmcs<F>, MX: Mmcs<EF>> {
    /// Every symbol of each queried base coset, one width-1 row per symbol.
    /// Cosets follow sampled query order; symbols inside a coset are ascending.
    pub base_opened_values: Vec<Vec<F>>,
    /// Multiproof for the base commitment's queried rows.
    pub base_multi_proof: MT::MultiProof,
    /// One entry per intermediate fold batch, excluding the final batch.
    pub rounds: Vec<RoundProof<EF, MX>>,
    /// Witness for the single grind before the query phase.
    pub pow_witness: F,
}

/// Runs the query phase: binds the full final codeword, grinds the single proof-of-work
/// witness, samples query indices from the base codeword's domain, then opens the base
/// commitment and every intermediate fold-batch commitment at all coset indices each query needs.
///
/// `rounds` is every round commitment the fold phase produced.
/// That is one per fold batch except the last, whose codeword is never committed.
///
/// The last batch travels in the clear as the proof's final codeword.
/// A Merkle path for it would only repeat what the verifier can already read.
#[tracing::instrument(name = "binary pcs open queries", skip_all)]
pub(crate) fn open_queries<F, EF, MT, MX, Ch>(
    config: &BinaryPcsConfig,
    mmcs: &MT,
    round_mmcs: &MX,
    transcript: &mut BinaryPcsProverTranscript<'_, F, EF, Ch>,
    base_merkle_data: &MT::ProverData<DenseMatrix<F>>,
    rounds: &[RoundCommitment<EF, MX>],
    final_codeword: &[EF],
) -> QueryProofs<F, EF, MT, MX>
where
    F: TranscriptField,
    EF: ExtensionField<F>,
    MT: Mmcs<F>,
    MX: Mmcs<EF>,
    Ch: FieldChallenger<F> + GrindingChallenger<Witness = F> + CanSampleUniformBits<F>,
{
    assert_eq!(
        rounds.len(),
        config.num_fold_batches() - 1,
        "rounds is the caller's own fold-phase output, never proof-supplied data"
    );

    // The last word is sent in the clear, not committed by a Merkle root. Bind every
    // symbol before grinding or sampling so it cannot be chosen after seeing queries.
    transcript.final_codeword(final_codeword);
    let pow_witness = transcript.query_pow();

    // The draw indexes pairs, so each position is lifted back to a coset start.
    let shift = config.log_folding_factor() - 1;
    let indices: Vec<usize> = transcript
        .query_pairs()
        .into_iter()
        .map(|pair| pair << shift)
        .collect();
    let base_indices = flat_coset_indices(&indices, 0, config.log_folding_factor());
    let (base_values, base_multi_proof) = mmcs.open_multi_batch(&base_indices, base_merkle_data);
    let base_opened_values = single_matrix_rows(base_values);

    let opened_rounds = rounds
        .iter()
        .zip(config.fold_batches().skip(1))
        .map(|(round, (start, arity))| {
            let round_indices = flat_coset_indices(&indices, start, arity);
            let (values, multi_proof) =
                round_mmcs.open_multi_batch(&round_indices, &round.merkle_data);
            RoundProof {
                commitment: round.commitment.clone(),
                opened_values: single_matrix_rows(values),
                multi_proof,
            }
        })
        .collect();

    QueryProofs {
        base_opened_values,
        base_multi_proof,
        rounds: opened_rounds,
        pow_witness,
    }
}

/// Strips the always-one-matrix middle index from a batched-opening result.
/// The count is asserted rather than assumed.
fn single_matrix_rows<T>(values: Vec<Vec<Vec<T>>>) -> Vec<Vec<T>> {
    values
        .into_iter()
        .map(|mut per_matrix| {
            assert_eq!(per_matrix.len(), 1, "each round commits exactly one matrix");
            per_matrix.swap_remove(0)
        })
        .collect()
}

#[cfg(test)]
mod tests {
    use alloc::vec::Vec;
    use alloc::{format, vec};

    use p3_binary_dft::{AdditiveRsEncoder, EncodableLevel, NaiveAdditiveNtt};
    use p3_binary_field::{BinaryField8, BinaryField64, BinaryField128};
    use p3_challenger::fs::TranscriptField;
    use p3_challenger::{CanObserve, CanSampleUniformBits, FieldChallenger, GrindingChallenger};
    use p3_commit::Mmcs;
    use p3_field::ExtensionField;
    use p3_matrix::dense::RowMajorMatrix;
    use p3_multilinear_util::point::Point;
    use p3_multilinear_util::poly::Poly;
    use p3_sumcheck::layout::{Layout, PrefixProver, SuffixProver, Table};
    use p3_sumcheck::{OpeningBatch, SumcheckData};
    use rand::SeedableRng;
    use rand::distr::{Distribution, StandardUniform};
    use rand::rngs::SmallRng;

    use super::{MIN_ENCODED_ARITY, commit, fold_rounds_with};
    use crate::fold::{ChallengeField, FoldAlphabet, fold_codeword, fold_codeword_batch};
    use crate::params::{BinaryPcsConfig, BinaryPcsParams};
    use crate::test_util::{
        LevelChallenger, LevelMmcs, challenger, level_challenger, level_mmcs, mmcs,
        narrow_challenger, narrow_mmcs,
    };
    use crate::transcript::{BinaryPcsProverTranscript, BinaryPcsShape};

    type F = BinaryField128;

    const NUM_VARIABLES: usize = 8;
    const LOG_INV_RATE: usize = 2;

    /// After every round, the codeword and the sumcheck describe the same polynomial: the
    /// final codeword's symbols all equal the constant the sumcheck folds to.
    #[test]
    fn the_codeword_and_the_sumcheck_stay_in_lockstep() {
        let mut rng = SmallRng::seed_from_u64(21);
        let table = Table::rand(&mut rng, 1, NUM_VARIABLES);
        let witness = SuffixProver::<F, F>::new_witness(vec![table], 0);

        let mut ch = challenger();
        let (mut layout, _root, data) = SuffixProver::<F, F>::commit(
            &AdditiveRsEncoder::<F, NaiveAdditiveNtt<F>>::default(),
            &mmcs(),
            witness,
            0,
            LOG_INV_RATE,
        );
        let m = mmcs().get_matrices(&data)[0].clone();
        assert_eq!(m.width, 1);
        let mut codeword = m.values;

        let _virtual_eval = layout.add_virtual_eval(&mut ch);
        let mut sc = SumcheckData::<F, F>::default();
        let (mut prover, head) = layout.into_sumcheck(&mut sc, 0, &mut ch);
        assert_eq!(head.num_variables(), 0);

        for _ in 0..prover.num_variables() {
            let beta = prover.compute_sumcheck_polynomials(&mut sc, &mut ch, 1, 0, None);
            codeword = fold_codeword(&codeword, beta.as_slice()[0]);
        }

        let final_value = prover.evals().as_constant().expect("fully folded");
        assert_eq!(codeword.len(), 1 << LOG_INV_RATE);
        assert!(codeword.iter().all(|&v| v == final_value));
    }

    /// The lockstep property is specific to suffix binding's evaluation-basis order.
    /// Driving the identical procedure through prefix binding breaks it.
    ///
    /// The final codeword's symbols no longer all equal the constant the sumcheck reaches.
    ///
    /// This is why the layout is a fixed type rather than a caller-supplied parameter.
    /// The two orders are not interchangeable.
    ///
    /// The difference is a property of the fold's pair-merging arithmetic, not a tuning knob.
    #[test]
    fn prefix_layout_does_not_stay_in_lockstep() {
        let mut rng = SmallRng::seed_from_u64(21);
        let table = Table::rand(&mut rng, 1, NUM_VARIABLES);
        let witness = PrefixProver::<F, F>::new_witness(vec![table], 0);

        let mut ch = challenger();
        let (mut layout, _root, data) = PrefixProver::<F, F>::commit(
            &AdditiveRsEncoder::<F, NaiveAdditiveNtt<F>>::default(),
            &mmcs(),
            witness,
            0,
            LOG_INV_RATE,
        );
        let m = mmcs().get_matrices(&data)[0].clone();
        assert_eq!(m.width, 1);
        let mut codeword = m.values;

        let _virtual_eval = layout.add_virtual_eval(&mut ch);
        let mut sc = SumcheckData::<F, F>::default();
        let (mut prover, head) = layout.into_sumcheck(&mut sc, 0, &mut ch);
        assert_eq!(head.num_variables(), 0);

        for _ in 0..prover.num_variables() {
            let beta = prover.compute_sumcheck_polynomials(&mut sc, &mut ch, 1, 0, None);
            codeword = fold_codeword(&codeword, beta.as_slice()[0]);
        }

        let final_value = prover.evals().as_constant().expect("fully folded");
        assert!(!codeword.iter().all(|&v| v == final_value));
    }

    /// Drives the crate's own commit and fold phases end to end, against an independent oracle.
    ///
    /// The oracle folds the original message variable by variable.
    /// It consumes the randomness the fold phase returns, in the order returned.
    ///
    /// The constant it reaches must be the value every final codeword symbol carries.
    #[test]
    fn commit_and_fold_rounds_match_an_independent_message_fold() {
        let mut rng = SmallRng::seed_from_u64(0xC0FFEE);
        let poly = Poly::<F>::rand(&mut rng, NUM_VARIABLES);
        let mut message = poly.clone();
        let table = Table::new(RowMajorMatrix::new(poly.into_evals(), 1 << NUM_VARIABLES));
        let witness = SuffixProver::<F, F>::new_witness(vec![table], 0);

        let params = BinaryPcsParams {
            log_inv_rate: LOG_INV_RATE,
            pow_bits: 4,
            security_level: 40,
        };
        let config = BinaryPcsConfig::try_new::<F, F>(NUM_VARIABLES, params).unwrap();
        let encoder = AdditiveRsEncoder::<F, NaiveAdditiveNtt<F>>::default();
        let mmcs_instance = mmcs();

        let mut ch = challenger();
        let (_commitment, prover_data) =
            commit::<F, F, _, _>(&config, &encoder, &mmcs_instance, witness);
        let mut transcript = BinaryPcsProverTranscript::new(&mut ch, BinaryPcsShape::new(&config));
        let (_merkle_data, _sumcheck_data, rounds, randomness, final_codeword) =
            fold_rounds_with::<false, F, F, _, _, _>(
                prover_data,
                &config,
                &mmcs_instance,
                &mmcs_instance,
                &mut transcript,
            );
        // Only the fold phase runs here, so the driver is released rather than closed.
        transcript.abort();

        assert_eq!(rounds.len(), config.num_fold_rounds() - 1);
        assert_eq!(randomness.num_variables(), NUM_VARIABLES);
        assert_eq!(final_codeword.len(), 1 << LOG_INV_RATE);

        for &beta in randomness.as_slice() {
            message.fix_suffix_var_mut(beta);
        }
        let expected = message.as_constant().expect("fully folded");
        assert!(final_codeword.iter().all(|&v| v == expected));
    }

    /// The same independent-oracle check, with the columns committed over a narrower alphabet.
    ///
    /// The base codeword holds 64-bit symbols and every folded codeword 128-bit ones.
    /// The first fold of the schedule is the one that crosses between them.
    #[test]
    fn a_narrow_alphabet_folds_to_the_same_constant_as_its_own_message() {
        let mut rng = SmallRng::seed_from_u64(0xC0FFEE);
        let table = Table::rand(&mut rng, 1, NUM_VARIABLES);

        // The message as a polynomial over the challenge field, cell for cell.
        let embedded = Poly::new(
            table
                .poly(0)
                .as_slice()
                .iter()
                .map(|&value| F::from(value))
                .collect::<alloc::vec::Vec<_>>(),
        );
        let witness = SuffixProver::<BinaryField64, F>::new_witness(vec![table], 0);

        let params = BinaryPcsParams {
            log_inv_rate: LOG_INV_RATE,
            pow_bits: 4,
            security_level: 40,
        };
        let config = BinaryPcsConfig::try_new::<BinaryField64, F>(NUM_VARIABLES, params).unwrap();
        let encoder = <BinaryField64 as EncodableLevel>::Encoder::default();

        // The sponge speaks the committed alphabet, so a narrow run needs its own challenger.
        let mut ch = narrow_challenger();
        let (_commitment, prover_data) =
            commit::<BinaryField64, F, _, _>(&config, &encoder, &narrow_mmcs(), witness);
        let mut transcript = BinaryPcsProverTranscript::new(&mut ch, BinaryPcsShape::new(&config));
        let (_merkle_data, _sumcheck_data, _rounds, randomness, final_codeword) =
            fold_rounds_with::<false, BinaryField64, F, _, _, _>(
                prover_data,
                &config,
                &narrow_mmcs(),
                &mmcs(),
                &mut transcript,
            );
        transcript.abort();

        // Binding the embedded message in the same order must reach the same constant.
        let mut message = embedded;
        for &beta in randomness.as_slice() {
            message.fix_suffix_var_mut(beta);
        }
        let expected = message.as_constant().expect("fully folded");
        assert_eq!(final_codeword.len(), 1 << LOG_INV_RATE);
        assert!(final_codeword.iter().all(|&v| v == expected));
    }

    /// Invariant: the fused route and the reference route agree on every fold round.
    ///
    ///     round messages       round commitments      folding randomness
    ///     final codeword       transcript state left behind
    ///
    /// The fold rounds are the only place the two routes differ.
    ///
    /// Everything they produce is a deterministic function of the transcript.
    ///
    /// So the comparison is reproducible under threaded execution.
    ///
    /// The query phase's grinding search is not, which is why it stays out of scope here.
    #[test]
    fn fold_rounds_agree_with_binding_each_round() {
        // Invariant: how many passes compute a round polynomial never changes its value.
        //
        //     fused    : round r measures and applies round r-1's binding in one pass
        //     reference: round r measures, then a second pass applies round r's binding
        //
        // Fixture shapes: driven twice from identically seeded challengers.
        //
        //     8  variables: every fused pass takes the serial branch
        //     15 variables: the early rounds take the threaded branch, where a fused pass
        //                   writing its own input in place would race another task's reads
        //
        // Both folding factors, because they exercise different held-challenge paths:
        //
        //     1:  every round is its own batch    ->  every held challenge crosses a batch
        //     3:  three rounds share a batch      ->  one also crosses a round boundary
        //
        // That inner boundary is where the reference route settles its binding.
        for (num_variables, log_folding_factor) in [(8usize, 1usize), (8, 3), (15, 1), (15, 3)] {
            let params = BinaryPcsParams {
                log_inv_rate: LOG_INV_RATE,
                pow_bits: 4,
                security_level: 40,
            };
            let config = BinaryPcsConfig::try_new_with_folding::<F, F>(
                num_variables,
                params,
                log_folding_factor,
            )
            .unwrap();

            // The shipped encoder, not the naive one.
            //
            // The larger arity is out of reach of a quadratic transform in a debug build.
            let encoder = AdditiveRsEncoder::<F>::default();
            let mmcs_instance = mmcs();

            let mut rng = SmallRng::seed_from_u64(0xF0FA + num_variables as u64);
            let table = Table::rand(&mut rng, 1, num_variables);
            let shape = format!("{num_variables} variables, arity {log_folding_factor}");

            // Fused route.
            let mut got_ch = challenger();
            let (_commitment, got_data) = commit::<F, F, _, _>(
                &config,
                &encoder,
                &mmcs_instance,
                SuffixProver::<F, F>::new_witness(vec![table.clone()], 0),
            );
            let mut got_t =
                BinaryPcsProverTranscript::new(&mut got_ch, BinaryPcsShape::new(&config));
            let (_, got_sumcheck, got_rounds, got_randomness, got_final) =
                fold_rounds_with::<false, F, F, _, _, _>(
                    got_data,
                    &config,
                    &mmcs_instance,
                    &mmcs_instance,
                    &mut got_t,
                );
            // Only the fold phase runs here, so the driver is released rather than closed.
            got_t.abort();
            drop(got_t);

            // Reference route, from an identically seeded challenger.
            let mut want_ch = challenger();
            let (_commitment, want_data) = commit::<F, F, _, _>(
                &config,
                &encoder,
                &mmcs_instance,
                SuffixProver::<F, F>::new_witness(vec![table], 0),
            );
            let mut want_t =
                BinaryPcsProverTranscript::new(&mut want_ch, BinaryPcsShape::new(&config));
            let (_, want_sumcheck, want_rounds, want_randomness, want_final) =
                fold_rounds_with::<true, F, F, _, _, _>(
                    want_data,
                    &config,
                    &mmcs_instance,
                    &mmcs_instance,
                    &mut want_t,
                );
            want_t.abort();
            drop(want_t);

            // Round by round first, so a discrepancy is localised to the round that drifted.
            assert_eq!(
                got_sumcheck.num_rounds(),
                want_sumcheck.num_rounds(),
                "{shape}: round count"
            );
            for (round, (got_msg, want_msg)) in got_sumcheck
                .polynomial_evaluations()
                .iter()
                .zip(want_sumcheck.polynomial_evaluations())
                .enumerate()
            {
                assert_eq!(got_msg, want_msg, "{shape}: round {round} message");
            }

            // The challenges follow the messages, and the codeword folds follow the challenges.
            assert_eq!(
                got_randomness.as_slice(),
                want_randomness.as_slice(),
                "{shape}: folding randomness"
            );
            assert_eq!(got_final, want_final, "{shape}: final codeword");
            for (round, (got_round, want_round)) in got_rounds.iter().zip(&want_rounds).enumerate()
            {
                assert_eq!(
                    got_round.commitment, want_round.commitment,
                    "{shape}: round {round} commitment"
                );
            }

            // The transcripts must also be left in the same state.
            //
            // Equal outputs do not show that on their own.
            //
            // Two challengers that diverged could still have produced the same outputs.
            assert_eq!(
                got_ch.sample_algebra_element::<F>(),
                want_ch.sample_algebra_element::<F>(),
                "{shape}: transcript state"
            );
        }
    }

    /// Runs the fold phase over one column under one direct claim, and compares every codeword it
    /// produces with folding the base codeword by the batch challenges it returns.
    ///
    /// The claim shape takes the banked residual route, which holds the bound message at its
    /// stage boundaries. Whichever of encoding and folding the phase picks per batch, every
    /// committed codeword and the final one must be the fold.
    fn check_fold_phase_codewords<const BIND_EACH_ROUND: bool, A, EF>(
        num_variables: usize,
        log_folding_factor: usize,
        log_inv_rate: usize,
        seed: u64,
    ) where
        A: EncodableLevel + TranscriptField + FoldAlphabet<EF>,
        EF: ChallengeField<A> + ExtensionField<A> + FoldAlphabet<EF>,
        LevelMmcs<A>: Mmcs<A>,
        LevelMmcs<EF>: Mmcs<EF>,
        LevelChallenger<A>: FieldChallenger<A>
            + GrindingChallenger<Witness = A>
            + CanSampleUniformBits<A>
            + CanObserve<<LevelMmcs<EF> as Mmcs<EF>>::Commitment>
            + Clone,
        StandardUniform: Distribution<A> + Distribution<EF>,
    {
        let params = BinaryPcsParams {
            log_inv_rate,
            pow_bits: 0,
            security_level: 40,
        };
        let config = BinaryPcsConfig::try_new_with_folding::<A, EF>(
            num_variables,
            params,
            log_folding_factor,
        )
        .unwrap();
        let (base_mmcs, round_mmcs) = (level_mmcs::<A>(), level_mmcs::<EF>());
        let shape = format!(
            "bits {}/{}, {num_variables} variables, arity {log_folding_factor}, rate {log_inv_rate}",
            A::bits(),
            EF::bits()
        );

        let mut rng = SmallRng::seed_from_u64(seed);
        let table = Table::<A>::rand(&mut rng, 1, num_variables);
        let (_commitment, mut prover_data) = commit::<A, EF, _, _>(
            &config,
            &A::Encoder::default(),
            &base_mmcs,
            SuffixProver::<A, EF>::new_witness(vec![table], 0),
        );
        let point = Point::<EF>::rand(&mut rng, num_variables);
        prover_data
            .layout
            .record_opening(0, &OpeningBatch::new(vec![0], Vec::new()), &point);

        // The route hands out a bound column at some round, which only the banked route does.
        // A batch folding enough rounds to be encoded ends on a round that holds one, so its
        // codeword below comes from encoding rather than from folding.
        let mut probe_ch = level_challenger::<A>();
        let mut probe_sc = SumcheckData::default();
        let (mut probe, _) = prover_data
            .layout
            .clone()
            .into_sumcheck_in::<EF::SumcheckRepr, _>(&mut probe_sc, 0, &mut probe_ch);
        let mut holds_bound_column = false;
        for (batch, (_, arity)) in config.fold_batches().enumerate() {
            for _ in 0..arity {
                let _ = probe.compute_sumcheck_polynomials(&mut probe_sc, &mut probe_ch, 1, 0);
                holds_bound_column |= probe.bound_column().is_some();
            }
            if arity >= MIN_ENCODED_ARITY {
                assert!(
                    probe.bound_column().is_some(),
                    "{shape}: batch {batch} encodes its codeword"
                );
            }
        }
        assert!(holds_bound_column, "{shape}: banked route");

        let mut ch = level_challenger::<A>();
        let mut transcript = BinaryPcsProverTranscript::new(&mut ch, BinaryPcsShape::new(&config));
        let (merkle_data, _sumcheck_data, rounds, randomness, final_codeword) =
            fold_rounds_with::<BIND_EACH_ROUND, A, EF, _, _, _>(
                prover_data,
                &config,
                &base_mmcs,
                &round_mmcs,
                &mut transcript,
            );
        transcript.abort();

        // Fold batch by batch from the base codeword, the reference every route must match.
        let base = base_mmcs.get_matrices(&merkle_data)[0].values.clone();
        let mut expected: Vec<EF> = Vec::new();
        for (batch, (start, arity)) in config.fold_batches().enumerate() {
            let challenges = &randomness.as_slice()[start..start + arity];
            expected = if batch == 0 {
                fold_codeword_batch(&base, challenges)
            } else {
                fold_codeword_batch(&expected, challenges)
            };
            let got = rounds.get(batch).map_or_else(
                || final_codeword.clone(),
                |round| {
                    round_mmcs.get_matrices(&round.merkle_data)[0]
                        .values
                        .clone()
                },
            );
            assert_eq!(got, expected, "{shape}: batch {batch}");
        }
    }

    /// Invariant: whichever of encoding the bound message and folding the previous codeword a
    /// batch takes, its codeword is the fold of the base codeword by every challenge so far.
    ///
    /// The prover commits each batch's codeword from whichever of the two it picks, and the
    /// verifier folds queried cosets of the committed codewords, so the two must never differ.
    ///
    /// Fixture state: every folding factor from one round per batch to four, both fold routes,
    /// and every challenge field over a committed alphabet as wide as itself and a narrow one.
    ///
    ///     8-bit alphabet        a 2^8 base codeword, the whole domain it spans
    ///     wider alphabets       several stages, ending on a short one, at two rates
    #[test]
    fn every_fold_phase_codeword_is_the_fold_of_the_base_codeword() {
        for (seed, log_folding_factor) in (0..).zip(1..=4) {
            for (num_variables, log_inv_rate) in [(13, 1), (13, 2)] {
                check_fold_phase_codewords::<false, F, F>(
                    num_variables,
                    log_folding_factor,
                    log_inv_rate,
                    seed,
                );
                check_fold_phase_codewords::<false, BinaryField64, F>(
                    num_variables,
                    log_folding_factor,
                    log_inv_rate,
                    seed,
                );
                check_fold_phase_codewords::<false, BinaryField64, BinaryField64>(
                    num_variables,
                    log_folding_factor,
                    log_inv_rate,
                    seed,
                );
            }
            check_fold_phase_codewords::<false, BinaryField8, BinaryField64>(
                6,
                log_folding_factor,
                2,
                seed,
            );
            check_fold_phase_codewords::<false, BinaryField8, F>(6, log_folding_factor, 2, seed);
            check_fold_phase_codewords::<true, F, F>(13, log_folding_factor, 1, seed);
            check_fold_phase_codewords::<true, BinaryField64, BinaryField64>(
                13,
                log_folding_factor,
                1,
                seed,
            );
        }
        for (seed, num_variables) in [(4, 12), (5, 16)] {
            check_fold_phase_codewords::<false, F, F>(num_variables, 4, 1, seed);
        }
        check_fold_phase_codewords::<false, F, F>(16, 8, 1, 6);
    }

    /// Committing rejects an arity mismatch in every build profile, not only a debug one.
    ///
    /// Falling through would surface later, far from the precondition that failed.
    /// It would read as a final-codeword length mismatch, or a panic inside the fold.
    #[test]
    #[should_panic(expected = "witness arity must match the config it is committed against")]
    fn commit_rejects_a_witness_arity_mismatch() {
        let params = BinaryPcsParams {
            log_inv_rate: LOG_INV_RATE,
            pow_bits: 4,
            security_level: 40,
        };
        let config = BinaryPcsConfig::try_new::<F, F>(NUM_VARIABLES, params).unwrap();
        let encoder = AdditiveRsEncoder::<F, NaiveAdditiveNtt<F>>::default();
        let mmcs_instance = mmcs();
        let mut rng = SmallRng::seed_from_u64(0);
        let table = Table::rand(&mut rng, 1, NUM_VARIABLES - 1);
        let witness = SuffixProver::<F, F>::new_witness(vec![table], 0);

        let _ = commit::<F, F, _, _>(&config, &encoder, &mmcs_instance, witness);
    }
}