1use std::{iter, ops::Deref};
8
9use binius_alloc::Allocator;
10use binius_field::{Field, PackedField, util::powers};
11use binius_ip::sumcheck::RoundCoeffs;
12use binius_math::{
13 FieldVec, field_buffer::FieldBuffer, line::extrapolate_line, univariate::evaluate_univariate,
14};
15
16pub fn expand_libra_eval<A: Allocator, P: PackedField>(
41 alloc: &A,
42 challenge_point: &[P::Scalar],
43 n_vars: usize,
44 degree: usize,
45 m_n: usize,
46 m_d: usize,
47) -> FieldVec<P, A> {
48 debug_assert!(challenge_point.len() == n_vars);
49 debug_assert!(n_vars <= 1 << m_n);
50 debug_assert!(degree < 1 << m_d);
51
52 let log_size = m_n + m_d;
53 let mut buffer = FieldBuffer::zeros_in(alloc, log_size);
54 let row_stride = 1 << m_d;
55
56 for (j, &r_j) in challenge_point.iter().enumerate() {
57 let base_idx = j * row_stride;
58 for (k, power) in powers(r_j).take(degree + 1).enumerate() {
59 buffer.set(base_idx + k, power);
60 }
61 }
62
63 buffer
64}
65
66pub struct Mask<P: PackedField, Data: Deref<Target = [P]> = Box<[P]>> {
81 n_vars: usize,
83 degree: usize,
85 buffer: FieldBuffer<P, Data>,
89}
90
91impl<F: Field, P: PackedField<Scalar = F>, Data: Deref<Target = [P]>> Mask<P, Data> {
92 pub const fn new(n_vars: usize, degree: usize, buffer: FieldBuffer<P, Data>) -> Self {
100 Self {
101 n_vars,
102 degree,
103 buffer,
104 }
105 }
106
107 pub const fn n_vars(&self) -> usize {
109 self.n_vars
110 }
111
112 pub const fn degree(&self) -> usize {
114 self.degree
115 }
116
117 const fn log_degree_plus_one(&self) -> usize {
119 (self.degree + 1).next_power_of_two().ilog2() as usize
120 }
121
122 pub fn get_coeff(&self, var_index: usize, coeff_index: usize) -> F {
124 debug_assert!(var_index < self.n_vars);
125 debug_assert!(coeff_index <= self.degree);
126 let row_stride = 1 << self.log_degree_plus_one();
127 self.buffer.get(var_index * row_stride + coeff_index)
128 }
129
130 pub fn coeffs_for_var(&self, var_index: usize) -> impl Iterator<Item = F> + '_ {
132 debug_assert!(var_index < self.n_vars);
133 let m_d = self.log_degree_plus_one();
134 let row_stride = 1 << m_d;
135 let start = var_index * row_stride;
136 (0..=self.degree).map(move |j| self.buffer.get(start + j))
137 }
138
139 pub fn evaluate_univariate(&self, var_index: usize, x: F) -> F {
141 let coeffs: Vec<_> = self.coeffs_for_var(var_index).collect();
142 evaluate_univariate(&coeffs, &x)
143 }
144
145 pub fn evaluate_mle(&self, eval_point: &[F]) -> F {
156 assert_eq!(eval_point.len(), self.n_vars);
157
158 iter::zip(0..self.n_vars, eval_point)
159 .map(|(i, &z_i)| {
160 let g_at_0 = self.get_coeff(i, 0);
161 let g_at_1 = self.evaluate_univariate(i, F::ONE);
162 extrapolate_line(g_at_0, g_at_1, z_i)
163 })
164 .sum()
165 }
166
167 pub fn evaluate(&self, point: &[F]) -> F {
169 assert_eq!(point.len(), self.n_vars);
170 iter::zip(0..self.n_vars, point)
171 .map(|(i, &r_i)| self.evaluate_univariate(i, r_i))
172 .sum()
173 }
174
175 fn sum_univariate_over_infinity(&self, var_index: usize) -> F {
177 self.get_coeff(var_index, 0) + self.get_coeff(var_index, self.degree)
178 }
179
180 pub fn sum_over_infinity_cube(&self) -> F {
184 (0..self.n_vars)
185 .map(|i| self.sum_univariate_over_infinity(i))
186 .sum()
187 }
188
189 pub fn infinity_round_coeffs(&self, challenges: &[F]) -> RoundCoeffs<F> {
200 let var_index = self.n_vars - 1 - challenges.len();
201 let bound = iter::zip((var_index + 1..self.n_vars).rev(), challenges)
202 .map(|(i, &r_i)| self.evaluate_univariate(i, r_i))
203 .sum::<F>();
204 let free = (0..var_index)
205 .map(|i| self.sum_univariate_over_infinity(i))
206 .sum::<F>();
207 let mut coeffs = self.coeffs_for_var(var_index).collect::<Vec<_>>();
208 coeffs[0] += bound + free;
209 RoundCoeffs(coeffs)
210 }
211}
212
213impl<P: PackedField, Data: Deref<Target = [P]>> AsRef<FieldBuffer<P, Data>> for Mask<P, Data> {
214 fn as_ref(&self) -> &FieldBuffer<P, Data> {
215 &self.buffer
216 }
217}
218
219#[cfg(test)]
220mod tests {
221 use binius_alloc::GlobalAllocator;
222 use binius_field::{Random, arch::OptimalB128};
223 use binius_ip::libra::{libra_eval, mask_buffer_dimensions};
224 use binius_math::{
225 multilinear::hypercube::{InfCube, OneCube, eq_ind_partial_eval_scalars},
226 test_utils::{random_field_buffer, random_scalars},
227 };
228 use binius_transcript::{ProverTranscript, fiat_shamir::HasherChallenger};
229 use rand::prelude::*;
230
231 use super::*;
232
233 type StdChallenger = HasherChallenger<sha2::Sha256>;
234 type B128 = OptimalB128;
235
236 #[test]
237 fn test_libra_eval_inner_product_equals_mask_eval() {
238 use binius_alloc::GlobalAllocator;
239 use binius_math::inner_product::inner_product_buffers;
240
241 let mut rng = StdRng::seed_from_u64(0);
242 let n_vars = 6;
243 let degree = 2;
244
245 let (m_n, m_d) = mask_buffer_dimensions(n_vars, degree);
247 let mask_buffer = random_field_buffer::<B128>(&mut rng, m_n + m_d);
248
249 let challenge_point: Vec<B128> = random_scalars(&mut rng, n_vars);
251
252 let mask = Mask::new(n_vars, degree, mask_buffer.as_view());
254 let direct_eval: B128 = (0..n_vars)
255 .map(|i| mask.evaluate_univariate(i, challenge_point[i]))
256 .sum();
257
258 let libra_eval_tensor = expand_libra_eval::<_, B128>(
260 &GlobalAllocator,
261 &challenge_point,
262 n_vars,
263 degree,
264 m_n,
265 m_d,
266 );
267 let inner_product_eval = inner_product_buffers(&mask_buffer, &libra_eval_tensor);
268
269 assert_eq!(
270 direct_eval, inner_product_eval,
271 "Inner product <g', libra_eval_r> should equal g(r)"
272 );
273 }
274
275 #[test]
276 fn test_libra_eval_sumcheck() {
277 use binius_alloc::GlobalAllocator;
278 use binius_ip::{libra::libra_eval, sumcheck::verify};
279 use binius_math::{inner_product::inner_product_par, multilinear::evaluate::evaluate};
280
281 use crate::sumcheck::{bivariate_product_prover, prove_single};
282
283 let mut rng = StdRng::seed_from_u64(0);
284 let n_vars = 6;
285 let degree = 2;
286 let alloc = GlobalAllocator;
287
288 let (m_n, m_d) = mask_buffer_dimensions(n_vars, degree);
290 let log_size = m_n + m_d;
291 let mask_buffer = random_field_buffer::<B128>(&mut rng, log_size);
292
293 let challenge_point: Vec<B128> = random_scalars(&mut rng, n_vars);
295
296 let libra_eval_tensor = expand_libra_eval::<_, B128>(
298 &GlobalAllocator,
299 &challenge_point,
300 n_vars,
301 degree,
302 m_n,
303 m_d,
304 );
305
306 let claimed_sum = inner_product_par(&mask_buffer, &libra_eval_tensor);
308
309 let prover =
311 bivariate_product_prover(&alloc, [mask_buffer.clone(), libra_eval_tensor], claimed_sum);
312
313 let mut prover_transcript = ProverTranscript::new(StdChallenger::default());
315 let output = prove_single(prover, &mut prover_transcript);
316
317 prover_transcript
319 .message()
320 .write_slice(&output.multilinear_evals);
321
322 let mut verifier_transcript = prover_transcript.into_verifier();
324 let sumcheck_output = verify(
325 log_size,
326 2, claimed_sum,
328 &mut verifier_transcript,
329 )
330 .unwrap();
331
332 let multilinear_evals: Vec<B128> = verifier_transcript.message().read_vec(2).unwrap();
334 let [g_prime_eval, libra_eval_out] = [multilinear_evals[0], multilinear_evals[1]];
335
336 assert_eq!(g_prime_eval * libra_eval_out, sumcheck_output.eval);
338
339 let mut query_point = sumcheck_output.challenges;
344 query_point.reverse();
345 let (query_k, query_j) = query_point.split_at(m_d);
346
347 let expected_libra_eval_out =
348 libra_eval::<OneCube, B128>(&challenge_point, query_j, query_k, n_vars, degree);
349 assert_eq!(
350 libra_eval_out, expected_libra_eval_out,
351 "libra_eval should match the sumcheck-reduced evaluation"
352 );
353
354 let expected_g_prime_eval = evaluate(&mask_buffer, &query_point);
356 assert_eq!(g_prime_eval, expected_g_prime_eval);
357 }
358
359 #[test]
360 fn libra_eval_over_the_infinity_cube_reads_monomial_coefficients() {
361 let mut rng = StdRng::seed_from_u64(0);
362 let degree = 2;
363 for n_vars in [0, 1, 3, 4, 5] {
364 let (m_n, m_d) = mask_buffer_dimensions(n_vars, degree);
365 let challenge_point = random_scalars::<B128>(&mut rng, n_vars);
366 let query_point = random_scalars::<B128>(&mut rng, m_n + m_d);
367
368 let table = expand_libra_eval::<_, B128>(
369 &GlobalAllocator,
370 &challenge_point,
371 n_vars,
372 degree,
373 m_n,
374 m_d,
375 );
376 let monomials = eq_ind_partial_eval_scalars::<InfCube, B128>(&query_point);
377 let expected = iter::zip(table.iter_scalars(), monomials)
378 .map(|(t, m)| t * m)
379 .sum::<B128>();
380
381 let (query_k, query_j) = query_point.split_at(m_d);
382 assert_eq!(
383 libra_eval::<InfCube, B128>(&challenge_point, query_j, query_k, n_vars, degree),
384 expected,
385 "n_vars={n_vars}"
386 );
387 }
388 }
389
390 #[test]
391 fn infinity_round_polynomials_run_the_sumcheck() {
392 let mut rng = StdRng::seed_from_u64(0);
393 let (n_vars, degree) = (5, 2);
394 let (m_n, m_d) = mask_buffer_dimensions(n_vars, degree);
395 let buffer = random_field_buffer::<B128>(&mut rng, m_n + m_d);
396 let mask = Mask::new(n_vars, degree, buffer.as_view());
397
398 let mut claim = mask.sum_over_infinity_cube();
399 let mut challenges = Vec::new();
400 for _ in 0..n_vars {
401 let coeffs = mask.infinity_round_coeffs(&challenges);
402 assert_eq!(coeffs[0] + coeffs[degree], claim);
404 let challenge = B128::random(&mut rng);
405 claim = coeffs.evaluate(&challenge);
406 challenges.push(challenge);
407 }
408 challenges.reverse();
409 assert_eq!(mask.evaluate(&challenges), claim);
410 }
411}