openvm_stark_backend/keygen/
types.rs

Help
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
37#[derive(Clone, Debug, Serialize, Deserialize)]
38#[repr(C)]
39pub struct StarkVerifyingParams {
40    /// Trace sub-matrix widths
41    pub width: TraceWidth,
42    /// Number of public values for this STARK only
43    pub num_public_values: usize,
44    /// Number of values to expose to verifier in each trace challenge phase
45    pub num_exposed_values_after_challenge: Vec<usize>,
46    /// For only this RAP, how many challenges are needed in each trace challenge phase
47    pub num_challenges_to_sample: Vec<usize>,
48}
49
50/// Verifier data for preprocessed trace for a single AIR.
51///
52/// Currently assumes each AIR has it's own preprocessed commitment
53#[derive(Clone, Serialize, Deserialize)]
54pub struct VerifierSinglePreprocessedData<Com> {
55    /// Commitment to the preprocessed trace.
56    pub commit: Com,
57}
58
59/// Verifying key for a single STARK (corresponding to single AIR matrix)
60#[derive(Clone, Serialize, Deserialize)]
61#[repr(C)]
62pub struct StarkVerifyingKey<Val, Com> {
63    /// Preprocessed trace data, if any
64    pub preprocessed_data: Option<VerifierSinglePreprocessedData<Com>>,
65    /// Parameters of the STARK
66    pub params: StarkVerifyingParams,
67    /// Symbolic constraints of the AIR in all challenge phases. This is
68    /// a serialization of the constraints in the AIR.
69    pub symbolic_constraints: SymbolicConstraintsDag<Val>,
70    /// The factor to multiple the trace degree by to get the degree of the quotient polynomial. Determined from the max constraint degree of the AIR constraints.
71    /// This is equivalently the number of chunks the quotient polynomial is split into.
72    pub quotient_degree: u8,
73    pub rap_phase_seq_kind: RapPhaseSeqKind,
74}
75
76/// Common verifying key for multiple AIRs.
77///
78/// This struct contains the necessary data for the verifier to verify proofs generated for
79/// multiple AIRs using a single verifying key.
80#[derive(Derivative, Serialize, Deserialize)]
81#[derivative(Clone(bound = "Com<SC>: Clone"))]
82#[serde(bound(
83    serialize = "Com<SC>: Serialize",
84    deserialize = "Com<SC>: Deserialize<'de>"
85))]
86pub struct MultiStarkVerifyingKey<SC: StarkGenericConfig> {
87    /// All parts of the verifying key needed by the verifier, except
88    /// the `pre_hash` used to initialize the Fiat-Shamir transcript.
89    pub inner: MultiStarkVerifyingKey0<SC>,
90    /// The hash of all other parts of the verifying key. The Fiat-Shamir hasher will
91    /// initialize by observing this hash.
92    pub pre_hash: Com<SC>,
93}
94
95/// Everything in [MultiStarkVerifyingKey] except the `pre_hash` used to initialize the Fiat-Shamir transcript.
96#[derive(Derivative, Serialize, Deserialize)]
97#[derivative(Clone(bound = "Com<SC>: Clone"))]
98#[serde(bound(
99    serialize = "Com<SC>: Serialize",
100    deserialize = "Com<SC>: Deserialize<'de>"
101))]
102pub struct MultiStarkVerifyingKey0<SC: StarkGenericConfig> {
103    pub per_air: Vec<StarkVerifyingKey<Val<SC>, Com<SC>>>,
104    pub trace_height_constraints: Vec<LinearConstraint>,
105    pub log_up_pow_bits: usize,
106}
107
108#[derive(Serialize, Deserialize, Clone, Debug, PartialEq, Eq)]
109pub struct LinearConstraint {
110    pub coefficients: Vec<u32>,
111    pub threshold: u32,
112}
113
114/// Proving key for a single STARK (corresponding to single AIR matrix)
115#[derive(Serialize, Deserialize, Derivative)]
116#[derivative(Clone(bound = "Com<SC>: Clone"))]
117#[serde(bound(
118    serialize = "PcsProverData<SC>: Serialize",
119    deserialize = "PcsProverData<SC>: Deserialize<'de>"
120))]
121pub struct StarkProvingKey<SC: StarkGenericConfig> {
122    /// Type name of the AIR, for display purposes only
123    pub air_name: String,
124    /// Verifying key
125    pub vk: StarkVerifyingKey<Val<SC>, Com<SC>>,
126    /// Prover only data for preprocessed trace
127    pub preprocessed_data: Option<ProverOnlySinglePreprocessedData<SC>>,
128    /// Partial proving key for RAP partial proving in challenge phases
129    pub rap_partial_pk: RapPartialProvingKey<SC>,
130}
131
132/// Common proving key for multiple AIRs.
133///
134/// This struct contains the necessary data for the prover to generate proofs for multiple AIRs
135/// using a single proving key.
136#[derive(Serialize, Deserialize, Derivative)]
137#[derivative(Clone(bound = "Com<SC>: Clone"))]
138#[serde(bound(
139    serialize = "PcsProverData<SC>: Serialize",
140    deserialize = "PcsProverData<SC>: Deserialize<'de>"
141))]
142pub struct MultiStarkProvingKey<SC: StarkGenericConfig> {
143    pub per_air: Vec<StarkProvingKey<SC>>,
144    pub trace_height_constraints: Vec<LinearConstraint>,
145    /// Maximum degree of constraints across all AIRs
146    pub max_constraint_degree: usize,
147    pub log_up_pow_bits: usize,
148    /// See [MultiStarkVerifyingKey]
149    pub vk_pre_hash: Com<SC>,
150}
151
152impl<Val, Com> StarkVerifyingKey<Val, Com> {
153    pub fn num_cached_mains(&self) -> usize {
154        self.params.width.cached_mains.len()
155    }
156
157    pub fn has_common_main(&self) -> bool {
158        self.params.width.common_main != 0
159    }
160
161    pub fn has_interaction(&self) -> bool {
162        !self.symbolic_constraints.interactions.is_empty()
163    }
164}
165
166impl<SC: StarkGenericConfig> MultiStarkProvingKey<SC> {
167    pub fn get_vk(&self) -> MultiStarkVerifyingKey<SC> {
168        MultiStarkVerifyingKey {
169            inner: self.get_vk0(),
170            pre_hash: self.vk_pre_hash.clone(),
171        }
172    }
173
174    fn get_vk0(&self) -> MultiStarkVerifyingKey0<SC> {
175        MultiStarkVerifyingKey0 {
176            per_air: self.per_air.iter().map(|pk| pk.vk.clone()).collect(),
177            trace_height_constraints: self.trace_height_constraints.clone(),
178            log_up_pow_bits: self.log_up_pow_bits,
179        }
180    }
181}
182impl<SC: StarkGenericConfig> MultiStarkVerifyingKey<SC> {
183    pub fn num_challenges_per_phase(&self) -> Vec<usize> {
184        self.full_view().num_challenges_per_phase()
185    }
186}
187
188/// Prover only data for preprocessed trace for a single AIR.
189/// Currently assumes each AIR has it's own preprocessed commitment
190#[derive(Serialize, Deserialize, Derivative)]
191#[derivative(Clone(bound = "Com<SC>: Clone"))]
192#[serde(bound(
193    serialize = "PcsProverData<SC>: Serialize",
194    deserialize = "PcsProverData<SC>: Deserialize<'de>"
195))]
196pub struct ProverOnlySinglePreprocessedData<SC: StarkGenericConfig> {
197    /// Preprocessed trace matrix.
198    pub trace: Arc<RowMajorMatrix<Val<SC>>>,
199    /// Prover data, such as a Merkle tree, for the trace commitment.
200    pub data: Arc<PcsProverData<SC>>,
201}
openvm_stark_backend/keygen/types.rs

openvm_stark_backend/keygen/
types.rs
