binius_verifier/protocols/pubcheck.rs
1// Copyright 2025 Irreducible Inc.
2use std::iter;
3
4use binius_field::Field;
5use binius_ip::{mlecheck, sumcheck::SumcheckOutput};
6use binius_transcript::{VerifierTranscript, fiat_shamir::Challenger};
7
8use crate::error::Error;
9
10/// Output of [`verify`].
11#[derive(Debug)]
12pub struct VerifyOutput<F: Field> {
13 /// Evaluation of the (w - p) polynomial at `eval_point`.
14 pub eval: F,
15 /// Evaluation point from the MLE-check.
16 pub eval_point: Vec<F>,
17}
18
19/// Verify the public input check (pubcheck) protocol.
20///
21/// The pubcheck protocol argues that the witness multilinear agrees with the public input
22/// multilinear on a subdomain. The witness $w$ is $\ell$-variate, and the public multilinear $p$
23/// is $m$-variate, where $m \le \ell$. The interactive reduction argues that for all $v \in B_m$
24///
25/// $$
26/// w(v_0, \ldots, v_{m-1}, 0^{\ell - m}) = p(v_0, \ldots, v_{m-1})
27/// $$
28///
29/// The protocol is an MLE-check on the multilinear $w$, using a zero-padded challenge point. It
30/// begins with an $m$-dimensional challenge point $r$ and reduces to an MLE-check that
31/// $w(r || 0) = p(r)$.
32///
33/// ## Arguments
34///
35/// * `n_witness_vars` - base-2 logarithm of the number of witness words
36/// * `challenge` - the $m$-dimensional challenge point
37/// * `transcript` - the verifier's transcript
38///
39/// ## Preconditions
40///
41/// * `challenge.len()` is at most `n_witness_vars`
42pub fn verify<F: Field, Challenger_: Challenger>(
43 n_witness_vars: usize,
44 public_eval: F,
45 challenge: &[F],
46 transcript: &mut VerifierTranscript<Challenger_>,
47) -> Result<VerifyOutput<F>, Error> {
48 let n_public_vars = challenge.len();
49 assert!(n_public_vars <= n_witness_vars); // precondition
50
51 // The MLE-check verifier checks an evaluation at the zero-padded point.
52 let zero_padded_eval_point = itertools::chain(challenge.iter().copied(), iter::repeat(F::ZERO))
53 .take(n_witness_vars)
54 .collect::<Vec<_>>();
55
56 let SumcheckOutput {
57 eval,
58 mut challenges,
59 } = mlecheck::verify(
60 &zero_padded_eval_point,
61 1, // degree 1 for w multilinear
62 public_eval,
63 transcript,
64 )?;
65
66 // MLE-check expects prover to bind variables high-to-low, so reverse challenge order.
67 challenges.reverse();
68
69 Ok(VerifyOutput {
70 eval,
71 eval_point: challenges,
72 })
73}