binius_ip_prover/sumcheck/

padded.rs

// Copyright 2026 Irreducible Inc.
// Copyright 2026 The Binius Developers
use binius_field::Field;
use binius_ip::sumcheck::RoundCoeffs;
use binius_math::multilinear::eq::eq_one_var;

use crate::sumcheck::common::SumcheckProver;

/// Decorator that pads the number of variables of an inner [`SumcheckProver`].
///
/// Given an inner prover for the hypercube sum of an `n`-variate multilinear
/// $f(X_0, \ldots, X_{n-1}) = s$, this exposes a prover over `n + n_extra_vars` variables for the
/// equivalent claim
///
/// $$
/// f(X_0, \ldots, X_{n-1}) \cdot \text{eq}(0^{n_\text{extra}}, X_n, \ldots, X_{n+n_\text{extra}-1})
/// = s $$
///
/// Since $\text{eq}(0, \cdot)$ sums to 1 over the hypercube, this padded claim holds iff the
/// original does. This is useful for batching sumchecks with unequal numbers of variables: a
/// shorter sumcheck can be padded up to match a longer one.
///
/// The sumcheck protocol binds variables in high-index to low-index order, so the `n_extra_vars`
/// padding variables (the highest-indexed ones) are bound first. Concretely:
///
/// - In a padding round `i < n_extra_vars`, the round polynomial is $R_i(X) = s \cdot \text{eq}(0,
///   X) \cdot \prod_{k<i} \text{eq}(0, r_k)$, where $r_k$ is the $k$-th challenge. This is a
///   genuine degree-1 polynomial built without touching the inner prover. It is emitted with
///   `degree + 1` coefficients, the ones above $X^1$ zero, so a batch that contains it has the full
///   degree in every round, even when this prover is the only one of that degree.
/// - In an inner round `i \ge n_extra_vars`, the round polynomial is $R^\text{inner}_{i -
///   n_\text{extra}}(X) \cdot \prod_{k<n_\text{extra}} \text{eq}(0, r_k)$.
///
/// The accumulated equality factor $\prod_{k} \text{eq}(0, r_k)$ over the padding challenges is
/// tracked in `eq_prefix`; it stops changing once the padding rounds are done.
#[derive(Debug, Clone)]
pub struct PaddedSumcheckDecorator<F: Field, Inner> {
	inner: Inner,
	n_extra_vars: usize,
	/// The degree at which the padding rounds are emitted.
	degree: usize,
	/// Number of folds performed so far.
	round: usize,
	/// $\prod_{k < \min(\text{round}, n_\text{extra})} \text{eq}(0, r_k)$.
	eq_prefix: F,
	/// The inner prover's claimed sums, one per claim.
	///
	/// A padding round emits its polynomial from these and leaves the inner prover untouched.
	/// They are read only during the padding rounds, where the inner claims cannot have moved.
	claims: Vec<F>,
}

impl<F: Field, Inner: SumcheckProver<F>> PaddedSumcheckDecorator<F, Inner> {
	/// Wraps `inner`, padding its claim with `n_extra_vars` extra (highest-indexed) variables.
	///
	/// # Arguments
	///
	/// * `inner` - The prover whose variable count is being raised.
	/// * `n_extra_vars` - How many padding variables to prepend.
	/// * `claims` - The inner prover's claimed sums, one per claim.
	/// * `degree` - The round degree the verifier reads, at least 1. The padding rounds are emitted
	///   at this degree.
	pub const fn new(inner: Inner, n_extra_vars: usize, claims: Vec<F>, degree: usize) -> Self {
		Self {
			inner,
			n_extra_vars,
			degree,
			round: 0,
			eq_prefix: F::ONE,
			claims,
		}
	}

	/// Whether the current round binds one of the padding variables.
	const fn in_padding_phase(&self) -> bool {
		self.round < self.n_extra_vars
	}
}

impl<F: Field, Inner: SumcheckProver<F>> SumcheckProver<F> for PaddedSumcheckDecorator<F, Inner> {
	fn n_vars(&self) -> usize {
		self.inner.n_vars() + self.n_extra_vars.saturating_sub(self.round)
	}

	fn execute(&mut self) -> Vec<RoundCoeffs<F>> {
		if self.in_padding_phase() {
			// R_i(X) = (s * eq_prefix) * eq(0, X), with eq(0, X) = 1 - X, zero-extended to the
			// round degree. The inner prover is not touched during padding rounds.
			self.claims
				.iter()
				.map(|&claim| {
					let scaled = claim * self.eq_prefix;
					let mut coeffs = vec![F::ZERO; self.degree + 1];
					coeffs[0] = scaled;
					coeffs[1] = -scaled;
					RoundCoeffs(coeffs)
				})
				.collect()
		} else {
			self.inner
				.execute()
				.into_iter()
				.map(|coeffs| coeffs * self.eq_prefix)
				.collect()
		}
	}

	fn fold(&mut self, challenge: F) {
		if self.in_padding_phase() {
			// eq(0, challenge) = 1 - challenge.
			self.eq_prefix *= eq_one_var(F::ZERO, challenge);
		} else {
			self.inner.fold(challenge);
		}
		self.round += 1;
	}

	fn finish(self) -> Vec<F> {
		// The final multilinear evaluations are those of the inner prover; padding does not add
		// multilinears.
		self.inner.finish()
	}
}

#[cfg(test)]
mod tests {
	use binius_compute::GlobalAllocator;
	use binius_field::{
		Random,
		arch::{OptimalB128, OptimalPackedB128},
	};
	use binius_ip::sumcheck::{BatchSumcheckOutput, RoundCoeffs, batch_verify, verify};
	use binius_math::{
		inner_product::inner_product_par,
		multilinear::{eq::eq_one_var, evaluate::evaluate},
		test_utils::random_field_buffer,
	};
	use binius_transcript::{ProverTranscript, fiat_shamir::HasherChallenger};
	use either::Either;
	use rand::prelude::*;

	use super::*;
	use crate::sumcheck::{
		batch::batch_prove_and_write_evals,
		bivariate_product_evaluator::{BivariateProductEvaluator, bivariate_product_prover},
		prove::prove_single,
		round_evaluator::SharedSumcheckProver,
	};

	type F = OptimalB128;
	type P = OptimalPackedB128;
	type StdChallenger = HasherChallenger<sha2::Sha256>;

	fn make_inner<'alloc>(
		rng: &mut impl Rng,
		alloc: &'alloc GlobalAllocator,
		n_vars: usize,
	) -> (SharedSumcheckProver<'alloc, GlobalAllocator, P, BivariateProductEvaluator>, F) {
		let a = random_field_buffer::<P>(&mut *rng, n_vars);
		let b = random_field_buffer::<P>(&mut *rng, n_vars);
		let sum = inner_product_par(&a, &b);
		let prover = bivariate_product_prover(alloc, [a, b], sum);
		(prover, sum)
	}

	/// A degree-1 prover for the hypercube sum of one multilinear, held as its evaluations.
	struct MultilinearSumProver(Vec<F>);

	impl SumcheckProver<F> for MultilinearSumProver {
		fn n_vars(&self) -> usize {
			self.0.len().ilog2() as usize
		}

		fn execute(&mut self) -> Vec<RoundCoeffs<F>> {
			// The highest variable splits the evaluations into its X = 0 and X = 1 halves.
			let (lo, hi) = self.0.split_at(self.0.len() / 2);
			let r_0 = lo.iter().copied().sum::<F>();
			let r_1 = hi.iter().copied().sum::<F>();
			vec![RoundCoeffs(vec![r_0, r_1 - r_0])]
		}

		fn fold(&mut self, challenge: F) {
			let half = self.0.len() / 2;
			let (lo, hi) = self.0.split_at_mut(half);
			for (lo_i, &hi_i) in lo.iter_mut().zip(hi.iter()) {
				*lo_i += challenge * (hi_i - *lo_i);
			}
			self.0.truncate(half);
		}

		fn finish(self) -> Vec<F> {
			self.0
		}
	}

	/// The padding rounds emit `s * eq(0, X) * prod eq(0, r_k)`, and the inner rounds emit the
	/// inner round polynomial scaled by the same padding product.
	#[test]
	fn test_round_polynomials_closed_form() {
		let mut rng = StdRng::seed_from_u64(0);
		let n_vars = 6;
		let n_extra_vars = 3;
		let alloc = GlobalAllocator;

		let (inner, sum) = make_inner(&mut rng, &alloc, n_vars);
		// A parallel bare inner prover, driven only on the inner-phase challenges, to compare round
		// polynomials against.
		let (mut bare_inner, _) = make_inner(&mut StdRng::seed_from_u64(0), &alloc, n_vars);
		let mut padded = PaddedSumcheckDecorator::new(inner, n_extra_vars, vec![sum], 2);

		let challenges = (0..n_vars + n_extra_vars)
			.map(|_| F::random(&mut rng))
			.collect::<Vec<_>>();

		let mut eq_prefix = F::ONE;
		for (i, &challenge) in challenges.iter().enumerate() {
			assert_eq!(padded.n_vars(), n_vars + n_extra_vars - i);

			let round_coeffs = padded.execute();
			assert_eq!(round_coeffs.len(), 1);

			if i < n_extra_vars {
				// v * (1 - X) with v = s * eq_prefix, zero-extended to degree 2.
				let v = sum * eq_prefix;
				assert_eq!(round_coeffs[0], RoundCoeffs(vec![v, -v, F::ZERO]));
			} else {
				// Inner round polynomial scaled by the (now complete) padding product.
				let inner_coeffs = bare_inner.execute();
				let expected = inner_coeffs[0].clone() * eq_prefix;
				assert_eq!(round_coeffs[0], expected);
				bare_inner.fold(challenge);
			}

			padded.fold(challenge);
			if i < n_extra_vars {
				eq_prefix *= eq_one_var(F::ZERO, challenge);
			}
		}

		assert_eq!(padded.n_vars(), 0);
	}

	#[test]
	fn test_round_polynomials_preserve_the_claim() {
		// Invariant: every round polynomial sums over its endpoints to the running claim.
		//
		// This is the identity the verifier checks each round.
		// Tracking the claim here independently, as the verifier does, keeps the check honest.
		let mut rng = StdRng::seed_from_u64(1);
		let n_vars = 5;
		let n_extra_vars = 2;
		let alloc = GlobalAllocator;

		let (inner, sum) = make_inner(&mut rng, &alloc, n_vars);
		let mut padded = PaddedSumcheckDecorator::new(inner, n_extra_vars, vec![sum], 2);

		// The running claim starts at the inner prover's sum, before any padding is applied.
		let mut running = sum;
		for _ in 0..n_vars + n_extra_vars {
			let round_coeffs = padded.execute();
			assert_eq!(round_coeffs.len(), 1);
			assert_eq!(running, round_coeffs[0].sum_over_endpoints());

			// The next round's claim is this polynomial at the challenge.
			let challenge = F::random(&mut rng);
			running = round_coeffs[0].evaluate(&challenge);
			padded.fold(challenge);
		}
	}

	/// Full prove/verify roundtrip through a transcript, with the fixed-degree verifier.
	#[test]
	fn test_prove_verify_roundtrip() {
		let mut rng = StdRng::seed_from_u64(2);
		let n_vars = 7;
		let n_extra_vars = 4;
		let total_vars = n_vars + n_extra_vars;
		let alloc = GlobalAllocator;

		let a = random_field_buffer::<P>(&mut rng, n_vars);
		let b = random_field_buffer::<P>(&mut rng, n_vars);
		let sum = inner_product_par(&a, &b);
		let inner = bivariate_product_prover(&alloc, [a.clone(), b.clone()], sum);
		let padded = PaddedSumcheckDecorator::new(inner, n_extra_vars, vec![sum], 2);

		let mut prover_transcript = ProverTranscript::new(StdChallenger::default());
		let output = prove_single(padded, &mut prover_transcript);
		prover_transcript
			.message()
			.write_slice(&output.multilinear_evals);

		let mut verifier_transcript = prover_transcript.into_verifier();
		let sumcheck_output = verify(total_vars, 2, sum, &mut verifier_transcript)
			.expect("verification should succeed");
		let challenges = sumcheck_output.challenges;

		let multilinear_evals: Vec<F> = verifier_transcript.message().read_vec(2).unwrap();
		assert_eq!(output.multilinear_evals, multilinear_evals);
		assert_eq!(output.challenges, challenges);

		// The padding challenges (bound first) define the eq factor.
		let eq_pad: F = challenges[..n_extra_vars]
			.iter()
			.map(|&r| eq_one_var(F::ZERO, r))
			.product();

		// Reduced eval = A(r_inner) * B(r_inner) * prod eq(0, r_pad).
		assert_eq!(multilinear_evals[0] * multilinear_evals[1] * eq_pad, sumcheck_output.eval);

		// The inner multilinears evaluate to the claimed values at the (reversed) inner challenges.
		let mut inner_point = challenges[n_extra_vars..].to_vec();
		inner_point.reverse();
		assert_eq!(evaluate(&a, &inner_point), multilinear_evals[0]);
		assert_eq!(evaluate(&b, &inner_point), multilinear_evals[1]);
	}

	/// A padded degree-2 prover batches with a longer, unpadded degree-1 prover. The padding rounds
	/// carry the batch's degree 2, so every batched round polynomial has the degree the verifier
	/// reads.
	#[test]
	fn test_batch_padded_with_longer_lower_degree_prover() {
		let mut rng = StdRng::seed_from_u64(4);
		let n_vars = 4;
		let n_extra_vars = 3;
		let total_vars = n_vars + n_extra_vars;
		let alloc = GlobalAllocator;

		let (inner, product_sum) = make_inner(&mut rng, &alloc, n_vars);
		let padded = PaddedSumcheckDecorator::new(inner, n_extra_vars, vec![product_sum], 2);

		let m = (0..1 << total_vars)
			.map(|_| F::random(&mut rng))
			.collect::<Vec<_>>();
		let m_sum = m.iter().copied().sum::<F>();
		let linear = MultilinearSumProver(m);

		let mut prover_transcript = ProverTranscript::new(StdChallenger::default());
		let output = batch_prove_and_write_evals(
			vec![Either::Left(padded), Either::Right(linear)],
			&mut prover_transcript,
		);

		let mut verifier_transcript = prover_transcript.into_verifier();
		let BatchSumcheckOutput {
			batch_coeff,
			eval,
			challenges,
		} = batch_verify(total_vars, 2, &[product_sum, m_sum], &mut verifier_transcript)
			.expect("verification should succeed");
		let evals: Vec<F> = verifier_transcript.message().read_vec(3).unwrap();
		assert_eq!(output.challenges, challenges);

		let eq_pad: F = challenges[..n_extra_vars]
			.iter()
			.map(|&r| eq_one_var(F::ZERO, r))
			.product();

		// Reduced eval = A(r) * B(r) * prod eq(0, r_pad) + batch_coeff * M(r).
		assert_eq!(evals[0] * evals[1] * eq_pad + batch_coeff * evals[2], eval);
	}

	/// With no extra variables the decorator is a transparent passthrough.
	#[test]
	fn test_no_padding_passthrough() {
		let mut rng = StdRng::seed_from_u64(3);
		let n_vars = 6;
		let alloc = GlobalAllocator;

		let (inner, sum) = make_inner(&mut rng, &alloc, n_vars);
		let padded = PaddedSumcheckDecorator::new(inner, 0, vec![sum], 2);
		assert_eq!(padded.n_vars(), n_vars);

		let mut prover_transcript = ProverTranscript::new(StdChallenger::default());
		let output = prove_single(padded, &mut prover_transcript);
		prover_transcript
			.message()
			.write_slice(&output.multilinear_evals);

		let mut verifier_transcript = prover_transcript.into_verifier();
		let sumcheck_output =
			verify(n_vars, 2, sum, &mut verifier_transcript).expect("verification should succeed");
		let multilinear_evals: Vec<F> = verifier_transcript.message().read_vec(2).unwrap();

		assert_eq!(multilinear_evals[0] * multilinear_evals[1], sumcheck_output.eval);
		assert_eq!(output.challenges, sumcheck_output.challenges);
	}
}