Skip to main content

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(&params, 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(&params, &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}