lib_q_zkp/
stark.rs

1//! zk-STARK implementation
2//!
3//! This module provides a high-level interface to lib-Q's zk-STARK implementation.
4//!
5//! The STARK implementation is based on Plonky3, adapted for lib-Q's requirements:
6//! - Uses SHAKE256 (NIST-approved post-quantum hash) instead of non-NIST hashes
7//! - Supports `Complex<Mersenne31>` field for efficient arithmetic (TWO_ADICITY = 32)
8//! - Implements the ethSTARK protocol for strong security guarantees
9
10extern crate alloc;
11use alloc::vec::Vec;
12use core::result::Result;
13
14use lib_q_stark::{
15    Domain,
16    Proof as StarkProof,
17    StarkConfig,
18    StarkGenericConfig,
19    SymbolicAirBuilder,
20    Val,
21    VerificationError,
22    get_log_num_quotient_chunks,
23    prove,
24    verify,
25};
26use lib_q_stark_air::Air;
27use lib_q_stark_challenger::{
28    CanObserve,
29    CanSampleBits,
30    ComplexFieldChallenger,
31    FieldChallenger,
32    GrindingChallenger,
33    Shake256Challenger32,
34};
35use lib_q_stark_commit::{
36    ExtensionMmcs,
37    Pcs,
38    PolynomialSpace,
39};
40use lib_q_stark_field::extension::Complex;
41use lib_q_stark_field::{
42    BasedVectorSpace,
43    PrimeCharacteristicRing,
44};
45use lib_q_stark_fri::{
46    FriDataExtractor,
47    TwoAdicFriPcs,
48};
49use lib_q_stark_matrix::dense::RowMajorMatrix;
50use lib_q_stark_merkle::MerkleTreeMmcs;
51use lib_q_stark_mersenne31::{
52    Mersenne31,
53    Mersenne31ComplexRadix2Dit,
54};
55use lib_q_stark_shake256::Shake256Hash;
56use lib_q_stark_symmetric::{
57    CompressionFunctionFromHasher,
58    SerializingHasher,
59};
60
61// Concrete config type aliases (used as return types for config factory functions).
62// Public so that pub type DefaultConfig/ZkConfig/PoseidonConfig satisfy private_interfaces.
63pub type ConfigVal = Complex<Mersenne31>;
64pub type ConfigDft = Mersenne31ComplexRadix2Dit;
65pub type DefaultValMmcs = MerkleTreeMmcs<
66    <ConfigVal as lib_q_stark_field::Field>::Packing,
67    u8,
68    SerializingHasher<Shake256Hash>,
69    CompressionFunctionFromHasher<Shake256Hash, 2, 32>,
70    32,
71>;
72pub type DefaultChallengeMmcs = ExtensionMmcs<ConfigVal, ConfigVal, DefaultValMmcs>;
73pub type DefaultPcs = TwoAdicFriPcs<ConfigVal, ConfigDft, DefaultValMmcs, DefaultChallengeMmcs>;
74pub type DefaultConfig =
75    StarkConfig<DefaultPcs, ConfigVal, ComplexFieldChallenger<Shake256Challenger32<Mersenne31>>>;
76
77#[cfg(feature = "recursive-proofs-experimental")]
78use lib_q_stark_merkle::PoseidonMmcs as PoseidonMmcsType;
79#[cfg(feature = "recursive-proofs-experimental")]
80pub type PoseidonChallengeMmcs = ExtensionMmcs<ConfigVal, ConfigVal, PoseidonMmcsType>;
81#[cfg(feature = "recursive-proofs-experimental")]
82pub type PoseidonPcs = TwoAdicFriPcs<ConfigVal, ConfigDft, PoseidonMmcsType, PoseidonChallengeMmcs>;
83#[cfg(feature = "recursive-proofs-experimental")]
84pub type PoseidonConfig =
85    StarkConfig<PoseidonPcs, ConfigVal, ComplexFieldChallenger<Shake256Challenger32<Mersenne31>>>;
86
87use lib_q_stark_fri::HidingFriPcs;
88use lib_q_stark_merkle::MerkleTreeHidingMmcs;
89pub type ZkValMmcs = MerkleTreeHidingMmcs<
90    <ConfigVal as lib_q_stark_field::Field>::Packing,
91    u8,
92    SerializingHasher<Shake256Hash>,
93    CompressionFunctionFromHasher<Shake256Hash, 2, 32>,
94    lib_q_random::DeterministicRng,
95    32,
96    4,
97>;
98pub type ZkChallengeMmcs = ExtensionMmcs<ConfigVal, ConfigVal, ZkValMmcs>;
99pub type ZkPcs =
100    HidingFriPcs<ConfigVal, ConfigDft, ZkValMmcs, ZkChallengeMmcs, lib_q_random::DeterministicRng>;
101pub type ZkConfig =
102    StarkConfig<ZkPcs, ConfigVal, ComplexFieldChallenger<Shake256Challenger32<Mersenne31>>>;
103
104/// FRI query parameters used when replaying the verifier (e.g. for recursive aggregation).
105#[derive(Clone, Debug)]
106pub struct FriQueryParams {
107    pub num_queries: usize,
108    pub log_blowup: usize,
109    pub log_final_poly_len: usize,
110    pub proof_of_work_bits: usize,
111}
112
113// Generic type aliases for StarkVerifier (`C: StarkGenericConfig` on the alias is stable Rust).
114type PcsCommitment<C: StarkGenericConfig> =
115    <C::Pcs as Pcs<C::Challenge, C::Challenger>>::Commitment;
116
117type CommitmentRounds<C: StarkGenericConfig> = Vec<(
118    PcsCommitment<C>,
119    Vec<(Domain<C>, Vec<(C::Challenge, Vec<C::Challenge>)>)>,
120)>;
121
122type QuotientRounds<C: StarkGenericConfig> =
123    Vec<(Domain<C>, Vec<(C::Challenge, Vec<C::Challenge>)>)>;
124
125/// zk-STARK prover
126///
127/// This is a high-level wrapper around the STARK proving functionality.
128/// It provides a convenient interface for generating STARK proofs with a given configuration.
129///
130/// # Example
131///
132/// ```rust,ignore
133/// use lib_q_zkp::stark::{StarkProver, default_config};
134/// use Complex;
135/// use Mersenne31;
136///
137/// type Val = Complex<Mersenne31>;
138///
139/// let config = default_config();
140/// let prover = StarkProver::new(config);
141/// // air: implements Air trait
142/// // trace: RowMajorMatrix<Val>
143/// // public_values: &[Val]
144/// let proof = prover.prove(&air, trace, &public_values);
145/// ```
146pub struct StarkProver<C: StarkGenericConfig> {
147    config: C,
148}
149
150impl<C: StarkGenericConfig> StarkProver<C> {
151    /// Create a new zk-STARK prover with the given configuration
152    pub fn new(config: C) -> Self {
153        Self { config }
154    }
155
156    /// Generate a STARK proof for the given AIR, trace, and public values
157    ///
158    /// # Arguments
159    ///
160    /// * `air` - The Algebraic Intermediate Representation defining the constraints
161    /// * `trace` - The witness trace matrix (contains secret data)
162    /// * `public_values` - Public values known to both prover and verifier
163    ///
164    /// # Returns
165    ///
166    /// A STARK proof that can be verified without revealing the witness trace
167    #[cfg(not(debug_assertions))]
168    pub fn prove<A>(
169        &self,
170        air: &A,
171        trace: RowMajorMatrix<Val<C>>,
172        public_values: &[Val<C>],
173    ) -> Result<StarkProof<C>, lib_q_stark::ProverError>
174    where
175        A: Air<SymbolicAirBuilder<Val<C>>>
176            + for<'a> Air<lib_q_stark::ProverConstraintFolder<'a, C>>,
177    {
178        prove(&self.config, air, trace, public_values)
179    }
180
181    #[cfg(debug_assertions)]
182    pub fn prove<A>(
183        &self,
184        air: &A,
185        trace: RowMajorMatrix<Val<C>>,
186        public_values: &[Val<C>],
187    ) -> Result<StarkProof<C>, lib_q_stark::ProverError>
188    where
189        A: Air<SymbolicAirBuilder<Val<C>>>
190            + for<'a> Air<lib_q_stark::ProverConstraintFolder<'a, C>>
191            + for<'a> Air<lib_q_stark::DebugConstraintBuilder<'a, Val<C>>>,
192    {
193        prove(&self.config, air, trace, public_values)
194    }
195
196    /// Get a reference to the underlying configuration
197    pub fn config(&self) -> &C {
198        &self.config
199    }
200}
201
202/// zk-STARK verifier
203///
204/// This is a high-level wrapper around the STARK verification functionality.
205/// It provides a convenient interface for verifying STARK proofs with a given configuration.
206///
207/// # Example
208///
209/// ```rust,ignore
210/// use lib_q_zkp::stark::{StarkVerifier, default_config};
211/// use Complex;
212/// use Mersenne31;
213///
214/// type Val = Complex<Mersenne31>;
215///
216/// let config = default_config();
217/// let verifier = StarkVerifier::new(config);
218/// // air: implements Air trait (same as used in proof generation)
219/// // proof: StarkProof<Config>
220/// // public_values: &[Val]
221/// verifier.verify(&air, &proof, &public_values)?;
222/// ```
223pub struct StarkVerifier<C: StarkGenericConfig> {
224    config: C,
225}
226
227impl<C: StarkGenericConfig> StarkVerifier<C> {
228    /// Create a new zk-STARK verifier with the given configuration
229    pub fn new(config: C) -> Self {
230        Self { config }
231    }
232
233    /// Verify a STARK proof for the given AIR and public values
234    ///
235    /// # Arguments
236    ///
237    /// * `air` - The Algebraic Intermediate Representation that was used to generate the proof
238    /// * `proof` - The STARK proof to verify
239    /// * `public_values` - Public values that were used during proof generation
240    ///
241    /// # Returns
242    ///
243    /// `Ok(())` if the proof is valid, `Err(VerificationError)` otherwise
244    pub fn verify<A>(
245        &self,
246        air: &A,
247        proof: &StarkProof<C>,
248        public_values: &[Val<C>],
249    ) -> Result<(), VerificationError<lib_q_stark::PcsError<C>>>
250    where
251        A: Air<SymbolicAirBuilder<Val<C>>>
252            + for<'a> Air<lib_q_stark::VerifierConstraintFolder<'a, C>>,
253    {
254        verify(&self.config, air, proof, public_values)
255    }
256
257    /// Derive Fiat–Shamir challenges by replaying the verifier transcript.
258    ///
259    /// Returns `(zeta, zeta_next, alpha, betas)` so that callers (e.g. aggregation)
260    /// can serialize proofs with real challenges. Only supports proofs without
261    /// preprocessed trace (`preprocessed_width == 0`).
262    #[allow(clippy::type_complexity)]
263    pub fn derive_challenges<A>(
264        &self,
265        air: &A,
266        proof: &StarkProof<C>,
267        public_values: &[Val<C>],
268    ) -> Result<
269        (
270            C::Challenge,
271            C::Challenge,
272            C::Challenge,
273            Vec<C::Challenge>,
274        ),
275        VerificationError<lib_q_stark::PcsError<C>>,
276    >
277    where
278        A: Air<SymbolicAirBuilder<Val<C>>>
279            + for<'a> Air<lib_q_stark::VerifierConstraintFolder<'a, C>>,
280        <<C as StarkGenericConfig>::Pcs as Pcs<C::Challenge, C::Challenger>>::Proof:
281            FriDataExtractor<Challenge = C::Challenge>,
282        C::Challenger: CanObserve<Val<C>>
283            + CanObserve<<C::Pcs as Pcs<C::Challenge, C::Challenger>>::Commitment>
284            + CanObserve<
285                <<<C as StarkGenericConfig>::Pcs as Pcs<C::Challenge, C::Challenger>>::Proof as FriDataExtractor>::Commitment,
286            >,
287    {
288        let config = &self.config;
289        let pcs = config.pcs();
290        let commitments = &proof.commitments;
291        let opened_values = &proof.opened_values;
292        let opening_proof = &proof.opening_proof;
293        let degree_bits = proof.degree_bits;
294
295        let preprocessed_width = air
296            .preprocessed_trace()
297            .as_ref()
298            .map(|m| m.width)
299            .unwrap_or(0);
300        if preprocessed_width > 0 {
301            return Err(VerificationError::InvalidProofShape);
302        }
303
304        let degree = 1 << degree_bits;
305        if degree == 0 {
306            return Err(VerificationError::InvalidProofShape);
307        }
308
309        let trace_domain: Domain<C> = pcs.natural_domain_for_degree(degree);
310        let init_trace_domain = pcs.natural_domain_for_degree(degree >> config.is_zk());
311
312        let log_num_quotient_chunks = get_log_num_quotient_chunks::<Val<C>, A>(
313            air,
314            preprocessed_width,
315            public_values.len(),
316            config.is_zk(),
317        );
318        let num_quotient_chunks = 1 << (log_num_quotient_chunks + config.is_zk());
319
320        if (opened_values.random.is_some() != C::Pcs::ZK) ||
321            (commitments.random.is_some() != C::Pcs::ZK)
322        {
323            return Err(VerificationError::RandomizationError);
324        }
325
326        let air_width = A::width(air);
327        let valid_shape = opened_values.trace_local.len() == air_width &&
328            opened_values.trace_next.len() == air_width &&
329            opened_values.quotient_chunks.len() == num_quotient_chunks &&
330            opened_values
331                .quotient_chunks
332                .iter()
333                .all(|qc| qc.len() == C::Challenge::DIMENSION) &&
334            opened_values
335                .random
336                .as_ref()
337                .is_none_or(|r| r.len() == C::Challenge::DIMENSION);
338        if !valid_shape {
339            return Err(VerificationError::InvalidProofShape);
340        }
341
342        let quotient_domain =
343            trace_domain.create_disjoint_domain(1 << (degree_bits + log_num_quotient_chunks));
344        let quotient_chunks_domains = quotient_domain.split_domains(num_quotient_chunks);
345        let randomized_quotient_chunks_domains: Vec<Domain<C>> = quotient_chunks_domains
346            .iter()
347            .map(|d: &Domain<C>| pcs.natural_domain_for_degree(d.size() << config.is_zk()))
348            .collect();
349
350        let mut challenger = config.initialise_challenger();
351
352        challenger.observe(Val::<C>::from_usize(degree_bits));
353        challenger.observe(Val::<C>::from_usize(degree_bits - config.is_zk()));
354        challenger.observe(Val::<C>::from_usize(preprocessed_width));
355        challenger.observe(Val::<C>::from_usize(A::width(air)));
356        challenger.observe(commitments.trace.clone());
357        challenger.observe_slice(public_values);
358
359        let alpha = challenger.sample_algebra_element();
360        challenger.observe(commitments.quotient_chunks.clone());
361        if let Some(ref r_commit) = commitments.random {
362            challenger.observe(r_commit.clone());
363        }
364
365        let zeta = challenger.sample_algebra_element();
366        let zeta_next = init_trace_domain
367            .next_point(zeta)
368            .ok_or(VerificationError::NextPointUnavailable)?;
369
370        let mut coms_to_verify: CommitmentRounds<C> =
371            if let Some(ref random_commit) = commitments.random {
372                let random_values = opened_values
373                    .random
374                    .as_ref()
375                    .ok_or(VerificationError::RandomizationError)?;
376                alloc::vec![(
377                    random_commit.clone(),
378                    alloc::vec![(trace_domain, alloc::vec![(zeta, random_values.clone())],)],
379                )]
380            } else {
381                alloc::vec![]
382            };
383
384        coms_to_verify.push((
385            commitments.trace.clone(),
386            alloc::vec![(
387                trace_domain,
388                alloc::vec![
389                    (zeta, opened_values.trace_local.clone()),
390                    (zeta_next, opened_values.trace_next.clone()),
391                ],
392            )],
393        ));
394
395        let quotient_rounds: QuotientRounds<C> = randomized_quotient_chunks_domains
396            .iter()
397            .zip(opened_values.quotient_chunks.iter())
398            .map(|(domain, values)| (*domain, alloc::vec![(zeta, values.clone())]))
399            .collect();
400        coms_to_verify.push((commitments.quotient_chunks.clone(), quotient_rounds));
401
402        for (_, round) in &coms_to_verify {
403            for (_, mat) in round {
404                for (_, point) in mat {
405                    for opening in point {
406                        challenger.observe_algebra_element(*opening);
407                    }
408                }
409            }
410        }
411
412        let _alpha_fri = challenger.sample_algebra_element::<C::Challenge>();
413
414        let betas: Vec<C::Challenge> = opening_proof
415            .commit_phase_commits()
416            .iter()
417            .map(|comm| {
418                challenger.observe(comm.clone());
419                challenger.sample_algebra_element()
420            })
421            .collect();
422
423        Ok((zeta, zeta_next, alpha, betas))
424    }
425
426    /// Derive FRI query positions by replaying the Fiat–Shamir challenger through commitments,
427    /// FRI betas, final polynomial, and PoW, then sampling `num_queries` indices.
428    ///
429    /// Returns the same query indices the verifier would use when verifying the proof.
430    /// Call with the same FRI params used to produce the proof (e.g. from config).
431    pub fn derive_query_positions<A>(
432        &self,
433        air: &A,
434        proof: &StarkProof<C>,
435        public_values: &[Val<C>],
436        fri_params: &FriQueryParams,
437    ) -> Result<Vec<usize>, VerificationError<lib_q_stark::PcsError<C>>>
438    where
439        A: Air<SymbolicAirBuilder<Val<C>>>
440            + for<'a> Air<lib_q_stark::VerifierConstraintFolder<'a, C>>,
441        <<C as StarkGenericConfig>::Pcs as Pcs<C::Challenge, C::Challenger>>::Proof:
442            FriDataExtractor<Challenge = C::Challenge>,
443        C::Challenger: CanObserve<Val<C>>
444            + CanObserve<<C::Pcs as Pcs<C::Challenge, C::Challenger>>::Commitment>
445            + CanObserve<
446                <<<C as StarkGenericConfig>::Pcs as Pcs<C::Challenge, C::Challenger>>::Proof as FriDataExtractor>::Commitment,
447            >
448            + GrindingChallenger<
449                Witness = <<<C as StarkGenericConfig>::Pcs as Pcs<C::Challenge, C::Challenger>>::Proof as FriDataExtractor>::Witness,
450            >,
451        <<<C as StarkGenericConfig>::Pcs as Pcs<C::Challenge, C::Challenger>>::Proof as FriDataExtractor>::Witness: Clone,
452    {
453        let config = &self.config;
454        let pcs = config.pcs();
455        let commitments = &proof.commitments;
456        let opened_values = &proof.opened_values;
457        let opening_proof = &proof.opening_proof;
458        let degree_bits = proof.degree_bits;
459
460        let preprocessed_width = air
461            .preprocessed_trace()
462            .as_ref()
463            .map(|m| m.width)
464            .unwrap_or(0);
465        if preprocessed_width > 0 {
466            return Err(VerificationError::InvalidProofShape);
467        }
468
469        let degree = 1 << degree_bits;
470        if degree == 0 {
471            return Err(VerificationError::InvalidProofShape);
472        }
473
474        let log_num_quotient_chunks = get_log_num_quotient_chunks::<Val<C>, A>(
475            air,
476            preprocessed_width,
477            public_values.len(),
478            config.is_zk(),
479        );
480        let num_quotient_chunks = 1 << (log_num_quotient_chunks + config.is_zk());
481
482        if (opened_values.random.is_some() != C::Pcs::ZK) ||
483            (commitments.random.is_some() != C::Pcs::ZK)
484        {
485            return Err(VerificationError::RandomizationError);
486        }
487
488        let air_width = A::width(air);
489        let valid_shape = opened_values.trace_local.len() == air_width &&
490            opened_values.trace_next.len() == air_width &&
491            opened_values.quotient_chunks.len() == num_quotient_chunks &&
492            opened_values
493                .quotient_chunks
494                .iter()
495                .all(|qc| qc.len() == C::Challenge::DIMENSION) &&
496            opened_values
497                .random
498                .as_ref()
499                .is_none_or(|r| r.len() == C::Challenge::DIMENSION);
500        if !valid_shape {
501            return Err(VerificationError::InvalidProofShape);
502        }
503
504        let trace_domain: Domain<C> = pcs.natural_domain_for_degree(degree);
505        let init_trace_domain = pcs.natural_domain_for_degree(degree >> config.is_zk());
506        let quotient_domain =
507            trace_domain.create_disjoint_domain(1 << (degree_bits + log_num_quotient_chunks));
508        let quotient_chunks_domains = quotient_domain.split_domains(num_quotient_chunks);
509        let randomized_quotient_chunks_domains: Vec<Domain<C>> = quotient_chunks_domains
510            .iter()
511            .map(|d: &Domain<C>| pcs.natural_domain_for_degree(d.size() << config.is_zk()))
512            .collect();
513
514        let mut challenger = config.initialise_challenger();
515
516        challenger.observe(Val::<C>::from_usize(degree_bits));
517        challenger.observe(Val::<C>::from_usize(degree_bits - config.is_zk()));
518        challenger.observe(Val::<C>::from_usize(preprocessed_width));
519        challenger.observe(Val::<C>::from_usize(A::width(air)));
520        challenger.observe(commitments.trace.clone());
521        challenger.observe_slice(public_values);
522
523        let _alpha: Val<C> = challenger.sample_algebra_element();
524        challenger.observe(commitments.quotient_chunks.clone());
525        if let Some(ref r_commit) = commitments.random {
526            challenger.observe(r_commit.clone());
527        }
528
529        let zeta = challenger.sample_algebra_element();
530        let _zeta_next = init_trace_domain
531            .next_point(zeta)
532            .ok_or(VerificationError::NextPointUnavailable)?;
533
534        let mut coms_to_verify: CommitmentRounds<C> =
535            if let Some(ref random_commit) = commitments.random {
536                let random_values = opened_values
537                    .random
538                    .as_ref()
539                    .ok_or(VerificationError::RandomizationError)?;
540                alloc::vec![(
541                    random_commit.clone(),
542                    alloc::vec![(trace_domain, alloc::vec![(zeta, random_values.clone())],)],
543                )]
544            } else {
545                alloc::vec![]
546            };
547
548        coms_to_verify.push((
549            commitments.trace.clone(),
550            alloc::vec![(
551                trace_domain,
552                alloc::vec![
553                    (zeta, opened_values.trace_local.clone()),
554                    (
555                        init_trace_domain
556                            .next_point(zeta)
557                            .ok_or(VerificationError::NextPointUnavailable)?,
558                        opened_values.trace_next.clone(),
559                    ),
560                ],
561            )],
562        ));
563
564        let quotient_rounds: QuotientRounds<C> = randomized_quotient_chunks_domains
565            .iter()
566            .zip(opened_values.quotient_chunks.iter())
567            .map(|(domain, values)| (*domain, alloc::vec![(zeta, values.clone())]))
568            .collect();
569        coms_to_verify.push((commitments.quotient_chunks.clone(), quotient_rounds));
570
571        for (_, round) in &coms_to_verify {
572            for (_, mat) in round {
573                for (_, point) in mat {
574                    for opening in point {
575                        challenger.observe_algebra_element(*opening);
576                    }
577                }
578            }
579        }
580
581        let _alpha_fri = challenger.sample_algebra_element::<C::Challenge>();
582
583        for comm in opening_proof.commit_phase_commits() {
584            challenger.observe(comm.clone());
585            let _beta: C::Challenge = challenger.sample_algebra_element();
586        }
587
588        for coeff in opening_proof.final_poly() {
589            challenger.observe_algebra_element(*coeff);
590        }
591
592        if !challenger.check_witness(
593            fri_params.proof_of_work_bits,
594            opening_proof.pow_witness().clone(),
595        ) {
596            return Err(VerificationError::InvalidProofShape);
597        }
598
599        let log_global_max_height = opening_proof.commit_phase_commits().len() +
600            fri_params.log_blowup +
601            fri_params.log_final_poly_len;
602        const EXTRA_QUERY_INDEX_BITS: usize = 0;
603
604        let mut positions = Vec::with_capacity(fri_params.num_queries);
605        for _ in 0..fri_params.num_queries {
606            let index = challenger.sample_bits(log_global_max_height + EXTRA_QUERY_INDEX_BITS);
607            positions.push(index);
608        }
609
610        Ok(positions)
611    }
612
613    /// Get a reference to the underlying configuration
614    pub fn config(&self) -> &C {
615        &self.config
616    }
617}
618
619/// Creates a production-ready default STARK configuration
620///
621/// This configuration uses:
622/// - **SHAKE256** for all hash operations (NIST-approved, post-quantum secure)
623/// - **`Complex<Mersenne31>`** field (TWO_ADICITY = 32) for efficient arithmetic
624/// - Production FRI parameters (100 queries, 16 proof-of-work bits)
625///
626/// # Example
627///
628/// ```rust,ignore
629/// use lib_q_zkp::stark::{default_config, StarkProver, StarkVerifier};
630///
631/// let config = default_config();
632/// let prover = StarkProver::new(config.clone());
633/// let verifier = StarkVerifier::new(config);
634/// ```
635pub fn default_config() -> DefaultConfig {
636    use lib_q_stark_fri::FriParameters;
637
638    type ValMmcs = DefaultValMmcs;
639    type ChallengeMmcs = DefaultChallengeMmcs;
640    type Dft = ConfigDft;
641    type Pcs = DefaultPcs;
642    type MyHash = SerializingHasher<Shake256Hash>;
643    type MyCompress = CompressionFunctionFromHasher<Shake256Hash, 2, 32>;
644    type BaseChallenger = Shake256Challenger32<Mersenne31>;
645    type Challenger = ComplexFieldChallenger<BaseChallenger>;
646
647    let shake256 = Shake256Hash {};
648    let hash = MyHash::new(shake256);
649    let compress = MyCompress::new(shake256);
650    let val_mmcs = ValMmcs::new(hash, compress);
651    let challenge_mmcs = ChallengeMmcs::new(val_mmcs.clone());
652    let dft = Dft::default();
653    let fri_params = FriParameters {
654        log_blowup: 2,
655        log_final_poly_len: 0,
656        num_queries: 100,
657        proof_of_work_bits: 16,
658        mmcs: challenge_mmcs,
659    };
660    let pcs = Pcs::new(dft, val_mmcs, fri_params);
661    let base_challenger = BaseChallenger::from_hasher(Vec::new(), Shake256Hash);
662    let challenger = Challenger::new(base_challenger);
663
664    StarkConfig::new(pcs, challenger)
665}
666
667/// STARK configuration for **tests and local development only**.
668///
669/// Same construction as [`default_config`], but FRI uses
670/// [`lib_q_stark_fri::create_test_fri_params`] (2 queries, 1 proof-of-work bit) so proving
671/// and verification complete quickly. **Do not use for production**; proofs are not
672/// production-sound and are incompatible with verifiers configured for [`default_config`].
673///
674/// Soundness is far below production; do not use this config to assert that verification
675/// **rejects** wrong public inputs (e.g. wrong Merkle root). For those negative tests, use
676/// [`default_config`] on prover and verifier.
677pub fn fast_proof_config() -> DefaultConfig {
678    use lib_q_stark_fri::create_test_fri_params;
679
680    type ValMmcs = DefaultValMmcs;
681    type ChallengeMmcs = DefaultChallengeMmcs;
682    type Dft = ConfigDft;
683    type Pcs = DefaultPcs;
684    type MyHash = SerializingHasher<Shake256Hash>;
685    type MyCompress = CompressionFunctionFromHasher<Shake256Hash, 2, 32>;
686    type BaseChallenger = Shake256Challenger32<Mersenne31>;
687    type Challenger = ComplexFieldChallenger<BaseChallenger>;
688
689    let shake256 = Shake256Hash {};
690    let hash = MyHash::new(shake256);
691    let compress = MyCompress::new(shake256);
692    let val_mmcs = ValMmcs::new(hash, compress);
693    let challenge_mmcs = ChallengeMmcs::new(val_mmcs.clone());
694    let dft = Dft::default();
695    let fri_params = create_test_fri_params(challenge_mmcs, 0);
696    let pcs = Pcs::new(dft, val_mmcs, fri_params);
697    let base_challenger = BaseChallenger::from_hasher(Vec::new(), Shake256Hash);
698    let challenger = Challenger::new(base_challenger);
699
700    StarkConfig::new(pcs, challenger)
701}
702
703/// STARK config that uses Poseidon-based Merkle trees (PoseidonMmcs).
704/// Use this as the outer config when producing recursive proofs so that Merkle paths
705/// are compatible with MerkleInclusionAir (Poseidon constraints in-circuit).
706#[cfg(feature = "recursive-proofs-experimental")]
707pub fn poseidon_config() -> PoseidonConfig {
708    use lib_q_stark_fri::FriParameters;
709    use lib_q_stark_merkle::{
710        PoseidonMmcs,
711        poseidon_mmcs_instance,
712    };
713
714    type ValMmcs = PoseidonMmcs;
715    type ChallengeMmcs = PoseidonChallengeMmcs;
716    type Dft = ConfigDft;
717    type Pcs = PoseidonPcs;
718    type BaseChallenger = Shake256Challenger32<Mersenne31>;
719    type Challenger = ComplexFieldChallenger<BaseChallenger>;
720
721    let (hash, compress) = poseidon_mmcs_instance();
722    let val_mmcs = ValMmcs::new(hash, compress);
723    let challenge_mmcs = ChallengeMmcs::new(val_mmcs.clone());
724    let dft = Dft::default();
725    let fri_params = FriParameters {
726        log_blowup: 2,
727        log_final_poly_len: 0,
728        num_queries: 100,
729        proof_of_work_bits: 16,
730        mmcs: challenge_mmcs,
731    };
732    let pcs = Pcs::new(dft, val_mmcs, fri_params);
733    let base_challenger = BaseChallenger::from_hasher(Vec::new(), Shake256Hash);
734    let challenger = Challenger::new(base_challenger);
735
736    StarkConfig::new(pcs, challenger)
737}
738
739/// Same PCS and challenger construction as [`poseidon_config`], but FRI uses
740/// [`lib_q_stark_fri::create_test_fri_params`] (2 queries, 1 proof-of-work bit) so recursive
741/// aggregation tests finish quickly. **Not for production**; incompatible with verifiers
742/// expecting [`poseidon_config`] FRI parameters.
743#[cfg(feature = "recursive-proofs-experimental")]
744pub fn poseidon_test_config() -> PoseidonConfig {
745    use lib_q_stark_fri::create_test_fri_params;
746    use lib_q_stark_merkle::{
747        PoseidonMmcs,
748        poseidon_mmcs_instance,
749    };
750
751    type ValMmcs = PoseidonMmcs;
752    type ChallengeMmcs = PoseidonChallengeMmcs;
753    type Dft = ConfigDft;
754    type Pcs = PoseidonPcs;
755    type BaseChallenger = Shake256Challenger32<Mersenne31>;
756    type Challenger = ComplexFieldChallenger<BaseChallenger>;
757
758    let (hash, compress) = poseidon_mmcs_instance();
759    let val_mmcs = ValMmcs::new(hash, compress);
760    let challenge_mmcs = ChallengeMmcs::new(val_mmcs.clone());
761    let dft = Dft::default();
762    let fri_params = create_test_fri_params(challenge_mmcs, 0);
763    let pcs = Pcs::new(dft, val_mmcs, fri_params);
764    let base_challenger = BaseChallenger::from_hasher(Vec::new(), Shake256Hash);
765    let challenger = Challenger::new(base_challenger);
766
767    StarkConfig::new(pcs, challenger)
768}
769
770/// Default FRI parameters used by `default_config()` (for security parameter tests).
771/// Returns (log_blowup, num_queries, proof_of_work_bits).
772#[doc(hidden)]
773pub const fn default_fri_params_for_tests() -> (usize, usize, usize) {
774    (2, 100, 16)
775}
776
777/// ZK config for tests: uses HidingFriPcs so proofs are randomized (statistical ZK).
778/// Not for production; uses test FRI params (few queries, low PoW).
779pub fn zk_config() -> ZkConfig {
780    zk_config_with_seeds(0, 1)
781}
782
783/// Same as `zk_config()` but with explicit RNG seeds (for tests that need distinct proofs).
784#[doc(hidden)]
785pub fn zk_config_with_seeds(val_mmcs_seed: u64, pcs_seed: u64) -> ZkConfig {
786    use lib_q_stark_fri::create_test_fri_params_zk;
787
788    type ValMmcs = ZkValMmcs;
789    type ChallengeMmcs = ZkChallengeMmcs;
790    type Dft = ConfigDft;
791    type Pcs = ZkPcs;
792    type MyHash = SerializingHasher<Shake256Hash>;
793    type MyCompress = CompressionFunctionFromHasher<Shake256Hash, 2, 32>;
794    type BaseChallenger = Shake256Challenger32<Mersenne31>;
795    type Challenger = ComplexFieldChallenger<BaseChallenger>;
796
797    let shake256 = Shake256Hash {};
798    let hash = MyHash::new(shake256);
799    let compress = MyCompress::new(shake256);
800    let val_mmcs = ValMmcs::new(
801        hash,
802        compress,
803        lib_q_random::DeterministicRng::seed_from_u64(val_mmcs_seed),
804    );
805    let challenge_mmcs = ChallengeMmcs::new(val_mmcs.clone());
806    let dft = Dft::default();
807    let fri_params = create_test_fri_params_zk(challenge_mmcs);
808    let pcs = Pcs::new(
809        dft,
810        val_mmcs,
811        fri_params,
812        4,
813        lib_q_random::DeterministicRng::seed_from_u64(pcs_seed),
814    );
815    let base_challenger = BaseChallenger::from_hasher(Vec::new(), Shake256Hash);
816    let challenger = Challenger::new(base_challenger);
817
818    StarkConfig::new(pcs, challenger)
819}
820
821#[cfg(test)]
822mod tests {
823    extern crate alloc;
824    use alloc::vec;
825
826    use super::*;
827    use crate::air::{
828        ArithmeticAir,
829        TraceGenerator,
830    };
831
832    fn sample_arithmetic_proof() -> (ArithmeticAir, StarkProof<DefaultConfig>, Vec<ConfigVal>) {
833        let air = ArithmeticAir::new(1).expect("ArithmeticAir");
834        let input = vec![(ConfigVal::ONE, ConfigVal::ONE)];
835        let trace = air.generate_trace(&input).expect("trace");
836        let public_values = air.public_values(&input);
837        let proof = StarkProver::new(default_config())
838            .prove(&air, trace, &public_values)
839            .expect("proof generation");
840        (air, proof, public_values)
841    }
842
843    #[test]
844    fn test_stark_prover_creation() {
845        let config = default_config();
846        let _prover = StarkProver::new(config);
847        // Just verify that creation doesn't panic
848    }
849
850    #[test]
851    fn test_stark_verifier_creation() {
852        let config = default_config();
853        let _verifier = StarkVerifier::new(config);
854        // Just verify that creation doesn't panic
855    }
856
857    #[test]
858    fn test_default_config() {
859        let _config = default_config();
860        // Just verify that config creation doesn't panic
861    }
862
863    #[test]
864    fn test_default_fri_params_for_tests_values() {
865        let (log_blowup, num_queries, proof_of_work_bits) = default_fri_params_for_tests();
866        assert_eq!(log_blowup, 2);
867        assert_eq!(num_queries, 100);
868        assert_eq!(proof_of_work_bits, 16);
869    }
870
871    #[test]
872    fn test_zk_config_builders_create_zk_configs() {
873        let zk_a = zk_config();
874        let zk_b = zk_config_with_seeds(11, 29);
875        assert_eq!(zk_a.is_zk(), 1);
876        assert_eq!(zk_b.is_zk(), 1);
877    }
878
879    #[test]
880    fn test_prover_and_verifier_config_accessors() {
881        let prover = StarkProver::new(default_config());
882        let verifier = StarkVerifier::new(default_config());
883        assert_eq!(prover.config().is_zk(), 0);
884        assert_eq!(verifier.config().is_zk(), 0);
885    }
886
887    #[test]
888    fn test_stark_prove_and_verify_roundtrip() {
889        let (air, proof, public_values) = sample_arithmetic_proof();
890        let verifier = StarkVerifier::new(default_config());
891        verifier
892            .verify(&air, &proof, &public_values)
893            .expect("proof should verify");
894    }
895
896    #[test]
897    fn test_derive_challenges_and_query_positions() {
898        let (air, proof, public_values) = sample_arithmetic_proof();
899        let verifier = StarkVerifier::new(default_config());
900
901        let (_zeta, _zeta_next, _alpha, betas) = verifier
902            .derive_challenges(&air, &proof, &public_values)
903            .expect("derive_challenges");
904
905        let (log_blowup, num_queries, proof_of_work_bits) = default_fri_params_for_tests();
906        assert!(betas.len() <= num_queries);
907        let fri_params = FriQueryParams {
908            num_queries,
909            log_blowup,
910            log_final_poly_len: 0,
911            proof_of_work_bits,
912        };
913        let positions = verifier
914            .derive_query_positions(&air, &proof, &public_values, &fri_params)
915            .expect("derive_query_positions");
916        assert_eq!(positions.len(), num_queries);
917    }
918
919    #[test]
920    fn test_derive_query_positions_rejects_wrong_public_values_shape() {
921        let (air, proof, _public_values) = sample_arithmetic_proof();
922        let verifier = StarkVerifier::new(default_config());
923        let (log_blowup, num_queries, proof_of_work_bits) = default_fri_params_for_tests();
924        let fri_params = FriQueryParams {
925            num_queries,
926            log_blowup,
927            log_final_poly_len: 0,
928            proof_of_work_bits,
929        };
930        let wrong_public_values = vec![ConfigVal::ZERO; 2];
931        let result =
932            verifier.derive_query_positions(&air, &proof, &wrong_public_values, &fri_params);
933        assert!(result.is_err());
934    }
935
936    #[test]
937    fn test_derive_challenges_rejects_random_commitment_mismatch() {
938        let (air, mut proof, public_values) = sample_arithmetic_proof();
939        let verifier = StarkVerifier::new(default_config());
940
941        proof.commitments.random = Some(proof.commitments.trace.clone());
942        let result = verifier.derive_challenges(&air, &proof, &public_values);
943        assert!(matches!(result, Err(VerificationError::RandomizationError)));
944    }
945
946    #[test]
947    fn test_derive_challenges_rejects_random_values_mismatch() {
948        let (air, mut proof, public_values) = sample_arithmetic_proof();
949        let verifier = StarkVerifier::new(default_config());
950
951        proof.opened_values.random = Some(vec![ConfigVal::ZERO]);
952        let result = verifier.derive_challenges(&air, &proof, &public_values);
953        assert!(matches!(result, Err(VerificationError::RandomizationError)));
954    }
955
956    #[test]
957    fn test_derive_challenges_rejects_invalid_trace_shape() {
958        let (air, mut proof, public_values) = sample_arithmetic_proof();
959        let verifier = StarkVerifier::new(default_config());
960
961        let _ = proof.opened_values.trace_local.pop();
962        let result = verifier.derive_challenges(&air, &proof, &public_values);
963        assert!(matches!(result, Err(VerificationError::InvalidProofShape)));
964    }
965
966    #[test]
967    fn test_derive_challenges_rejects_invalid_quotient_chunk_shape() {
968        let (air, mut proof, public_values) = sample_arithmetic_proof();
969        let verifier = StarkVerifier::new(default_config());
970
971        proof.opened_values.quotient_chunks.clear();
972        let result = verifier.derive_challenges(&air, &proof, &public_values);
973        assert!(matches!(result, Err(VerificationError::InvalidProofShape)));
974    }
975
976    #[test]
977    fn test_derive_query_positions_rejects_random_commitment_mismatch() {
978        let (air, mut proof, public_values) = sample_arithmetic_proof();
979        let verifier = StarkVerifier::new(default_config());
980        let (log_blowup, num_queries, proof_of_work_bits) = default_fri_params_for_tests();
981        let fri_params = FriQueryParams {
982            num_queries,
983            log_blowup,
984            log_final_poly_len: 0,
985            proof_of_work_bits,
986        };
987
988        proof.commitments.random = Some(proof.commitments.trace.clone());
989        let result = verifier.derive_query_positions(&air, &proof, &public_values, &fri_params);
990        assert!(matches!(result, Err(VerificationError::RandomizationError)));
991    }
992
993    #[test]
994    fn test_derive_query_positions_rejects_random_values_without_commitment() {
995        let (air, mut proof, public_values) = sample_arithmetic_proof();
996        let verifier = StarkVerifier::new(default_config());
997        let (log_blowup, num_queries, proof_of_work_bits) = default_fri_params_for_tests();
998        let fri_params = FriQueryParams {
999            num_queries,
1000            log_blowup,
1001            log_final_poly_len: 0,
1002            proof_of_work_bits,
1003        };
1004
1005        proof.opened_values.random = Some(vec![ConfigVal::ZERO]);
1006        let result = verifier.derive_query_positions(&air, &proof, &public_values, &fri_params);
1007        assert!(matches!(result, Err(VerificationError::RandomizationError)));
1008    }
1009
1010    #[test]
1011    fn test_derive_query_positions_rejects_invalid_trace_shape() {
1012        let (air, mut proof, public_values) = sample_arithmetic_proof();
1013        let verifier = StarkVerifier::new(default_config());
1014        let (log_blowup, num_queries, proof_of_work_bits) = default_fri_params_for_tests();
1015        let fri_params = FriQueryParams {
1016            num_queries,
1017            log_blowup,
1018            log_final_poly_len: 0,
1019            proof_of_work_bits,
1020        };
1021
1022        let _ = proof.opened_values.trace_next.pop();
1023        let result = verifier.derive_query_positions(&air, &proof, &public_values, &fri_params);
1024        assert!(matches!(result, Err(VerificationError::InvalidProofShape)));
1025    }
1026
1027    #[test]
1028    fn test_derive_query_positions_rejects_invalid_pow_witness() {
1029        let (air, proof, public_values) = sample_arithmetic_proof();
1030        let verifier = StarkVerifier::new(default_config());
1031        let (log_blowup, num_queries, _proof_of_work_bits) = default_fri_params_for_tests();
1032        let fri_params = FriQueryParams {
1033            num_queries,
1034            log_blowup,
1035            log_final_poly_len: 0,
1036            // Tighten PoW bits while staying in-field (<= 30 for Mersenne31).
1037            proof_of_work_bits: 30,
1038        };
1039
1040        let result = verifier.derive_query_positions(&air, &proof, &public_values, &fri_params);
1041        assert!(matches!(result, Err(VerificationError::InvalidProofShape)));
1042    }
1043
1044    #[test]
1045    fn test_verify_rejects_invalid_trace_local_shape() {
1046        let (air, mut proof, public_values) = sample_arithmetic_proof();
1047        let verifier = StarkVerifier::new(default_config());
1048        let _ = proof.opened_values.trace_local.pop();
1049        let result = verifier.verify(&air, &proof, &public_values);
1050        assert!(matches!(result, Err(VerificationError::InvalidProofShape)));
1051    }
1052
1053    #[test]
1054    fn test_verify_rejects_invalid_trace_next_shape() {
1055        let (air, mut proof, public_values) = sample_arithmetic_proof();
1056        let verifier = StarkVerifier::new(default_config());
1057        let _ = proof.opened_values.trace_next.pop();
1058        let result = verifier.verify(&air, &proof, &public_values);
1059        assert!(matches!(result, Err(VerificationError::InvalidProofShape)));
1060    }
1061
1062    #[test]
1063    fn test_verify_rejects_invalid_quotient_chunk_shape() {
1064        let (air, mut proof, public_values) = sample_arithmetic_proof();
1065        let verifier = StarkVerifier::new(default_config());
1066        proof.opened_values.quotient_chunks.clear();
1067        let result = verifier.verify(&air, &proof, &public_values);
1068        assert!(matches!(result, Err(VerificationError::InvalidProofShape)));
1069    }
1070
1071    #[test]
1072    fn test_verify_rejects_random_commitment_mismatch() {
1073        let (air, mut proof, public_values) = sample_arithmetic_proof();
1074        let verifier = StarkVerifier::new(default_config());
1075        proof.commitments.random = Some(proof.commitments.trace.clone());
1076        let result = verifier.verify(&air, &proof, &public_values);
1077        assert!(matches!(result, Err(VerificationError::RandomizationError)));
1078    }
1079
1080    #[test]
1081    fn test_verify_rejects_random_values_mismatch() {
1082        let (air, mut proof, public_values) = sample_arithmetic_proof();
1083        let verifier = StarkVerifier::new(default_config());
1084        proof.opened_values.random = Some(vec![ConfigVal::ZERO]);
1085        let result = verifier.verify(&air, &proof, &public_values);
1086        assert!(matches!(result, Err(VerificationError::RandomizationError)));
1087    }
1088}
lib_q_zkp/stark.rs

lib_q_zkp/
stark.rs
