Skip to main content

binius_prover/protocols/shift/
phase_1.rs

1// Copyright 2025 Irreducible Inc.
2// Copyright 2026 The Binius Developers
3
4use std::{iter, ops::Deref};
5
6use binius_alloc::Allocator;
7use binius_core::word::Word;
8use binius_field::{BinaryField, Field, PackedField, WideMul};
9use binius_ip::sumcheck::RoundCoeffs;
10use binius_ip_prover::{
11	channel::IPProverChannel,
12	sumcheck::{
13		ProveSingleOutput, bivariate_product_evaluator::BivariateProductEvaluator,
14		bivariate_product_prover, common::SumcheckProver, prove_single, round_evals::RoundEvals,
15		round_evaluator::SharedSumcheckProver,
16	},
17};
18use binius_math::{FieldBuffer, FieldVec, multilinear::fold::fold_highest_var_inplace};
19use binius_verifier::protocols::shift::LOG_SHIFT_COUNT;
20use tracing::instrument;
21
22use super::{
23	SegmentWords,
24	claims::PreparedOperandClaims,
25	key_collection::{DenseShiftEncoding, KeyCollection},
26	monster::shift_operator_table,
27	outer::OuterShiftStage,
28	shift_ind::ShiftChallenge,
29};
30
31/// Proves the first phase of the shift reduction.
32///
33/// Builds the witness-and-batching multilinear for both segments and concatenates their rows.
34/// One sumcheck then runs over their product, against a weight table that is never materialized.
35///
36/// # Arguments
37///
38/// - `key_collection`: the prover's key collection for the constraint system.
39/// - `words`: the value-vector words.
40/// - `prepared`: the prepared claim of each operation, indexed by the operation a key names.
41/// - `oblong_weights`: the weights of the reduction's first factor, one per bit position.
42/// - `channel`: the prover channel the interactive rounds run over.
43/// - `alloc`: the allocator the intermediate buffers are drawn from.
44///
45/// # Returns
46///
47/// The challenge point split into its axes, alongside the leftover weights.
48/// Also the two evaluations this phase reduced to.
49#[instrument(skip_all, name = "prover_phase_1")]
50pub fn prove_phase_1<F, P, Channel, A>(
51	key_collection: &KeyCollection,
52	words: SegmentWords<'_>,
53	prepared: &PreparedOperandClaims<F>,
54	oblong_weights: &[F],
55	channel: &mut Channel,
56	alloc: &A,
57) -> Phase1Output<F>
58where
59	F: BinaryField,
60	P: PackedField<Scalar = F>,
61	Channel: IPProverChannel<F>,
62	A: Allocator,
63{
64	// Accumulate the witness-and-batching rows of the public and hidden segments separately.
65	// The public words are the prefix of the value vector.
66	// Each segment's key ranges are relative to its own segment.
67	let public = key_collection
68		.public
69		.build_g::<_, P>(words.public, prepared);
70	let hidden = key_collection
71		.hidden
72		.build_g::<_, P>(words.hidden, prepared);
73	let g = SparseShiftRows::from_segments([
74		(&public, &key_collection.public.dense_shift_enc),
75		(&hidden, &key_collection.hidden.dense_shift_enc),
76	]);
77
78	g.run_phase_1_sumcheck(oblong_weights, prepared.batched_eval, channel, alloc)
79}
80
81/// The number of variables the shift-and-bit phases of the reduction span: the bit position
82/// within a word, the inner shift slot, and the outer shift slot.
83///
84/// No table the prover ever builds spans all three axes at once — avoiding that table is why
85/// the outer-slot rounds exist.
86pub const PHASE_1_LOG_LEN: usize = Word::LOG_BITS + LOG_SHIFT_ROWS;
87
88/// The number of variables of the row-index axis: two shift slots, since a term names two
89/// shifts applied in sequence.
90///
91/// The slots are ordered outer-major, so the rounds binding this axis peel the outer shift
92/// first.
93pub const LOG_SHIFT_ROWS: usize = 2 * LOG_SHIFT_COUNT;
94
95/// The number of variables one shift-weight table spans: one row of weights per (shift
96/// variant, shift amount) pair, one weight per bit position within a word.
97pub const SHIFT_OPERATOR_LOG_LEN: usize = Word::LOG_BITS + LOG_SHIFT_COUNT;
98
99/// The output of the first proving phase.
100///
101/// The challenge point the phase's rounds bound, split into its axes, plus the two
102/// evaluations the reduction still needs to carry forward.
103#[derive(Debug, Clone)]
104pub struct Phase1Output<F> {
105	/// The bit position within a word.
106	pub r_j: Vec<F>,
107	/// The inner shift's amount and variant.
108	pub inner: ShiftChallenge<F>,
109	/// The outer shift's amount and variant.
110	pub outer: ShiftChallenge<F>,
111	/// The weights carried through the outer shift, at the outer challenge point.
112	///
113	/// Read by the next phase's bit-index rounds.
114	pub psi: Vec<F>,
115	/// The evaluation claim the next phase proves: the product of the two evaluations below.
116	pub gamma: F,
117	/// The witness-and-batching multilinear, evaluated at the bound shift and bit point.
118	///
119	/// Carried through the remaining phases' rounds, so it is never recomputed.
120	pub g_eval: F,
121}
122
123/// The number of packed elements one row of `Word::BITS` scalars occupies.
124pub(super) const fn row_len<P: PackedField>() -> usize {
125	assert!(
126		P::LOG_WIDTH <= Word::LOG_BITS,
127		"a row of `Word::BITS` scalars must be a whole number of packed elements"
128	);
129	Word::BITS >> P::LOG_WIDTH
130}
131
132/// The nonzero rows of the witness-and-batching multilinear that a constraint system's shifts
133/// reach: one row of weights per (shift variant, shift amount) pair actually named, each
134/// tagged with its row index.
135///
136/// A constraint system only ever names a few dozen pairs — 16 for a SHA-256 circuit, 40 for
137/// Keccak.
138///
139/// Rows at a repeated index add up wherever the multilinear is read, so two segments' rows can
140/// simply concatenate here with no deduplication step.
141#[derive(Debug, Clone)]
142pub struct SparseShiftRows<P: PackedField> {
143	/// The row index of each stored row, in the same order as the row values below.
144	///
145	/// An index can repeat.
146	indices: Vec<u32>,
147	/// The stored rows end to end, in the same order as the indices above.
148	values: Vec<P>,
149	/// The number of row-index variables the sumcheck has yet to bind.
150	log_rows: usize,
151}
152
153impl<P: PackedField> SparseShiftRows<P> {
154	/// Collects the rows two key segments accumulated, tagged with the shift index each sits at.
155	///
156	/// Each segment's rows arrive in its own dense encoding order, which decodes each position
157	/// back to the shift index this list keys on.
158	/// The two segments' rows simply concatenate: a shift both use appears twice, and the two
159	/// rows add up wherever the multilinear is read later.
160	///
161	/// # Panics
162	///
163	/// Panics unless each segment's row count matches what its encoding accounts for.
164	pub fn from_segments(segments: [(&[P], &DenseShiftEncoding); 2]) -> Self {
165		let mut indices = Vec::new();
166		let mut values = Vec::new();
167
168		// Each segment contributes its own rows, tagged with its own shift indices.
169		for (rows, dense_shift_enc) in segments {
170			assert_eq!(
171				rows.len(),
172				dense_shift_enc.len() * row_len::<P>(),
173				"a segment holds one row per shift its encoding names"
174			);
175			// Decode each stored row's position back to the shift index it belongs to.
176			indices.extend(dense_shift_enc.shift_indices().map(|index| index as u32));
177			// Rows just concatenate: a shift both segments use simply appears twice.
178			values.extend_from_slice(rows);
179		}
180
181		Self::new(indices, values, LOG_SHIFT_ROWS)
182	}
183
184	/// Collects stored rows sitting at the given indices of a row space `log_rows` variables
185	/// wide.
186	///
187	/// An index can repeat: rows at a repeated index add up wherever the multilinear is read
188	/// later.
189	///
190	/// # Panics
191	///
192	/// Panics unless there is one row of values per index and every index fits the row space.
193	pub fn new(indices: Vec<u32>, values: Vec<P>, log_rows: usize) -> Self {
194		assert_eq!(
195			values.len(),
196			indices.len() * row_len::<P>(),
197			"the values hold one row per index"
198		);
199		assert!(
200			indices
201				.iter()
202				.all(|&index| (index as usize) < 1 << log_rows),
203			"every index names a row of the space"
204		);
205
206		Self {
207			indices,
208			values,
209			log_rows,
210		}
211	}
212
213	/// The number of row-index variables the sumcheck has yet to bind.
214	pub(crate) const fn log_rows(&self) -> usize {
215		self.log_rows
216	}
217
218	/// The stored rows, each with the row index it sits at.
219	#[allow(clippy::chunks_exact_to_as_chunks)] // `row_len::<P>()` is not a const generic arg
220	pub(crate) fn rows(&self) -> impl Iterator<Item = (usize, &[P])> {
221		iter::zip(&self.indices, self.values.chunks_exact(row_len::<P>()))
222			.map(|(&index, row)| (index as usize, row))
223	}
224
225	/// The index-space bit the next round binds, separating the two halves of the row space.
226	///
227	/// # Panics
228	///
229	/// Panics unless at least one row-index variable remains to bind.
230	pub(crate) fn half(&self) -> usize {
231		assert!(self.log_rows > 0, "precondition: a row-index variable remains to bind");
232		1 << (self.log_rows - 1)
233	}
234
235	/// Binds the highest row-index variable to a challenge.
236	///
237	/// Folding is linear, so a row keeps its identity across it: it is scaled by the challenge
238	/// weight of its half, then moved down into the folded index space.
239	/// The list stays the same length, with nothing paired up or merged.
240	///
241	/// # Panics
242	///
243	/// Panics unless at least one row-index variable remains to bind.
244	pub(crate) fn fold(&mut self, challenge: P::Scalar) {
245		let half = self.half();
246		let lower_weight = P::broadcast(P::Scalar::ONE - challenge);
247		let upper_weight = P::broadcast(challenge);
248
249		let row_len = row_len::<P>();
250		// Every stored row moves on its own: the fold is linear, so no row needs its
251		// counterpart from the other half to update.
252		for (position, index) in self.indices.iter_mut().enumerate() {
253			let row = &mut self.values[position * row_len..][..row_len];
254			if *index as usize & half == 0 {
255				// Lower half: scale by `1 - challenge` and keep the same index.
256				row.iter_mut().for_each(|value| *value *= lower_weight);
257			} else {
258				// Upper half: scale by `challenge` and fold the index into the lower half.
259				row.iter_mut().for_each(|value| *value *= upper_weight);
260				*index ^= half as u32;
261			}
262		}
263
264		self.log_rows -= 1;
265	}
266
267	/// Collapses every remaining row-index variable into one dense row over the bit position:
268	/// the sum of the stored rows, now that they all sit at the same index.
269	///
270	/// # Panics
271	///
272	/// Panics unless every row-index variable is already bound.
273	fn into_bit_multilinear<A: Allocator>(self, alloc: &A) -> FieldVec<P, A> {
274		assert_eq!(self.log_rows, 0, "precondition: every row-index variable is bound");
275
276		let mut multilinear = FieldBuffer::zeros_in(alloc, Word::LOG_BITS);
277		// Every stored row now sits at the same index, so they all add into one dense row.
278		for (_, row) in self.rows() {
279			for (slot, &value) in iter::zip(multilinear.as_mut(), row) {
280				*slot += value;
281			}
282		}
283		multilinear
284	}
285
286	/// Computes one round message of the phase-1 sumcheck over the row index.
287	///
288	/// Sampled at 1 and at infinity, with the claim supplying the value at 0.
289	/// Both samples are linear in the stored rows, so each row contributes independently and
290	/// facing rows across the split never have to be paired up.
291	///
292	/// ```text
293	/// R(1)   = sum_v G_1(v) H_1(v)             row (i, c) adds <c, h[i]>, upper half only
294	/// R(inf) = sum_v (G_0 + G_1)(H_0 + H_1)    row (i, c) adds <c, h[i] + h[i ^ half]>, either half
295	/// ```
296	fn round_coeffs<F, Data>(&self, h: &FieldBuffer<P, Data>, claim: F) -> RoundCoeffs<F>
297	where
298		F: Field,
299		P: PackedField<Scalar = F>,
300		Data: Deref<Target = [P]>,
301	{
302		let half = self.half();
303		let row_len = row_len::<P>();
304		let h_rows = h.as_ref();
305
306		// The per-point products accumulate in unreduced (wide) form and reduce once at the
307		// end.
308		let mut y_1 = <P as WideMul>::Output::default();
309		let mut y_inf = <P as WideMul>::Output::default();
310		for (index, row) in self.rows() {
311			let own = &h_rows[index * row_len..][..row_len];
312			let facing = &h_rows[(index ^ half) * row_len..][..row_len];
313
314			for i in 0..row_len {
315				// The infinity evaluation reads H(0) + H(1), the same sum from either half.
316				// So a row's own half only decides its contribution to the evaluation at 1.
317				if index & half != 0 {
318					y_1 += P::wide_mul(row[i], own[i]);
319				}
320				y_inf += P::wide_mul(row[i], own[i] + facing[i]);
321			}
322		}
323
324		// A row is a whole number of packed elements, so every lane of the accumulators is
325		// live.
326		let sum_lanes = |wide| P::reduce(wide).iter().sum::<F>();
327		RoundEvals([sum_lanes(y_1), sum_lanes(y_inf)]).interpolate(claim)
328	}
329
330	/// Runs the phase-1 sumcheck over the product of this row list and a weight table.
331	///
332	/// This row list is zero outside the rows a constraint system's shifts name, dense within
333	/// a named row.
334	/// A weight table holding one row per possible shift sequence would need `2^24` entries
335	/// and is never built:
336	///
337	/// - The rounds binding the outer shift slot read only the stored rows, so their cost follows
338	///   the shifts the constraint system names, not the whole space.
339	/// - Once the outer slot is bound, both multilinears are one dense row, and a shared
340	///   dense-product prover runs the remaining rounds.
341	///
342	/// Every round message matches what a fully dense prover would send.
343	///
344	/// The outer rounds run here, rather than inside that dense-product prover, because the
345	/// weights they leave behind must outlive it: the next phase's rounds run against those
346	/// same weights.
347	///
348	/// # Arguments
349	///
350	/// - `oblong_weights`: the weights of the reduction's first factor, one per bit position.
351	/// - `sum`: the claim being proved, which must equal the true product exactly when the witness
352	///   satisfies the constraint system.
353	///
354	/// # Returns
355	///
356	/// The challenge point split into its axes, the leftover weights, and the two evaluations
357	/// this phase reduced to.
358	#[instrument(skip_all, name = "run_sumcheck")]
359	pub fn run_phase_1_sumcheck<F, Channel, A>(
360		mut self,
361		oblong_weights: &[F],
362		sum: F,
363		channel: &mut Channel,
364		alloc: &A,
365	) -> Phase1Output<F>
366	where
367		F: BinaryField,
368		P: PackedField<Scalar = F>,
369		Channel: IPProverChannel<F>,
370		A: Allocator,
371	{
372		assert_eq!(self.log_rows(), LOG_SHIFT_ROWS, "the row list spans both shift slots");
373
374		// Phase 1a: bind the outer shift slot, one round at a time.
375		//
376		// Each round asks the outer-slot driver for the round polynomial, sends it, samples
377		// the challenge, then folds both the driver and the row list by that challenge.
378		let mut outer = OuterShiftStage::new(alloc, oblong_weights);
379		let mut claim = sum;
380		let mut outer_point = Vec::with_capacity(LOG_SHIFT_COUNT);
381		for _ in 0..LOG_SHIFT_COUNT {
382			let round_coeffs = outer.round_coeffs(&self, claim);
383			channel.send_many(round_coeffs.clone().truncate().coeffs());
384			let challenge = channel.sample();
385			claim = round_coeffs.evaluate(&challenge);
386			outer.fold(challenge);
387			self.fold(challenge);
388			outer_point.push(challenge);
389		}
390		// The weights the outer rounds leave behind: what the next phase runs against.
391		let psi = outer.psi().to_vec();
392
393		// Phase 1b: bind the inner shift slot and the bit position.
394		//
395		// What is left is one shift slot and the bit position, against the weight table built
396		// from the outer rounds' leftover weights.
397		let h = shift_operator_table(alloc, &psi);
398
399		// The row list itself becomes the sparse half of the row-and-bit sumcheck prover.
400		let g = self;
401		let ProveSingleOutput {
402			multilinear_evals,
403			mut challenges,
404		} = prove_single(Phase1SumcheckProver::new(g, h, claim, alloc), channel);
405
406		// The rounds bind coordinates from the most significant one down.
407		// Reversing recovers the evaluation point in increasing order of significance: the bit
408		// position, then the inner slot's amount and variant, then the outer slot's.
409		challenges.reverse();
410		assert_eq!(challenges.len(), SHIFT_OPERATOR_LOG_LEN);
411		let mut r_j = challenges;
412		let r_v_inner = r_j.split_off(Word::LOG_BITS * 2);
413		let r_s_inner = r_j.split_off(Word::LOG_BITS);
414
415		outer_point.reverse();
416		let mut r_s_outer = outer_point;
417		let r_v_outer = r_s_outer.split_off(Word::LOG_BITS);
418
419		let [g_eval, h_eval] = multilinear_evals
420			.try_into()
421			.expect("prover has 2 multilinear polynomials");
422
423		Phase1Output {
424			r_j,
425			inner: ShiftChallenge::new(r_s_inner, r_v_inner),
426			outer: ShiftChallenge::new(r_s_outer, r_v_outer),
427			psi,
428			gamma: g_eval * h_eval,
429			g_eval,
430		}
431	}
432}
433
434/// A sumcheck prover for the product of a sparse row list and a dense weight table, both
435/// spanning one shift slot and the bit position.
436///
437/// The row list is zero outside the rows a constraint system's shifts name, dense within a
438/// named row.
439/// So this prover changes strategy halfway through:
440///
441/// - While the row index has unbound variables, each round reads only the stored rows, at a cost
442///   that follows how many shifts the constraint system names, not the whole row space.
443/// - Once the row index is bound, both multilinears are one dense row, and a shared dense-product
444///   prover takes over.
445///
446/// Every round message matches what a fully dense prover would send.
447///
448/// # Performance
449///
450/// Both the sampled evaluations and the fold are linear in the sparse row list, so each
451/// stored row contributes independently, walking whole packed rows rather than individual
452/// scalar points.
453pub struct Phase1SumcheckProver<'alloc, A: Allocator, P: PackedField> {
454	alloc: &'alloc A,
455	/// The stage the protocol is in.
456	///
457	/// Always holds a value between calls, only briefly emptied while the row-stage buffers
458	/// move into the bit-stage prover.
459	stage: Option<Stage<'alloc, A, P>>,
460}
461
462/// Which half of the protocol the prover is in.
463enum Stage<'alloc, A: Allocator, P: PackedField> {
464	/// Binding the row index, over the rows the sparse list stores.
465	Rows {
466		g: SparseShiftRows<P>,
467		h: FieldVec<P, A>,
468		/// This round's sum claim.
469		claim: P::Scalar,
470		/// The round polynomial.
471		///
472		/// Set once the round's message is produced, and cleared again once the challenge
473		/// that reduces it to the next claim arrives.
474		coeffs: Option<RoundCoeffs<P::Scalar>>,
475	},
476	/// Binding the bit position, with both multilinears now one dense row.
477	Bits(SharedSumcheckProver<'alloc, A, P, BivariateProductEvaluator>),
478}
479
480impl<'alloc, A: Allocator, F: Field, P: PackedField<Scalar = F>>
481	Phase1SumcheckProver<'alloc, A, P>
482{
483	/// Creates a prover for the claim that the two multilinears' product sums to the given
484	/// value over the hypercube.
485	///
486	/// The outer shift slot is already bound by the time this runs, so the dense multilinear
487	/// is the weight table over the weights those rounds left behind, and the row list's
488	/// remaining row index is the inner slot.
489	///
490	/// # Panics
491	///
492	/// Panics unless both multilinears span exactly one shift slot and the bit position.
493	pub fn new(g: SparseShiftRows<P>, h: FieldVec<P, A>, sum: F, alloc: &'alloc A) -> Self {
494		assert_eq!(h.log_len(), SHIFT_OPERATOR_LOG_LEN, "h spans one shift slot");
495		assert_eq!(g.log_rows(), LOG_SHIFT_COUNT, "g's rows span one shift slot");
496
497		Self {
498			alloc,
499			stage: Some(Stage::Rows {
500				g,
501				h,
502				claim: sum,
503				coeffs: None,
504			}),
505		}
506	}
507}
508
509impl<A: Allocator, F: Field, P: PackedField<Scalar = F>> SumcheckProver<F>
510	for Phase1SumcheckProver<'_, A, P>
511{
512	fn n_vars(&self) -> usize {
513		match self.stage.as_ref().expect("the stage is set between calls") {
514			// The weight table spans both axes through the row rounds.
515			// So its length is what remains.
516			Stage::Rows { h, .. } => h.log_len(),
517			Stage::Bits(prover) => prover.n_vars(),
518		}
519	}
520
521	fn execute(&mut self) -> Vec<RoundCoeffs<F>> {
522		match self.stage.as_mut().expect("the stage is set between calls") {
523			Stage::Rows {
524				g,
525				h,
526				claim,
527				coeffs,
528			} => {
529				// Row stage: compute this round's message from the stored rows alone, and
530				// hold onto it until the challenge that reduces the claim arrives.
531				let round_coeffs = g.round_coeffs(h, *claim);
532				*coeffs = Some(round_coeffs.clone());
533				vec![round_coeffs]
534			}
535			// Bit stage: delegate to the shared dense-product prover.
536			Stage::Bits(prover) => prover.execute(),
537		}
538	}
539
540	fn fold(&mut self, challenge: F) {
541		// Taken out so the row stage's buffers can move into the bit stage's prover below.
542		let stage = self.stage.take().expect("the stage is set between calls");
543		self.stage = Some(match stage {
544			Stage::Rows {
545				mut g,
546				mut h,
547				coeffs,
548				..
549			} => {
550				let claim = coeffs
551					.expect("execute is called before fold")
552					.evaluate(&challenge);
553				// Fold both multilinears by the same challenge.
554				// The sparse rows move into their half's slot of the shrunken row space.
555				// The dense weight table folds its highest variable the ordinary way.
556				g.fold(challenge);
557				fold_highest_var_inplace(&mut h, challenge);
558
559				if g.log_rows() > 0 {
560					// The row index still has unbound variables: stay in the row stage.
561					Stage::Rows {
562						g,
563						h,
564						claim,
565						coeffs: None,
566					}
567				} else {
568					// The row index is bound.
569					// What is left of each multilinear is one dense row over the bit
570					// position, which the shared prover handles from here.
571					Stage::Bits(bivariate_product_prover(
572						self.alloc,
573						[g.into_bit_multilinear(self.alloc), h],
574						claim,
575					))
576				}
577			}
578			Stage::Bits(mut prover) => {
579				// Bit stage: delegate the fold to the shared dense-product prover.
580				prover.fold(challenge);
581				Stage::Bits(prover)
582			}
583		});
584	}
585
586	fn finish(self) -> Vec<F> {
587		match self.stage.expect("the stage is set between calls") {
588			Stage::Rows { .. } => panic!("finish called before the row index was bound"),
589			// The columns went in as `[g, h]`, so the evaluations come out in that order.
590			Stage::Bits(prover) => prover.finish(),
591		}
592	}
593}
594
595#[cfg(test)]
596mod tests {
597	use binius_alloc::GlobalAllocator;
598	use binius_core::constraint_system::{
599		AndConstraint, ConstraintSystem, InoutSegment, Shift, ShiftedValueIndex, ValueIndex,
600	};
601	use binius_field::{Field, Ghash128b, PackedGhash2x128b};
602	use binius_math::{inner_product::inner_product_buffers, test_utils::random_scalars};
603	use binius_transcript::ProverTranscript;
604	use binius_verifier::config::StdChallenger;
605	use rand::{SeedableRng, rngs::StdRng};
606
607	use super::*;
608	use crate::protocols::shift::KeyCollection;
609
610	type F = Ghash128b;
611
612	impl<P: PackedField> SparseShiftRows<P> {
613		/// Spreads the rows over the space they still span, as a dense multilinear.
614		///
615		/// Rows at a repeated index add up.
616		/// Every row the constraint system does not name stays zero.
617		///
618		/// Nothing in the actual proving path needs this.
619		/// It exists only so these tests have a dense reference to check the sparse rounds
620		/// against.
621		fn scatter<A: Allocator>(&self, alloc: &A) -> FieldVec<P, A> {
622			let row_len = row_len::<P>();
623			let mut g = FieldBuffer::zeros_in(alloc, self.log_rows + Word::LOG_BITS);
624			for (index, row) in self.rows() {
625				// A row is a whole number of packed elements, so it lands at row alignment.
626				let slots = &mut g.as_mut()[index * row_len..][..row_len];
627				for (slot, &value) in iter::zip(slots, row) {
628					*slot += value;
629				}
630			}
631			g
632		}
633	}
634
635	/// A system whose two segments name overlapping but distinct shifts.
636	///
637	/// The public segment names `(Sll, 0)` and `(Slr, 3)`; the hidden one `(Sll, 0)`, `(Sar, 7)`
638	/// and `(Rotr, 1)`. So `(Sll, 0)` is the shift the merge has to sum across segments.
639	fn overlapping_shift_system() -> ConstraintSystem {
640		let public = ValueIndex::constant(1);
641		let hidden = ValueIndex::private(1);
642		ConstraintSystem {
643			constants: vec![Word::ZERO; 4],
644			n_inout: 0,
645			n_private: 4,
646			zero_constraints: Vec::new(),
647			and_constraints: vec![AndConstraint([
648				vec![
649					ShiftedValueIndex::plain(public),
650					ShiftedValueIndex::srl(public, 3),
651				],
652				vec![ShiftedValueIndex::sar(hidden, 7)],
653				vec![
654					ShiftedValueIndex::rotr(hidden, 1),
655					ShiftedValueIndex::plain(hidden),
656				],
657			])],
658			imul_constraints: Vec::new(),
659			bmul_constraints: Vec::new(),
660		}
661	}
662
663	/// The two segments' rows concatenate, each tagged with the shift index it sits at.
664	///
665	/// A shift both segments name appears twice rather than being merged — `g` is the sum of its
666	/// rows, so the two add up wherever it is read, and nothing has to deduplicate them.
667	#[test]
668	fn from_segments_concatenates_the_two_encodings() {
669		let key_collection =
670			KeyCollection::build(&overlapping_shift_system(), InoutSegment::Public);
671
672		// Fill each segment's rows with a distinct constant per row, so a row's value says which
673		// segment it came from.
674		let segment_rows = |enc: &DenseShiftEncoding, base: u128| {
675			(0..enc.len() * Word::BITS)
676				.map(|i| F::new(base + (i / Word::BITS) as u128))
677				.collect::<Vec<F>>()
678		};
679		let public = segment_rows(&key_collection.public.dense_shift_enc, 0x100);
680		let hidden = segment_rows(&key_collection.hidden.dense_shift_enc, 0x200);
681
682		let g = SparseShiftRows::from_segments([
683			(&public, &key_collection.public.dense_shift_enc),
684			(&hidden, &key_collection.hidden.dense_shift_enc),
685		]);
686
687		// The public segment's two shifts, then the hidden segment's three. Every term here is
688		// singly shifted, so its outer slot is the identity and its quadruple index is its inner
689		// shift's. `(Sll, 0)` is the first row of both segments, so index 0 appears twice.
690		let row_index = |shift: Shift| shift.index() as u32;
691		assert_eq!(
692			g.indices,
693			[
694				row_index(Shift::IDENTITY),
695				row_index(Shift::srl(3)),
696				row_index(Shift::IDENTITY),
697				row_index(Shift::sar(7)),
698				row_index(Shift::rotr(1)),
699			]
700		);
701
702		// Each row is the one its own segment accumulated, untouched by the other's.
703		let row = |position: usize| &g.values[position * Word::BITS..][..Word::BITS];
704		for (position, expected) in [0x100, 0x101, 0x200, 0x201, 0x202].into_iter().enumerate() {
705			assert!(row(position).iter().all(|&value| value == F::new(expected)));
706		}
707
708		// Where `g` is read, the two rows at the identity add up.
709		let at = |shift: Shift| {
710			g.rows()
711				.filter(|&(index, _)| index == shift.index())
712				.map(|(_, row)| row[0])
713				.sum::<F>()
714		};
715		assert_eq!(at(Shift::IDENTITY), F::new(0x100) + F::new(0x200));
716		assert_eq!(at(Shift::srl(3)), F::new(0x101));
717		assert_eq!(at(Shift::sar(7)), F::new(0x201));
718		assert_eq!(at(Shift::rotr(1)), F::new(0x202));
719	}
720
721	/// A sequence is placed outer-major, so the outer slot lands where the first rounds bind it.
722	#[test]
723	fn a_sequence_is_keyed_outer_major() {
724		let hidden = ValueIndex::private(1);
725		let sequence = [Shift::srl(3), Shift::sll(5)];
726		let cs = ConstraintSystem {
727			constants: vec![Word::ZERO; 4],
728			n_inout: 0,
729			n_private: 4,
730			zero_constraints: Vec::new(),
731			and_constraints: vec![AndConstraint([
732				vec![ShiftedValueIndex::new(hidden, sequence)],
733				Vec::new(),
734				Vec::new(),
735			])],
736			imul_constraints: Vec::new(),
737			bmul_constraints: Vec::new(),
738		};
739
740		let key_collection = KeyCollection::build(&cs, InoutSegment::Public);
741		let [inner, outer] = sequence;
742		assert_eq!(
743			key_collection
744				.hidden
745				.dense_shift_enc
746				.shift_indices()
747				.collect::<Vec<_>>(),
748			[outer.index() << LOG_SHIFT_COUNT | inner.index()]
749		);
750	}
751
752	/// The scatter puts every row where its shift index names, and leaves the rest zero.
753	///
754	/// The outer rounds are past by the time the dense reference below is taken, so the rows span
755	/// one shift slot here rather than the quadruple `from_segments` keys on.
756	#[test]
757	fn scatter_places_rows_at_their_shift_index() {
758		let indices = [Shift::IDENTITY, Shift::sar(7), Shift::rotr(1)]
759			.map(|shift| shift.index() as u32)
760			.to_vec();
761		let values = (0..indices.len() * Word::BITS)
762			.map(|i| F::new(1 + (i / Word::BITS) as u128))
763			.collect::<Vec<F>>();
764		let rows = SparseShiftRows::<F>::new(indices.clone(), values, LOG_SHIFT_COUNT);
765
766		let g = rows.scatter(&GlobalAllocator);
767		assert_eq!(g.log_len(), SHIFT_OPERATOR_LOG_LEN);
768
769		// Exactly the named rows are non-zero, and each holds what the list held.
770		for (row, &shift_index) in indices.iter().enumerate() {
771			let offset = shift_index as usize * Word::BITS;
772			for bit in 0..Word::BITS {
773				assert_eq!(g.get(offset + bit), F::new(1 + row as u128));
774			}
775		}
776		for row in (0..1 << LOG_SHIFT_COUNT).filter(|row| !indices.contains(&(*row as u32))) {
777			assert!((0..Word::BITS).all(|bit| g.get(row * Word::BITS + bit) == F::ZERO));
778		}
779	}
780
781	/// Runs the same claim through a single dense product-sumcheck prover, with no round handled
782	/// specially.
783	///
784	/// This is the reference the sparse-and-dense hybrid prover's round messages have to
785	/// reproduce.
786	fn run_dense_reference<P: PackedField<Scalar = F>>(
787		g: &SparseShiftRows<P>,
788		h: FieldVec<P, GlobalAllocator>,
789		sum: F,
790		channel: &mut ProverTranscript<StdChallenger>,
791	) -> (Vec<F>, F) {
792		let prover =
793			bivariate_product_prover(&GlobalAllocator, [g.scatter(&GlobalAllocator), h], sum);
794
795		let ProveSingleOutput {
796			multilinear_evals,
797			mut challenges,
798		} = prove_single(prover, channel);
799		challenges.reverse();
800
801		let [g_eval, h_eval] = multilinear_evals
802			.try_into()
803			.expect("prover has 2 multilinear polynomials");
804
805		(challenges, g_eval * h_eval)
806	}
807
808	/// The `g` and `h` the row and bit rounds run over, from pseudo-random weights.
809	///
810	/// The outer rounds are past by this point, so `g`'s rows sit at the inner shift each sequence
811	/// names. They carry arbitrary values rather than ones a witness produces: the sumcheck is a
812	/// statement about whatever multilinears it is handed, so what the rows hold does not bear on
813	/// whether the sparse rounds reproduce the dense ones.
814	fn phase_1_multilinears<P: PackedField<Scalar = F>>(
815		cs: &ConstraintSystem,
816		seed: u64,
817	) -> (SparseShiftRows<P>, FieldVec<P, GlobalAllocator>) {
818		let mut rng = StdRng::seed_from_u64(seed);
819		let key_collection = KeyCollection::build(cs, InoutSegment::Public);
820
821		let mut indices = Vec::new();
822		let mut values = Vec::new();
823		for segment in [&key_collection.public, &key_collection.hidden] {
824			for [inner, _] in segment.dense_shift_enc.iter() {
825				indices.push(inner.index() as u32);
826				values.extend((0..row_len::<P>()).map(|_| P::random(&mut rng)));
827			}
828		}
829		let g = SparseShiftRows::new(indices, values, LOG_SHIFT_COUNT);
830
831		// The weights `h` is built from are arbitrary here for the same reason `g`'s rows are.
832		let h = shift_operator_table(&GlobalAllocator, &random_scalars::<F>(&mut rng, Word::BITS));
833
834		(g, h)
835	}
836
837	/// The sparse rounds send exactly what the dense prover sends.
838	///
839	/// The two provers sum the same product over the same hypercube, so every round message — and
840	/// therefore the whole transcript, the challenges it draws, and the evaluation it reduces to —
841	/// must agree. This is what lets the verifier stay untouched.
842	fn assert_sparse_matches_dense<P: PackedField<Scalar = F>>(cs: &ConstraintSystem, seed: u64) {
843		let (g, h) = phase_1_multilinears::<P>(cs, seed);
844		// The true sum, so the test exercises a sumcheck a verifier would accept.
845		let sum = inner_product_buffers(&g.scatter(&GlobalAllocator), &h);
846
847		let mut sparse_transcript = ProverTranscript::<StdChallenger>::default();
848		let ProveSingleOutput {
849			multilinear_evals,
850			challenges: mut sparse_challenges,
851		} = prove_single(
852			Phase1SumcheckProver::new(g.clone(), h.clone(), sum, &GlobalAllocator),
853			&mut sparse_transcript,
854		);
855		sparse_challenges.reverse();
856		let [g_eval, h_eval] = multilinear_evals
857			.try_into()
858			.expect("prover has 2 multilinear polynomials");
859
860		let mut dense_transcript = ProverTranscript::<StdChallenger>::default();
861		let (dense_challenges, dense_eval) = run_dense_reference(&g, h, sum, &mut dense_transcript);
862
863		assert_eq!(sparse_challenges, dense_challenges);
864		assert_eq!(g_eval * h_eval, dense_eval);
865		assert_eq!(sparse_transcript.finalize(), dense_transcript.finalize());
866	}
867
868	#[test]
869	fn sparse_rounds_match_the_dense_prover() {
870		// Both packing widths the prover is instantiated at: the m4 prover drives phase 1 with
871		// scalars, the single-instance prover with a packed field.
872		assert_sparse_matches_dense::<F>(&overlapping_shift_system(), 0);
873		assert_sparse_matches_dense::<PackedGhash2x128b>(&overlapping_shift_system(), 1);
874	}
875
876	/// A constraint system that constrains nothing names no shift, so `g` stores no row at all.
877	///
878	/// The sparse rounds then have nothing to scan, which must still leave the transcript the one
879	/// a dense prover over the zero `g` would have written.
880	#[test]
881	fn sparse_rounds_match_the_dense_prover_with_an_empty_g() {
882		let cs = ConstraintSystem {
883			constants: vec![Word::ZERO; 4],
884			n_inout: 0,
885			n_private: 4,
886			zero_constraints: Vec::new(),
887			and_constraints: Vec::new(),
888			imul_constraints: Vec::new(),
889			bmul_constraints: Vec::new(),
890		};
891
892		let key_collection = KeyCollection::build(&cs, InoutSegment::Public);
893		assert!(key_collection.public.dense_shift_enc.is_empty());
894		assert!(key_collection.hidden.dense_shift_enc.is_empty());
895
896		assert_sparse_matches_dense::<PackedGhash2x128b>(&cs, 2);
897	}
898}