Skip to main content

binius_prover/
prove.rs

1// Copyright 2025 Irreducible Inc.
2// Copyright 2026 The Binius Developers
3
4use std::{marker::PhantomData, mem::MaybeUninit};
5
6use binius_alloc::{Allocator, BufferPool, VecLike};
7use binius_core::{
8	constraint_system::{ConstraintSystem, InoutSegment, Operand, ValueVec},
9	word::Word,
10};
11use binius_field::{PackedField, Rijndael8b as B8};
12use binius_hash_prover::ParallelHashSuite;
13use binius_iop_prover::{basefold::compiler::BaseFoldProverCompiler, channel::IOPProverChannel};
14use binius_ip::sumcheck::SumcheckOutput;
15use binius_ip_prover::channel::WordIPProverChannel;
16use binius_math::{
17	BinarySubspace, FieldBuffer, FieldVec,
18	ntt::{NeighborsLastMultiThread, domain_context::GaoMateerPreExpanded},
19};
20use binius_transcript::{ProverTranscript, fiat_shamir::Challenger};
21use binius_utils::{
22	SerializeBytes,
23	checked_arithmetics::log2_ceil_usize,
24	rayon::{prelude::*, task_size::IndexedParallelIteratorExt},
25};
26use binius_verifier::{
27	IOPVerifier, Verifier,
28	config::{B128, LOG_WORDS_PER_ELEM},
29	protocols::bitand::AndCheckOutput,
30};
31use digest::Output;
32
33use super::error::Error;
34use crate::{
35	protocols::{
36		binmul, bitand, intmul,
37		rerand::OperandWitness,
38		shift::{self, KeyCollection, OperandClaims, ShiftOutput},
39	},
40	ring_switch,
41};
42
43/// Type alias for the prover NTT parameterized by field.
44type ProverNTT<F> = NeighborsLastMultiThread<GaoMateerPreExpanded<F>>;
45
46/// IOP prover for a particular constraint system.
47///
48/// This struct encapsulates the constraint system and pre-computed keys,
49/// providing the core proving logic independent of the specific IOP compilation strategy.
50/// Most users should use [`Prover`] instead, which wraps this with a BaseFold compiler.
51#[derive(Debug)]
52pub struct IOPProver {
53	constraint_system: ConstraintSystem,
54	n_witness_elems: usize,
55	key_collection: KeyCollection,
56}
57
58impl IOPProver {
59	/// Constructs an IOP prover from an IOP verifier and pre-computed keys.
60	pub fn new(iop_verifier: IOPVerifier, key_collection: KeyCollection) -> Self {
61		let n_witness_elems = iop_verifier.n_witness_elems();
62		let constraint_system = iop_verifier.into_constraint_system();
63		Self {
64			constraint_system,
65			n_witness_elems,
66			key_collection,
67		}
68	}
69
70	/// Returns the constraint system.
71	pub const fn constraint_system(&self) -> &ConstraintSystem {
72		&self.constraint_system
73	}
74
75	/// Returns a reference to the KeyCollection.
76	///
77	/// This can be used to serialize the KeyCollection for later use.
78	pub const fn key_collection(&self) -> &KeyCollection {
79		&self.key_collection
80	}
81
82	/// Proves using an IOP channel interface.
83	///
84	/// This is the core proving logic, independent of the specific IOP compilation strategy.
85	/// For most users, [`Prover::prove`] is the simpler interface.
86	pub fn prove<A, P, Channel>(
87		&self,
88		witness: &ValueVec,
89		channel: &mut Channel,
90		alloc: &A,
91	) -> Result<(), Error>
92	where
93		A: Allocator,
94		P: PackedField<Scalar = B128>,
95		Channel: IOPProverChannel<P, A> + WordIPProverChannel<B128, Word = Word>,
96	{
97		let cs = &self.constraint_system;
98
99		// [phase] Setup - initialization and constraint system setup
100		//
101		// Only the non-public words are committed as the trace oracle; the public segment is a
102		// verifier-known polynomial.
103		let setup_guard = tracing::debug_span!("Prepare witness").entered();
104		// The oracle is the `n_witness_elems` the words fill, sent as its `2^⌈log2 n⌉` prefix view.
105		let witness_packed = pack_witness::<P, _>(
106			alloc,
107			log2_ceil_usize(self.n_witness_elems),
108			witness.non_public(),
109		)?;
110		drop(setup_guard);
111
112		// Observe the inout words, which includes them in Fiat-Shamir. The constants are fixed by
113		// the constraint system, so only the per-instance values are observed.
114		channel.observe_words(witness.inout());
115
116		// [phase] Witness Commit - witness generation and commitment
117		let witness_commit_guard = tracing::info_span!("Commit witness").entered();
118
119		// Commit witness via channel.
120		let trace_oracle = channel.send_oracle(witness_packed.as_view());
121
122		drop(witness_commit_guard);
123
124		// [phase] IntMul Reduction - multiplication constraint reduction
125		//
126		// Skipped entirely (no transcript messages) when the constraint system has no IMUL
127		// constraints. The verifier applies the identical guard, so the transcript stays in sync;
128		// the IntMul claim is then a zero claim, contributing nothing to the shift reduction.
129		//
130		// The columns are kept with the output, since the BitAnd sumcheck re-reads them.
131		let intmul = if cs.n_imul_constraints() > 0 {
132			let intmul_guard = tracing::info_span!(
133				"[phase] IntMul check",
134				n_constraints = cs.imul_constraints.len()
135			)
136			.entered();
137			let mul_columns = tracing::debug_span!("Assemble columns")
138				.in_scope(|| build_operation_columns(&cs.imul_constraints, witness, alloc));
139
140			let [a, b, lo, hi] = &mul_columns;
141			let intmul_output = intmul::prove::<_, _, P, _>([a, b, lo, hi], &mut *channel, alloc)?;
142			drop(intmul_guard);
143			Some((mul_columns, intmul_output))
144		} else {
145			None
146		};
147
148		// [phase] BinMul Reduction - GHASH-field multiplication constraint reduction
149		//
150		// Runs immediately after the IntMul reduction and before BitAnd, matching the verifier so
151		// the transcript stays in sync. Skipped entirely (no transcript messages) when there are
152		// no BMUL constraints; the BinMul claim is then a zero claim, contributing nothing to the
153		// shift reduction.
154		let binmul = if cs.n_bmul_constraints() > 0 {
155			let binmul_guard = tracing::info_span!(
156				"[phase] BinMul check",
157				n_constraints = cs.bmul_constraints.len()
158			)
159			.entered();
160			let binmul_columns = tracing::debug_span!("Assemble columns")
161				.in_scope(|| build_operation_columns(&cs.bmul_constraints, witness, alloc));
162
163			let [a_lo, a_hi, b_lo, b_hi, c_lo, c_hi] = &binmul_columns;
164			let binmul_output = binmul::prove::<_, _, P, _>(
165				[a_lo, a_hi, b_lo, b_hi, c_lo, c_hi],
166				&mut *channel,
167				alloc,
168			);
169			drop(binmul_guard);
170			Some((binmul_columns, binmul_output))
171		} else {
172			None
173		};
174
175		// [phase] BitAnd Reduction - AND constraint reduction
176		//
177		// Its sumcheck carries the multiplications' per-bit operand claims, IntMul first.
178		let operands = [
179			intmul.as_ref().map(|(columns, output)| OperandWitness {
180				words: columns.iter().map(|column| &**column).collect(),
181				claims: output.operand_claims(),
182			}),
183			binmul.as_ref().map(|(columns, output)| OperandWitness {
184				words: columns.iter().map(|column| &**column).collect(),
185				claims: output.operand_claims(),
186			}),
187		]
188		.into_iter()
189		.flatten()
190		.collect::<Vec<_>>();
191		let bitand_guard =
192			tracing::info_span!("[phase] BitAnd check", n_constraints = cs.and_constraints.len())
193				.entered();
194		let AndCheckOutput {
195			z_challenge,
196			rerand,
197		} = {
198			// Only the `A` and `B` columns are built; the reduction derives `C = A & B`.
199			let bitand_columns = tracing::debug_span!("Assemble columns")
200				.in_scope(|| build_operation_columns(&cs.and_constraints, witness, alloc));
201			bitand::prove::<_, B128, P, _, _>(bitand_columns, &operands, &mut *channel, alloc)
202		};
203		drop(bitand_guard);
204
205		// [phase] Zero Reduction - linear constraint reduction
206		//
207		// Every operation is claimed at one constraint point: the BitAnd sumcheck's point, extended
208		// when the ZERO set is wider. The extension is drawn here, where the verifier draws it. See
209		// `IOPVerifier::verify` for why the Zero reduction carries no message.
210		let claims = OperandClaims::from_rerand(cs, 0, z_challenge, &rerand, || channel.sample());
211
212		// The shift reduction folds the bit axis over the 64-point domain, as the verifier's
213		// `shift::check_eval` does.
214		let subspace = BinarySubspace::<B8>::with_dim(Word::LOG_BITS).isomorphic();
215
216		// [phase] Shift Reduction - shift operations
217		let shift_guard = tracing::info_span!(
218			"[phase] Shift Reduction",
219			phase = "shift_reduction",
220			perfetto_category = "phase"
221		)
222		.entered();
223		let ShiftOutput {
224			sumcheck: SumcheckOutput {
225				challenges: eval_point,
226				eval: _,
227			},
228			wiring_eval,
229		} = shift::prove::<_, P, _, _>(
230			&self.key_collection,
231			witness.public(),
232			witness.non_public(),
233			claims,
234			&subspace,
235			&mut *channel,
236			alloc,
237		);
238		drop(shift_guard);
239
240		// Split the shift's final point `r_j || r_y || r_segment` into its three parts. The bit
241		// index `r_j` addresses a bit within a 64-bit word, the segment selector `r_segment` is
242		// the last coordinate, and the word index `r_y` is everything in between.
243		let witness_point = &eval_point[..eval_point.len() - 1];
244		let (r_j, r_y) = witness_point.split_at(Word::LOG_BITS);
245
246		// Prove the public segment's evaluation claim, which the verifier's public-input check
247		// consumes.
248		ring_switch::prove_public_eval::<_, P, _>(alloc, witness.public(), r_j, r_y, &mut *channel);
249
250		// The wiring evaluation the verifier closes the shift check with, sent where it reads it:
251		// after the public segment's claim.
252		channel.send_public_claim(wiring_eval);
253
254		// [phase] Ring-Switching + PCS Opening
255		let pcs_guard = tracing::info_span!(
256			"[phase] PCS Opening",
257			phase = "pcs_opening",
258			perfetto_category = "phase"
259		)
260		.entered();
261
262		// Ring-switching reduction of the witness claim, at the point above less its segment
263		// selector — the verifier consumes that when reconstructing the full witness evaluation.
264		let ring_switch::RingSwitchOutput {
265			rs_eq_ind,
266			sumcheck_claim,
267		} = ring_switch::prove(
268			alloc,
269			witness_packed.as_view(),
270			self.n_witness_elems,
271			witness_point,
272			&mut *channel,
273		);
274
275		// Prove oracle relations via channel (runs BaseFold internally). The intmul pushforward
276		// relation, when the IntMul reduction ran, was already queued inside phase 5.
277		channel.prove_oracle_relation(trace_oracle, rs_eq_ind, sumcheck_claim);
278
279		drop(pcs_guard);
280
281		Ok(())
282	}
283}
284
285/// Warns once per process if the CPU supports carryless multiply but this build does not use it.
286///
287/// The GHASH field arithmetic is selected at compile time, so a default-target x86_64 build runs
288/// the software multiply even on CPUs with PCLMULQDQ, silently costing an order of magnitude in
289/// prover throughput (see issue #1800). Building with `-C target-cpu=native` or
290/// `-C target-feature=+pclmulqdq` selects the hardware path.
291#[cfg(target_arch = "x86_64")]
292fn warn_on_software_field_arithmetic() {
293	use std::{arch::is_x86_feature_detected, sync::Once};
294
295	static ONCE: Once = Once::new();
296	ONCE.call_once(|| {
297		if !cfg!(target_feature = "pclmulqdq") && is_x86_feature_detected!("pclmulqdq") {
298			tracing::warn!(
299				"this CPU supports carryless multiply (PCLMULQDQ), but the build does not \
300				 enable it, so field arithmetic will run in software; rebuild with \
301				 `-C target-cpu=native` or `-C target-feature=+pclmulqdq`"
302			);
303		}
304	});
305}
306
307#[cfg(not(target_arch = "x86_64"))]
308const fn warn_on_software_field_arithmetic() {}
309
310/// Struct for proving instances of a particular constraint system.
311///
312/// The [`Self::setup`] constructor pre-processes reusable structures for proving instances of the
313/// given constraint system. Then [`Self::prove`] is called one or more times with individual
314/// instances.
315pub struct Prover<P, H>
316where
317	P: PackedField<Scalar = B128>,
318	H: ParallelHashSuite,
319{
320	/// The constraint system and the reduction that commits it, independent of the commitment.
321	iop_prover: IOPProver,
322	/// The commitment scheme's parameters, mirrored from the verifier this prover was set up for.
323	iop_compiler: BaseFoldProverCompiler<P, ProverNTT<B128>>,
324	/// The pool that recycles this prover's working buffers. It lives for the prover's lifetime,
325	/// so blocks freed by one `prove` call are reused by the next.
326	pool: BufferPool,
327	/// The prover creates its Merkle transcript channels with the hash suite `H`.
328	_hash_marker: PhantomData<H>,
329}
330
331impl<P, H> Prover<P, H>
332where
333	P: PackedField<Scalar = B128>,
334	H: ParallelHashSuite,
335	Output<H::LeafHash>: SerializeBytes,
336{
337	/// Constructs a prover corresponding to a constraint system verifier.
338	///
339	/// See [`Prover`] struct documentation for details.
340	pub fn setup(verifier: Verifier<H>) -> Result<Self, Error> {
341		let key_collection =
342			KeyCollection::build(verifier.constraint_system(), InoutSegment::Public);
343		Self::setup_with_key_collection(verifier, key_collection)
344	}
345
346	/// Constructs a prover with a pre-built KeyCollection.
347	///
348	/// This allows loading a previously serialized KeyCollection to avoid
349	/// the expensive key building phase during setup.
350	pub fn setup_with_key_collection(
351		verifier: Verifier<H>,
352		key_collection: KeyCollection,
353	) -> Result<Self, Error> {
354		warn_on_software_field_arithmetic();
355
356		// Rebuild the verifier's evaluation domain, which its compiler fixed as the Gao-Mateer
357		// basis of that dimension.
358		let domain_context =
359			GaoMateerPreExpanded::generate(verifier.iop_compiler().max_log_domain_size());
360		// FIXME TODO For mobile phones, the number of shares should potentially be more than the
361		// number of threads, because the threads/cores have different performance (but in the NTT
362		// each share has the same amount of work)
363		let log_num_shares = binius_utils::rayon::current_num_threads().ilog2() as usize;
364		let ntt = NeighborsLastMultiThread::new(domain_context, log_num_shares);
365
366		// Mirror the verifier's parameters, so neither side can pick its own.
367		let iop_compiler =
368			BaseFoldProverCompiler::from_verifier_compiler(verifier.iop_compiler(), ntt);
369
370		let iop_prover = IOPProver::new(verifier.into_iop_verifier(), key_collection);
371
372		Ok(Prover {
373			iop_prover,
374			iop_compiler,
375			pool: BufferPool::new(),
376			_hash_marker: PhantomData,
377		})
378	}
379
380	/// Returns a reference to the IOP prover.
381	pub const fn iop_prover(&self) -> &IOPProver {
382		&self.iop_prover
383	}
384
385	/// Returns a reference to the KeyCollection.
386	///
387	/// This can be used to serialize the KeyCollection for later use.
388	pub const fn key_collection(&self) -> &KeyCollection {
389		self.iop_prover.key_collection()
390	}
391
392	pub fn prove<Challenger_: Challenger + Clone>(
393		&self,
394		witness: &ValueVec,
395		transcript: &mut ProverTranscript<Challenger_>,
396	) -> Result<(), Error> {
397		let cs = self.iop_prover.constraint_system();
398
399		let _prove_guard = tracing::info_span!(
400			"Prove",
401			n_hidden_words = cs.n_hidden_words(InoutSegment::Public),
402			n_bitand = cs.and_constraints.len(),
403			n_intmul = cs.imul_constraints.len(),
404		)
405		.entered();
406
407		// Working buffers for this proof are drawn from the prover's pool, recycling blocks freed
408		// by earlier proofs. The pool is passed as an `&BufferPool` allocator, and the channel
409		// commits its Merkle trees out of the same pool.
410		let alloc = &self.pool;
411
412		// The unified channel takes an rng to mask ZK oracles, but a plain `Prover` produces a
413		// transparent proof whose only oracle is non-ZK, so no masks are drawn and the rng is never
414		// consumed.
415		let mut channel = self
416			.iop_compiler
417			.create_channel_without_zk_from_transcript::<H, Challenger_, _, _>(transcript, alloc);
418		self.iop_prover
419			.prove::<_, P, _>(witness, &mut channel, &alloc)?;
420		channel.finish();
421		Ok(())
422	}
423}
424
425/// Packs committed witness words into the field buffer committed as the trace oracle.
426///
427/// Two 64-bit words are packed little-endian into one 128-bit field element.
428/// The element sequence is zero-padded up to `2^log_witness_elems`.
429///
430/// # Arguments
431///
432/// - `alloc`: the allocator the packed buffer is drawn from.
433/// - `log_witness_elems`: base-2 logarithm of the committed field-element count.
434/// - `witness`: the committed witness words, in value-vector order.
435///
436/// # Returns
437///
438/// The packed multilinear over `log_witness_elems` variables, ready to commit.
439///
440/// # Errors
441///
442/// Returns an error when the words do not fit in `2^log_witness_elems` field elements.
443pub fn pack_witness<P: PackedField<Scalar = B128>, A: Allocator>(
444	alloc: &A,
445	log_witness_elems: usize,
446	witness: &[Word],
447) -> Result<FieldVec<P, A>, Error> {
448	// The number of field elements that constitute the packed witness.
449	let n_witness_elems = witness.len().div_ceil(1 << LOG_WORDS_PER_ELEM);
450	if n_witness_elems > 1 << log_witness_elems {
451		return Err(Error::ArgumentError {
452			arg: "witness".to_string(),
453			msg: "witness element count is incompatible with the constraint system".to_string(),
454		});
455	}
456
457	let len = 1 << log_witness_elems.saturating_sub(P::LOG_WIDTH);
458	let mut padded_witness_elems = alloc.alloc::<P>(len);
459
460	// Pack word pairs into B128 elements (2 words per field element), then group into P.
461	// Zero-pad up to the power-of-two witness polynomial length after the real words.
462	let (pairs, word_remaining) = witness.as_chunks::<2>();
463	let aligned_len = pairs.len() / P::WIDTH * P::WIDTH;
464	let (pairs_aligned, word_pair_remaining) = pairs.split_at(aligned_len);
465	// The buffer is sized for the whole padded witness, which the trailing element and the zero
466	// padding below fill out, so the aligned groups are written straight into its spare capacity
467	// rather than collected into a buffer of their own.
468	let n_aligned_elems = aligned_len / P::WIDTH;
469	(
470		pairs_aligned.par_chunks(P::WIDTH),
471		padded_witness_elems.spare_capacity_mut()[..n_aligned_elems].par_iter_mut(),
472	)
473		.into_par_iter()
474		.with_min_task_bytes::<P>()
475		.for_each(|(word_pairs, out)| {
476			out.write(P::from_scalars(
477				word_pairs
478					.iter()
479					.map(|[w0, w1]| B128::new(((w1.0 as u128) << 64) | (w0.0 as u128))),
480			));
481		});
482	// Safety: `aligned_len` is an exact multiple of `P::WIDTH`, so the chunk iterator yields
483	// exactly `n_aligned_elems` items — the same length as the spare-capacity slice it is zipped
484	// with. That equal length is what makes this sound: rayon's zip silently truncates to the
485	// shorter side, so a mismatch would leave slots uninitialized. With the lengths equal, the loop
486	// above writes each of the first `n_aligned_elems` slots exactly once.
487	unsafe { padded_witness_elems.set_len(n_aligned_elems) };
488
489	// The trailing partial group: any leftover word pairs (fewer than `P::WIDTH` of them) together
490	// with a final unpaired word are packed into a single `P` element. This keeps the zero padding
491	// strictly after the last real word, rather than splitting the unpaired word into a separate
492	// element and leaving a zero in the middle of the witness (BINIUS-173).
493	if !word_pair_remaining.is_empty() || !word_remaining.is_empty() {
494		let word_pairs = word_pair_remaining
495			.iter()
496			.copied()
497			.chain(word_remaining.iter().map(|&word| [word, Word::ZERO]));
498		padded_witness_elems.push(P::from_scalars(
499			word_pairs.map(|[w0, w1]| B128::new(((w1.0 as u128) << 64) | (w0.0 as u128))),
500		));
501	}
502
503	padded_witness_elems.resize(len, P::default());
504
505	Ok(FieldBuffer::new(log_witness_elems, padded_witness_elems))
506}
507
508/// Evaluates the leading `N_COLS` operands of every constraint against the witness, one
509/// materialized column per operand.
510///
511/// Column `i` holds operand `i` of every constraint, in the constraint type's storage order — the
512/// order the shift reduction batches operands in. Each column has exactly one row per constraint,
513/// in the same order, and nothing beyond them: every reduction rounds the constraint axis up to
514/// `constraints.len().next_power_of_two()` itself and reads the rows past a column's end as zero,
515/// which satisfies every constraint type.
516///
517/// An empty constraint slice still yields one zero row. [`ConstraintSystem::log_and_constraints`]
518/// reports `None` for an empty AND set and the verifier reads that as *zero* constraint variables —
519/// one all-zero row, not zero rows — and the BitAnd check has no skip branch. The two
520/// multiplication checks run only on a non-empty constraint set, so only AND reaches this.
521///
522/// [`ConstraintSystem::log_and_constraints`]: binius_core::constraint_system::ConstraintSystem::log_and_constraints
523///
524/// `N_COLS` may be smaller than `ARITY`, in which case the trailing operands are not evaluated. The
525/// BitAnd check uses that to skip its `C` column: on a satisfying witness `C = A & B` holds
526/// word-by-word, so the reduction derives it from the `A` and `B` columns instead.
527fn build_operation_columns<C, A, const ARITY: usize, const N_COLS: usize>(
528	constraints: &[C],
529	witness: &ValueVec,
530	alloc: &A,
531) -> [A::Vec<Word>; N_COLS]
532where
533	C: AsRef<[Operand; ARITY]> + Sync,
534	A: Allocator,
535{
536	const {
537		assert!(N_COLS <= ARITY, "N_COLS must not exceed the constraint arity");
538	}
539
540	let n_constraints = constraints.len();
541	// One row per constraint, and one standing in for an empty set (see above).
542	let n_rows = n_constraints.max(1);
543	(0..N_COLS)
544		.into_par_iter()
545		.map(|op_idx| {
546			let mut column = alloc.alloc::<Word>(n_rows);
547			// The allocator may hand back more capacity than requested, so bound the spare slice to
548			// the row count.
549			let rows = &mut column.spare_capacity_mut()[..n_rows];
550			// No constraint writes the empty set's row, so zero it here.
551			if n_constraints == 0 {
552				rows.fill(MaybeUninit::new(Word::ZERO));
553			}
554			(constraints, &mut *rows)
555				.into_par_iter()
556				.for_each(|(constraint, out)| {
557					out.write(witness.eval_operand(&constraint.as_ref()[op_idx]));
558				});
559			// Safety: the parallel loop writes each of the `n_rows` entries exactly once, since the
560			// zip is over equal-length sides — except when the constraint set is empty and the one
561			// row standing in for it was zeroed above.
562			unsafe { column.set_len(n_rows) };
563			column
564		})
565		.collect::<Vec<_>>()
566		.try_into()
567		.unwrap_or_else(|_| unreachable!("source iterator has N_COLS elements"))
568}
569
570#[cfg(test)]
571mod tests {
572	use binius_alloc::GlobalAllocator;
573	use binius_core::constraint_system::{AndConstraint, ConstraintSystem};
574	use binius_field::{Field, PackedGhash2x128b};
575	use binius_frontend::CircuitBuilder;
576
577	use super::{B128, ValueVec, Word, build_operation_columns, pack_witness};
578
579	/// A circuit of `n_gates` independent AND gates, its constraint system, and a valid witness.
580	///
581	/// One gate commits three words: two operands and the result.
582	/// So the committed trace grows with the gate count, giving the opening a realistic size.
583	fn and_gate_system(n_gates: usize) -> (ConstraintSystem, ValueVec) {
584		let builder = CircuitBuilder::new();
585		let wires: Vec<_> = (0..n_gates)
586			.map(|_| {
587				let x = builder.add_witness();
588				let y = builder.add_witness();
589				builder.force_commit(builder.band(x, y));
590				(x, y)
591			})
592			.collect();
593		let circuit = builder.build();
594
595		let mut w = circuit.new_witness_filler();
596		for (i, &(x, y)) in wires.iter().enumerate() {
597			// Both operands are non-zero on every gate, so a zero row can only be padding.
598			w[x] = Word(0x0123_4567_89AB_CDEF | (i as u64) << 32 | 1);
599			w[y] = Word(0xFEDC_BA98_7654_3210 | (i as u64) | 1);
600		}
601		circuit.populate_wire_witness(&mut w).unwrap();
602
603		let cs = circuit.constraint_system().clone();
604		cs.validate().unwrap();
605		(cs, w.into_value_vec())
606	}
607
608	/// The AND constraints of that circuit, and the same witness.
609	///
610	/// One gate yields one AND constraint, so the constraint count is `n_gates` exactly.
611	fn and_gate_witness(n_gates: usize) -> (Vec<AndConstraint>, ValueVec) {
612		let (cs, witness) = and_gate_system(n_gates);
613		assert_eq!(cs.n_and_constraints(), n_gates);
614		(cs.and_constraints, witness)
615	}
616
617	/// The columns stop at the last constraint rather than rounding up to a power of two: the
618	/// reductions round the constraint axis up themselves and read the rows past a column's end as
619	/// zero.
620	#[test]
621	fn build_operation_columns_stops_at_the_last_constraint() {
622		let (constraints, witness) = and_gate_witness(3);
623		let columns = build_operation_columns::<AndConstraint, _, 3, 2>(
624			&constraints,
625			&witness,
626			&GlobalAllocator,
627		);
628
629		// Three rows, not the four the reduction runs over. The fixture makes every operand
630		// non-zero, so a surviving padding row would show up as a zero tail.
631		for column in &columns {
632			assert_eq!(column.len(), 3);
633			assert!(column.iter().all(|&word| word != Word::ZERO));
634		}
635	}
636
637	/// An empty constraint set still yields one all-zero row: the verifier reads
638	/// `log_and_constraints() == None` as zero constraint variables, which is one row, and the
639	/// BitAnd check has no skip branch.
640	#[test]
641	fn build_operation_columns_gives_an_empty_set_one_zero_row() {
642		let (_, witness) = and_gate_witness(1);
643		let columns =
644			build_operation_columns::<AndConstraint, _, 3, 2>(&[], &witness, &GlobalAllocator);
645
646		for column in &columns {
647			assert_eq!(column.len(), 1);
648			assert_eq!(column[0], Word::ZERO);
649		}
650	}
651
652	/// The packing `pack_witness` is specified to produce: consecutive little-endian B128 elements
653	/// (low word in bits 0..64, high word in bits 64..128), a final unpaired word in the low half,
654	/// then zero padding up to `n_elems`.
655	fn expected_scalars(words: &[Word], n_elems: usize) -> Vec<B128> {
656		let mut scalars = vec![B128::ZERO; n_elems];
657		for (elem, pair) in scalars.iter_mut().zip(words.chunks(2)) {
658			let lo = pair[0].0 as u128;
659			let hi = pair.get(1).map_or(0, |w| w.0 as u128);
660			*elem = B128::new((hi << 64) | lo);
661		}
662		scalars
663	}
664
665	/// Regression test for BINIUS-173: with `P::WIDTH = 2`, a witness of 7 words has 3 word-pairs
666	/// (not a multiple of the packing width) plus a trailing unpaired word. The buggy code
667	/// zero-padded the final partial `P` chunk and then pushed the unpaired word as a *separate*
668	/// element, shifting the last real scalar by one position.
669	#[test]
670	fn test_pack_witness_unaligned_pair_count_with_remainder() {
671		type P = PackedGhash2x128b;
672		assert_eq!(P::WIDTH, 2, "this test is meaningful only when the packing width is 2");
673
674		let words: Vec<Word> = (1..=7u64).map(Word).collect();
675		let log_witness_elems = 3; // 8 field elements: 4 real, 4 zero-padding.
676
677		let packed = pack_witness::<P, _>(&GlobalAllocator, log_witness_elems, &words).unwrap();
678		let got: Vec<B128> = packed.iter_scalars().collect();
679
680		assert_eq!(got, expected_scalars(&words, 1 << log_witness_elems));
681	}
682
683	/// Covers every residue of the word count around the `2 * P::WIDTH` boundary (aligned and
684	/// unaligned, with and without a trailing word) plus a few larger sizes.
685	#[test]
686	fn test_pack_witness_various_lengths() {
687		type P = PackedGhash2x128b;
688
689		for n_words in [1usize, 2, 3, 4, 5, 6, 7, 8, 9, 13, 17] {
690			let words: Vec<Word> = (0..n_words as u64).map(|i| Word(i + 100)).collect();
691			let n_elems = n_words.div_ceil(2);
692			// Round up to a power of two, and to at least one full packed element.
693			let log_witness_elems = n_elems.max(P::WIDTH).next_power_of_two().ilog2() as usize;
694
695			let packed = pack_witness::<P, _>(&GlobalAllocator, log_witness_elems, &words).unwrap();
696			let got: Vec<B128> = packed.iter_scalars().collect();
697
698			assert_eq!(
699				got,
700				expected_scalars(&words, 1 << log_witness_elems),
701				"n_words = {n_words}"
702			);
703		}
704	}
705}