openvm_stark_backend/soundness/
vk.rs

1use p3_util::log2_ceil_usize;
2
3use super::{base_field_order, challenge_field_bits, SoundnessCalculator};
4use crate::{keygen::types::MultiStarkVerifyingKey, StarkProtocolConfig};
5
6impl SoundnessCalculator {
7    /// Computes a conservative soundness estimate for the verifier defined by the given `vk`.
8    ///
9    /// The verifying key does not fix a single proof shape: optional AIRs may be absent and trace
10    /// heights can vary within verifier-enforced bounds. This function therefore uses verifier-side
11    /// upper bounds derived from the key.
12    pub fn calculate_from_vk<SC: StarkProtocolConfig>(vk: &MultiStarkVerifyingKey<SC>) -> Self {
13        let params = &vk.inner.params;
14        let num_airs = vk.inner.per_air.len();
15        let mut max_constraints_per_air = 0;
16        let mut max_interactions_per_air = 0;
17        let mut num_trace_columns_bound = 0;
18
19        for air_vk in &vk.inner.per_air {
20            max_constraints_per_air = max_constraints_per_air
21                .max(air_vk.symbolic_constraints.constraints.constraint_idx.len());
22            max_interactions_per_air =
23                max_interactions_per_air.max(air_vk.symbolic_constraints.interactions.len());
24            num_trace_columns_bound += air_vk.params.width.total_width();
25        }
26
27        let n_logup = calculate_n_logup_bound_from_interaction_limit(
28            params.l_skip,
29            params.logup.max_interaction_count as usize,
30        )
31        .min(calculate_n_logup_bound_from_vk_shape(
32            params.l_skip,
33            num_airs,
34            max_interactions_per_air,
35            params.log_stacked_height(),
36        ));
37
38        Self::calculate(
39            params,
40            base_field_order::<SC>(),
41            challenge_field_bits::<SC>(),
42            max_constraints_per_air,
43            num_airs,
44            params.max_constraint_degree,
45            params.log_stacked_height(),
46            num_trace_columns_bound,
47            params.w_stack,
48            n_logup,
49        )
50    }
51}
52
53fn calculate_n_logup_bound_from_interaction_limit(
54    l_skip: usize,
55    max_interaction_count: usize,
56) -> usize {
57    if max_interaction_count == 0 {
58        return 0;
59    }
60    log2_ceil_usize(max_interaction_count).saturating_sub(l_skip)
61}
62
63fn calculate_n_logup_bound_from_vk_shape(
64    l_skip: usize,
65    num_airs: usize,
66    max_interactions_per_air: usize,
67    max_log_trace_height: usize,
68) -> usize {
69    if num_airs == 0 || max_interactions_per_air == 0 {
70        return 0;
71    }
72
73    (log2_ceil_usize(num_airs) + log2_ceil_usize(max_interactions_per_air) + max_log_trace_height)
74        .saturating_sub(l_skip)
75}
76
77#[cfg(test)]
78mod tests {
79    use p3_baby_bear::BabyBear;
80    use p3_field::{extension::BinomialExtensionField, PrimeCharacteristicRing};
81
82    use crate::{
83        air_builders::symbolic::{
84            SymbolicConstraintsDag, SymbolicExpressionDag, SymbolicExpressionNode,
85        },
86        hasher::MerkleHasher,
87        interaction::Interaction,
88        keygen::types::{
89            MultiStarkVerifyingKey, MultiStarkVerifyingKey0, StarkVerifyingKey,
90            StarkVerifyingParams, TraceWidth,
91        },
92        soundness::{base_field_order, challenge_field_bits, SoundnessCalculator},
93        test_utils::default_test_params_small,
94        StarkProtocolConfig,
95    };
96
97    #[derive(Clone, Debug)]
98    struct DummyHasher;
99
100    impl MerkleHasher for DummyHasher {
101        type F = BabyBear;
102        type Digest = [BabyBear; 1];
103
104        fn hash_slice(&self, _vals: &[Self::F]) -> Self::Digest {
105            [BabyBear::ZERO]
106        }
107
108        fn compress(&self, _left: Self::Digest, _right: Self::Digest) -> Self::Digest {
109            [BabyBear::ZERO]
110        }
111    }
112
113    #[derive(Clone, Debug)]
114    struct DummyConfig {
115        params: crate::SystemParams,
116    }
117
118    impl StarkProtocolConfig for DummyConfig {
119        type F = BabyBear;
120        type EF = BinomialExtensionField<BabyBear, 4>;
121        type Digest = [BabyBear; 1];
122        type Hasher = DummyHasher;
123
124        fn params(&self) -> &crate::SystemParams {
125            &self.params
126        }
127
128        fn hasher(&self) -> &Self::Hasher {
129            static HASHER: DummyHasher = DummyHasher;
130            &HASHER
131        }
132    }
133
134    fn constraints_with_counts(
135        num_constraints: usize,
136        num_interactions: usize,
137    ) -> SymbolicConstraintsDag<BabyBear> {
138        let mut nodes = Vec::new();
139        let mut constraint_idx = Vec::new();
140        for i in 0..num_constraints {
141            nodes.push(SymbolicExpressionNode::Constant(BabyBear::from_usize(
142                i + 1,
143            )));
144            constraint_idx.push(i);
145        }
146        let base_idx = nodes.len();
147        let interactions = (0..num_interactions)
148            .map(|i| {
149                nodes.push(SymbolicExpressionNode::Constant(BabyBear::from_usize(
150                    i + 11,
151                )));
152                nodes.push(SymbolicExpressionNode::Constant(BabyBear::ONE));
153                Interaction {
154                    message: vec![base_idx + 2 * i],
155                    count: base_idx + 2 * i + 1,
156                    bus_index: 0,
157                    count_weight: 0,
158                }
159            })
160            .collect();
161
162        SymbolicConstraintsDag {
163            constraints: SymbolicExpressionDag {
164                nodes,
165                constraint_idx,
166            },
167            interactions,
168        }
169    }
170
171    fn test_vk() -> MultiStarkVerifyingKey<DummyConfig> {
172        let params = default_test_params_small();
173        MultiStarkVerifyingKey::<DummyConfig> {
174            inner: MultiStarkVerifyingKey0 {
175                params,
176                per_air: vec![
177                    StarkVerifyingKey {
178                        preprocessed_data: None,
179                        params: StarkVerifyingParams {
180                            width: TraceWidth {
181                                preprocessed: None,
182                                cached_mains: vec![],
183                                common_main: 2,
184                            },
185                            num_public_values: 3,
186                            need_rot: false,
187                        },
188                        symbolic_constraints: constraints_with_counts(4, 0),
189                        max_constraint_degree: 1,
190                        is_required: true,
191                        unused_variables: vec![],
192                    },
193                    StarkVerifyingKey {
194                        preprocessed_data: None,
195                        params: StarkVerifyingParams {
196                            width: TraceWidth {
197                                preprocessed: None,
198                                cached_mains: vec![],
199                                common_main: 2,
200                            },
201                            num_public_values: 0,
202                            need_rot: false,
203                        },
204                        symbolic_constraints: constraints_with_counts(0, 1),
205                        max_constraint_degree: 1,
206                        is_required: true,
207                        unused_variables: vec![],
208                    },
209                    StarkVerifyingKey {
210                        preprocessed_data: None,
211                        params: StarkVerifyingParams {
212                            width: TraceWidth {
213                                preprocessed: None,
214                                cached_mains: vec![],
215                                common_main: 2,
216                            },
217                            num_public_values: 0,
218                            need_rot: false,
219                        },
220                        symbolic_constraints: constraints_with_counts(0, 1),
221                        max_constraint_degree: 1,
222                        is_required: true,
223                        unused_variables: vec![],
224                    },
225                ],
226                trace_height_constraints: vec![crate::keygen::types::LinearConstraint {
227                    coefficients: vec![0, 1, 1],
228                    threshold: 1 << 30,
229                }],
230            },
231            pre_hash: [BabyBear::ZERO],
232        }
233    }
234
235    #[test]
236    fn calculates_vk_soundness_from_verifier_bounds() {
237        let vk = test_vk();
238        let params = vk.inner.params.clone();
239        let soundness = SoundnessCalculator::calculate_from_vk(&vk);
240
241        let expected = SoundnessCalculator::calculate(
242            &params,
243            base_field_order::<DummyConfig>(),
244            challenge_field_bits::<DummyConfig>(),
245            4,
246            3,
247            params.max_constraint_degree,
248            params.log_stacked_height(),
249            6,
250            params.w_stack,
251            10,
252        );
253
254        assert_eq!(soundness.total_bits, expected.total_bits);
255        assert_eq!(
256            soundness.constraint_batching_bits,
257            expected.constraint_batching_bits
258        );
259    }
260}
openvm_stark_backend/soundness/vk.rs

openvm_stark_backend/soundness/
vk.rs
