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 {
87            mmcs: MmcsVerifyBatchCostEstimate::from_dim(width, max_log_height),
88            num_ro_eval,
89        }
90    }
91}
92
93impl Add for FriOpenInputCostEstimate {
94    type Output = Self;
95
96    fn add(self, rhs: Self) -> Self::Output {
97        Self {
98            mmcs: self.mmcs + rhs.mmcs,
99            num_ro_eval: self.num_ro_eval + rhs.num_ro_eval,
100        }
101    }
102}
103
104pub struct FriQueryCostEstimate {
105    /// Cost from MMCS batch verification.
106    pub mmcs: MmcsVerifyBatchCostEstimate,
107    /// Number of single FRI fold evaluations: `e0 + (beta - xs[0]) * (e1 - e0) / (xs[1] - xs[0])`.
108    pub num_fri_folds: usize,
109}
110
111impl FriQueryCostEstimate {
112    /// `max_log_height` is the trace height, before blowup.
113    pub fn new(max_log_height: usize, fri_params: FriParameters) -> Self {
114        let mut mmcs = MmcsVerifyBatchCostEstimate {
115            num_f_to_hash: 2 * max_log_height,
116            num_compress: max_log_height * (max_log_height + fri_params.log_blowup - 1) / 2,
117        };
118        mmcs.num_compress *= fri_params.num_queries;
119        mmcs.num_f_to_hash *= fri_params.num_queries;
120        let num_fri_folds = max_log_height * fri_params.num_queries;
121        Self {
122            mmcs,
123            num_fri_folds,
124        }
125    }
126}
127
128impl Add for FriQueryCostEstimate {
129    type Output = Self;
130
131    fn add(self, rhs: Self) -> Self::Output {
132        Self {
133            mmcs: self.mmcs + rhs.mmcs,
134            num_fri_folds: self.num_fri_folds + rhs.num_fri_folds,
135        }
136    }
137}
138
139pub struct FriVerifierCostEstimate {
140    pub open_input: FriOpenInputCostEstimate,
141    pub query: FriQueryCostEstimate,
142    /// We currently ignore the constraint evaluation cost because it does not scale with number of
143    /// FRI queries.
144    pub constraint_eval: PhantomData<usize>,
145}
146
147impl FriVerifierCostEstimate {
148    pub fn new(
149        params: VerifierCostParameters,
150        fri_params: FriParameters,
151        ext_degree: usize,
152    ) -> Self {
153        // Go through different rounds: preprocessed, main, permutation, quotient
154
155        // TODO: ignoring preprocessed trace opening for now
156
157        // Main
158        // Currently assumes opening at just zeta, omega * zeta
159        let mut open_input = FriOpenInputCostEstimate::new(
160            params.num_main_columns,
161            params.log_max_height,
162            2,
163            fri_params,
164        );
165        let mut query = FriQueryCostEstimate::new(params.log_max_height, fri_params);
166
167        // Permutation
168        // Currently assumes opening at just zeta, omega * zeta
169        open_input = open_input
170            + FriOpenInputCostEstimate::new(
171                params.num_perm_columns,
172                params.log_max_height,
173                2,
174                fri_params,
175            );
176        query = query + FriQueryCostEstimate::new(params.log_max_height, fri_params);
177
178        // Add quotient polynomial opening contribution
179        // Quotient only opens at single point zeta
180        open_input = open_input
181            + FriOpenInputCostEstimate::new(
182                params.quotient_degree * ext_degree,
183                params.log_max_height,
184                1,
185                fri_params,
186            );
187        query = query + FriQueryCostEstimate::new(params.log_max_height, fri_params);
188
189        Self {
190            open_input,
191            query,
192            constraint_eval: PhantomData,
193        }
194    }
195
196    pub fn from_vk<SC: StarkGenericConfig>(
197        vks: &[&StarkVerifyingKey<Val<SC>, Com<SC>>],
198        fri_params: FriParameters,
199        log_max_height: usize,
200    ) -> Self {
201        let num_main_columns: usize = vks
202            .iter()
203            .map(|vk| {
204                vk.params.width.common_main + vk.params.width.cached_mains.iter().sum::<usize>()
205            })
206            .sum();
207        let ext_degree = <SC::Challenge as FieldExtensionAlgebra<Val<SC>>>::D;
208        let num_perm_columns: usize = vks
209            .iter()
210            .map(|vk| vk.params.width.after_challenge.iter().sum::<usize>())
211            .sum::<usize>()
212            * ext_degree;
213        let quotient_degree = vks.iter().map(|vk| vk.quotient_degree).max().unwrap_or(0) as usize;
214        Self::new(
215            VerifierCostParameters {
216                num_main_columns,
217                num_perm_columns,
218                log_max_height,
219                quotient_degree,
220            },
221            fri_params,
222            ext_degree,
223        )
224    }
225}
openvm_stark_sdk/cost_estimate.rs

openvm_stark_sdk/
cost_estimate.rs
