miden_air/
config.rs

1//! STARK configuration factories for different hash functions.
2//!
3//! Each factory creates a [`StarkConfig`](miden_crypto::stark::StarkConfig) bundling the
4//! PCS parameters, LMCS commitment scheme, and Fiat-Shamir challenger for proving and verification.
5
6use alloc::vec;
7
8use miden_core::{Felt, field::QuadFelt};
9use miden_crypto::{
10    field::Field,
11    hash::{
12        blake::Blake3Hasher,
13        keccak::{Keccak256Hash, KeccakF, VECTOR_LEN},
14        poseidon2::Poseidon2Permutation256,
15        rpo::RpoPermutation256,
16        rpx::RpxPermutation256,
17    },
18    stark::{
19        GenericStarkConfig,
20        challenger::{CanObserve, DuplexChallenger, HashChallenger, SerializingChallenger64},
21        dft::Radix2DitParallel,
22        fri::PcsParams,
23        hasher::{ChainingHasher, SerializingStatefulSponge, StatefulSponge},
24        lmcs::LmcsConfig,
25        symmetric::{
26            CompressionFunctionFromHasher, CryptographicPermutation, PaddingFreeSponge,
27            TruncatedPermutation,
28        },
29    },
30};
31
32// SHARED TYPES
33// ================================================================================================
34
35/// Miden VM STARK configuration with pre-filled common type parameters.
36///
37/// All Miden configurations use `Felt` as the base field, `QuadFelt` as the extension field,
38/// and `Radix2DitParallel<Felt>` as the DFT. Only the LMCS commitment scheme (`L`) and
39/// Fiat-Shamir challenger (`Ch`) vary by hash function.
40pub type MidenStarkConfig<L, Ch> =
41    GenericStarkConfig<Felt, QuadFelt, L, Radix2DitParallel<Felt>, Ch>;
42
43type PackedFelt = <Felt as Field>::Packing;
44
45/// Number of inputs to the Merkle compression function.
46const COMPRESSION_INPUTS: usize = 2;
47
48// PCS PARAMETERS
49// ================================================================================================
50
51/// Log2 of the FRI blowup factor (blowup = 8).
52const LOG_BLOWUP: u8 = 3;
53/// Log2 of the FRI folding arity (arity = 4).
54pub const LOG_FOLDING_ARITY: u8 = 2;
55/// Log2 of the final polynomial degree (degree = 128).
56const LOG_FINAL_DEGREE: u8 = 7;
57/// Proof-of-work bits for FRI folding challenges.
58pub const FOLDING_POW_BITS: usize = 4;
59/// Proof-of-work bits for DEEP composition polynomial.
60pub const DEEP_POW_BITS: usize = 12;
61/// Number of FRI query repetitions.
62const NUM_QUERIES: usize = 27;
63/// Proof-of-work bits for query phase.
64const QUERY_POW_BITS: usize = 16;
65
66/// Default PCS parameters shared by all hash function configurations.
67pub fn pcs_params() -> PcsParams {
68    PcsParams::new(
69        LOG_BLOWUP,
70        LOG_FOLDING_ARITY,
71        LOG_FINAL_DEGREE,
72        FOLDING_POW_BITS,
73        DEEP_POW_BITS,
74        NUM_QUERIES,
75        QUERY_POW_BITS,
76    )
77    .expect("invalid PCS parameters")
78}
79
80// DOMAIN-SEPARATED FIAT-SHAMIR TRANSCRIPT
81// ================================================================================================
82
83/// RELATION_DIGEST = Poseidon2::hash_elements([PROTOCOL_ID, CIRCUIT_COMMITMENT]).
84///
85/// Compile-time constant binding the Fiat-Shamir transcript to the Miden VM AIR.
86/// Must match the constants in `crates/lib/core/asm/sys/vm/mod.masm`.
87pub const RELATION_DIGEST: [Felt; 4] = [
88    Felt::new(9663888320842941557),
89    Felt::new(5569923100392661778),
90    Felt::new(10686243500486164404),
91    Felt::new(9017524969302659247),
92];
93
94/// Observes PCS protocol parameters and per-proof trace height into the challenger.
95///
96/// Call on a challenger obtained from `config.challenger()` to complete the
97/// domain-separated transcript initialization. The config factories already bind
98/// RELATION_DIGEST into the prototype challenger; this function adds the remaining
99/// protocol parameters and per-proof trace height.
100pub fn observe_protocol_params(challenger: &mut impl CanObserve<Felt>, log_trace_height: u64) {
101    // Batch 1: PCS parameters, zero-padded to SPONGE_RATE.
102    challenger.observe(Felt::new(NUM_QUERIES as u64));
103    challenger.observe(Felt::new(QUERY_POW_BITS as u64));
104    challenger.observe(Felt::new(DEEP_POW_BITS as u64));
105    challenger.observe(Felt::new(FOLDING_POW_BITS as u64));
106    challenger.observe(Felt::new(LOG_BLOWUP as u64));
107    challenger.observe(Felt::new(LOG_FINAL_DEGREE as u64));
108    challenger.observe(Felt::new(1_u64 << LOG_FOLDING_ARITY));
109    challenger.observe(Felt::ZERO);
110
111    // Batch 2: per-proof trace height, zero-padded to SPONGE_RATE.
112    challenger.observe(Felt::new(log_trace_height));
113    for _ in 1..SPONGE_RATE {
114        challenger.observe(Felt::ZERO);
115    }
116}
117
118/// Absorbs variable-length public inputs into the challenger.
119///
120/// Each VLPI group is a flat slice of fixed-width messages. `message_widths[i]` gives the
121/// width of each message in group `i`. Every message is zero-padded to the next multiple
122/// of `SPONGE_RATE` and reversed before observation, matching the layout the MASM recursive
123/// verifier's `mem_stream` + `horner_eval_base` expects.
124pub fn observe_var_len_public_inputs<C: CanObserve<Felt>>(
125    challenger: &mut C,
126    var_len_public_inputs: &[&[Felt]],
127    message_widths: &[usize],
128) {
129    assert_eq!(
130        var_len_public_inputs.len(),
131        message_widths.len(),
132        "must provide one message width per VLPI group"
133    );
134    for (group, &msg_width) in var_len_public_inputs.iter().zip(message_widths) {
135        assert!(msg_width > 0, "VLPI message width must be positive");
136        let padded_width = msg_width.next_multiple_of(SPONGE_RATE);
137        for message in group.chunks(msg_width) {
138            assert_eq!(
139                message.len(),
140                msg_width,
141                "VLPI group has trailing elements that don't form a complete message"
142            );
143            let mut padded = vec![Felt::ZERO; padded_width];
144            for (i, &elem) in message.iter().enumerate() {
145                padded[padded_width - 1 - i] = elem;
146            }
147            challenger.observe_slice(&padded);
148        }
149    }
150}
151
152// ALGEBRAIC HASHES (RPO, Poseidon2, RPX)
153// ================================================================================================
154
155/// Sponge state width in field elements.
156const SPONGE_WIDTH: usize = 12;
157/// Sponge rate (absorbable elements per permutation).
158const SPONGE_RATE: usize = 8;
159/// Sponge digest width in field elements.
160const DIGEST_WIDTH: usize = 4;
161/// Range of capacity slots within the sponge state array.
162const CAPACITY_RANGE: core::ops::Range<usize> = SPONGE_RATE..SPONGE_WIDTH;
163
164/// Algebraic LMCS (for RPO, Poseidon2, RPX).
165type AlgLmcs<P> = LmcsConfig<
166    PackedFelt,
167    PackedFelt,
168    StatefulSponge<P, SPONGE_WIDTH, SPONGE_RATE, DIGEST_WIDTH>,
169    TruncatedPermutation<P, COMPRESSION_INPUTS, DIGEST_WIDTH, SPONGE_WIDTH>,
170    SPONGE_WIDTH,
171    DIGEST_WIDTH,
172>;
173
174/// Algebraic duplex challenger (for RPO, Poseidon2, RPX).
175type AlgChallenger<P> = DuplexChallenger<Felt, P, SPONGE_WIDTH, SPONGE_RATE>;
176
177/// Concrete STARK configuration type for Poseidon2.
178pub type Poseidon2Config =
179    MidenStarkConfig<AlgLmcs<Poseidon2Permutation256>, AlgChallenger<Poseidon2Permutation256>>;
180
181/// Creates an RPO-based STARK configuration.
182pub fn rpo_config(
183    params: PcsParams,
184) -> MidenStarkConfig<AlgLmcs<RpoPermutation256>, AlgChallenger<RpoPermutation256>> {
185    alg_config(params, RpoPermutation256)
186}
187
188/// Creates a Poseidon2-based STARK configuration.
189pub fn poseidon2_config(
190    params: PcsParams,
191) -> MidenStarkConfig<AlgLmcs<Poseidon2Permutation256>, AlgChallenger<Poseidon2Permutation256>> {
192    alg_config(params, Poseidon2Permutation256)
193}
194
195/// Creates an RPX-based STARK configuration.
196pub fn rpx_config(
197    params: PcsParams,
198) -> MidenStarkConfig<AlgLmcs<RpxPermutation256>, AlgChallenger<RpxPermutation256>> {
199    alg_config(params, RpxPermutation256)
200}
201
202/// Internal helper: builds an algebraic STARK configuration from a permutation.
203///
204/// The prototype challenger has RELATION_DIGEST pre-loaded in the sponge capacity.
205/// When `observe_protocol_params` is called, the first duplexing permutes this
206/// capacity together with the PCS parameters written into the rate.
207fn alg_config<P>(params: PcsParams, perm: P) -> MidenStarkConfig<AlgLmcs<P>, AlgChallenger<P>>
208where
209    P: CryptographicPermutation<[Felt; SPONGE_WIDTH]> + Copy,
210{
211    let lmcs = LmcsConfig::new(StatefulSponge::new(perm), TruncatedPermutation::new(perm));
212    let mut state = [Felt::ZERO; SPONGE_WIDTH];
213    state[CAPACITY_RANGE].copy_from_slice(&RELATION_DIGEST);
214    let challenger = DuplexChallenger {
215        sponge_state: state,
216        input_buffer: vec![],
217        output_buffer: vec![],
218        permutation: perm,
219    };
220    GenericStarkConfig::new(params, lmcs, Radix2DitParallel::default(), challenger)
221}
222
223// BLAKE3
224// ================================================================================================
225
226/// Digest size in bytes for Blake3.
227const BLAKE_DIGEST_SIZE: usize = 32;
228
229/// Blake3 LMCS.
230type BlakeLmcs = LmcsConfig<
231    Felt,
232    u8,
233    ChainingHasher<Blake3Hasher>,
234    CompressionFunctionFromHasher<Blake3Hasher, COMPRESSION_INPUTS, BLAKE_DIGEST_SIZE>,
235    BLAKE_DIGEST_SIZE,
236    BLAKE_DIGEST_SIZE,
237>;
238
239/// Blake3 challenger.
240type BlakeChallenger =
241    SerializingChallenger64<Felt, HashChallenger<u8, Blake3Hasher, BLAKE_DIGEST_SIZE>>;
242
243/// Creates a Blake3_256-based STARK configuration.
244pub fn blake3_256_config(params: PcsParams) -> MidenStarkConfig<BlakeLmcs, BlakeChallenger> {
245    let lmcs = LmcsConfig::new(
246        ChainingHasher::new(Blake3Hasher),
247        CompressionFunctionFromHasher::new(Blake3Hasher),
248    );
249    let mut challenger = SerializingChallenger64::from_hasher(vec![], Blake3Hasher);
250    challenger.observe_slice(&RELATION_DIGEST);
251    GenericStarkConfig::new(params, lmcs, Radix2DitParallel::default(), challenger)
252}
253
254// KECCAK
255// ================================================================================================
256
257/// Keccak permutation state width (in u64 elements).
258const KECCAK_WIDTH: usize = 25;
259/// Keccak sponge rate (absorbable u64 elements per permutation).
260const KECCAK_RATE: usize = 17;
261/// Keccak digest width (in u64 elements).
262const KECCAK_DIGEST: usize = 4;
263/// Keccak-256 digest size in bytes (for the Fiat-Shamir challenger).
264const KECCAK_CHALLENGER_DIGEST_SIZE: usize = 32;
265
266/// Keccak MMCS sponge (padding-free, used for compression).
267type KeccakMmcsSponge = PaddingFreeSponge<KeccakF, KECCAK_WIDTH, KECCAK_RATE, KECCAK_DIGEST>;
268
269/// Keccak LMCS using the stateful binary sponge with `[Felt; VECTOR_LEN]` packing.
270type KeccakLmcs = LmcsConfig<
271    [Felt; VECTOR_LEN],
272    [u64; VECTOR_LEN],
273    SerializingStatefulSponge<StatefulSponge<KeccakF, KECCAK_WIDTH, KECCAK_RATE, KECCAK_DIGEST>>,
274    CompressionFunctionFromHasher<KeccakMmcsSponge, COMPRESSION_INPUTS, KECCAK_DIGEST>,
275    KECCAK_WIDTH,
276    KECCAK_DIGEST,
277>;
278
279/// Keccak challenger.
280type KeccakChallenger =
281    SerializingChallenger64<Felt, HashChallenger<u8, Keccak256Hash, KECCAK_CHALLENGER_DIGEST_SIZE>>;
282
283/// Creates a Keccak-based STARK configuration.
284///
285/// Uses the stateful binary sponge with the Keccak permutation and `[Felt; VECTOR_LEN]` packing
286/// for SIMD parallelization.
287pub fn keccak_config(params: PcsParams) -> MidenStarkConfig<KeccakLmcs, KeccakChallenger> {
288    let mmcs_sponge = KeccakMmcsSponge::new(KeccakF {});
289    let compress = CompressionFunctionFromHasher::new(mmcs_sponge);
290    let sponge = SerializingStatefulSponge::new(StatefulSponge::new(KeccakF {}));
291    let lmcs = LmcsConfig::new(sponge, compress);
292    let mut challenger = SerializingChallenger64::from_hasher(vec![], Keccak256Hash {});
293    challenger.observe_slice(&RELATION_DIGEST);
294    GenericStarkConfig::new(params, lmcs, Radix2DitParallel::default(), challenger)
295}
miden_air/config.rs

miden_air/
config.rs
