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}
123
124#[derive(Serialize, Deserialize, Clone, Debug, PartialEq, Eq)]
125pub struct LinearConstraint {
126    pub coefficients: Vec<u32>,
127    pub threshold: u32,
128}
129
130/// Proving key for a single STARK (corresponding to single AIR matrix)
131#[derive(Serialize, Deserialize, Derivative)]
132#[derivative(Clone(bound = "Com<SC>: Clone"))]
133#[serde(bound(
134    serialize = "PcsProverData<SC>: Serialize",
135    deserialize = "PcsProverData<SC>: Deserialize<'de>"
136))]
137pub struct StarkProvingKey<SC: StarkGenericConfig> {
138    /// Type name of the AIR, for display purposes only
139    pub air_name: String,
140    /// Verifying key
141    pub vk: StarkVerifyingKey<Val<SC>, Com<SC>>,
142    /// Prover only data for preprocessed trace
143    pub preprocessed_data: Option<ProverOnlySinglePreprocessedData<SC>>,
144    /// Partial proving key for RAP partial proving in challenge phases
145    pub rap_partial_pk: RapPartialProvingKey<SC>,
146}
147
148/// Common proving key for multiple AIRs.
149///
150/// This struct contains the necessary data for the prover to generate proofs for multiple AIRs
151/// using a single proving key.
152#[derive(Serialize, Deserialize, Derivative)]
153#[derivative(Clone(bound = "Com<SC>: Clone"))]
154#[serde(bound(
155    serialize = "PcsProverData<SC>: Serialize",
156    deserialize = "PcsProverData<SC>: Deserialize<'de>"
157))]
158pub struct MultiStarkProvingKey<SC: StarkGenericConfig> {
159    pub per_air: Vec<StarkProvingKey<SC>>,
160    pub trace_height_constraints: Vec<LinearConstraint>,
161    /// Maximum degree of constraints across all AIRs
162    pub max_constraint_degree: usize,
163    pub log_up_pow_bits: usize,
164    /// See [MultiStarkVerifyingKey]
165    pub vk_pre_hash: Com<SC>,
166}
167
168impl<Val, Com> StarkVerifyingKey<Val, Com> {
169    pub fn num_cached_mains(&self) -> usize {
170        self.params.width.cached_mains.len()
171    }
172
173    pub fn has_common_main(&self) -> bool {
174        self.params.width.common_main != 0
175    }
176
177    pub fn has_interaction(&self) -> bool {
178        !self.symbolic_constraints.interactions.is_empty()
179    }
180}
181
182impl<SC: StarkGenericConfig> MultiStarkProvingKey<SC> {
183    pub fn get_vk(&self) -> MultiStarkVerifyingKey<SC> {
184        MultiStarkVerifyingKey {
185            inner: self.get_vk0(),
186            pre_hash: self.vk_pre_hash.clone(),
187        }
188    }
189
190    fn get_vk0(&self) -> MultiStarkVerifyingKey0<SC> {
191        MultiStarkVerifyingKey0 {
192            per_air: self.per_air.iter().map(|pk| pk.vk.clone()).collect(),
193            trace_height_constraints: self.trace_height_constraints.clone(),
194            log_up_pow_bits: self.log_up_pow_bits,
195        }
196    }
197}
198impl<SC: StarkGenericConfig> MultiStarkVerifyingKey<SC> {
199    pub fn num_challenges_per_phase(&self) -> Vec<usize> {
200        self.full_view().num_challenges_per_phase()
201    }
202
203    pub fn main_widths(&self) -> Vec<usize> {
204        self.full_view().main_widths()
205    }
206
207    pub fn total_widths(&self) -> Vec<usize> {
208        self.full_view().total_widths::<SC::Challenge>()
209    }
210
211    pub fn num_interactions(&self) -> Vec<usize> {
212        self.full_view().num_interactions()
213    }
214}
215
216/// Prover only data for preprocessed trace for a single AIR.
217/// Currently assumes each AIR has it's own preprocessed commitment
218#[derive(Serialize, Deserialize, Derivative)]
219#[derivative(Clone(bound = "Com<SC>: Clone"))]
220#[serde(bound(
221    serialize = "PcsProverData<SC>: Serialize",
222    deserialize = "PcsProverData<SC>: Deserialize<'de>"
223))]
224pub struct ProverOnlySinglePreprocessedData<SC: StarkGenericConfig> {
225    /// Preprocessed trace matrix.
226    pub trace: Arc<RowMajorMatrix<Val<SC>>>,
227    /// Prover data, such as a Merkle tree, for the trace commitment.
228    pub data: Arc<PcsProverData<SC>>,
229}
openvm_stark_backend/keygen/types.rs

openvm_stark_backend/keygen/
types.rs
