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

lib_q_zkp/
stark.rs
