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

lib_q_zkp/
stark.rs
