openvm-stark-backend 2.0.0

Multi-matrix STARK backend for the SWIRL proof system
Documentation 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93

//! Backend for proving and verifying mixed-matrix STARKs.
//! The backend is designed to be modular and compatible with different hardware implementations.
//! The backend provides prover and verifier implementations of the SWIRL proof system.
//!
//! The aim is to support different circuit representations and permutation/lookup arguments.

// Re-export all Plonky3 crates
pub use p3_air;
pub use p3_challenger;
pub use p3_field;
pub use p3_matrix;
pub use p3_maybe_rayon;
pub use p3_symmetric;
pub use p3_util;
use p3_util::log2_ceil_u64;

/// AIR builders for prover and verifier, including support for cross-matrix permutation arguments.
pub mod air_builders;
pub mod codec;
/// Copy of Plonky3's DFT module without parallelism (Rayon) for faster single-threaded execution.
/// Used by the prover **only**.
pub mod dft;
/// Protocol hasher trait definition.
pub mod hasher;
/// Log-up permutation argument implementation as RAP.
pub mod interaction;
/// Proving and verifying key generation
pub mod keygen;
/// Memory estimates for segmented proving.
pub mod memory_metering;
/// Common polynomial utilities shared by prover and verifier
pub mod poly_common;
/// Definition of the STARK proof struct.
pub mod proof;
pub mod prover;
pub mod soundness;
pub mod utils;
pub mod verifier;

#[cfg(feature = "lean")]
pub mod lean;

#[cfg(any(test, feature = "test-utils"))]
pub mod test_utils;
// #[cfg(test)]
// pub mod tests;

/// Fiat-Shamir transcript trait and implementations (duplex sponge, multi-field).
pub mod transcript;

mod any_air;
/// STARK Protocol configuration trait
mod config;
/// Trait for STARK backend engine proving keygen, proviing, verifying API functions.
mod engine;
#[cfg(feature = "multi-field-transcript")]
pub mod multi_field_packing;
pub use any_air::*;
pub use config::*;
pub use engine::*;
pub use transcript::*;

// Use jemalloc as global allocator for performance
#[cfg(all(feature = "jemalloc", unix, not(test)))]
#[global_allocator]
static GLOBAL: tikv_jemallocator::Jemalloc = tikv_jemallocator::Jemalloc;

// Use mimalloc as global allocator
#[cfg(all(feature = "mimalloc", not(test)))]
#[global_allocator]
static GLOBAL: mimalloc::MiMalloc = mimalloc::MiMalloc;

/// Common utility function for computing `n_logup` parameter in terms of `total_interactions`,
/// which is the sum of interaction message counts across all traces, using the lifted trace
/// heights.
///
/// This calculation must be consistent between the prover and verifier and is enforced by
/// the verifier.
// NOTE: we could use a more strict calculation of `n_logup = log2_ceil(total_interactions >>
// l_skip)` but the `leading_zeros` calculation below is easier to check in the recursion
// circuit. The formula below is equivalent to `log2_ceil(total_interactions + 1) - l_skip`.
pub fn calculate_n_logup(l_skip: usize, total_interactions: u64) -> usize {
    if total_interactions != 0 {
        let n_logup = (u64::BITS - total_interactions.leading_zeros()) as usize - l_skip;
        debug_assert_eq!(
            n_logup + l_skip,
            log2_ceil_u64(total_interactions + 1) as usize
        );
        n_logup
    } else {
        0
    }
}