Skip to main content

binius_iop/basefold/
channel.rs

1// Copyright 2026 The Binius Developers
2
3//! BaseFold ZK implementation of the IOP verifier channel.
4
5use binius_core::word::Word;
6use binius_field::{BinaryField, FieldOps, util::powers};
7use binius_ip::channel::{IPVerifierChannel, WordIPVerifierChannel};
8use binius_math::{
9	line::extrapolate_line,
10	multilinear::eq::{eq_ind, eq_ind_partial_eval_scalars, eq_ind_zero},
11	univariate::evaluate_univariate,
12};
13use itertools::izip;
14
15use crate::{
16	basefold::{
17		self,
18		layout::{RoundLayout, zk_commit_point},
19	},
20	channel::{Error, IOPVerifierChannel, OracleSchedule, OracleSpec, TransparentEvalFn},
21	fri::FRIParams,
22	merkle_channel::MerkleIPVerifierChannel,
23};
24
25/// Oracle handle returned by [`BaseFoldVerifierChannel::recv_oracle`].
26#[derive(Debug, Clone, Copy)]
27pub struct BaseFoldOracle {
28	/// The round whose oracle this one is committed in.
29	round: usize,
30	/// The oracle's block within its round oracle, in units of its own length.
31	block_offset: usize,
32	/// The oracle's own `log_msg_len`.
33	log_len: usize,
34}
35
36/// One operand in a queued relation: an oracle and the transparent multilinear it is paired with,
37/// over the oracle's own variables.
38struct Operand<Elem> {
39	oracle: BaseFoldOracle,
40	transparent: TransparentEvalFn<Elem>,
41}
42
43/// A relation queued by [`IOPVerifierChannel::verify_multi_oracle_relation`]: its claim and the
44/// operands whose inner products with their oracles sum to it.
45struct Relation<Elem> {
46	claim: Elem,
47	operands: Vec<Operand<Elem>>,
48}
49
50/// A verifier channel that uses ZK BaseFold for all oracle commitments and openings.
51///
52/// Each round of the schedule is committed as one round oracle, laid out by
53/// [`layout_rounds`](basefold::layout::layout_rounds), whose commitment arrives with the round's
54/// last oracle. The opening runs over the round oracles.
55///
56/// # Type Parameters
57///
58/// - `'a`: Lifetime for borrowed references
59/// - `F`: The binary field type
60/// - `Channel`: The Merkle channel carrying all prover interaction
61pub struct BaseFoldVerifierChannel<'a, F, Channel>
62where
63	F: BinaryField,
64	Channel: MerkleIPVerifierChannel<F, Elem: From<F> + 'static>,
65{
66	/// The Merkle channel carrying all prover interaction: field elements, challenges,
67	/// commitments, and openings.
68	channel: Channel,
69	schedule: &'a OracleSchedule,
70	layouts: &'a [RoundLayout],
71	fri_params: &'a FRIParams<F>,
72	/// One commitment per round committed so far, so its length is also the open round's index.
73	oracle_commitments: Vec<Channel::Commitment>,
74	/// How many oracles have been received so far.
75	n_received: usize,
76	/// How many of the open round's oracles have been received so far.
77	n_in_round: usize,
78	/// The relations queued by [`IOPVerifierChannel::verify_multi_oracle_relation`], opened
79	/// together in [`Self::finish`].
80	relations: Vec<Relation<Channel::Elem>>,
81}
82
83impl<'a, F, Channel> BaseFoldVerifierChannel<'a, F, Channel>
84where
85	F: BinaryField,
86	Channel: MerkleIPVerifierChannel<F, Elem: From<F> + 'static>,
87{
88	/// Creates a new BaseFold ZK verifier channel over a Merkle channel from precomputed FRI
89	/// parameters.
90	///
91	/// The FRI parameters should already account for ZK (log_batch_size = 1, doubled message
92	/// length).
93	pub const fn new(
94		channel: Channel,
95		schedule: &'a OracleSchedule,
96		layouts: &'a [RoundLayout],
97		fri_params: &'a FRIParams<F>,
98	) -> Self {
99		Self {
100			channel,
101			schedule,
102			layouts,
103			fri_params,
104			oracle_commitments: Vec::new(),
105			n_received: 0,
106			n_in_round: 0,
107			relations: Vec::new(),
108		}
109	}
110
111	/// Receives the commitment to the next round oracle, the one at index
112	/// `oracle_commitments.len()`.
113	fn recv_round_commitment(&mut self) -> Result<(), Error> {
114		let index = self.oracle_commitments.len();
115		let layout = &self.layouts[index];
116		// Receive the commitment with its Merkle tree shape, matching the prover-side commit: the
117		// oracle's codeword has dimension `log_dim - log_lift` and one interleaved coset of
118		// `2^log_batch_size` scalars per leaf.
119		let fri_oracle = &self.fri_params.input_oracles()[index];
120		let depth = (self.fri_params.rs_code().log_dim() - fri_oracle.log_lift)
121			+ self.fri_params.rs_code().log_inv_rate();
122
123		// The committed message length implied by this shape is `log_batch_size + depth -
124		// log_inv_rate`; it must cover the round oracle plus, for a ZK one, the equal-length
125		// interleaved mask.
126		assert_eq!(
127			fri_oracle.log_batch_size() + depth - self.fri_params.rs_code().log_inv_rate(),
128			layout.log_len + usize::from(layout.is_zk),
129			"invariant: the FRI commitment shape must be consistent with the round oracle's length"
130		);
131
132		let commitment = self
133			.channel
134			.recv_merkle_commitment(1 << fri_oracle.log_batch_size(), depth)?;
135
136		self.oracle_commitments.push(commitment);
137
138		Ok(())
139	}
140
141	/// Consumes the channel and verifies the single combined opening over **all** committed
142	/// oracles.
143	///
144	/// All oracle relations queued by
145	/// [`verify_multi_oracle_relation`](IOPVerifierChannel::verify_multi_oracle_relation) across
146	/// every call are processed here in one batch: batching into one relation, then one BaseFold
147	/// sumcheck opening over every committed oracle (in oracle-index order). Because the whole
148	/// opening is deferred to this point, every oracle is committed, so the precomputed combined
149	/// `FRIParams` (`optimal_for_batch` over all oracle specs) serves the opening.
150	///
151	/// Returns the Merkle channel, so a caller can still reach what it accumulated.
152	pub fn finish(self) -> Result<Channel, Error> {
153		let n_remaining = self.schedule.specs().len() - self.n_received;
154		assert!(n_remaining == 0, "finish called but {n_remaining} oracle specs remaining",);
155
156		let Self {
157			mut channel,
158			schedule: _,
159			layouts,
160			fri_params,
161			oracle_commitments,
162			n_received: _,
163			n_in_round: _,
164			relations,
165		} = self;
166
167		if !relations.is_empty() {
168			verify_batch_zk_basefold(
169				&mut channel,
170				layouts,
171				fri_params,
172				&oracle_commitments,
173				relations,
174			)?;
175		}
176
177		Ok(channel)
178	}
179}
180
181/// Verifies the combined ZK BaseFold opening over all committed round oracles.
182///
183/// This drives `channel` — the Merkle channel taken from the destructured
184/// [`BaseFoldVerifierChannel`] — through its [`MerkleIPVerifierChannel`] interface, in the steps of
185/// binius.xyz#128, "Batched ZK BaseFold opening":
186///
187/// 1. Batch the queued relations into `T_r = Σ_j μ^j t_{j,r}` and `s = Σ_j μ^j s_j`.
188/// 2. If some round is masked, receive the mask claim `s' = Σ_r <ω_r, T_r>`.
189/// 3. Sample the mask fold γ and take the target `lerp(γ, s, s')`. An unmasked round has `ω_r =
190///    M_r`, so folding it is a no-op.
191/// 4. Run one BaseFold sumcheck on `<G, T>` with `G(X, Z) = Σ_r M^γ_r↑(X) · eq(r, Z)` and `T(X, Z)
192///    = Σ_r T_r↑(X) · eq(r, Z)`. The final point `(ρ, ζ)` has `T(ρ, ζ)` evaluated here from the
193///    operand closures.
194///
195/// With no masked round there is no mask claim and no γ, and the target is `s`.
196///
197/// `T_r↑` is `T_r` placed at the origin of the opening's variables: its value at `ρ` is that of
198/// `T_r` at the last `ℓ_r` coordinates, times `eq(0, ρ_{<n-ℓ_r})`, where `ρ` is the challenges in
199/// binding order. The sum of `M_r↑ · T_r↑` over
200/// `X` is then `<M_r, T_r>` however `M_r↑` is lifted and repeated by the FRI.
201///
202/// A ZK round is committed reversed by [`zk_commit_index`](basefold::layout::zk_commit_index),
203/// which puts its ZK pad on the lowest coefficients of its codeword. `M_r` and `T_r` above are then
204/// the reversed tables, and the last `ℓ_r` coordinates of `ρ` map to the point over the round's
205/// own coordinates through [`zk_commit_point`]. The inner product, and so the claim, is unchanged.
206fn verify_batch_zk_basefold<F, Channel>(
207	channel: &mut Channel,
208	layouts: &[RoundLayout],
209	fri_params: &FRIParams<F>,
210	oracle_commitments: &[Channel::Commitment],
211	relations: Vec<Relation<Channel::Elem>>,
212) -> Result<(), Error>
213where
214	F: BinaryField,
215	Channel: MerkleIPVerifierChannel<F, Elem: From<F> + 'static>,
216{
217	assert_eq!(layouts.len(), oracle_commitments.len());
218
219	// `ℓ = max_r ℓ_r`, the variable count of the opening.
220	let n_vars = layouts
221		.iter()
222		.map(|layout| layout.log_len)
223		.max()
224		.expect("at least one oracle");
225
226	// Batch the relations at one sampled μ: the combined claim is `s = Σ_j μ^j · s_j`.
227	let mu = channel.sample();
228	let claims = relations
229		.iter()
230		.map(|relation| relation.claim.clone())
231		.collect::<Vec<_>>();
232	let claim = evaluate_univariate(&claims, &mu);
233
234	// A masked opening receives the mask claim and folds with γ.
235	let (target, gamma) = if layouts.iter().any(|layout| layout.is_zk) {
236		let s_prime = channel.recv_one()?;
237		let gamma = channel.sample();
238		(extrapolate_line(claim, s_prime, gamma.clone()), Some(gamma))
239	} else {
240		(claim, None)
241	};
242
243	// `T_r(ρ) = Σ_j μ^j Σ_{operands of relation j on round r} t(ρ_{<ℓ_o}) · eq(b, ρ_{ℓ_o..ℓ_r})`.
244	// On the round oracle, an operand is the oracle's own transparent `t` over its low variables,
245	// and zero outside its block `b` over the high ones.
246	let multiplicand_eval = move |rho: &[Channel::Elem], zeta: &[Channel::Elem]| {
247		// Each round's point over `M_r`, the last `ℓ_r` challenges in binding order. A ZK round is
248		// committed reversed, so the point over its committed table maps to `M_r` through
249		// `zk_commit_point`.
250		let round_points = layouts
251			.iter()
252			.map(|layout| {
253				let point = &rho[n_vars - layout.log_len..];
254				if layout.is_zk {
255					zk_commit_point(point)
256				} else {
257					point.to_vec()
258				}
259			})
260			.collect::<Vec<_>>();
261
262		let mut round_evals = vec![Channel::Elem::zero(); layouts.len()];
263		for (mu_j, relation) in izip!(powers(mu), &relations) {
264			for Operand {
265				oracle,
266				transparent,
267			} in &relation.operands
268			{
269				let (low, high) = round_points[oracle.round].split_at(oracle.log_len);
270				let block_bits = (0..high.len())
271					.map(|bit| {
272						if (oracle.block_offset >> bit) & 1 == 1 {
273							Channel::Elem::one()
274						} else {
275							Channel::Elem::zero()
276						}
277					})
278					.collect::<Vec<_>>();
279				round_evals[oracle.round] +=
280					mu_j.clone() * eq_ind(high, &block_bits) * transparent(low);
281			}
282		}
283
284		let eq_tensor = eq_ind_partial_eval_scalars(zeta);
285		izip!(round_evals, layouts, eq_tensor)
286			.map(|(eval, layout, eq_r)| eq_r * eval * eq_ind_zero(&rho[..n_vars - layout.log_len]))
287			.sum::<Channel::Elem>()
288	};
289
290	basefold::verify_sumcheck_basefold(
291		fri_params,
292		oracle_commitments,
293		target,
294		n_vars,
295		gamma,
296		multiplicand_eval,
297		channel,
298	)?;
299
300	Ok(())
301}
302
303impl<F, Channel> IPVerifierChannel<F> for BaseFoldVerifierChannel<'_, F, Channel>
304where
305	F: BinaryField,
306	Channel: MerkleIPVerifierChannel<F, Elem: From<F> + 'static>,
307{
308	type Elem = Channel::Elem;
309
310	fn recv_one(&mut self) -> Result<Self::Elem, binius_ip::channel::Error> {
311		self.channel.recv_one()
312	}
313
314	fn recv_many(&mut self, n: usize) -> Result<Vec<Self::Elem>, binius_ip::channel::Error> {
315		self.channel.recv_many(n)
316	}
317
318	fn recv_array<const N: usize>(&mut self) -> Result<[Self::Elem; N], binius_ip::channel::Error> {
319		self.channel.recv_array()
320	}
321
322	fn recv_public_claim(&mut self) -> Result<Self::Elem, binius_ip::channel::Error> {
323		self.channel.recv_public_claim()
324	}
325
326	fn sample(&mut self) -> Self::Elem {
327		self.channel.sample()
328	}
329
330	fn observe_one(&mut self, val: F) -> Self::Elem {
331		self.channel.observe_one(val)
332	}
333
334	fn observe_many(&mut self, vals: &[F]) -> Vec<Self::Elem> {
335		self.channel.observe_many(vals)
336	}
337
338	fn assert_zero(&mut self, val: Self::Elem) -> Result<(), binius_ip::channel::Error> {
339		self.channel.assert_zero(val)
340	}
341}
342
343impl<F, Channel> WordIPVerifierChannel<F> for BaseFoldVerifierChannel<'_, F, Channel>
344where
345	F: BinaryField,
346	Channel: MerkleIPVerifierChannel<F, Elem: From<F> + 'static>,
347{
348	type Word = Channel::Word;
349
350	fn observe_words(&mut self, words: &[Word]) -> Vec<Self::Word> {
351		self.channel.observe_words(words)
352	}
353
354	fn subset_sum(&mut self, elems: &[Self::Elem], word: &Self::Word) -> Self::Elem {
355		self.channel.subset_sum(elems, word)
356	}
357
358	fn select(&mut self, elems: &[Self::Elem], word: &Self::Word) -> Self::Elem {
359		self.channel.select(elems, word)
360	}
361
362	fn sample_bits(&mut self, bits: usize) -> Self::Word {
363		self.channel.sample_bits(bits)
364	}
365
366	fn pack_words(&mut self, words: &[Self::Word]) -> Vec<Self::Elem> {
367		self.channel.pack_words(words)
368	}
369}
370
371impl<'a, F, Channel> IOPVerifierChannel<F> for BaseFoldVerifierChannel<'a, F, Channel>
372where
373	F: BinaryField,
374	Channel: MerkleIPVerifierChannel<F, Elem: From<F> + 'static>,
375{
376	type Oracle = BaseFoldOracle;
377
378	fn remaining_oracle_specs(&self) -> &[OracleSpec] {
379		&self.schedule.specs()[self.n_received..]
380	}
381
382	fn recv_oracle(
383		&mut self,
384		len: usize,
385		is_witness_dependent: bool,
386	) -> Result<Self::Oracle, Error> {
387		let spec = *self
388			.remaining_oracle_specs()
389			.first()
390			.expect("recv_oracle called but no remaining oracle specs");
391		assert_eq!(len, spec.len, "oracle content length must match its spec");
392		// A spec is zero-knowledge iff the protocol is and the oracle is witness-dependent. The
393		// protocol-level flag is not known here, so only one direction can be checked.
394		assert!(
395			!spec.is_zk || is_witness_dependent,
396			"a zero-knowledge oracle spec must be received as witness-dependent"
397		);
398
399		let index = self.oracle_commitments.len();
400		let layout = &self.layouts[index];
401		let oracle = BaseFoldOracle {
402			round: index,
403			block_offset: layout.block_offsets[self.n_in_round],
404			log_len: spec.log_msg_len(),
405		};
406		self.n_received += 1;
407		self.n_in_round += 1;
408
409		// The round's last oracle brings the commitment to the whole round oracle.
410		if self.n_in_round < layout.block_offsets.len() {
411			return Ok(oracle);
412		}
413		self.n_in_round = 0;
414
415		self.recv_round_commitment()?;
416
417		Ok(oracle)
418	}
419
420	fn verify_multi_oracle_relation(
421		&mut self,
422		operands: impl IntoIterator<Item = (Self::Oracle, TransparentEvalFn<Self::Elem>)>,
423		claim: Self::Elem,
424	) -> Result<(), Error> {
425		// Queue the relation; the actual opening (sumchecks + combined
426		// FRI) happens once, over all committed round oracles, in [`Self::finish`].
427		let n_committed = self.oracle_commitments.len();
428		let operands = operands
429			.into_iter()
430			.map(|(oracle, transparent)| {
431				assert!(
432					oracle.round < n_committed,
433					"oracle's round {} is not committed yet",
434					oracle.round
435				);
436				Operand {
437					oracle,
438					transparent,
439				}
440			})
441			.collect();
442		self.relations.push(Relation { claim, operands });
443		Ok(())
444	}
445}