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::{
41    BinomialExtensionField,
42    Complex,
43};
44use lib_q_stark_field::{
45    BasedVectorSpace,
46    PrimeCharacteristicRing,
47};
48use lib_q_stark_fri::{
49    FriDataExtractor,
50    TwoAdicFriPcs,
51};
52use lib_q_stark_matrix::dense::RowMajorMatrix;
53use lib_q_stark_merkle::MerkleTreeMmcs;
54use lib_q_stark_mersenne31::{
55    Mersenne31,
56    Mersenne31ComplexRadix2Dit,
57};
58use lib_q_stark_shake256::Shake256Hash;
59use lib_q_stark_symmetric::{
60    CompressionFunctionFromHasher,
61    SerializingHasher,
62};
63
64// Concrete config type aliases (used as return types for config factory functions).
65// Public so that pub type DefaultConfig/ZkConfig/PoseidonConfig satisfy private_interfaces.
66pub type ConfigVal = Complex<Mersenne31>;
67/// FRI **challenge field**: the degree-3 extension over `Complex<Mersenne31>`, i.e. `GF(p^6)`
68/// (~186 bits). Upgraded from using the value field itself (`Complex<Mersenne31>` = `GF(p^2)`,
69/// ~62 bits) as the challenge field — ~62 bits was a hard ceiling on Fiat–Shamir/DEEP soundness far
70/// below 128. Constants are Sage-verified in `lib-q-stark-mersenne31/src/extension.rs`
71/// (`HasComplexBinomialExtension<3>`: `y^3 - 5i`). See `membership-arm-a-soundness-params.md`.
72pub type ConfigChallenge = BinomialExtensionField<ConfigVal, 3>;
73pub type ConfigDft = Mersenne31ComplexRadix2Dit;
74pub type DefaultValMmcs = MerkleTreeMmcs<
75    <ConfigVal as lib_q_stark_field::Field>::Packing,
76    u8,
77    SerializingHasher<Shake256Hash>,
78    CompressionFunctionFromHasher<Shake256Hash, 2, 32>,
79    32,
80>;
81pub type DefaultChallengeMmcs = ExtensionMmcs<ConfigVal, ConfigVal, DefaultValMmcs>;
82pub type DefaultPcs = TwoAdicFriPcs<ConfigVal, ConfigDft, DefaultValMmcs, DefaultChallengeMmcs>;
83pub type DefaultConfig =
84    StarkConfig<DefaultPcs, ConfigVal, ComplexFieldChallenger<Shake256Challenger32<Mersenne31>>>;
85
86// ---------------------------------------------------------------------------
87// Arm A **membership** config — 128-bit-PQ variant of `DefaultConfig` with a larger FRI challenge
88// field. The shared `DefaultConfig` keeps the value field (`Complex<Mersenne31>`, ~62 bits) as its
89// challenge field (the recursive-aggregation verifier in `air/recursive_types.rs` hardcodes that
90// width); the membership prover/verifier instead use the degree-3 challenge extension `GF(p^6)`
91// (~186 bits) so the unlinkable-membership proof clears 128-bit (FS/DEEP no longer the binder; the
92// binding term is the SHAKE256 commitment at 128). Same value field, DFT, and Merkle commitment as
93// `DefaultConfig`; only the challenge field + FRI params differ.
94pub type MembershipChallengeMmcs = ExtensionMmcs<ConfigVal, ConfigChallenge, DefaultValMmcs>;
95pub type MembershipPcs =
96    TwoAdicFriPcs<ConfigVal, ConfigDft, DefaultValMmcs, MembershipChallengeMmcs>;
97pub type MembershipConfig = StarkConfig<
98    MembershipPcs,
99    ConfigChallenge,
100    ComplexFieldChallenger<Shake256Challenger32<Mersenne31>>,
101>;
102
103#[cfg(feature = "recursive-proofs-experimental")]
104use lib_q_stark_merkle::PoseidonMmcs as PoseidonMmcsType;
105#[cfg(feature = "recursive-proofs-experimental")]
106pub type PoseidonChallengeMmcs = ExtensionMmcs<ConfigVal, ConfigVal, PoseidonMmcsType>;
107#[cfg(feature = "recursive-proofs-experimental")]
108pub type PoseidonPcs = TwoAdicFriPcs<ConfigVal, ConfigDft, PoseidonMmcsType, PoseidonChallengeMmcs>;
109#[cfg(feature = "recursive-proofs-experimental")]
110pub type PoseidonConfig =
111    StarkConfig<PoseidonPcs, ConfigVal, ComplexFieldChallenger<Shake256Challenger32<Mersenne31>>>;
112
113use lib_q_stark_fri::HidingFriPcs;
114use lib_q_stark_merkle::MerkleTreeHidingMmcs;
115pub type ZkValMmcs = MerkleTreeHidingMmcs<
116    <ConfigVal as lib_q_stark_field::Field>::Packing,
117    u8,
118    SerializingHasher<Shake256Hash>,
119    CompressionFunctionFromHasher<Shake256Hash, 2, 32>,
120    lib_q_random::Kt128Rng,
121    32,
122    4,
123>;
124pub type ZkChallengeMmcs = ExtensionMmcs<ConfigVal, ConfigVal, ZkValMmcs>;
125pub type ZkPcs =
126    HidingFriPcs<ConfigVal, ConfigDft, ZkValMmcs, ZkChallengeMmcs, lib_q_random::Kt128Rng>;
127pub type ZkConfig =
128    StarkConfig<ZkPcs, ConfigVal, ComplexFieldChallenger<Shake256Challenger32<Mersenne31>>>;
129
130/// Arm A **membership** hiding (ZK) config — 128-bit-PQ variant of [`ZkConfig`] with the degree-3
131/// challenge field (`GF(p^6)` ~186 bits). See [`MembershipConfig`].
132pub type MembershipZkChallengeMmcs = ExtensionMmcs<ConfigVal, ConfigChallenge, ZkValMmcs>;
133pub type MembershipZkPcs = HidingFriPcs<
134    ConfigVal,
135    ConfigDft,
136    ZkValMmcs,
137    MembershipZkChallengeMmcs,
138    lib_q_random::Kt128Rng,
139>;
140pub type MembershipZkConfig = StarkConfig<
141    MembershipZkPcs,
142    ConfigChallenge,
143    ComplexFieldChallenger<Shake256Challenger32<Mersenne31>>,
144>;
145
146/// FRI query parameters used when replaying the verifier (e.g. for recursive aggregation).
147#[derive(Clone, Debug)]
148pub struct FriQueryParams {
149    pub num_queries: usize,
150    pub log_blowup: usize,
151    pub log_final_poly_len: usize,
152    pub proof_of_work_bits: usize,
153}
154
155// Generic type aliases for StarkVerifier (`C: StarkGenericConfig` on the alias is stable Rust).
156type PcsCommitment<C: StarkGenericConfig> =
157    <C::Pcs as Pcs<C::Challenge, C::Challenger>>::Commitment;
158
159type CommitmentRounds<C: StarkGenericConfig> = Vec<(
160    PcsCommitment<C>,
161    Vec<(Domain<C>, Vec<(C::Challenge, Vec<C::Challenge>)>)>,
162)>;
163
164type QuotientRounds<C: StarkGenericConfig> =
165    Vec<(Domain<C>, Vec<(C::Challenge, Vec<C::Challenge>)>)>;
166
167/// zk-STARK prover
168///
169/// This is a high-level wrapper around the STARK proving functionality.
170/// It provides a convenient interface for generating STARK proofs with a given configuration.
171///
172/// # Example
173///
174/// ```rust,ignore
175/// use lib_q_zkp::stark::{StarkProver, default_config};
176/// use Complex;
177/// use Mersenne31;
178///
179/// type Val = Complex<Mersenne31>;
180///
181/// let config = default_config();
182/// let prover = StarkProver::new(config);
183/// // air: implements Air trait
184/// // trace: RowMajorMatrix<Val>
185/// // public_values: &[Val]
186/// let proof = prover.prove(&air, trace, &public_values);
187/// ```
188pub struct StarkProver<C: StarkGenericConfig> {
189    config: C,
190}
191
192impl<C: StarkGenericConfig> StarkProver<C> {
193    /// Create a new zk-STARK prover with the given configuration
194    pub fn new(config: C) -> Self {
195        Self { config }
196    }
197
198    /// Generate a STARK proof for the given AIR, trace, and public values
199    ///
200    /// # Arguments
201    ///
202    /// * `air` - The Algebraic Intermediate Representation defining the constraints
203    /// * `trace` - The witness trace matrix (contains secret data)
204    /// * `public_values` - Public values known to both prover and verifier
205    ///
206    /// # Returns
207    ///
208    /// A STARK proof that can be verified without revealing the witness trace
209    #[cfg(not(debug_assertions))]
210    pub fn prove<A>(
211        &self,
212        air: &A,
213        trace: RowMajorMatrix<Val<C>>,
214        public_values: &[Val<C>],
215    ) -> Result<StarkProof<C>, lib_q_stark::ProverError>
216    where
217        A: Air<SymbolicAirBuilder<Val<C>>>
218            + for<'a> Air<lib_q_stark::ProverConstraintFolder<'a, C>>,
219    {
220        prove(&self.config, air, trace, public_values)
221    }
222
223    #[cfg(debug_assertions)]
224    pub fn prove<A>(
225        &self,
226        air: &A,
227        trace: RowMajorMatrix<Val<C>>,
228        public_values: &[Val<C>],
229    ) -> Result<StarkProof<C>, lib_q_stark::ProverError>
230    where
231        A: Air<SymbolicAirBuilder<Val<C>>>
232            + for<'a> Air<lib_q_stark::ProverConstraintFolder<'a, C>>
233            + for<'a> Air<lib_q_stark::DebugConstraintBuilder<'a, Val<C>>>,
234    {
235        prove(&self.config, air, trace, public_values)
236    }
237
238    /// Get a reference to the underlying configuration
239    pub fn config(&self) -> &C {
240        &self.config
241    }
242}
243
244/// zk-STARK verifier
245///
246/// This is a high-level wrapper around the STARK verification functionality.
247/// It provides a convenient interface for verifying STARK proofs with a given configuration.
248///
249/// # Example
250///
251/// ```rust,ignore
252/// use lib_q_zkp::stark::{StarkVerifier, default_config};
253/// use Complex;
254/// use Mersenne31;
255///
256/// type Val = Complex<Mersenne31>;
257///
258/// let config = default_config();
259/// let verifier = StarkVerifier::new(config);
260/// // air: implements Air trait (same as used in proof generation)
261/// // proof: StarkProof<Config>
262/// // public_values: &[Val]
263/// verifier.verify(&air, &proof, &public_values)?;
264/// ```
265pub struct StarkVerifier<C: StarkGenericConfig> {
266    config: C,
267}
268
269impl<C: StarkGenericConfig> StarkVerifier<C> {
270    /// Create a new zk-STARK verifier with the given configuration
271    pub fn new(config: C) -> Self {
272        Self { config }
273    }
274
275    /// Verify a STARK proof for the given AIR and public values
276    ///
277    /// # Arguments
278    ///
279    /// * `air` - The Algebraic Intermediate Representation that was used to generate the proof
280    /// * `proof` - The STARK proof to verify
281    /// * `public_values` - Public values that were used during proof generation
282    ///
283    /// # Returns
284    ///
285    /// `Ok(())` if the proof is valid, `Err(VerificationError)` otherwise
286    pub fn verify<A>(
287        &self,
288        air: &A,
289        proof: &StarkProof<C>,
290        public_values: &[Val<C>],
291    ) -> Result<(), VerificationError<lib_q_stark::PcsError<C>>>
292    where
293        A: Air<SymbolicAirBuilder<Val<C>>>
294            + for<'a> Air<lib_q_stark::VerifierConstraintFolder<'a, C>>,
295    {
296        verify(&self.config, air, proof, public_values)
297    }
298
299    /// Derive Fiat–Shamir challenges by replaying the verifier transcript.
300    ///
301    /// Returns `(zeta, zeta_next, alpha, betas)` so that callers (e.g. aggregation)
302    /// can serialize proofs with real challenges. Only supports proofs without
303    /// preprocessed trace (`preprocessed_width == 0`).
304    #[allow(clippy::type_complexity)]
305    pub fn derive_challenges<A>(
306        &self,
307        air: &A,
308        proof: &StarkProof<C>,
309        public_values: &[Val<C>],
310    ) -> Result<
311        (
312            C::Challenge,
313            C::Challenge,
314            C::Challenge,
315            Vec<C::Challenge>,
316        ),
317        VerificationError<lib_q_stark::PcsError<C>>,
318    >
319    where
320        A: Air<SymbolicAirBuilder<Val<C>>>
321            + for<'a> Air<lib_q_stark::VerifierConstraintFolder<'a, C>>,
322        <<C as StarkGenericConfig>::Pcs as Pcs<C::Challenge, C::Challenger>>::Proof:
323            FriDataExtractor<Challenge = C::Challenge>,
324        C::Challenger: CanObserve<Val<C>>
325            + CanObserve<<C::Pcs as Pcs<C::Challenge, C::Challenger>>::Commitment>
326            + CanObserve<
327                <<<C as StarkGenericConfig>::Pcs as Pcs<C::Challenge, C::Challenger>>::Proof as FriDataExtractor>::Commitment,
328            >,
329    {
330        let config = &self.config;
331        let pcs = config.pcs();
332        let commitments = &proof.commitments;
333        let opened_values = &proof.opened_values;
334        let opening_proof = &proof.opening_proof;
335        let degree_bits = proof.degree_bits;
336
337        let preprocessed_width = air
338            .preprocessed_trace()
339            .as_ref()
340            .map(|m| m.width)
341            .unwrap_or(0);
342        if preprocessed_width > 0 {
343            return Err(VerificationError::InvalidProofShape);
344        }
345
346        let degree = 1 << degree_bits;
347        if degree == 0 {
348            return Err(VerificationError::InvalidProofShape);
349        }
350
351        let trace_domain: Domain<C> = pcs.natural_domain_for_degree(degree);
352        let init_trace_domain = pcs.natural_domain_for_degree(degree >> config.is_zk());
353
354        let log_num_quotient_chunks = get_log_num_quotient_chunks::<Val<C>, A>(
355            air,
356            preprocessed_width,
357            public_values.len(),
358            config.is_zk(),
359        );
360        let num_quotient_chunks = 1 << (log_num_quotient_chunks + config.is_zk());
361
362        if (opened_values.random.is_some() != C::Pcs::ZK) ||
363            (commitments.random.is_some() != C::Pcs::ZK)
364        {
365            return Err(VerificationError::RandomizationError);
366        }
367
368        let air_width = A::width(air);
369        let valid_shape = opened_values.trace_local.len() == air_width &&
370            opened_values.trace_next.len() == air_width &&
371            opened_values.quotient_chunks.len() == num_quotient_chunks &&
372            opened_values
373                .quotient_chunks
374                .iter()
375                .all(|qc| qc.len() == C::Challenge::DIMENSION) &&
376            opened_values
377                .random
378                .as_ref()
379                .is_none_or(|r| r.len() == C::Challenge::DIMENSION);
380        if !valid_shape {
381            return Err(VerificationError::InvalidProofShape);
382        }
383
384        let quotient_domain =
385            trace_domain.create_disjoint_domain(1 << (degree_bits + log_num_quotient_chunks));
386        let quotient_chunks_domains = quotient_domain.split_domains(num_quotient_chunks);
387        let randomized_quotient_chunks_domains: Vec<Domain<C>> = quotient_chunks_domains
388            .iter()
389            .map(|d: &Domain<C>| pcs.natural_domain_for_degree(d.size() << config.is_zk()))
390            .collect();
391
392        let mut challenger = config.initialise_challenger();
393
394        challenger.observe(Val::<C>::from_usize(degree_bits));
395        challenger.observe(Val::<C>::from_usize(degree_bits - config.is_zk()));
396        challenger.observe(Val::<C>::from_usize(preprocessed_width));
397        challenger.observe(Val::<C>::from_usize(A::width(air)));
398        challenger.observe(commitments.trace.clone());
399        challenger.observe_slice(public_values);
400
401        let alpha = challenger.sample_algebra_element();
402        challenger.observe(commitments.quotient_chunks.clone());
403        if let Some(ref r_commit) = commitments.random {
404            challenger.observe(r_commit.clone());
405        }
406
407        let zeta = challenger.sample_algebra_element();
408        let zeta_next = init_trace_domain
409            .next_point(zeta)
410            .ok_or(VerificationError::NextPointUnavailable)?;
411
412        let mut coms_to_verify: CommitmentRounds<C> =
413            if let Some(ref random_commit) = commitments.random {
414                let random_values = opened_values
415                    .random
416                    .as_ref()
417                    .ok_or(VerificationError::RandomizationError)?;
418                alloc::vec![(
419                    random_commit.clone(),
420                    alloc::vec![(trace_domain, alloc::vec![(zeta, random_values.clone())],)],
421                )]
422            } else {
423                alloc::vec![]
424            };
425
426        coms_to_verify.push((
427            commitments.trace.clone(),
428            alloc::vec![(
429                trace_domain,
430                alloc::vec![
431                    (zeta, opened_values.trace_local.clone()),
432                    (zeta_next, opened_values.trace_next.clone()),
433                ],
434            )],
435        ));
436
437        let quotient_rounds: QuotientRounds<C> = randomized_quotient_chunks_domains
438            .iter()
439            .zip(opened_values.quotient_chunks.iter())
440            .map(|(domain, values)| (*domain, alloc::vec![(zeta, values.clone())]))
441            .collect();
442        coms_to_verify.push((commitments.quotient_chunks.clone(), quotient_rounds));
443
444        for (_, round) in &coms_to_verify {
445            for (_, mat) in round {
446                for (_, point) in mat {
447                    for opening in point {
448                        challenger.observe_algebra_element(*opening);
449                    }
450                }
451            }
452        }
453
454        let _alpha_fri = challenger.sample_algebra_element::<C::Challenge>();
455
456        let betas: Vec<C::Challenge> = opening_proof
457            .commit_phase_commits()
458            .iter()
459            .map(|comm| {
460                challenger.observe(comm.clone());
461                challenger.sample_algebra_element()
462            })
463            .collect();
464
465        Ok((zeta, zeta_next, alpha, betas))
466    }
467
468    /// Derive FRI query positions by replaying the Fiat–Shamir challenger through commitments,
469    /// FRI betas, final polynomial, and PoW, then sampling `num_queries` indices.
470    ///
471    /// Returns the same query indices the verifier would use when verifying the proof.
472    /// Call with the same FRI params used to produce the proof (e.g. from config).
473    pub fn derive_query_positions<A>(
474        &self,
475        air: &A,
476        proof: &StarkProof<C>,
477        public_values: &[Val<C>],
478        fri_params: &FriQueryParams,
479    ) -> Result<Vec<usize>, VerificationError<lib_q_stark::PcsError<C>>>
480    where
481        A: Air<SymbolicAirBuilder<Val<C>>>
482            + for<'a> Air<lib_q_stark::VerifierConstraintFolder<'a, C>>,
483        <<C as StarkGenericConfig>::Pcs as Pcs<C::Challenge, C::Challenger>>::Proof:
484            FriDataExtractor<Challenge = C::Challenge>,
485        C::Challenger: CanObserve<Val<C>>
486            + CanObserve<<C::Pcs as Pcs<C::Challenge, C::Challenger>>::Commitment>
487            + CanObserve<
488                <<<C as StarkGenericConfig>::Pcs as Pcs<C::Challenge, C::Challenger>>::Proof as FriDataExtractor>::Commitment,
489            >
490            + GrindingChallenger<
491                Witness = <<<C as StarkGenericConfig>::Pcs as Pcs<C::Challenge, C::Challenger>>::Proof as FriDataExtractor>::Witness,
492            >,
493        <<<C as StarkGenericConfig>::Pcs as Pcs<C::Challenge, C::Challenger>>::Proof as FriDataExtractor>::Witness: Clone,
494    {
495        let config = &self.config;
496        let pcs = config.pcs();
497        let commitments = &proof.commitments;
498        let opened_values = &proof.opened_values;
499        let opening_proof = &proof.opening_proof;
500        let degree_bits = proof.degree_bits;
501
502        let preprocessed_width = air
503            .preprocessed_trace()
504            .as_ref()
505            .map(|m| m.width)
506            .unwrap_or(0);
507        if preprocessed_width > 0 {
508            return Err(VerificationError::InvalidProofShape);
509        }
510
511        let degree = 1 << degree_bits;
512        if degree == 0 {
513            return Err(VerificationError::InvalidProofShape);
514        }
515
516        let log_num_quotient_chunks = get_log_num_quotient_chunks::<Val<C>, A>(
517            air,
518            preprocessed_width,
519            public_values.len(),
520            config.is_zk(),
521        );
522        let num_quotient_chunks = 1 << (log_num_quotient_chunks + config.is_zk());
523
524        if (opened_values.random.is_some() != C::Pcs::ZK) ||
525            (commitments.random.is_some() != C::Pcs::ZK)
526        {
527            return Err(VerificationError::RandomizationError);
528        }
529
530        let air_width = A::width(air);
531        let valid_shape = opened_values.trace_local.len() == air_width &&
532            opened_values.trace_next.len() == air_width &&
533            opened_values.quotient_chunks.len() == num_quotient_chunks &&
534            opened_values
535                .quotient_chunks
536                .iter()
537                .all(|qc| qc.len() == C::Challenge::DIMENSION) &&
538            opened_values
539                .random
540                .as_ref()
541                .is_none_or(|r| r.len() == C::Challenge::DIMENSION);
542        if !valid_shape {
543            return Err(VerificationError::InvalidProofShape);
544        }
545
546        let trace_domain: Domain<C> = pcs.natural_domain_for_degree(degree);
547        let init_trace_domain = pcs.natural_domain_for_degree(degree >> config.is_zk());
548        let quotient_domain =
549            trace_domain.create_disjoint_domain(1 << (degree_bits + log_num_quotient_chunks));
550        let quotient_chunks_domains = quotient_domain.split_domains(num_quotient_chunks);
551        let randomized_quotient_chunks_domains: Vec<Domain<C>> = quotient_chunks_domains
552            .iter()
553            .map(|d: &Domain<C>| pcs.natural_domain_for_degree(d.size() << config.is_zk()))
554            .collect();
555
556        let mut challenger = config.initialise_challenger();
557
558        challenger.observe(Val::<C>::from_usize(degree_bits));
559        challenger.observe(Val::<C>::from_usize(degree_bits - config.is_zk()));
560        challenger.observe(Val::<C>::from_usize(preprocessed_width));
561        challenger.observe(Val::<C>::from_usize(A::width(air)));
562        challenger.observe(commitments.trace.clone());
563        challenger.observe_slice(public_values);
564
565        let _alpha: Val<C> = challenger.sample_algebra_element();
566        challenger.observe(commitments.quotient_chunks.clone());
567        if let Some(ref r_commit) = commitments.random {
568            challenger.observe(r_commit.clone());
569        }
570
571        let zeta = challenger.sample_algebra_element();
572        let _zeta_next = init_trace_domain
573            .next_point(zeta)
574            .ok_or(VerificationError::NextPointUnavailable)?;
575
576        let mut coms_to_verify: CommitmentRounds<C> =
577            if let Some(ref random_commit) = commitments.random {
578                let random_values = opened_values
579                    .random
580                    .as_ref()
581                    .ok_or(VerificationError::RandomizationError)?;
582                alloc::vec![(
583                    random_commit.clone(),
584                    alloc::vec![(trace_domain, alloc::vec![(zeta, random_values.clone())],)],
585                )]
586            } else {
587                alloc::vec![]
588            };
589
590        coms_to_verify.push((
591            commitments.trace.clone(),
592            alloc::vec![(
593                trace_domain,
594                alloc::vec![
595                    (zeta, opened_values.trace_local.clone()),
596                    (
597                        init_trace_domain
598                            .next_point(zeta)
599                            .ok_or(VerificationError::NextPointUnavailable)?,
600                        opened_values.trace_next.clone(),
601                    ),
602                ],
603            )],
604        ));
605
606        let quotient_rounds: QuotientRounds<C> = randomized_quotient_chunks_domains
607            .iter()
608            .zip(opened_values.quotient_chunks.iter())
609            .map(|(domain, values)| (*domain, alloc::vec![(zeta, values.clone())]))
610            .collect();
611        coms_to_verify.push((commitments.quotient_chunks.clone(), quotient_rounds));
612
613        for (_, round) in &coms_to_verify {
614            for (_, mat) in round {
615                for (_, point) in mat {
616                    for opening in point {
617                        challenger.observe_algebra_element(*opening);
618                    }
619                }
620            }
621        }
622
623        let _alpha_fri = challenger.sample_algebra_element::<C::Challenge>();
624
625        for comm in opening_proof.commit_phase_commits() {
626            challenger.observe(comm.clone());
627            let _beta: C::Challenge = challenger.sample_algebra_element();
628        }
629
630        for coeff in opening_proof.final_poly() {
631            challenger.observe_algebra_element(*coeff);
632        }
633
634        if !challenger.check_witness(
635            fri_params.proof_of_work_bits,
636            opening_proof.pow_witness().clone(),
637        ) {
638            return Err(VerificationError::InvalidProofShape);
639        }
640
641        let log_global_max_height = opening_proof.commit_phase_commits().len() +
642            fri_params.log_blowup +
643            fri_params.log_final_poly_len;
644        const EXTRA_QUERY_INDEX_BITS: usize = 0;
645
646        let mut positions = Vec::with_capacity(fri_params.num_queries);
647        for _ in 0..fri_params.num_queries {
648            let index = challenger.sample_bits(log_global_max_height + EXTRA_QUERY_INDEX_BITS);
649            positions.push(index);
650        }
651
652        Ok(positions)
653    }
654
655    /// Get a reference to the underlying configuration
656    pub fn config(&self) -> &C {
657        &self.config
658    }
659}
660
661/// Creates a production-ready default STARK configuration
662///
663/// This configuration uses:
664/// - **SHAKE256** for all hash operations (NIST-approved, post-quantum secure)
665/// - **`Complex<Mersenne31>`** field (TWO_ADICITY = 32) for efficient arithmetic
666/// - Production FRI parameters (100 queries, 16 proof-of-work bits)
667///
668/// # Example
669///
670/// ```rust,ignore
671/// use lib_q_zkp::stark::{default_config, StarkProver, StarkVerifier};
672///
673/// let config = default_config();
674/// let prover = StarkProver::new(config.clone());
675/// let verifier = StarkVerifier::new(config);
676/// ```
677pub fn default_config() -> DefaultConfig {
678    use lib_q_stark_fri::FriParameters;
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 = FriParameters {
696        log_blowup: 2,
697        log_final_poly_len: 0,
698        num_queries: 100,
699        proof_of_work_bits: 16,
700        mmcs: challenge_mmcs,
701    };
702    let pcs = Pcs::new(dft, val_mmcs, fri_params);
703    let base_challenger = BaseChallenger::from_hasher(Vec::new(), Shake256Hash);
704    let challenger = Challenger::new(base_challenger);
705
706    StarkConfig::new(pcs, challenger)
707}
708
709/// Construct the Arm A **membership** transparent config — 128-bit-PQ ([`MembershipConfig`]).
710/// Identical to [`default_config`] except: (1) the FRI challenge field is the degree-3 extension
711/// `GF(p^6)` (~186 bits) instead of the ~62-bit value field, and (2) FRI `log_blowup = 3`
712/// (ρ = 1/8), `num_queries = 96`, `proof_of_work_bits = 20`. With the larger challenge field the
713/// FS/DEEP term is no longer the binder; the binding soundness term is the SHAKE256 commitment at
714/// 128 bits, and the query phase clears 128-bit on the conjectured (288) and provable-Johnson (144)
715/// bounds. (The shared `default_config` stays ~62-bit because the recursive-aggregation verifier in
716/// `air/recursive_types.rs` hardcodes the value-field challenge width; membership does not recurse.)
717pub fn membership_config() -> MembershipConfig {
718    use lib_q_stark_fri::FriParameters;
719
720    let shake256 = Shake256Hash {};
721    let hash = SerializingHasher::<Shake256Hash>::new(shake256);
722    let compress = CompressionFunctionFromHasher::<Shake256Hash, 2, 32>::new(shake256);
723    let val_mmcs = DefaultValMmcs::new(hash, compress);
724    let challenge_mmcs = MembershipChallengeMmcs::new(val_mmcs.clone());
725    let dft = ConfigDft::default();
726    let fri_params = FriParameters {
727        log_blowup: 3,
728        log_final_poly_len: 0,
729        num_queries: 96,
730        proof_of_work_bits: 20,
731        mmcs: challenge_mmcs,
732    };
733    let pcs = MembershipPcs::new(dft, val_mmcs, fri_params);
734    let base_challenger = Shake256Challenger32::<Mersenne31>::from_hasher(Vec::new(), Shake256Hash);
735    let challenger = ComplexFieldChallenger::new(base_challenger);
736    StarkConfig::new(pcs, challenger)
737}
738
739/// STARK configuration for **tests and local development only**.
740///
741/// Same construction as [`default_config`], but FRI uses
742/// [`lib_q_stark_fri::create_test_fri_params`] (2 queries, 1 proof-of-work bit) so proving
743/// and verification complete quickly. **Do not use for production**; proofs are not
744/// production-sound and are incompatible with verifiers configured for [`default_config`].
745///
746/// Soundness is far below production; do not use this config to assert that verification
747/// **rejects** wrong public inputs (e.g. wrong Merkle root). For those negative tests, use
748/// [`default_config`] on prover and verifier.
749pub fn fast_proof_config() -> DefaultConfig {
750    use lib_q_stark_fri::create_test_fri_params;
751
752    type ValMmcs = DefaultValMmcs;
753    type ChallengeMmcs = DefaultChallengeMmcs;
754    type Dft = ConfigDft;
755    type Pcs = DefaultPcs;
756    type MyHash = SerializingHasher<Shake256Hash>;
757    type MyCompress = CompressionFunctionFromHasher<Shake256Hash, 2, 32>;
758    type BaseChallenger = Shake256Challenger32<Mersenne31>;
759    type Challenger = ComplexFieldChallenger<BaseChallenger>;
760
761    let shake256 = Shake256Hash {};
762    let hash = MyHash::new(shake256);
763    let compress = MyCompress::new(shake256);
764    let val_mmcs = ValMmcs::new(hash, compress);
765    let challenge_mmcs = ChallengeMmcs::new(val_mmcs.clone());
766    let dft = Dft::default();
767    let fri_params = create_test_fri_params(challenge_mmcs, 0);
768    let pcs = Pcs::new(dft, val_mmcs, fri_params);
769    let base_challenger = BaseChallenger::from_hasher(Vec::new(), Shake256Hash);
770    let challenger = Challenger::new(base_challenger);
771
772    StarkConfig::new(pcs, challenger)
773}
774
775/// Fast (minimal-FRI) [`MembershipConfig`] for tests — the degree-3-challenge-field analogue of
776/// [`fast_proof_config`]. Not sound for production; only for round-trip tests.
777pub fn membership_fast_config() -> MembershipConfig {
778    use lib_q_stark_fri::create_test_fri_params;
779
780    let shake256 = Shake256Hash {};
781    let hash = SerializingHasher::<Shake256Hash>::new(shake256);
782    let compress = CompressionFunctionFromHasher::<Shake256Hash, 2, 32>::new(shake256);
783    let val_mmcs = DefaultValMmcs::new(hash, compress);
784    let challenge_mmcs = MembershipChallengeMmcs::new(val_mmcs.clone());
785    let dft = ConfigDft::default();
786    let fri_params = create_test_fri_params(challenge_mmcs, 0);
787    let pcs = MembershipPcs::new(dft, val_mmcs, fri_params);
788    let base_challenger = Shake256Challenger32::<Mersenne31>::from_hasher(Vec::new(), Shake256Hash);
789    let challenger = ComplexFieldChallenger::new(base_challenger);
790    StarkConfig::new(pcs, challenger)
791}
792
793/// STARK config that uses Poseidon-based Merkle trees (PoseidonMmcs).
794/// Use this as the outer config when producing recursive proofs so that Merkle paths
795/// are compatible with MerkleInclusionAir (Poseidon constraints in-circuit).
796#[cfg(feature = "recursive-proofs-experimental")]
797pub fn poseidon_config() -> PoseidonConfig {
798    use lib_q_stark_fri::FriParameters;
799    use lib_q_stark_merkle::{
800        PoseidonMmcs,
801        poseidon_mmcs_instance,
802    };
803
804    type ValMmcs = PoseidonMmcs;
805    type ChallengeMmcs = PoseidonChallengeMmcs;
806    type Dft = ConfigDft;
807    type Pcs = PoseidonPcs;
808    type BaseChallenger = Shake256Challenger32<Mersenne31>;
809    type Challenger = ComplexFieldChallenger<BaseChallenger>;
810
811    let (hash, compress) = poseidon_mmcs_instance();
812    let val_mmcs = ValMmcs::new(hash, compress);
813    let challenge_mmcs = ChallengeMmcs::new(val_mmcs.clone());
814    let dft = Dft::default();
815    let fri_params = FriParameters {
816        log_blowup: 2,
817        log_final_poly_len: 0,
818        num_queries: 100,
819        proof_of_work_bits: 16,
820        mmcs: challenge_mmcs,
821    };
822    let pcs = Pcs::new(dft, val_mmcs, fri_params);
823    let base_challenger = BaseChallenger::from_hasher(Vec::new(), Shake256Hash);
824    let challenger = Challenger::new(base_challenger);
825
826    StarkConfig::new(pcs, challenger)
827}
828
829/// Same PCS and challenger construction as [`poseidon_config`], but FRI uses
830/// [`lib_q_stark_fri::create_test_fri_params`] (2 queries, 1 proof-of-work bit) so recursive
831/// aggregation tests finish quickly. **Not for production**; incompatible with verifiers
832/// expecting [`poseidon_config`] FRI parameters.
833#[cfg(feature = "recursive-proofs-experimental")]
834pub fn poseidon_test_config() -> PoseidonConfig {
835    use lib_q_stark_fri::create_test_fri_params;
836    use lib_q_stark_merkle::{
837        PoseidonMmcs,
838        poseidon_mmcs_instance,
839    };
840
841    type ValMmcs = PoseidonMmcs;
842    type ChallengeMmcs = PoseidonChallengeMmcs;
843    type Dft = ConfigDft;
844    type Pcs = PoseidonPcs;
845    type BaseChallenger = Shake256Challenger32<Mersenne31>;
846    type Challenger = ComplexFieldChallenger<BaseChallenger>;
847
848    let (hash, compress) = poseidon_mmcs_instance();
849    let val_mmcs = ValMmcs::new(hash, compress);
850    let challenge_mmcs = ChallengeMmcs::new(val_mmcs.clone());
851    let dft = Dft::default();
852    let fri_params = create_test_fri_params(challenge_mmcs, 0);
853    let pcs = Pcs::new(dft, val_mmcs, fri_params);
854    let base_challenger = BaseChallenger::from_hasher(Vec::new(), Shake256Hash);
855    let challenger = Challenger::new(base_challenger);
856
857    StarkConfig::new(pcs, challenger)
858}
859
860/// Default FRI parameters used by `default_config()` (for security parameter tests).
861/// Returns (log_blowup, num_queries, proof_of_work_bits).
862#[doc(hidden)]
863pub const fn default_fri_params_for_tests() -> (usize, usize, usize) {
864    (2, 100, 16)
865}
866
867/// ZK config for tests: uses HidingFriPcs so proofs are randomized (statistical ZK).
868/// Not for production; uses test FRI params (few queries, low PoW).
869pub fn zk_config() -> ZkConfig {
870    zk_config_with_seeds(0, 1)
871}
872
873/// Same as `zk_config()` but with explicit RNG seeds (for tests that need distinct proofs).
874#[doc(hidden)]
875pub fn zk_config_with_seeds(val_mmcs_seed: u64, pcs_seed: u64) -> ZkConfig {
876    use lib_q_stark_fri::create_test_fri_params_zk;
877
878    type ValMmcs = ZkValMmcs;
879    type ChallengeMmcs = ZkChallengeMmcs;
880    type Dft = ConfigDft;
881    type Pcs = ZkPcs;
882    type MyHash = SerializingHasher<Shake256Hash>;
883    type MyCompress = CompressionFunctionFromHasher<Shake256Hash, 2, 32>;
884    type BaseChallenger = Shake256Challenger32<Mersenne31>;
885    type Challenger = ComplexFieldChallenger<BaseChallenger>;
886
887    let shake256 = Shake256Hash {};
888    let hash = MyHash::new(shake256);
889    let compress = MyCompress::new(shake256);
890    let val_mmcs = ValMmcs::new(
891        hash,
892        compress,
893        lib_q_random::Kt128Rng::from_u64(val_mmcs_seed),
894    );
895    let challenge_mmcs = ChallengeMmcs::new(val_mmcs.clone());
896    let dft = Dft::default();
897    let fri_params = create_test_fri_params_zk(challenge_mmcs);
898    let pcs = Pcs::new(
899        dft,
900        val_mmcs,
901        fri_params,
902        4,
903        lib_q_random::Kt128Rng::from_u64(pcs_seed),
904    );
905    let base_challenger = BaseChallenger::from_hasher(Vec::new(), Shake256Hash);
906    let challenger = Challenger::new(base_challenger);
907
908    StarkConfig::new(pcs, challenger)
909}
910
911/// ZK config with explicit FRI parameters and RNG seeds.
912///
913/// The hiding PCS LDEs the (randomized) trace at `log_blowup + 1`. High-degree AIRs (e.g. the
914/// Poseidon `x⁵` S-box, constraint degree 5) need a LARGER `log_blowup` than low-degree AIRs so
915/// the quotient-evaluation domain stays within the committed LDE — the hiding PCS's
916/// extrapolation fallback for out-of-LDE domains is not implemented. For degree-5 AIRs use
917/// `log_blowup >= 3`.
918#[doc(hidden)]
919pub fn zk_config_with_params(
920    log_blowup: usize,
921    num_queries: usize,
922    proof_of_work_bits: usize,
923    val_mmcs_seed: u64,
924    pcs_seed: u64,
925) -> ZkConfig {
926    use lib_q_stark_fri::FriParameters;
927
928    type ValMmcs = ZkValMmcs;
929    type ChallengeMmcs = ZkChallengeMmcs;
930    type Dft = ConfigDft;
931    type Pcs = ZkPcs;
932    type MyHash = SerializingHasher<Shake256Hash>;
933    type MyCompress = CompressionFunctionFromHasher<Shake256Hash, 2, 32>;
934    type BaseChallenger = Shake256Challenger32<Mersenne31>;
935    type Challenger = ComplexFieldChallenger<BaseChallenger>;
936
937    let shake256 = Shake256Hash {};
938    let hash = MyHash::new(shake256);
939    let compress = MyCompress::new(shake256);
940    let val_mmcs = ValMmcs::new(
941        hash,
942        compress,
943        lib_q_random::Kt128Rng::from_u64(val_mmcs_seed),
944    );
945    let challenge_mmcs = ChallengeMmcs::new(val_mmcs.clone());
946    let dft = Dft::default();
947    let fri_params = FriParameters {
948        log_blowup,
949        log_final_poly_len: 0,
950        num_queries,
951        proof_of_work_bits,
952        mmcs: challenge_mmcs,
953    };
954    let pcs = Pcs::new(
955        dft,
956        val_mmcs,
957        fri_params,
958        4,
959        lib_q_random::Kt128Rng::from_u64(pcs_seed),
960    );
961    let base_challenger = BaseChallenger::from_hasher(Vec::new(), Shake256Hash);
962    let challenger = Challenger::new(base_challenger);
963
964    StarkConfig::new(pcs, challenger)
965}
966
967/// Production ZK config seeded from **256-bit CSPRNG entropy** (the hiding secret). Use this
968/// for real zero-knowledge proofs. `val_seed` (hiding-MMCS salts) and `pcs_seed` (blinding
969/// polynomials) MUST be INDEPENDENT, fresh, unpredictable CSPRNG draws — sharing or predicting
970/// them voids hiding. The KT128-backed [`lib_q_random::Kt128Rng`] expands each 256-bit seed
971/// into a cryptographically pseudorandom stream (unlike the xorshift64 `DeterministicRng` used
972/// by the `*_with_seeds`/`*_with_params` test helpers).
973pub fn zk_config_with_seed_bytes(
974    log_blowup: usize,
975    num_queries: usize,
976    proof_of_work_bits: usize,
977    val_seed: [u8; 32],
978    pcs_seed: [u8; 32],
979) -> ZkConfig {
980    use lib_q_stark_fri::FriParameters;
981
982    type ValMmcs = ZkValMmcs;
983    type ChallengeMmcs = ZkChallengeMmcs;
984    type Dft = ConfigDft;
985    type Pcs = ZkPcs;
986    type MyHash = SerializingHasher<Shake256Hash>;
987    type MyCompress = CompressionFunctionFromHasher<Shake256Hash, 2, 32>;
988    type BaseChallenger = Shake256Challenger32<Mersenne31>;
989    type Challenger = ComplexFieldChallenger<BaseChallenger>;
990
991    let shake256 = Shake256Hash {};
992    let hash = MyHash::new(shake256);
993    let compress = MyCompress::new(shake256);
994    let val_mmcs = ValMmcs::new(
995        hash,
996        compress,
997        lib_q_random::Kt128Rng::from_seed_bytes(val_seed),
998    );
999    let challenge_mmcs = ChallengeMmcs::new(val_mmcs.clone());
1000    let dft = Dft::default();
1001    let fri_params = FriParameters {
1002        log_blowup,
1003        log_final_poly_len: 0,
1004        num_queries,
1005        proof_of_work_bits,
1006        mmcs: challenge_mmcs,
1007    };
1008    let pcs = Pcs::new(
1009        dft,
1010        val_mmcs,
1011        fri_params,
1012        4,
1013        lib_q_random::Kt128Rng::from_seed_bytes(pcs_seed),
1014    );
1015    let base_challenger = BaseChallenger::from_hasher(Vec::new(), Shake256Hash);
1016    let challenger = Challenger::new(base_challenger);
1017
1018    StarkConfig::new(pcs, challenger)
1019}
1020
1021/// Arm A **membership** hiding-PCS ZK config from 256-bit CSPRNG seeds — 128-bit-PQ
1022/// ([`MembershipZkConfig`], degree-3 challenge field). Mirrors [`zk_config_with_seed_bytes`].
1023pub fn membership_zk_config_with_seed_bytes(
1024    log_blowup: usize,
1025    num_queries: usize,
1026    proof_of_work_bits: usize,
1027    val_seed: [u8; 32],
1028    pcs_seed: [u8; 32],
1029) -> MembershipZkConfig {
1030    use lib_q_stark_fri::FriParameters;
1031
1032    let shake256 = Shake256Hash {};
1033    let hash = SerializingHasher::<Shake256Hash>::new(shake256);
1034    let compress = CompressionFunctionFromHasher::<Shake256Hash, 2, 32>::new(shake256);
1035    let val_mmcs = ZkValMmcs::new(
1036        hash,
1037        compress,
1038        lib_q_random::Kt128Rng::from_seed_bytes(val_seed),
1039    );
1040    let challenge_mmcs = MembershipZkChallengeMmcs::new(val_mmcs.clone());
1041    let dft = ConfigDft::default();
1042    let fri_params = FriParameters {
1043        log_blowup,
1044        log_final_poly_len: 0,
1045        num_queries,
1046        proof_of_work_bits,
1047        mmcs: challenge_mmcs,
1048    };
1049    let pcs = MembershipZkPcs::new(
1050        dft,
1051        val_mmcs,
1052        fri_params,
1053        4,
1054        lib_q_random::Kt128Rng::from_seed_bytes(pcs_seed),
1055    );
1056    let base_challenger = Shake256Challenger32::<Mersenne31>::from_hasher(Vec::new(), Shake256Hash);
1057    let challenger = ComplexFieldChallenger::new(base_challenger);
1058    StarkConfig::new(pcs, challenger)
1059}
1060
1061/// Arm A **membership** ZK config with explicit FRI params + xorshift test seeds — 128-bit-PQ
1062/// ([`MembershipZkConfig`]). Mirrors [`zk_config_with_params`]; used by the verifier (FRI params
1063/// must match the prover; the verifier needs no hiding entropy).
1064#[doc(hidden)]
1065pub fn membership_zk_config_with_params(
1066    log_blowup: usize,
1067    num_queries: usize,
1068    proof_of_work_bits: usize,
1069    val_mmcs_seed: u64,
1070    pcs_seed: u64,
1071) -> MembershipZkConfig {
1072    use lib_q_stark_fri::FriParameters;
1073
1074    let shake256 = Shake256Hash {};
1075    let hash = SerializingHasher::<Shake256Hash>::new(shake256);
1076    let compress = CompressionFunctionFromHasher::<Shake256Hash, 2, 32>::new(shake256);
1077    let val_mmcs = ZkValMmcs::new(
1078        hash,
1079        compress,
1080        lib_q_random::Kt128Rng::from_u64(val_mmcs_seed),
1081    );
1082    let challenge_mmcs = MembershipZkChallengeMmcs::new(val_mmcs.clone());
1083    let dft = ConfigDft::default();
1084    let fri_params = FriParameters {
1085        log_blowup,
1086        log_final_poly_len: 0,
1087        num_queries,
1088        proof_of_work_bits,
1089        mmcs: challenge_mmcs,
1090    };
1091    let pcs = MembershipZkPcs::new(
1092        dft,
1093        val_mmcs,
1094        fri_params,
1095        4,
1096        lib_q_random::Kt128Rng::from_u64(pcs_seed),
1097    );
1098    let base_challenger = Shake256Challenger32::<Mersenne31>::from_hasher(Vec::new(), Shake256Hash);
1099    let challenger = ComplexFieldChallenger::new(base_challenger);
1100    StarkConfig::new(pcs, challenger)
1101}
1102
1103#[cfg(test)]
1104mod tests {
1105    extern crate alloc;
1106    use alloc::vec;
1107
1108    use super::*;
1109    use crate::air::{
1110        ArithmeticAir,
1111        TraceGenerator,
1112    };
1113
1114    fn sample_arithmetic_proof() -> (ArithmeticAir, StarkProof<DefaultConfig>, Vec<ConfigVal>) {
1115        let air = ArithmeticAir::new(1).expect("ArithmeticAir");
1116        let input = vec![(ConfigVal::ONE, ConfigVal::ONE)];
1117        let trace = air.generate_trace(&input).expect("trace");
1118        let public_values = air.public_values(&input);
1119        let proof = StarkProver::new(default_config())
1120            .prove(&air, trace, &public_values)
1121            .expect("proof generation");
1122        (air, proof, public_values)
1123    }
1124
1125    #[test]
1126    fn test_stark_prover_creation() {
1127        let config = default_config();
1128        let _prover = StarkProver::new(config);
1129        // Just verify that creation doesn't panic
1130    }
1131
1132    #[test]
1133    fn test_stark_verifier_creation() {
1134        let config = default_config();
1135        let _verifier = StarkVerifier::new(config);
1136        // Just verify that creation doesn't panic
1137    }
1138
1139    #[test]
1140    fn test_default_config() {
1141        let _config = default_config();
1142        // Just verify that config creation doesn't panic
1143    }
1144
1145    #[test]
1146    fn test_default_fri_params_for_tests_values() {
1147        let (log_blowup, num_queries, proof_of_work_bits) = default_fri_params_for_tests();
1148        assert_eq!(log_blowup, 2);
1149        assert_eq!(num_queries, 100);
1150        assert_eq!(proof_of_work_bits, 16);
1151    }
1152
1153    #[test]
1154    fn test_zk_config_builders_create_zk_configs() {
1155        let zk_a = zk_config();
1156        let zk_b = zk_config_with_seeds(11, 29);
1157        assert_eq!(zk_a.is_zk(), 1);
1158        assert_eq!(zk_b.is_zk(), 1);
1159    }
1160
1161    #[test]
1162    fn test_prover_and_verifier_config_accessors() {
1163        let prover = StarkProver::new(default_config());
1164        let verifier = StarkVerifier::new(default_config());
1165        assert_eq!(prover.config().is_zk(), 0);
1166        assert_eq!(verifier.config().is_zk(), 0);
1167    }
1168
1169    #[test]
1170    fn test_stark_prove_and_verify_roundtrip() {
1171        let (air, proof, public_values) = sample_arithmetic_proof();
1172        let verifier = StarkVerifier::new(default_config());
1173        verifier
1174            .verify(&air, &proof, &public_values)
1175            .expect("proof should verify");
1176    }
1177
1178    #[test]
1179    fn test_derive_challenges_and_query_positions() {
1180        let (air, proof, public_values) = sample_arithmetic_proof();
1181        let verifier = StarkVerifier::new(default_config());
1182
1183        let (_zeta, _zeta_next, _alpha, betas) = verifier
1184            .derive_challenges(&air, &proof, &public_values)
1185            .expect("derive_challenges");
1186
1187        let (log_blowup, num_queries, proof_of_work_bits) = default_fri_params_for_tests();
1188        assert!(betas.len() <= num_queries);
1189        let fri_params = FriQueryParams {
1190            num_queries,
1191            log_blowup,
1192            log_final_poly_len: 0,
1193            proof_of_work_bits,
1194        };
1195        let positions = verifier
1196            .derive_query_positions(&air, &proof, &public_values, &fri_params)
1197            .expect("derive_query_positions");
1198        assert_eq!(positions.len(), num_queries);
1199    }
1200
1201    #[test]
1202    fn test_derive_query_positions_rejects_wrong_public_values_shape() {
1203        let (air, proof, _public_values) = sample_arithmetic_proof();
1204        let verifier = StarkVerifier::new(default_config());
1205        let (log_blowup, num_queries, proof_of_work_bits) = default_fri_params_for_tests();
1206        let fri_params = FriQueryParams {
1207            num_queries,
1208            log_blowup,
1209            log_final_poly_len: 0,
1210            proof_of_work_bits,
1211        };
1212        let wrong_public_values = vec![ConfigVal::ZERO; 2];
1213        let result =
1214            verifier.derive_query_positions(&air, &proof, &wrong_public_values, &fri_params);
1215        assert!(result.is_err());
1216    }
1217
1218    #[test]
1219    fn test_derive_challenges_rejects_random_commitment_mismatch() {
1220        let (air, mut proof, public_values) = sample_arithmetic_proof();
1221        let verifier = StarkVerifier::new(default_config());
1222
1223        proof.commitments.random = Some(proof.commitments.trace.clone());
1224        let result = verifier.derive_challenges(&air, &proof, &public_values);
1225        assert!(matches!(result, Err(VerificationError::RandomizationError)));
1226    }
1227
1228    #[test]
1229    fn test_derive_challenges_rejects_random_values_mismatch() {
1230        let (air, mut proof, public_values) = sample_arithmetic_proof();
1231        let verifier = StarkVerifier::new(default_config());
1232
1233        proof.opened_values.random = Some(vec![ConfigVal::ZERO]);
1234        let result = verifier.derive_challenges(&air, &proof, &public_values);
1235        assert!(matches!(result, Err(VerificationError::RandomizationError)));
1236    }
1237
1238    #[test]
1239    fn test_derive_challenges_rejects_invalid_trace_shape() {
1240        let (air, mut proof, public_values) = sample_arithmetic_proof();
1241        let verifier = StarkVerifier::new(default_config());
1242
1243        let _ = proof.opened_values.trace_local.pop();
1244        let result = verifier.derive_challenges(&air, &proof, &public_values);
1245        assert!(matches!(result, Err(VerificationError::InvalidProofShape)));
1246    }
1247
1248    #[test]
1249    fn test_derive_challenges_rejects_invalid_quotient_chunk_shape() {
1250        let (air, mut proof, public_values) = sample_arithmetic_proof();
1251        let verifier = StarkVerifier::new(default_config());
1252
1253        proof.opened_values.quotient_chunks.clear();
1254        let result = verifier.derive_challenges(&air, &proof, &public_values);
1255        assert!(matches!(result, Err(VerificationError::InvalidProofShape)));
1256    }
1257
1258    #[test]
1259    fn test_derive_query_positions_rejects_random_commitment_mismatch() {
1260        let (air, mut proof, public_values) = sample_arithmetic_proof();
1261        let verifier = StarkVerifier::new(default_config());
1262        let (log_blowup, num_queries, proof_of_work_bits) = default_fri_params_for_tests();
1263        let fri_params = FriQueryParams {
1264            num_queries,
1265            log_blowup,
1266            log_final_poly_len: 0,
1267            proof_of_work_bits,
1268        };
1269
1270        proof.commitments.random = Some(proof.commitments.trace.clone());
1271        let result = verifier.derive_query_positions(&air, &proof, &public_values, &fri_params);
1272        assert!(matches!(result, Err(VerificationError::RandomizationError)));
1273    }
1274
1275    #[test]
1276    fn test_derive_query_positions_rejects_random_values_without_commitment() {
1277        let (air, mut proof, public_values) = sample_arithmetic_proof();
1278        let verifier = StarkVerifier::new(default_config());
1279        let (log_blowup, num_queries, proof_of_work_bits) = default_fri_params_for_tests();
1280        let fri_params = FriQueryParams {
1281            num_queries,
1282            log_blowup,
1283            log_final_poly_len: 0,
1284            proof_of_work_bits,
1285        };
1286
1287        proof.opened_values.random = Some(vec![ConfigVal::ZERO]);
1288        let result = verifier.derive_query_positions(&air, &proof, &public_values, &fri_params);
1289        assert!(matches!(result, Err(VerificationError::RandomizationError)));
1290    }
1291
1292    #[test]
1293    fn test_derive_query_positions_rejects_invalid_trace_shape() {
1294        let (air, mut proof, public_values) = sample_arithmetic_proof();
1295        let verifier = StarkVerifier::new(default_config());
1296        let (log_blowup, num_queries, proof_of_work_bits) = default_fri_params_for_tests();
1297        let fri_params = FriQueryParams {
1298            num_queries,
1299            log_blowup,
1300            log_final_poly_len: 0,
1301            proof_of_work_bits,
1302        };
1303
1304        let _ = proof.opened_values.trace_next.pop();
1305        let result = verifier.derive_query_positions(&air, &proof, &public_values, &fri_params);
1306        assert!(matches!(result, Err(VerificationError::InvalidProofShape)));
1307    }
1308
1309    #[test]
1310    fn test_derive_query_positions_rejects_invalid_pow_witness() {
1311        let (air, proof, public_values) = sample_arithmetic_proof();
1312        let verifier = StarkVerifier::new(default_config());
1313        let (log_blowup, num_queries, _proof_of_work_bits) = default_fri_params_for_tests();
1314        let fri_params = FriQueryParams {
1315            num_queries,
1316            log_blowup,
1317            log_final_poly_len: 0,
1318            // Tighten PoW bits while staying in-field (<= 30 for Mersenne31).
1319            proof_of_work_bits: 30,
1320        };
1321
1322        let result = verifier.derive_query_positions(&air, &proof, &public_values, &fri_params);
1323        assert!(matches!(result, Err(VerificationError::InvalidProofShape)));
1324    }
1325
1326    #[test]
1327    fn test_verify_rejects_invalid_trace_local_shape() {
1328        let (air, mut proof, public_values) = sample_arithmetic_proof();
1329        let verifier = StarkVerifier::new(default_config());
1330        let _ = proof.opened_values.trace_local.pop();
1331        let result = verifier.verify(&air, &proof, &public_values);
1332        assert!(matches!(result, Err(VerificationError::InvalidProofShape)));
1333    }
1334
1335    #[test]
1336    fn test_verify_rejects_invalid_trace_next_shape() {
1337        let (air, mut proof, public_values) = sample_arithmetic_proof();
1338        let verifier = StarkVerifier::new(default_config());
1339        let _ = proof.opened_values.trace_next.pop();
1340        let result = verifier.verify(&air, &proof, &public_values);
1341        assert!(matches!(result, Err(VerificationError::InvalidProofShape)));
1342    }
1343
1344    #[test]
1345    fn test_verify_rejects_invalid_quotient_chunk_shape() {
1346        let (air, mut proof, public_values) = sample_arithmetic_proof();
1347        let verifier = StarkVerifier::new(default_config());
1348        proof.opened_values.quotient_chunks.clear();
1349        let result = verifier.verify(&air, &proof, &public_values);
1350        assert!(matches!(result, Err(VerificationError::InvalidProofShape)));
1351    }
1352
1353    #[test]
1354    fn test_verify_rejects_random_commitment_mismatch() {
1355        let (air, mut proof, public_values) = sample_arithmetic_proof();
1356        let verifier = StarkVerifier::new(default_config());
1357        proof.commitments.random = Some(proof.commitments.trace.clone());
1358        let result = verifier.verify(&air, &proof, &public_values);
1359        assert!(matches!(result, Err(VerificationError::RandomizationError)));
1360    }
1361
1362    #[test]
1363    fn test_verify_rejects_random_values_mismatch() {
1364        let (air, mut proof, public_values) = sample_arithmetic_proof();
1365        let verifier = StarkVerifier::new(default_config());
1366        proof.opened_values.random = Some(vec![ConfigVal::ZERO]);
1367        let result = verifier.verify(&air, &proof, &public_values);
1368        assert!(matches!(result, Err(VerificationError::RandomizationError)));
1369    }
1370}
lib_q_zkp/stark.rs

lib_q_zkp/
stark.rs
