binius_ip/
prodcheck.rs

1// Copyright 2025-2026 The Binius Developers
2
3//! Reduction from the products over the sumcubes of a multilinear to a multilinear evaluation.
4//!
5//! The reduction input is a multilinear $f(Z_0, \ldots, Z_{k-1}, X_0, \ldots, X_{n-1})$. The
6//! product polynomial is the multilinear
7//!
8//! $$
9//! p(X_0, \ldots, X_{n-1}) = \sum_{x \in B_n} \text{eq}(x ; X) \prod_{z \in B_k} f(z, x)
10//! $$
11//!
12//! This protocol is a GKR-based protocol with $k$ sumcheck invocations. We define a sequence of
13//! multilinears $p_0, \ldots, p_k$, where $p_k = f$ and for all $i < k$:
14//!
15//! $$
16//! p_i(Z_0, \ldots, Z_{i-1}, X_0, \ldots, X_{n-1}) = \sum_{x \in B_n} \sum_{z \in B_i} \text{eq}(x
17//! ; X) \text{eq}(z ; Z) p_{i+1}(z, 0, x) p_{i+1}(z, 1, x) $$
18
19use binius_field::Field;
20use binius_math::line::extrapolate_line;
21use binius_transcript::Error as TranscriptError;
22
23// Re-export MultilinearEvalClaim from crate root for backward compatibility
24pub use crate::MultilinearEvalClaim;
25use crate::{
26	channel::IPVerifierChannel,
27	mlecheck,
28	sumcheck::{self, SumcheckOutput},
29};
30
31pub fn verify<F, C>(
32	k: usize,
33	claim: MultilinearEvalClaim<C::Elem>,
34	channel: &mut C,
35) -> Result<MultilinearEvalClaim<C::Elem>, Error>
36where
37	F: Field,
38	C: IPVerifierChannel<F>,
39{
40	if k == 0 {
41		return Ok(claim);
42	}
43
44	let MultilinearEvalClaim { eval, point } = claim;
45
46	// Reduce p_i evaluation to two evaluations of p_{i+1}.
47	let SumcheckOutput { eval, challenges } = mlecheck::verify(&point, 2, eval, channel)?;
48
49	// Read evaluations of p_{i+1)(0, \ldots) and p_{i+1}(1, \ldots).
50	let [eval_0, eval_1] = channel.recv_array()?;
51
52	channel.assert_zero(eval_0.clone() * eval_1.clone() - eval)?;
53
54	// Reduce evaluations of p_{i+1}(0, \ldots) and p_{i+1}(1, \ldots) to single eval at
55	// p_{i+1}(r, \ldots).
56	let r = channel.sample();
57
58	let next_eval = extrapolate_line(eval_0, eval_1, r.clone());
59
60	let mut next_point = challenges;
61	next_point.reverse();
62	next_point.push(r);
63
64	verify(
65		k - 1,
66		MultilinearEvalClaim {
67			eval: next_eval,
68			point: next_point,
69		},
70		channel,
71	)
72}
73
74#[derive(Debug, thiserror::Error)]
75pub enum Error {
76	#[error("sumcheck error: {0}")]
77	Sumcheck(#[source] sumcheck::Error),
78	#[error("transcript error: {0}")]
79	Transcript(#[source] TranscriptError),
80	#[error("verification error: {0}")]
81	Verification(#[from] VerificationError),
82}
83
84impl From<sumcheck::Error> for Error {
85	fn from(err: sumcheck::Error) -> Self {
86		match err {
87			sumcheck::Error::Verification(err) => VerificationError::Sumcheck(err).into(),
88			_ => Error::Sumcheck(err),
89		}
90	}
91}
92
93impl From<TranscriptError> for Error {
94	fn from(err: TranscriptError) -> Self {
95		match err {
96			TranscriptError::NotEnoughBytes => VerificationError::TranscriptIsEmpty.into(),
97			_ => Error::Transcript(err),
98		}
99	}
100}
101
102impl From<crate::channel::Error> for Error {
103	fn from(err: crate::channel::Error) -> Self {
104		match err {
105			crate::channel::Error::ProofEmpty => VerificationError::TranscriptIsEmpty.into(),
106			crate::channel::Error::InvalidAssert => VerificationError::InvalidAssert.into(),
107		}
108	}
109}
110
111#[derive(Debug, thiserror::Error)]
112pub enum VerificationError {
113	#[error("sumcheck: {0}")]
114	Sumcheck(#[from] sumcheck::VerificationError),
115	#[error("incorrect round evaluation: {round}")]
116	IncorrectRoundEvaluation { round: usize },
117	#[error("transcript is empty")]
118	TranscriptIsEmpty,
119	#[error("invalid assertion: value is not zero")]
120	InvalidAssert,
121}
binius_ip/prodcheck.rs

binius_ip/
prodcheck.rs
