Skip to main content

binius_spartan_prover/
lib.rs

1// Copyright 2025 Irreducible Inc.
2// Copyright 2026 The Binius Developers
3
4//! Spartan-based proof generation for Binius64 constraint systems.
5//!
6//! This crate provides the [`Prover`] struct for generating zero-knowledge proofs
7//! using the Spartan protocol adapted for Binius64's constraint system. It is the
8//! prover-side counterpart to `binius_spartan_verifier`.
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 generate a Spartan-based proof. This is an alternative to the main
14//! `binius_prover` crate.
15//!
16//! # Key types
17//!
18//! - [`Prover`] - Main proving interface; call [`Prover::setup`] with a verifier, then
19//!   [`Prover::prove`] with witness data
20//! - [`IOPProver`] - Core IOP proving logic, independent of the compilation strategy
21//!
22//! # Related crates
23//!
24//! - `binius_spartan_verifier` - Verification counterpart
25//! - `binius_spartan_frontend` - Constraint system builder for Spartan
26//! - `binius_prover` - Alternative proving backend
27
28#![warn(rustdoc::missing_crate_level_docs)]
29
30mod error;
31mod wiring;
32pub mod wrapper;
33
34use std::{
35	iter::{repeat_n, repeat_with},
36	marker::PhantomData,
37	ops::Deref,
38};
39
40use binius_alloc::{Allocator, BufferPool, VecLike};
41use binius_field::{BinaryField, Field, PackedField};
42use binius_hash_prover::ParallelHashSuite;
43use binius_iop_prover::{basefold::compiler::BaseFoldProverCompiler, channel::IOPProverChannel};
44use binius_ip_prover::{
45	channel::IPProverChannel,
46	libra,
47	sumcheck::{quadratic_mlecheck_prover, zk_mlecheck},
48};
49use binius_math::{
50	FieldBuffer, FieldSlice, FieldVec,
51	inner_product::inner_product_buffers,
52	multilinear::eq::eq_ind_partial_eval,
53	ntt::{NeighborsLastMultiThread, domain_context::GaoMateerPreExpanded},
54	univariate::evaluate_univariate,
55};
56use binius_spartan_frontend::constraint_system::{
57	MulConstraint, Witness, WitnessIndex, WitnessSegment,
58};
59use binius_spartan_verifier::{
60	Verifier,
61	constraint_system::{BlindingInfo, ConstraintSystemPadded},
62	wiring::evaluate_wiring_mle_public,
63};
64use binius_transcript::{ProverTranscript, fiat_shamir::Challenger};
65use binius_utils::{SerializeBytes, checked_arithmetics::checked_log_2, rayon::prelude::*};
66use digest::Output;
67pub use error::*;
68use itertools::chain;
69use rand::CryptoRng;
70
71use crate::wiring::{WiringTranspose, fold_constraints};
72
73type ProverNTT<F> = NeighborsLastMultiThread<GaoMateerPreExpanded<F>>;
74
75/// IOP prover for a particular constraint system.
76///
77/// This struct encapsulates the constraint system and pre-computed wiring transpose,
78/// providing the core proving logic independent of the specific IOP compilation strategy.
79/// Most users should use [`Prover`] instead, which wraps this with a BaseFold compiler.
80#[derive(Debug)]
81pub struct IOPProver<F: Field> {
82	constraint_system: ConstraintSystemPadded<F>,
83	precommit_wiring_transpose: WiringTranspose,
84	private_wiring_transpose: WiringTranspose,
85}
86
87/// Struct for proving instances of a particular constraint system.
88///
89/// The [`Self::setup`] constructor pre-processes reusable structures for proving instances of the
90/// given constraint system. Then [`Self::prove`] is called one or more times with individual
91/// instances.
92pub struct Prover<P, H>
93where
94	P: PackedField<Scalar: BinaryField>,
95	H: ParallelHashSuite,
96{
97	iop_prover: IOPProver<P::Scalar>,
98	basefold_compiler: BaseFoldProverCompiler<P, ProverNTT<P::Scalar>>,
99	/// The pool that recycles this prover's working buffers. It lives for the prover's lifetime,
100	/// so blocks freed by one `prove` call are reused by the next.
101	pool: BufferPool,
102	/// The prover creates its Merkle transcript channels with the hash suite `H`.
103	_hash_marker: PhantomData<H>,
104}
105
106impl<F: Field> IOPProver<F> {
107	/// Constructs an IOP prover for a constraint system.
108	pub fn new(constraint_system: ConstraintSystemPadded<F>) -> Self {
109		let precommit_wiring_transpose = WiringTranspose::transpose(
110			WitnessSegment::Precommit,
111			constraint_system.precommit_size(),
112			constraint_system.mul_constraints(),
113		);
114		let private_wiring_transpose = WiringTranspose::transpose(
115			WitnessSegment::Private,
116			constraint_system.private_size(),
117			constraint_system.mul_constraints(),
118		);
119		Self {
120			constraint_system,
121			precommit_wiring_transpose,
122			private_wiring_transpose,
123		}
124	}
125
126	pub const fn constraint_system(&self) -> &ConstraintSystemPadded<F> {
127		&self.constraint_system
128	}
129
130	/// Packs and commits the precommit segment of a witness on the channel.
131	///
132	/// This must be called before [`Self::prove`], and the returned oracle handle and packed
133	/// precommit buffer must be passed into `prove`. Callers that wrap the IOP (e.g. the ZK
134	/// wrapper) can invoke this separately so the precommit oracle handle is available before the
135	/// rest of the protocol runs.
136	pub fn commit_precommit<P, Channel, A>(
137		&self,
138		witness: &Witness<F>,
139		rng: &mut impl CryptoRng,
140		channel: &mut Channel,
141		alloc: &A,
142	) -> (Channel::Oracle, FieldVec<P, A>)
143	where
144		F: BinaryField,
145		P: PackedField<Scalar = F>,
146		Channel: IOPProverChannel<P, A>,
147		A: Allocator,
148	{
149		let cs = &self.constraint_system;
150		let precommit_blinding = *cs.blinding_info();
151		let precommit_packed = pack_and_blind_witness::<_, _, P>(
152			alloc,
153			cs.log_precommit() as usize,
154			witness.precommit(),
155			cs.n_precommit() as usize,
156			&precommit_blinding,
157			rng,
158		);
159		let precommit_oracle = channel.send_oracle(precommit_packed.as_view());
160		(precommit_oracle, precommit_packed)
161	}
162
163	/// Proves using an IOP channel interface.
164	///
165	/// This is the core proving logic, independent of the specific IOP compilation strategy.
166	/// For most users, [`Prover::prove`] is the simpler interface.
167	///
168	/// # Arguments
169	///
170	/// * `witness` - The witness values for the constraint system
171	/// * `precommit_oracle` - Oracle handle obtained from [`Self::commit_precommit`]
172	/// * `precommit_packed` - Packed precommit buffer obtained from [`Self::commit_precommit`]
173	/// * `rng` - Random number generator for blinding
174	/// * `channel` - The IOP prover channel (public input must be observed on transcript before
175	///   creating the channel; the precommit oracle must already have been committed on it via
176	///   [`Self::commit_precommit`])
177	pub fn prove<P, Channel, A>(
178		&self,
179		witness: &Witness<F>,
180		precommit_oracle: Channel::Oracle,
181		precommit_packed: FieldSlice<'_, P>,
182		mut rng: impl CryptoRng,
183		channel: &mut Channel,
184		alloc: &A,
185	) -> Result<(), Error>
186	where
187		F: BinaryField,
188		P: PackedField<Scalar = F>,
189		Channel: IOPProverChannel<P, A>,
190		A: Allocator,
191	{
192		let _prove_guard =
193			tracing::info_span!("Prove", operation = "prove", perfetto_category = "operation")
194				.entered();
195
196		let cs = &self.constraint_system;
197
198		// Check that the witness segments have the expected sizes
199		let expected_public_size = 1 << cs.log_public() as usize;
200		let expected_precommit_size = cs.precommit_size();
201		let expected_private_size = cs.private_size();
202		if witness.public().len() != expected_public_size {
203			return Err(Error::ArgumentError {
204				arg: "witness".to_string(),
205				msg: format!(
206					"public segment has {} elements, expected {}",
207					witness.public().len(),
208					expected_public_size
209				),
210			});
211		}
212		if witness.precommit().len() != expected_precommit_size {
213			return Err(Error::ArgumentError {
214				arg: "witness".to_string(),
215				msg: format!(
216					"precommit segment has {} elements, expected {}",
217					witness.precommit().len(),
218					expected_precommit_size
219				),
220			});
221		}
222		if witness.private().len() != expected_private_size {
223			return Err(Error::ArgumentError {
224				arg: "witness".to_string(),
225				msg: format!(
226					"private segment has {} elements, expected {}",
227					witness.private().len(),
228					expected_private_size
229				),
230			});
231		}
232
233		let log_mul_constraints = checked_log_2(cs.mul_constraints().len());
234
235		// Create mask buffer for the ZK mulcheck mask polynomial.
236		let (m_n, m_d) = cs.mask_dims();
237		let mask_degree = 2; // quadratic composition
238		let log_masks_buffer_size = m_n + m_d;
239
240		let masks_buffer = {
241			// Growing a pooled buffer past the block it was handed would reallocate and free that
242			// block at the element's alignment rather than the pool's, so the fill below takes
243			// exactly the allocated count.
244			let packed_len = 1 << log_masks_buffer_size.saturating_sub(P::LOG_WIDTH);
245			let mut values = alloc.alloc::<P>(packed_len);
246			values.extend(repeat_with(|| P::random(&mut rng)).take(packed_len));
247			FieldBuffer::new(log_masks_buffer_size, values)
248		};
249
250		// Pack private witness into field elements and add blinding
251		let blinding_info = cs.blinding_info();
252		let private_packed = pack_and_blind_witness::<_, _, P>(
253			alloc,
254			cs.log_private() as usize,
255			witness.private(),
256			cs.n_private() as usize,
257			blinding_info,
258			&mut rng,
259		);
260
261		// Send the private and mask oracles to the channel. The precommit oracle was committed
262		// by the caller via `commit_precommit` and passed in as `precommit_oracle`.
263		let private_oracle = channel.send_oracle(private_packed.as_view());
264		let mask_oracle = channel.send_oracle(masks_buffer.as_view());
265
266		let mulcheck_mask =
267			libra::Mask::new(log_mul_constraints, mask_degree, masks_buffer.as_view());
268
269		// Prove the multiplication constraints
270		let (mulcheck_evals, mask_eval, r_x) = prove_mulcheck::<F, P, _, _>(
271			cs.mul_constraints(),
272			witness.public(),
273			precommit_packed,
274			private_packed.as_view(),
275			mulcheck_mask,
276			&mut *channel,
277			alloc,
278		);
279
280		// λ is the batching challenge for the constraint operands
281		let lambda = channel.sample();
282
283		// Batch together the constraint operand evaluation claims.
284		let batched_sum = evaluate_univariate(&mulcheck_evals, &lambda);
285
286		// Compute eq indicator tensor for r_x (shared across all segment evaluations)
287		let r_x_tensor = eq_ind_partial_eval::<F>(&r_x);
288
289		// Compute rₓ^⊤ (M_A + λ M_B + λ² M_C) x
290		let public_eval = evaluate_wiring_mle_public(
291			cs.mul_constraints(),
292			witness.public(),
293			&lambda,
294			r_x_tensor.as_ref(),
295		);
296
297		// Compute the precommit segment's contribution to the wiring check.
298		// The prover sends this as a scalar; the oracle relation then verifies it.
299		let precommit_wiring_poly =
300			fold_constraints(alloc, &self.precommit_wiring_transpose, lambda, r_x_tensor.as_ref());
301		let precommit_claim = inner_product_buffers(&precommit_packed, &precommit_wiring_poly);
302		channel.send_one(precommit_claim);
303
304		let private_claim = batched_sum - public_eval - precommit_claim;
305
306		// Fold private wiring constraints
307		let private_wiring_poly =
308			fold_constraints(alloc, &self.private_wiring_transpose, lambda, r_x_tensor.as_ref());
309
310		// Compute the mask folding polynomial (libra_eval tensor)
311		let n_vars = r_x.len();
312		let libra_eval_tensor =
313			libra::expand_libra_eval::<A, P>(alloc, &r_x, n_vars, mask_degree, m_n, m_d);
314
315		// Prove all oracle relations.
316		channel.prove_oracle_relation(precommit_oracle, precommit_wiring_poly, precommit_claim);
317		channel.prove_oracle_relation(private_oracle, private_wiring_poly, private_claim);
318		channel.prove_oracle_relation(mask_oracle, libra_eval_tensor, mask_eval);
319
320		Ok(())
321	}
322}
323
324impl<F, P, H> Prover<P, H>
325where
326	F: BinaryField,
327	P: PackedField<Scalar = F>,
328	H: ParallelHashSuite,
329	Output<H::LeafHash>: SerializeBytes,
330{
331	/// Constructs a prover corresponding to a constraint system verifier.
332	///
333	/// See [`Prover`] struct documentation for details.
334	pub fn setup(verifier: &Verifier<F, H>) -> Result<Self, Error> {
335		let log_num_shares = binius_utils::rayon::current_num_threads().ilog2() as usize;
336
337		// Rebuild the verifier's evaluation domain, which its compiler fixed as the Gao-Mateer
338		// basis of that dimension.
339		let domain_context =
340			GaoMateerPreExpanded::generate(verifier.iop_compiler().max_log_domain_size());
341		let ntt = NeighborsLastMultiThread::new(domain_context, log_num_shares);
342
343		// Create the BaseFold ZK compiler from verifier compiler (reuses the oracle schedule and
344		// fri_params)
345		let basefold_compiler =
346			BaseFoldProverCompiler::from_verifier_compiler(verifier.iop_compiler(), ntt);
347
348		let iop_prover = IOPProver::new(verifier.constraint_system().clone());
349
350		Ok(Prover {
351			iop_prover,
352			basefold_compiler,
353			pool: BufferPool::new(),
354			_hash_marker: PhantomData,
355		})
356	}
357
358	/// Returns a reference to the IOP prover.
359	pub const fn iop_prover(&self) -> &IOPProver<P::Scalar> {
360		&self.iop_prover
361	}
362
363	/// Returns a reference to the BaseFold ZK prover compiler.
364	pub const fn iop_compiler(&self) -> &BaseFoldProverCompiler<P, ProverNTT<F>> {
365		&self.basefold_compiler
366	}
367
368	/// Generates a proof for a witness against the constraint system.
369	///
370	/// # Arguments
371	///
372	/// * `witness` - The witness values for the constraint system
373	/// * `rng` - Random number generator for blinding
374	/// * `transcript` - The prover transcript for Fiat-Shamir
375	///
376	/// # Preconditions
377	///
378	/// * The witness length must match the constraint system size
379	pub fn prove<Challenger_: Challenger>(
380		&self,
381		witness: &Witness<F>,
382		mut rng: impl CryptoRng,
383		transcript: &mut ProverTranscript<Challenger_>,
384	) -> Result<(), Error> {
385		// Prover observes the public input (includes it in Fiat-Shamir).
386		let public = witness.public();
387		transcript.observe().write_slice(public);
388
389		// Working buffers for this proof are drawn from the prover's pool, recycling blocks freed
390		// by earlier proofs. The channel gets the same pool, so the Merkle trees it commits draw
391		// their nodes from it too.
392		let alloc = &self.pool;
393		// Create ZK channel (owns the RNG for mask generation), commit the precommit oracle,
394		// and delegate to the IOP prover.
395		let mut channel = self
396			.basefold_compiler
397			.create_channel_from_transcript::<H, Challenger_, _, _>(transcript, &mut rng, alloc);
398		let (precommit_oracle, precommit_packed) =
399			self.iop_prover
400				.commit_precommit::<P, _, _>(witness, &mut rng, &mut channel, &alloc);
401		// The IOP prover only queues the oracle relations; `finish` runs the single combined
402		// opening.
403		self.iop_prover.prove::<P, _, _>(
404			witness,
405			precommit_oracle,
406			precommit_packed.as_view(),
407			rng,
408			&mut channel,
409			&alloc,
410		)?;
411		channel.finish();
412		Ok(())
413	}
414}
415
416fn prove_mulcheck<F, P, Channel, A>(
417	mul_constraints: &[MulConstraint<WitnessIndex>],
418	public: &[F],
419	precommit_packed: FieldSlice<'_, P>,
420	private_packed: FieldSlice<'_, P>,
421	mask: libra::Mask<P, impl Deref<Target = [P]>>,
422	channel: &mut Channel,
423	alloc: &A,
424) -> ([F; 3], F, Vec<F>)
425where
426	F: BinaryField,
427	P: PackedField<Scalar = F>,
428	Channel: IPProverChannel<F>,
429	A: Allocator,
430{
431	let mulcheck_witness = wiring::build_mulcheck_witness(
432		alloc,
433		mul_constraints,
434		public,
435		precommit_packed,
436		private_packed,
437	);
438
439	// Sample random evaluation point for mulcheck
440	let r_mulcheck = channel.sample_many(mask.n_vars());
441
442	// Prove the mul-gate zerocheck a * b - c = 0 over the shared store.
443	let mlecheck_prover = quadratic_mlecheck_prover(
444		alloc,
445		[mulcheck_witness.a, mulcheck_witness.b, mulcheck_witness.c],
446		|[a, b, c]| a * b - c, // composition
447		|[a, b, _c]| a * b,    // infinity_composition (quadratic term only)
448		r_mulcheck,
449		F::ZERO, // eval_claim: zerocheck
450	);
451
452	// Run the ZK MLE-check protocol
453	let mlecheck_output = zk_mlecheck::prove(mlecheck_prover, mask, channel);
454
455	// Extract the reduced evaluation point and multilinear evaluations
456	let mut r_x = mlecheck_output.challenges;
457	r_x.reverse(); // Match verifier's order
458
459	let [a_eval, b_eval, c_eval]: [F; 3] = mlecheck_output
460		.multilinear_evals
461		.try_into()
462		.expect("mlecheck returns 3 evaluations");
463
464	// Write the multilinear evaluations to channel
465	channel.send_many(&[a_eval, b_eval, c_eval]);
466
467	let mulcheck_evals = [a_eval, b_eval, c_eval];
468	let mask_eval = mlecheck_output.mask_eval;
469
470	(mulcheck_evals, mask_eval, r_x)
471}
472
473/// Packs witness values into a [`FieldBuffer`] and adds blinding values for dummy wires.
474fn pack_and_blind_witness<A: Allocator, F: Field, P: PackedField<Scalar = F>>(
475	alloc: &A,
476	log_private: usize,
477	private: &[F],
478	n_private: usize,
479	blinding_info: &BlindingInfo,
480	mut rng: impl CryptoRng,
481) -> FieldVec<P, A> {
482	// Growing a pooled buffer past the block it was handed would reallocate and free that block at
483	// the element's alignment rather than the pool's, so the fill below must fit exactly.
484	let packed_len = 1 << log_private.saturating_sub(P::LOG_WIDTH);
485	let mut packed = alloc.alloc::<P>(packed_len);
486	if log_private < P::LOG_WIDTH {
487		// The whole segment lives in one packed element's low lanes.
488		debug_assert_eq!(packed_len, 1);
489		let elems_iter = private.iter().copied();
490		let zeros_iter = repeat_n(F::ZERO, (1 << log_private) - private.len());
491
492		packed.push(P::from_scalars(chain!(elems_iter, zeros_iter)));
493	} else {
494		// Zero the block once, then overwrite the prefix holding real scalars. The zip stops at the
495		// last real chunk, so the zero tail is the padding the buffer wants anyway. Collecting into
496		// a `Vec` first and copying that in would cost a second allocation and a full memcpy — the
497		// very thing pooling is here to remove.
498		debug_assert!(private.len() <= 1 << log_private);
499		packed.resize(packed_len, P::zero());
500		private
501			.par_chunks(P::WIDTH)
502			.zip(packed.par_iter_mut())
503			.for_each(|(chunk, out)| *out = P::from_scalars(chunk.iter().copied()));
504	}
505
506	let mut buffer = FieldBuffer::new(log_private, packed);
507
508	// Set random values for dummy constraint wires (A * B = C) after the actual private wires
509	let constraint_wire_base = n_private;
510	for i in 0..blinding_info.n_dummy_constraints {
511		let a = F::random(&mut rng);
512		let b = F::random(&mut rng);
513		let c = a * b;
514
515		buffer.set(constraint_wire_base + 3 * i, a);
516		buffer.set(constraint_wire_base + 3 * i + 1, b);
517		buffer.set(constraint_wire_base + 3 * i + 2, c);
518	}
519
520	buffer
521}