stwo_gpu/core/
proof.rs

1use core::mem;
2use core::ops::Deref;
3
4use serde::{Deserialize, Serialize};
5use std_shims::Vec;
6
7use crate::core::circle::CirclePoint;
8use crate::core::fields::m31::BaseField;
9use crate::core::fields::qm31::{SecureField, SECURE_EXTENSION_DEGREE};
10use crate::core::fri::{FriLayerProof, FriProof};
11use crate::core::pcs::quotients::{CommitmentSchemeProof, CommitmentSchemeProofAux};
12use crate::core::vcs::hash::Hash;
13use crate::core::vcs_lifted::merkle_hasher::MerkleHasherLifted;
14use crate::core::vcs_lifted::verifier::MerkleDecommitmentLifted;
15
16#[derive(Clone, Debug, Serialize, Deserialize)]
17pub struct StarkProof<H: MerkleHasherLifted>(pub CommitmentSchemeProof<H>);
18
19#[derive(Clone, Debug, Serialize, Deserialize)]
20pub struct ExtendedStarkProof<H: MerkleHasherLifted> {
21    pub proof: StarkProof<H>,
22    pub aux: CommitmentSchemeProofAux<H>,
23}
24
25impl<H: MerkleHasherLifted> StarkProof<H> {
26    /// Extracts the composition trace Out-Of-Domain-Sample evaluation from the mask.
27    pub(crate) fn extract_composition_oods_eval(
28        &self,
29        oods_point: CirclePoint<SecureField>,
30        composition_log_size: u32,
31    ) -> Option<SecureField> {
32        // TODO(andrew): `[.., composition_mask, _quotients_mask]` when add quotients
33        // commitment.
34        let [.., left_and_right_composition_mask] = &**self.sampled_values else {
35            return None;
36        };
37        let left_and_right_coordinate_evals: [SecureField; 2 * SECURE_EXTENSION_DEGREE] =
38            left_and_right_composition_mask
39                .iter()
40                .map(|columns| {
41                    let &[eval] = &columns[..] else {
42                        return None;
43                    };
44                    Some(eval)
45                })
46                .collect::<Option<Vec<_>>>()?
47                .try_into()
48                .ok()?;
49
50        let (left_coordinate_evals, right_coordinate_evals) =
51            left_and_right_coordinate_evals.split_at(SECURE_EXTENSION_DEGREE);
52
53        let left_eval = SecureField::from_partial_evals(left_coordinate_evals.try_into().ok()?);
54        let right_eval = SecureField::from_partial_evals(right_coordinate_evals.try_into().ok()?);
55        let value = left_eval + oods_point.repeated_double(composition_log_size - 2).x * right_eval;
56        Some(value)
57    }
58
59    /// Returns the estimate size (in bytes) of the proof.
60    pub fn size_estimate(&self) -> usize {
61        SizeEstimate::size_estimate(self)
62    }
63
64    /// Returns size estimates (in bytes) for different parts of the proof.
65    pub fn size_breakdown_estimate(&self) -> StarkProofSizeBreakdown {
66        let Self(commitment_scheme_proof) = self;
67
68        let CommitmentSchemeProof {
69            commitments,
70            sampled_values,
71            decommitments,
72            queried_values,
73            proof_of_work: _,
74            fri_proof,
75            config: _,
76        } = commitment_scheme_proof;
77
78        let FriProof {
79            first_layer,
80            inner_layers,
81            last_layer_poly,
82        } = fri_proof;
83
84        let mut inner_layers_samples_size = 0;
85        let mut inner_layers_hashes_size = 0;
86
87        for FriLayerProof {
88            fri_witness,
89            decommitment,
90            commitment,
91        } in inner_layers
92        {
93            inner_layers_samples_size += fri_witness.size_estimate();
94            inner_layers_hashes_size += decommitment.size_estimate() + commitment.size_estimate();
95        }
96
97        StarkProofSizeBreakdown {
98            oods_samples: sampled_values.size_estimate(),
99            queries_values: queried_values.size_estimate(),
100            fri_samples: last_layer_poly.size_estimate()
101                + inner_layers_samples_size
102                + first_layer.fri_witness.size_estimate(),
103            fri_decommitments: inner_layers_hashes_size
104                + first_layer.decommitment.size_estimate()
105                + first_layer.commitment.size_estimate(),
106            trace_decommitments: commitments.size_estimate() + decommitments.size_estimate(),
107        }
108    }
109}
110
111impl<H: MerkleHasherLifted> Deref for StarkProof<H> {
112    type Target = CommitmentSchemeProof<H>;
113
114    fn deref(&self) -> &CommitmentSchemeProof<H> {
115        &self.0
116    }
117}
118
119/// Size estimate (in bytes) for different parts of the proof.
120#[derive(Debug)]
121pub struct StarkProofSizeBreakdown {
122    pub oods_samples: usize,
123    pub queries_values: usize,
124    pub fri_samples: usize,
125    pub fri_decommitments: usize,
126    pub trace_decommitments: usize,
127}
128
129trait SizeEstimate {
130    fn size_estimate(&self) -> usize;
131}
132
133impl<T: SizeEstimate> SizeEstimate for [T] {
134    fn size_estimate(&self) -> usize {
135        self.iter().map(|v| v.size_estimate()).sum()
136    }
137}
138
139impl<T: SizeEstimate> SizeEstimate for Vec<T> {
140    fn size_estimate(&self) -> usize {
141        self.iter().map(|v| v.size_estimate()).sum()
142    }
143}
144
145impl<H: Hash> SizeEstimate for H {
146    fn size_estimate(&self) -> usize {
147        mem::size_of::<Self>()
148    }
149}
150
151impl SizeEstimate for BaseField {
152    fn size_estimate(&self) -> usize {
153        mem::size_of::<Self>()
154    }
155}
156
157impl SizeEstimate for SecureField {
158    fn size_estimate(&self) -> usize {
159        mem::size_of::<Self>()
160    }
161}
162
163impl<H: MerkleHasherLifted> SizeEstimate for MerkleDecommitmentLifted<H> {
164    fn size_estimate(&self) -> usize {
165        let Self { hash_witness } = self;
166        hash_witness.size_estimate()
167    }
168}
169
170impl<H: MerkleHasherLifted> SizeEstimate for FriLayerProof<H> {
171    fn size_estimate(&self) -> usize {
172        let Self {
173            fri_witness,
174            decommitment,
175            commitment,
176        } = self;
177        fri_witness.size_estimate() + decommitment.size_estimate() + commitment.size_estimate()
178    }
179}
180
181impl<H: MerkleHasherLifted> SizeEstimate for FriProof<H> {
182    fn size_estimate(&self) -> usize {
183        let Self {
184            first_layer,
185            inner_layers,
186            last_layer_poly,
187        } = self;
188        first_layer.size_estimate() + inner_layers.size_estimate() + last_layer_poly.size_estimate()
189    }
190}
191
192impl<H: MerkleHasherLifted> SizeEstimate for CommitmentSchemeProof<H> {
193    fn size_estimate(&self) -> usize {
194        let Self {
195            commitments,
196            sampled_values,
197            decommitments,
198            queried_values,
199            proof_of_work,
200            fri_proof,
201            config,
202        } = self;
203        commitments.size_estimate()
204            + sampled_values.size_estimate()
205            + decommitments.size_estimate()
206            + queried_values.size_estimate()
207            + mem::size_of_val(proof_of_work)
208            + fri_proof.size_estimate()
209            + mem::size_of_val(config)
210    }
211}
212
213impl<H: MerkleHasherLifted> SizeEstimate for StarkProof<H> {
214    fn size_estimate(&self) -> usize {
215        let Self(commitment_scheme_proof) = self;
216        commitment_scheme_proof.size_estimate()
217    }
218}
219
220#[cfg(test)]
221mod tests {
222    use num_traits::One;
223
224    use crate::core::fields::m31::BaseField;
225    use crate::core::fields::qm31::{SecureField, SECURE_EXTENSION_DEGREE};
226    use crate::core::proof::SizeEstimate;
227
228    #[test]
229    fn test_base_field_size_estimate() {
230        assert_eq!(BaseField::one().size_estimate(), 4);
231    }
232
233    #[test]
234    fn test_secure_field_size_estimate() {
235        assert_eq!(
236            SecureField::one().size_estimate(),
237            4 * SECURE_EXTENSION_DEGREE
238        );
239    }
240}
stwo_gpu/core/proof.rs

stwo_gpu/core/
proof.rs
