openvm_stark_sdk/
cost_estimate.rs

1use std::{marker::PhantomData, ops::Add};
2
3use openvm_stark_backend::{
4    config::{Com, StarkGenericConfig, Val},
5    keygen::types::StarkVerifyingKey,
6    p3_field::FieldExtensionAlgebra,
7};
8
9use crate::config::FriParameters;
10
11/// Properties of a multi-trace circuit necessary to estimate verifier cost.
12#[derive(Clone, Copy, Debug)]
13pub struct VerifierCostParameters {
14    /// Total number of base field columns across all AIR traces before challenge.
15    pub num_main_columns: usize,
16    /// Total number of base field columns across all AIR traces for logup permutation.
17    pub num_perm_columns: usize,
18    /// log_2 Maximum height of an AIR trace.
19    pub log_max_height: usize,
20    /// Degree of quotient polynomial. This is `max_constraint_degree - 1`.
21    pub quotient_degree: usize,
22}
23
24/// Mmcs batch verification consist of hashing the leaf and then a normal Merkle proof.
25/// We separate the cost of hashing (which requires proper padding to be a cryptographic hash) from
26/// the cost of 2-to-1 compression function on the hash digest because in tree proofs the internal
27/// layers do not need to use a compression function with padding.
28///
29/// Currently the estimate ignores the additional details of hashing in matrices of different
30/// heights.
31#[derive(Clone, Copy, Debug)]
32pub struct MmcsVerifyBatchCostEstimate {
33    /// Hash cost in terms of number of field elements to hash. To convert to true hash cost, it
34    /// depends on the rate of the cryptographic hash.
35    pub num_f_to_hash: usize,
36    /// Number of calls of 2-to-1 compression function.
37    pub num_compress: usize,
38}
39
40impl MmcsVerifyBatchCostEstimate {
41    /// `width` is number of base field columns.
42    /// `max_log_height_lde` is the height of the MMCS (which includes blowup)
43    pub fn from_dim(width: usize, max_log_height_lde: usize) -> Self {
44        Self {
45            num_f_to_hash: width,
46            num_compress: max_log_height_lde,
47        }
48    }
49}
50
51impl Add for MmcsVerifyBatchCostEstimate {
52    type Output = Self;
53
54    fn add(self, rhs: Self) -> Self::Output {
55        Self {
56            num_f_to_hash: self.num_f_to_hash + rhs.num_f_to_hash,
57            num_compress: self.num_compress + rhs.num_compress,
58        }
59    }
60}
61
62#[derive(Clone, Copy, Debug)]
63pub struct FriOpenInputCostEstimate {
64    /// Cost from MMCS batch verification.
65    pub mmcs: MmcsVerifyBatchCostEstimate,
66    /// Number of operations of the form $+ \alpha^? \frac{M_j(\zeta) - y_{ij}}{\zeta - z_i}$ in
67    /// the reduced opening evaluation.
68    pub num_ro_eval: usize,
69}
70
71impl FriOpenInputCostEstimate {
72    /// `width` is number of base field columns.
73    /// `max_log_height` is the trace height, before blowup.
74    /// `num_points` is number of points to open.
75    pub fn new(
76        width: usize,
77        max_log_height: usize,
78        num_points: usize,
79        fri_params: FriParameters,
80    ) -> Self {
81        let mut mmcs =
82            MmcsVerifyBatchCostEstimate::from_dim(width, max_log_height + fri_params.log_blowup);
83        mmcs.num_compress *= fri_params.num_queries;
84        mmcs.num_f_to_hash *= fri_params.num_queries;
85        let num_ro_eval = width * num_points * fri_params.num_queries;
86        Self { mmcs, num_ro_eval }
87    }
88}
89
90impl Add for FriOpenInputCostEstimate {
91    type Output = Self;
92
93    fn add(self, rhs: Self) -> Self::Output {
94        Self {
95            mmcs: self.mmcs + rhs.mmcs,
96            num_ro_eval: self.num_ro_eval + rhs.num_ro_eval,
97        }
98    }
99}
100
101pub struct FriQueryCostEstimate {
102    /// Cost from MMCS batch verification.
103    pub mmcs: MmcsVerifyBatchCostEstimate,
104    /// Number of single FRI fold evaluations: `e0 + (beta - xs[0]) * (e1 - e0) / (xs[1] - xs[0])`.
105    pub num_fri_folds: usize,
106}
107
108impl FriQueryCostEstimate {
109    /// `max_log_height` is the trace height, before blowup.
110    pub fn new(max_log_height: usize, fri_params: FriParameters) -> Self {
111        let mut mmcs = MmcsVerifyBatchCostEstimate {
112            num_f_to_hash: 2 * max_log_height,
113            num_compress: max_log_height * (max_log_height + fri_params.log_blowup - 1) / 2,
114        };
115        mmcs.num_compress *= fri_params.num_queries;
116        mmcs.num_f_to_hash *= fri_params.num_queries;
117        let num_fri_folds = max_log_height * fri_params.num_queries;
118        Self {
119            mmcs,
120            num_fri_folds,
121        }
122    }
123}
124
125impl Add for FriQueryCostEstimate {
126    type Output = Self;
127
128    fn add(self, rhs: Self) -> Self::Output {
129        Self {
130            mmcs: self.mmcs + rhs.mmcs,
131            num_fri_folds: self.num_fri_folds + rhs.num_fri_folds,
132        }
133    }
134}
135
136pub struct FriVerifierCostEstimate {
137    pub open_input: FriOpenInputCostEstimate,
138    pub query: FriQueryCostEstimate,
139    /// We currently ignore the constraint evaluation cost because it does not scale with number of
140    /// FRI queries.
141    pub constraint_eval: PhantomData<usize>,
142}
143
144impl FriVerifierCostEstimate {
145    pub fn new(
146        params: VerifierCostParameters,
147        fri_params: FriParameters,
148        ext_degree: usize,
149    ) -> Self {
150        // Go through different rounds: preprocessed, main, permutation, quotient
151
152        // TODO: ignoring preprocessed trace opening for now
153
154        // Main
155        // Currently assumes opening at just zeta, omega * zeta
156        let mut open_input = FriOpenInputCostEstimate::new(
157            params.num_main_columns,
158            params.log_max_height,
159            2,
160            fri_params,
161        );
162        let mut query = FriQueryCostEstimate::new(params.log_max_height, fri_params);
163
164        // Permutation
165        // Currently assumes opening at just zeta, omega * zeta
166        open_input = open_input
167            + FriOpenInputCostEstimate::new(
168                params.num_perm_columns,
169                params.log_max_height,
170                2,
171                fri_params,
172            );
173        query = query + FriQueryCostEstimate::new(params.log_max_height, fri_params);
174
175        // Add quotient polynomial opening contribution
176        // Quotient only opens at single point zeta
177        open_input = open_input
178            + FriOpenInputCostEstimate::new(
179                params.quotient_degree * ext_degree,
180                params.log_max_height,
181                1,
182                fri_params,
183            );
184        query = query + FriQueryCostEstimate::new(params.log_max_height, fri_params);
185
186        Self {
187            open_input,
188            query,
189            constraint_eval: PhantomData,
190        }
191    }
192
193    pub fn from_vk<SC: StarkGenericConfig>(
194        vks: &[&StarkVerifyingKey<Val<SC>, Com<SC>>],
195        fri_params: FriParameters,
196        log_max_height: usize,
197    ) -> Self {
198        let num_main_columns: usize = vks
199            .iter()
200            .map(|vk| {
201                vk.params.width.common_main + vk.params.width.cached_mains.iter().sum::<usize>()
202            })
203            .sum();
204        let ext_degree = <SC::Challenge as FieldExtensionAlgebra<Val<SC>>>::D;
205        let num_perm_columns: usize = vks
206            .iter()
207            .map(|vk| vk.params.width.after_challenge.iter().sum::<usize>())
208            .sum::<usize>()
209            * ext_degree;
210        let quotient_degree = vks.iter().map(|vk| vk.quotient_degree).max().unwrap_or(0) as usize;
211        Self::new(
212            VerifierCostParameters {
213                num_main_columns,
214                num_perm_columns,
215                log_max_height,
216                quotient_degree,
217            },
218            fri_params,
219            ext_degree,
220        )
221    }
222}
openvm_stark_sdk/cost_estimate.rs

openvm_stark_sdk/
cost_estimate.rs
