Skip to main content

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}