1use std::{array, iter, mem::MaybeUninit, ops::Deref};
5
6use binius_alloc::{Allocator, VecLike};
7use binius_core::word::Word;
8use binius_field::{
9 ExtensionField, PackedField,
10 linear_transformation::{
11 BytewiseLookupTransformationFactory, InputWrappingTransformationFactory,
12 LinearTransformationFactory, OutputWrappingTransformationFactory, Transformation,
13 },
14 packed_extension,
15};
16use binius_ip_prover::{
17 channel::IPProverChannel,
18 sumcheck::{bivariate_product_prover, prove_single},
19};
20use binius_math::{
21 FieldBuffer, FieldSlice, FieldVec,
22 inner_product::inner_product_packed,
23 multilinear::eq::{eq_ind_partial_eval, eq_ind_zero, scaled_eq_ind_partial_eval},
24 tensor_algebra::TensorAlgebra,
25};
26use binius_utils::{checked_arithmetics::log2_ceil_usize, rayon::prelude::*};
27use binius_verifier::{
28 config::{B1, B128, LOG_WORDS_PER_ELEM},
29 protocols::shift::evaluate_words_mle,
30};
31use itertools::izip;
32
33use crate::{
34 bit_matrix::{ColumnSums, LOG_WEIGHTS_PER_TABLE, RowFoldTables},
35 prove::pack_witness,
36};
37
38pub const LOG_SPLIT_BLOCK: usize = <B128 as ExtensionField<B1>>::LOG_DEGREE;
46
47const N_ROW_TABLES: usize = 1 << (LOG_SPLIT_BLOCK - LOG_WEIGHTS_PER_TABLE);
49
50pub fn fold_1b_rows_for_b128_split<P, Data>(
98 mat: &FieldBuffer<P, Data>,
99 eq_lo: &FieldBuffer<B128>,
100 eq_hi: &FieldBuffer<B128>,
101) -> FieldBuffer<B128>
102where
103 P: PackedField<Scalar = B128>,
104 Data: Deref<Target = [P]>,
105{
106 let log_scalar_bit_width = <B128 as ExtensionField<B1>>::LOG_DEGREE;
107 assert_eq!(mat.log_len(), eq_lo.log_len() + eq_hi.log_len()); assert!(eq_lo.log_len() >= P::LOG_WIDTH || eq_hi.log_len() == 0); assert!(eq_lo.log_len() <= LOG_SPLIT_BLOCK); let lo_tables = RowFoldTables::<B128, N_ROW_TABLES>::new(eq_lo.as_ref());
117
118 let block_packed_len = 1 << eq_lo.log_len().saturating_sub(P::LOG_WIDTH);
120
121 (mat.as_ref().par_chunks(block_packed_len), eq_hi.as_ref().par_iter())
122 .into_par_iter()
123 .fold(
124 || FieldBuffer::zeros(log_scalar_bit_width),
125 |mut acc, (mat_block, &eq_hi_val)| {
126 let mut rows = P::iter_slice(mat_block);
132 let mut sums = ColumnSums::zero();
133
134 lo_tables.fold_into(
141 iter::repeat_with(|| {
142 array::from_fn(|_| {
143 rows.next()
144 .map(packed_extension::cast_base::<B1, _>)
145 .unwrap_or_default()
146 })
147 })
148 .take(N_ROW_TABLES),
149 &mut sums,
150 );
151
152 sums.add_scaled_to(eq_hi_val, acc.as_mut());
155 acc
156 },
157 )
158 .reduce_with(|mut lhs, rhs| {
161 for (lhs_i, &rhs_i) in izip!(lhs.as_mut(), rhs.as_ref()) {
162 *lhs_i += rhs_i;
163 }
164 lhs
165 })
166 .unwrap_or_else(|| FieldBuffer::zeros(log_scalar_bit_width))
168}
169
170pub fn rs_eq_ind_from_factors<A, P>(
203 alloc: &A,
204 n: usize,
205 eq_lo: &FieldBuffer<B128>,
206 eq_hi: &FieldBuffer<B128>,
207 row_batch_query: &FieldBuffer<B128>,
208) -> FieldVec<P, A>
209where
210 A: Allocator,
211 P: PackedField<Scalar = B128>,
212{
213 assert!(eq_lo.log_len() >= P::LOG_WIDTH || eq_hi.log_len() == 0); assert_eq!(row_batch_query.log_len(), <B128 as ExtensionField<B1>>::LOG_DEGREE); let transform = OutputWrappingTransformationFactory::new(
218 InputWrappingTransformationFactory::new(BytewiseLookupTransformationFactory),
219 )
220 .create(row_batch_query.as_ref());
221
222 let log_len = eq_lo.log_len() + eq_hi.log_len();
223 assert!(n <= 1 << log_len); let packed_len = 1usize << log_len.saturating_sub(P::LOG_WIDTH);
225 let block_packed_len = 1 << eq_lo.log_len().saturating_sub(P::LOG_WIDTH);
226
227 let lo_len = eq_lo.as_ref().len();
229 let n_live_blocks = n.div_ceil(lo_len);
230 let block_vals = eq_hi.as_ref()[..n_live_blocks]
231 .par_iter()
232 .enumerate()
233 .map(|(hi, &eq_hi_val)| Some((n.min((hi + 1) * lo_len) - hi * lo_len, eq_hi_val)))
234 .chain(binius_utils::rayon::iter::repeat_n(None, eq_hi.as_ref().len() - n_live_blocks));
235
236 let mut out = alloc.alloc::<P>(packed_len);
238 (out.spare_capacity_mut()[..packed_len].par_chunks_mut(block_packed_len), block_vals)
239 .into_par_iter()
240 .for_each(|(out_block, block_val)| {
241 let Some((n_live, eq_hi_val)) = block_val else {
242 out_block.fill(MaybeUninit::new(P::zero()));
243 return;
244 };
245
246 let entry = |lo: B128| transform.transform(&(lo * eq_hi_val));
249 #[allow(clippy::chunks_exact_to_as_chunks)]
251 let lo_chunks = eq_lo.as_ref()[..n_live].chunks_exact(P::WIDTH);
252 let dangling = lo_chunks.remainder();
253 let (full, rest) = out_block.split_at_mut(n_live / P::WIDTH);
254 for (slot, lo_chunk) in iter::zip(full, lo_chunks) {
255 slot.write(P::from_fn(|j| entry(lo_chunk[j])));
256 }
257
258 let mut rest = rest.iter_mut();
261 if !dangling.is_empty() {
262 rest.next()
263 .expect("a dangling entry has a slot")
264 .write(P::from_scalars(dangling.iter().map(|&lo| entry(lo))));
265 }
266 for slot in rest {
267 slot.write(P::zero());
268 }
269 });
270 unsafe { out.set_len(packed_len) };
272
273 FieldBuffer::new(log_len, out)
274}
275
276fn expand_tensor_factors(point: &[B128], scale: B128) -> (FieldBuffer<B128>, FieldBuffer<B128>) {
283 let (point_lo, point_hi) = point.split_at(point.len().min(LOG_SPLIT_BLOCK));
284 (
285 eq_ind_partial_eval::<B128>(point_lo),
286 scaled_eq_ind_partial_eval::<B128>(point_hi, scale),
287 )
288}
289
290pub struct RingSwitchOutput<A: Allocator, P: PackedField> {
292 pub rs_eq_ind: FieldVec<P, A>,
294 pub sumcheck_claim: P::Scalar,
296}
297
298pub fn prove<A, P, Channel>(
327 alloc: &A,
328 packed_witness: FieldSlice<'_, P>,
329 n_pack: usize,
330 eval_point: &[B128],
331 channel: &mut Channel,
332) -> RingSwitchOutput<A, P>
333where
334 A: Allocator,
335 P: PackedField<Scalar = B128>,
336 Channel: IPProverChannel<B128>,
337{
338 let log_packing = <B128 as ExtensionField<B1>>::LOG_DEGREE;
339 assert!(packed_witness.log_len() + log_packing <= eval_point.len());
340 assert!(n_pack <= 1 << packed_witness.log_len());
341
342 let (eval_point_suffix, surplus) = eval_point[log_packing..].split_at(packed_witness.log_len());
343 let surplus_scale = eq_ind_zero(surplus);
344 let (eq_lo, eq_hi) = tracing::debug_span!("Expand evaluation suffix query")
345 .in_scope(|| expand_tensor_factors(eval_point_suffix, surplus_scale));
346
347 let s_hat_v = tracing::debug_span!("Compute ring-switching partial evaluations")
349 .in_scope(|| fold_1b_rows_for_b128_split(&packed_witness, &eq_lo, &eq_hi));
350 channel.send_many(s_hat_v.as_ref());
351
352 let s_hat_u = TensorAlgebra::<B1, B128>::new(s_hat_v.as_ref().to_vec())
354 .transpose()
355 .elems;
356
357 let r_double_prime = channel.sample_many(log_packing);
359 let eq_r_double_prime = eq_ind_partial_eval::<B128>(&r_double_prime);
360
361 let sumcheck_claim = inner_product_packed::<B128, B128>(
364 log_packing,
365 s_hat_u.into_iter(),
366 eq_r_double_prime.as_ref().iter().copied(),
367 );
368
369 let rs_eq_ind =
373 tracing::debug_span!("Compute ring-switching equality indicator").in_scope(|| {
374 rs_eq_ind_from_factors::<A, P>(alloc, n_pack, &eq_lo, &eq_hi, &eq_r_double_prime)
375 });
376
377 RingSwitchOutput {
378 rs_eq_ind,
379 sumcheck_claim,
380 }
381}
382
383pub fn prove_public_eval<A, P, Channel>(
408 alloc: &A,
409 public_words: &[Word],
410 r_j: &[B128],
411 r_y: &[B128],
412 channel: &mut Channel,
413) where
414 A: Allocator,
415 P: PackedField<Scalar = B128>,
416 Channel: IPProverChannel<B128>,
417{
418 let log_public_elems = log2_ceil_usize(public_words.len()).saturating_sub(LOG_WORDS_PER_ELEM);
421 let r_y_public = &r_y[..log_public_elems + LOG_WORDS_PER_ELEM];
422
423 channel.send_one(evaluate_words_mle::<B128, B128>(public_words, r_j, r_y_public));
424
425 let packed = pack_witness::<P, _>(alloc, log_public_elems, public_words)
426 .expect("the element count is derived from the words being packed");
427 let RingSwitchOutput {
428 rs_eq_ind,
429 sumcheck_claim,
430 } = prove(alloc, packed.as_view(), 1 << log_public_elems, &[r_j, r_y_public].concat(), channel);
431
432 let prover = bivariate_product_prover(alloc, [packed, rs_eq_ind], sumcheck_claim);
436 prove_single(prover, channel);
437}
438
439#[cfg(test)]
440mod test {
441 use binius_alloc::GlobalAllocator;
442 use binius_field::{
443 ExtensionField, Field, Ghash128b, PackedField, PackedGhash2x128b, PackedGhash4x128b,
444 PackedSubfield, packed_extension,
445 };
446 use binius_hash::StdDigest;
447 use binius_math::{
448 FieldBuffer,
449 inner_product::{inner_product_buffers, inner_product_subfield},
450 multilinear::{eq::eq_ind_partial_eval, evaluate::evaluate_inplace},
451 test_utils::{index_to_hypercube_point, random_field_buffer, random_scalars},
452 };
453 use binius_transcript::{ProverTranscript, fiat_shamir::HasherChallenger};
454 use binius_verifier::{
455 config::B1,
456 ring_switch::{RingSwitchVerifyOutput, eval_rs_eq, verify},
457 };
458 use rand::{SeedableRng, rngs::StdRng};
459
460 use super::*;
461
462 type F = Ghash128b;
463
464 fn naive_fold_1b_rows<P: PackedField<Scalar = F>>(mat: &FieldBuffer<P>, eq: &[F]) -> Vec<F> {
471 let mut out = vec![F::ZERO; <F as ExtensionField<B1>>::DEGREE];
472 for (r, &weight) in eq.iter().enumerate() {
473 let row = mat.get(r);
474 for (bit, out_b) in iter::zip(ExtensionField::<B1>::iter_bases(&row), &mut out) {
475 if bit == B1::ONE {
476 *out_b += weight;
477 }
478 }
479 }
480 out
481 }
482
483 fn check_split_fold_matches_definition<P: PackedField<Scalar = F>>(log_len: usize, seed: u64) {
490 let mut rng = StdRng::seed_from_u64(seed);
491 let mat = random_field_buffer::<P>(&mut rng, log_len);
492 let point: Vec<F> = random_scalars(&mut rng, log_len);
493
494 let expected = naive_fold_1b_rows(&mat, eq_ind_partial_eval::<F>(&point).as_ref());
495
496 for split_at in P::LOG_WIDTH.min(log_len)..=log_len.min(LOG_SPLIT_BLOCK) {
499 let (point_lo, point_hi) = point.split_at(split_at);
500 let eq_lo = eq_ind_partial_eval::<F>(point_lo);
501 let eq_hi = eq_ind_partial_eval::<F>(point_hi);
502
503 let split = fold_1b_rows_for_b128_split(&mat, &eq_lo, &eq_hi);
504 assert_eq!(
505 split.as_ref(),
506 expected.as_slice(),
507 "log_len={log_len}, split_at={split_at}"
508 );
509 }
510 }
511
512 #[test]
513 fn test_split_fold_matches_definition() {
514 for (i, log_len) in [0, 1, 2, 6, 7, 8].into_iter().enumerate() {
516 let seed = i as u64;
517 check_split_fold_matches_definition::<F>(log_len, seed);
518 check_split_fold_matches_definition::<PackedGhash2x128b>(log_len, seed);
519 check_split_fold_matches_definition::<PackedGhash4x128b>(log_len, seed);
520 }
521 }
522
523 fn check_rs_eq_ind_from_factors<P: PackedField<Scalar = F>>(log_len: usize, seed: u64) {
530 let mut rng = StdRng::seed_from_u64(seed);
531 let point: Vec<F> = random_scalars(&mut rng, log_len);
532 let row_batching_challenges: Vec<F> =
533 random_scalars(&mut rng, <F as ExtensionField<B1>>::LOG_DEGREE);
534 let row_batch_query = eq_ind_partial_eval::<F>(&row_batching_challenges);
535
536 for split_at in P::LOG_WIDTH.min(log_len)..=log_len {
538 let (point_lo, point_hi) = point.split_at(split_at);
539 let eq_lo = eq_ind_partial_eval::<F>(point_lo);
540 let eq_hi = eq_ind_partial_eval::<F>(point_hi);
541
542 for n in [1 << log_len, (1 << log_len) * 2 / 3] {
544 let rs_eq_ind = rs_eq_ind_from_factors::<_, P>(
545 &GlobalAllocator,
546 n,
547 &eq_lo,
548 &eq_hi,
549 &row_batch_query,
550 );
551
552 for index in 0..1 << log_len {
553 let expected = eval_rs_eq::<F>(
554 n,
555 &point,
556 &index_to_hypercube_point::<F>(log_len, index),
557 row_batch_query.as_ref(),
558 );
559 assert_eq!(
560 rs_eq_ind.get(index),
561 expected,
562 "split_at={split_at}, n={n}, index={index}"
563 );
564 }
565
566 let trailing = rs_eq_ind.as_ref()[0].iter().skip(1 << log_len);
569 assert!(
570 trailing.take(P::WIDTH).all(|lane| lane == F::ZERO),
571 "split_at={split_at}, n={n}"
572 );
573 }
574 }
575 }
576
577 #[test]
578 fn test_rs_eq_ind_from_factors() {
579 for (i, log_len) in [0, 1, 2, 6, 7, 8].into_iter().enumerate() {
581 let seed = i as u64;
582 check_rs_eq_ind_from_factors::<F>(log_len, seed);
583 check_rs_eq_ind_from_factors::<PackedGhash2x128b>(log_len, seed);
584 check_rs_eq_ind_from_factors::<PackedGhash4x128b>(log_len, seed);
585 }
586 }
587
588 #[test]
589 fn test_out_of_range_evaluation() {
590 let mut rng = StdRng::from_seed([0; 32]);
591
592 let n_vars_big_field = 3;
596
597 let z_vals: Vec<F> = random_scalars(&mut rng, n_vars_big_field);
599
600 let row_batching_challenges: Vec<F> =
601 random_scalars(&mut rng, <F as ExtensionField<B1>>::LOG_DEGREE);
602
603 let row_batching_expanded_query: FieldBuffer<F> =
604 eq_ind_partial_eval(&row_batching_challenges);
605
606 let (eq_lo, eq_hi) = expand_tensor_factors(&z_vals, F::ONE);
607 let rs_eq = rs_eq_ind_from_factors::<_, F>(
608 &GlobalAllocator,
609 1 << n_vars_big_field,
610 &eq_lo,
611 &eq_hi,
612 &row_batching_expanded_query,
613 );
614
615 let eval_point: Vec<F> = random_scalars(&mut rng, n_vars_big_field);
617
618 let tensor_expanded_eval_point = eq_ind_partial_eval::<F>(&eval_point);
621 let expected_eval = inner_product_buffers(&rs_eq, &tensor_expanded_eval_point);
622
623 let actual_eval = eval_rs_eq::<F>(
624 1 << n_vars_big_field,
625 &z_vals,
626 &eval_point,
627 row_batching_expanded_query.as_ref(),
628 );
629
630 assert_eq!(expected_eval, actual_eval);
631 }
632
633 #[test]
634 fn test_row_fold_composes_into_the_claim() {
635 let mut rng = StdRng::seed_from_u64(0);
636
637 type P = PackedGhash2x128b;
638
639 let n = 10;
646 let log_degree = <F as ExtensionField<B1>>::LOG_DEGREE;
647
648 let bit_matrix = random_field_buffer::<PackedSubfield<P, B1>>(&mut rng, n + log_degree);
650 let eval_point: Vec<F> = random_scalars(&mut rng, n + log_degree);
651 let (prefix, suffix) = eval_point.split_at(log_degree);
652
653 let full_tensor = eq_ind_partial_eval::<F>(&eval_point);
655 let expected = inner_product_subfield(
656 PackedField::iter_slice(bit_matrix.as_ref()),
657 PackedField::iter_slice(full_tensor.as_ref()),
658 );
659
660 let mat = FieldBuffer::<P>::new(
664 n,
665 bit_matrix
666 .as_ref()
667 .iter()
668 .map(|&bits_packed| packed_extension::cast_ext::<B1, P>(bits_packed))
669 .collect(),
670 );
671 let (eq_lo, eq_hi) = expand_tensor_factors(suffix, F::ONE);
672 let s_hat_v = fold_1b_rows_for_b128_split(&mat, &eq_lo, &eq_hi);
673
674 assert_eq!(evaluate_inplace(s_hat_v, prefix), expected);
675 }
676
677 #[test]
678 fn a_short_oracle_with_surplus_coordinates_ring_switches() {
679 type P = PackedGhash2x128b;
680 type StdChallenger = HasherChallenger<StdDigest>;
681
682 let (n_vars, n_pack, n_surplus) = (4, 11, 2);
685 let log_degree = <F as ExtensionField<B1>>::LOG_DEGREE;
686 let mut rng = StdRng::seed_from_u64(0);
687 let mut witness = random_field_buffer::<P>(&mut rng, n_vars);
688 for i in n_pack..1 << n_vars {
689 witness.set(i, F::ZERO);
690 }
691 let eval_point: Vec<F> = random_scalars(&mut rng, log_degree + n_vars + n_surplus);
692
693 let (inner_point, surplus) = eval_point.split_at(log_degree + n_vars);
695 let bits = PackedField::iter_slice(witness.as_ref())
696 .flat_map(|elem| ExtensionField::<B1>::iter_bases(&elem).collect::<Vec<_>>());
697 let tensor = eq_ind_partial_eval::<F>(inner_point);
698 let evaluation_claim = iter::zip(bits, tensor.iter_scalars())
699 .map(|(bit, weight)| weight * bit)
700 .sum::<F>()
701 * surplus.iter().map(|&r| F::ONE - r).product::<F>();
702
703 let mut prover_transcript = ProverTranscript::new(StdChallenger::default());
704 let RingSwitchOutput {
705 rs_eq_ind,
706 sumcheck_claim,
707 } = prove(&GlobalAllocator, witness.as_view(), n_pack, &eval_point, &mut prover_transcript);
708
709 let mut verifier_transcript = prover_transcript.into_verifier();
710 let RingSwitchVerifyOutput {
711 eq_r_double_prime,
712 sumcheck_claim: verifier_claim,
713 } = verify(evaluation_claim, &eval_point, &mut verifier_transcript).unwrap();
714
715 assert_eq!(verifier_claim, sumcheck_claim);
716 assert_eq!(inner_product_buffers(&witness, &rs_eq_ind), sumcheck_claim);
717 assert!(
718 rs_eq_ind
719 .iter_scalars()
720 .skip(n_pack)
721 .all(|value| value == F::ZERO)
722 );
723
724 let query: Vec<F> = random_scalars(&mut rng, n_vars);
726 assert_eq!(
727 eval_rs_eq(n_pack, &eval_point[log_degree..], &query, &eq_r_double_prime),
728 inner_product_buffers(&rs_eq_ind, &eq_ind_partial_eval::<P>(&query)),
729 );
730 }
731}