binius_iop/basefold/
opening.rs

1// Copyright 2025 Irreducible Inc.
2// Copyright 2026 The Binius Developers
3
4//! The core BaseFold opening protocol on the verifier side.
5
6use binius_field::BinaryField;
7use binius_ip::{mlecheck, sumcheck::RoundCoeffs};
8use binius_utils::checked_arithmetics::log2_ceil_usize;
9
10use super::error::Error;
11use crate::{
12	fri::{FRIFoldVerifier, FRIParams, verify::FRIQueryVerifier},
13	merkle_channel::MerkleIPVerifierChannel,
14};
15
16/// Verifies a *combined* multilinear-evaluation BaseFold opening: a single degree-1 MLE-check
17/// interleaved with a single FRI over the piecewise-concatenated oracle of the Batched ZK BaseFold
18/// construction (whitepaper §7.2 / §sec:batched-basefold Step 2).
19///
20/// This is the verifier counterpart of
21/// `binius_iop_prover::basefold::prove_mlecheck_basefold`. A prior batched sumcheck has
22/// reduced the `k` masked opening claims to per-oracle point-evaluation claims `π_i'(ρ_i) = α_i` at
23/// a shared point `r ∈ K^𝐧` (`𝐧 = max_i n_i`). The oracle-index variables are then collapsed up
24/// front at sampled batching challenges `r'` into a single combined multilinear
25/// `𝛑(X) = Σ_i e[i] · π_i^↑(X)`, `e` the indicator expanded at `r'`, with target `s' = 𝛑(r)`; this
26/// routine checks `𝛑(r) = s'` against the `k` committed codewords via one combined FRI.
27///
28/// ## Arguments
29///
30/// * `codeword_commitments` - one per oracle, in the same order as [`FRIParams::input_oracles`], as
31///   commitment handles previously received over `channel` (via
32///   [`MerkleIPVerifierChannel::recv_merkle_commitment`]).
33/// * `eval_claim` - the combined target `s'`.
34/// * `eval_point` - the point `r` (length `𝐧 = fri_params.rs_code().log_dim()`), low-to-high order.
35/// * `batch_challenge` - the masking challenge `γ` used in the FRI inner (unbatch) round.
36/// * `outer_challenges` - the batching challenges `r'` (length `log_n_oracles`) used in the FRI
37///   outer (oracle-combine) rounds.
38/// * `channel` - the Merkle channel carrying all prover interaction: round coefficients,
39///   challenges, commitments, and query openings.
40///
41/// The final consistency check is asserted internally, so `Ok` means the opening verified.
42///
43/// The MLE-check folds the equality-indicator factor into its round-proof recovery.
44/// So the final reduced value is the plain multilinear evaluation of the combined oracle at `r`.
45/// On an honest opening that value equals the final FRI value.
46/// This routine asserts their equality and rejects on any mismatch.
47pub fn verify_mlecheck_basefold<F, Channel>(
48	fri_params: &FRIParams<F>,
49	codeword_commitments: &[Channel::Commitment],
50	eval_claim: Channel::Elem,
51	eval_point: &[Channel::Elem],
52	batch_challenge: Option<Channel::Elem>,
53	outer_challenges: &[Channel::Elem],
54	channel: &mut Channel,
55) -> Result<(), Error>
56where
57	F: BinaryField,
58	Channel: MerkleIPVerifierChannel<F>,
59	Channel::Elem: From<F>,
60{
61	// The MLE-check round polynomial is degree 1 (the composite is the multilinear itself).
62	const DEGREE: usize = 1;
63
64	let log_n_oracles = log2_ceil_usize(fri_params.input_oracles().len());
65	assert_eq!(outer_challenges.len(), log_n_oracles);
66
67	// The MLE-check runs over the combined opening's `𝐧 = max_i log_msg_len_i` variables, supplied
68	// as `eval_point`. For an all-ZK batch this equals `rs_code().log_dim()`; with non-ZK oracles
69	// it can exceed it, since those oracles fold their batch dimensions within the leading MLE
70	// rounds.
71	let n_vars = eval_point.len();
72
73	// `n_inner` inner (unbatch) rounds: one for the shared mask challenge γ when any ZK oracle is
74	// present, none otherwise.
75	let n_inner = usize::from(batch_challenge.is_some());
76	let mut challenges = Vec::with_capacity(n_vars + n_inner + log_n_oracles);
77	let mut fri_fold_verifier = FRIFoldVerifier::new(fri_params);
78
79	// Inner (unbatch) round: fold every interleaved (π_i ‖ ω_i) ZK codeword at the masking
80	// challenge.
81	if let Some(gamma) = batch_challenge {
82		fri_fold_verifier.process_round(channel)?;
83		challenges.push(gamma);
84	}
85
86	// Outer rounds: combine the `k` lifted codewords at the batching challenges `r'`. These carry
87	// no sumcheck round-polynomial (the oracle-index variables are collapsed deterministically).
88	// The first fold consumes its challenges as `[γ] ++ r' ++ fresh_X`, so the outer challenges are
89	// processed here (right after γ) to land in the outer window; the leading standard rounds then
90	// supply each non-ZK oracle's later batch fold.
91	for outer_challenge in outer_challenges {
92		fri_fold_verifier.process_round(channel)?;
93		challenges.push(outer_challenge.clone());
94	}
95
96	// Standard rounds: the only sumcheck (MLE-check) rounds, folding the combined codeword at the
97	// fresh challenges over the `𝐧` variables `X`.
98	let mut sum = eval_claim;
99	for round in 0..n_vars {
100		let round_proof = mlecheck::RoundProof(RoundCoeffs(channel.recv_many(DEGREE)?));
101		fri_fold_verifier.process_round(channel)?;
102
103		// MLE-check binds variables high-to-low, so round `i` uses coordinate `eval_point[n-1-i]`.
104		let alpha = eval_point[n_vars - 1 - round].clone();
105		let round_coeffs = round_proof.recover(sum, alpha);
106		let challenge = channel.sample();
107		sum = round_coeffs.evaluate(&challenge);
108		challenges.push(challenge);
109	}
110
111	fri_fold_verifier.process_round(channel)?;
112	let round_commitments = fri_fold_verifier.finalize();
113
114	let fri_verifier = FRIQueryVerifier::new_batch(
115		fri_params,
116		codeword_commitments,
117		&round_commitments,
118		&challenges,
119	);
120
121	let final_fri_value = fri_verifier.verify(channel)?;
122
123	// The MLE-check folds the equality-indicator factor into its round-proof recovery.
124	// So the final reduced value is the plain evaluation, identical to the final FRI value.
125	// Reject on any mismatch.
126	channel.assert_zero(sum - final_fri_value)?;
127
128	Ok(())
129}
binius_iop/basefold/opening.rs

binius_iop/basefold/
opening.rs
