1#![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#[derive(Debug)]
81pub struct IOPProver<F: Field> {
82 constraint_system: ConstraintSystemPadded<F>,
83 precommit_wiring_transpose: WiringTranspose,
84 private_wiring_transpose: WiringTranspose,
85}
86
87pub 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 pool: BufferPool,
102 _hash_marker: PhantomData<H>,
104}
105
106impl<F: Field> IOPProver<F> {
107 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 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 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 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 let (m_n, m_d) = cs.mask_dims();
237 let mask_degree = 2; let log_masks_buffer_size = m_n + m_d;
239
240 let masks_buffer = {
241 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 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 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 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 let lambda = channel.sample();
282
283 let batched_sum = evaluate_univariate(&mulcheck_evals, &lambda);
285
286 let r_x_tensor = eq_ind_partial_eval::<F>(&r_x);
288
289 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 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 let private_wiring_poly =
308 fold_constraints(alloc, &self.private_wiring_transpose, lambda, r_x_tensor.as_ref());
309
310 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 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 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 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 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 pub const fn iop_prover(&self) -> &IOPProver<P::Scalar> {
360 &self.iop_prover
361 }
362
363 pub const fn iop_compiler(&self) -> &BaseFoldProverCompiler<P, ProverNTT<F>> {
365 &self.basefold_compiler
366 }
367
368 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 let public = witness.public();
387 transcript.observe().write_slice(public);
388
389 let alloc = &self.pool;
393 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 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 let r_mulcheck = channel.sample_many(mask.n_vars());
441
442 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, |[a, b, _c]| a * b, r_mulcheck,
449 F::ZERO, );
451
452 let mlecheck_output = zk_mlecheck::prove(mlecheck_prover, mask, channel);
454
455 let mut r_x = mlecheck_output.challenges;
457 r_x.reverse(); 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 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
473fn 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 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 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 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 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}