binius_core/ring_switch/

common.rs

// Copyright 2024-2025 Irreducible Inc.

use std::sync::Arc;

use binius_field::{Field, TowerField};
use binius_utils::sparse_index::SparseIndex;

use super::error::Error;
use crate::{
	oracle::MultilinearPolyOracle, piop::CommitMeta,
	protocols::evalcheck::EvalcheckMultilinearClaim,
};

/// A prefix of an evaluation claim query.
///
/// For an evaluation point $(z_0, ..., z_\ell)$, the prefix is $(z_0, ..., z_{\kappa-1})$, where
/// $\kappa$ is the binary logarithm of the embedding degree.
#[derive(Debug)]
pub struct EvalClaimPrefixDesc<F: Field> {
	pub prefix: Vec<F>,
}

impl<F: Field> EvalClaimPrefixDesc<F> {
	pub fn kappa(&self) -> usize {
		self.prefix.len()
	}
}

/// A suffix of an evaluation claim query.
///
/// For an evaluation point $(z_0, ..., z_\ell)$, the prefix is $(z_\kappa, ..., z_{\ell-1})$,
/// where $\kappa$ is the binary logarithm of the embedding degree.
#[derive(Debug)]
pub struct EvalClaimSuffixDesc<F: Field> {
	pub suffix: Arc<[F]>,
	pub kappa: usize,
}

/// An incomplete [`crate::piop::PIOPSumcheckClaim`] for which the sum has not been determined yet.
#[derive(Debug)]
pub struct PIOPSumcheckClaimDesc<'a, F: Field> {
	/// Index of the committed multilinear, referencing the commit metadata.
	pub committed_idx: usize,
	/// Index of the suffix descriptor, referencing the slice in an [`EvalClaimSystem`].
	pub suffix_desc_idx: usize,
	pub eval_claim: &'a EvalcheckMultilinearClaim<F>,
}

/// A system of relations required to verify multilinear evaluation claims using the batched
/// FRI-Binius protocol.
///
/// Fields are public because this is internal to the module.
#[derive(Debug)]
pub struct EvalClaimSystem<'a, F: Field> {
	pub commit_meta: &'a CommitMeta,
	pub prefix_descs: Vec<EvalClaimPrefixDesc<F>>,
	pub suffix_descs: Vec<EvalClaimSuffixDesc<F>>,
	pub sumcheck_claim_descs: Vec<PIOPSumcheckClaimDesc<'a, F>>,
	pub eval_claim_to_prefix_desc_index: Vec<usize>,
}

impl<'a, F: TowerField> EvalClaimSystem<'a, F> {
	/// Constructs a new system of claim relations.
	///
	/// ## Arguments
	///
	/// * `commit_meta` - metadata about the polynomial commitment.
	/// * `oracle_to_commit_index` - a sparse index mapping oracle IDs to IDs in the commit
	///     metadata.
	/// * `eval_claims` - the evaluation claims on committed multilinear polynomials.
	pub fn new(
		commit_meta: &'a CommitMeta,
		oracle_to_commit_index: SparseIndex<usize>,
		eval_claims: &'a [EvalcheckMultilinearClaim<F>],
	) -> Result<Self, Error> {
		// Sort evaluation claims in ascending order by number of packed variables. This must
		// happen before we do any further index mapping.
		let mut eval_claims = eval_claims.iter().collect::<Vec<_>>();
		eval_claims.sort_by_key(|claim| match claim.poly {
			// The number of packed variables is n_vars + tower_level - F::TOWER_LEVEL. Just use
			// n_vars + tower_level as the sort key because we haven't checked that the subtraction
			// wouldn't underflow yet.
			MultilinearPolyOracle::Committed {
				n_vars,
				tower_level,
				..
			} => n_vars + tower_level,
			// Ignore any non-committed oracles for now, they'll be caught later in a context where
			// we can return an error.
			_ => 0,
		});

		let (
			prefix_descs,
			eval_claim_to_prefix_desc_index,
			suffix_descs,
			eval_claim_to_suffix_desc_index,
		) = group_claims_by_eval_point(&eval_claims)?;

		let sumcheck_claim_descs = eval_claims
			.into_iter()
			.enumerate()
			.map(|(i, eval_claim)| {
				let MultilinearPolyOracle::Committed { oracle_id, .. } = eval_claim.poly else {
					return Err(Error::EvalcheckClaimForDerivedPoly {
						id: eval_claim.poly.id(),
					});
				};
				let committed_idx =
					oracle_to_commit_index
						.get(oracle_id)
						.copied()
						.ok_or_else(|| Error::OracleToCommitIndexMissingEntry {
							id: eval_claim.poly.id(),
						})?;
				let suffix_desc_idx = eval_claim_to_suffix_desc_index[i];
				Ok(PIOPSumcheckClaimDesc {
					committed_idx,
					suffix_desc_idx,
					eval_claim,
				})
			})
			.collect::<Result<Vec<_>, _>>()?;

		Ok(Self {
			commit_meta,
			prefix_descs,
			suffix_descs,
			sumcheck_claim_descs,
			eval_claim_to_prefix_desc_index,
		})
	}

	pub fn max_claim_kappa(&self) -> usize {
		self.prefix_descs
			.iter()
			.map(|desc| desc.kappa())
			.max()
			.unwrap_or(0)
	}
}

#[allow(clippy::type_complexity)]
fn group_claims_by_eval_point<F: TowerField>(
	claims: &[&EvalcheckMultilinearClaim<F>],
) -> Result<(Vec<EvalClaimPrefixDesc<F>>, Vec<usize>, Vec<EvalClaimSuffixDesc<F>>, Vec<usize>), Error>
{
	let mut prefix_descs = Vec::<EvalClaimPrefixDesc<F>>::new();
	let mut suffix_descs = Vec::<EvalClaimSuffixDesc<F>>::new();
	let mut claim_to_prefix_index = Vec::with_capacity(claims.len());
	let mut claim_to_suffix_index = Vec::with_capacity(claims.len());
	for claim in claims {
		let MultilinearPolyOracle::Committed {
			oracle_id: id,
			tower_level,
			..
		} = claim.poly
		else {
			return Err(Error::EvalcheckClaimForDerivedPoly {
				id: claim.poly.id(),
			});
		};
		let kappa = F::TOWER_LEVEL.checked_sub(tower_level).ok_or_else(|| {
			Error::OracleTowerLevelTooHigh {
				id,
				max: F::TOWER_LEVEL,
			}
		})?;

		let (prefix, suffix) = claim.eval_point.split_at(kappa);

		let prefix_id = prefix_descs
			.iter()
			.position(|desc| desc.prefix == prefix)
			.unwrap_or_else(|| {
				let index = prefix_descs.len();
				prefix_descs.push(EvalClaimPrefixDesc {
					prefix: prefix.to_vec(),
				});
				index
			});
		claim_to_prefix_index.push(prefix_id);

		let suffix_id = suffix_descs
			.iter()
			.position(|desc| &*desc.suffix == suffix && desc.kappa == kappa)
			.unwrap_or_else(|| {
				let index = suffix_descs.len();
				suffix_descs.push(EvalClaimSuffixDesc {
					suffix: suffix.to_vec().into(),
					kappa,
				});
				index
			});
		claim_to_suffix_index.push(suffix_id);
	}
	Ok((prefix_descs, claim_to_prefix_index, suffix_descs, claim_to_suffix_index))
}