Skip to main content

binius_verifier/
verify.rs

1// Copyright 2025 Irreducible Inc.
2// Copyright 2026 The Binius Developers
3
4use std::marker::PhantomData;
5
6use binius_core::{
7	constraint_system::{ConstraintSystem, InoutSegment},
8	word::Word,
9};
10use binius_field::{BinaryField, ExtensionField, FieldOps, Rijndael8b as B8};
11use binius_hash::HashSuite;
12use binius_iop::{
13	basefold::compiler::BaseFoldVerifierCompiler,
14	channel::{IOPVerifierChannel, OracleSchedule, oracle_setup::OracleSetupChannel},
15};
16use binius_ip::channel::{IPVerifierChannel, WordIPVerifierChannel};
17use binius_math::{BinarySubspace, univariate::EvaluationDomain};
18use binius_transcript::{VerifierTranscript, fiat_shamir::Challenger};
19use binius_utils::DeserializeBytes;
20use digest::Output;
21use itertools::chain;
22
23use super::error::Error;
24use crate::{
25	config::{B1, B128, LOG_WORDS_PER_ELEM, PROVER_SMALL_FIELD_ZEROCHECK_CHALLENGES},
26	fri::{FRIParams, calculate_n_test_queries},
27	merkle_tree::BinaryMerkleTreeScheme,
28	protocols::{
29		bitand::{AndCheckOutput, UnivariateSkipOutput, verify_univariate_skip},
30		rerand::{self, OperandClaims},
31		shift::{self, WiringEvalClaim, WiringInfo},
32	},
33	reduction::{ReductionOutput, reduce_constraints, verify_public_eval},
34	ring_switch,
35};
36
37pub const SECURITY_BITS: usize = 96;
38
39/// IOP verifier for a particular constraint system.
40///
41/// This struct encapsulates the constraint system, providing the core verification logic
42/// independent of the specific IOP compilation strategy. Most users should use [`Verifier`]
43/// instead, which wraps this with a BaseFold compiler.
44#[derive(Debug, Clone)]
45pub struct IOPVerifier {
46	constraint_system: ConstraintSystem,
47	log_public_words: usize,
48	/// The constraint system's wiring matrix.
49	wiring: WiringInfo,
50}
51
52impl IOPVerifier {
53	/// Constructs an IOP verifier for a constraint system.
54	///
55	/// The constraint system must already be validated via [`ConstraintSystem::validate`].
56	///
57	/// # Panics
58	///
59	/// Panics if the wiring matrix's addresses do not fit; see [`WiringInfo::new`].
60	pub fn new(constraint_system: ConstraintSystem, log_public_words: usize) -> Self {
61		let wiring = WiringInfo::new(&constraint_system, InoutSegment::Public);
62		Self {
63			constraint_system,
64			log_public_words,
65			wiring,
66		}
67	}
68
69	/// Returns the constraint system.
70	pub const fn constraint_system(&self) -> &ConstraintSystem {
71		&self.constraint_system
72	}
73
74	/// Consumes the IOP verifier and returns the inner constraint system.
75	pub fn into_constraint_system(self) -> ConstraintSystem {
76		self.constraint_system
77	}
78
79	/// Returns the wiring matrix, which a wiring claim is settled against.
80	pub const fn wiring(&self) -> &WiringInfo {
81		&self.wiring
82	}
83
84	/// Returns log2 of the number of public constants and input/output words.
85	pub const fn log_public_words(&self) -> usize {
86		self.log_public_words
87	}
88
89	/// Returns log2 of the number of field elements in the packed trace.
90	///
91	/// The trace oracle commits only the witness's hidden segment; the public segment is a
92	/// verifier-known polynomial. The shift reduction claims that segment over the shared
93	/// word-index space, which spans the wider of the two segments, so the claim is over
94	/// `log_segment_words` words. The oracle itself holds only the [`Self::n_witness_elems`] the
95	/// hidden words fill, and the ring-switch accounts for the coordinates in between.
96	///
97	/// ## Preconditions
98	/// * the wider segment spans at least one field element's worth of words, which every system
99	///   with more than one public or private value satisfies
100	pub const fn log_witness_elems(&self) -> usize {
101		let log_segment_words = self
102			.constraint_system
103			.log_segment_words(InoutSegment::Public);
104		assert!(
105			log_segment_words >= LOG_WORDS_PER_ELEM,
106			"the committed trace is a whole number of field elements, so the wider value \
107			 segment spans at least that many words"
108		);
109		log_segment_words - LOG_WORDS_PER_ELEM
110	}
111
112	/// Returns the number of field elements the committed trace words fill.
113	pub const fn n_witness_elems(&self) -> usize {
114		self.constraint_system
115			.n_hidden_words(InoutSegment::Public)
116			.div_ceil(1 << LOG_WORDS_PER_ELEM)
117	}
118
119	/// Returns log2 of the number of words in the committed trace.
120	pub const fn log_witness_words(&self) -> usize {
121		self.log_witness_elems() + LOG_WORDS_PER_ELEM
122	}
123
124	/// Returns the oracle schedule for the IOP channel.
125	///
126	/// This describes the oracles (the witness) that the prover commits to, grouped into the rounds
127	/// they are committed in.
128	///
129	/// `is_zk` is the protocol-level zero-knowledge flag: in a ZK proof the witness oracle is
130	/// masked, in a transparent proof it is not. The flag is taken per call so that a non-ZK
131	/// oracle can still participate in a ZK protocol (e.g. indexed relation openings).
132	///
133	/// The schedule is derived by running [`Self::verify`] against an [`OracleSetupChannel`], which
134	/// records each oracle received (via `recv_oracle`) without performing any real verification.
135	/// This keeps the schedule automatically in lockstep with the `recv_oracle` calls in
136	/// `verify`, rather than duplicating it here.
137	pub fn oracle_schedule(&self, is_zk: bool) -> OracleSchedule {
138		let mut channel = OracleSetupChannel::new(is_zk);
139		// The setup channel carries concrete words, so the statement it verifies against is just
140		// words — handing them through `observe_words` to get them back buys nothing.
141		let inout = vec![Word::ZERO; self.constraint_system.n_inout];
142		// The result is discarded: the setup channel performs no real verification (all `recv_*`
143		// return zero, `assert_zero` is a no-op), so we only read back the recorded oracle
144		// schedule. Its wiring claim goes with it, since discharging one records no oracle.
145		let _ = self.verify(&inout, &mut channel);
146		channel.into_oracle_schedule()
147	}
148
149	/// Verifies a proof using an IOP channel.
150	///
151	/// This is the core verification logic, independent of the specific IOP compilation strategy.
152	/// For most users, [`Verifier::verify`] is the simpler interface.
153	///
154	/// `inout` is the statement as the channel carries it, which is what
155	/// [`WordIPVerifierChannel::observe_words`] returns: the caller observes the concrete words and
156	/// passes on what comes back. A channel that carries words as wires introduces them there, so
157	/// the verification below reads the statement symbolically rather than as fixed data.
158	///
159	/// The reduction's wiring evaluation comes back as a [`WiringEvalClaim`] rather than being
160	/// checked here, so the caller chooses how the constraint system is read: by computing the
161	/// evaluation, or by any other argument that opens the claim.
162	pub fn verify<Channel>(
163		&self,
164		inout: &[Channel::Word],
165		channel: &mut Channel,
166	) -> Result<WiringEvalClaim<'_, Channel::Elem>, Error>
167	where
168		Channel: IOPVerifierChannel<B128> + WordIPVerifierChannel<B128>,
169		Channel::Elem: FieldOps<Scalar = B128> + From<B128>,
170	{
171		// The caller passes only the inout values. The constants are already part of the
172		// constraint system, so restating them would be redundant — and a caller that restated
173		// them wrongly would be describing a different system.
174		if inout.len() != self.constraint_system.n_inout {
175			return Err(Error::IncorrectPublicInputLength {
176				expected: self.constraint_system.n_inout,
177				actual: inout.len(),
178			});
179		}
180
181		// The shift reduction reads the whole public segment, which is the constants followed by
182		// the inout values — the order the value vector places them in. The constants are fixed by
183		// the constraint system, so they lift into the channel's word type as themselves.
184		let public = self
185			.constraint_system
186			.constants
187			.iter()
188			.map(|&word| Channel::Word::from(word))
189			.chain(inout.iter().cloned())
190			.collect::<Vec<_>>();
191
192		let _verify_guard =
193			tracing::info_span!("Verify", operation = "verify", perfetto_category = "operation")
194				.entered();
195
196		// Receive the trace oracle commitment via channel. The trace is the witness, so it is
197		// witness-dependent (masked in a ZK proof).
198		let trace_oracle = channel.recv_oracle(self.n_witness_elems(), true)?;
199
200		// Reduce every constraint to one claim on the committed trace.
201		let cs = self.constraint_system();
202		// A single circuit has no instance coordinates, so `r_rho` is empty.
203		let ReductionOutput {
204			r_x,
205			z_challenge,
206			operand_claims,
207			..
208		} = reduce_constraints(cs, 0, channel)?;
209
210		// Reduce the operand claims to one witness evaluation.
211		let shift_output = {
212			let _guard = tracing::info_span!(
213				"[phase] Verify Shift Reduction",
214				phase = "verify_shift_reduction",
215				perfetto_category = "phase"
216			)
217			.entered();
218			shift::verify::<B128, _>(
219				cs.log_segment_words(InoutSegment::Public),
220				&operand_claims,
221				channel,
222			)?
223		};
224		let shift::VerifyOutput {
225			r_j,
226			r_y,
227			witness_eval,
228			..
229		} = &shift_output;
230
231		// Tie in the public values, then close the shift reduction against them.
232		let wiring = {
233			let _guard = tracing::info_span!(
234				"[phase] Verify Public Input",
235				phase = "verify_public_input",
236				perfetto_category = "phase"
237			)
238			.entered();
239			let public_eval =
240				verify_public_eval(cs, InoutSegment::Public, &public, r_j, r_y, channel)?;
241			let shift_domain = BinarySubspace::<B8>::with_dim(Word::LOG_BITS).isomorphic::<B128>();
242			shift::check_eval::<B128, _>(
243				&self.wiring,
244				public_eval,
245				&r_x,
246				&shift_domain,
247				&z_challenge,
248				&shift_output,
249				channel,
250			)?
251		};
252
253		// [phase] Ring-Switching + Verify PCS Opening
254		let pcs_guard = tracing::info_span!(
255			"[phase] Verify PCS Opening",
256			phase = "verify_pcs_opening",
257			perfetto_category = "phase"
258		)
259		.entered();
260
261		// Ring-switching verification of the witness claim.
262		// Without instance coordinates, the trace opens at `r_j || r_y`.
263		let eval_point = [r_j.as_slice(), r_y].concat();
264		let ring_switch::RingSwitchVerifyOutput {
265			eq_r_double_prime,
266			sumcheck_claim,
267		} = ring_switch::verify(witness_eval.clone(), &eval_point, channel)?;
268
269		let log_packing = <B128 as ExtensionField<B1>>::LOG_DEGREE;
270		let eval_point_high = eval_point[log_packing..].to_vec();
271
272		let n_witness_elems = self.n_witness_elems();
273		let transparent = Box::new(move |point: &[Channel::Elem]| {
274			ring_switch::eval_rs_eq(
275				n_witness_elems,
276				&eval_point_high,
277				point,
278				eq_r_double_prime.as_ref(),
279			)
280		});
281
282		// Verify oracle relations (runs BaseFold internally and verifies the product check). The
283		// intmul pushforward relation, when the IntMul reduction ran, was already queued inside
284		// phase 5.
285		channel.verify_oracle_relation(trace_oracle, transparent, sumcheck_claim)?;
286
287		drop(pcs_guard);
288
289		Ok(wiring)
290	}
291
292	/// Observes the statement, verifies against it, and discharges the wiring claim in the field.
293	///
294	/// This is the whole verification for a channel that carries field values rather than wires.
295	/// Observing is done here rather than by the caller.
296	/// Such a channel has no other use for the concrete words.
297	pub fn verify_statement<Channel>(
298		&self,
299		inout: &[Word],
300		channel: &mut Channel,
301	) -> Result<(), Error>
302	where
303		Channel: IOPVerifierChannel<B128, Elem = B128> + WordIPVerifierChannel<B128>,
304	{
305		let inout = channel.observe_words(inout);
306		self.verify(&inout, channel)?.check_native()?;
307		Ok(())
308	}
309}
310
311/// Struct for verifying instances of a particular constraint system.
312///
313/// The [`Self::setup`] constructor determines public parameters for proving instances of the given
314/// constraint system. Then [`Self::verify`] is called one or more times with individual instances.
315#[derive(Clone)]
316pub struct Verifier<H: HashSuite> {
317	/// The constraint system and the reduction that opens it, independent of the commitment.
318	iop_verifier: IOPVerifier,
319	/// The commitment scheme's parameters, chosen once at setup.
320	iop_compiler: BaseFoldVerifierCompiler<B128>,
321	/// The verifier creates its Merkle transcript channels with the hash suite `H`.
322	_hash_marker: PhantomData<H>,
323}
324
325impl<H> Verifier<H>
326where
327	H: HashSuite,
328	Output<H::LeafHash>: DeserializeBytes,
329{
330	/// Constructs a verifier for a constraint system.
331	///
332	/// See [`Verifier`] struct documentation for details.
333	///
334	/// # Errors
335	///
336	/// Returns an error when the constraint system is invalid.
337	pub fn setup(constraint_system: ConstraintSystem, log_inv_rate: usize) -> Result<Self, Error> {
338		constraint_system.validate()?;
339
340		let log_public_words = constraint_system.log_public_words(InoutSegment::Public);
341
342		let iop_verifier = IOPVerifier::new(constraint_system, log_public_words);
343
344		// A plain `Verifier` produces a transparent (non-ZK) proof, so the witness oracle is not
345		// masked.
346		let oracle_schedule = iop_verifier.oracle_schedule(false);
347
348		let merkle_scheme = BinaryMerkleTreeScheme::<B128, H>::new();
349
350		// The query count is fixed by the rate and the soundness target.
351		let n_test_queries = calculate_n_test_queries(SECURITY_BITS, log_inv_rate);
352
353		let iop_compiler = BaseFoldVerifierCompiler::new(
354			&merkle_scheme,
355			oracle_schedule,
356			log_inv_rate,
357			n_test_queries,
358		);
359
360		Ok(Self {
361			iop_verifier,
362			iop_compiler,
363			_hash_marker: PhantomData,
364		})
365	}
366
367	/// Returns a reference to the IOP verifier.
368	pub const fn iop_verifier(&self) -> &IOPVerifier {
369		&self.iop_verifier
370	}
371
372	/// Consumes the verifier and returns the inner IOP verifier.
373	pub fn into_iop_verifier(self) -> IOPVerifier {
374		self.iop_verifier
375	}
376
377	/// Returns log2 of the number of words in the witness.
378	pub const fn log_witness_words(&self) -> usize {
379		self.iop_verifier.log_witness_words()
380	}
381
382	/// Returns log2 of the number of field elements in the packed trace.
383	pub const fn log_witness_elems(&self) -> usize {
384		self.iop_verifier.log_witness_elems()
385	}
386
387	/// Returns the constraint system.
388	pub const fn constraint_system(&self) -> &ConstraintSystem {
389		self.iop_verifier.constraint_system()
390	}
391
392	/// Returns the chosen FRI parameters.
393	pub const fn fri_params(&self) -> &FRIParams<B128> {
394		self.iop_compiler.fri_params()
395	}
396
397	/// Returns log2 of the number of public constants and input/output words.
398	pub const fn log_public_words(&self) -> usize {
399		self.iop_verifier.log_public_words()
400	}
401
402	/// Returns the IOP compiler for creating verifier channels.
403	pub const fn iop_compiler(&self) -> &BaseFoldVerifierCompiler<B128> {
404		&self.iop_compiler
405	}
406
407	pub fn verify<Challenger_: Challenger>(
408		&self,
409		inout: &[Word],
410		transcript: &mut VerifierTranscript<Challenger_>,
411	) -> Result<(), Error> {
412		let cs = self.iop_verifier.constraint_system();
413
414		let _verify_scope = tracing::info_span!(
415			"Verify",
416			n_hidden_words = cs.n_hidden_words(InoutSegment::Public),
417			n_bitand = cs.and_constraints.len(),
418			n_intmul = cs.imul_constraints.len(),
419		)
420		.entered();
421
422		let mut channel = self
423			.iop_compiler
424			.create_channel_from_transcript::<H, Challenger_, _>(transcript);
425		self.iop_verifier.verify_statement(inout, &mut channel)?;
426		channel.finish()?;
427		Ok(())
428	}
429}
430
431/// Verifies the batched BitAnd check: `A & B == C` on every row.
432///
433/// This is the univariate-skip zerocheck of `A(Z, X) * B(Z, X) - C(Z, X) == 0` for all rows
434/// `(Z, X)`, where `Z` is the bit index within a 64-bit word and `X` is the row index. Its
435/// multilinear rounds are one sumcheck with the operand-column MLE-checks of `operands`; see
436/// [`rerand`].
437///
438/// # Arguments
439///
440/// - `log_constraint_count`: base-2 logarithm of the row count — the operand column length, which
441///   the prover zero-pads up to a power of two. The single-instance verifier passes `ceil(log2(n))`
442///   for `n` AND constraints; the batched M4 verifier adds its log instance count, since one row
443///   there is an (instance, constraint) pair.
444/// - `eval_domain`: the univariate-skip domain, one dimension above the 64-bit word, already lifted
445///   to `F`. The caller passes it so it matches the shift reduction's domain by construction.
446/// - `operands`: the multiplication reductions' per-bit operand claims. They must be in the
447///   transcript before this runs, since it draws the challenge that folds them.
448/// - `channel`: the verifier channel that reads messages and redraws Fiat-Shamir challenges.
449///
450/// # Errors
451///
452/// Returns an error if any sumcheck round message or the final consistency check fails.
453pub fn verify_bitand_reduction<F, C>(
454	log_constraint_count: usize,
455	eval_domain: &BinarySubspace<F>,
456	operands: &[OperandClaims<'_, C::Elem>],
457	channel: &mut C,
458) -> Result<AndCheckOutput<C::Elem>, Error>
459where
460	F: BinaryField + From<B8>,
461	C: IPVerifierChannel<F>,
462	// Used to make deterministic basis challenges symbolic
463	C::Elem: From<F>,
464{
465	let small_field_zerocheck_challenges = PROVER_SMALL_FIELD_ZEROCHECK_CHALLENGES
466		.into_iter()
467		.take(log_constraint_count)
468		.map(|b8_val| C::Elem::from(F::from(b8_val)))
469		.collect::<Vec<_>>();
470
471	let big_field_zerocheck_challenges =
472		channel.sample_many(log_constraint_count - small_field_zerocheck_challenges.len());
473
474	let zerocheck_challenges =
475		chain!(small_field_zerocheck_challenges, big_field_zerocheck_challenges)
476			.collect::<Vec<_>>();
477
478	let UnivariateSkipOutput { z_challenge, claim } = verify_univariate_skip(channel, eval_domain)?;
479	// The operand columns fold over the 64-point domain: the skip domain less its top dimension.
480	let lagrange = eval_domain
481		.reduce_dim(Word::LOG_BITS)
482		.lagrange_evals(&z_challenge);
483	let rerand = rerand::verify(&zerocheck_challenges, claim, &lagrange, operands, channel)?;
484	Ok(AndCheckOutput {
485		z_challenge,
486		rerand,
487	})
488}