binius_verifier/protocols/rerand.rs
1// Copyright 2026 The Binius Developers
2
3//! The BitAnd sumcheck, batched with the multiplication reductions' operand-column MLE-checks.
4//!
5//! After the univariate skip, the BitAnd claim `g(z)` is the MLE-check
6//!
7//! ```text
8//! g(z) = sum_x eq(x, r_x) * (A(z, x) * B(z, x) - C(z, x))
9//! ```
10//!
11//! at the zerocheck point `r_x`. Each operand column of an IntMul or BinMul reduction carries one
12//! claim per bit at that reduction's own point `rho`. The Lagrange weights at `z` fold them to one
13//! MLE-check per column, `alpha = sum_x eq(x, rho) * Z(z, x)`, with no transcript traffic.
14//!
15//! One sumcheck in plain form proves all of them, batched by powers of one challenge `theta`,
16//! BitAnd first. It runs over the longest summand's variables. A shorter summand is zero-padded on
17//! its high variables, so its point is a prefix of the unified point `r*`.
18//!
19//! The round polynomials have degree 3: BitAnd's composition has degree 2, and its equality
20//! indicator adds one.
21
22use std::iter;
23
24use binius_core::word::Word;
25use binius_field::Field;
26use binius_ip::{
27 channel::IPVerifierChannel,
28 sumcheck::{BatchSumcheckOutput, batch_verify},
29};
30use binius_math::{
31 inner_product::inner_product,
32 multilinear::eq::{eq_ind, eq_ind_zero},
33 univariate::evaluate_univariate,
34};
35
36use crate::Error;
37
38/// One reduction's per-bit evaluation claims on its operand columns, at that reduction's point.
39pub struct OperandClaims<'a, E> {
40 /// The reduction's constraint point. In batch mode: instances low, constraints high.
41 pub point: &'a [E],
42 /// One 64-entry array per operand column, in the shift reduction's operand order.
43 pub columns: Vec<&'a [E; Word::BITS]>,
44}
45
46/// Degree of the batched round polynomials: the BitAnd summand's prime degree 2 plus its indicator.
47pub const SUMCHECK_DEGREE: usize = 3;
48
49/// The evaluation claims the batched sumcheck reduces to, all at prefixes of one point.
50#[derive(Debug, Clone, PartialEq, Eq)]
51pub struct RerandOutput<F> {
52 /// The unified point `r*`, low-to-high. Its length is the longest summand's variable count.
53 pub eval_point: Vec<F>,
54 /// The evaluations of `A`, `B` and `C`, folded at `z`, at `eval_point[..r_x.len()]`.
55 pub bitand_evals: [F; 3],
56 /// One evaluation per operand column, flattened in input order, each at
57 /// `eval_point[..point.len()]` for its reduction's point.
58 pub operand_evals: Vec<F>,
59}
60
61/// Verifies the BitAnd sumcheck batched with the operand-column MLE-checks.
62///
63/// The prover sends the round polynomials, then the evaluations `[a, b, c]`, then one evaluation
64/// per operand column in input order.
65///
66/// # Arguments
67///
68/// * `zerocheck_challenges` - the BitAnd summand's point `r_x`.
69/// * `bitand_claim` - the univariate-skip polynomial at `z`, `g(z)`.
70/// * `lagrange` - the Lagrange weights at `z` on the 64-point domain.
71/// * `operands` - the operand claims of each multiplication reduction.
72/// * `channel` - the verifier channel.
73///
74/// # Soundness
75///
76/// The per-bit claims of `operands` must be in the transcript before `z` was drawn. Otherwise a
77/// prover can choose them as a function of the weights that fold them.
78///
79/// # Errors
80///
81/// Returns an error if the sumcheck or its closing check fails.
82pub fn verify<F, C>(
83 zerocheck_challenges: &[C::Elem],
84 bitand_claim: C::Elem,
85 lagrange: &[C::Elem],
86 operands: &[OperandClaims<'_, C::Elem>],
87 channel: &mut C,
88) -> Result<RerandOutput<C::Elem>, Error>
89where
90 F: Field,
91 C: IPVerifierChannel<F>,
92{
93 // Fold each column's per-bit claims to one MLE-check claim at the reduction's point.
94 let operand_claims = operands.iter().flat_map(|operand| {
95 operand
96 .columns
97 .iter()
98 .map(|column| inner_product(column.iter().cloned(), lagrange.iter().cloned()))
99 });
100 let sums = iter::once(bitand_claim)
101 .chain(operand_claims)
102 .collect::<Vec<_>>();
103
104 let n_vars = operands
105 .iter()
106 .map(|operand| operand.point.len())
107 .fold(zerocheck_challenges.len(), usize::max);
108 let BatchSumcheckOutput {
109 batch_coeff,
110 eval,
111 challenges: mut eval_point,
112 } = batch_verify(n_vars, SUMCHECK_DEGREE, &sums, channel)?;
113 eval_point.reverse();
114
115 let bitand_evals = channel.recv_array::<3>()?;
116 let operand_evals = channel.recv_many(sums.len() - 1)?;
117
118 // A summand at `point` is weighted by its indicator on the low coordinates and by the zero
119 // indicator on the padding coordinates above them.
120 let weight = |point: &[C::Elem]| {
121 let (low, padding) = eval_point.split_at(point.len());
122 eq_ind(point, low) * eq_ind_zero(padding)
123 };
124 let [a, b, c] = bitand_evals.clone();
125 let bitand_term = weight(zerocheck_challenges) * (a * b - c);
126 let operand_weights = operands
127 .iter()
128 .flat_map(|operand| iter::repeat_n(weight(operand.point), operand.columns.len()));
129 let operand_terms =
130 iter::zip(operand_weights, &operand_evals).map(|(weight, eval)| weight * eval.clone());
131 let terms = iter::once(bitand_term)
132 .chain(operand_terms)
133 .collect::<Vec<_>>();
134 channel.assert_zero(evaluate_univariate(&terms, &batch_coeff) - eval)?;
135
136 Ok(RerandOutput {
137 eval_point,
138 bitand_evals,
139 operand_evals,
140 })
141}