Skip to main content

binius_spartan_verifier/
lib.rs

1// Copyright 2025 Irreducible Inc.
2// Copyright 2026 The Binius Developers
3
4//! Spartan-based proof verification for Binius64 constraint systems.
5//!
6//! This crate provides the [`Verifier`] struct for verifying zero-knowledge proofs
7//! generated by `binius_spartan_prover`. It implements the Spartan protocol adapted
8//! for Binius64's constraint system.
9//!
10//! # When to use this crate
11//!
12//! Use this crate when you have a constraint system built with `binius_spartan_frontend`
13//! and need to verify a Spartan-based proof. This is an alternative to the main
14//! `binius_verifier` crate.
15//!
16//! # Key types
17//!
18//! - [`Verifier`] - Main verification interface; call [`Verifier::setup`] with a constraint system,
19//!   then [`Verifier::verify`] with a proof and public inputs
20//! - [`IOPVerifier`] - Core IOP verification logic, independent of the compilation strategy
21//! - [`Error`] - Error type returned when proof verification fails
22//!
23//! # Related crates
24//!
25//! - `binius_spartan_prover` - Proving counterpart
26//! - `binius_spartan_frontend` - Constraint system builder for Spartan
27//! - `binius_verifier` - Alternative verification backend
28
29#![warn(rustdoc::missing_crate_level_docs)]
30
31pub mod config;
32pub mod constraint_system;
33pub mod wiring;
34pub mod wrapper;
35
36use std::{marker::PhantomData, rc::Rc};
37
38use binius_field::{BinaryField, Field, field::FieldOps};
39use binius_hash::HashSuite;
40use binius_iop::{
41	basefold,
42	basefold::compiler::BaseFoldVerifierCompiler,
43	channel::{
44		IOPVerifierChannel, OracleSchedule,
45		oracle_setup::{DummyElem, OracleSetupChannel},
46	},
47	fri,
48	merkle_tree::BinaryMerkleTreeScheme,
49};
50use binius_ip::{channel::IPVerifierChannel, libra, mlecheck, sumcheck};
51use binius_math::{
52	multilinear::{eq::eq_ind_partial_eval_scalars, hypercube::OneCube},
53	univariate::evaluate_univariate,
54};
55use binius_spartan_frontend::constraint_system::{ConstraintSystem, WitnessSegment};
56use binius_transcript::{VerifierTranscript, fiat_shamir::Challenger};
57use binius_utils::{DeserializeBytes, checked_arithmetics::checked_log_2};
58use digest::Output;
59
60use crate::constraint_system::{BlindingInfo, ConstraintSystemPadded};
61
62pub const SECURITY_BITS: usize = 96;
63
64/// Output of the multiplication constraint check verification.
65#[derive(Debug, Clone)]
66pub struct MulcheckOutput<F> {
67	/// Evaluation of operand A at the challenge point.
68	pub a_eval: F,
69	/// Evaluation of operand B at the challenge point.
70	pub b_eval: F,
71	/// Evaluation of operand C at the challenge point.
72	pub c_eval: F,
73	/// Evaluation of the mask polynomial at the challenge point.
74	pub mask_eval: F,
75	/// The challenge point from the sumcheck reduction.
76	pub r_x: Vec<F>,
77}
78
79/// IOP verifier for a particular constraint system.
80///
81/// This struct encapsulates the constraint system, providing the core verification logic
82/// independent of the specific IOP compilation strategy. Most users should use [`Verifier`]
83/// instead, which wraps this with a BaseFold compiler.
84#[derive(Debug, Clone)]
85pub struct IOPVerifier<F: Field> {
86	constraint_system: ConstraintSystemPadded<F>,
87}
88
89/// Struct for verifying instances of a particular constraint system.
90///
91/// The [`Self::setup`] constructor determines public parameters for proving instances of the given
92/// constraint system. Then [`Self::verify`] is called one or more times with individual instances.
93#[derive(Clone)]
94pub struct Verifier<F, H>
95where
96	F: BinaryField,
97	H: HashSuite,
98{
99	iop_verifier: IOPVerifier<F>,
100	/// BaseFold ZK compiler for creating verifier channels.
101	basefold_compiler: BaseFoldVerifierCompiler<F>,
102	/// The verifier creates its Merkle transcript channels with the hash suite `H`.
103	_hash_marker: PhantomData<H>,
104}
105
106impl<F: Field> IOPVerifier<F> {
107	/// Constructs an IOP verifier for a constraint system.
108	pub const fn new(constraint_system: ConstraintSystemPadded<F>) -> Self {
109		Self { constraint_system }
110	}
111
112	pub const fn constraint_system(&self) -> &ConstraintSystemPadded<F> {
113		&self.constraint_system
114	}
115
116	/// Returns the oracle schedule for the IOP channel.
117	///
118	/// This describes the oracles (precommit, witness and mask) that the prover commits to, grouped
119	/// into the rounds they are committed in.
120	///
121	/// The schedule is derived by replaying the oracle-receiving sequence against an
122	/// [`OracleSetupChannel`] (which records each `recv_oracle` without doing real verification),
123	/// rather than hardcoding it. IronSpartan proofs are always zero-knowledge. The precommit
124	/// oracle is received by the outer [`Verifier::verify`] before it delegates to
125	/// [`Self::verify`], so it is recorded here first to match that order.
126	pub fn oracle_schedule(&self) -> OracleSchedule
127	where
128		F: BinaryField,
129	{
130		let cs = &self.constraint_system;
131		let mut channel = OracleSetupChannel::new(true);
132		// Record the precommit oracle first (`OracleSetupChannel` implements the channel trait for
133		// every `F`, so the trait is named explicitly to fix `F`); the `verify` call below fixes it
134		// for the rest of the sequence.
135		<OracleSetupChannel as IOPVerifierChannel<F>>::recv_oracle(
136			&mut channel,
137			cs.precommit_len(),
138			true,
139		)
140		.expect("OracleSetupChannel::recv_oracle is infallible");
141		let public = vec![DummyElem::<F>::default(); 1 << cs.log_public()];
142		// Discarded: the setup channel performs no real verification; we only read back the
143		// recorded oracle schedule.
144		let _ = self.verify((), &public, &mut channel);
145		channel.into_oracle_schedule()
146	}
147
148	/// Verifies a proof using an IOP channel.
149	///
150	/// This is the core verification logic, independent of the specific IOP compilation strategy.
151	/// For most users, [`Verifier::verify`] is the simpler interface.
152	///
153	/// # Arguments
154	///
155	/// * `precommit_oracle` - Handle to the precommit oracle, received from the channel by the
156	///   caller before invoking `verify`.
157	/// * `public` - The public inputs to the constraint system
158	/// * `channel` - The IOP verifier channel
159	///
160	/// # Returns
161	///
162	/// `Ok(())` if the proof is valid, `Err(_)` otherwise.
163	pub fn verify<Channel>(
164		&self,
165		precommit_oracle: Channel::Oracle,
166		public: &[Channel::Elem],
167		channel: &mut Channel,
168	) -> Result<(), Error>
169	where
170		F: BinaryField,
171		Channel: IOPVerifierChannel<F>,
172	{
173		let cs = &self.constraint_system;
174
175		// Check that the public input length is correct
176		if public.len() != 1 << cs.log_public() {
177			return Err(Error::IncorrectPublicInputLength {
178				expected: 1 << cs.log_public(),
179				actual: public.len(),
180			});
181		}
182
183		// Receive the private and mask oracle commitments.
184		// The private witness is witness-dependent.
185		// The mask is a fresh random draw, not witness data.
186		// It is still flagged witness-dependent so the protocol keeps treating it as secret.
187		let private_oracle = channel.recv_oracle(cs.private_len(), true)?;
188		let (m_n, m_d) = cs.mask_dims();
189		let mask_oracle = channel.recv_oracle(1 << (m_n + m_d), true)?;
190
191		// Verify the multiplication constraints.
192		let MulcheckOutput {
193			a_eval,
194			b_eval,
195			c_eval,
196			mask_eval,
197			r_x,
198		} = verify_mulcheck(cs, channel)?;
199
200		// λ is the batching challenge for the constraint operands
201		let lambda = channel.sample();
202
203		// Batch together the constraint operand evaluation claims.
204		let batched_sum = evaluate_univariate(&[a_eval, b_eval, c_eval], &lambda);
205
206		// Compute rₓ^⊤ (M_A + λ M_B + λ² M_C) x. Shared via `Rc` so the transparent closures can
207		// own it and outlive this call (the opening is deferred to the channel's `finish()`). `Rc`
208		// suffices over `Arc` because the closures (`TransparentEvalFn`, no `Send` bound) and the
209		// channel never cross a thread boundary.
210		let r_x_tensor: Rc<[Channel::Elem]> = eq_ind_partial_eval_scalars(&r_x).into();
211
212		// The public segment's contribution to the operand evaluations.
213		let public_eval =
214			wiring::evaluate_wiring_mle_public(cs.mul_constraints(), public, &lambda, &r_x_tensor);
215
216		// Prover sends the precommit segment's contribution to the operand evaluations.
217		let precommit_claim = channel.recv_one()?;
218
219		let private_claim = batched_sum - public_eval - precommit_claim.clone();
220
221		// Build one transparent closure per oracle relation.
222		// The two wiring closures share the multiplication constraints through a single `Rc`.
223		// They own this handle and are `'static`, outliving this call for the deferred opening.
224		let mul_constraints: Rc<[_]> = cs.mul_constraints().into();
225		let precommit_transparent = wiring::eval_transparent(
226			mul_constraints.clone(),
227			WitnessSegment::Precommit,
228			r_x_tensor.clone(),
229			lambda.clone(),
230		);
231		let private_transparent =
232			wiring::eval_transparent(mul_constraints, WitnessSegment::Private, r_x_tensor, lambda);
233		let mask_transparent = mask_transparent(cs, &r_x);
234
235		// Verify all oracle relations
236		channel.verify_oracle_relation(precommit_oracle, precommit_transparent, precommit_claim)?;
237		channel.verify_oracle_relation(private_oracle, private_transparent, private_claim)?;
238		channel.verify_oracle_relation(mask_oracle, mask_transparent, mask_eval)?;
239
240		Ok(())
241	}
242}
243
244impl<F, H> Verifier<F, H>
245where
246	F: BinaryField,
247	H: HashSuite,
248	Output<H::LeafHash>: DeserializeBytes,
249{
250	/// Constructs a verifier for a constraint system.
251	///
252	/// See [`Verifier`] struct documentation for details.
253	pub fn setup(
254		constraint_system: ConstraintSystem<F>,
255		log_inv_rate: usize,
256	) -> Result<Self, Error> {
257		// Modify the constraint system for zero-knowledge.
258		let n_test_queries = fri::calculate_n_test_queries(SECURITY_BITS, log_inv_rate);
259		let blinding_info = BlindingInfo::default();
260		let constraint_system = ConstraintSystemPadded::new(constraint_system, blinding_info);
261
262		let iop_verifier = IOPVerifier::new(constraint_system);
263		let merkle_scheme = BinaryMerkleTreeScheme::<F, H>::new();
264
265		// Create the BaseFold ZK compiler for IOP verification
266		let basefold_compiler = BaseFoldVerifierCompiler::new(
267			&merkle_scheme,
268			iop_verifier.oracle_schedule(),
269			log_inv_rate,
270			n_test_queries,
271		);
272
273		Ok(Self {
274			iop_verifier,
275			basefold_compiler,
276			_hash_marker: PhantomData,
277		})
278	}
279
280	/// Returns a reference to the IOP verifier.
281	pub const fn iop_verifier(&self) -> &IOPVerifier<F> {
282		&self.iop_verifier
283	}
284
285	pub const fn constraint_system(&self) -> &ConstraintSystemPadded<F> {
286		self.iop_verifier.constraint_system()
287	}
288
289	/// Returns a reference to the BaseFold ZK verifier compiler.
290	pub const fn iop_compiler(&self) -> &BaseFoldVerifierCompiler<F> {
291		&self.basefold_compiler
292	}
293
294	/// Verifies a proof against the constraint system.
295	///
296	/// # Arguments
297	///
298	/// * `public` - The public inputs to the constraint system
299	/// * `transcript` - The verifier transcript for Fiat-Shamir
300	///
301	/// # Preconditions
302	///
303	/// * The public input length must match the constraint system's public input size
304	pub fn verify<Challenger_: Challenger>(
305		&self,
306		public: &[F],
307		transcript: &mut VerifierTranscript<Challenger_>,
308	) -> Result<(), Error> {
309		// Verifier observes the public input (includes it in Fiat-Shamir).
310		transcript.observe().write_slice(public);
311
312		// Create channel, receive the precommit oracle, and delegate to IOPVerifier::verify. The
313		// IOP verifier only queues the oracle relations; `finish` runs the single combined opening.
314		let mut channel = self
315			.basefold_compiler
316			.create_channel_from_transcript::<H, Challenger_, _>(transcript);
317		let cs = self.constraint_system();
318		let precommit_oracle = channel.recv_oracle(cs.precommit_len(), true)?;
319		self.iop_verifier
320			.verify(precommit_oracle, public, &mut channel)?;
321		channel.finish()?;
322		Ok(())
323	}
324}
325
326fn verify_mulcheck<F, C>(
327	cs: &ConstraintSystemPadded<F>,
328	channel: &mut C,
329) -> Result<MulcheckOutput<C::Elem>, Error>
330where
331	F: BinaryField,
332	C: IPVerifierChannel<F>,
333{
334	let log_mul_constraints = checked_log_2(cs.mul_constraints().len());
335
336	// Sample random evaluation point
337	let r_mulcheck = channel.sample_many(log_mul_constraints);
338
339	// Verify the zerocheck for the multiplication constraints.
340	let mlecheck::VerifyZKOutput {
341		eval,
342		mask_eval,
343		challenges: mut r_x,
344	} = mlecheck::verify_zk(&r_mulcheck, 2, C::Elem::zero(), channel)?;
345
346	// Reverse because sumcheck binds high-to-low variable indices.
347	r_x.reverse();
348
349	// Read the claimed evaluations
350	let [a_eval, b_eval, c_eval] = channel.recv_array()?;
351
352	channel.assert_zero(a_eval.clone() * b_eval.clone() - c_eval.clone() - eval)?;
353
354	Ok(MulcheckOutput {
355		a_eval,
356		b_eval,
357		c_eval,
358		mask_eval,
359		r_x,
360	})
361}
362
363/// Returns a closure that evaluates the mask transparent polynomial at a given point.
364fn mask_transparent<F: Field, E: FieldOps + 'static>(
365	cs: &ConstraintSystemPadded<F>,
366	r_x: &[E],
367) -> binius_iop::channel::TransparentEvalFn<E> {
368	let (_m_n, m_d) = cs.mask_dims();
369	let n_vars = r_x.len();
370	let mask_degree = 2; // quadratic composition
371	let r_x = r_x.to_vec();
372
373	Box::new(move |point: &[E]| {
374		// Split into query_k (low-order bits) and query_j (high-order bits).
375		let (query_k, query_j) = point.split_at(m_d);
376
377		libra::libra_eval::<OneCube, _>(&r_x, query_j, query_k, n_vars, mask_degree)
378	})
379}
380
381#[derive(Debug, thiserror::Error)]
382pub enum Error {
383	#[error("FRI error: {0}")]
384	FRI(#[from] fri::Error),
385	#[error("Sumcheck error: {0}")]
386	Sumcheck(#[from] sumcheck::Error),
387	#[error("BaseFold error: {0}")]
388	BaseFold(#[from] basefold::Error),
389	#[error("Transcript error: {0}")]
390	Transcript(#[from] binius_transcript::Error),
391	#[error("IOP channel error: {0}")]
392	IOPChannel(#[from] binius_iop::channel::Error),
393	#[error("IP channel error: {0}")]
394	IPChannel(#[from] binius_ip::channel::Error),
395	#[error("incorrect public inputs length: expected {expected}, got {actual}")]
396	IncorrectPublicInputLength { expected: usize, actual: usize },
397	#[error("incorrect reduction output of the multiplication check")]
398	IncorrectMulCheckEvaluation,
399}