1use std::{iter, ops::Deref};
5
6use binius_alloc::Allocator;
7use binius_core::word::Word;
8use binius_field::{BinaryField, Field, PackedField, WideMul};
9use binius_ip::sumcheck::RoundCoeffs;
10use binius_ip_prover::{
11 channel::IPProverChannel,
12 sumcheck::{
13 ProveSingleOutput, bivariate_product_evaluator::BivariateProductEvaluator,
14 bivariate_product_prover, common::SumcheckProver, prove_single, round_evals::RoundEvals,
15 round_evaluator::SharedSumcheckProver,
16 },
17};
18use binius_math::{FieldBuffer, FieldVec, multilinear::fold::fold_highest_var_inplace};
19use binius_verifier::protocols::shift::LOG_SHIFT_COUNT;
20use tracing::instrument;
21
22use super::{
23 SegmentWords,
24 claims::PreparedOperandClaims,
25 key_collection::{DenseShiftEncoding, KeyCollection},
26 monster::shift_operator_table,
27 outer::OuterShiftStage,
28 shift_ind::ShiftChallenge,
29};
30
31#[instrument(skip_all, name = "prover_phase_1")]
50pub fn prove_phase_1<F, P, Channel, A>(
51 key_collection: &KeyCollection,
52 words: SegmentWords<'_>,
53 prepared: &PreparedOperandClaims<F>,
54 oblong_weights: &[F],
55 channel: &mut Channel,
56 alloc: &A,
57) -> Phase1Output<F>
58where
59 F: BinaryField,
60 P: PackedField<Scalar = F>,
61 Channel: IPProverChannel<F>,
62 A: Allocator,
63{
64 let public = key_collection
68 .public
69 .build_g::<_, P>(words.public, prepared);
70 let hidden = key_collection
71 .hidden
72 .build_g::<_, P>(words.hidden, prepared);
73 let g = SparseShiftRows::from_segments([
74 (&public, &key_collection.public.dense_shift_enc),
75 (&hidden, &key_collection.hidden.dense_shift_enc),
76 ]);
77
78 g.run_phase_1_sumcheck(oblong_weights, prepared.batched_eval, channel, alloc)
79}
80
81pub const PHASE_1_LOG_LEN: usize = Word::LOG_BITS + LOG_SHIFT_ROWS;
87
88pub const LOG_SHIFT_ROWS: usize = 2 * LOG_SHIFT_COUNT;
94
95pub const SHIFT_OPERATOR_LOG_LEN: usize = Word::LOG_BITS + LOG_SHIFT_COUNT;
98
99#[derive(Debug, Clone)]
104pub struct Phase1Output<F> {
105 pub r_j: Vec<F>,
107 pub inner: ShiftChallenge<F>,
109 pub outer: ShiftChallenge<F>,
111 pub psi: Vec<F>,
115 pub gamma: F,
117 pub g_eval: F,
121}
122
123pub(super) const fn row_len<P: PackedField>() -> usize {
125 assert!(
126 P::LOG_WIDTH <= Word::LOG_BITS,
127 "a row of `Word::BITS` scalars must be a whole number of packed elements"
128 );
129 Word::BITS >> P::LOG_WIDTH
130}
131
132#[derive(Debug, Clone)]
142pub struct SparseShiftRows<P: PackedField> {
143 indices: Vec<u32>,
147 values: Vec<P>,
149 log_rows: usize,
151}
152
153impl<P: PackedField> SparseShiftRows<P> {
154 pub fn from_segments(segments: [(&[P], &DenseShiftEncoding); 2]) -> Self {
165 let mut indices = Vec::new();
166 let mut values = Vec::new();
167
168 for (rows, dense_shift_enc) in segments {
170 assert_eq!(
171 rows.len(),
172 dense_shift_enc.len() * row_len::<P>(),
173 "a segment holds one row per shift its encoding names"
174 );
175 indices.extend(dense_shift_enc.shift_indices().map(|index| index as u32));
177 values.extend_from_slice(rows);
179 }
180
181 Self::new(indices, values, LOG_SHIFT_ROWS)
182 }
183
184 pub fn new(indices: Vec<u32>, values: Vec<P>, log_rows: usize) -> Self {
194 assert_eq!(
195 values.len(),
196 indices.len() * row_len::<P>(),
197 "the values hold one row per index"
198 );
199 assert!(
200 indices
201 .iter()
202 .all(|&index| (index as usize) < 1 << log_rows),
203 "every index names a row of the space"
204 );
205
206 Self {
207 indices,
208 values,
209 log_rows,
210 }
211 }
212
213 pub(crate) const fn log_rows(&self) -> usize {
215 self.log_rows
216 }
217
218 #[allow(clippy::chunks_exact_to_as_chunks)] pub(crate) fn rows(&self) -> impl Iterator<Item = (usize, &[P])> {
221 iter::zip(&self.indices, self.values.chunks_exact(row_len::<P>()))
222 .map(|(&index, row)| (index as usize, row))
223 }
224
225 pub(crate) fn half(&self) -> usize {
231 assert!(self.log_rows > 0, "precondition: a row-index variable remains to bind");
232 1 << (self.log_rows - 1)
233 }
234
235 pub(crate) fn fold(&mut self, challenge: P::Scalar) {
245 let half = self.half();
246 let lower_weight = P::broadcast(P::Scalar::ONE - challenge);
247 let upper_weight = P::broadcast(challenge);
248
249 let row_len = row_len::<P>();
250 for (position, index) in self.indices.iter_mut().enumerate() {
253 let row = &mut self.values[position * row_len..][..row_len];
254 if *index as usize & half == 0 {
255 row.iter_mut().for_each(|value| *value *= lower_weight);
257 } else {
258 row.iter_mut().for_each(|value| *value *= upper_weight);
260 *index ^= half as u32;
261 }
262 }
263
264 self.log_rows -= 1;
265 }
266
267 fn into_bit_multilinear<A: Allocator>(self, alloc: &A) -> FieldVec<P, A> {
274 assert_eq!(self.log_rows, 0, "precondition: every row-index variable is bound");
275
276 let mut multilinear = FieldBuffer::zeros_in(alloc, Word::LOG_BITS);
277 for (_, row) in self.rows() {
279 for (slot, &value) in iter::zip(multilinear.as_mut(), row) {
280 *slot += value;
281 }
282 }
283 multilinear
284 }
285
286 fn round_coeffs<F, Data>(&self, h: &FieldBuffer<P, Data>, claim: F) -> RoundCoeffs<F>
297 where
298 F: Field,
299 P: PackedField<Scalar = F>,
300 Data: Deref<Target = [P]>,
301 {
302 let half = self.half();
303 let row_len = row_len::<P>();
304 let h_rows = h.as_ref();
305
306 let mut y_1 = <P as WideMul>::Output::default();
309 let mut y_inf = <P as WideMul>::Output::default();
310 for (index, row) in self.rows() {
311 let own = &h_rows[index * row_len..][..row_len];
312 let facing = &h_rows[(index ^ half) * row_len..][..row_len];
313
314 for i in 0..row_len {
315 if index & half != 0 {
318 y_1 += P::wide_mul(row[i], own[i]);
319 }
320 y_inf += P::wide_mul(row[i], own[i] + facing[i]);
321 }
322 }
323
324 let sum_lanes = |wide| P::reduce(wide).iter().sum::<F>();
327 RoundEvals([sum_lanes(y_1), sum_lanes(y_inf)]).interpolate(claim)
328 }
329
330 #[instrument(skip_all, name = "run_sumcheck")]
359 pub fn run_phase_1_sumcheck<F, Channel, A>(
360 mut self,
361 oblong_weights: &[F],
362 sum: F,
363 channel: &mut Channel,
364 alloc: &A,
365 ) -> Phase1Output<F>
366 where
367 F: BinaryField,
368 P: PackedField<Scalar = F>,
369 Channel: IPProverChannel<F>,
370 A: Allocator,
371 {
372 assert_eq!(self.log_rows(), LOG_SHIFT_ROWS, "the row list spans both shift slots");
373
374 let mut outer = OuterShiftStage::new(alloc, oblong_weights);
379 let mut claim = sum;
380 let mut outer_point = Vec::with_capacity(LOG_SHIFT_COUNT);
381 for _ in 0..LOG_SHIFT_COUNT {
382 let round_coeffs = outer.round_coeffs(&self, claim);
383 channel.send_many(round_coeffs.clone().truncate().coeffs());
384 let challenge = channel.sample();
385 claim = round_coeffs.evaluate(&challenge);
386 outer.fold(challenge);
387 self.fold(challenge);
388 outer_point.push(challenge);
389 }
390 let psi = outer.psi().to_vec();
392
393 let h = shift_operator_table(alloc, &psi);
398
399 let g = self;
401 let ProveSingleOutput {
402 multilinear_evals,
403 mut challenges,
404 } = prove_single(Phase1SumcheckProver::new(g, h, claim, alloc), channel);
405
406 challenges.reverse();
410 assert_eq!(challenges.len(), SHIFT_OPERATOR_LOG_LEN);
411 let mut r_j = challenges;
412 let r_v_inner = r_j.split_off(Word::LOG_BITS * 2);
413 let r_s_inner = r_j.split_off(Word::LOG_BITS);
414
415 outer_point.reverse();
416 let mut r_s_outer = outer_point;
417 let r_v_outer = r_s_outer.split_off(Word::LOG_BITS);
418
419 let [g_eval, h_eval] = multilinear_evals
420 .try_into()
421 .expect("prover has 2 multilinear polynomials");
422
423 Phase1Output {
424 r_j,
425 inner: ShiftChallenge::new(r_s_inner, r_v_inner),
426 outer: ShiftChallenge::new(r_s_outer, r_v_outer),
427 psi,
428 gamma: g_eval * h_eval,
429 g_eval,
430 }
431 }
432}
433
434pub struct Phase1SumcheckProver<'alloc, A: Allocator, P: PackedField> {
454 alloc: &'alloc A,
455 stage: Option<Stage<'alloc, A, P>>,
460}
461
462enum Stage<'alloc, A: Allocator, P: PackedField> {
464 Rows {
466 g: SparseShiftRows<P>,
467 h: FieldVec<P, A>,
468 claim: P::Scalar,
470 coeffs: Option<RoundCoeffs<P::Scalar>>,
475 },
476 Bits(SharedSumcheckProver<'alloc, A, P, BivariateProductEvaluator>),
478}
479
480impl<'alloc, A: Allocator, F: Field, P: PackedField<Scalar = F>>
481 Phase1SumcheckProver<'alloc, A, P>
482{
483 pub fn new(g: SparseShiftRows<P>, h: FieldVec<P, A>, sum: F, alloc: &'alloc A) -> Self {
494 assert_eq!(h.log_len(), SHIFT_OPERATOR_LOG_LEN, "h spans one shift slot");
495 assert_eq!(g.log_rows(), LOG_SHIFT_COUNT, "g's rows span one shift slot");
496
497 Self {
498 alloc,
499 stage: Some(Stage::Rows {
500 g,
501 h,
502 claim: sum,
503 coeffs: None,
504 }),
505 }
506 }
507}
508
509impl<A: Allocator, F: Field, P: PackedField<Scalar = F>> SumcheckProver<F>
510 for Phase1SumcheckProver<'_, A, P>
511{
512 fn n_vars(&self) -> usize {
513 match self.stage.as_ref().expect("the stage is set between calls") {
514 Stage::Rows { h, .. } => h.log_len(),
517 Stage::Bits(prover) => prover.n_vars(),
518 }
519 }
520
521 fn execute(&mut self) -> Vec<RoundCoeffs<F>> {
522 match self.stage.as_mut().expect("the stage is set between calls") {
523 Stage::Rows {
524 g,
525 h,
526 claim,
527 coeffs,
528 } => {
529 let round_coeffs = g.round_coeffs(h, *claim);
532 *coeffs = Some(round_coeffs.clone());
533 vec![round_coeffs]
534 }
535 Stage::Bits(prover) => prover.execute(),
537 }
538 }
539
540 fn fold(&mut self, challenge: F) {
541 let stage = self.stage.take().expect("the stage is set between calls");
543 self.stage = Some(match stage {
544 Stage::Rows {
545 mut g,
546 mut h,
547 coeffs,
548 ..
549 } => {
550 let claim = coeffs
551 .expect("execute is called before fold")
552 .evaluate(&challenge);
553 g.fold(challenge);
557 fold_highest_var_inplace(&mut h, challenge);
558
559 if g.log_rows() > 0 {
560 Stage::Rows {
562 g,
563 h,
564 claim,
565 coeffs: None,
566 }
567 } else {
568 Stage::Bits(bivariate_product_prover(
572 self.alloc,
573 [g.into_bit_multilinear(self.alloc), h],
574 claim,
575 ))
576 }
577 }
578 Stage::Bits(mut prover) => {
579 prover.fold(challenge);
581 Stage::Bits(prover)
582 }
583 });
584 }
585
586 fn finish(self) -> Vec<F> {
587 match self.stage.expect("the stage is set between calls") {
588 Stage::Rows { .. } => panic!("finish called before the row index was bound"),
589 Stage::Bits(prover) => prover.finish(),
591 }
592 }
593}
594
595#[cfg(test)]
596mod tests {
597 use binius_alloc::GlobalAllocator;
598 use binius_core::constraint_system::{
599 AndConstraint, ConstraintSystem, InoutSegment, Shift, ShiftedValueIndex, ValueIndex,
600 };
601 use binius_field::{Field, Ghash128b, PackedGhash2x128b};
602 use binius_math::{inner_product::inner_product_buffers, test_utils::random_scalars};
603 use binius_transcript::ProverTranscript;
604 use binius_verifier::config::StdChallenger;
605 use rand::{SeedableRng, rngs::StdRng};
606
607 use super::*;
608 use crate::protocols::shift::KeyCollection;
609
610 type F = Ghash128b;
611
612 impl<P: PackedField> SparseShiftRows<P> {
613 fn scatter<A: Allocator>(&self, alloc: &A) -> FieldVec<P, A> {
622 let row_len = row_len::<P>();
623 let mut g = FieldBuffer::zeros_in(alloc, self.log_rows + Word::LOG_BITS);
624 for (index, row) in self.rows() {
625 let slots = &mut g.as_mut()[index * row_len..][..row_len];
627 for (slot, &value) in iter::zip(slots, row) {
628 *slot += value;
629 }
630 }
631 g
632 }
633 }
634
635 fn overlapping_shift_system() -> ConstraintSystem {
640 let public = ValueIndex::constant(1);
641 let hidden = ValueIndex::private(1);
642 ConstraintSystem {
643 constants: vec![Word::ZERO; 4],
644 n_inout: 0,
645 n_private: 4,
646 zero_constraints: Vec::new(),
647 and_constraints: vec![AndConstraint([
648 vec![
649 ShiftedValueIndex::plain(public),
650 ShiftedValueIndex::srl(public, 3),
651 ],
652 vec![ShiftedValueIndex::sar(hidden, 7)],
653 vec![
654 ShiftedValueIndex::rotr(hidden, 1),
655 ShiftedValueIndex::plain(hidden),
656 ],
657 ])],
658 imul_constraints: Vec::new(),
659 bmul_constraints: Vec::new(),
660 }
661 }
662
663 #[test]
668 fn from_segments_concatenates_the_two_encodings() {
669 let key_collection =
670 KeyCollection::build(&overlapping_shift_system(), InoutSegment::Public);
671
672 let segment_rows = |enc: &DenseShiftEncoding, base: u128| {
675 (0..enc.len() * Word::BITS)
676 .map(|i| F::new(base + (i / Word::BITS) as u128))
677 .collect::<Vec<F>>()
678 };
679 let public = segment_rows(&key_collection.public.dense_shift_enc, 0x100);
680 let hidden = segment_rows(&key_collection.hidden.dense_shift_enc, 0x200);
681
682 let g = SparseShiftRows::from_segments([
683 (&public, &key_collection.public.dense_shift_enc),
684 (&hidden, &key_collection.hidden.dense_shift_enc),
685 ]);
686
687 let row_index = |shift: Shift| shift.index() as u32;
691 assert_eq!(
692 g.indices,
693 [
694 row_index(Shift::IDENTITY),
695 row_index(Shift::srl(3)),
696 row_index(Shift::IDENTITY),
697 row_index(Shift::sar(7)),
698 row_index(Shift::rotr(1)),
699 ]
700 );
701
702 let row = |position: usize| &g.values[position * Word::BITS..][..Word::BITS];
704 for (position, expected) in [0x100, 0x101, 0x200, 0x201, 0x202].into_iter().enumerate() {
705 assert!(row(position).iter().all(|&value| value == F::new(expected)));
706 }
707
708 let at = |shift: Shift| {
710 g.rows()
711 .filter(|&(index, _)| index == shift.index())
712 .map(|(_, row)| row[0])
713 .sum::<F>()
714 };
715 assert_eq!(at(Shift::IDENTITY), F::new(0x100) + F::new(0x200));
716 assert_eq!(at(Shift::srl(3)), F::new(0x101));
717 assert_eq!(at(Shift::sar(7)), F::new(0x201));
718 assert_eq!(at(Shift::rotr(1)), F::new(0x202));
719 }
720
721 #[test]
723 fn a_sequence_is_keyed_outer_major() {
724 let hidden = ValueIndex::private(1);
725 let sequence = [Shift::srl(3), Shift::sll(5)];
726 let cs = ConstraintSystem {
727 constants: vec![Word::ZERO; 4],
728 n_inout: 0,
729 n_private: 4,
730 zero_constraints: Vec::new(),
731 and_constraints: vec![AndConstraint([
732 vec![ShiftedValueIndex::new(hidden, sequence)],
733 Vec::new(),
734 Vec::new(),
735 ])],
736 imul_constraints: Vec::new(),
737 bmul_constraints: Vec::new(),
738 };
739
740 let key_collection = KeyCollection::build(&cs, InoutSegment::Public);
741 let [inner, outer] = sequence;
742 assert_eq!(
743 key_collection
744 .hidden
745 .dense_shift_enc
746 .shift_indices()
747 .collect::<Vec<_>>(),
748 [outer.index() << LOG_SHIFT_COUNT | inner.index()]
749 );
750 }
751
752 #[test]
757 fn scatter_places_rows_at_their_shift_index() {
758 let indices = [Shift::IDENTITY, Shift::sar(7), Shift::rotr(1)]
759 .map(|shift| shift.index() as u32)
760 .to_vec();
761 let values = (0..indices.len() * Word::BITS)
762 .map(|i| F::new(1 + (i / Word::BITS) as u128))
763 .collect::<Vec<F>>();
764 let rows = SparseShiftRows::<F>::new(indices.clone(), values, LOG_SHIFT_COUNT);
765
766 let g = rows.scatter(&GlobalAllocator);
767 assert_eq!(g.log_len(), SHIFT_OPERATOR_LOG_LEN);
768
769 for (row, &shift_index) in indices.iter().enumerate() {
771 let offset = shift_index as usize * Word::BITS;
772 for bit in 0..Word::BITS {
773 assert_eq!(g.get(offset + bit), F::new(1 + row as u128));
774 }
775 }
776 for row in (0..1 << LOG_SHIFT_COUNT).filter(|row| !indices.contains(&(*row as u32))) {
777 assert!((0..Word::BITS).all(|bit| g.get(row * Word::BITS + bit) == F::ZERO));
778 }
779 }
780
781 fn run_dense_reference<P: PackedField<Scalar = F>>(
787 g: &SparseShiftRows<P>,
788 h: FieldVec<P, GlobalAllocator>,
789 sum: F,
790 channel: &mut ProverTranscript<StdChallenger>,
791 ) -> (Vec<F>, F) {
792 let prover =
793 bivariate_product_prover(&GlobalAllocator, [g.scatter(&GlobalAllocator), h], sum);
794
795 let ProveSingleOutput {
796 multilinear_evals,
797 mut challenges,
798 } = prove_single(prover, channel);
799 challenges.reverse();
800
801 let [g_eval, h_eval] = multilinear_evals
802 .try_into()
803 .expect("prover has 2 multilinear polynomials");
804
805 (challenges, g_eval * h_eval)
806 }
807
808 fn phase_1_multilinears<P: PackedField<Scalar = F>>(
815 cs: &ConstraintSystem,
816 seed: u64,
817 ) -> (SparseShiftRows<P>, FieldVec<P, GlobalAllocator>) {
818 let mut rng = StdRng::seed_from_u64(seed);
819 let key_collection = KeyCollection::build(cs, InoutSegment::Public);
820
821 let mut indices = Vec::new();
822 let mut values = Vec::new();
823 for segment in [&key_collection.public, &key_collection.hidden] {
824 for [inner, _] in segment.dense_shift_enc.iter() {
825 indices.push(inner.index() as u32);
826 values.extend((0..row_len::<P>()).map(|_| P::random(&mut rng)));
827 }
828 }
829 let g = SparseShiftRows::new(indices, values, LOG_SHIFT_COUNT);
830
831 let h = shift_operator_table(&GlobalAllocator, &random_scalars::<F>(&mut rng, Word::BITS));
833
834 (g, h)
835 }
836
837 fn assert_sparse_matches_dense<P: PackedField<Scalar = F>>(cs: &ConstraintSystem, seed: u64) {
843 let (g, h) = phase_1_multilinears::<P>(cs, seed);
844 let sum = inner_product_buffers(&g.scatter(&GlobalAllocator), &h);
846
847 let mut sparse_transcript = ProverTranscript::<StdChallenger>::default();
848 let ProveSingleOutput {
849 multilinear_evals,
850 challenges: mut sparse_challenges,
851 } = prove_single(
852 Phase1SumcheckProver::new(g.clone(), h.clone(), sum, &GlobalAllocator),
853 &mut sparse_transcript,
854 );
855 sparse_challenges.reverse();
856 let [g_eval, h_eval] = multilinear_evals
857 .try_into()
858 .expect("prover has 2 multilinear polynomials");
859
860 let mut dense_transcript = ProverTranscript::<StdChallenger>::default();
861 let (dense_challenges, dense_eval) = run_dense_reference(&g, h, sum, &mut dense_transcript);
862
863 assert_eq!(sparse_challenges, dense_challenges);
864 assert_eq!(g_eval * h_eval, dense_eval);
865 assert_eq!(sparse_transcript.finalize(), dense_transcript.finalize());
866 }
867
868 #[test]
869 fn sparse_rounds_match_the_dense_prover() {
870 assert_sparse_matches_dense::<F>(&overlapping_shift_system(), 0);
873 assert_sparse_matches_dense::<PackedGhash2x128b>(&overlapping_shift_system(), 1);
874 }
875
876 #[test]
881 fn sparse_rounds_match_the_dense_prover_with_an_empty_g() {
882 let cs = ConstraintSystem {
883 constants: vec![Word::ZERO; 4],
884 n_inout: 0,
885 n_private: 4,
886 zero_constraints: Vec::new(),
887 and_constraints: Vec::new(),
888 imul_constraints: Vec::new(),
889 bmul_constraints: Vec::new(),
890 };
891
892 let key_collection = KeyCollection::build(&cs, InoutSegment::Public);
893 assert!(key_collection.public.dense_shift_enc.is_empty());
894 assert!(key_collection.hidden.dense_shift_enc.is_empty());
895
896 assert_sparse_matches_dense::<PackedGhash2x128b>(&cs, 2);
897 }
898}