Skip to main content

binius_verifier/protocols/shift/
shift_ind.rs

1// Copyright 2025 Irreducible Inc.
2// Copyright 2026 The Binius Developers
3
4//! Evaluation of the shift indicator multilinear extensions.
5
6use std::iter;
7
8use binius_core::word::Word;
9use binius_field::FieldOps;
10use binius_math::{line::extrapolate_line, multilinear::eq::eq_one_var};
11
12use super::SHIFT_VARIANT_COUNT;
13
14/// The number of bit variables a half-word (`*32`) shift variant acts over.
15const HALF_WORD_LOG_BITS: usize = Word::LOG_BITS - 1;
16
17/// Evaluates the eight shift indicator multilinear extensions at one point.
18///
19/// A shift indicator is the 3·[`Word::LOG_BITS`]-variate multilinear extension of the predicate
20/// relating an output bit index `i`, an input bit index `j` and a shift amount `s`:
21///
22/// ```text
23/// sll   i == j + s            sll32   i / 32 == j / 32 and i % 32 == j % 32 + s % 32
24/// srl   j == i + s            srl32   likewise, over each half independently
25/// sra   j == min(i + s, 63)   sra32
26/// rotr  j == (i + s) % 64     rotr32
27/// ```
28///
29/// The results are ordered by [`ShiftVariant`](binius_core::ShiftVariant), so the array indexes
30/// straight by variant.
31///
32/// ## Preconditions
33///
34/// * `r_i`, `r_j` and `r_s` each have exactly [`Word::LOG_BITS`] entries
35pub fn evaluate_shift_inds<E: FieldOps>(
36	r_i: &[E],
37	r_j: &[E],
38	r_s: &[E],
39) -> [E; SHIFT_VARIANT_COUNT] {
40	assert_eq!(r_i.len(), Word::LOG_BITS); // precondition
41	assert_eq!(r_j.len(), Word::LOG_BITS); // precondition
42	assert_eq!(r_s.len(), Word::LOG_BITS); // precondition
43
44	let [sll, srl, sra, rotr] = evaluate_variants(r_i, r_j, r_s);
45
46	// A half-word variant applies the same four rules to each 32-bit half, reading only the low
47	// bits of the shift amount. The two halves never mix, so the indicator also carries the
48	// equality of the halves the two bit indices fall in.
49	let [sll32, srl32, sra32, rotr32] = evaluate_variants(
50		&r_i[..HALF_WORD_LOG_BITS],
51		&r_j[..HALF_WORD_LOG_BITS],
52		&r_s[..HALF_WORD_LOG_BITS],
53	);
54	let same_half = eq_one_var(r_i[HALF_WORD_LOG_BITS].clone(), r_j[HALF_WORD_LOG_BITS].clone());
55
56	[
57		sll,
58		srl,
59		sra,
60		rotr,
61		same_half.clone() * sll32,
62		same_half.clone() * srl32,
63		same_half.clone() * sra32,
64		same_half * rotr32,
65	]
66}
67
68/// Evaluates the four shift indicators over `r_i.len()` bit variables, in variant order.
69///
70/// All four are built from the indicators of the addition `i + s`: whether it equals `j`, and
71/// whether it equals `j` only after wrapping past the top bit.
72fn evaluate_variants<E: FieldOps>(r_i: &[E], r_j: &[E], r_s: &[E]) -> [E; 4] {
73	let (srl, wrapped) = evaluate_sum_inds(r_i, r_j, r_s);
74
75	// A left shift is a right shift with the two bit indices exchanged: `i == j + s`.
76	let (sll, _) = evaluate_sum_inds(r_j, r_i, r_s);
77
78	// An arithmetic right shift agrees with the logical one until the sum overflows, past which
79	// every output bit reads the sign bit. The product of the `r_j` coordinates is the equality
80	// indicator selecting that top position.
81	let sign_position: E = r_j.iter().cloned().product();
82	let sra = srl.clone() + sign_position * evaluate_overflow_ind(r_i, r_s);
83
84	// A rotation keeps the bits the sum carries past the top, wrapping them around instead.
85	let rotr = srl.clone() + wrapped;
86
87	[sll, srl, sra, rotr]
88}
89
90/// Evaluates the multilinear extensions of the two indicators of the addition `i + s`:
91/// `i + s == j`, and `i + s == j + 2^n` — the sum wrapped around the top bit.
92///
93/// The addition is checked one bit position at a time, carrying between positions, so the state
94/// is the pair of indicators that the positions below sum correctly with a carry out of 0 and of
95/// 1 respectively. Both start certain: the empty sum is correct and carries nothing.
96fn evaluate_sum_inds<E: FieldOps>(r_i: &[E], r_j: &[E], r_s: &[E]) -> (E, E) {
97	iter::zip(iter::zip(r_i, r_j), r_s).fold(
98		(E::one(), E::zero()),
99		|(no_carry, carry), ((i, j), s)| {
100			// A position's transition reads `j` and `s` through three weights only: the two agree,
101			// only `j` is set, or only `s` is set.
102			let both = j.clone() * s;
103			let j_only = j.clone() - &both;
104			let s_only = s.clone() - &both;
105			let agree = eq_one_var(j.clone(), s.clone());
106
107			// The transitions at `i = 0` and at `i = 1`, interpolated at the coordinate. With
108			// `i = 0` the position sums correctly either when `j` agrees with `s` and nothing
109			// carries in, or when only `j` is set and the carry coming in fills it; it carries out
110			// only when `s` absorbs a carry in. With `i = 1` the position carries out whenever `s`
111			// is set or a carry comes in, and sums correctly against the `j` those leave.
112			(
113				extrapolate_line(
114					agree.clone() * &no_carry + j_only.clone() * &carry,
115					j_only * &no_carry,
116					i.clone(),
117				),
118				extrapolate_line(
119					s_only.clone() * &carry,
120					s_only * &no_carry + agree * &carry,
121					i.clone(),
122				),
123			)
124		},
125	)
126}
127
128/// Evaluates the multilinear extension of the indicator that the addition `i + s` overflows past
129/// the top bit, `i + s >= 2^n`.
130///
131/// This is [`evaluate_sum_inds`]'s carry state with the input bit index summed out: exactly one
132/// `j` completes the addition for each `(i, s)`, so summing over `j` leaves the carry alone.
133fn evaluate_overflow_ind<E: FieldOps>(r_i: &[E], r_s: &[E]) -> E {
134	iter::zip(r_i, r_s).fold(E::zero(), |carry, (i, s)| {
135		// With `i = 0` only a carry in that `s` propagates survives; with `i = 1` the position
136		// carries out whenever `s` is set or a carry comes in.
137		extrapolate_line(s.clone() * &carry, s.clone() + (E::one() - s) * &carry, i.clone())
138	})
139}
140
141#[cfg(test)]
142mod tests {
143	use std::array;
144
145	use binius_field::{Field, Ghash128b as B128};
146	use binius_math::test_utils::random_scalars;
147	use rand::{RngExt, SeedableRng, rngs::StdRng};
148
149	use super::*;
150
151	/// The bit-index hypercube vertex at `index`.
152	fn bit_index_vertex(index: usize) -> [B128; Word::LOG_BITS] {
153		array::from_fn(|bit| {
154			if (index >> bit) & 1 == 1 {
155				B128::ONE
156			} else {
157				B128::ZERO
158			}
159		})
160	}
161
162	/// Over the hypercube the eight evaluations must be the indicators of the integer relations
163	/// the shift variants are defined by.
164	#[test]
165	fn hypercube_vertices_match_the_shift_relations() {
166		let mut rng = StdRng::seed_from_u64(0);
167
168		for _trial in 0..1024 {
169			let i = rng.random_range(0..Word::BITS);
170			let j = rng.random_range(0..Word::BITS);
171			let s = rng.random_range(0..Word::BITS);
172
173			let evals = evaluate_shift_inds(
174				&bit_index_vertex(i),
175				&bit_index_vertex(j),
176				&bit_index_vertex(s),
177			);
178
179			let (i_lo, j_lo, s_lo) = (i % 32, j % 32, s % 32);
180			let same_half = i / 32 == j / 32;
181			let expected = [
182				i == j + s,
183				j == i + s,
184				j == (i + s).min(Word::BITS - 1),
185				j == (i + s) % Word::BITS,
186				same_half && i_lo == j_lo + s_lo,
187				same_half && j_lo == i_lo + s_lo,
188				same_half && j_lo == (i_lo + s_lo).min(31),
189				same_half && j_lo == (i_lo + s_lo) % 32,
190			];
191
192			for (variant, (eval, expected)) in iter::zip(evals, expected).enumerate() {
193				let expected = if expected { B128::ONE } else { B128::ZERO };
194				assert_eq!(eval, expected, "variant {variant} at i={i}, j={j}, s={s}");
195			}
196		}
197	}
198
199	/// The evaluations must be multilinear in every coordinate: their hypercube values pin the
200	/// polynomials down only together with this.
201	#[test]
202	fn evaluations_are_multilinear_in_every_coordinate() {
203		let mut rng = StdRng::seed_from_u64(0);
204		let point = [
205			random_scalars::<B128>(&mut rng, Word::LOG_BITS),
206			random_scalars::<B128>(&mut rng, Word::LOG_BITS),
207			random_scalars::<B128>(&mut rng, Word::LOG_BITS),
208		]
209		.concat();
210
211		let evaluate = |point: &[B128]| {
212			let (r_i, rest) = point.split_at(Word::LOG_BITS);
213			let (r_j, r_s) = rest.split_at(Word::LOG_BITS);
214			evaluate_shift_inds(r_i, r_j, r_s)
215		};
216
217		// Every coordinate of all three points, restricted to 0 and to 1.
218		for coordinate in 0..point.len() {
219			let restrict = |value| {
220				let mut restricted = point.clone();
221				restricted[coordinate] = value;
222				evaluate(&restricted)
223			};
224
225			for (variant, ((eval, at_zero), at_one)) in
226				iter::zip(iter::zip(evaluate(&point), restrict(B128::ZERO)), restrict(B128::ONE))
227					.enumerate()
228			{
229				assert_eq!(
230					eval,
231					extrapolate_line(at_zero, at_one, point[coordinate]),
232					"variant {variant} is not linear in coordinate {coordinate}"
233				);
234			}
235		}
236	}
237}