1use std::{marker::PhantomData, mem::MaybeUninit};
5
6use binius_alloc::{Allocator, BufferPool, VecLike};
7use binius_core::{
8 constraint_system::{ConstraintSystem, InoutSegment, Operand, ValueVec},
9 word::Word,
10};
11use binius_field::{PackedField, Rijndael8b as B8};
12use binius_hash_prover::ParallelHashSuite;
13use binius_iop_prover::{basefold::compiler::BaseFoldProverCompiler, channel::IOPProverChannel};
14use binius_ip::sumcheck::SumcheckOutput;
15use binius_ip_prover::channel::WordIPProverChannel;
16use binius_math::{
17 BinarySubspace, FieldBuffer, FieldVec,
18 ntt::{NeighborsLastMultiThread, domain_context::GaoMateerPreExpanded},
19};
20use binius_transcript::{ProverTranscript, fiat_shamir::Challenger};
21use binius_utils::{
22 SerializeBytes,
23 checked_arithmetics::log2_ceil_usize,
24 rayon::{prelude::*, task_size::IndexedParallelIteratorExt},
25};
26use binius_verifier::{
27 IOPVerifier, Verifier,
28 config::{B128, LOG_WORDS_PER_ELEM},
29 protocols::bitand::AndCheckOutput,
30};
31use digest::Output;
32
33use super::error::Error;
34use crate::{
35 protocols::{
36 binmul, bitand, intmul,
37 rerand::OperandWitness,
38 shift::{self, KeyCollection, OperandClaims, ShiftOutput},
39 },
40 ring_switch,
41};
42
43type ProverNTT<F> = NeighborsLastMultiThread<GaoMateerPreExpanded<F>>;
45
46#[derive(Debug)]
52pub struct IOPProver {
53 constraint_system: ConstraintSystem,
54 n_witness_elems: usize,
55 key_collection: KeyCollection,
56}
57
58impl IOPProver {
59 pub fn new(iop_verifier: IOPVerifier, key_collection: KeyCollection) -> Self {
61 let n_witness_elems = iop_verifier.n_witness_elems();
62 let constraint_system = iop_verifier.into_constraint_system();
63 Self {
64 constraint_system,
65 n_witness_elems,
66 key_collection,
67 }
68 }
69
70 pub const fn constraint_system(&self) -> &ConstraintSystem {
72 &self.constraint_system
73 }
74
75 pub const fn key_collection(&self) -> &KeyCollection {
79 &self.key_collection
80 }
81
82 pub fn prove<A, P, Channel>(
87 &self,
88 witness: &ValueVec,
89 channel: &mut Channel,
90 alloc: &A,
91 ) -> Result<(), Error>
92 where
93 A: Allocator,
94 P: PackedField<Scalar = B128>,
95 Channel: IOPProverChannel<P, A> + WordIPProverChannel<B128, Word = Word>,
96 {
97 let cs = &self.constraint_system;
98
99 let setup_guard = tracing::debug_span!("Prepare witness").entered();
104 let witness_packed = pack_witness::<P, _>(
106 alloc,
107 log2_ceil_usize(self.n_witness_elems),
108 witness.non_public(),
109 )?;
110 drop(setup_guard);
111
112 channel.observe_words(witness.inout());
115
116 let witness_commit_guard = tracing::info_span!("Commit witness").entered();
118
119 let trace_oracle = channel.send_oracle(witness_packed.as_view());
121
122 drop(witness_commit_guard);
123
124 let intmul = if cs.n_imul_constraints() > 0 {
132 let intmul_guard = tracing::info_span!(
133 "[phase] IntMul check",
134 n_constraints = cs.imul_constraints.len()
135 )
136 .entered();
137 let mul_columns = tracing::debug_span!("Assemble columns")
138 .in_scope(|| build_operation_columns(&cs.imul_constraints, witness, alloc));
139
140 let [a, b, lo, hi] = &mul_columns;
141 let intmul_output = intmul::prove::<_, _, P, _>([a, b, lo, hi], &mut *channel, alloc)?;
142 drop(intmul_guard);
143 Some((mul_columns, intmul_output))
144 } else {
145 None
146 };
147
148 let binmul = if cs.n_bmul_constraints() > 0 {
155 let binmul_guard = tracing::info_span!(
156 "[phase] BinMul check",
157 n_constraints = cs.bmul_constraints.len()
158 )
159 .entered();
160 let binmul_columns = tracing::debug_span!("Assemble columns")
161 .in_scope(|| build_operation_columns(&cs.bmul_constraints, witness, alloc));
162
163 let [a_lo, a_hi, b_lo, b_hi, c_lo, c_hi] = &binmul_columns;
164 let binmul_output = binmul::prove::<_, _, P, _>(
165 [a_lo, a_hi, b_lo, b_hi, c_lo, c_hi],
166 &mut *channel,
167 alloc,
168 );
169 drop(binmul_guard);
170 Some((binmul_columns, binmul_output))
171 } else {
172 None
173 };
174
175 let operands = [
179 intmul.as_ref().map(|(columns, output)| OperandWitness {
180 words: columns.iter().map(|column| &**column).collect(),
181 claims: output.operand_claims(),
182 }),
183 binmul.as_ref().map(|(columns, output)| OperandWitness {
184 words: columns.iter().map(|column| &**column).collect(),
185 claims: output.operand_claims(),
186 }),
187 ]
188 .into_iter()
189 .flatten()
190 .collect::<Vec<_>>();
191 let bitand_guard =
192 tracing::info_span!("[phase] BitAnd check", n_constraints = cs.and_constraints.len())
193 .entered();
194 let AndCheckOutput {
195 z_challenge,
196 rerand,
197 } = {
198 let bitand_columns = tracing::debug_span!("Assemble columns")
200 .in_scope(|| build_operation_columns(&cs.and_constraints, witness, alloc));
201 bitand::prove::<_, B128, P, _, _>(bitand_columns, &operands, &mut *channel, alloc)
202 };
203 drop(bitand_guard);
204
205 let claims = OperandClaims::from_rerand(cs, 0, z_challenge, &rerand, || channel.sample());
211
212 let subspace = BinarySubspace::<B8>::with_dim(Word::LOG_BITS).isomorphic();
215
216 let shift_guard = tracing::info_span!(
218 "[phase] Shift Reduction",
219 phase = "shift_reduction",
220 perfetto_category = "phase"
221 )
222 .entered();
223 let ShiftOutput {
224 sumcheck: SumcheckOutput {
225 challenges: eval_point,
226 eval: _,
227 },
228 wiring_eval,
229 } = shift::prove::<_, P, _, _>(
230 &self.key_collection,
231 witness.public(),
232 witness.non_public(),
233 claims,
234 &subspace,
235 &mut *channel,
236 alloc,
237 );
238 drop(shift_guard);
239
240 let witness_point = &eval_point[..eval_point.len() - 1];
244 let (r_j, r_y) = witness_point.split_at(Word::LOG_BITS);
245
246 ring_switch::prove_public_eval::<_, P, _>(alloc, witness.public(), r_j, r_y, &mut *channel);
249
250 channel.send_public_claim(wiring_eval);
253
254 let pcs_guard = tracing::info_span!(
256 "[phase] PCS Opening",
257 phase = "pcs_opening",
258 perfetto_category = "phase"
259 )
260 .entered();
261
262 let ring_switch::RingSwitchOutput {
265 rs_eq_ind,
266 sumcheck_claim,
267 } = ring_switch::prove(
268 alloc,
269 witness_packed.as_view(),
270 self.n_witness_elems,
271 witness_point,
272 &mut *channel,
273 );
274
275 channel.prove_oracle_relation(trace_oracle, rs_eq_ind, sumcheck_claim);
278
279 drop(pcs_guard);
280
281 Ok(())
282 }
283}
284
285#[cfg(target_arch = "x86_64")]
292fn warn_on_software_field_arithmetic() {
293 use std::{arch::is_x86_feature_detected, sync::Once};
294
295 static ONCE: Once = Once::new();
296 ONCE.call_once(|| {
297 if !cfg!(target_feature = "pclmulqdq") && is_x86_feature_detected!("pclmulqdq") {
298 tracing::warn!(
299 "this CPU supports carryless multiply (PCLMULQDQ), but the build does not \
300 enable it, so field arithmetic will run in software; rebuild with \
301 `-C target-cpu=native` or `-C target-feature=+pclmulqdq`"
302 );
303 }
304 });
305}
306
307#[cfg(not(target_arch = "x86_64"))]
308const fn warn_on_software_field_arithmetic() {}
309
310pub struct Prover<P, H>
316where
317 P: PackedField<Scalar = B128>,
318 H: ParallelHashSuite,
319{
320 iop_prover: IOPProver,
322 iop_compiler: BaseFoldProverCompiler<P, ProverNTT<B128>>,
324 pool: BufferPool,
327 _hash_marker: PhantomData<H>,
329}
330
331impl<P, H> Prover<P, H>
332where
333 P: PackedField<Scalar = B128>,
334 H: ParallelHashSuite,
335 Output<H::LeafHash>: SerializeBytes,
336{
337 pub fn setup(verifier: Verifier<H>) -> Result<Self, Error> {
341 let key_collection =
342 KeyCollection::build(verifier.constraint_system(), InoutSegment::Public);
343 Self::setup_with_key_collection(verifier, key_collection)
344 }
345
346 pub fn setup_with_key_collection(
351 verifier: Verifier<H>,
352 key_collection: KeyCollection,
353 ) -> Result<Self, Error> {
354 warn_on_software_field_arithmetic();
355
356 let domain_context =
359 GaoMateerPreExpanded::generate(verifier.iop_compiler().max_log_domain_size());
360 let log_num_shares = binius_utils::rayon::current_num_threads().ilog2() as usize;
364 let ntt = NeighborsLastMultiThread::new(domain_context, log_num_shares);
365
366 let iop_compiler =
368 BaseFoldProverCompiler::from_verifier_compiler(verifier.iop_compiler(), ntt);
369
370 let iop_prover = IOPProver::new(verifier.into_iop_verifier(), key_collection);
371
372 Ok(Prover {
373 iop_prover,
374 iop_compiler,
375 pool: BufferPool::new(),
376 _hash_marker: PhantomData,
377 })
378 }
379
380 pub const fn iop_prover(&self) -> &IOPProver {
382 &self.iop_prover
383 }
384
385 pub const fn key_collection(&self) -> &KeyCollection {
389 self.iop_prover.key_collection()
390 }
391
392 pub fn prove<Challenger_: Challenger + Clone>(
393 &self,
394 witness: &ValueVec,
395 transcript: &mut ProverTranscript<Challenger_>,
396 ) -> Result<(), Error> {
397 let cs = self.iop_prover.constraint_system();
398
399 let _prove_guard = tracing::info_span!(
400 "Prove",
401 n_hidden_words = cs.n_hidden_words(InoutSegment::Public),
402 n_bitand = cs.and_constraints.len(),
403 n_intmul = cs.imul_constraints.len(),
404 )
405 .entered();
406
407 let alloc = &self.pool;
411
412 let mut channel = self
416 .iop_compiler
417 .create_channel_without_zk_from_transcript::<H, Challenger_, _, _>(transcript, alloc);
418 self.iop_prover
419 .prove::<_, P, _>(witness, &mut channel, &alloc)?;
420 channel.finish();
421 Ok(())
422 }
423}
424
425pub fn pack_witness<P: PackedField<Scalar = B128>, A: Allocator>(
444 alloc: &A,
445 log_witness_elems: usize,
446 witness: &[Word],
447) -> Result<FieldVec<P, A>, Error> {
448 let n_witness_elems = witness.len().div_ceil(1 << LOG_WORDS_PER_ELEM);
450 if n_witness_elems > 1 << log_witness_elems {
451 return Err(Error::ArgumentError {
452 arg: "witness".to_string(),
453 msg: "witness element count is incompatible with the constraint system".to_string(),
454 });
455 }
456
457 let len = 1 << log_witness_elems.saturating_sub(P::LOG_WIDTH);
458 let mut padded_witness_elems = alloc.alloc::<P>(len);
459
460 let (pairs, word_remaining) = witness.as_chunks::<2>();
463 let aligned_len = pairs.len() / P::WIDTH * P::WIDTH;
464 let (pairs_aligned, word_pair_remaining) = pairs.split_at(aligned_len);
465 let n_aligned_elems = aligned_len / P::WIDTH;
469 (
470 pairs_aligned.par_chunks(P::WIDTH),
471 padded_witness_elems.spare_capacity_mut()[..n_aligned_elems].par_iter_mut(),
472 )
473 .into_par_iter()
474 .with_min_task_bytes::<P>()
475 .for_each(|(word_pairs, out)| {
476 out.write(P::from_scalars(
477 word_pairs
478 .iter()
479 .map(|[w0, w1]| B128::new(((w1.0 as u128) << 64) | (w0.0 as u128))),
480 ));
481 });
482 unsafe { padded_witness_elems.set_len(n_aligned_elems) };
488
489 if !word_pair_remaining.is_empty() || !word_remaining.is_empty() {
494 let word_pairs = word_pair_remaining
495 .iter()
496 .copied()
497 .chain(word_remaining.iter().map(|&word| [word, Word::ZERO]));
498 padded_witness_elems.push(P::from_scalars(
499 word_pairs.map(|[w0, w1]| B128::new(((w1.0 as u128) << 64) | (w0.0 as u128))),
500 ));
501 }
502
503 padded_witness_elems.resize(len, P::default());
504
505 Ok(FieldBuffer::new(log_witness_elems, padded_witness_elems))
506}
507
508fn build_operation_columns<C, A, const ARITY: usize, const N_COLS: usize>(
528 constraints: &[C],
529 witness: &ValueVec,
530 alloc: &A,
531) -> [A::Vec<Word>; N_COLS]
532where
533 C: AsRef<[Operand; ARITY]> + Sync,
534 A: Allocator,
535{
536 const {
537 assert!(N_COLS <= ARITY, "N_COLS must not exceed the constraint arity");
538 }
539
540 let n_constraints = constraints.len();
541 let n_rows = n_constraints.max(1);
543 (0..N_COLS)
544 .into_par_iter()
545 .map(|op_idx| {
546 let mut column = alloc.alloc::<Word>(n_rows);
547 let rows = &mut column.spare_capacity_mut()[..n_rows];
550 if n_constraints == 0 {
552 rows.fill(MaybeUninit::new(Word::ZERO));
553 }
554 (constraints, &mut *rows)
555 .into_par_iter()
556 .for_each(|(constraint, out)| {
557 out.write(witness.eval_operand(&constraint.as_ref()[op_idx]));
558 });
559 unsafe { column.set_len(n_rows) };
563 column
564 })
565 .collect::<Vec<_>>()
566 .try_into()
567 .unwrap_or_else(|_| unreachable!("source iterator has N_COLS elements"))
568}
569
570#[cfg(test)]
571mod tests {
572 use binius_alloc::GlobalAllocator;
573 use binius_core::constraint_system::{AndConstraint, ConstraintSystem};
574 use binius_field::{Field, PackedGhash2x128b};
575 use binius_frontend::CircuitBuilder;
576
577 use super::{B128, ValueVec, Word, build_operation_columns, pack_witness};
578
579 fn and_gate_system(n_gates: usize) -> (ConstraintSystem, ValueVec) {
584 let builder = CircuitBuilder::new();
585 let wires: Vec<_> = (0..n_gates)
586 .map(|_| {
587 let x = builder.add_witness();
588 let y = builder.add_witness();
589 builder.force_commit(builder.band(x, y));
590 (x, y)
591 })
592 .collect();
593 let circuit = builder.build();
594
595 let mut w = circuit.new_witness_filler();
596 for (i, &(x, y)) in wires.iter().enumerate() {
597 w[x] = Word(0x0123_4567_89AB_CDEF | (i as u64) << 32 | 1);
599 w[y] = Word(0xFEDC_BA98_7654_3210 | (i as u64) | 1);
600 }
601 circuit.populate_wire_witness(&mut w).unwrap();
602
603 let cs = circuit.constraint_system().clone();
604 cs.validate().unwrap();
605 (cs, w.into_value_vec())
606 }
607
608 fn and_gate_witness(n_gates: usize) -> (Vec<AndConstraint>, ValueVec) {
612 let (cs, witness) = and_gate_system(n_gates);
613 assert_eq!(cs.n_and_constraints(), n_gates);
614 (cs.and_constraints, witness)
615 }
616
617 #[test]
621 fn build_operation_columns_stops_at_the_last_constraint() {
622 let (constraints, witness) = and_gate_witness(3);
623 let columns = build_operation_columns::<AndConstraint, _, 3, 2>(
624 &constraints,
625 &witness,
626 &GlobalAllocator,
627 );
628
629 for column in &columns {
632 assert_eq!(column.len(), 3);
633 assert!(column.iter().all(|&word| word != Word::ZERO));
634 }
635 }
636
637 #[test]
641 fn build_operation_columns_gives_an_empty_set_one_zero_row() {
642 let (_, witness) = and_gate_witness(1);
643 let columns =
644 build_operation_columns::<AndConstraint, _, 3, 2>(&[], &witness, &GlobalAllocator);
645
646 for column in &columns {
647 assert_eq!(column.len(), 1);
648 assert_eq!(column[0], Word::ZERO);
649 }
650 }
651
652 fn expected_scalars(words: &[Word], n_elems: usize) -> Vec<B128> {
656 let mut scalars = vec![B128::ZERO; n_elems];
657 for (elem, pair) in scalars.iter_mut().zip(words.chunks(2)) {
658 let lo = pair[0].0 as u128;
659 let hi = pair.get(1).map_or(0, |w| w.0 as u128);
660 *elem = B128::new((hi << 64) | lo);
661 }
662 scalars
663 }
664
665 #[test]
670 fn test_pack_witness_unaligned_pair_count_with_remainder() {
671 type P = PackedGhash2x128b;
672 assert_eq!(P::WIDTH, 2, "this test is meaningful only when the packing width is 2");
673
674 let words: Vec<Word> = (1..=7u64).map(Word).collect();
675 let log_witness_elems = 3; let packed = pack_witness::<P, _>(&GlobalAllocator, log_witness_elems, &words).unwrap();
678 let got: Vec<B128> = packed.iter_scalars().collect();
679
680 assert_eq!(got, expected_scalars(&words, 1 << log_witness_elems));
681 }
682
683 #[test]
686 fn test_pack_witness_various_lengths() {
687 type P = PackedGhash2x128b;
688
689 for n_words in [1usize, 2, 3, 4, 5, 6, 7, 8, 9, 13, 17] {
690 let words: Vec<Word> = (0..n_words as u64).map(|i| Word(i + 100)).collect();
691 let n_elems = n_words.div_ceil(2);
692 let log_witness_elems = n_elems.max(P::WIDTH).next_power_of_two().ilog2() as usize;
694
695 let packed = pack_witness::<P, _>(&GlobalAllocator, log_witness_elems, &words).unwrap();
696 let got: Vec<B128> = packed.iter_scalars().collect();
697
698 assert_eq!(
699 got,
700 expected_scalars(&words, 1 << log_witness_elems),
701 "n_words = {n_words}"
702 );
703 }
704 }
705}