openvm_stark_sdk/config/
fri_params.rs

1use std::f64::consts::LN_2;
2
3use openvm_stark_backend::{
4    config::DeepAliParameters, interaction::LogUpSecurityParameters, p3_field::Field,
5};
6use serde::{Deserialize, Serialize};
7
8use crate::config::log_up_params::log_up_security_params_baby_bear_100_bits;
9
10pub const MAX_NUM_CONSTRAINTS: usize = 30_000;
11pub const MAX_BATCH_SIZE_LOG_BLOWUP_1: usize = 80_000;
12pub const MAX_BATCH_SIZE_LOG_BLOWUP_2: usize = 4_000;
13
14#[derive(Clone, Copy, Debug, Serialize, Deserialize, PartialEq, Eq)]
15pub struct FriParameters {
16    pub log_blowup: usize,
17    pub log_final_poly_len: usize,
18    pub num_queries: usize,
19    pub query_proof_of_work_bits: usize,
20    pub commit_proof_of_work_bits: usize,
21}
22
23impl FriParameters {
24    /// Conjectured bits of security.
25    /// See ethSTARK paper (<https://eprint.iacr.org/2021/582.pdf>) section 5.10.1 equation (19)
26    ///
27    /// `challenge_field_bits` is the number of bits in the challenge field (extension field) of the
28    /// STARK config.
29    pub fn get_conjectured_security_bits(&self, challenge_field_bits: usize) -> usize {
30        let fri_query_security_bits =
31            self.num_queries * self.log_blowup + self.query_proof_of_work_bits;
32        // The paper says min(fri_field_bits, fri_query_security_bits) - 1 but plonky2 (https://github.com/0xPolygonZero/plonky2/blob/41dc325e61ab8d4c0491e68e667c35a4e8173ffa/starky/src/config.rs#L86C1-L87C1) omits the -1
33        challenge_field_bits.min(fri_query_security_bits)
34    }
35
36    /// See [standard_fri_params_with_100_bits_security].
37    pub fn standard_fast() -> Self {
38        standard_fri_params_with_100_bits_security(1)
39    }
40
41    #[deprecated(note = "use standard_with_100_bits_security instead")]
42    pub fn standard_with_100_bits_conjectured_security(log_blowup: usize) -> Self {
43        #[allow(deprecated)]
44        standard_fri_params_with_100_bits_conjectured_security(log_blowup)
45    }
46
47    /// See [standard_fri_params_with_100_bits_security].
48    pub fn standard_with_100_bits_security(log_blowup: usize) -> Self {
49        standard_fri_params_with_100_bits_security(log_blowup)
50    }
51
52    pub fn max_constraint_degree(&self) -> usize {
53        (1 << self.log_blowup) + 1
54    }
55
56    /// New FRI parameters for testing usage with the specific `log_blowup`.
57    /// If the environment variable `OPENVM_FAST_TEST` is set to "1", then the parameters are **not
58    /// secure** and meant for fast testing only.
59    ///
60    /// In production, use `Self::standard_with_100_bits_security` instead.
61    pub fn new_for_testing(log_blowup: usize) -> Self {
62        if let Ok("1") = std::env::var("OPENVM_FAST_TEST").as_deref() {
63            Self {
64                log_blowup,
65                log_final_poly_len: 0,
66                num_queries: 2,
67                commit_proof_of_work_bits: 0,
68                query_proof_of_work_bits: 0,
69            }
70        } else {
71            Self::standard_with_100_bits_security(log_blowup)
72        }
73    }
74
75    /// We (via Plonky3) use multi-FRI, whose security in the unique decoding regime can be bounded
76    /// above by the security of batch FRI by considering all polynomials in the largest domain.
77    ///
78    /// Following <https://eprint.iacr.org/2023/1071.pdf>, <https://eprint.iacr.org/2025/1993.pdf>,
79    /// we use round-by-round soundness since we use FRI as a non-interactive protocol via
80    /// Fiat-Shamir.
81    ///
82    /// We use multi-FRI with <=2 opening points (the second point for rotation openings). The
83    /// `num_batch_columns` is the maximum number of columns to be batched for any fixed domain
84    /// size. A trace polynomial over the base field opened at 2 points gets a contribution of
85    /// 2. A trace polynomial over the extension field opened at 2 points gets a contribution of
86    /// 8.
87    pub fn security_bits_fri(
88        &self,
89        challenge_field_bits: f64,
90        num_batch_columns: usize,
91        max_log_domain_size: usize,
92    ) -> f64 {
93        let commit_bits = self.security_bits_fri_commit_phase(
94            challenge_field_bits,
95            num_batch_columns,
96            max_log_domain_size,
97        );
98        tracing::debug!("FRI commit phase security bits: {commit_bits}");
99        let query_bits = self.security_bits_fri_query_phase();
100        tracing::debug!("FRI query phase security bits: {query_bits}");
101        commit_bits.min(query_bits)
102    }
103
104    /// Batch FRI error according to <https://eprint.iacr.org/2022/1216.pdf> in the unique decoding regime.
105    /// The batch FRI bound is an overestimate because in multi-FRI the error contribution for
106    /// batching over smaller domain sizes is smaller.
107    ///
108    /// We assume arity-2 folding.
109    pub fn security_bits_fri_commit_phase(
110        &self,
111        challenge_field_bits: f64,
112        num_batch_columns: usize,
113        max_log_domain_size: usize,
114    ) -> f64 {
115        let domain_size = 2.0_f64.powi(max_log_domain_size as i32);
116        let field_size = 2.0_f64.powf(challenge_field_bits);
117
118        // Using formula (1) from https://eprint.iacr.org/2022/1216.pdf on correlated agreement in UDR.
119        let batch_term = num_batch_columns - 1;
120        let fold_term = 1; // (3 - 1) * 1/2, where in each stage of multi-FRI we batch 3 terms using 1, beta, beta^2
121                           // and we start at half the largest domain size
122        -(batch_term.max(fold_term) as f64 * domain_size / field_size).log2()
123            + self.commit_proof_of_work_bits as f64
124    }
125
126    pub fn security_bits_fri_query_phase(&self) -> f64 {
127        let rho = (2.0_f64).powi(-(self.log_blowup as i32));
128        let theta = (1.0 - rho) / 2.0;
129        -(self.num_queries as f64 * (-theta).ln_1p() / LN_2) + self.query_proof_of_work_bits as f64
130    }
131
132    /// The bits of security from DEEP-ALI.
133    /// Note that unlike in Theorem 8 of <https://eprint.iacr.org/2022/1216.pdf>, we do not include the rotation in the denominator of the quotient polynomial. Instead the quotient polynomial denominator consists only of `Z_H(X) = X^{trace_height} - 1`. The rotation opening point is handled as part of FRI PCS opening as an additional opening point. This means that for us `k^+ = k + 1`. We also include degree of selectors within the `max_constraint_degree` parameter.
134    pub fn security_bits_deep_ali(
135        &self,
136        params: &DeepAliParameters,
137        challenge_field_bits: f64,
138        max_log_domain_size: usize,
139        max_constraint_degree: usize,
140        max_num_constraints: usize,
141    ) -> f64 {
142        assert!(max_constraint_degree <= (1 << self.log_blowup) + 1);
143        let trace_length = 2.0_f64.powi(max_log_domain_size.saturating_sub(self.log_blowup) as i32);
144        let domain_size = 2.0_f64.powi(max_log_domain_size as i32);
145        let field_size = 2.0_f64.powf(challenge_field_bits);
146        // Error term obtained from Schwartz-Zippel applied to the constraint polynomial and
147        // vanishing polynomial. The random out-of-domain point must avoid subgroup H and
148        // codeword evaluation coset D.
149        let e_deep = (max_constraint_degree as f64) * (trace_length - 1.0)
150            / (field_size - trace_length - domain_size);
151        // ALI error is from algebraic batching
152        let e_ali = (max_num_constraints as f64) / field_size;
153        (-e_deep.log2() + params.deep_pow_bits as f64).min(-e_ali.log2())
154    }
155}
156
157/// Pre-defined FRI parameters with 100 bits of provable security, meaning we do
158/// not rely on any conjectures about Reed–Solomon codes (e.g., about proximity
159/// gaps) or the ethSTARK Toy Problem Conjecture.
160///
161/// Bits of provable security refers to Fiat-Shamir security, which is obtained from round-by-round
162/// soundness analysis.
163///
164/// The value `num_queries` is chosen so that the verifier accepts a δ-far
165/// codeword for δ = (1 - 2**(-log_blowup)) with probability at most 2^{-80}.
166/// I.e., we target the unique-decoding radius. We require 20 PoW bits
167/// just before the query phase begins to boost the soundness to 100 bits.
168///
169/// Assumes that:
170/// - the challenge field has size at least 2^123
171/// - for `log_blowup = 1`, the number of trace polynomials batched in any level of multi-FRI is at
172///   most 80000. A trace polynomial over the base field opened at 2 points gets a contribution of
173///   2. A trace polynomial over the extension field opened at 2 points gets a contribution of 8.
174/// - for `log_blowup > 1`, the number of trace polynomials batched in any level of multi-FRI is at
175///   most 4000.
176/// - the maximum trace height is 2^27
177/// - for DEEP-ALI, the maximum number of constraints is 15000.
178pub fn standard_fri_params_with_100_bits_security(log_blowup: usize) -> FriParameters {
179    let fri_params = match log_blowup {
180        1 => FriParameters {
181            log_blowup,
182            log_final_poly_len: 0,
183            num_queries: 193,
184            commit_proof_of_work_bits: 20,
185            query_proof_of_work_bits: 20,
186        },
187        2 => FriParameters {
188            log_blowup,
189            log_final_poly_len: 0,
190            num_queries: 118,
191            commit_proof_of_work_bits: 16,
192            query_proof_of_work_bits: 20,
193        },
194        3 => FriParameters {
195            log_blowup,
196            log_final_poly_len: 0,
197            num_queries: 97,
198            commit_proof_of_work_bits: 16,
199            query_proof_of_work_bits: 20,
200        },
201        4 => FriParameters {
202            log_blowup,
203            log_final_poly_len: 0,
204            num_queries: 88,
205            commit_proof_of_work_bits: 16,
206            query_proof_of_work_bits: 20,
207        },
208        _ => panic!("No standard FRI params defined for log blowup {log_blowup}",),
209    };
210    tracing::debug!("FRI parameters | log_blowup: {log_blowup:<2} | num_queries: {:<2} | commit_proof_of_work_bits: {:<2} | query_proof_of_work_bits: {:<2}", fri_params.num_queries, fri_params.commit_proof_of_work_bits, fri_params.query_proof_of_work_bits);
211    fri_params
212}
213
214/// Pre-defined FRI parameters with 100 bits of conjectured security.
215/// Security bits calculated following ethSTARK (<https://eprint.iacr.org/2021/582.pdf>) 5.10.1 eq (19)
216///
217/// Assumes that the challenge field used as more than 100 bits.
218#[deprecated(note = "use standard_fri_params_with_100_bits_security instead")]
219pub fn standard_fri_params_with_100_bits_conjectured_security(log_blowup: usize) -> FriParameters {
220    let fri_params = match log_blowup {
221        // plonky2 standard fast config uses num_queries=84: https://github.com/0xPolygonZero/plonky2/blob/41dc325e61ab8d4c0491e68e667c35a4e8173ffa/starky/src/config.rs#L49
222        // plonky3's default is num_queries=100, so we will use that. See https://github.com/Plonky3/Plonky3/issues/380 for related security discussion.
223        1 => FriParameters {
224            log_blowup,
225            log_final_poly_len: 0,
226            num_queries: 100,
227            commit_proof_of_work_bits: 0,
228            query_proof_of_work_bits: 16,
229        },
230        2 => FriParameters {
231            log_blowup,
232            log_final_poly_len: 0,
233            num_queries: 44,
234            commit_proof_of_work_bits: 0,
235            query_proof_of_work_bits: 16,
236        },
237        // plonky2 standard recursion config: https://github.com/0xPolygonZero/plonky2/blob/41dc325e61ab8d4c0491e68e667c35a4e8173ffa/plonky2/src/plonk/circuit_data.rs#L101
238        3 => FriParameters {
239            log_blowup,
240            log_final_poly_len: 0,
241            num_queries: 30,
242            commit_proof_of_work_bits: 0,
243            query_proof_of_work_bits: 16,
244        },
245        4 => FriParameters {
246            log_blowup,
247            log_final_poly_len: 0,
248            num_queries: 23,
249            commit_proof_of_work_bits: 0,
250            query_proof_of_work_bits: 16,
251        },
252        _ => panic!("No standard FRI params defined for log blowup {log_blowup}",),
253    };
254    assert!(fri_params.get_conjectured_security_bits(100) >= 100);
255    tracing::debug!("FRI parameters | log_blowup: {log_blowup:<2} | num_queries: {:<2} | commit_pow_bits: {:<2}, query_pow_bits: {:<2}", fri_params.num_queries, fri_params.commit_proof_of_work_bits, fri_params.query_proof_of_work_bits);
256    fri_params
257}
258
259#[derive(Clone, Debug)]
260pub struct SecurityParameters {
261    pub fri_params: FriParameters,
262    pub log_up_params: LogUpSecurityParameters,
263    pub deep_ali_params: DeepAliParameters,
264}
265
266impl SecurityParameters {
267    /// See [standard_fri_params_with_100_bits_security].
268    pub fn standard_fast() -> Self {
269        Self::new_baby_bear_100_bits(FriParameters::standard_fast())
270    }
271
272    /// See [standard_fri_params_with_100_bits_security].
273    ///
274    /// Bits of provable security refers to Fiat-Shamir security, which is obtained from
275    /// round-by-round soundness analysis.
276    pub fn standard_100_bits_with_fri_log_blowup(log_blowup: usize) -> Self {
277        Self::new_baby_bear_100_bits(FriParameters::standard_with_100_bits_security(log_blowup))
278    }
279
280    pub fn new_baby_bear_100_bits(fri_params: FriParameters) -> Self {
281        Self {
282            fri_params,
283            log_up_params: log_up_security_params_baby_bear_100_bits(),
284            deep_ali_params: deep_ali_security_params_baby_bear_100_bits(),
285        }
286    }
287
288    pub fn security_bits<EF: Field>(
289        &self,
290        challenge_field_bits: f64,
291        num_batch_columns: usize,
292        max_log_domain_size: usize,
293        max_constraint_degree: usize,
294        max_num_constraints: usize,
295    ) -> f64 {
296        let fri_bits = self.fri_params.security_bits_fri(
297            challenge_field_bits,
298            num_batch_columns,
299            max_log_domain_size,
300        );
301        tracing::debug!("FRI security bits: {fri_bits}");
302        let deep_ali_bits = self.fri_params.security_bits_deep_ali(
303            &self.deep_ali_params,
304            challenge_field_bits,
305            max_log_domain_size,
306            max_constraint_degree,
307            max_num_constraints,
308        );
309        tracing::debug!("DEEP-ALI security bits: {deep_ali_bits}");
310        let logup_bits = self.log_up_params.bits_of_security::<EF>() as i32;
311        tracing::debug!("LogUp security bits: {logup_bits}");
312
313        fri_bits.min(deep_ali_bits).min(logup_bits as f64)
314    }
315}
316
317pub fn deep_ali_security_params_baby_bear_100_bits() -> DeepAliParameters {
318    DeepAliParameters { deep_pow_bits: 5 }
319}
320
321#[cfg(test)]
322mod security_tests {
323    use openvm_stark_backend::p3_field::{
324        extension::BinomialExtensionField, PrimeField64, TwoAdicField,
325    };
326    use p3_baby_bear::BabyBear;
327    use tracing::Level;
328
329    use super::*;
330    use crate::config::setup_tracing_with_log_level;
331
332    #[test]
333    fn test_params_provable_security() {
334        setup_tracing_with_log_level(Level::DEBUG);
335
336        let challenge_field_bits = (BabyBear::ORDER_U64 as f64).powi(4).log2();
337        for log_blowup in 1..=4 {
338            let params = SecurityParameters::standard_100_bits_with_fri_log_blowup(log_blowup);
339            let num_batch_columns = if log_blowup == 1 {
340                MAX_BATCH_SIZE_LOG_BLOWUP_1
341            } else {
342                MAX_BATCH_SIZE_LOG_BLOWUP_2
343            };
344            let max_constraint_degree = (1 << log_blowup) + 1;
345            let max_log_domain_size = BabyBear::TWO_ADICITY;
346            let bits = params.security_bits::<BinomialExtensionField<BabyBear, 4>>(
347                challenge_field_bits,
348                num_batch_columns,
349                max_log_domain_size,
350                max_constraint_degree,
351                MAX_NUM_CONSTRAINTS,
352            );
353            assert!(
354                bits >= 100.0,
355                "log_blowup: {log_blowup} has {bits} bits of security"
356            );
357        }
358    }
359}
openvm_stark_sdk/config/fri_params.rs

openvm_stark_sdk/config/
fri_params.rs
