Skip to main content

binius_prover/
ring_switch.rs

1// Copyright 2025 Irreducible Inc.
2// Copyright 2026 The Binius Developers
3
4use std::{array, iter, mem::MaybeUninit, ops::Deref};
5
6use binius_alloc::{Allocator, VecLike};
7use binius_core::word::Word;
8use binius_field::{
9	ExtensionField, PackedField,
10	linear_transformation::{
11		BytewiseLookupTransformationFactory, InputWrappingTransformationFactory,
12		LinearTransformationFactory, OutputWrappingTransformationFactory, Transformation,
13	},
14	packed_extension,
15};
16use binius_ip_prover::{
17	channel::IPProverChannel,
18	sumcheck::{bivariate_product_prover, prove_single},
19};
20use binius_math::{
21	FieldBuffer, FieldSlice, FieldVec,
22	inner_product::inner_product_packed,
23	multilinear::eq::{eq_ind_partial_eval, eq_ind_zero, scaled_eq_ind_partial_eval},
24	tensor_algebra::TensorAlgebra,
25};
26use binius_utils::{checked_arithmetics::log2_ceil_usize, rayon::prelude::*};
27use binius_verifier::{
28	config::{B1, B128, LOG_WORDS_PER_ELEM},
29	protocols::shift::evaluate_words_mle,
30};
31use itertools::izip;
32
33use crate::{
34	bit_matrix::{ColumnSums, LOG_WEIGHTS_PER_TABLE, RowFoldTables},
35	prove::pack_witness,
36};
37
38/// Base-2 log of the low-factor length the tensor split targets.
39///
40/// The row fold consumes a chunk of as many rows as a row has columns.
41/// So the low factor spans exactly that many rows.
42/// For 128 columns that is 16 tables of 256 field elements, or 64 KiB.
43/// That footprint stays resident in a performance core's L1 data cache across every hi-block.
44/// A wider factor needs proportionally more tables and starts missing that cache.
45pub const LOG_SPLIT_BLOCK: usize = <B128 as ExtensionField<B1>>::LOG_DEGREE;
46
47/// Number of subset-sum tables one chunk of the split fold uses.
48const N_ROW_TABLES: usize = 1 << (LOG_SPLIT_BLOCK - LOG_WEIGHTS_PER_TABLE);
49
50/// Folds the 1-bit rows of a matrix against an equality tensor supplied as two factors.
51///
52/// # Overview
53///
54/// The equality tensor over `n_lo + n_hi` coordinates factors along any coordinate split:
55///
56/// ```text
57///     tensor[hi << n_lo | lo] = eq_lo[lo] * eq_hi[hi]
58/// ```
59///
60/// Multiplication distributes over the sum, so the fold regroups exactly:
61///
62/// ```text
63///     sum_x tensor[x] * row[x]
64///       = sum_hi eq_hi[hi] * ( sum_lo eq_lo[lo] * row[hi, lo] )
65/// ```
66///
67/// Each block of the matrix folds against the low factor alone.
68/// Its result is then scaled once by that block's high-factor entry and merged.
69/// Field addition and multiplication are exact.
70/// So the result is bit-identical to folding against the materialized tensor.
71///
72/// # Why the factored form is faster
73///
74/// Both effects follow from the tables covering only the low factor, so being built once.
75///
76/// Memory traffic:
77///
78/// - The full tensor is never written or read, so only the matrix streams through.
79/// - Folding against a materialized tensor reads one tensor entry per row alongside it.
80/// - That doubles the stream for the same arithmetic.
81///
82/// Lookup count:
83///
84/// - A table built once costs nothing per row, so it can cover eight rows instead of four.
85/// - Eight-row groups halve the lookups and accumulator updates.
86/// - Those updates are what the fold is bound on, not arithmetic or bandwidth.
87/// - A table rebuilt per group cannot widen: 256 entries per group costs more than it saves.
88///
89/// The price is one multiply per row, to scale each block by its high-factor entry.
90///
91/// # Preconditions
92///
93/// * The matrix must have as many rows as the two factors have entries together.
94/// * A block must cover a whole number of packed elements, so the chunking below aligns. The
95///   exception is a matrix that fits inside one packed element, which is a single block.
96/// * The low factor must span at most one row fold chunk, which is 128 rows.
97pub fn fold_1b_rows_for_b128_split<P, Data>(
98	mat: &FieldBuffer<P, Data>,
99	eq_lo: &FieldBuffer<B128>,
100	eq_hi: &FieldBuffer<B128>,
101) -> FieldBuffer<B128>
102where
103	P: PackedField<Scalar = B128>,
104	Data: Deref<Target = [P]>,
105{
106	let log_scalar_bit_width = <B128 as ExtensionField<B1>>::LOG_DEGREE;
107	assert_eq!(mat.log_len(), eq_lo.log_len() + eq_hi.log_len()); // precondition
108	assert!(eq_lo.log_len() >= P::LOG_WIDTH || eq_hi.log_len() == 0); // precondition
109	assert!(eq_lo.log_len() <= LOG_SPLIT_BLOCK); // precondition
110
111	// One subset-sum table per group of eight rows, built once and reused by every hi-block.
112	// A low factor shorter than a full block leaves the trailing weights zero.
113	// So every row past its end is weighted zero, whatever bits that row holds:
114	// rows past the end of a block read as zero, and a matrix narrower than one packed
115	// element leaves lanes that are not rows at all.
116	let lo_tables = RowFoldTables::<B128, N_ROW_TABLES>::new(eq_lo.as_ref());
117
118	// A sub-width low factor still occupies its one packed element, so the block is that element.
119	let block_packed_len = 1 << eq_lo.log_len().saturating_sub(P::LOG_WIDTH);
120
121	(mat.as_ref().par_chunks(block_packed_len), eq_hi.as_ref().par_iter())
122		.into_par_iter()
123		.fold(
124			|| FieldBuffer::zeros(log_scalar_bit_width),
125			|mut acc, (mat_block, &eq_hi_val)| {
126				// Fold this block against the low factor alone:
127				//
128				//     block[col] = sum_lo eq_lo[lo] * bit_col(mat_block[lo])
129				//
130				// A matrix row is 128 single-bit columns, which is one full-width packed row.
131				let mut rows = P::iter_slice(mat_block);
132				let mut sums = ColumnSums::zero();
133
134				// Gather each group's rows out of the packed elements they sit in, lazily, so a
135				// group is folded as soon as it is complete.
136				// Rows past the end of the block stay zero, and lanes past the last row carry
137				// weight zero, so neither contributes.
138				// A field element and a 128-bit row of single-bit scalars share one underlier, so
139				// each view is free.
140				lo_tables.fold_into(
141					iter::repeat_with(|| {
142						array::from_fn(|_| {
143							rows.next()
144								.map(packed_extension::cast_base::<B1, _>)
145								.unwrap_or_default()
146						})
147					})
148					.take(N_ROW_TABLES),
149					&mut sums,
150				);
151
152				// Scale by this block's high-factor entry and merge.
153				// That is 128 multiplies per block, one per row.
154				sums.add_scaled_to(eq_hi_val, acc.as_mut());
155				acc
156			},
157		)
158		// A merge seeded with a partial that already exists never touches a buffer of zeros.
159		// An identity would allocate and zero one accumulator per merge, then add all of it.
160		.reduce_with(|mut lhs, rhs| {
161			for (lhs_i, &rhs_i) in izip!(lhs.as_mut(), rhs.as_ref()) {
162				*lhs_i += rhs_i;
163			}
164			lhs
165		})
166		// An empty matrix yields no partials at all, and folds to zero.
167		.unwrap_or_else(|| FieldBuffer::zeros(log_scalar_bit_width))
168}
169
170/// Builds the ring-switching equality indicator directly from the tensor's two factors.
171///
172/// # Overview
173///
174/// The indicator is the suffix equality tensor, folded bitwise by the row-batching query.
175/// Expanding that tensor and then folding it would read and rewrite a whole `2^n` buffer.
176/// This route produces each entry in one pass instead:
177///
178/// ```text
179///     out[hi << n_lo | lo] = fold(eq_lo[lo] * eq_hi[hi])
180/// ```
181///
182/// Entries at and above `n` are zero and are never computed.
183///
184/// The tensor expansion already costs one multiply per entry.
185/// So the fused product changes no operation count.
186/// It removes one full read pass and one full write pass over the `2^n` buffer.
187///
188/// ## Arguments
189///
190/// * `alloc` - the allocator the returned indicator is drawn from
191/// * `n` - the number of leading entries computed; the rest are zero
192/// * `eq_lo` - the low tensor factor
193/// * `eq_hi` - the high tensor factor
194/// * `row_batch_query` - the vector every entry is folded bitwise by
195///
196/// ## Preconditions
197///
198/// * `row_batch_query.len()` must equal 128, the extension degree of B128 over B1
199/// * `n <= 2^(eq_lo.log_len() + eq_hi.log_len())`
200/// * A block must cover a whole number of packed elements, so the chunking below aligns. The
201///   exception is an output that fits inside one packed element, which is a single block.
202pub fn rs_eq_ind_from_factors<A, P>(
203	alloc: &A,
204	n: usize,
205	eq_lo: &FieldBuffer<B128>,
206	eq_hi: &FieldBuffer<B128>,
207	row_batch_query: &FieldBuffer<B128>,
208) -> FieldVec<P, A>
209where
210	A: Allocator,
211	P: PackedField<Scalar = B128>,
212{
213	assert!(eq_lo.log_len() >= P::LOG_WIDTH || eq_hi.log_len() == 0); // precondition
214	assert_eq!(row_batch_query.log_len(), <B128 as ExtensionField<B1>>::LOG_DEGREE); // precondition
215
216	// The bitwise fold that maps a tensor entry to its indicator entry, shared by every block.
217	let transform = OutputWrappingTransformationFactory::new(
218		InputWrappingTransformationFactory::new(BytewiseLookupTransformationFactory),
219	)
220	.create(row_batch_query.as_ref());
221
222	let log_len = eq_lo.log_len() + eq_hi.log_len();
223	assert!(n <= 1 << log_len); // precondition
224	let packed_len = 1usize << log_len.saturating_sub(P::LOG_WIDTH);
225	let block_packed_len = 1 << eq_lo.log_len().saturating_sub(P::LOG_WIDTH);
226
227	// The blocks holding an entry below `n` are computed; the rest are filled with zeros.
228	let lo_len = eq_lo.as_ref().len();
229	let n_live_blocks = n.div_ceil(lo_len);
230	let block_vals = eq_hi.as_ref()[..n_live_blocks]
231		.par_iter()
232		.enumerate()
233		.map(|(hi, &eq_hi_val)| Some((n.min((hi + 1) * lo_len) - hi * lo_len, eq_hi_val)))
234		.chain(binius_utils::rayon::iter::repeat_n(None, eq_hi.as_ref().len() - n_live_blocks));
235
236	// The buffer is written exactly once, block by block, so it starts uninitialized.
237	let mut out = alloc.alloc::<P>(packed_len);
238	(out.spare_capacity_mut()[..packed_len].par_chunks_mut(block_packed_len), block_vals)
239		.into_par_iter()
240		.for_each(|(out_block, block_val)| {
241			let Some((n_live, eq_hi_val)) = block_val else {
242				out_block.fill(MaybeUninit::new(P::zero()));
243				return;
244			};
245
246			// Each slot holds P::WIDTH consecutive entries of this hi-block.
247			// Every entry below `n` is one product of the two factors, folded and written once.
248			let entry = |lo: B128| transform.transform(&(lo * eq_hi_val));
249			// `as_chunks` needs a const width, which a generic `P::WIDTH` is not.
250			#[allow(clippy::chunks_exact_to_as_chunks)]
251			let lo_chunks = eq_lo.as_ref()[..n_live].chunks_exact(P::WIDTH);
252			let dangling = lo_chunks.remainder();
253			let (full, rest) = out_block.split_at_mut(n_live / P::WIDTH);
254			for (slot, lo_chunk) in iter::zip(full, lo_chunks) {
255				slot.write(P::from_fn(|j| entry(lo_chunk[j])));
256			}
257
258			// A dangling element, at `n` or in a sub-width output, has its lanes past the last
259			// entry filled with zeros rather than left undefined. So do the slots after it.
260			let mut rest = rest.iter_mut();
261			if !dangling.is_empty() {
262				rest.next()
263					.expect("a dangling entry has a slot")
264					.write(P::from_scalars(dangling.iter().map(|&lo| entry(lo))));
265			}
266			for slot in rest {
267				slot.write(P::zero());
268			}
269		});
270	// SAFETY: the block partition covers all `packed_len` slots and every slot was written.
271	unsafe { out.set_len(packed_len) };
272
273	FieldBuffer::new(log_len, out)
274}
275
276/// Expands `point` into the two factors of its equality tensor scaled by `scale`, low factor
277/// first.
278///
279/// The `2^n` tensor itself is never materialized: both consumers read the factors directly.
280/// The low factor spans one row fold chunk, or the whole point when that is shorter. The scale
281/// enters through the high factor.
282fn expand_tensor_factors(point: &[B128], scale: B128) -> (FieldBuffer<B128>, FieldBuffer<B128>) {
283	let (point_lo, point_hi) = point.split_at(point.len().min(LOG_SPLIT_BLOCK));
284	(
285		eq_ind_partial_eval::<B128>(point_lo),
286		scaled_eq_ind_partial_eval::<B128>(point_hi, scale),
287	)
288}
289
290/// Output of ring-switching prover.
291pub struct RingSwitchOutput<A: Allocator, P: PackedField> {
292	/// The ring-switching equality indicator MLE (transparent poly for BaseFold).
293	pub rs_eq_ind: FieldVec<P, A>,
294	/// The sumcheck claim.
295	pub sumcheck_claim: P::Scalar,
296}
297
298/// Prove the ring-switching reduction.
299///
300/// Takes the packed witness and evaluation point from shift reduction, and:
301/// 1. Computes partial evaluations s_hat_v
302/// 2. Sends s_hat_v to verifier via channel
303/// 3. Samples row-batching challenges
304/// 4. Computes the ring-switching equality indicator and sumcheck claim
305///
306/// Returns the transparent polynomial and sumcheck claim for BaseFold.
307///
308/// ## Arguments
309///
310/// * `alloc` - the allocator the ring-switching equality indicator is drawn from
311/// * `packed_witness` - the packed witness buffer (B1 polynomial packed into P elements), zero at
312///   and above `n_pack`
313/// * `n_pack` - the oracle's length; the indicator vanishes above it
314/// * `eval_point` - the evaluation point from shift reduction
315/// * `channel` - the prover channel for sending/sampling
316///
317/// The claim may span more coordinates than the packed witness, when the word-index space is wider
318/// than the oracle. The witness is zero there, so the surplus coordinates contribute the scale
319/// `c = Π (1 - r_j)`, which enters every tensor entry before the row-batching fold.
320///
321/// ## Preconditions
322///
323/// * `packed_witness.log_len() + log_packing <= eval_point.len()` where log_packing is the base-2
324///   log of the extension degree of B128 over B1 (= 7)
325/// * `n_pack <= 2^packed_witness.log_len()`
326pub fn prove<A, P, Channel>(
327	alloc: &A,
328	packed_witness: FieldSlice<'_, P>,
329	n_pack: usize,
330	eval_point: &[B128],
331	channel: &mut Channel,
332) -> RingSwitchOutput<A, P>
333where
334	A: Allocator,
335	P: PackedField<Scalar = B128>,
336	Channel: IPProverChannel<B128>,
337{
338	let log_packing = <B128 as ExtensionField<B1>>::LOG_DEGREE;
339	assert!(packed_witness.log_len() + log_packing <= eval_point.len());
340	assert!(n_pack <= 1 << packed_witness.log_len());
341
342	let (eval_point_suffix, surplus) = eval_point[log_packing..].split_at(packed_witness.log_len());
343	let surplus_scale = eq_ind_zero(surplus);
344	let (eq_lo, eq_hi) = tracing::debug_span!("Expand evaluation suffix query")
345		.in_scope(|| expand_tensor_factors(eval_point_suffix, surplus_scale));
346
347	// Ring-switching partial evaluations (Method of Four Russians)
348	let s_hat_v = tracing::debug_span!("Compute ring-switching partial evaluations")
349		.in_scope(|| fold_1b_rows_for_b128_split(&packed_witness, &eq_lo, &eq_hi));
350	channel.send_many(s_hat_v.as_ref());
351
352	// Basis transpose
353	let s_hat_u = TensorAlgebra::<B1, B128>::new(s_hat_v.as_ref().to_vec())
354		.transpose()
355		.elems;
356
357	// Sample row-batching challenges
358	let r_double_prime = channel.sample_many(log_packing);
359	let eq_r_double_prime = eq_ind_partial_eval::<B128>(&r_double_prime);
360
361	// GF(2^128) reduction is F2-linear, so it commutes with XOR.
362	// Summing 128 wide products then reducing once matches reducing each term first.
363	let sumcheck_claim = inner_product_packed::<B128, B128>(
364		log_packing,
365		s_hat_u.into_iter(),
366		eq_r_double_prime.as_ref().iter().copied(),
367	);
368
369	// Compute ring-switching equality indicator (transparent poly), zero at and above `n_pack` so
370	// it vanishes above the oracle. The fold is F2-linear, so this is the indicator of the
371	// truncated tensor.
372	let rs_eq_ind =
373		tracing::debug_span!("Compute ring-switching equality indicator").in_scope(|| {
374			rs_eq_ind_from_factors::<A, P>(alloc, n_pack, &eq_lo, &eq_hi, &eq_r_double_prime)
375		});
376
377	RingSwitchOutput {
378		rs_eq_ind,
379		sumcheck_claim,
380	}
381}
382
383/// Proves the public segment's evaluation claim.
384///
385/// The shift closes over the public segment as a bit matrix, at `r_j` over the bit within a word
386/// and the low coordinates of `r_y` over the word index. The verifier holds the segment but not
387/// its bits, so the claim is stated here and reduced in two steps:
388///
389/// 1. a ring-switch onto the segment's packed form, leaving the claim `sum_x P(x) A(x)` against the
390///    ring-switching indicator;
391/// 2. a sumcheck over the packed segment's own variables, leaving one evaluation of each factor.
392///
393/// Nothing here is committed, so the verifier finishes on its own: it evaluates the packed
394/// segment's multilinear from the words it holds, and the indicator from its succinct formula.
395///
396/// ## Arguments
397///
398/// * `alloc` - the allocator the packed segment and the indicator are drawn from
399/// * `public_words` - the public segment, unpadded
400/// * `r_j` - the bit-index challenges
401/// * `r_y` - the word-index challenges, of which the segment spans the low ones
402/// * `channel` - the prover channel for sending/sampling
403///
404/// ## Preconditions
405///
406/// * `r_y` must have at least as many coordinates as the packed segment spans words
407pub fn prove_public_eval<A, P, Channel>(
408	alloc: &A,
409	public_words: &[Word],
410	r_j: &[B128],
411	r_y: &[B128],
412	channel: &mut Channel,
413) where
414	A: Allocator,
415	P: PackedField<Scalar = B128>,
416	Channel: IPProverChannel<B128>,
417{
418	// The claim is over the packed segment, so it spans whole field elements: a segment shorter
419	// than one still spans one, reading the words past its end as zero.
420	let log_public_elems = log2_ceil_usize(public_words.len()).saturating_sub(LOG_WORDS_PER_ELEM);
421	let r_y_public = &r_y[..log_public_elems + LOG_WORDS_PER_ELEM];
422
423	channel.send_one(evaluate_words_mle::<B128, B128>(public_words, r_j, r_y_public));
424
425	let packed = pack_witness::<P, _>(alloc, log_public_elems, public_words)
426		.expect("the element count is derived from the words being packed");
427	let RingSwitchOutput {
428		rs_eq_ind,
429		sumcheck_claim,
430	} = prove(alloc, packed.as_view(), 1 << log_public_elems, &[r_j, r_y_public].concat(), channel);
431
432	// The reduced claim is the sum of the two multilinears' product over the hypercube, which is
433	// what the trace's opening hands to BaseFold. Here it is discharged by the sumcheck alone: the
434	// final evaluations need no message, since the verifier computes both itself.
435	let prover = bivariate_product_prover(alloc, [packed, rs_eq_ind], sumcheck_claim);
436	prove_single(prover, channel);
437}
438
439#[cfg(test)]
440mod test {
441	use binius_alloc::GlobalAllocator;
442	use binius_field::{
443		ExtensionField, Field, Ghash128b, PackedField, PackedGhash2x128b, PackedGhash4x128b,
444		PackedSubfield, packed_extension,
445	};
446	use binius_hash::StdDigest;
447	use binius_math::{
448		FieldBuffer,
449		inner_product::{inner_product_buffers, inner_product_subfield},
450		multilinear::{eq::eq_ind_partial_eval, evaluate::evaluate_inplace},
451		test_utils::{index_to_hypercube_point, random_field_buffer, random_scalars},
452	};
453	use binius_transcript::{ProverTranscript, fiat_shamir::HasherChallenger};
454	use binius_verifier::{
455		config::B1,
456		ring_switch::{RingSwitchVerifyOutput, eval_rs_eq, verify},
457	};
458	use rand::{SeedableRng, rngs::StdRng};
459
460	use super::*;
461
462	type F = Ghash128b;
463
464	// The row fold, written straight from its definition:
465	//
466	//     out[b] = sum_r eq[r] * bit_b(row r)
467	//
468	// Only the `eq.len()` rows the weights address take part.
469	// Lanes past the last row of a sub-width buffer are not rows, so they never appear here.
470	fn naive_fold_1b_rows<P: PackedField<Scalar = F>>(mat: &FieldBuffer<P>, eq: &[F]) -> Vec<F> {
471		let mut out = vec![F::ZERO; <F as ExtensionField<B1>>::DEGREE];
472		for (r, &weight) in eq.iter().enumerate() {
473			let row = mat.get(r);
474			for (bit, out_b) in iter::zip(ExtensionField::<B1>::iter_bases(&row), &mut out) {
475				if bit == B1::ONE {
476					*out_b += weight;
477				}
478			}
479		}
480		out
481	}
482
483	// The split fold must reproduce that definition at every legal split of the point.
484	//
485	//     split:  fold(mat, eq(lo), eq(hi)) with the tensor never materialized
486	//
487	// The matrix is random packed elements, so a sub-width buffer holds unrelated data in the
488	// lanes past its last row. The fold must weight those zero and reach the same result.
489	fn check_split_fold_matches_definition<P: PackedField<Scalar = F>>(log_len: usize, seed: u64) {
490		let mut rng = StdRng::seed_from_u64(seed);
491		let mat = random_field_buffer::<P>(&mut rng, log_len);
492		let point: Vec<F> = random_scalars(&mut rng, log_len);
493
494		let expected = naive_fold_1b_rows(&mat, eq_ind_partial_eval::<F>(&point).as_ref());
495
496		// The low factor must cover whole packed elements, unless the matrix is one element.
497		// The ceiling is the 128-row chunk the row fold consumes.
498		for split_at in P::LOG_WIDTH.min(log_len)..=log_len.min(LOG_SPLIT_BLOCK) {
499			let (point_lo, point_hi) = point.split_at(split_at);
500			let eq_lo = eq_ind_partial_eval::<F>(point_lo);
501			let eq_hi = eq_ind_partial_eval::<F>(point_hi);
502
503			let split = fold_1b_rows_for_b128_split(&mat, &eq_lo, &eq_hi);
504			assert_eq!(
505				split.as_ref(),
506				expected.as_slice(),
507				"log_len={log_len}, split_at={split_at}"
508			);
509		}
510	}
511
512	#[test]
513	fn test_split_fold_matches_definition() {
514		// Row counts below, at and above one packed element, for each packing width.
515		for (i, log_len) in [0, 1, 2, 6, 7, 8].into_iter().enumerate() {
516			let seed = i as u64;
517			check_split_fold_matches_definition::<F>(log_len, seed);
518			check_split_fold_matches_definition::<PackedGhash2x128b>(log_len, seed);
519			check_split_fold_matches_definition::<PackedGhash4x128b>(log_len, seed);
520		}
521	}
522
523	// The indicator must match the verifier's succinct formula for the same polynomial.
524	//
525	//     out[i] = A(point, i)
526	//
527	// `eval_rs_eq` evaluates `A` through the tensor algebra, independently of how the prover
528	// builds the buffer, so it pins the fused route at every legal split of the point.
529	fn check_rs_eq_ind_from_factors<P: PackedField<Scalar = F>>(log_len: usize, seed: u64) {
530		let mut rng = StdRng::seed_from_u64(seed);
531		let point: Vec<F> = random_scalars(&mut rng, log_len);
532		let row_batching_challenges: Vec<F> =
533			random_scalars(&mut rng, <F as ExtensionField<B1>>::LOG_DEGREE);
534		let row_batch_query = eq_ind_partial_eval::<F>(&row_batching_challenges);
535
536		// The indicator has no chunk ceiling, so the low factor may span the whole point.
537		for split_at in P::LOG_WIDTH.min(log_len)..=log_len {
538			let (point_lo, point_hi) = point.split_at(split_at);
539			let eq_lo = eq_ind_partial_eval::<F>(point_lo);
540			let eq_hi = eq_ind_partial_eval::<F>(point_hi);
541
542			// The full length, and a truncation that ends mid-block and mid-packed-element.
543			for n in [1 << log_len, (1 << log_len) * 2 / 3] {
544				let rs_eq_ind = rs_eq_ind_from_factors::<_, P>(
545					&GlobalAllocator,
546					n,
547					&eq_lo,
548					&eq_hi,
549					&row_batch_query,
550				);
551
552				for index in 0..1 << log_len {
553					let expected = eval_rs_eq::<F>(
554						n,
555						&point,
556						&index_to_hypercube_point::<F>(log_len, index),
557						row_batch_query.as_ref(),
558					);
559					assert_eq!(
560						rs_eq_ind.get(index),
561						expected,
562						"split_at={split_at}, n={n}, index={index}"
563					);
564				}
565
566				// A sub-width buffer's trailing lanes are not entries, and the sumcheck provers
567				// downstream read them as zero, so the write must leave them zero.
568				let trailing = rs_eq_ind.as_ref()[0].iter().skip(1 << log_len);
569				assert!(
570					trailing.take(P::WIDTH).all(|lane| lane == F::ZERO),
571					"split_at={split_at}, n={n}"
572				);
573			}
574		}
575	}
576
577	#[test]
578	fn test_rs_eq_ind_from_factors() {
579		// Entry counts below, at and above one packed element, for each packing width.
580		for (i, log_len) in [0, 1, 2, 6, 7, 8].into_iter().enumerate() {
581			let seed = i as u64;
582			check_rs_eq_ind_from_factors::<F>(log_len, seed);
583			check_rs_eq_ind_from_factors::<PackedGhash2x128b>(log_len, seed);
584			check_rs_eq_ind_from_factors::<PackedGhash4x128b>(log_len, seed);
585		}
586	}
587
588	#[test]
589	fn test_out_of_range_evaluation() {
590		let mut rng = StdRng::from_seed([0; 32]);
591
592		// `eval_rs_eq` must agree with the indicator off the hypercube as well:
593		//
594		//     eval_rs_eq(z, x, q) = sum_i eq(x)[i] * rs_eq_ind[i]
595		let n_vars_big_field = 3;
596
597		// setup ring switch eq mle
598		let z_vals: Vec<F> = random_scalars(&mut rng, n_vars_big_field);
599
600		let row_batching_challenges: Vec<F> =
601			random_scalars(&mut rng, <F as ExtensionField<B1>>::LOG_DEGREE);
602
603		let row_batching_expanded_query: FieldBuffer<F> =
604			eq_ind_partial_eval(&row_batching_challenges);
605
606		let (eq_lo, eq_hi) = expand_tensor_factors(&z_vals, F::ONE);
607		let rs_eq = rs_eq_ind_from_factors::<_, F>(
608			&GlobalAllocator,
609			1 << n_vars_big_field,
610			&eq_lo,
611			&eq_hi,
612			&row_batching_expanded_query,
613		);
614
615		// out of range eval point
616		let eval_point: Vec<F> = random_scalars(&mut rng, n_vars_big_field);
617
618		// compare eval against inner product w/ eq ind mle of eval point
619
620		let tensor_expanded_eval_point = eq_ind_partial_eval::<F>(&eval_point);
621		let expected_eval = inner_product_buffers(&rs_eq, &tensor_expanded_eval_point);
622
623		let actual_eval = eval_rs_eq::<F>(
624			1 << n_vars_big_field,
625			&z_vals,
626			&eval_point,
627			row_batching_expanded_query.as_ref(),
628		);
629
630		assert_eq!(expected_eval, actual_eval);
631	}
632
633	#[test]
634	fn test_row_fold_composes_into_the_claim() {
635		let mut rng = StdRng::seed_from_u64(0);
636
637		type P = PackedGhash2x128b;
638
639		// The prover's row fold and the verifier's partial evaluation compose into the claim:
640		//
641		//     <eq(point), bits>  ==  evaluate(s_hat_v, point[..log_degree])
642		//
643		// where `s_hat_v[b] = sum_r eq(point[log_degree..])[r] * bit_b(row r)`.
644		// The low coordinates of the point index the bits within a row, the high ones the rows.
645		let n = 10;
646		let log_degree = <F as ExtensionField<B1>>::LOG_DEGREE;
647
648		// A random B1 matrix of 2^(n + log_degree) bits, and a point over the same index space.
649		let bit_matrix = random_field_buffer::<PackedSubfield<P, B1>>(&mut rng, n + log_degree);
650		let eval_point: Vec<F> = random_scalars(&mut rng, n + log_degree);
651		let (prefix, suffix) = eval_point.split_at(log_degree);
652
653		// Reference: expand the whole point and contract it against every bit.
654		let full_tensor = eq_ind_partial_eval::<F>(&eval_point);
655		let expected = inner_product_subfield(
656			PackedField::iter_slice(bit_matrix.as_ref()),
657			PackedField::iter_slice(full_tensor.as_ref()),
658		);
659
660		// Prover route: fold the rows against the suffix factors, then evaluate at the prefix.
661		// Viewing 128 single-bit scalars as one field element is a reinterpretation, so the rows
662		// are the same memory.
663		let mat = FieldBuffer::<P>::new(
664			n,
665			bit_matrix
666				.as_ref()
667				.iter()
668				.map(|&bits_packed| packed_extension::cast_ext::<B1, P>(bits_packed))
669				.collect(),
670		);
671		let (eq_lo, eq_hi) = expand_tensor_factors(suffix, F::ONE);
672		let s_hat_v = fold_1b_rows_for_b128_split(&mat, &eq_lo, &eq_hi);
673
674		assert_eq!(evaluate_inplace(s_hat_v, prefix), expected);
675	}
676
677	#[test]
678	fn a_short_oracle_with_surplus_coordinates_ring_switches() {
679		type P = PackedGhash2x128b;
680		type StdChallenger = HasherChallenger<StdDigest>;
681
682		// An oracle of 2^4 packed elements holding 11, claimed over a word-index space two
683		// coordinates wider than the oracle.
684		let (n_vars, n_pack, n_surplus) = (4, 11, 2);
685		let log_degree = <F as ExtensionField<B1>>::LOG_DEGREE;
686		let mut rng = StdRng::seed_from_u64(0);
687		let mut witness = random_field_buffer::<P>(&mut rng, n_vars);
688		for i in n_pack..1 << n_vars {
689			witness.set(i, F::ZERO);
690		}
691		let eval_point: Vec<F> = random_scalars(&mut rng, log_degree + n_vars + n_surplus);
692
693		// The claim is the witness bits over the wider space, where it is zero above the oracle.
694		let (inner_point, surplus) = eval_point.split_at(log_degree + n_vars);
695		let bits = PackedField::iter_slice(witness.as_ref())
696			.flat_map(|elem| ExtensionField::<B1>::iter_bases(&elem).collect::<Vec<_>>());
697		let tensor = eq_ind_partial_eval::<F>(inner_point);
698		let evaluation_claim = iter::zip(bits, tensor.iter_scalars())
699			.map(|(bit, weight)| weight * bit)
700			.sum::<F>()
701			* surplus.iter().map(|&r| F::ONE - r).product::<F>();
702
703		let mut prover_transcript = ProverTranscript::new(StdChallenger::default());
704		let RingSwitchOutput {
705			rs_eq_ind,
706			sumcheck_claim,
707		} = prove(&GlobalAllocator, witness.as_view(), n_pack, &eval_point, &mut prover_transcript);
708
709		let mut verifier_transcript = prover_transcript.into_verifier();
710		let RingSwitchVerifyOutput {
711			eq_r_double_prime,
712			sumcheck_claim: verifier_claim,
713		} = verify(evaluation_claim, &eval_point, &mut verifier_transcript).unwrap();
714
715		assert_eq!(verifier_claim, sumcheck_claim);
716		assert_eq!(inner_product_buffers(&witness, &rs_eq_ind), sumcheck_claim);
717		assert!(
718			rs_eq_ind
719				.iter_scalars()
720				.skip(n_pack)
721				.all(|value| value == F::ZERO)
722		);
723
724		// The verifier's succinct indicator agrees with the prover's buffer off the hypercube.
725		let query: Vec<F> = random_scalars(&mut rng, n_vars);
726		assert_eq!(
727			eval_rs_eq(n_pack, &eval_point[log_degree..], &query, &eq_r_double_prime),
728			inner_product_buffers(&rs_eq_ind, &eq_ind_partial_eval::<P>(&query)),
729		);
730	}
731}