miden_air/trace/
challenges.rs

1//! Unified bus challenge encoding.
2//!
3//! Provides [`Challenges`], a single struct for encoding multiset/LogUp bus messages
4//! as `alpha + <beta, message>`. This type is used by:
5//!
6//! - **AIR constraints** (symbolic expressions): `Challenges<AB::ExprEF>`
7//! - **Processor aux trace builders** (concrete field elements): `Challenges<E>`
8//! - **Verifier** (`reduced_aux_values`): `Challenges<EF>`
9//!
10//! See [`super::bus_message`] for the standard coefficient index layout.
11
12use core::ops::{AddAssign, Mul};
13
14use miden_core::field::PrimeCharacteristicRing;
15
16use super::MAX_MESSAGE_WIDTH;
17
18/// Encodes multiset/LogUp contributions as **alpha + <beta, message>**.
19///
20/// - `alpha`: randomness base
21/// - `beta_powers`: precomputed powers `[beta^0, beta^1, ..., beta^(MAX_MESSAGE_WIDTH-1)]`
22///
23/// The challenges are derived from permutation randomness:
24/// - `alpha = challenges[0]`
25/// - `beta  = challenges[1]`
26///
27/// Precomputed once and passed by reference to all bus components.
28pub struct Challenges<EF: PrimeCharacteristicRing> {
29    pub alpha: EF,
30    pub beta_powers: [EF; MAX_MESSAGE_WIDTH],
31}
32
33impl<EF: PrimeCharacteristicRing> Challenges<EF> {
34    /// Builds `alpha` and precomputed `beta` powers.
35    pub fn new(alpha: EF, beta: EF) -> Self {
36        let mut beta_powers = core::array::from_fn(|_| EF::ONE);
37        for i in 1..MAX_MESSAGE_WIDTH {
38            beta_powers[i] = beta_powers[i - 1].clone() * beta.clone();
39        }
40        Self { alpha, beta_powers }
41    }
42
43    /// Encodes as **alpha + sum(beta_powers\[i\] * elem\[i\])** with K consecutive elements.
44    #[inline(always)]
45    pub fn encode<BF, const K: usize>(&self, elems: [BF; K]) -> EF
46    where
47        EF: Mul<BF, Output = EF> + AddAssign,
48        BF: Clone,
49    {
50        const { assert!(K <= MAX_MESSAGE_WIDTH, "Message length exceeds beta_powers capacity") };
51        let mut acc = self.alpha.clone();
52        for (i, elem) in elems.iter().enumerate() {
53            acc += self.beta_powers[i].clone() * elem.clone();
54        }
55        acc
56    }
57
58    /// Encodes as **alpha + sum(beta_powers\[layout\[i\]\] * values\[i\])** using sparse positions.
59    #[inline(always)]
60    pub fn encode_sparse<BF, const K: usize>(&self, layout: [usize; K], values: [BF; K]) -> EF
61    where
62        EF: Mul<BF, Output = EF> + AddAssign,
63        BF: Clone,
64    {
65        let mut acc = self.alpha.clone();
66        for i in 0..K {
67            let idx = layout[i];
68            debug_assert!(
69                idx < self.beta_powers.len(),
70                "encode_sparse index {} exceeds beta_powers length ({})",
71                idx,
72                self.beta_powers.len()
73            );
74            acc += self.beta_powers[idx].clone() * values[i].clone();
75        }
76        acc
77    }
78}
miden_air/trace/challenges.rs

miden_air/trace/
challenges.rs
