openvm_backend_tests/
lib.rs

1//! Shared test suite for STARK backend implementations.
2//!
3//! This crate provides generic test functions that can be used to verify any
4//! [`StarkEngine`] implementation against the `BabyBearPoseidon2` configuration.
5//!
6//! # Usage
7//!
8//! The easiest way to use this crate is via the [`backend_test_suite!`] macro,
9//! which generates the complete shared test suite with a single invocation:
10//!
11//! ```ignore
12//! openvm_backend_tests::backend_test_suite!(MyEngine);
13//! ```
14//!
15//! Individual test functions can also be called directly for custom wrappers:
16//!
17//! ```ignore
18//! #[test]
19//! fn test_proof_shape_verifier() {
20//!     openvm_backend_tests::proof_shape_verifier::<MyEngine>().unwrap();
21//! }
22//! ```
23//!
24//! # Adding New Tests
25//!
26//! 1. Add a `pub fn` here (with `E: StarkEngine<SC = SC>` bound for engine-generic tests).
27//! 2. Add the test to the [`backend_test_suite!`] macro.
28//! 3. Each backend automatically picks it up on next build.
29
30use std::sync::Arc;
31
32use itertools::Itertools;
33use openvm_stark_backend::{
34    any_air_arc_vec,
35    keygen::types::LinearConstraint,
36    poly_common::Squarable,
37    prover::{
38        poly::Ple, stacked_pcs::stacked_commit, whir::prove_whir_opening, AirProvingContext,
39        ColMajorMatrix, CpuColMajorBackend, DeviceDataTransporter, DeviceMultiStarkProvingKey,
40        MatrixDimensions, ProvingContext,
41    },
42    test_utils::{
43        default_test_params_small,
44        dummy_airs::{
45            fib_air::air::FibonacciAir,
46            fib_selector_air::air::FibonacciSelectorAir,
47            interaction::dummy_interaction_air::{
48                DummyInteractionAir, DummyInteractionChip, DummyInteractionData,
49            },
50        },
51        prove_up_to_batch_constraints, test_system_params_small, test_whir_config_small,
52        CachedFixture11, FibFixture, InteractionsFixture11, MixtureFixture,
53        PreprocessedAndCachedFixture, PreprocessedFibFixture, SelfInteractionFixture, TestFixture,
54    },
55    transcript::duplex_sponge::DuplexSpongeValidator,
56    utils::disable_debug_builder,
57    verifier::{
58        batch_constraints::verify_zerocheck_and_logup,
59        fractional_sumcheck_gkr::{verify_gkr, GkrVerificationError},
60        proof_shape::verify_proof_shape,
61        verify,
62        whir::{binary_k_fold, verify_whir, VerifyWhirError},
63    },
64    AirRef, FiatShamirTranscript, StarkEngine, StarkProtocolConfig, SystemParams,
65    TranscriptHistory, WhirConfig, WhirParams, WhirProximityStrategy, WhirRoundConfig,
66};
67use openvm_stark_sdk::{
68    config::{
69        baby_bear_poseidon2::{
70            default_duplex_sponge, default_duplex_sponge_recorder, poseidon2_perm,
71            BabyBearPoseidon2Config, BabyBearPoseidon2RefEngine, DuplexSponge, EF, F,
72        },
73        log_up_params::log_up_security_params_baby_bear_100_bits,
74    },
75    utils::{setup_tracing, setup_tracing_with_log_level},
76};
77use p3_field::{Field, PrimeCharacteristicRing, PrimeField32, TwoAdicField};
78use p3_matrix::dense::RowMajorMatrix;
79use p3_util::log2_strict_usize;
80use rand::{rngs::StdRng, Rng, SeedableRng};
81use tracing::{debug, Level};
82
83pub type SC = BabyBearPoseidon2Config;
84
85// ---------------------------------------------------------------------------
86// Helper: run_test equivalent that handles device transport generically
87// ---------------------------------------------------------------------------
88
89/// Generic version of `StarkEngine::run_test` that accepts CPU-side contexts
90/// and handles device transport automatically.
91pub fn run_test_on_cpu_ctx<E: StarkEngine<SC = SC>>(
92    engine: &E,
93    airs: Vec<AirRef<SC>>,
94    ctxs: Vec<AirProvingContext<CpuColMajorBackend<SC>>>,
95) -> eyre::Result<()> {
96    let cpu_ctx = ProvingContext::new(ctxs.into_iter().enumerate().collect());
97    let d_ctx = engine.device().transport_proving_ctx_to_device(&cpu_ctx);
98    engine.run_test(airs, d_ctx.per_trace.into_iter().map(|(_, c)| c).collect())?;
99    Ok(())
100}
101
102// ===========================================================================
103// 1. Proof shape verification
104// ===========================================================================
105
106pub fn proof_shape_verifier<E: StarkEngine<SC = SC>>() -> eyre::Result<()> {
107    setup_tracing();
108    let log_trace_degree = 3;
109
110    let engine = E::new(default_test_params_small());
111
112    // without interactions
113    let (vk, proof) = FibFixture::new(0, 1, 1 << log_trace_degree).keygen_and_prove(&engine);
114    verify_proof_shape(&vk.inner, &proof)?;
115
116    // with interactions
117    let (vk, proof) = InteractionsFixture11.keygen_and_prove(&engine);
118    verify_proof_shape(&vk.inner, &proof)?;
119
120    // with cached trace
121    let params = engine.config().clone();
122    let (vk, proof) = CachedFixture11::new(params).keygen_and_prove(&engine);
123    verify_proof_shape(&vk.inner, &proof)?;
124
125    // with preprocessed trace
126    let height = 1 << log_trace_degree;
127    let sels = (0..height).map(|i| i % 2 == 0).collect_vec();
128    let (vk, proof) = PreprocessedFibFixture::new(0, 1, sels).keygen_and_prove(&engine);
129    verify_proof_shape(&vk.inner, &proof)?;
130
131    Ok(())
132}
133
134pub fn proof_shape_verifier_rng_system_params<E: StarkEngine<SC = SC>>() -> eyre::Result<()> {
135    setup_tracing();
136    let mut rng = StdRng::from_seed([228; 32]);
137    let w_stack = 16;
138    for _ in 0..10 {
139        let l_skip = rng.random_range(1usize..=2);
140        let n_stack = rng.random_range(8usize..=9);
141        let k_whir = rng.random_range(1usize..=4);
142        let log_blowup = rng.random_range(1usize..=3);
143        let num_whir_rounds = rng.random_range(1..=2);
144        let mut rounds = Vec::with_capacity(num_whir_rounds);
145        for _ in 0..num_whir_rounds {
146            rounds.push(WhirRoundConfig {
147                num_queries: rng.random_range(1..=10),
148            });
149        }
150        let whir = WhirConfig {
151            k: k_whir,
152            rounds,
153            mu_pow_bits: 1,
154            query_phase_pow_bits: 1,
155            folding_pow_bits: 1,
156            proximity: WhirProximityStrategy::SplitUniqueList {
157                m: 3,
158                list_start_round: 1,
159            },
160        };
161        let params = SystemParams {
162            l_skip,
163            n_stack,
164            w_stack,
165            log_blowup,
166            whir,
167            logup: log_up_security_params_baby_bear_100_bits(0.0),
168            max_constraint_degree: 3,
169        };
170        let engine = E::new(params);
171        let (vk, proof) = InteractionsFixture11.keygen_and_prove(&engine);
172        verify_proof_shape(&vk.inner, &proof)?;
173    }
174    Ok(())
175}
176
177// ===========================================================================
178// 2. Simple end-to-end prove + verify
179// ===========================================================================
180
181pub fn interactions_single_sender_receiver_happy<E: StarkEngine<SC = SC>>() -> eyre::Result<()> {
182    setup_tracing();
183    let engine = E::new(default_test_params_small());
184    let fx = InteractionsFixture11;
185    let (vk, proof) = fx.keygen_and_prove(&engine);
186    engine.verify(&vk, &proof)?;
187    Ok(())
188}
189
190pub fn single_cached_trace_stark<E: StarkEngine<SC = SC>>() -> eyre::Result<()> {
191    setup_tracing();
192    let engine = E::new(default_test_params_small());
193    let fx = CachedFixture11::new(engine.config().clone());
194    let (vk, proof) = fx.keygen_and_prove(&engine);
195    engine.verify(&vk, &proof)?;
196    Ok(())
197}
198
199pub fn single_preprocessed_trace_stark<E: StarkEngine<SC = SC>>(
200    log_trace_degree: usize,
201) -> eyre::Result<()> {
202    setup_tracing();
203    let engine = E::new(default_test_params_small());
204    let height = 1 << log_trace_degree;
205    let sels = (0..height).map(|i| i % 2 == 0).collect_vec();
206    let fx = PreprocessedFibFixture::new(0, 1, sels);
207    let (vk, proof) = fx.keygen_and_prove(&engine);
208    engine.verify(&vk, &proof)?;
209    Ok(())
210}
211
212pub fn multi_interaction_traces_stark<E: StarkEngine<SC = SC>>(
213    log_trace_degree: usize,
214) -> eyre::Result<()> {
215    setup_tracing();
216    let engine = E::new(default_test_params_small());
217    let fx = SelfInteractionFixture {
218        widths: vec![4, 7, 8, 8, 10, 100],
219        log_height: log_trace_degree,
220        bus_index: 4,
221    };
222    let (vk, proof) = fx.keygen_and_prove(&engine);
223    engine.verify(&vk, &proof)?;
224    Ok(())
225}
226
227pub fn mixture_traces_stark<E: StarkEngine<SC = SC>>(log_trace_degree: usize) -> eyre::Result<()> {
228    setup_tracing();
229    let engine = E::new(default_test_params_small());
230    let fx = MixtureFixture::standard(log_trace_degree, engine.config().clone());
231    let (vk, proof) = fx.keygen_and_prove(&engine);
232    engine.verify(&vk, &proof)?;
233    Ok(())
234}
235
236pub fn matrix_stacking_overflow<E: StarkEngine<SC = SC>>() -> eyre::Result<()> {
237    setup_tracing();
238    let params = test_system_params_small(3, 5, 3);
239    let engine = E::new(params);
240    let fx = SelfInteractionFixture {
241        widths: vec![4, 7, 8, 8, 10],
242        log_height: 1,
243        bus_index: 4,
244    };
245    let (vk, proof) = fx.keygen_and_prove(&engine);
246    engine.verify(&vk, &proof)?;
247    Ok(())
248}
249
250// ===========================================================================
251// 3. Roundtrip tests (custom system params)
252// ===========================================================================
253
254pub fn fib_air_roundtrip<E: StarkEngine<SC = SC>>(
255    l_skip: usize,
256    log_trace_degree: usize,
257) -> eyre::Result<()> {
258    setup_tracing_with_log_level(Level::DEBUG);
259
260    let n_stack = 8;
261    let w_stack = 8;
262    let k_whir = 4;
263    let whir_params = WhirParams {
264        k: k_whir,
265        log_final_poly_len: k_whir,
266        query_phase_pow_bits: 1,
267        folding_pow_bits: 11,
268        mu_pow_bits: 10,
269        proximity: WhirProximityStrategy::UniqueDecoding,
270    };
271    let log_blowup = 1;
272    let whir = WhirConfig::new(log_blowup, l_skip + n_stack, whir_params, 80);
273    let params = SystemParams {
274        l_skip,
275        n_stack,
276        w_stack,
277        log_blowup,
278        whir,
279        logup: log_up_security_params_baby_bear_100_bits(0.0),
280        max_constraint_degree: 3,
281    };
282    let fib = FibFixture::new(0, 1, 1 << log_trace_degree);
283
284    let engine = E::new(params);
285    let (pk, vk) = fib.keygen(&engine);
286    let mut prover_transcript = engine.initial_transcript();
287    let proof = fib.prove_from_transcript(&engine, &pk, &mut prover_transcript);
288
289    let mut verifier_sponge = default_duplex_sponge();
290    verify(engine.config(), &vk, &proof, &mut verifier_sponge)?;
291    Ok(())
292}
293
294pub fn dummy_interactions_roundtrip<E: StarkEngine<SC = SC>>(
295    l_skip: usize,
296    n_stack: usize,
297    k_whir: usize,
298) -> eyre::Result<()> {
299    let params = test_system_params_small(l_skip, n_stack, k_whir);
300    let engine = E::new(params);
301    let fx = InteractionsFixture11;
302    let (pk, vk) = fx.keygen(&engine);
303
304    let mut prover_transcript = engine.initial_transcript();
305    let proof = fx.prove_from_transcript(&engine, &pk, &mut prover_transcript);
306
307    let mut verifier_sponge = default_duplex_sponge();
308    verify(engine.config(), &vk, &proof, &mut verifier_sponge)?;
309    Ok(())
310}
311
312pub fn cached_trace_roundtrip<E: StarkEngine<SC = SC>>(
313    l_skip: usize,
314    n_stack: usize,
315    k_whir: usize,
316) -> eyre::Result<()> {
317    setup_tracing_with_log_level(Level::DEBUG);
318    let params = test_system_params_small(l_skip, n_stack, k_whir);
319    let engine = E::new(params);
320    let fx = CachedFixture11::new(engine.config().clone());
321    let (pk, vk) = fx.keygen(&engine);
322
323    let mut prover_transcript = engine.initial_transcript();
324    let proof = fx.prove_from_transcript(&engine, &pk, &mut prover_transcript);
325
326    let mut verifier_sponge = default_duplex_sponge();
327    verify(engine.config(), &vk, &proof, &mut verifier_sponge)?;
328    Ok(())
329}
330
331pub fn preprocessed_trace_roundtrip<E: StarkEngine<SC = SC>>(
332    l_skip: usize,
333    n_stack: usize,
334    k_whir: usize,
335) -> eyre::Result<()> {
336    let params = test_system_params_small(l_skip, n_stack, k_whir);
337    let engine = E::new(params);
338    let log_trace_degree = 8;
339    let height = 1 << log_trace_degree;
340    let sels = (0..height).map(|i| i % 2 == 0).collect_vec();
341    let fx = PreprocessedFibFixture::new(0, 1, sels);
342    let (pk, vk) = fx.keygen(&engine);
343
344    let mut prover_transcript = engine.initial_transcript();
345    let proof = fx.prove_from_transcript(&engine, &pk, &mut prover_transcript);
346
347    let mut verifier_sponge = default_duplex_sponge();
348    verify(engine.config(), &vk, &proof, &mut verifier_sponge)?;
349    Ok(())
350}
351
352pub fn preprocessed_and_cached_trace_roundtrip<E: StarkEngine<SC = SC>>(
353    l_skip: usize,
354    n_stack: usize,
355    k_whir: usize,
356    num_cached_parts: usize,
357) -> eyre::Result<()> {
358    let params = test_system_params_small(l_skip, n_stack, k_whir);
359    let engine = E::new(params);
360    let log_trace_degree = 8;
361    let height = 1 << log_trace_degree;
362    let sels = (0..height).map(|i| i % 2 == 0).collect_vec();
363    let fx = PreprocessedAndCachedFixture::new(sels, engine.config().clone(), num_cached_parts);
364    let (pk, vk) = fx.keygen(&engine);
365
366    let mut prover_transcript = engine.initial_transcript();
367    let proof = fx.prove_from_transcript(&engine, &pk, &mut prover_transcript);
368
369    let mut verifier_sponge = default_duplex_sponge();
370    verify(engine.config(), &vk, &proof, &mut verifier_sponge)?;
371    Ok(())
372}
373
374// ===========================================================================
375// 4. Pipeline decomposition tests
376// ===========================================================================
377
378pub fn batch_sumcheck_zero_interactions<E: StarkEngine<SC = SC>>(
379    log_trace_degree: usize,
380) -> eyre::Result<()> {
381    setup_tracing_with_log_level(Level::DEBUG);
382
383    let engine = E::new(default_test_params_small());
384    let params = engine.params();
385    let fib = FibFixture::new(0, 1, 1 << log_trace_degree);
386    let (pk, vk) = fib.keygen(&engine);
387    let device = engine.device();
388    let d_pk = device.transport_pk_to_device(&pk);
389    let cpu_ctx = fib.generate_proving_ctx();
390    let ctx = device.transport_proving_ctx_to_device(&cpu_ctx);
391
392    let mut n_per_air: Vec<isize> = Vec::with_capacity(ctx.per_trace.len());
393    for (_, trace) in ctx.common_main_traces() {
394        let trace_height = trace.height();
395        let log_height = log2_strict_usize(trace_height);
396        let n = log_height as isize - params.l_skip as isize;
397        n_per_air.push(n);
398    }
399
400    let mut prover_transcript = engine.initial_transcript();
401    let mut verifier_sponge = default_duplex_sponge();
402
403    let omega_skip = F::two_adic_generator(params.l_skip);
404    let omega_skip_pows = omega_skip.powers().take(1 << params.l_skip).collect_vec();
405
406    let pvs = vec![ctx.per_trace[0].1.public_values.clone()];
407    let (partial_proof, _) =
408        prove_up_to_batch_constraints(&engine, &mut prover_transcript, &d_pk, ctx);
409    let (gkr_proof, batch_proof) = partial_proof.into();
410
411    let r = verify_zerocheck_and_logup::<SC, _>(
412        &mut verifier_sponge,
413        &vk.inner,
414        &pvs,
415        &gkr_proof,
416        &batch_proof,
417        &[0],
418        &n_per_air,
419        &omega_skip_pows,
420    )?;
421    assert_eq!(r.len(), log_trace_degree.saturating_sub(params.l_skip) + 1);
422    Ok(())
423}
424
425/// Negative test: with zero interactions, a `gkr_proof.q0_claim != EF::ONE` must cause
426/// `verify_zerocheck_and_logup` to reject with `InvalidZeroRoundValue`.
427pub fn batch_sumcheck_zero_interactions_malleable_q0<E: StarkEngine<SC = SC>>() -> eyre::Result<()>
428{
429    setup_tracing_with_log_level(Level::DEBUG);
430
431    let engine = E::new(default_test_params_small());
432    let params = engine.params();
433    let log_trace_degree = 4;
434    let fib = FibFixture::new(0, 1, 1 << log_trace_degree);
435    let (pk, vk) = fib.keygen(&engine);
436    let device = engine.device();
437    let d_pk = device.transport_pk_to_device(&pk);
438    let cpu_ctx = fib.generate_proving_ctx();
439    let ctx = device.transport_proving_ctx_to_device(&cpu_ctx);
440
441    let mut n_per_air: Vec<isize> = Vec::with_capacity(ctx.per_trace.len());
442    for (_, trace) in ctx.common_main_traces() {
443        let trace_height = trace.height();
444        let log_height = log2_strict_usize(trace_height);
445        let n = log_height as isize - params.l_skip as isize;
446        n_per_air.push(n);
447    }
448
449    let mut prover_transcript = engine.initial_transcript();
450    let omega_skip = F::two_adic_generator(params.l_skip);
451    let omega_skip_pows = omega_skip.powers().take(1 << params.l_skip).collect_vec();
452
453    let pvs = vec![ctx.per_trace[0].1.public_values.clone()];
454    let (partial_proof, _) =
455        prove_up_to_batch_constraints(&engine, &mut prover_transcript, &d_pk, ctx);
456    let (mut gkr_proof, batch_proof) = partial_proof.into();
457
458    // Sanity: honest prover produces q0_claim = 1 when there are no interactions.
459    assert_eq!(gkr_proof.q0_claim, EF::ONE);
460    let tampered = EF::from_u64(2);
461    gkr_proof.q0_claim = tampered;
462
463    let mut verifier_sponge = default_duplex_sponge();
464    let err = verify_zerocheck_and_logup::<SC, _>(
465        &mut verifier_sponge,
466        &vk.inner,
467        &pvs,
468        &gkr_proof,
469        &batch_proof,
470        &[0],
471        &n_per_air,
472        &omega_skip_pows,
473    )
474    .expect_err("verifier must reject a tampered q0_claim when there are no interactions");
475    assert_eq!(
476        err,
477        GkrVerificationError::InvalidZeroRoundValue { actual: tampered }.into(),
478    );
479    Ok(())
480}
481
482pub fn gkr_verify_zero_interactions<E: StarkEngine<SC = SC>>() -> eyre::Result<()> {
483    setup_tracing_with_log_level(Level::DEBUG);
484
485    let engine = E::new(default_test_params_small());
486    let params = engine.params();
487    let fx = InteractionsFixture11;
488    let (pk, _vk) = fx.keygen(&engine);
489    let device = engine.device();
490    let d_pk = device.transport_pk_to_device(&pk);
491    let cpu_ctx = fx.generate_proving_ctx();
492    let ctx = device
493        .transport_proving_ctx_to_device(&cpu_ctx)
494        .into_sorted();
495
496    let mut prover_transcript = engine.initial_transcript();
497    let (partial_proof, _) =
498        prove_up_to_batch_constraints(&engine, &mut prover_transcript, &d_pk, ctx);
499    let (gkr_proof, _) = partial_proof.into();
500
501    let mut transcript = default_duplex_sponge();
502    assert!(FiatShamirTranscript::<SC>::check_witness(
503        &mut transcript,
504        params.logup.pow_bits,
505        gkr_proof.logup_pow_witness
506    ));
507    let _alpha = FiatShamirTranscript::<SC>::sample_ext(&mut transcript);
508    let _beta = FiatShamirTranscript::<SC>::sample_ext(&mut transcript);
509    let total_rounds = gkr_proof.claims_per_layer.len();
510    let _ = verify_gkr::<SC, _>(&gkr_proof, &mut transcript, total_rounds)?;
511
512    Ok(())
513}
514
515pub fn batch_constraints_with_interactions<E: StarkEngine<SC = SC>>() -> eyre::Result<()> {
516    setup_tracing_with_log_level(Level::DEBUG);
517
518    let engine = E::new(default_test_params_small());
519    let fx = InteractionsFixture11;
520    let (pk, vk) = fx.keygen(&engine);
521    let device = engine.device();
522    let d_pk = device.transport_pk_to_device(&pk);
523    let cpu_ctx = fx.generate_proving_ctx();
524    let ctx = device
525        .transport_proving_ctx_to_device(&cpu_ctx)
526        .into_sorted();
527    let l_skip = engine.params().l_skip;
528
529    let mut pvs = vec![vec![]; vk.inner.per_air.len()];
530    let (trace_id_to_air_ids, ns): (Vec<_>, Vec<_>) = ctx
531        .per_trace
532        .iter()
533        .map(|(air_idx, trace_ctx)| {
534            pvs[*air_idx] = trace_ctx.public_values.clone();
535            (
536                *air_idx,
537                log2_strict_usize(trace_ctx.common_main.height()) as isize - l_skip as isize,
538            )
539        })
540        .multiunzip();
541    debug!(?trace_id_to_air_ids);
542    debug!(n_per_trace = ?ns);
543    let omega_pows = F::two_adic_generator(l_skip)
544        .powers()
545        .take(1 << l_skip)
546        .collect_vec();
547
548    let mut prover_transcript = engine.initial_transcript();
549    let (partial_proof, _) =
550        prove_up_to_batch_constraints(&engine, &mut prover_transcript, &d_pk, ctx);
551    let (gkr_proof, batch_proof) = partial_proof.into();
552
553    let mut verifier_transcript = default_duplex_sponge();
554    verify_zerocheck_and_logup::<SC, _>(
555        &mut verifier_transcript,
556        &vk.inner,
557        &pvs,
558        &gkr_proof,
559        &batch_proof,
560        &trace_id_to_air_ids,
561        &ns,
562        &omega_pows,
563    )?;
564    Ok(())
565}
566
567// ===========================================================================
568// 5. Custom context construction
569// ===========================================================================
570
571pub fn single_fib_and_dummy_trace_stark<E: StarkEngine<SC = SC>>(
572    log_trace_degree: usize,
573) -> eyre::Result<()> {
574    setup_tracing();
575
576    let engine = E::new(default_test_params_small());
577
578    // Create interactions fixture with larger trace
579    let sender_height = 2 * (1 << 3);
580    let sender_trace = RowMajorMatrix::new(
581        [0, 1, 3, 5, 7, 4, 546, 889]
582            .into_iter()
583            .cycle()
584            .take(2 * sender_height)
585            .map(F::from_usize)
586            .collect(),
587        2,
588    );
589    let receiver_trace = RowMajorMatrix::new(
590        [1, 5, 3, 4, 4, 4, 2, 5, 0, 123, 545, 889, 1, 889, 0, 456]
591            .into_iter()
592            .cycle()
593            .take(4 * sender_height)
594            .map(F::from_usize)
595            .collect(),
596        2,
597    );
598
599    // Create fibonacci fixture with small trace
600    let height = 2 * (1 << log_trace_degree);
601    let fib = FibFixture::new(0, 1, height);
602
603    // Generate AIRs and proving keys
604    let fx_fixture = InteractionsFixture11;
605    let fx_airs = fx_fixture.airs();
606    let fib_airs = fib.airs();
607    let mut combined_airs = fx_airs;
608    combined_airs.extend(fib_airs);
609    let (combined_pk, _combined_vk) = engine.keygen(&combined_airs);
610    let device = engine.device();
611    let combined_pk = device.transport_pk_to_device(&combined_pk);
612
613    // Generate custom contexts for interactions with modified traces
614    let mut per_trace: Vec<_> = [sender_trace, receiver_trace]
615        .into_iter()
616        .enumerate()
617        .map(|(air_idx, trace)| {
618            (
619                air_idx,
620                AirProvingContext::simple_no_pis(ColMajorMatrix::from_row_major(&trace)),
621            )
622        })
623        .collect();
624    let fib_ctx = fib.generate_proving_ctx().per_trace.pop().unwrap().1;
625
626    // Combine contexts
627    per_trace.push((per_trace.len(), fib_ctx));
628    let cpu_ctx = ProvingContext::new(per_trace);
629    let combined_ctx = device
630        .transport_proving_ctx_to_device(&cpu_ctx)
631        .into_sorted();
632
633    let proof = engine.prove(&combined_pk, combined_ctx)?;
634    engine.verify(&combined_pk.get_vk(), &proof)?;
635    Ok(())
636}
637
638// ===========================================================================
639// 6. Interaction tests (positive and negative)
640// ===========================================================================
641
642pub fn optional_air<E: StarkEngine<SC = SC>>() -> eyre::Result<()> {
643    setup_tracing();
644
645    let engine = E::new(default_test_params_small());
646    let config = engine.config().clone();
647    let device = engine.device();
648
649    let fib_air = Arc::new(FibonacciAir) as AirRef<SC>;
650    let send_chip1: DummyInteractionChip<SC> =
651        DummyInteractionChip::new_without_partition(1, true, 0);
652    let send_chip2: DummyInteractionChip<SC> =
653        DummyInteractionChip::new_with_partition(config.clone(), 1, true, 0);
654    let recv_chip1: DummyInteractionChip<SC> =
655        DummyInteractionChip::new_without_partition(1, false, 0);
656
657    let airs = vec![
658        fib_air,
659        send_chip1.air(),
660        send_chip2.air(),
661        recv_chip1.air(),
662    ];
663    let (pk, _vk) = engine.keygen(&airs);
664    let d_pk = device.transport_pk_to_device(&pk);
665
666    // Case 1: All AIRs are present.
667    {
668        let fib = FibFixture::new(0, 1, 8);
669        let fib_air_ctx = fib
670            .generate_proving_ctx()
671            .per_trace
672            .into_iter()
673            .next()
674            .unwrap()
675            .1;
676
677        let mut s1: DummyInteractionChip<SC> =
678            DummyInteractionChip::new_without_partition(1, true, 0);
679        s1.load_data(DummyInteractionData {
680            count: vec![1, 2, 4],
681            fields: vec![vec![1], vec![2], vec![3]],
682        });
683        let mut s2: DummyInteractionChip<SC> =
684            DummyInteractionChip::new_with_partition(config.clone(), 1, true, 0);
685        s2.load_data(DummyInteractionData {
686            count: vec![1, 2, 8],
687            fields: vec![vec![1], vec![2], vec![3]],
688        });
689        let mut r1: DummyInteractionChip<SC> =
690            DummyInteractionChip::new_without_partition(1, false, 0);
691        r1.load_data(DummyInteractionData {
692            count: vec![2, 4, 12],
693            fields: vec![vec![1], vec![2], vec![3]],
694        });
695
696        let cpu_ctx = ProvingContext::new(vec![
697            (0, fib_air_ctx),
698            (1, s1.generate_proving_ctx()),
699            (2, s2.generate_proving_ctx()),
700            (3, r1.generate_proving_ctx()),
701        ]);
702        let d_ctx = device.transport_proving_ctx_to_device(&cpu_ctx);
703        let proof = engine.prove(&d_pk, d_ctx)?;
704        engine.verify(&pk.get_vk(), &proof)?;
705    }
706
707    // Case 2: Only send_chip1 and recv_chip1 present (fib and send_chip2 omitted).
708    {
709        let mut s1: DummyInteractionChip<SC> =
710            DummyInteractionChip::new_without_partition(1, true, 0);
711        s1.load_data(DummyInteractionData {
712            count: vec![1, 2, 4],
713            fields: vec![vec![1], vec![2], vec![3]],
714        });
715        let mut r1: DummyInteractionChip<SC> =
716            DummyInteractionChip::new_without_partition(1, false, 0);
717        r1.load_data(DummyInteractionData {
718            count: vec![1, 2, 4],
719            fields: vec![vec![1], vec![2], vec![3]],
720        });
721
722        let cpu_ctx = ProvingContext::new(vec![
723            (1, s1.generate_proving_ctx()),
724            (3, r1.generate_proving_ctx()),
725        ]);
726        let d_ctx = device.transport_proving_ctx_to_device(&cpu_ctx);
727        let proof = engine.prove(&d_pk, d_ctx)?;
728        engine.verify(&pk.get_vk(), &proof)?;
729    }
730
731    // Case 3: Negative - unbalanced interactions.
732    {
733        disable_debug_builder();
734        let mut r1: DummyInteractionChip<SC> =
735            DummyInteractionChip::new_without_partition(1, false, 0);
736        r1.load_data(DummyInteractionData {
737            count: vec![1, 2, 4],
738            fields: vec![vec![1], vec![2], vec![3]],
739        });
740
741        let cpu_ctx = ProvingContext::new(vec![(3, r1.generate_proving_ctx())]);
742        let d_ctx = device.transport_proving_ctx_to_device(&cpu_ctx);
743        let result = engine.prove(&d_pk, d_ctx);
744        assert!(
745            result.is_err(),
746            "Expected prover to fail with unbalanced interactions"
747        );
748    }
749    Ok(())
750}
751
752pub fn vkey_methods<E: StarkEngine<SC = SC>>() {
753    setup_tracing();
754
755    let engine = E::new(default_test_params_small());
756    let fib_air = FibonacciAir;
757    let send_air = DummyInteractionAir::new(1, true, 0);
758    let recv_air = DummyInteractionAir::new(1, false, 0);
759
760    let airs = any_air_arc_vec![fib_air, send_air, recv_air];
761    let (_pk, vk) = engine.keygen(&airs);
762
763    assert_eq!(vk.inner.per_air.len(), 3);
764    assert_eq!(vk.inner.per_air[0].params.width.main_width(), 2);
765    assert_eq!(vk.inner.per_air[1].params.width.main_width(), 2);
766    assert_eq!(vk.inner.per_air[2].params.width.main_width(), 2);
767    assert_eq!(vk.inner.per_air[0].num_interactions(), 0);
768    assert_eq!(vk.inner.per_air[1].num_interactions(), 1);
769    assert_eq!(vk.inner.per_air[2].num_interactions(), 1);
770}
771
772pub fn interaction_trace_height_constraints<E: StarkEngine<SC = SC>>() {
773    let log_trace_degree = 3;
774    let n = 1usize << log_trace_degree;
775    let sels: Vec<bool> = (0..n).map(|i| i % 2 == 0).collect();
776    let fib_air = FibonacciSelectorAir::new(sels, true);
777    let mut sender_air = DummyInteractionAir::new(1, true, 0);
778    sender_air.count_weight = 3;
779    let mut sender_air_2 = DummyInteractionAir::new(1, true, 0);
780    sender_air_2.count_weight = 1;
781    let mut sender_air_3 = DummyInteractionAir::new(1, true, 1);
782    sender_air_3.count_weight = 7;
783
784    let engine = E::new(default_test_params_small());
785    let airs: Vec<AirRef<SC>> = vec![
786        Arc::new(fib_air),
787        Arc::new(sender_air),
788        Arc::new(sender_air_2),
789        Arc::new(sender_air_3),
790    ];
791    let (_pk, vk) = engine.keygen(&airs);
792
793    assert_eq!(vk.inner.trace_height_constraints.len(), 3);
794
795    assert_eq!(
796        vk.inner.trace_height_constraints[0],
797        LinearConstraint {
798            coefficients: vec![0, 3, 1, 0],
799            threshold: F::ORDER_U32,
800        }
801    );
802    assert_eq!(
803        vk.inner.trace_height_constraints[1],
804        LinearConstraint {
805            coefficients: vec![0, 0, 0, 7],
806            threshold: F::ORDER_U32,
807        }
808    );
809    assert_eq!(
810        vk.inner.trace_height_constraints[2],
811        LinearConstraint {
812            coefficients: vec![1, 1, 1, 1],
813            threshold: engine.params().logup.max_interaction_count,
814        }
815    );
816}
817
818pub fn trace_height_constraints_implied_removal<E: StarkEngine<SC = SC>>() {
819    let log_trace_degree = 3;
820    let n = 1usize << log_trace_degree;
821    let sels: Vec<bool> = (0..n).map(|i| i % 2 == 0).collect();
822    let fib_air = FibonacciSelectorAir::new(sels, true);
823    let sender_air = DummyInteractionAir::new(1, true, 0);
824    let sender_air_2 = DummyInteractionAir::new(1, true, 1);
825
826    let engine = E::new(default_test_params_small());
827    let airs: Vec<AirRef<SC>> = vec![
828        Arc::new(fib_air),
829        Arc::new(sender_air),
830        Arc::new(sender_air_2),
831    ];
832    let (_pk, vk) = engine.keygen(&airs);
833
834    assert_eq!(vk.inner.trace_height_constraints.len(), 1);
835    assert_eq!(
836        vk.inner.trace_height_constraints[0],
837        LinearConstraint {
838            coefficients: vec![1, 1, 1],
839            threshold: engine.params().logup.max_interaction_count,
840        }
841    );
842}
843
844pub fn interaction_multi_rows_neg<E: StarkEngine<SC = SC>>() {
845    setup_tracing();
846
847    let sender_trace = RowMajorMatrix::new(
848        [0, 1, 3, 5, 7, 4, 546, 0]
849            .into_iter()
850            .map(F::from_usize)
851            .collect(),
852        2,
853    );
854    let sender_air = DummyInteractionAir::new(1, true, 0);
855
856    // count of 0 is 545 != 546 in sender
857    let receiver_trace = RowMajorMatrix::new(
858        [1, 5, 3, 4, 4, 4, 2, 5, 0, 123, 545, 0, 0, 0, 0, 456]
859            .into_iter()
860            .map(F::from_usize)
861            .collect(),
862        2,
863    );
864    let receiver_air = DummyInteractionAir::new(1, false, 0);
865
866    disable_debug_builder();
867    let engine = E::new(default_test_params_small());
868    let result = run_test_on_cpu_ctx(
869        &engine,
870        any_air_arc_vec![sender_air, receiver_air],
871        vec![
872            AirProvingContext::simple_no_pis(ColMajorMatrix::from_row_major(&sender_trace)),
873            AirProvingContext::simple_no_pis(ColMajorMatrix::from_row_major(&receiver_trace)),
874        ],
875    );
876    assert!(
877        result.is_err(),
878        "Expected test to fail with unbalanced interactions"
879    );
880}
881
882pub fn interaction_all_zero_sender<E: StarkEngine<SC = SC>>() -> eyre::Result<()> {
883    setup_tracing();
884
885    let sender_trace = RowMajorMatrix::new(
886        [0, 1, 0, 5, 0, 4, 0, 889]
887            .into_iter()
888            .map(F::from_usize)
889            .collect(),
890        2,
891    );
892    let sender_air = DummyInteractionAir::new(1, true, 0);
893
894    let engine = E::new(default_test_params_small());
895    run_test_on_cpu_ctx(
896        &engine,
897        any_air_arc_vec![sender_air],
898        vec![AirProvingContext::simple_no_pis(
899            ColMajorMatrix::from_row_major(&sender_trace),
900        )],
901    )?;
902    Ok(())
903}
904
905pub fn interaction_multi_senders<E: StarkEngine<SC = SC>>() -> eyre::Result<()> {
906    setup_tracing();
907
908    let sender_trace1 = RowMajorMatrix::new(
909        [0, 1, 3, 5, 6, 4, 333, 889]
910            .into_iter()
911            .map(F::from_usize)
912            .collect(),
913        2,
914    );
915    let sender_trace2 =
916        RowMajorMatrix::new([1, 4, 213, 889].into_iter().map(F::from_usize).collect(), 2);
917    let sender_air = DummyInteractionAir::new(1, true, 0);
918
919    let receiver_trace = RowMajorMatrix::new(
920        [1, 5, 3, 4, 4, 4, 2, 5, 0, 123, 545, 889, 1, 889, 0, 456]
921            .into_iter()
922            .map(F::from_usize)
923            .collect(),
924        2,
925    );
926    let receiver_air = DummyInteractionAir::new(1, false, 0);
927
928    let engine = E::new(default_test_params_small());
929    run_test_on_cpu_ctx(
930        &engine,
931        any_air_arc_vec![sender_air, sender_air, receiver_air],
932        vec![
933            AirProvingContext::simple_no_pis(ColMajorMatrix::from_row_major(&sender_trace1)),
934            AirProvingContext::simple_no_pis(ColMajorMatrix::from_row_major(&sender_trace2)),
935            AirProvingContext::simple_no_pis(ColMajorMatrix::from_row_major(&receiver_trace)),
936        ],
937    )?;
938    Ok(())
939}
940
941pub fn interaction_multi_senders_neg<E: StarkEngine<SC = SC>>() {
942    setup_tracing();
943
944    // Changed 6→5 for sender1 so sums don't balance
945    let sender_trace1 = RowMajorMatrix::new(
946        [0, 1, 3, 5, 5, 4, 333, 889]
947            .into_iter()
948            .map(F::from_usize)
949            .collect(),
950        2,
951    );
952    let sender_trace2 =
953        RowMajorMatrix::new([1, 4, 213, 889].into_iter().map(F::from_usize).collect(), 2);
954    let sender_air = DummyInteractionAir::new(1, true, 0);
955
956    let receiver_trace = RowMajorMatrix::new(
957        [1, 5, 3, 4, 4, 4, 2, 5, 0, 123, 545, 889, 1, 889, 0, 456]
958            .into_iter()
959            .map(F::from_usize)
960            .collect(),
961        2,
962    );
963    let receiver_air = DummyInteractionAir::new(1, false, 0);
964
965    disable_debug_builder();
966    let engine = E::new(default_test_params_small());
967    let result = run_test_on_cpu_ctx(
968        &engine,
969        any_air_arc_vec![sender_air, sender_air, receiver_air],
970        vec![
971            AirProvingContext::simple_no_pis(ColMajorMatrix::from_row_major(&sender_trace1)),
972            AirProvingContext::simple_no_pis(ColMajorMatrix::from_row_major(&sender_trace2)),
973            AirProvingContext::simple_no_pis(ColMajorMatrix::from_row_major(&receiver_trace)),
974        ],
975    );
976    assert!(
977        result.is_err(),
978        "Expected test to fail with unbalanced interactions"
979    );
980}
981
982pub fn interaction_multi_sender_receiver<E: StarkEngine<SC = SC>>() -> eyre::Result<()> {
983    setup_tracing();
984
985    let sender_trace1 = RowMajorMatrix::new(
986        [0, 1, 3, 5, 6, 4, 333, 889]
987            .into_iter()
988            .map(F::from_usize)
989            .collect(),
990        2,
991    );
992    let sender_trace2 =
993        RowMajorMatrix::new([1, 4, 213, 889].into_iter().map(F::from_usize).collect(), 2);
994    let sender_air = DummyInteractionAir::new(1, true, 0);
995
996    let receiver_trace1 = RowMajorMatrix::new(
997        [1, 5, 3, 4, 4, 4, 2, 5, 0, 123, 545, 889, 0, 289, 0, 456]
998            .into_iter()
999            .map(F::from_usize)
1000            .collect(),
1001        2,
1002    );
1003    let receiver_trace2 = RowMajorMatrix::new([1, 889].into_iter().map(F::from_usize).collect(), 2);
1004    let receiver_air = DummyInteractionAir::new(1, false, 0);
1005
1006    let engine = E::new(default_test_params_small());
1007    run_test_on_cpu_ctx(
1008        &engine,
1009        any_air_arc_vec![sender_air, sender_air, receiver_air, receiver_air],
1010        vec![
1011            AirProvingContext::simple_no_pis(ColMajorMatrix::from_row_major(&sender_trace1)),
1012            AirProvingContext::simple_no_pis(ColMajorMatrix::from_row_major(&sender_trace2)),
1013            AirProvingContext::simple_no_pis(ColMajorMatrix::from_row_major(&receiver_trace1)),
1014            AirProvingContext::simple_no_pis(ColMajorMatrix::from_row_major(&receiver_trace2)),
1015        ],
1016    )?;
1017    Ok(())
1018}
1019
1020pub fn interaction_cached_trace_neg<E: StarkEngine<SC = SC>>() {
1021    setup_tracing();
1022
1023    let engine = E::new(default_test_params_small());
1024    let config = engine.config().clone();
1025
1026    let mut sender_chip: DummyInteractionChip<SC> =
1027        DummyInteractionChip::new_without_partition(2, true, 0);
1028    sender_chip.load_data(DummyInteractionData {
1029        count: vec![0, 7, 3, 546],
1030        fields: vec![vec![1, 1], vec![4, 2], vec![5, 1], vec![889, 4]],
1031    });
1032
1033    // field [889, 4] has count 545 != 546 in sender
1034    let mut receiver_chip: DummyInteractionChip<SC> =
1035        DummyInteractionChip::new_with_partition(config, 2, false, 0);
1036    receiver_chip.load_data(DummyInteractionData {
1037        count: vec![1, 3, 4, 2, 0, 545, 1, 0],
1038        fields: vec![
1039            vec![5, 1],
1040            vec![4, 2],
1041            vec![4, 2],
1042            vec![5, 1],
1043            vec![123, 3],
1044            vec![889, 4],
1045            vec![889, 10], // changed from [889, 4] to cause mismatch
1046            vec![456, 5],
1047        ],
1048    });
1049
1050    let airs = vec![receiver_chip.air(), sender_chip.air()];
1051    let ctxs = vec![
1052        receiver_chip.generate_proving_ctx(),
1053        sender_chip.generate_proving_ctx(),
1054    ];
1055
1056    disable_debug_builder();
1057    let device = engine.device();
1058    let (pk, vk) = engine.keygen(&airs);
1059    let d_pk = device.transport_pk_to_device(&pk);
1060    let cpu_ctx = ProvingContext::new(ctxs.into_iter().enumerate().collect());
1061    let d_ctx = device.transport_proving_ctx_to_device(&cpu_ctx);
1062    let result = engine.prove(&d_pk, d_ctx);
1063    if let Ok(proof) = result {
1064        assert!(
1065            engine.verify(&vk, &proof).is_err(),
1066            "Expected verification to fail with unbalanced interactions"
1067        );
1068    }
1069}
1070
1071// ===========================================================================
1072// 7. WHIR tests (PCS-level, not engine-generic)
1073// ===========================================================================
1074
1075/// Generate random evaluation points for WHIR tests.
1076pub fn generate_random_z(params: &SystemParams, rng: &mut StdRng) -> (Vec<EF>, Vec<EF>) {
1077    let z_prism: Vec<_> = (0..params.n_stack + 1)
1078        .map(|_| EF::from_u64(rng.random()))
1079        .collect();
1080
1081    let z_cube = {
1082        let z_cube = z_prism[0]
1083            .exp_powers_of_2()
1084            .take(params.l_skip)
1085            .chain(z_prism[1..].iter().copied())
1086            .collect_vec();
1087        debug_assert_eq!(z_cube.len(), params.n_stack + params.l_skip);
1088        z_cube
1089    };
1090
1091    (z_prism, z_cube)
1092}
1093
1094/// Compute stacking openings for a single matrix at the given evaluation point.
1095pub fn stacking_openings_for_matrix(
1096    params: &SystemParams,
1097    z_prism: &[EF],
1098    matrix: &ColMajorMatrix<F>,
1099) -> Vec<EF> {
1100    matrix
1101        .columns()
1102        .map(|col| {
1103            Ple::from_evaluations(params.l_skip, col).eval_at_point(
1104                params.l_skip,
1105                z_prism[0],
1106                &z_prism[1..],
1107            )
1108        })
1109        .collect()
1110}
1111
1112/// Run a CPU WHIR prove-then-verify cycle for the given proving key and context.
1113fn run_whir_test(
1114    config: &SC,
1115    pk: DeviceMultiStarkProvingKey<CpuColMajorBackend<SC>>,
1116    ctx: &ProvingContext<CpuColMajorBackend<SC>>,
1117) -> eyre::Result<()> {
1118    let params = config.params();
1119    let (common_main_commit, common_main_pcs_data) = {
1120        let traces = ctx
1121            .common_main_traces()
1122            .map(|(_, trace)| trace)
1123            .collect_vec();
1124        stacked_commit(
1125            config.hasher(),
1126            params.l_skip,
1127            params.n_stack,
1128            params.log_blowup,
1129            params.k_whir(),
1130            &traces,
1131        )?
1132    };
1133
1134    let mut commits = vec![common_main_commit];
1135    let mut committed_mats = vec![(&common_main_pcs_data.matrix, &common_main_pcs_data.tree)];
1136    for (air_id, trace_ctx) in &ctx.per_trace {
1137        let pcs_datas = pk.per_air[*air_id]
1138            .preprocessed_data
1139            .iter()
1140            .chain(&trace_ctx.cached_mains);
1141        for cd in pcs_datas {
1142            let data = &cd.data;
1143            committed_mats.push((&data.matrix, &data.tree));
1144            commits.push(data.commit()?);
1145        }
1146    }
1147
1148    let mut rng = StdRng::seed_from_u64(0);
1149    let (z_prism, z_cube) = generate_random_z(params, &mut rng);
1150
1151    let mut prover_sponge = default_duplex_sponge_recorder();
1152
1153    let proof = prove_whir_opening::<SC, _>(
1154        &mut prover_sponge,
1155        config.hasher(),
1156        params.l_skip,
1157        params.log_blowup,
1158        params.whir(),
1159        &committed_mats,
1160        &z_cube,
1161    )?;
1162
1163    let stacking_openings = committed_mats
1164        .iter()
1165        .map(|(matrix, _)| stacking_openings_for_matrix(params, &z_prism, matrix))
1166        .collect_vec();
1167
1168    let mut verifier_sponge =
1169        DuplexSpongeValidator::new(poseidon2_perm().clone(), prover_sponge.into_log());
1170    verify_whir::<SC, _>(
1171        &mut verifier_sponge,
1172        config,
1173        &proof,
1174        &stacking_openings,
1175        &commits,
1176        &z_cube,
1177    )?;
1178    Ok(())
1179}
1180
1181fn run_whir_fib_test(params: SystemParams) -> eyre::Result<()> {
1182    let engine = BabyBearPoseidon2RefEngine::<DuplexSponge>::new(params.clone());
1183    let fib = FibFixture::new(0, 1, 1 << params.log_stacked_height());
1184    let (pk, _vk) = fib.keygen(&engine);
1185    let pk = engine.device().transport_pk_to_device(&pk);
1186    let ctx = fib.generate_proving_ctx();
1187    run_whir_test(engine.config(), pk, &ctx)
1188}
1189
1190/// Test binary k-fold operation with k=1.
1191pub fn fold_single() {
1192    let mut rng = StdRng::seed_from_u64(0);
1193
1194    let a0 = EF::from_u32(rng.random());
1195    let a1 = EF::from_u32(rng.random());
1196    let alpha = EF::from_u32(rng.random());
1197    let x = F::from_u32(rng.random());
1198
1199    let result = binary_k_fold(vec![a0, a1], &[alpha], x);
1200    assert_eq!(result, a0 + (alpha - x) * (a0 - a1) * x.double().inverse());
1201}
1202
1203/// Test binary k-fold operation with k=2.
1204pub fn fold_double() {
1205    let mut rng = StdRng::seed_from_u64(0);
1206
1207    let a0 = EF::from_u32(rng.random());
1208    let a1 = EF::from_u32(rng.random());
1209    let a2 = EF::from_u32(rng.random());
1210    let a3 = EF::from_u32(rng.random());
1211    let alpha0 = EF::from_u32(rng.random());
1212    let alpha1 = EF::from_u32(rng.random());
1213
1214    let x = F::from_u32(rng.random());
1215
1216    let result = binary_k_fold(vec![a0, a1, a2, a3], &[alpha0, alpha1], x);
1217    let tw = F::two_adic_generator(2);
1218
1219    let b0 = a0 + (alpha0 - x) * (a0 - a2) * x.double().inverse();
1220    let b1 = a1 + (alpha0 - (tw * x)) * (a1 - a3) * (tw * x).double().inverse();
1221    let x2 = x.square();
1222    let expected = b0 + (alpha1 - x2) * (b0 - b1) * x2.double().inverse();
1223
1224    assert_eq!(result, expected);
1225}
1226
1227/// Test CPU WHIR prover + verifier with a single Fibonacci commitment under
1228/// varying stacking and folding parameters.
1229pub fn whir_single_fib(
1230    n_stack: usize,
1231    log_blowup: usize,
1232    k_whir: usize,
1233    log_final_poly_len: usize,
1234) -> eyre::Result<()> {
1235    setup_tracing_with_log_level(Level::DEBUG);
1236    let l_skip = 2;
1237    let w_stack = 8;
1238    let whir = test_whir_config_small(log_blowup, l_skip + n_stack, k_whir, log_final_poly_len);
1239
1240    let params = SystemParams {
1241        l_skip,
1242        n_stack,
1243        w_stack,
1244        log_blowup,
1245        whir,
1246        logup: log_up_security_params_baby_bear_100_bits(0.0),
1247        max_constraint_degree: 3,
1248    };
1249    run_whir_fib_test(params)
1250}
1251
1252/// Build a [`WhirConfig`] with 2 rounds for multi-commitment WHIR tests.
1253pub fn whir_test_config(k_whir: usize) -> WhirConfig {
1254    WhirConfig {
1255        k: k_whir,
1256        rounds: vec![
1257            WhirRoundConfig { num_queries: 6 },
1258            WhirRoundConfig { num_queries: 5 },
1259        ],
1260        mu_pow_bits: 1,
1261        query_phase_pow_bits: 1,
1262        folding_pow_bits: 1,
1263        proximity: WhirProximityStrategy::UniqueDecoding, /* not relevant since `rounds` is
1264                                                           * manually set above */
1265    }
1266}
1267
1268/// Test CPU WHIR prover + verifier with 5 randomly generated commitments.
1269pub fn whir_multiple_commitments() -> eyre::Result<()> {
1270    setup_tracing_with_log_level(Level::DEBUG);
1271
1272    let mut rng = StdRng::seed_from_u64(42);
1273
1274    let params = SystemParams {
1275        l_skip: 3,
1276        n_stack: 3,
1277        w_stack: 64,
1278        log_blowup: 1,
1279        whir: whir_test_config(2),
1280        logup: log_up_security_params_baby_bear_100_bits(0.0),
1281        max_constraint_degree: 3,
1282    };
1283    let config = BabyBearPoseidon2Config::default_from_params(params);
1284    let params = config.params();
1285
1286    let n_rows = 1 << (params.n_stack + params.l_skip);
1287
1288    let mut matrices = vec![];
1289    let mut commits = vec![];
1290    let mut trees = vec![];
1291
1292    let num_commitments = 5;
1293    for _ in 0..num_commitments {
1294        let n_cols = (rng.random::<u64>() % 10 + 3) as usize;
1295        let data = (0..n_rows * n_cols)
1296            .map(|_| F::from_u64(rng.random()))
1297            .collect_vec();
1298        let mat = ColMajorMatrix::new(data, n_cols);
1299
1300        let (commit, pcs_data) = stacked_commit(
1301            config.hasher(),
1302            params.l_skip,
1303            params.n_stack,
1304            params.log_blowup,
1305            params.k_whir(),
1306            &[&mat],
1307        )?;
1308
1309        matrices.push(mat);
1310        commits.push(commit);
1311        trees.push(pcs_data.tree);
1312    }
1313
1314    debug_assert_eq!(matrices[0].height(), 1 << (params.n_stack + params.l_skip));
1315
1316    let (z_prism, z_cube) = generate_random_z(params, &mut rng);
1317
1318    let mut prover_sponge = default_duplex_sponge_recorder();
1319
1320    let committed_mats = matrices.iter().zip(trees.iter()).collect_vec();
1321    let proof = prove_whir_opening::<SC, _>(
1322        &mut prover_sponge,
1323        config.hasher(),
1324        params.l_skip,
1325        params.log_blowup,
1326        params.whir(),
1327        &committed_mats,
1328        &z_cube,
1329    )?;
1330
1331    let stacking_openings: Vec<Vec<EF>> = matrices
1332        .iter()
1333        .map(|mat| stacking_openings_for_matrix(params, &z_prism, mat))
1334        .collect();
1335
1336    let mut verifier_sponge =
1337        DuplexSpongeValidator::new(poseidon2_perm().clone(), prover_sponge.into_log());
1338    verify_whir::<SC, _>(
1339        &mut verifier_sponge,
1340        &config,
1341        &proof,
1342        &stacking_openings,
1343        &commits,
1344        &z_cube,
1345    )?;
1346    Ok(())
1347}
1348
1349/// Soundness test: verify that WHIR correctly rejects tampered openings.
1350pub fn whir_multiple_commitments_negative() {
1351    setup_tracing_with_log_level(Level::DEBUG);
1352
1353    let mut rng = StdRng::seed_from_u64(42);
1354
1355    let params = SystemParams {
1356        l_skip: 3,
1357        n_stack: 3,
1358        w_stack: 64,
1359        log_blowup: 1,
1360        whir: whir_test_config(2),
1361        logup: log_up_security_params_baby_bear_100_bits(0.0),
1362        max_constraint_degree: 3,
1363    };
1364    let config = BabyBearPoseidon2Config::default_from_params(params);
1365    let params = config.params();
1366
1367    let n_rows = 1 << (params.n_stack + params.l_skip);
1368
1369    let mut matrices = vec![];
1370    let mut commits = vec![];
1371    let mut trees = vec![];
1372
1373    let num_commitments = 5;
1374    for _ in 0..num_commitments {
1375        let n_cols = (rng.random::<u64>() % 10 + 3) as usize;
1376        let data = (0..n_rows * n_cols)
1377            .map(|_| F::from_u64(rng.random()))
1378            .collect_vec();
1379        let mat = ColMajorMatrix::new(data, n_cols);
1380
1381        let (commit, pcs_data) = stacked_commit(
1382            config.hasher(),
1383            params.l_skip,
1384            params.n_stack,
1385            params.log_blowup,
1386            params.k_whir(),
1387            &[&mat],
1388        )
1389        .unwrap();
1390
1391        matrices.push(mat);
1392        commits.push(commit);
1393        trees.push(pcs_data.tree);
1394    }
1395
1396    debug_assert_eq!(matrices[0].height(), 1 << (params.n_stack + params.l_skip));
1397
1398    let (z_prism, z_cube) = generate_random_z(params, &mut rng);
1399
1400    let mut prover_sponge = default_duplex_sponge();
1401    let mut verifier_sponge = default_duplex_sponge();
1402
1403    let committed_mats = matrices.iter().zip(trees.iter()).collect_vec();
1404    let proof = prove_whir_opening::<SC, _>(
1405        &mut prover_sponge,
1406        config.hasher(),
1407        params.l_skip,
1408        params.log_blowup,
1409        params.whir(),
1410        &committed_mats,
1411        &z_cube,
1412    )
1413    .unwrap();
1414
1415    let mut stacking_openings: Vec<Vec<EF>> = matrices
1416        .iter()
1417        .map(|mat| stacking_openings_for_matrix(params, &z_prism, mat))
1418        .collect();
1419
1420    // change an opening to test soundness
1421    stacking_openings[1][2] = EF::ONE;
1422
1423    assert!(matches!(
1424        verify_whir::<SC, _>(
1425            &mut verifier_sponge,
1426            &config,
1427            &proof,
1428            &stacking_openings,
1429            &commits,
1430            &z_cube,
1431        ),
1432        Err(VerifyWhirError::FinalPolyConstraint)
1433    ));
1434}
1435
1436// ===========================================================================
1437// Test suite macros
1438// ===========================================================================
1439
1440/// Helper: generate `#[test]` functions for parameterized engine-generic tests.
1441///
1442/// Proc macro attributes like `#[test_case]` cannot be used inside
1443/// `macro_rules!` expansions — Rust's macro hygiene assigns different syntax
1444/// contexts to the generated tokens, causing the proc macro to emit wrapper
1445/// functions that fail to connect arguments to parameters. This helper
1446/// side-steps the issue by expanding each parameter set into its own `#[test]`
1447/// function via pure `macro_rules!`.
1448///
1449/// # Variants
1450///
1451/// ```ignore
1452/// // Function returning Result (calls .unwrap()):
1453/// __test_cases!($engine, fib_air_roundtrip, unwrap, {
1454///     test_fib_air_roundtrip(2, 10),
1455///     test_fib_air_roundtrip_small(2, 1),
1456/// });
1457///
1458/// // Function returning ():
1459/// __test_cases!($engine, single_preprocessed_trace_stark, {
1460///     test_single_preprocessed_trace_stark(10),
1461///     test_single_preprocessed_trace_stark_zero(0),
1462/// });
1463/// ```
1464#[doc(hidden)]
1465// Must export macro for $crate::__test_cases hygiene inside backend_test_suite!
1466#[macro_export]
1467macro_rules! __test_cases {
1468    // Engine-generic, returns Result (call .unwrap())
1469    ($engine:ty, $func:ident, unwrap, { $( $test_name:ident( $($arg:expr),* ) ),+ $(,)? }) => {
1470        $(
1471            #[test]
1472            fn $test_name() {
1473                $crate::$func::<$engine>($($arg),*).unwrap();
1474            }
1475        )+
1476    };
1477    // Engine-generic, returns ()
1478    ($engine:ty, $func:ident, { $( $test_name:ident( $($arg:expr),* ) ),+ $(,)? }) => {
1479        $(
1480            #[test]
1481            fn $test_name() {
1482                $crate::$func::<$engine>($($arg),*);
1483            }
1484        )+
1485    };
1486}
1487
1488/// Generate the complete shared backend test suite for the given engine type.
1489///
1490/// This macro expands to `#[test]` functions covering all engine-generic tests
1491/// plus WHIR PCS tests. Parameterized tests use the [`__test_cases!`] helper.
1492///
1493/// # Example
1494///
1495/// ```ignore
1496/// use openvm_stark_sdk::config::baby_bear_poseidon2::*;
1497///
1498/// type Engine = BabyBearPoseidon2RefEngine<DuplexSponge>;
1499/// openvm_backend_tests::backend_test_suite!(Engine);
1500/// ```
1501#[macro_export]
1502macro_rules! backend_test_suite {
1503    ($engine:ty) => {
1504        // === 1. Proof shape verification ===
1505
1506        $crate::__test_cases!($engine, proof_shape_verifier, unwrap, {
1507            test_proof_shape_verifier(),
1508        });
1509
1510        $crate::__test_cases!($engine, proof_shape_verifier_rng_system_params, unwrap, {
1511            test_proof_shape_verifier_rng_system_params(),
1512        });
1513
1514        // === 2. Simple end-to-end ===
1515
1516        $crate::__test_cases!($engine, interactions_single_sender_receiver_happy, unwrap, {
1517            test_interactions_single_sender_receiver_happy(),
1518        });
1519
1520        $crate::__test_cases!($engine, single_cached_trace_stark, unwrap, {
1521            test_single_cached_trace_stark(),
1522        });
1523
1524        $crate::__test_cases!($engine, single_preprocessed_trace_stark, unwrap, {
1525            test_single_preprocessed_trace_stark(10),
1526            test_single_preprocessed_trace_stark_log_height_gt_l_skip(3),
1527            test_single_preprocessed_trace_stark_log_height_eq_l_skip(2),
1528            test_single_preprocessed_trace_stark_log_height_lt_l_skip(1),
1529            test_single_preprocessed_trace_stark_log_height_zero(0),
1530        });
1531
1532        $crate::__test_cases!($engine, multi_interaction_traces_stark, unwrap, {
1533            test_multi_interaction_traces_stark(10),
1534            test_multi_interaction_traces_stark_log_height_gt_l_skip(3),
1535            test_multi_interaction_traces_stark_log_height_eq_l_skip(2),
1536            test_multi_interaction_traces_stark_log_height_lt_l_skip(1),
1537            test_multi_interaction_traces_stark_log_height_zero(0),
1538        });
1539
1540        $crate::__test_cases!($engine, mixture_traces_stark, unwrap, {
1541            test_mixture_traces_stark(10),
1542            test_mixture_traces_stark_log_height_gt_l_skip(3),
1543            test_mixture_traces_stark_log_height_eq_l_skip(2),
1544            test_mixture_traces_stark_log_height_lt_l_skip(1),
1545            test_mixture_traces_stark_log_height_zero(0),
1546        });
1547
1548        $crate::__test_cases!($engine, matrix_stacking_overflow, unwrap, {
1549            test_matrix_stacking_overflow(),
1550        });
1551
1552        // === 3. Roundtrip tests ===
1553
1554        $crate::__test_cases!($engine, fib_air_roundtrip, unwrap, {
1555            test_fib_air_roundtrip(2, 10),
1556            test_fib_air_roundtrip_log_trace_degree_1_lt_l_skip_2(2, 1),
1557            test_fib_air_roundtrip_log_trace_degree_0_lt_l_skip_2(2, 0),
1558            test_fib_air_roundtrip_log_trace_degree_2_lt_l_skip_3(3, 2),
1559            test_fib_air_roundtrip_large_l_skip(6, 10),
1560        });
1561
1562        $crate::__test_cases!($engine, dummy_interactions_roundtrip, unwrap, {
1563            test_dummy_interactions_roundtrip_2_8_3(2, 8, 3),
1564            test_dummy_interactions_roundtrip_5_5_4(5, 5, 4),
1565        });
1566
1567        $crate::__test_cases!($engine, cached_trace_roundtrip, unwrap, {
1568            test_cached_trace_roundtrip_2_8_3(2, 8, 3),
1569            test_cached_trace_roundtrip_5_5_4(5, 5, 4),
1570            test_cached_trace_roundtrip_5_8_3(5, 8, 3),
1571            test_cached_trace_roundtrip_6_7_3(6, 7, 3),
1572        });
1573
1574        $crate::__test_cases!($engine, preprocessed_trace_roundtrip, unwrap, {
1575            test_preprocessed_trace_roundtrip_2_8_3(2, 8, 3),
1576            test_preprocessed_trace_roundtrip_5_5_4(5, 5, 4),
1577        });
1578
1579        $crate::__test_cases!($engine, preprocessed_and_cached_trace_roundtrip, unwrap, {
1580            test_preprocessed_and_cached_trace_roundtrip_2_8_3_1(2, 8, 3, 1),
1581            test_preprocessed_and_cached_trace_roundtrip_2_8_3_2(2, 8, 3, 2),
1582            test_preprocessed_and_cached_trace_roundtrip_2_8_3_3(2, 8, 3, 3),
1583            test_preprocessed_and_cached_trace_roundtrip_5_5_4_1(5, 5, 4, 1),
1584            test_preprocessed_and_cached_trace_roundtrip_5_5_4_2(5, 5, 4, 2),
1585            test_preprocessed_and_cached_trace_roundtrip_5_5_4_3(5, 5, 4, 3),
1586        });
1587
1588        // === 4. Pipeline decomposition ===
1589
1590        $crate::__test_cases!($engine, batch_sumcheck_zero_interactions, unwrap, {
1591            test_batch_sumcheck_zero_interactions(4),
1592            test_batch_sumcheck_zero_interactions_log_height_eq_l_skip(2),
1593            test_batch_sumcheck_zero_interactions_log_height_lt_l_skip(1),
1594            test_batch_sumcheck_zero_interactions_log_height_zero(0),
1595        });
1596
1597        $crate::__test_cases!($engine, batch_sumcheck_zero_interactions_malleable_q0, unwrap, {
1598            test_batch_sumcheck_zero_interactions_malleable_q0(),
1599        });
1600
1601        $crate::__test_cases!($engine, gkr_verify_zero_interactions, unwrap, {
1602            test_gkr_verify_zero_interactions(),
1603        });
1604
1605        $crate::__test_cases!($engine, batch_constraints_with_interactions, unwrap, {
1606            test_batch_constraints_with_interactions(),
1607        });
1608
1609        // === 5. Custom context construction ===
1610
1611        $crate::__test_cases!($engine, single_fib_and_dummy_trace_stark, unwrap, {
1612            test_single_fib_and_dummy_trace_stark(3),
1613            test_single_fib_and_dummy_trace_stark_log_height_eq_l_skip(2),
1614            test_single_fib_and_dummy_trace_stark_log_height_lt_l_skip(1),
1615            test_single_fib_and_dummy_trace_stark_log_height_zero(0),
1616        });
1617
1618        // === 6. Interaction tests ===
1619
1620        $crate::__test_cases!($engine, optional_air, unwrap, {
1621            test_optional_air(),
1622        });
1623
1624        $crate::__test_cases!($engine, vkey_methods, {
1625            test_vkey_methods(),
1626        });
1627
1628        $crate::__test_cases!($engine, interaction_trace_height_constraints, {
1629            test_interaction_trace_height_constraints(),
1630        });
1631
1632        $crate::__test_cases!($engine, trace_height_constraints_implied_removal, {
1633            test_trace_height_constraints_implied_removal(),
1634        });
1635
1636        $crate::__test_cases!($engine, interaction_multi_rows_neg, {
1637            test_interaction_multi_rows_neg(),
1638        });
1639
1640        $crate::__test_cases!($engine, interaction_all_zero_sender, unwrap, {
1641            test_interaction_all_zero_sender(),
1642        });
1643
1644        $crate::__test_cases!($engine, interaction_multi_senders, unwrap, {
1645            test_interaction_multi_senders(),
1646        });
1647
1648        $crate::__test_cases!($engine, interaction_multi_senders_neg, {
1649            test_interaction_multi_senders_neg(),
1650        });
1651
1652        $crate::__test_cases!($engine, interaction_multi_sender_receiver, unwrap, {
1653            test_interaction_multi_sender_receiver(),
1654        });
1655
1656        $crate::__test_cases!($engine, interaction_cached_trace_neg, {
1657            test_interaction_cached_trace_neg(),
1658        });
1659
1660        // === 7. WHIR PCS tests (not engine-generic, plain wrappers) ===
1661
1662        #[test]
1663        fn test_fold_single() {
1664            $crate::fold_single();
1665        }
1666
1667        #[test]
1668        fn test_fold_double() {
1669            $crate::fold_double();
1670        }
1671
1672        #[test]
1673        fn test_whir_single_fib_0_1_1_0() {
1674            $crate::whir_single_fib(0, 1, 1, 0).unwrap();
1675        }
1676
1677        #[test]
1678        fn test_whir_single_fib_2_1_1_2() {
1679            $crate::whir_single_fib(2, 1, 1, 2).unwrap();
1680        }
1681
1682        #[test]
1683        fn test_whir_single_fib_2_1_2_0() {
1684            $crate::whir_single_fib(2, 1, 2, 0).unwrap();
1685        }
1686
1687        #[test]
1688        fn test_whir_single_fib_2_1_3_1() {
1689            $crate::whir_single_fib(2, 1, 3, 1).unwrap();
1690        }
1691
1692        #[test]
1693        fn test_whir_single_fib_2_1_4_0() {
1694            $crate::whir_single_fib(2, 1, 4, 0).unwrap();
1695        }
1696
1697        #[test]
1698        fn test_whir_single_fib_2_2_4_0() {
1699            $crate::whir_single_fib(2, 2, 4, 0).unwrap();
1700        }
1701
1702        #[test]
1703        fn test_whir_multiple_commitments() {
1704            $crate::whir_multiple_commitments().unwrap();
1705        }
1706
1707        #[test]
1708        fn test_whir_multiple_commitments_negative() {
1709            $crate::whir_multiple_commitments_negative();
1710        }
1711    };
1712}
openvm_backend_tests/lib.rs

openvm_backend_tests/
lib.rs
