openvm_stark_backend/keygen/
types.rs

1// Keygen API for STARK backend
2// Changes:
3// - All AIRs can be optional
4use std::sync::Arc;
5
6use derivative::Derivative;
7use p3_matrix::dense::RowMajorMatrix;
8use serde::{Deserialize, Serialize};
9
10use crate::{
11    air_builders::symbolic::SymbolicConstraintsDag,
12    config::{Com, PcsProverData, RapPartialProvingKey, StarkGenericConfig, Val},
13    interaction::RapPhaseSeqKind,
14};
15
16/// Widths of different parts of trace matrix
17#[derive(Clone, Debug, Serialize, Deserialize)]
18pub struct TraceWidth {
19    pub preprocessed: Option<usize>,
20    pub cached_mains: Vec<usize>,
21    pub common_main: usize,
22    /// Width counted by extension field elements, _not_ base field elements
23    pub after_challenge: Vec<usize>,
24}
25
26impl TraceWidth {
27    /// Returns the widths of all main traces, including the common main trace if it exists.
28    pub fn main_widths(&self) -> Vec<usize> {
29        let mut ret = self.cached_mains.clone();
30        if self.common_main != 0 {
31            ret.push(self.common_main);
32        }
33        ret
34    }
35
36    /// Returns the width of the main trace, i.e., the sum of all cached main widths and the common
37    /// main width.
38    pub fn main_width(&self) -> usize {
39        self.cached_mains.iter().sum::<usize>() + self.common_main
40    }
41
42    /// Total width of the trace matrix, including the preprocessed width, main width, and
43    /// after-challenge widths.
44    pub fn total_width(&self, ext_degree: usize) -> usize {
45        self.preprocessed.unwrap_or(0)
46            + self.main_width()
47            + self.after_challenge.iter().sum::<usize>() * ext_degree
48    }
49}
50
51#[derive(Clone, Debug, Serialize, Deserialize)]
52#[repr(C)]
53pub struct StarkVerifyingParams {
54    /// Trace sub-matrix widths
55    pub width: TraceWidth,
56    /// Number of public values for this STARK only
57    pub num_public_values: usize,
58    /// Number of values to expose to verifier in each trace challenge phase
59    pub num_exposed_values_after_challenge: Vec<usize>,
60    /// For only this RAP, how many challenges are needed in each trace challenge phase
61    pub num_challenges_to_sample: Vec<usize>,
62}
63
64/// Verifier data for preprocessed trace for a single AIR.
65///
66/// Currently assumes each AIR has it's own preprocessed commitment
67#[derive(Clone, Serialize, Deserialize)]
68pub struct VerifierSinglePreprocessedData<Com> {
69    /// Commitment to the preprocessed trace.
70    pub commit: Com,
71}
72
73/// Verifying key for a single STARK (corresponding to single AIR matrix)
74#[derive(Clone, Serialize, Deserialize)]
75#[repr(C)]
76pub struct StarkVerifyingKey<Val, Com> {
77    /// Preprocessed trace data, if any
78    pub preprocessed_data: Option<VerifierSinglePreprocessedData<Com>>,
79    /// Parameters of the STARK
80    pub params: StarkVerifyingParams,
81    /// Symbolic constraints of the AIR in all challenge phases. This is
82    /// a serialization of the constraints in the AIR.
83    pub symbolic_constraints: SymbolicConstraintsDag<Val>,
84    /// The factor to multiply the trace degree by to get the degree of the quotient polynomial.
85    /// Determined from the max constraint degree of the AIR constraints. This is equivalently
86    /// the number of chunks the quotient polynomial is split into.
87    pub quotient_degree: u8,
88    pub rap_phase_seq_kind: RapPhaseSeqKind,
89}
90
91/// Common verifying key for multiple AIRs.
92///
93/// This struct contains the necessary data for the verifier to verify proofs generated for
94/// multiple AIRs using a single verifying key.
95#[derive(Derivative, Serialize, Deserialize)]
96#[derivative(Clone(bound = "Com<SC>: Clone"))]
97#[serde(bound(
98    serialize = "Com<SC>: Serialize",
99    deserialize = "Com<SC>: Deserialize<'de>"
100))]
101pub struct MultiStarkVerifyingKey<SC: StarkGenericConfig> {
102    /// All parts of the verifying key needed by the verifier, except
103    /// the `pre_hash` used to initialize the Fiat-Shamir transcript.
104    pub inner: MultiStarkVerifyingKey0<SC>,
105    /// The hash of all other parts of the verifying key. The Fiat-Shamir hasher will
106    /// initialize by observing this hash.
107    pub pre_hash: Com<SC>,
108}
109
110/// Everything in [MultiStarkVerifyingKey] except the `pre_hash` used to initialize the Fiat-Shamir
111/// transcript.
112#[derive(Derivative, Serialize, Deserialize)]
113#[derivative(Clone(bound = "Com<SC>: Clone"))]
114#[serde(bound(
115    serialize = "Com<SC>: Serialize",
116    deserialize = "Com<SC>: Deserialize<'de>"
117))]
118pub struct MultiStarkVerifyingKey0<SC: StarkGenericConfig> {
119    pub per_air: Vec<StarkVerifyingKey<Val<SC>, Com<SC>>>,
120    pub trace_height_constraints: Vec<LinearConstraint>,
121    pub log_up_pow_bits: usize,
122    pub deep_pow_bits: usize,
123}
124
125#[derive(Serialize, Deserialize, Clone, Debug, PartialEq, Eq)]
126pub struct LinearConstraint {
127    pub coefficients: Vec<u32>,
128    pub threshold: u32,
129}
130
131/// Proving key for a single STARK (corresponding to single AIR matrix)
132#[derive(Serialize, Deserialize, Derivative)]
133#[derivative(Clone(bound = "Com<SC>: Clone"))]
134#[serde(bound(
135    serialize = "PcsProverData<SC>: Serialize",
136    deserialize = "PcsProverData<SC>: Deserialize<'de>"
137))]
138pub struct StarkProvingKey<SC: StarkGenericConfig> {
139    /// Type name of the AIR, for display purposes only
140    pub air_name: String,
141    /// Verifying key
142    pub vk: StarkVerifyingKey<Val<SC>, Com<SC>>,
143    /// Prover only data for preprocessed trace
144    pub preprocessed_data: Option<ProverOnlySinglePreprocessedData<SC>>,
145    /// Partial proving key for RAP partial proving in challenge phases
146    pub rap_partial_pk: RapPartialProvingKey<SC>,
147}
148
149/// Common proving key for multiple AIRs.
150///
151/// This struct contains the necessary data for the prover to generate proofs for multiple AIRs
152/// using a single proving key.
153#[derive(Serialize, Deserialize, Derivative)]
154#[derivative(Clone(bound = "Com<SC>: Clone"))]
155#[serde(bound(
156    serialize = "PcsProverData<SC>: Serialize",
157    deserialize = "PcsProverData<SC>: Deserialize<'de>"
158))]
159pub struct MultiStarkProvingKey<SC: StarkGenericConfig> {
160    pub per_air: Vec<StarkProvingKey<SC>>,
161    pub trace_height_constraints: Vec<LinearConstraint>,
162    /// Maximum degree of constraints across all AIRs
163    pub max_constraint_degree: usize,
164    pub log_up_pow_bits: usize,
165    pub deep_pow_bits: usize,
166    /// See [MultiStarkVerifyingKey]
167    pub vk_pre_hash: Com<SC>,
168}
169
170impl<Val, Com> StarkVerifyingKey<Val, Com> {
171    pub fn num_cached_mains(&self) -> usize {
172        self.params.width.cached_mains.len()
173    }
174
175    pub fn has_common_main(&self) -> bool {
176        self.params.width.common_main != 0
177    }
178
179    pub fn has_interaction(&self) -> bool {
180        !self.symbolic_constraints.interactions.is_empty()
181    }
182}
183
184impl<SC: StarkGenericConfig> MultiStarkProvingKey<SC> {
185    pub fn get_vk(&self) -> MultiStarkVerifyingKey<SC> {
186        MultiStarkVerifyingKey {
187            inner: self.get_vk0(),
188            pre_hash: self.vk_pre_hash.clone(),
189        }
190    }
191
192    fn get_vk0(&self) -> MultiStarkVerifyingKey0<SC> {
193        MultiStarkVerifyingKey0 {
194            per_air: self.per_air.iter().map(|pk| pk.vk.clone()).collect(),
195            trace_height_constraints: self.trace_height_constraints.clone(),
196            log_up_pow_bits: self.log_up_pow_bits,
197            deep_pow_bits: self.deep_pow_bits,
198        }
199    }
200}
201impl<SC: StarkGenericConfig> MultiStarkVerifyingKey<SC> {
202    pub fn num_challenges_per_phase(&self) -> Vec<usize> {
203        self.full_view().num_challenges_per_phase()
204    }
205
206    pub fn main_widths(&self) -> Vec<usize> {
207        self.full_view().main_widths()
208    }
209
210    pub fn total_widths(&self) -> Vec<usize> {
211        self.full_view().total_widths::<SC::Challenge>()
212    }
213
214    pub fn num_interactions(&self) -> Vec<usize> {
215        self.full_view().num_interactions()
216    }
217}
218
219/// Prover only data for preprocessed trace for a single AIR.
220/// Currently assumes each AIR has it's own preprocessed commitment
221#[derive(Serialize, Deserialize, Derivative)]
222#[derivative(Clone(bound = "Com<SC>: Clone"))]
223#[serde(bound(
224    serialize = "PcsProverData<SC>: Serialize",
225    deserialize = "PcsProverData<SC>: Deserialize<'de>"
226))]
227pub struct ProverOnlySinglePreprocessedData<SC: StarkGenericConfig> {
228    /// Preprocessed trace matrix.
229    pub trace: Arc<RowMajorMatrix<Val<SC>>>,
230    /// Prover data, such as a Merkle tree, for the trace commitment.
231    pub data: Arc<PcsProverData<SC>>,
232}
openvm_stark_backend/keygen/types.rs

openvm_stark_backend/keygen/
types.rs
