1use 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#[derive(Debug, Clone, Copy)]
27pub struct BaseFoldOracle {
28 round: usize,
30 block_offset: usize,
32 log_len: usize,
34}
35
36struct Operand<Elem> {
39 oracle: BaseFoldOracle,
40 transparent: TransparentEvalFn<Elem>,
41}
42
43struct Relation<Elem> {
46 claim: Elem,
47 operands: Vec<Operand<Elem>>,
48}
49
50pub struct BaseFoldVerifierChannel<'a, F, Channel>
62where
63 F: BinaryField,
64 Channel: MerkleIPVerifierChannel<F, Elem: From<F> + 'static>,
65{
66 channel: Channel,
69 schedule: &'a OracleSchedule,
70 layouts: &'a [RoundLayout],
71 fri_params: &'a FRIParams<F>,
72 oracle_commitments: Vec<Channel::Commitment>,
74 n_received: usize,
76 n_in_round: usize,
78 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 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 fn recv_round_commitment(&mut self) -> Result<(), Error> {
114 let index = self.oracle_commitments.len();
115 let layout = &self.layouts[index];
116 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 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 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
181fn 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 let n_vars = layouts
221 .iter()
222 .map(|layout| layout.log_len)
223 .max()
224 .expect("at least one oracle");
225
226 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 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 let multiplicand_eval = move |rho: &[Channel::Elem], zeta: &[Channel::Elem]| {
247 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 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 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 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}