openvm_stark_backend/keygen/
types.rs

1// NOTE[jpw]: copied from stark-backend but renamed for , now generic in SC
2
3// Keygen API for STARK backend
4// Changes:
5// - All AIRs can be optional
6use std::sync::Arc;
7
8use derivative::Derivative;
9use serde::{Deserialize, Serialize};
10use thiserror::Error;
11
12use crate::{
13    air_builders::symbolic::{symbolic_variable::SymbolicVariable, SymbolicConstraintsDag},
14    prover::stacked_pcs::StackedPcsData,
15    StarkProtocolConfig, SystemParams,
16};
17
18/// Widths of different parts of trace matrix
19#[derive(Clone, Debug, Serialize, Deserialize)]
20pub struct TraceWidth {
21    pub preprocessed: Option<usize>,
22    pub cached_mains: Vec<usize>,
23    pub common_main: 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 and main width.
43    pub fn total_width(&self) -> usize {
44        self.preprocessed.unwrap_or(0) + self.main_width()
45    }
46}
47
48#[derive(Serialize, Deserialize, Clone, Debug, PartialEq, Eq)]
49pub struct LinearConstraint {
50    pub coefficients: Vec<u32>,
51    pub threshold: u32,
52}
53
54impl LinearConstraint {
55    /// Returns true if `self` is logically implied by `other`, i.e.,
56    /// whenever `other` is satisfied, `self` is also satisfied.
57    pub fn is_implied_by(&self, other: &LinearConstraint) -> bool {
58        self.threshold >= other.threshold
59            && self
60                .coefficients
61                .iter()
62                .zip(&other.coefficients)
63                .all(|(a, b)| a <= b)
64    }
65}
66
67#[derive(Error, Debug)]
68pub enum KeygenError {
69    #[error("AIR {name} has zero main trace width")]
70    AirWidthZero { name: String },
71    #[error("AIR {name} must have at least one constraint or interaction")]
72    AirNoConstraintsOrInteractions { name: String },
73    #[error("AIR {name} interaction {interaction_index} has a zero-length message")]
74    InteractionMessageEmpty {
75        name: String,
76        interaction_index: usize,
77    },
78    #[error("Max constraint degree exceeded for AIR {name}: {degree} > {max_degree}")]
79    MaxConstraintDegreeExceeded {
80        name: String,
81        degree: usize,
82        max_degree: usize,
83    },
84}
85
86#[derive(Clone, Debug, Serialize, Deserialize)]
87#[repr(C)]
88pub struct StarkVerifyingParams {
89    /// Trace sub-matrix widths
90    pub width: TraceWidth,
91    /// Number of public values for this STARK only
92    pub num_public_values: usize,
93    /// A flag indicating whether at least one rotated variable is used in any
94    /// of the constraints and/or interactions across all trace parts (common,
95    /// preprocessed if there is one, all cached).
96    pub need_rot: bool,
97}
98
99/// Verifier data for preprocessed trace for a single AIR.
100///
101/// Currently assumes each AIR has it's own preprocessed commitment
102#[derive(Clone, Debug, Serialize, Deserialize)]
103pub struct VerifierSinglePreprocessedData<Digest> {
104    /// Commitment to the preprocessed trace.
105    pub commit: Digest,
106    /// The hypercube dimension of the preprocessed data _before stacking_ (log_height -
107    /// vk.l_skip).
108    pub hypercube_dim: isize,
109    /// The width of the data after stacking.
110    pub stacking_width: usize,
111}
112
113/// Verifying key for a single STARK (corresponding to single AIR matrix)
114#[derive(Clone, Debug, Serialize, Deserialize)]
115#[repr(C)]
116pub struct StarkVerifyingKey<F, Digest> {
117    /// Preprocessed trace data, if any
118    pub preprocessed_data: Option<VerifierSinglePreprocessedData<Digest>>,
119    /// Parameters of the STARK
120    pub params: StarkVerifyingParams,
121    /// Symbolic constraints of the AIR in all challenge phases. This is
122    /// a serialization of the constraints in the AIR.
123    pub symbolic_constraints: SymbolicConstraintsDag<F>,
124    /// The maximum degree of any polynomial (constraint or interaction) for this AIR.
125    pub max_constraint_degree: u8,
126    /// True means this AIR must have non-empty trace.
127    pub is_required: bool,
128    /// Symbolic variables referenced unreferenced by the AIR.
129    pub unused_variables: Vec<SymbolicVariable<F>>,
130}
131
132/// Common verifying key for multiple AIRs.
133///
134/// This struct contains the necessary data for the verifier to verify proofs generated for
135/// multiple AIRs using a single verifying key.
136#[derive(Derivative, Serialize, Deserialize)]
137#[derivative(Clone(bound = ""), Debug(bound = ""))]
138#[serde(bound = "")]
139pub struct MultiStarkVerifyingKey<SC: StarkProtocolConfig> {
140    /// All parts of the verifying key needed by the verifier, except
141    /// the `pre_hash` used to initialize the Fiat-Shamir transcript.
142    pub inner: MultiStarkVerifyingKey0<SC>,
143    /// The hash of all other parts of the verifying key. The Fiat-Shamir hasher will
144    /// initialize by observing this hash.
145    pub pre_hash: SC::Digest,
146}
147
148/// Everything in [MultiStarkVerifyingKey] except the `pre_hash` used to initialize the Fiat-Shamir
149/// transcript.
150#[derive(Derivative, Serialize, Deserialize)]
151#[derivative(Clone(bound = ""), Debug(bound = ""))]
152#[serde(bound = "")]
153pub struct MultiStarkVerifyingKey0<SC: StarkProtocolConfig> {
154    pub params: SystemParams,
155    pub per_air: Vec<StarkVerifyingKey<SC::F, SC::Digest>>,
156    pub trace_height_constraints: Vec<LinearConstraint>,
157}
158
159/// Proving key for a single STARK (corresponding to single AIR matrix)
160#[derive(Derivative, Serialize, Deserialize)]
161#[derivative(Clone(bound = ""))]
162#[serde(bound = "")]
163pub struct StarkProvingKey<SC: StarkProtocolConfig> {
164    /// Type name of the AIR, for display purposes only
165    pub air_name: String,
166    /// Verifying key
167    pub vk: StarkVerifyingKey<SC::F, SC::Digest>,
168    /// Prover only data for preprocessed trace
169    pub preprocessed_data: Option<Arc<StackedPcsData<SC::F, SC::Digest>>>,
170}
171
172/// Common proving key for multiple AIRs.
173///
174/// This struct contains the necessary data for the prover to generate proofs for multiple AIRs
175/// using a single proving key.
176#[derive(Derivative, Serialize, Deserialize)]
177#[derivative(Clone(bound = ""))]
178#[serde(bound = "")]
179pub struct MultiStarkProvingKey<SC: StarkProtocolConfig> {
180    pub per_air: Vec<StarkProvingKey<SC>>,
181    pub trace_height_constraints: Vec<LinearConstraint>,
182    /// Maximum degree of constraints across all AIRs
183    pub max_constraint_degree: usize,
184    pub params: SystemParams,
185    /// See [MultiStarkVerifyingKey]
186    pub vk_pre_hash: SC::Digest,
187}
188
189impl<Val, Com> StarkVerifyingKey<Val, Com> {
190    pub fn num_cached_mains(&self) -> usize {
191        self.params.width.cached_mains.len()
192    }
193
194    pub fn num_parts(&self) -> usize {
195        1 + self.num_cached_mains() + (self.preprocessed_data.is_some() as usize)
196    }
197
198    pub fn has_interaction(&self) -> bool {
199        !self.symbolic_constraints.interactions.is_empty()
200    }
201
202    pub fn num_interactions(&self) -> usize {
203        self.symbolic_constraints.interactions.len()
204    }
205
206    /// Converts from a main part index (as used by the constraint DAG) to the
207    /// commitment part indexing scheme that includes preprocessed trace.
208    pub fn dag_main_part_index_to_commit_index(&self, index: usize) -> usize {
209        // In the dag, common main is the final part index.
210        if index == self.num_cached_mains() {
211            0
212        } else {
213            index + 1 + self.preprocessed_data.is_some() as usize
214        }
215    }
216}
217
218impl<SC: StarkProtocolConfig> MultiStarkProvingKey<SC> {
219    pub fn get_vk(&self) -> MultiStarkVerifyingKey<SC> {
220        MultiStarkVerifyingKey {
221            inner: self.get_vk0(),
222            pre_hash: self.vk_pre_hash,
223        }
224    }
225
226    fn get_vk0(&self) -> MultiStarkVerifyingKey0<SC> {
227        MultiStarkVerifyingKey0 {
228            params: self.params.clone(),
229            per_air: self.per_air.iter().map(|pk| pk.vk.clone()).collect(),
230            trace_height_constraints: self.trace_height_constraints.clone(),
231        }
232    }
233}
234
235impl<SC: StarkProtocolConfig> MultiStarkVerifyingKey<SC> {
236    /// Global maximum constraint degree across all AIRs and Interactions.
237    pub fn max_constraint_degree(&self) -> usize {
238        self.inner.max_constraint_degree()
239    }
240}
241
242impl<SC: StarkProtocolConfig> MultiStarkVerifyingKey0<SC> {
243    pub fn max_constraint_degree(&self) -> usize {
244        self.params.max_constraint_degree
245    }
246}
openvm_stark_backend/keygen/types.rs

openvm_stark_backend/keygen/
types.rs
