Skip to main content

binius_ip_prover/
libra.rs

1// Copyright 2026 The Binius Developers
2
3//! The prover's Libra mask polynomial.
4//!
5//! See [`binius_ip::libra`] for the mask and its coefficient table.
6
7use 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
16/// Generates hypercube evaluations of the libra_eval polynomial.
17///
18/// For a mask polynomial with `n_vars` variables and `degree`, generates a `FieldBuffer`
19/// of size `2^(m_n + m_d)` containing:
20///
21/// ```text
22/// libra_eval_r(j, k) = r[j]^k  if j < n_vars and k ≤ degree
23///                    = 0       otherwise
24/// ```
25///
26/// where `j` and `k` are derived from the hypercube index: `idx = j * 2^m_d + k`.
27///
28/// # Arguments
29///
30/// * `alloc` - The allocator the expansion is drawn from
31/// * `challenge_point` - The challenge point `r` from sumcheck (length `n_vars`)
32/// * `n_vars` - Number of variables in the mask polynomial
33/// * `degree` - Degree of each univariate in the mask polynomial
34/// * `m_n` - Log of number of rows (must satisfy `2^m_n >= n_vars`)
35/// * `m_d` - Log of row size (must satisfy `2^m_d >= degree + 1`)
36///
37/// # Panics
38///
39/// Panics (in debug mode) if `n_vars > 2^m_n` or `degree + 1 > 2^m_d`.
40pub 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
66/// Libra mask polynomial for ZK MLE-check protocols.
67///
68/// Stores coefficients for a separable polynomial $g(X) = \sum_i g_i(X_i)$
69/// where each $g_i$ is a univariate polynomial of degree $d$.
70///
71/// The coefficients are stored in a `FieldBuffer` with `m_n + m_d` variables where:
72/// - `m_n = ceil(log2(n))` - log of number of variables
73/// - `m_d = ceil(log2(d + 1))` - log of degree + 1
74///
75/// The buffer is conceptually an `n × (d+1)` matrix padded to `2^m_n × 2^m_d`,
76/// with random values in the `n × (d+1)` submatrix and zeros elsewhere.
77///
78/// The type is generic over the buffer storage type `Data`, allowing it to work
79/// with both owned buffers (`Box<[P]>`) and borrowed slices.
80pub struct Mask<P: PackedField, Data: Deref<Target = [P]> = Box<[P]>> {
81	/// Number of variables (n)
82	n_vars: usize,
83	/// Degree of each univariate polynomial (d)
84	degree: usize,
85	/// Coefficients stored as a FieldBuffer with log_len = m_n + m_d.
86	/// Layout: row i contains the monomial coefficients [g_{i,0}, ..., g_{i,d}, 0, ..., 0].
87	/// Row i spans indices [i * 2^m_d, (i+1) * 2^m_d).
88	buffer: FieldBuffer<P, Data>,
89}
90
91impl<F: Field, P: PackedField<Scalar = F>, Data: Deref<Target = [P]>> Mask<P, Data> {
92	/// Creates a new mask polynomial from a pre-allocated buffer.
93	///
94	/// # Arguments
95	///
96	/// * `n_vars` - Number of variables (n).
97	/// * `degree` - Degree of each univariate polynomial (d).
98	/// * `buffer` - Buffer with log_len = m_n + m_d.
99	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	/// Returns the number of variables.
108	pub const fn n_vars(&self) -> usize {
109		self.n_vars
110	}
111
112	/// Returns the degree of each univariate polynomial.
113	pub const fn degree(&self) -> usize {
114		self.degree
115	}
116
117	/// Returns m_d = ceil(log2(degree + 1)).
118	const fn log_degree_plus_one(&self) -> usize {
119		(self.degree + 1).next_power_of_two().ilog2() as usize
120	}
121
122	/// Gets the coefficient $g_{i,j}$ (coefficient of $X^j$ in $g_i$).
123	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	/// Returns the monomial coefficients [g_{i,0}, g_{i,1}, ..., g_{i,d}] for variable i.
131	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	/// Evaluates g_i(x) for a specific variable using Horner's method.
140	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	/// Computes the MLE of the mask polynomial at a point.
146	///
147	/// For a mask polynomial $g(X) = \sum_i g_i(X_i)$ where each $g_i$ is univariate,
148	/// the MLE at point $z$ is:
149	///
150	/// $$
151	/// \sum_{v \in \{0,1\}^n} g(v) \cdot eq(v, z) = \sum_i [(1-z_i) g_i(0) + z_i g_i(1)]
152	/// $$
153	///
154	/// This simplification arises because $\sum_{v_j \in \{0,1\}} eq_1(v_j, z_j) = 1$.
155	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	/// Evaluates the mask polynomial $g(r) = \sum_i g_i(r_i)$.
168	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	/// The sum of $g_i$ over $\{0, \infty\}$: its constant plus its leading coefficient.
176	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	/// The sum $\sum_{x \in \{0, \infty\}^n} g(x)$.
181	///
182	/// Each $g_i$ is summed over its own coordinate, and every other coordinate contributes one.
183	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	/// The round polynomial of the sumcheck of $g$ over $\{0, \infty\}^n$, after the top variables
190	/// are bound to `challenges` in binding order.
191	///
192	/// The round's variable is $X_c$, $c = n - 1 - i$ in round $i$. The univariates above it are
193	/// evaluated at their challenges, those below are summed over $\{0, \infty\}$, and $g_c$ is
194	/// the round polynomial's non-constant part.
195	///
196	/// ## Preconditions
197	///
198	/// * `challenges.len() < n_vars`
199	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		// Create random mask buffer
246		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		// Create random challenge point
250		let challenge_point: Vec<B128> = random_scalars(&mut rng, n_vars);
251
252		// Compute g(r) using direct computation.evaluate()
253		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		// Compute <g', libra_eval_r> using inner product
259		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		// Create random mask buffer (g')
289		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		// Create random challenge point r
294		let challenge_point: Vec<B128> = random_scalars(&mut rng, n_vars);
295
296		// Generate libra_eval tensor
297		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		// Compute the claimed sum: <g', libra_eval_r> = g(r)
307		let claimed_sum = inner_product_par(&mask_buffer, &libra_eval_tensor);
308
309		// Create the bivariate product sumcheck prover
310		let prover =
311			bivariate_product_prover(&alloc, [mask_buffer.clone(), libra_eval_tensor], claimed_sum);
312
313		// Run the proving protocol
314		let mut prover_transcript = ProverTranscript::new(StdChallenger::default());
315		let output = prove_single(prover, &mut prover_transcript);
316
317		// Write the multilinear evaluations to the transcript
318		prover_transcript
319			.message()
320			.write_slice(&output.multilinear_evals);
321
322		// Verify with sumcheck verifier
323		let mut verifier_transcript = prover_transcript.into_verifier();
324		let sumcheck_output = verify(
325			log_size,
326			2, // degree 2 for bivariate product
327			claimed_sum,
328			&mut verifier_transcript,
329		)
330		.unwrap();
331
332		// Read the multilinear evaluations
333		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		// Check that the product equals the reduced evaluation
337		assert_eq!(g_prime_eval * libra_eval_out, sumcheck_output.eval);
338
339		// Verify libra_eval_out using libra_eval
340		// The sumcheck binds variables high-to-low, so we need to reverse to get low-to-high order
341		// In the buffer layout, the low-order bits encode k (first m_d variables) and
342		// high-order bits encode j (next m_n variables)
343		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		// Also verify g' evaluation directly
355		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			// R(0) + R(∞) is the constant plus the leading coefficient.
403			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}