binius_verifier/protocols/shift/
shift_ind.rs1use 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
14const HALF_WORD_LOG_BITS: usize = Word::LOG_BITS - 1;
16
17pub 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); assert_eq!(r_j.len(), Word::LOG_BITS); assert_eq!(r_s.len(), Word::LOG_BITS); let [sll, srl, sra, rotr] = evaluate_variants(r_i, r_j, r_s);
45
46 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
68fn 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 let (sll, _) = evaluate_sum_inds(r_j, r_i, r_s);
77
78 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 let rotr = srl.clone() + wrapped;
86
87 [sll, srl, sra, rotr]
88}
89
90fn 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 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 (
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
128fn 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 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 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 #[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 #[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 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}