binius_ip/libra.rs
1// Copyright 2026 The Binius Developers
2
3//! The Libra mask polynomial and its committed coefficient table.
4//!
5//! A Libra mask on $n$ variables is the separable polynomial $g(X) = \sum_i g_i(X_i)$, each $g_i$ a
6//! univariate of degree $d$. Its coefficients are committed as a table $g'$ of
7//! $2^{m_n} \times 2^{m_d}$ entries, row $j$ holding the coefficients of $g_j$, so that
8//! $g(r) = \langle g', \textsf{libra-eval}_r \rangle$ is a linear query on the committed table.
9
10use binius_field::{field::FieldOps, util::powers};
11use binius_math::multilinear::hypercube::{Hypercube, eq_ind_partial_eval_scalars};
12
13/// Returns `(m_n, m_d)` dimensions for a mask polynomial buffer.
14///
15/// The ZK MLE-check protocol uses a separable mask polynomial with `n_vars` univariate polynomials,
16/// each of degree `d`. The mask coefficients are stored in a `2^m_n × 2^m_d` matrix where:
17/// - `m_n`: log of number of rows (one per variable, padded to power of two)
18/// - `m_d`: log of row size (degree + 1 coefficients, padded to power of two)
19///
20/// The protocol imposes `n * d + 1` linear constraints on the coefficients, so `m_n` is chosen
21/// such that `2^(m_n + m_d) >= n * d + 1`.
22///
23/// # Arguments
24///
25/// * `n_vars` - Number of variables (n).
26/// * `degree` - Degree of each univariate polynomial (d).
27///
28/// # Returns
29///
30/// A tuple `(m_n, m_d)` where the total mask buffer size is `2^(m_n + m_d)`.
31pub fn mask_buffer_dimensions(n_vars: usize, degree: usize) -> (usize, usize) {
32 let min_buffer_size = n_vars * degree + 1;
33 let m_d = (degree + 1).next_power_of_two().ilog2() as usize;
34 // m_n must be large enough to hold n_vars rows AND satisfy the DOF constraint
35 let m_n_for_vars = n_vars.next_power_of_two().ilog2() as usize;
36 let m_n_for_size = (min_buffer_size.next_power_of_two().ilog2() as usize).saturating_sub(m_d);
37 let m_n = m_n_for_vars.max(m_n_for_size);
38 (m_n, m_d)
39}
40
41/// Evaluates the multilinear with coefficients `libra_eval_r` over `Cube` at a query point.
42///
43/// Computes, at the query point `(query_j, query_k)`,
44///
45/// ```text
46/// Σⱼ Σₖ eq(j, query_j) · eq(k, query_k) · r[j]^k
47/// ```
48///
49/// for `j < n_vars` and `k ≤ degree`, where `eq` is `Cube`'s equality indicator. Over
50/// [`OneCube`](binius_math::multilinear::hypercube::OneCube) this is the multilinear extension of
51/// the table; over [`InfCube`](binius_math::multilinear::hypercube::InfCube) it is the multilinear
52/// whose monomial coefficients are the table.
53///
54/// # Arguments
55///
56/// * `challenge_point` - The challenge point `r` from sumcheck (length `n_vars`)
57/// * `query_j` - Query point for the variable index (length `m_n`)
58/// * `query_k` - Query point for the power index (length `m_d`)
59/// * `n_vars` - Number of variables in the mask polynomial
60/// * `degree` - Degree of each univariate in the mask polynomial
61pub fn libra_eval<Cube: Hypercube, F: FieldOps>(
62 challenge_point: &[F],
63 query_j: &[F],
64 query_k: &[F],
65 n_vars: usize,
66 degree: usize,
67) -> F {
68 let eq_j = eq_ind_partial_eval_scalars::<Cube, F>(query_j);
69 let eq_k = eq_ind_partial_eval_scalars::<Cube, F>(query_k);
70
71 eq_j.iter()
72 .take(n_vars)
73 .zip(challenge_point)
74 .map(|(eq_j_val, r_j)| {
75 eq_k.iter()
76 .take(degree + 1)
77 .zip(powers(r_j.clone()))
78 .map(|(eq_k_val, r_j_power)| eq_j_val.clone() * eq_k_val.clone() * r_j_power)
79 .sum::<F>()
80 })
81 .sum()
82}