binius_iop/fri/common.rs
1// Copyright 2024-2025 Irreducible Inc.
2// Copyright 2026 The Binius Developers
3
4use std::marker::PhantomData;
5
6use binius_field::{BinaryField, Field};
7use binius_math::reed_solomon::ReedSolomonCode;
8use binius_utils::checked_arithmetics::log2_ceil_usize;
9use getset::{CopyGetters, Getters};
10
11use crate::{channel::OracleSpec, merkle_tree::MerkleTreeScheme};
12
13/// Parameters for an FRI interleaved code proximity protocol.
14///
15/// ## Invariants
16///
17/// The dimension of the first-round (reduced) FRI oracle is
18/// `rs_code.log_dim() == log_terminal_dim + sum(fold_arities)`. For all oracle specs in
19/// `input_oracles`:
20/// - `log_batch_size <= log_msg_len`
21/// - `log_msg_len <= rs_code.log_dim() + log_batch_size` (equivalently, `log_msg_len <=
22/// log_terminal_dim + sum(fold_arities) + log_batch_size`)
23#[derive(Debug, Clone, Getters, CopyGetters)]
24pub struct FRIParams<F> {
25 /// The Reed-Solomon code the verifier is testing proximity to.
26 #[getset(get = "pub")]
27 rs_code: ReedSolomonCode<F>,
28 /// Guaranteed to be non-empty.
29 input_oracles: Vec<CodewordSpec>,
30 /// log2 the maximum message length of all input oracles, after lifting each to the reduced
31 /// dimension. Equals `rs_code.log_dim() + max_early + max_later`, where `max_early` (resp.
32 /// `max_later`) is the maximum `log_early_batch_size` (resp. `log_later_batch_size`) over the
33 /// input oracles (the within-oracle batch challenges the first fold must draw).
34 max_log_msg_len: usize,
35 /// log2 ceiling of the number of input oracles.
36 log_n_oracles: usize,
37 /// The reduction arities between each oracle sent to the verifier.
38 fold_arities: Vec<usize>,
39 /// log2 the dimension of the terminal codeword.
40 log_terminal_dim: usize,
41 /// The number oracle consistency queries required during the query phase.
42 #[getset(get_copy = "pub")]
43 n_test_queries: usize,
44}
45
46/// Specification of one committed codeword batched into the first-round FRI oracle.
47///
48/// Each input oracle commits an interleaved Reed–Solomon codeword whose own dimension is
49/// `rs_code.log_dim() - log_lift`; it is lifted to the shared reduced dimension by duplicating
50/// each entry `2^log_lift` times before the oracles are batched together. This is distinct from
51/// [`crate::channel::OracleSpec`], the higher-level description of an oracle to be committed (its
52/// message length and whether it is masked); a `CodewordSpec` is the resolved, FRI-level layout
53/// the [`FRIParams`] selection computes from a batch of those.
54#[derive(Debug, Clone)]
55pub struct CodewordSpec {
56 /// log2 the number of times each committed codeword entry is duplicated to lift it to the
57 /// shared first-round (reduced) dimension.
58 ///
59 /// The committed codeword's Reed–Solomon dimension is `rs_code.log_dim() - log_lift`, so its
60 /// message length is `rs_code.log_dim() - log_lift + log_batch_size`. It is `0` when the
61 /// oracle already sits at the reduced dimension.
62 pub log_lift: usize,
63 /// log2 the number of *early* batch-fold challenges this oracle's interleaving folds with.
64 ///
65 /// The first fold draws its within-oracle batch challenges in two groups: `max_early =
66 /// max(log_early_batch_size)` *early* challenges, sampled before the `log_n_oracles` outer
67 /// (oracle-combine) challenges, followed by `max_later = max(log_later_batch_size)` *later*
68 /// challenges, sampled after them. The full first-fold challenge slice is therefore
69 /// `[early (max_early)] ++ [outer (log_n_oracles)] ++ [later (max_later)]`.
70 ///
71 /// Oracle `i` folds its interleaving with the concatenation `early_window ++ later_window`,
72 /// where `early_window` is the `log_early_batch_size`-length *suffix* of the early challenges
73 /// and `later_window` is the `log_later_batch_size`-length *suffix* of the later challenges.
74 /// The early group carries the shared masking challenge γ of ZK BaseFold oracles (each such
75 /// oracle is purely early, `log_later_batch_size == 0`); the later group carries the non-ZK
76 /// oracles' flexible batch folds (each such oracle is purely later, `log_early_batch_size ==
77 /// 0`). The total interleave batch size of an oracle is `log_early_batch_size +
78 /// log_later_batch_size` (see [`Self::log_batch_size`]).
79 pub log_early_batch_size: usize,
80 /// log2 the number of *later* batch-fold challenges this oracle's interleaving folds with,
81 /// sampled after the outer (oracle-combine) challenges. See [`Self::log_early_batch_size`].
82 pub log_later_batch_size: usize,
83}
84
85impl CodewordSpec {
86 /// log2 the interleaved batch size: the early plus the later batch challenges.
87 pub const fn log_batch_size(&self) -> usize {
88 self.log_early_batch_size + self.log_later_batch_size
89 }
90}
91
92impl<F> FRIParams<F>
93where
94 F: BinaryField,
95{
96 /// ## Preconditions
97 ///
98 /// * `sum(fold_arities)` must be at most `rs_code.log_dim()`.
99 pub fn new(
100 rs_code: ReedSolomonCode<F>,
101 log_batch_size: usize,
102 fold_arities: Vec<usize>,
103 n_test_queries: usize,
104 ) -> Self {
105 // A single oracle already sits at the reduced dimension (no lifting) and is non-ZK /
106 // homogeneous: its whole batch is "later" (with `log_n_oracles == 0` there is no outer
107 // group between early and later, so this is identical to the old prefix convention).
108 let oracle_spec = CodewordSpec {
109 log_lift: 0,
110 log_early_batch_size: 0,
111 log_later_batch_size: log_batch_size,
112 };
113 Self::new_batch(rs_code, vec![oracle_spec], fold_arities, n_test_queries)
114 }
115
116 /// Create parameters for a batch of committed codewords with an explicit per-codeword layout.
117 ///
118 /// This is the low-level constructor: the caller supplies the reduced Reed–Solomon code, each
119 /// codeword's lift / early & later batch-fold routing, and the fold arities. The
120 /// proof-size-minimizing selection of those values from a batch of higher-level oracle
121 /// descriptions lives in [`Self::optimal_for_batch`].
122 ///
123 /// ## Preconditions
124 ///
125 /// * `oracles` is non-empty.
126 /// * `sum(fold_arities)` must be at most `rs_code.log_dim()`.
127 /// * For each oracle, `log_lift <= rs_code.log_dim()`.
128 pub fn new_batch(
129 rs_code: ReedSolomonCode<F>,
130 oracles: Vec<CodewordSpec>,
131 fold_arities: Vec<usize>,
132 n_test_queries: usize,
133 ) -> Self {
134 assert!(!oracles.is_empty(), "precondition: oracles must be non-empty");
135
136 let fold_arities_sum = fold_arities.iter().sum();
137 let log_terminal_dim = rs_code
138 .log_dim()
139 .checked_sub(fold_arities_sum)
140 .expect("precondition: sum(fold_arities) must be at most rs_code.log_dim()");
141
142 let log_n_oracles = log2_ceil_usize(oracles.len());
143
144 // The first fold draws its within-oracle batch challenges as `max_early` early challenges
145 // followed (after the `log_n_oracles` outer oracle-combine folds) by `max_later` later
146 // challenges, so the full first-fold slice is `[early ++ outer ++ later]`. The lifted
147 // message length each oracle reaches is `rs_code.log_dim() + max_early + max_later`.
148 let max_early = oracles
149 .iter()
150 .map(|spec| spec.log_early_batch_size)
151 .max()
152 .expect("oracles is non-empty");
153 let max_later = oracles
154 .iter()
155 .map(|spec| spec.log_later_batch_size)
156 .max()
157 .expect("oracles is non-empty");
158 let max_log_msg_len = rs_code.log_dim() + max_early + max_later;
159
160 Self {
161 rs_code,
162 input_oracles: oracles,
163 max_log_msg_len,
164 log_n_oracles,
165 fold_arities,
166 log_terminal_dim,
167 n_test_queries,
168 }
169 }
170
171 /// Create parameters for a batch of input oracles, minimizing the estimated proof size.
172 ///
173 /// The input oracles may have differing message lengths. Each oracle is reduced into a common
174 /// first-round FRI oracle, whose dimension is chosen to minimize the estimated proof size; the
175 /// per-oracle batch sizes and the subsequent fold arities are chosen along with it.
176 ///
177 /// Returns the parameters together with the estimated proof size in bytes.
178 ///
179 /// ## Arguments
180 ///
181 /// * `merkle_scheme` - the Merkle tree scheme used for commitments.
182 /// * `oracles` - the oracles to batch. A ZK oracle commits its message interleaved with an
183 /// equal-length mask (fixed `log_batch_size = 1`); a non-ZK oracle commits the bare message
184 /// with a batch size chosen optimally.
185 /// * `log_inv_rate` - the binary logarithm of the inverse Reed–Solomon code rate.
186 /// * `n_test_queries` - the number of test queries for the FRI protocol.
187 ///
188 /// ## Preconditions
189 ///
190 /// * `oracles` is non-empty.
191 pub fn optimal_for_batch<MerkleScheme>(
192 merkle_scheme: &MerkleScheme,
193 oracles: &[OracleSpec],
194 log_inv_rate: usize,
195 n_test_queries: usize,
196 ) -> (Self, usize)
197 where
198 MerkleScheme: MerkleTreeScheme<F>,
199 {
200 assert!(!oracles.is_empty()); // precondition
201
202 let ChooseCodewordSpecsOutput {
203 proof_size,
204 reduced_log_dim,
205 oracle_specs,
206 fold_arities,
207 } = choose_codeword_specs_for_oracles(merkle_scheme, oracles, log_inv_rate, n_test_queries);
208
209 let rs_code = ReedSolomonCode::new(reduced_log_dim, log_inv_rate);
210
211 let params = Self::new_batch(rs_code, oracle_specs, fold_arities, n_test_queries);
212 (params, proof_size)
213 }
214
215 /// Number of folding rounds in the FRI protocol.
216 ///
217 /// This is the largest input message length, plus `log_n_oracles` extra rounds that fold the
218 /// distinct input oracles together into the batched codeword.
219 pub const fn n_fold_rounds(&self) -> usize {
220 self.max_log_msg_len + self.log_n_oracles
221 }
222
223 /// Number of oracles sent during the fold rounds.
224 pub const fn n_oracles(&self) -> usize {
225 // One for the batched codeword commitment, and one for each subsequent one.
226 1 + self.fold_arities.len()
227 }
228
229 /// Number of bits in the query indices sampled during the query phase.
230 pub const fn index_bits(&self) -> usize {
231 self.rs_code.log_len()
232 }
233
234 /// Number of folding challenges the verifier sends after receiving the last oracle.
235 pub const fn n_final_challenges(&self) -> usize {
236 self.log_terminal_dim
237 }
238
239 /// The reduction arities between each oracle sent to the verifier.
240 pub fn fold_arities(&self) -> &[usize] {
241 &self.fold_arities
242 }
243
244 /// The specifications of the input oracles batched into the first-round FRI oracle.
245 pub fn input_oracles(&self) -> &[CodewordSpec] {
246 &self.input_oracles
247 }
248
249 /// The arity of the reduction to the first round oracle.
250 pub fn log_batch_size(&self) -> usize {
251 self.log_msg_len() - self.rs_code().log_dim()
252 }
253
254 /// The binary logarithm of the length of the initial oracle.
255 pub fn log_len(&self) -> usize {
256 self.log_msg_len() + self.rs_code().log_inv_rate()
257 }
258
259 /// The binary logarithm of the length of the initial message.
260 ///
261 /// This includes the `log_n_oracles` extra rounds used to fold the distinct input oracles
262 /// together, so it equals [`Self::n_fold_rounds`].
263 pub const fn log_msg_len(&self) -> usize {
264 self.max_log_msg_len + self.log_n_oracles
265 }
266}
267
268struct ChooseBatchSizeAndAritiesOutput {
269 proof_size: usize,
270 reduced_log_dim: usize,
271 fold_arities: Vec<usize>,
272}
273
274/// Choose the shared reduced dimension, fold arities, and resulting proof size for a batch of
275/// oracles, given each oracle's committed message length and (optionally fixed) batch size.
276///
277/// This is unaware of ZK: an oracle with a fixed `log_batch_size` (`Some`) has its batch size
278/// pinned by the caller, while an oracle with `None` takes a flexible batch size, decided here to
279/// reduce it to the shared dimension. For all input oracles we need their log_batch_size <=
280/// committed message length and committed message length <= reduced_log_dim + log_batch_size. We
281/// allow the committed message length to be less than reduced_log_dim + log_batch_size because we
282/// can lift Reed-Solomon encoded oracles.
283///
284/// `committed`: per oracle, its committed message length and its fixed log_batch_size (`Some`), or
285/// `None` for a flexible batch size.
286fn choose_batch_size_and_arities_multi<F, MerkleScheme>(
287 merkle_scheme: &MerkleScheme,
288 committed: &[(usize, Option<usize>)],
289 log_inv_rate: usize,
290 n_test_queries: usize,
291) -> ChooseBatchSizeAndAritiesOutput
292where
293 F: BinaryField,
294 MerkleScheme: MerkleTreeScheme<F>,
295{
296 // First, figure out lower and upper bounds on the reduced_log_dim. If there are any input
297 // oracles with a fixed log_batch_size, then their dimension lower bounds the reduced oracle
298 // dimension.
299 let min_reduced_log_dim = committed
300 .iter()
301 .filter_map(|&(committed_log_msg_len, log_batch_size)| {
302 Some(committed_log_msg_len - log_batch_size?)
303 })
304 .max()
305 .unwrap_or(0);
306 // The upper bound is then the committed message length of the largest flexible oracle, if
307 // larger.
308 let max_reduced_log_dim = committed
309 .iter()
310 .filter(|(_, log_batch_size)| log_batch_size.is_none())
311 .map(|&(committed_log_msg_len, _)| committed_log_msg_len)
312 .max()
313 .unwrap_or(0)
314 .max(min_reduced_log_dim);
315
316 let optimizer = ReductionOptimizer::<F, _>::new(merkle_scheme, n_test_queries);
317 let min_sizes = optimizer.compute_optimal_arities(max_reduced_log_dim, log_inv_rate);
318
319 // Compute the contribution of the oracles with a fixed batch size to the initial fold reduction
320 // size. It's not necessary to compute this for the purpose of parameter minimization, but it's
321 // nice to get the resulting proof size estimate from this function.
322 let fixed_reduction_size = committed
323 .iter()
324 .filter_map(|&(committed_log_msg_len, log_batch_size)| {
325 log_batch_size.map(|log_batch_size| {
326 optimizer.compute_layer_reduction_size(
327 committed_log_msg_len + log_inv_rate,
328 log_batch_size,
329 )
330 })
331 })
332 .sum::<usize>();
333
334 let (reduced_log_dim, proof_size) =
335 min_concave((min_reduced_log_dim..=max_reduced_log_dim).rev(), |reduced_log_dim| {
336 // Compute the reduction sizes of the oracles with a flexible batch size, assuming
337 // the first FRI round oracle has dimension reduced_log_dim.
338 let non_fixed_reduction_size = committed
339 .iter()
340 .filter(|(_, log_batch_size)| log_batch_size.is_none())
341 .map(|&(committed_log_msg_len, _)| {
342 optimizer.compute_layer_reduction_size(
343 committed_log_msg_len + log_inv_rate,
344 committed_log_msg_len.saturating_sub(reduced_log_dim),
345 )
346 })
347 .sum::<usize>();
348
349 let reduction_size = fixed_reduction_size + non_fixed_reduction_size;
350 let reduced_proof_size = min_sizes[reduced_log_dim].proof_size;
351 reduction_size + reduced_proof_size
352 })
353 .expect("range is non-empty because it's inclusive of an upper bound >= the lower bound");
354
355 let fold_arities =
356 optimizer.optimizer_entries_to_fold_arities(&min_sizes[..reduced_log_dim + 1]);
357
358 ChooseBatchSizeAndAritiesOutput {
359 proof_size,
360 reduced_log_dim,
361 fold_arities,
362 }
363}
364
365struct ChooseCodewordSpecsOutput {
366 proof_size: usize,
367 reduced_log_dim: usize,
368 oracle_specs: Vec<CodewordSpec>,
369 fold_arities: Vec<usize>,
370}
371
372fn choose_codeword_specs_for_oracles<F, MerkleScheme>(
373 merkle_scheme: &MerkleScheme,
374 oracles: &[OracleSpec],
375 log_inv_rate: usize,
376 n_test_queries: usize,
377) -> ChooseCodewordSpecsOutput
378where
379 F: BinaryField,
380 MerkleScheme: MerkleTreeScheme<F>,
381{
382 // We want to determine the dimension of the first folded FRI oracle, which we'll call the
383 // "reduced" oracle. This is reduced_log_dim. For each input oracle, we will determine a
384 // log_batch_size. A ZK oracle commits its message interleaved with an equal-length mask, so its
385 // committed message length is `log_msg_len + 1` and its batch size is fixed at 1. A non-ZK
386 // oracle commits the bare message and takes a flexible batch size.
387 //
388 // `committed`: per oracle, its committed message length and its fixed log_batch_size (`Some`
389 // for ZK oracles, `None` for flexible non-ZK ones).
390 let committed: Vec<(usize, Option<usize>)> = oracles
391 .iter()
392 .map(|oracle| {
393 let committed_log_msg_len = oracle.log_msg_len() + usize::from(oracle.is_zk);
394 let log_batch_size = oracle.is_zk.then_some(1);
395 (committed_log_msg_len, log_batch_size)
396 })
397 .collect();
398
399 let ChooseBatchSizeAndAritiesOutput {
400 proof_size,
401 reduced_log_dim,
402 fold_arities,
403 } = choose_batch_size_and_arities_multi(merkle_scheme, &committed, log_inv_rate, n_test_queries);
404
405 // Resolve each oracle's concrete log_batch_size (fixed, or chosen to reduce to the shared
406 // dimension), paired with its committed message length and is_zk flag.
407 let resolved: Vec<(usize, usize, bool)> = oracles
408 .iter()
409 .zip(&committed)
410 .map(|(oracle, &(committed_log_msg_len, log_batch_size))| {
411 let log_batch_size = log_batch_size
412 .unwrap_or_else(|| committed_log_msg_len.saturating_sub(reduced_log_dim));
413 (committed_log_msg_len, log_batch_size, oracle.is_zk)
414 })
415 .collect();
416
417 // ZK-aware early/later batch-fold routing. A ZK oracle's batch is the shared masking challenge
418 // γ, sampled *before* the outer (oracle-combine) challenges, so it is entirely "early". A
419 // non-ZK oracle's flexible batch is sampled *after* the outer challenges, so it is entirely
420 // "later". The first-fold challenge slice is therefore `[early ++ outer ++ later]`, and each
421 // oracle folds its interleaving with a suffix of whichever group it belongs to.
422 let oracle_specs = resolved
423 .iter()
424 .map(|&(committed_log_msg_len, log_batch_size, is_zk)| {
425 let log_early_batch_size = if is_zk { log_batch_size } else { 0 };
426 let log_later_batch_size = if is_zk { 0 } else { log_batch_size };
427 // The committed codeword's own dimension is `committed_log_msg_len - log_batch_size`;
428 // it is lifted to the reduced dimension, so `log_lift` is the gap between the two.
429 let oracle_log_dim = committed_log_msg_len - log_batch_size;
430 let log_lift = reduced_log_dim - oracle_log_dim;
431 CodewordSpec {
432 log_lift,
433 log_early_batch_size,
434 log_later_batch_size,
435 }
436 })
437 .collect();
438
439 ChooseCodewordSpecsOutput {
440 proof_size,
441 reduced_log_dim,
442 oracle_specs,
443 fold_arities,
444 }
445}
446
447/// Calculates the number of test queries required to achieve a target soundness error.
448///
449/// This chooses a number of test queries so that the soundness error of the FRI query phase is
450/// at most $2^{-t}$, where $t$ is the threshold `security_bits`. This _does not_ account for the
451/// soundness error from the FRI folding phase or any other protocols, only the query phase. This
452/// sets the proximity parameter for FRI to the code's unique decoding radius. See [DP24],
453/// Section 5.2, for concrete soundness analysis.
454///
455/// [DP24]: <https://eprint.iacr.org/2024/504>
456pub fn calculate_n_test_queries(security_bits: usize, log_inv_rate: usize) -> usize {
457 let rate = 2.0f64.powi(-(log_inv_rate as i32));
458 let per_query_err = 0.5 * (1f64 + rate);
459 (security_bits as f64 / -per_query_err.log2()).ceil() as usize
460}
461
462#[derive(Debug)]
463struct ReductionOptimizerEntry {
464 // The minimum proof size attainable for the indexed value of i.
465 proof_size: usize,
466 // The first reduction arity to achieve the minimum proof size. If the value is none,
467 // then the best reduction sequence is to skip all folding and send the full codeword.
468 arity: Option<usize>,
469}
470
471struct ReductionOptimizer<'a, F, MTScheme> {
472 merkle_scheme: &'a MTScheme,
473 n_test_queries: usize,
474 _marker: PhantomData<F>,
475}
476
477impl<'a, F, MTScheme> ReductionOptimizer<'a, F, MTScheme>
478where
479 F: Field,
480 MTScheme: MerkleTreeScheme<F>,
481{
482 const fn new(merkle_scheme: &'a MTScheme, n_test_queries: usize) -> Self {
483 Self {
484 merkle_scheme,
485 n_test_queries,
486 _marker: PhantomData,
487 }
488 }
489
490 /// The proof bytes one reduction of the given arity contributes.
491 ///
492 /// Each test query sends one opened coset and its Merkle branch:
493 ///
494 /// ```text
495 /// coset 2^arity field elements
496 /// branch one hash per tree level
497 /// ```
498 ///
499 /// The oracle commits one coset per leaf.
500 /// So its tree holds `2^(log_code_len - arity)` leaves, not `2^log_code_len`.
501 ///
502 /// Sizing the tree by the codeword length would charge `arity` extra hashes per branch.
503 /// The arities chosen would then minimize a proof size no prover produces.
504 fn compute_layer_reduction_size(&self, log_code_len: usize, arity: usize) -> usize {
505 // Each queried coset contains 2^arity values.
506 let leaf_size = F::BYTE_SIZE << arity;
507 // One coset per test query.
508 let leaves_size = leaf_size * self.n_test_queries;
509
510 // One leaf per coset, so the tree is `arity` levels shorter than the codeword.
511 let log_n_cosets = log_code_len - arity;
512
513 // Size of the Merkle multi-proof.
514 let optimal_layer = self
515 .merkle_scheme
516 .optimal_verify_layer(self.n_test_queries, log_n_cosets);
517 let merkle_size =
518 self.merkle_scheme
519 .proof_size(1 << log_n_cosets, self.n_test_queries, optimal_layer);
520
521 leaves_size + merkle_size
522 }
523
524 fn compute_optimal_arities(
525 &self,
526 log_msg_len: usize,
527 log_inv_rate: usize,
528 ) -> Vec<ReductionOptimizerEntry> {
529 type Entry = ReductionOptimizerEntry;
530
531 // This algorithm uses a dynamic programming approach to determine the sequence of arities
532 // that minimizes proof size. For each i in [0, log_msg_len], we determine the minimum
533 // proof size attainable when for a batched codeword with message size 2^i. This is
534 // determined by minimizing over the first reduction arity, using the values already
535 // determined for the smaller values of i.
536
537 // This vec maps log_msg_len values to the minimum proof size attainable for a batched FRI
538 // protocol committing a message with that length.
539 let mut min_sizes = Vec::<Entry>::with_capacity(log_msg_len + 1);
540
541 for i in 0..=log_msg_len {
542 // Length of the batched codeword.
543 let log_code_len = i + log_inv_rate;
544
545 let non_terminal_entry = min_concave(1..=i, |arity| {
546 // The additional proof bytes for the reduction by arity.
547 let reduction_proof_size = self.compute_layer_reduction_size(log_code_len, arity);
548 let reduced_proof_size = min_sizes[i - arity].proof_size;
549 reduction_proof_size + reduced_proof_size
550 })
551 .map(|(arity, proof_size)| Entry {
552 arity: Some(arity),
553 proof_size,
554 });
555
556 // Determine the proof size if this is the terminal codeword. In that case, the proof
557 // simply consists of the 2^(i + log_inv_rate) leaf values.
558 let terminal_proof_size = F::BYTE_SIZE << log_code_len;
559 let terminal_entry = Entry {
560 proof_size: terminal_proof_size,
561 arity: None,
562 };
563
564 let optimal_entry = if let Some(non_terminal_entry) = non_terminal_entry
565 && non_terminal_entry.proof_size < terminal_entry.proof_size
566 {
567 non_terminal_entry
568 } else {
569 terminal_entry
570 };
571
572 min_sizes.push(optimal_entry);
573 }
574
575 min_sizes
576 }
577
578 fn optimizer_entries_to_fold_arities(
579 &self,
580 min_sizes: &[ReductionOptimizerEntry],
581 ) -> Vec<usize> {
582 let mut fold_arities = Vec::new();
583
584 let mut i = min_sizes.len() - 1;
585 let mut entry = &min_sizes[i];
586 while let Some(arity) = entry.arity {
587 fold_arities.push(arity);
588 i -= arity;
589 entry = &min_sizes[i];
590 }
591 fold_arities
592 }
593}
594
595/// Minimizes `f` over the values yielded by `params`, returning the minimizing argument and value.
596///
597/// This assumes `f` is unimodal (quasi-convex) over the iteration order: non-increasing up to the
598/// minimum and non-decreasing afterwards. It scans in order and stops as soon as `f` strictly
599/// increases. On ties it keeps the later argument. Returns `None` if `params` is empty.
600fn min_concave<A: Copy, B: Ord>(
601 mut params: impl Iterator<Item = A>,
602 f: impl Fn(A) -> B,
603) -> Option<(A, B)> {
604 let mut min_a = params.next()?;
605 let mut min_b = f(min_a);
606 for a in params {
607 let b = f(a);
608 if b <= min_b {
609 min_a = a;
610 min_b = b;
611 } else {
612 // The function f is concave in the sequence of params, so break if it begins
613 // increasing.
614 break;
615 }
616 }
617 Some((min_a, min_b))
618}
619
620#[cfg(test)]
621mod tests {
622 use binius_field::Ghash128b as B128;
623 use binius_hash::StdHashSuite;
624
625 use super::*;
626 use crate::{fri::proof_size, merkle_tree::BinaryMerkleTreeScheme};
627
628 type TestMerkleScheme = BinaryMerkleTreeScheme<B128, StdHashSuite>;
629
630 fn test_merkle_scheme() -> TestMerkleScheme {
631 BinaryMerkleTreeScheme::new()
632 }
633
634 /// Security level the shipped verifier targets.
635 ///
636 /// Restated rather than imported.
637 /// `binius_verifier::SECURITY_BITS` lives in a crate that depends on this one.
638 const SECURITY_BITS: usize = 96;
639
640 /// Candidate inverse rates, wide enough to bracket where the proof size turns around.
641 const LOG_INV_RATES: [usize; 6] = [1, 2, 3, 4, 5, 6];
642
643 /// Exact proof size per shape and rate, as `(shape, log_inv_rate, n_test_queries, bytes)`.
644 ///
645 /// Every shape bottoms out inside the candidate range.
646 /// The smallest oracle bottoms out at rate 1/8, and the larger two at 1/16.
647 const PINNED_PROOF_SIZE_BY_RATE: [(&str, usize, usize, usize); 18] = [
648 ("single/17", 1, 232, 205152),
649 ("single/17", 2, 142, 160128),
650 ("single/17", 3, 116, 154240),
651 ("single/17", 4, 106, 161088),
652 ("single/17", 5, 101, 172544),
653 ("single/17", 6, 99, 186304),
654 ("single/24", 1, 232, 472480),
655 ("single/24", 2, 142, 340128),
656 ("single/24", 3, 116, 307264),
657 ("single/24", 4, 106, 307008),
658 ("single/24", 5, 101, 318240),
659 ("single/24", 6, 99, 336192),
660 ("zk/24+21", 1, 232, 730208),
661 ("zk/24+21", 2, 142, 513344),
662 ("zk/24+21", 3, 116, 458432),
663 ("zk/24+21", 4, 106, 452640),
664 ("zk/24+21", 5, 101, 463856),
665 ("zk/24+21", 6, 99, 485424),
666 ];
667
668 /// The exact proof size at one rate, with the arities re-optimized for it.
669 ///
670 /// The query count is not a parameter, but the one that rate needs for `SECURITY_BITS`.
671 /// A rate buys proof bytes precisely by changing it, so pairing the two is the point.
672 fn proof_size_at_rate(
673 merkle_scheme: &TestMerkleScheme,
674 oracles: &[OracleSpec],
675 log_inv_rate: usize,
676 ) -> usize {
677 let n_test_queries = calculate_n_test_queries(SECURITY_BITS, log_inv_rate);
678 let (params, _) =
679 FRIParams::optimal_for_batch(merkle_scheme, oracles, log_inv_rate, n_test_queries);
680 proof_size(¶ms, merkle_scheme)
681 }
682
683 // Invariant: the size the arity search minimizes is the size a prover actually sends.
684 //
685 // cost model what `compute_layer_reduction_size` charges, and the search minimizes
686 // proof_size the exact byte count
687 //
688 // The cost model omits the commitment digests, which do not vary with the arity choice.
689 // A batch of N input oracles carries `N + 1 + fold_arities.len()` of them.
690 #[test]
691 fn optimizer_estimate_matches_exact_proof_size() {
692 let merkle_scheme = test_merkle_scheme();
693 let digest_size = size_of::<<TestMerkleScheme as MerkleTreeScheme<B128>>::Digest>();
694
695 // Single oracles across the size range, then shapes that stress the batch layout: lifting,
696 // ZK mixed with flexible, non-power-of-two counts.
697 //
698 // A ZK oracle pins its batch size at 1; a non-ZK oracle takes a flexible one, so the two
699 // exercise different branches of the selection.
700 let mut batches: Vec<Vec<OracleSpec>> = Vec::new();
701 for log_msg_len in [0, 1, 4, 8, 12, 16, 20] {
702 batches.push(vec![OracleSpec::new(1 << log_msg_len)]);
703 batches.push(vec![OracleSpec::new_zk(1 << log_msg_len)]);
704 }
705 batches.extend([
706 vec![OracleSpec::new(1 << 16), OracleSpec::new(1 << 16)],
707 vec![OracleSpec::new(1 << 16), OracleSpec::new(1 << 12)],
708 vec![OracleSpec::new_zk(1 << 11), OracleSpec::new(1 << 16)],
709 vec![
710 OracleSpec::new_zk(1 << 9),
711 OracleSpec::new_zk(1 << 11),
712 OracleSpec::new(1 << 16),
713 ],
714 vec![
715 OracleSpec::new(1 << 20),
716 OracleSpec::new_zk(1 << 15),
717 OracleSpec::new(1 << 8),
718 OracleSpec::new_zk(1 << 4),
719 ],
720 ]);
721
722 for log_inv_rate in [1, 2, 3] {
723 for n_test_queries in [32, 128, 232] {
724 for oracles in &batches {
725 let (params, estimate) = FRIParams::optimal_for_batch(
726 &merkle_scheme,
727 oracles,
728 log_inv_rate,
729 n_test_queries,
730 );
731
732 let digests = (oracles.len() + 1 + params.fold_arities().len()) * digest_size;
733 assert_eq!(
734 estimate + digests,
735 proof_size(¶ms, &merkle_scheme),
736 "oracles={oracles:?} log_inv_rate={log_inv_rate} \
737 n_test_queries={n_test_queries} arities={:?}",
738 params.fold_arities(),
739 );
740 }
741 }
742 }
743 }
744
745 // Invariant: lowering the rate trades encoding work for proof bytes, and overshoots.
746 //
747 // queries fall monotonically as the rate falls, then flatten out
748 // bytes fall with the queries, then climb again
749 //
750 // The climb is the terminal codeword and every opened coset growing with the rate.
751 // The candidates bracket the turning point on both sides, and it moves with the oracle size.
752 #[test]
753 fn pinned_proof_size_by_rate() {
754 let merkle_scheme = test_merkle_scheme();
755
756 // A small and a large single oracle, plus a ZK batch.
757 // The ZK oracle pins its batch size at 1, taking the fixed-batch-size branch of selection.
758 // The shorter non-ZK oracle beside it exercises lifting.
759 let batches: [(&str, Vec<OracleSpec>); 3] = [
760 ("single/17", vec![OracleSpec::new(1 << 17)]),
761 ("single/24", vec![OracleSpec::new(1 << 24)]),
762 ("zk/24+21", vec![OracleSpec::new_zk(1 << 24), OracleSpec::new(1 << 21)]),
763 ];
764
765 let observed = batches
766 .iter()
767 .flat_map(|(label, oracles)| {
768 LOG_INV_RATES.map(|log_inv_rate| {
769 (
770 *label,
771 log_inv_rate,
772 calculate_n_test_queries(SECURITY_BITS, log_inv_rate),
773 proof_size_at_rate(&merkle_scheme, oracles, log_inv_rate),
774 )
775 })
776 })
777 .collect::<Vec<_>>();
778
779 assert_eq!(observed, PINNED_PROOF_SIZE_BY_RATE);
780 }
781
782 // Reports the rate trade-off, rather than asserting it, for picking `log_inv_rate` by hand.
783 //
784 // cargo test -p binius-iop --lib -- --ignored --nocapture report_rate_trade_off
785 //
786 // The encode column is derived, not measured, and is exact.
787 // `ReedSolomonCode::encode_batch` skips its first `log_inv_rate` NTT layers.
788 // It therefore runs `log_dim` layers over a codeword of `2^(log_dim + log_inv_rate)`:
789 //
790 // butterflies = log_dim * 2^(log_dim + log_inv_rate - 1)
791 //
792 // The rate enters as a bare factor of `2^log_inv_rate`, with no log term on it.
793 // One step down the rate is exactly twice the encoding work, so the column is a doubling.
794 //
795 // `crates/math/benches/reed_solomon.rs` measures how far memory traffic bends that.
796 #[test]
797 #[ignore = "prints a table instead of asserting; needs --nocapture to be useful"]
798 fn report_rate_trade_off() {
799 let merkle_scheme = test_merkle_scheme();
800
801 for log_msg_len in [17, 20, 24] {
802 let oracles = [OracleSpec::new(1 << log_msg_len)];
803 let priced = LOG_INV_RATES
804 .map(|log_inv_rate| proof_size_at_rate(&merkle_scheme, &oracles, log_inv_rate));
805 let smallest = priced
806 .iter()
807 .copied()
808 .min()
809 .expect("LOG_INV_RATES is non-empty");
810
811 println!();
812 println!(
813 "one non-ZK oracle, log_msg_len = {log_msg_len}, {SECURITY_BITS}-bit security"
814 );
815 println!(" rate queries proof vs best encode");
816 for (log_inv_rate, proof_size) in std::iter::zip(LOG_INV_RATES, priced) {
817 let n_test_queries = calculate_n_test_queries(SECURITY_BITS, log_inv_rate);
818 let kib = proof_size as f64 / 1024.0;
819 let vs_best = proof_size as f64 / smallest as f64;
820 // Encoding work relative to the first candidate, which is the cheapest to encode.
821 let encode = 1usize << (log_inv_rate - LOG_INV_RATES[0]);
822 println!(
823 " 1/{:<3} {n_test_queries:>7} {kib:>7.2} KiB {vs_best:>6.2}x {encode:>4}x",
824 1 << log_inv_rate
825 );
826 }
827 }
828 }
829
830 // Invariant: a lower rate needs fewer queries, but the saving flattens out fast.
831 //
832 // 1/2 -> 232 1/16 -> 106
833 // 1/4 -> 142 1/32 -> 101
834 // 1/8 -> 116 1/64 -> 99
835 //
836 // Past 1/8, halving the rate again buys ten queries while doubling the codeword.
837 // That flattening is why `pinned_proof_size_by_rate` turns around instead of falling forever.
838 #[test]
839 fn test_calculate_n_test_queries() {
840 let observed =
841 LOG_INV_RATES.map(|log_inv_rate| calculate_n_test_queries(SECURITY_BITS, log_inv_rate));
842 assert_eq!(observed, [232, 142, 116, 106, 101, 99]);
843 }
844
845 #[test]
846 fn test_min_proof_size_arities() {
847 let merkle_scheme = test_merkle_scheme();
848 let log_inv_rate = 2;
849 let n_test_queries = 128;
850 let arities = |log_msg_len| {
851 let optimizer = ReductionOptimizer::<B128, _>::new(&merkle_scheme, n_test_queries);
852 let min_sizes = optimizer.compute_optimal_arities(log_msg_len, log_inv_rate);
853 optimizer.optimizer_entries_to_fold_arities(&min_sizes)
854 };
855
856 // No folding needed, terminal codeword is optimal.
857 assert_eq!(arities(0), vec![]);
858 assert_eq!(arities(3), vec![]);
859 assert_eq!(arities(24), vec![4, 4, 4, 4]);
860 }
861
862 #[test]
863 fn test_optimal_for_batch_three_oracles() {
864 let merkle_scheme = test_merkle_scheme();
865 let log_inv_rate = 2;
866 let n_test_queries = 128;
867
868 // Two masked ZK oracles (fixed batch size 1, committed lengths 10 and 12) and one non-ZK
869 // oracle with a flexible batch size (committed length 16). The ZK oracles lower-bound the
870 // reduced dimension; the flexible oracle folds down to it.
871 let oracles = vec![
872 OracleSpec::new_zk(1 << 9),
873 OracleSpec::new_zk(1 << 11),
874 OracleSpec::new(1 << 16),
875 ];
876
877 let (fri_params, proof_size) =
878 FRIParams::optimal_for_batch(&merkle_scheme, &oracles, log_inv_rate, n_test_queries);
879
880 // The reduced oracle dimension is the dimension of the first FRI round oracle, equal to
881 // log_terminal_dim + sum(fold_arities).
882 let reduced_log_dim = fri_params.rs_code().log_dim();
883 assert_eq!(
884 reduced_log_dim,
885 fri_params.log_terminal_dim + fri_params.fold_arities().iter().sum::<usize>()
886 );
887
888 // Each input oracle satisfies the FRIParams invariants.
889 assert_eq!(fri_params.input_oracles.len(), oracles.len());
890 for (spec, oracle) in fri_params.input_oracles.iter().zip(&oracles) {
891 // A ZK oracle interleaves the message with an equal-length mask, so its committed
892 // message length is `log_msg_len + 1`; a non-ZK oracle commits the bare message.
893 let committed_log_msg_len = oracle.log_msg_len() + usize::from(oracle.is_zk);
894 // The committed codeword (dimension `committed_log_msg_len - log_batch_size`) is lifted
895 // to the reduced dimension, recovering the committed message length.
896 let oracle_log_dim = reduced_log_dim - spec.log_lift;
897 assert_eq!(oracle_log_dim + spec.log_batch_size(), committed_log_msg_len);
898 if oracle.is_zk {
899 // ZK oracles keep their fixed batch size of 1.
900 assert_eq!(spec.log_batch_size(), 1);
901 }
902 // log_batch_size <= committed message length
903 assert!(spec.log_batch_size() <= committed_log_msg_len);
904 }
905
906 // The largest input oracle is the non-ZK flexible one, so its batch size folds it down
907 // exactly to the reduced dimension (no lifting).
908 assert_eq!(fri_params.input_oracles[2].log_lift, 0);
909 assert_eq!(fri_params.input_oracles[2].log_batch_size(), 16 - reduced_log_dim);
910
911 // Pin the estimated proof size, to catch unintended changes in the optimizer.
912 //
913 // This sums one reduction per committed oracle, as the exact byte count does.
914 // `optimizer_estimate_matches_exact_proof_size` ties the two together.
915 assert_eq!(proof_size, 188416);
916 }
917}