binius_iop/fri/
size_estimation.rs

1// Copyright 2026 The Binius Developers
2
3use binius_field::BinaryField;
4
5use super::common::FRIParams;
6use crate::merkle_tree::MerkleTreeScheme;
7
8/// Exact byte-size of a FRI proof, including the initial commitment.
9///
10/// The size follows from the parameters alone, so the prover need not run.
11///
12/// Counted on the message channel:
13/// - the initial codeword commitment;
14/// - one commitment per fold round.
15///
16/// Counted on the decommitment channel:
17/// - the terminal codeword, sent in the clear;
18/// - the Merkle layer digests and the per-query branch digests;
19/// - the field elements of every opened coset.
20pub fn proof_size<F, VCS>(params: &FRIParams<F>, vcs: &VCS) -> usize
21where
22	F: BinaryField,
23	VCS: MerkleTreeScheme<F>,
24{
25	let digest_size = std::mem::size_of::<VCS::Digest>();
26
27	// Serialized byte-size of a single field element.
28	let value_size = {
29		let mut buf = Vec::new();
30		F::default()
31			.serialize(&mut buf)
32			.expect("default element can be serialized to a resizable buffer");
33		buf.len()
34	};
35
36	let n_test_queries = params.n_test_queries();
37
38	// One digest per input oracle, one per fold round, one for the terminal codeword.
39	let commitment_msg_size = (params.input_oracles().len() + params.n_oracles()) * digest_size;
40
41	// Terminal codeword sent in the clear: 2^(log_terminal_dim + log_inv_rate) field elements.
42	let log_terminal_dim = params.n_final_challenges();
43	let log_inv_rate = params.rs_code().log_inv_rate();
44	let terminate_codeword_size = (1 << (log_terminal_dim + log_inv_rate)) * value_size;
45
46	let mut merkle_sizes = 0;
47	let mut coset_values_size = 0;
48
49	// Per query, an oracle sends one coset of `2^arity` elements and a Merkle branch.
50	// The layer depth must be chosen for the tree it indexes.
51	let mut open = |log_n_cosets: usize, arity: usize| {
52		let layer_depth = vcs.optimal_verify_layer(n_test_queries, log_n_cosets);
53		merkle_sizes += vcs.proof_size(1 << log_n_cosets, n_test_queries, layer_depth);
54		coset_values_size += n_test_queries * (1 << arity) * value_size;
55	};
56
57	// Input oracles are opened one after another, each against its own commitment.
58	// So a batch of N sends N multi-proofs, not one.
59	//
60	// An oracle's codeword sits `log_lift` below the reduced dimension.
61	let log_dim = params.rs_code().log_dim();
62	for spec in params.input_oracles() {
63		open(log_dim - spec.log_lift + log_inv_rate, spec.log_batch_size());
64	}
65
66	// Then one per fold round.
67	// The outer oracle-combine challenges cost nothing: they recombine values already opened.
68	let mut log_n_cosets = params.index_bits();
69	for &arity in params.fold_arities() {
70		log_n_cosets -= arity;
71		open(log_n_cosets, arity);
72	}
73
74	commitment_msg_size + terminate_codeword_size + merkle_sizes + coset_values_size
75}
binius_iop/fri/size_estimation.rs

binius_iop/fri/
size_estimation.rs
