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}