Skip to main content

binius_verifier/
reduction.rs

1// Copyright 2025 Irreducible Inc.
2// Copyright 2026 The Binius Developers
3
4//! The constraint reduction shared by the single-instance and batched Binius64 verifiers.
5//!
6//! One circuit, and `2^k` instances of one circuit, reduce the same way. The instance count joins
7//! every row count, instance index low, constraint index high. One circuit is the batch with
8//! `k = 0`.
9//!
10//! The BitAnd sumcheck carries the IntMul and BinMul operand claims, each zero-padded on its high
11//! end. So it ends at one point, and every operation is claimed at a prefix of it:
12//!
13//! ```text
14//! r_rho      the instance, shared by every operation
15//! r_x_star   the constraint; each operation reads the prefix its row count spans
16//! ```
17//!
18//! The shift reduction takes every operation at the same constraint point `r_x`, its matrix padded
19//! with empty rows, so each claim is scaled up from its prefix to the whole point first.
20
21use std::{iter, slice};
22
23use binius_core::{
24	constraint_system::{ConstraintSystem, InoutSegment},
25	word::Word,
26};
27use binius_field::{ExtensionField, FieldOps, Rijndael8b as B8};
28use binius_iop::channel::IOPVerifierChannel;
29use binius_ip::{
30	channel::WordIPVerifierChannel,
31	sumcheck::{SumcheckOutput, verify as verify_sumcheck},
32};
33use binius_math::{
34	BinarySubspace,
35	multilinear::{eq::eq_ind_zero, evaluate::evaluate_inplace_scalars},
36};
37use binius_utils::checked_arithmetics::log2_ceil_usize;
38
39use crate::{
40	Error,
41	config::{B1, B128, LOG_WORDS_PER_ELEM},
42	protocols::{
43		binmul::{BinMulOutput, verify as verify_binmul_reduction},
44		bitand::AndCheckOutput,
45		intmul::{IntMulOutput, verify as verify_intmul_reduction},
46		rerand::RerandOutput,
47		zero,
48	},
49	ring_switch::{self, RingSwitchVerifyOutput, eval_rs_eq},
50	verify_bitand_reduction,
51};
52
53pub const ZERO_ARITY: usize = 1;
54pub const BITAND_ARITY: usize = 3;
55pub const INTMUL_ARITY: usize = 4;
56pub const BINMUL_ARITY: usize = 6;
57
58/// Each operation's operand arity, in the order the shift reduction's operand columns run.
59///
60/// The shift reduction's operand claims are one flat slice, holding each operation's run of this
61/// many evaluations in this order: `[zero, bitand, intmul, binmul]`.
62pub const OPERATION_ARITIES: [usize; 4] = [ZERO_ARITY, BITAND_ARITY, INTMUL_ARITY, BINMUL_ARITY];
63
64/// The base-2 logarithm of the operand axis: the operand columns, padded to a power of two.
65pub const LOG_OPERANDS: usize =
66	log2_ceil_usize(ZERO_ARITY + BITAND_ARITY + INTMUL_ARITY + BINMUL_ARITY);
67
68/// Each operation's row-variable count, in `[zero, bitand, intmul, binmul]` order.
69///
70/// An empty constraint array reads as zero variables.
71fn log_rows(cs: &ConstraintSystem) -> [usize; 4] {
72	[
73		cs.log_zero_constraints(),
74		cs.log_and_constraints(),
75		cs.log_imul_constraints(),
76		cs.log_bmul_constraints(),
77	]
78	.map(|log_rows| log_rows.unwrap_or(0))
79}
80
81/// The length of the constraint point `r_x`: the widest operation's row-variable count.
82///
83/// Every operation matrix is padded with empty rows up to `2^log_constraint_point(cs)` rows.
84pub fn log_constraint_point(cs: &ConstraintSystem) -> usize {
85	log_rows(cs).into_iter().max().unwrap_or(0)
86}
87
88/// Each operation's padding factor at the constraint point `r_x`, in `[zero, bitand, intmul,
89/// binmul]` order.
90///
91/// The constraint reductions claim an operation of `2^n` rows at the prefix `r_x[..n]`. Its matrix,
92/// padded with empty rows up to the length of `r_x`, evaluates at `r_x` to that claim times
93/// `eq(0, r_x[n..])`: a padding row carries no operand term. Scaled by its factor, every
94/// operation's claim is at the same full point, so one expansion of `r_x` serves them all.
95///
96/// # Soundness
97///
98/// A factor is zero only with negligible probability. A nonzero factor scales the claim and the
99/// multilinear it is about by the same unit, which is a bijection.
100///
101/// # Preconditions
102///
103/// * `r_x` has [`log_constraint_point`] coordinates.
104pub fn padding_scales<E: FieldOps>(cs: &ConstraintSystem, r_x: &[E]) -> [E; 4] {
105	assert_eq!(r_x.len(), log_constraint_point(cs)); // precondition
106
107	// The suffix products of the single-coordinate factors: `eq(0, r_x[n..])` at index `n`.
108	let mut suffix_scales = iter::once(E::one())
109		.chain(r_x.iter().rev().scan(E::one(), |scale, r_x_i| {
110			*scale = scale.clone() * eq_ind_zero(slice::from_ref(r_x_i));
111			Some(scale.clone())
112		}))
113		.collect::<Vec<_>>();
114	suffix_scales.reverse();
115	log_rows(cs).map(|log_rows| suffix_scales[log_rows].clone())
116}
117
118/// What [`reduce_constraints`] leaves for the caller: every operation's operand claims, all at one
119/// constraint point, for the shift reduction to take.
120#[derive(Debug)]
121pub struct ReductionOutput<F> {
122	/// The instance point every operation is claimed at.
123	///
124	/// Empty for a single circuit.
125	pub r_rho: Vec<F>,
126	/// The constraint point every operation is claimed at, its matrix padded with empty rows.
127	///
128	/// It has [`log_constraint_point`] coordinates.
129	pub r_x: Vec<F>,
130	/// The univariate challenge folding the bit axis, shared by every operation.
131	pub z_challenge: F,
132	/// One evaluation per operand column, the four operations' runs in [`OPERATION_ARITIES`]
133	/// order.
134	pub operand_claims: Vec<F>,
135}
136
137/// Reduces every constraint of `2^log_instances` instances to operand claims at one point.
138///
139/// The reductions run in this order, and the order is load-bearing:
140///
141/// ```text
142/// IntMul -> BinMul -> BitAnd -> Zero
143/// ```
144///
145/// The caller then runs the shift reduction on the operand claims, reads the public segment's
146/// evaluation with [`verify_public_eval`], and closes the shift with
147/// [`shift::check_eval`](crate::protocols::shift::check_eval).
148///
149/// # Arguments
150///
151/// - `cs`: the single-instance constraint system every instance satisfies.
152/// - `log_instances`: the base-2 logarithm of the instance count, 0 for a single circuit.
153/// - `channel`: the verifier channel that reads messages and redraws Fiat-Shamir challenges.
154///
155/// # Errors
156///
157/// Returns an error if any reduction's sumcheck fails.
158///
159/// # Soundness
160///
161/// IntMul and BinMul must run *before* BitAnd.
162/// BitAnd draws the univariate challenge that collapses their per-bit operand evaluations.
163/// Committing those evaluations first stops a prover choosing them as a function of it.
164///
165/// Do not reorder these, and keep the same order in the prover.
166pub fn reduce_constraints<Channel>(
167	cs: &ConstraintSystem,
168	log_instances: usize,
169	channel: &mut Channel,
170) -> Result<ReductionOutput<Channel::Elem>, Error>
171where
172	Channel: IOPVerifierChannel<B128>,
173	Channel::Elem: FieldOps<Scalar = B128> + From<B128>,
174{
175	// The AND-check's univariate-skip domain spans one dimension above the 64-bit word.
176	let andcheck_domain = BinarySubspace::<B8>::default()
177		.isomorphic::<B128>()
178		.reduce_dim(Word::LOG_BITS + 1);
179
180	// The multiplication columns span every instance's constraints.
181	// So each check runs over `log_instances` more row variables than one instance has.
182	let intmul_output = match cs.log_imul_constraints() {
183		Some(log_n_imul) => {
184			let _guard = tracing::info_span!(
185				"[phase] Verify IntMul Reduction",
186				phase = "verify_intmul_reduction",
187				perfetto_category = "phase",
188				n_constraints = cs.n_imul_constraints()
189			)
190			.entered();
191			Some(verify_intmul_reduction::<B128, _>(log_instances + log_n_imul, channel)?)
192		}
193		// An empty IMUL set skips the reduction entirely, reading nothing from the transcript.
194		// The prover carries the identical guard, so the two stay in sync.
195		None => None,
196	};
197
198	let binmul_output = match cs.log_bmul_constraints() {
199		Some(log_n_bmul) => {
200			let _guard = tracing::info_span!(
201				"[phase] Verify BinMul Reduction",
202				phase = "verify_binmul_reduction",
203				perfetto_category = "phase",
204				n_constraints = cs.n_bmul_constraints()
205			)
206			.entered();
207			Some(verify_binmul_reduction::<B128, _>(log_instances + log_n_bmul, channel)?)
208		}
209		None => None,
210	};
211
212	// The BitAnd sumcheck carries the multiplications' per-bit operand claims, IntMul first.
213	let operands = [
214		intmul_output.as_ref().map(IntMulOutput::operand_claims),
215		binmul_output.as_ref().map(BinMulOutput::operand_claims),
216	]
217	.into_iter()
218	.flatten()
219	.collect::<Vec<_>>();
220
221	// The BitAnd check has no skip branch: an empty AND set still reduces, over the single all-zero
222	// padding row, so `None` is zero constraint variables.
223	let log_n_and = cs.log_and_constraints().unwrap_or(0);
224	let AndCheckOutput {
225		z_challenge,
226		rerand: RerandOutput {
227			eval_point,
228			bitand_evals,
229			operand_evals,
230		},
231	} = {
232		let _guard = tracing::info_span!(
233			"[phase] Verify BitAnd Reduction",
234			phase = "verify_bitand_reduction",
235			perfetto_category = "phase",
236			n_constraints = cs.n_and_constraints()
237		)
238		.entered();
239		verify_bitand_reduction(log_instances + log_n_and, &andcheck_domain, &operands, channel)?
240	};
241
242	// The sumcheck's point is `r_rho || r_x_star`: the instance index low, the constraint index
243	// high. `r_x_star` spans the widest AND, IMUL and BMUL set.
244	let (r_rho, r_x_star) = eval_point.split_at(log_instances);
245
246	// The Zero reduction reads nothing and runs no sumcheck.
247	// A ZERO constraint is linear, so its oblong form vanishing at one unpredictable point
248	// certifies it.
249	//
250	// A ZERO array vanishes identically, so its claim is zero at any point. A ZERO set wider than
251	// the rest extends `r_x_star` with fresh challenges, and the prover draws the same extension
252	// at the same place. The result is the one constraint point `r_x` every operation is claimed at
253	// a prefix of.
254	let log_n_zero = cs.log_zero_constraints().unwrap_or(0);
255	let r_x_len = r_x_star.len().max(log_n_zero);
256	let r_x = zero::reduction_point(r_x_star, r_x_len, || channel.sample());
257
258	// The four operations' operand claims, one per column in [`OPERATION_ARITIES`] order. Each is
259	// scaled by its padding factor, which lifts it from its prefix of `r_x` to its padded matrix at
260	// the whole point.
261	let [_, bitand_scale, intmul_scale, binmul_scale] = padding_scales(cs, &r_x);
262	let mut operand_evals = operand_evals.into_iter();
263	let operand_claims = [
264		vec![Channel::Elem::zero(); ZERO_ARITY],
265		bitand_evals
266			.map(|eval| eval * bitand_scale.clone())
267			.to_vec(),
268		absent_or_claimed::<_, INTMUL_ARITY>(
269			cs.log_imul_constraints(),
270			&intmul_scale,
271			&mut operand_evals,
272		),
273		absent_or_claimed::<_, BINMUL_ARITY>(
274			cs.log_bmul_constraints(),
275			&binmul_scale,
276			&mut operand_evals,
277		),
278	]
279	.concat();
280	debug_assert_eq!(operand_claims.len(), OPERATION_ARITIES.iter().sum::<usize>());
281
282	Ok(ReductionOutput {
283		r_rho: r_rho.to_vec(),
284		r_x,
285		z_challenge,
286		operand_claims,
287	})
288}
289
290/// Reads the public segment's evaluation and reduces it onto the segment's packed form.
291///
292/// The shift closes over the public segment as a bit matrix: its multilinear is claimed at `r_j`
293/// over the bit within a word and the low coordinates of `r_y` over the word index. Evaluating
294/// that here would cost the verifier the bits of every public word. So the prover states the
295/// evaluation instead, and it is reduced in two steps:
296///
297/// 1. a ring-switch onto the packed segment — two words to a field element — leaving the claim
298///    `sum_x P(x) A(x)` against the ring-switching indicator;
299/// 2. a sumcheck over the packed segment's own variables, leaving one evaluation of each factor.
300///
301/// Nothing here is committed, so the verifier finishes on its own, with field arithmetic and no
302/// word bits: it evaluates the packed segment's multilinear from the words it holds, and the
303/// indicator from its succinct formula.
304///
305/// The reduction stands on its own, sharing nothing with the trace's: that one ends in a committed
306/// opening, this one in two evaluations the verifier computes from values it already has.
307///
308/// # Returns
309///
310/// The public segment over the shift's whole index space, which is what
311/// [`shift::check_eval`](crate::protocols::shift::check_eval) reconstructs the trace evaluation
312/// from: the claim scaled by the eq-zero factors of the word-index coordinates above the segment's
313/// span.
314///
315/// # Preconditions
316///
317/// * `r_y` must have at least as many coordinates as the packed segment spans words
318///
319/// # Errors
320///
321/// Returns an error if the ring-switch, the sumcheck, or its final check against the public words
322/// fails.
323pub fn verify_public_eval<Channel>(
324	cs: &ConstraintSystem,
325	inout: InoutSegment,
326	public: &[Channel::Word],
327	r_j: &[Channel::Elem],
328	r_y: &[Channel::Elem],
329	channel: &mut Channel,
330) -> Result<Channel::Elem, Error>
331where
332	Channel: WordIPVerifierChannel<B128>,
333	Channel::Elem: FieldOps<Scalar = B128> + From<B128>,
334{
335	// The claim is over the packed segment, so it spans whole field elements: a segment shorter
336	// than one still spans one, reading the words past its end as zero.
337	let log_public_elems = cs
338		.log_public_words(inout)
339		.saturating_sub(LOG_WORDS_PER_ELEM);
340	let log_packed_words = log_public_elems + LOG_WORDS_PER_ELEM;
341
342	// The claimed evaluation's point: the bit within a word, then the words the segment spans.
343	let eval_point = [r_j, &r_y[..log_packed_words]].concat();
344
345	let public_eval = channel.recv_one()?;
346	let RingSwitchVerifyOutput {
347		eq_r_double_prime,
348		sumcheck_claim,
349	} = ring_switch::verify(public_eval.clone(), &eval_point, channel)?;
350
351	// Reduce the ring-switched claim to one evaluation of each factor.
352	let SumcheckOutput {
353		eval,
354		challenges: mut r_public,
355	} = verify_sumcheck(log_public_elems, 2, sumcheck_claim, channel)?;
356	r_public.reverse();
357
358	// Close it out against the two factors, both of which the verifier computes: the packed
359	// segment's multilinear, over the words it already holds, and the ring-switching indicator.
360	let log_packing = <B128 as ExtensionField<B1>>::LOG_DEGREE;
361	let packed_public = channel
362		.pack_words(public)
363		.into_iter()
364		// The words past the segment's end read as zero, so the elements past its packed length do
365		// too, up to the power-of-two span the sumcheck ran over.
366		.chain(iter::repeat_with(Channel::Elem::zero))
367		.take(1 << log_public_elems)
368		.collect::<Vec<_>>();
369	let packed_eval = evaluate_inplace_scalars(packed_public, &r_public);
370	let rs_eq_eval =
371		eval_rs_eq(1 << r_public.len(), &eval_point[log_packing..], &r_public, &eq_r_double_prime);
372	channel.assert_zero(packed_eval * rs_eq_eval - eval)?;
373
374	// Extend the claim from the segment's own span to the shift's whole word-index space. Every
375	// word above the segment is zero, so each extra coordinate contributes its eq-zero factor.
376	Ok(eq_ind_zero(&r_y[log_packed_words..]) * public_eval)
377}
378
379/// An operation's operand evaluations scaled by its padding factor, or zeros when it is absent.
380///
381/// A present operation takes its `ARITY` evaluations off the front of `evals`.
382/// An absent operation has an empty constraint set, so the shift finds no key naming it.
383/// Its zero claim therefore contributes nothing.
384fn absent_or_claimed<F: FieldOps, const ARITY: usize>(
385	log_n_constraints: Option<usize>,
386	scale: &F,
387	evals: impl Iterator<Item = F>,
388) -> Vec<F> {
389	match log_n_constraints {
390		Some(_) => evals.take(ARITY).map(|eval| eval * scale.clone()).collect(),
391		None => vec![F::zero(); ARITY],
392	}
393}