binius_ip/mlecheck.rs
1// Copyright 2025 Irreducible Inc.
2// Copyright 2026 The Binius Developers
3
4use binius_field::{Field, field::FieldOps};
5
6use crate::{
7 channel::IPVerifierChannel,
8 sumcheck::{self, RoundCoeffs, SumcheckOutput},
9};
10
11/// Output of the zero-knowledge MLE-check verification.
12#[derive(Debug, Clone, PartialEq, Eq)]
13pub struct VerifyZKOutput<F> {
14 /// The reduced evaluation of the main polynomial at the challenge point.
15 pub eval: F,
16 /// The evaluation of the mask polynomial at the challenge point.
17 pub mask_eval: F,
18 /// The sequence of challenge values from each round.
19 pub challenges: Vec<F>,
20}
21
22/// An MLE-check protocol is an interactive protocol similar to sumcheck, but with modifications
23/// introduced in [Gruen24], Section 3.
24///
25/// The prover in an MLE-check argues a that for some $n$-variate polynomial
26/// $F(X_0, \ldots, X_{n-1})$ (which is not necessarily multilinear), for a given point
27/// $(z_0, \ldots, z_{n-1})$ and claimed value $s$, that
28///
29/// $$
30/// s = \sum_{v \in B_n} F(v) \cdot eq(v, z)
31/// $$
32///
33/// Unless $F$ is indeed multilinear, $s \ne F(z)$ necessarily. While the prover and verifier could
34/// engage in a standard sumcheck protocol to reduce this claim, it is concretely more efficient to
35/// use the optimized protocol from [Gruen24], which we call an "MLE-check".
36///
37/// [Gruen24]: <https://eprint.iacr.org/2024/108>
38///
39/// ## Arguments
40///
41/// * `point` - The evaluation point for the multilinear extension
42/// * `degree` - The degree of the univariate polynomial in each round
43/// * `eval` - The claimed multilinear-extension evaluation of the multivariate polynomial
44/// * `channel` - The channel for receiving prover messages and sampling challenges
45///
46/// ## Returns
47///
48/// Returns a `Result` containing the `SumcheckOutput` with the reduced evaluation and challenge
49/// point, or an error if verification fails.
50pub fn verify<F, C>(
51 point: &[C::Elem],
52 degree: usize,
53 mut eval: C::Elem,
54 channel: &mut C,
55) -> Result<SumcheckOutput<C::Elem>, sumcheck::Error>
56where
57 F: Field,
58 C: IPVerifierChannel<F>,
59{
60 let n_vars = point.len();
61
62 let mut challenges = Vec::with_capacity(n_vars);
63 for z_i in point.iter().rev() {
64 let round_proof = RoundProof(RoundCoeffs(channel.recv_many(degree)?));
65 let challenge = channel.sample();
66
67 let round_coeffs = round_proof.recover(eval, z_i.clone());
68 eval = round_coeffs.evaluate(&challenge);
69 challenges.push(challenge);
70 }
71
72 Ok(SumcheckOutput { eval, challenges })
73}
74
75/// Variation of the MLE-check protocol that provides the hiding property.
76///
77/// This protocol is based on the zero-knowledge sumcheck technique from [Libra], with a
78/// modification. When the field has characteristic 2, the Libra ZK-sumcheck protocol is not hiding.
79/// Instead, the mask polynomial $g$ is batched together with the multivariate polynomial whose MLE
80/// is being evaluated, whereas Libra would batch the mask polynomial together with the MLE itself.
81///
82/// [Libra]: <https://dl.acm.org/doi/10.1007/978-3-030-26954-8_24>
83pub fn verify_zk<F, C>(
84 point: &[C::Elem],
85 degree: usize,
86 eval: C::Elem,
87 channel: &mut C,
88) -> Result<VerifyZKOutput<C::Elem>, sumcheck::Error>
89where
90 F: Field,
91 C: IPVerifierChannel<F>,
92{
93 // Read the evaluation of the MLE of the mask polynomial (g).
94 let mask_eval = channel.recv_one()?;
95
96 // Randomly mix the evaluation claim with the mask evaluation claim.
97 let batch_challenge = channel.sample();
98 let batch_eval = eval + batch_challenge.clone() * mask_eval;
99
100 let SumcheckOutput {
101 eval: batch_eval_out,
102 challenges,
103 } = verify(point, degree, batch_eval, channel)?;
104
105 // Read the evaluation of the mask polynomial (g) at the sumcheck challenge point.
106 let mask_eval_out = channel.recv_one()?;
107
108 let eval_out = batch_eval_out - batch_challenge * mask_eval_out.clone();
109 Ok(VerifyZKOutput {
110 eval: eval_out,
111 mask_eval: mask_eval_out,
112 challenges,
113 })
114}
115
116/// An MLE-check round proof is a univariate polynomial in monomial basis with the coefficient of
117/// the lowest-degree term truncated off.
118///
119/// Since the verifier knows the claimed linear extrapolation of the polynomial values at the
120/// points 0 and 1, the low-degree term coefficient can be easily recovered. Truncating the
121/// coefficient off saves a small amount of proof data.
122///
123/// This is an analogous struct to [`sumcheck::RoundProof`], except that we truncate the low-degree
124/// coefficient instead of the high-degree coefficient.
125///
126/// In a sumcheck protocol, the verifier has a claimed sum $s$ and the round polynomial $R(X)$ must
127/// satisfy $R(0) + R(1) = s$. In an MLE-check protocol, the verifier has a claimed coordinate
128/// $\alpha$ and extrapolated value $s$ and the round polynomial must satisfy
129/// $(1 - \alpha) R(0) + \alpha R(1) = s$. This difference changes the recovery procedure and which
130/// polynomial coefficient is most convenient to truncate.
131#[derive(Debug, Default, Clone, PartialEq, Eq)]
132pub struct RoundProof<F>(pub RoundCoeffs<F>);
133
134impl<F> RoundProof<F> {
135 /// Truncates the polynomial coefficients to a round proof.
136 ///
137 /// Removes the first coefficient. See the struct documentation for more info.
138 ///
139 /// ## Pre-conditions
140 ///
141 /// * `coeffs` must not be empty
142 pub fn truncate(mut coeffs: RoundCoeffs<F>) -> Self {
143 coeffs.0.remove(0);
144 Self(coeffs)
145 }
146
147 /// Recovers all univariate polynomial coefficients from the compressed round proof.
148 ///
149 /// The prover has sent coefficients for the purported $i$'th round polynomial
150 /// $R(X) = \sum_{j=0}^d a_j * X^j$.
151 ///
152 /// However, the prover has not sent the lowest degree coefficient $a_0$. The verifier will
153 /// need to recover this missing coefficient.
154 ///
155 /// Let $s$ denote the current round's claimed sum and $\alpha_i$ be the $i$'th coordinate of
156 /// the evaluation point.
157 ///
158 /// The verifier expects the round polynomial $R_i$ to satisfy the identity
159 /// $s = (1 - \alpha) R(0) + \alpha R(1)$, or equivalently, $s = R(0) + (R(1) - R(0)) \alpha$.
160 ///
161 /// Using
162 /// $R(0) = a_0$
163 /// $R(1) = \sum_{j=0}^d a_j$
164 /// There is a unique $a_0$ that allows $R$ to satisfy the above identity. Specifically,
165 /// $a_0 = s - \alpha \sum_{j=1}^d a_j$.
166 pub fn recover(self, eval: F, alpha: F) -> RoundCoeffs<F>
167 where
168 F: FieldOps,
169 {
170 let Self(RoundCoeffs(mut coeffs)) = self;
171 let first_coeff = eval - alpha * coeffs.iter().cloned().sum::<F>();
172 coeffs.insert(0, first_coeff);
173 RoundCoeffs(coeffs)
174 }
175
176 /// The truncated polynomial coefficients.
177 pub fn coeffs(&self) -> &[F] {
178 &self.0.0
179 }
180}
181
182#[cfg(test)]
183mod tests {
184 use binius_field::{Random, arch::OptimalB128 as B128};
185 use binius_math::{line::extrapolate_line, test_utils::random_scalars};
186 use rand::prelude::*;
187
188 use super::*;
189
190 fn test_recover_with_degree<F: Field>(mut rng: impl Rng, alpha: F, degree: usize) {
191 let coeffs = RoundCoeffs(random_scalars(&mut rng, degree + 1));
192
193 let v0 = coeffs.evaluate(&F::ZERO);
194 let v1 = coeffs.evaluate(&F::ONE);
195 let eval = extrapolate_line(v0, v1, alpha);
196
197 let proof = RoundProof::truncate(coeffs.clone());
198 assert_eq!(proof.recover(eval, alpha), coeffs);
199 }
200
201 #[test]
202 fn test_recover() {
203 let mut rng = StdRng::seed_from_u64(0);
204 let alpha = B128::random(&mut rng);
205
206 for degree in 0..4 {
207 // Test with random coordinate
208 test_recover_with_degree(&mut rng, alpha, degree);
209
210 // Test edge case coordinate values
211 test_recover_with_degree(&mut rng, B128::ZERO, degree);
212 test_recover_with_degree(&mut rng, B128::ONE, degree);
213 }
214 }
215}