miden_stdlib/
lib.rs

1#![no_std]
2
3extern crate alloc;
4
5use alloc::sync::Arc;
6
7use miden_assembly::{Library, mast::MastForest, utils::Deserializable};
8use miden_utils_sync::LazyLock;
9
10// STANDARD LIBRARY
11// ================================================================================================
12
13/// TODO: add docs
14#[derive(Clone)]
15pub struct StdLibrary(Library);
16
17impl AsRef<Library> for StdLibrary {
18    fn as_ref(&self) -> &Library {
19        &self.0
20    }
21}
22
23impl From<StdLibrary> for Library {
24    fn from(value: StdLibrary) -> Self {
25        value.0
26    }
27}
28
29impl StdLibrary {
30    /// Serialized representation of the Miden standard library.
31    pub const SERIALIZED: &'static [u8] =
32        include_bytes!(concat!(env!("OUT_DIR"), "/assets/std.masl"));
33
34    /// Returns a reference to the [MastForest] underlying the Miden standard library.
35    pub fn mast_forest(&self) -> &Arc<MastForest> {
36        self.0.mast_forest()
37    }
38}
39
40impl Default for StdLibrary {
41    fn default() -> Self {
42        static STDLIB: LazyLock<StdLibrary> = LazyLock::new(|| {
43            let contents =
44                Library::read_from_bytes(StdLibrary::SERIALIZED).expect("failed to read std masl!");
45            StdLibrary(contents)
46        });
47        STDLIB.clone()
48    }
49}
50
51// FALCON SIGNATURE
52// ================================================================================================
53
54/// Event ID for pushing a Falcon signature to the advice stack.
55/// This event is used for testing purposes only.
56pub const EVENT_FALCON_SIG_TO_STACK: u32 = 3419226139;
57
58/// Signs the provided message with the provided secret key and returns the resulting signature
59/// encoded in the format required by the rpo_faclcon512::verify procedure, or `None` if the secret
60/// key is malformed due to either incorrect length or failed decoding.
61///
62/// The values are the ones required for a Falcon signature verification inside the VM and they are:
63///
64/// 1. The challenge point, a tuple of elements representing an element in the quadratic extension
65///    field, at which we evaluate the polynomials in the subsequent three points to check the
66///    product relationship.
67/// 2. The expanded public key represented as the coefficients of a polynomial of degree < 512.
68/// 3. The signature represented as the coefficients of a polynomial of degree < 512.
69/// 4. The product of the above two polynomials in the ring of polynomials with coefficients in the
70///    Miden field.
71/// 5. The nonce represented as 8 field elements.
72#[cfg(feature = "std")]
73pub fn falcon_sign(
74    sk: &[miden_core::Felt],
75    msg: miden_core::Word,
76) -> Option<alloc::vec::Vec<miden_core::Felt>> {
77    use alloc::{vec, vec::Vec};
78
79    use miden_core::{
80        Felt,
81        crypto::{
82            dsa::rpo_falcon512::{Polynomial, SecretKey},
83            hash::Rpo256,
84        },
85        utils::Deserializable,
86    };
87
88    // Create the corresponding secret key
89    let mut sk_bytes = Vec::with_capacity(sk.len());
90    for element in sk {
91        let value = element.as_int();
92        if value > u8::MAX as u64 {
93            return None;
94        }
95        sk_bytes.push(value as u8);
96    }
97
98    let sk = SecretKey::read_from_bytes(&sk_bytes).ok()?;
99
100    // We can now generate the signature
101    let sig = sk.sign(msg);
102
103    // The signature is composed of a nonce and a polynomial s2
104
105    // The nonce is represented as 8 field elements.
106    let nonce = sig.nonce();
107
108    // We convert the signature to a polynomial
109    let s2 = sig.sig_poly();
110
111    // We also need in the VM the expanded key corresponding to the public key the was provided
112    // via the operand stack
113    let h = sk.compute_pub_key_poly().0;
114
115    // Lastly, for the probabilistic product routine that is part of the verification procedure,
116    // we need to compute the product of the expanded key and the signature polynomial in
117    // the ring of polynomials with coefficients in the Miden field.
118    let pi = Polynomial::mul_modulo_p(&h, s2);
119
120    // We now push the expanded key, the signature polynomial, and the product of the
121    // expanded key and the signature polynomial to the advice stack. We also push
122    // the challenge point at which the previous polynomials will be evaluated.
123    // Finally, we push the nonce needed for the hash-to-point algorithm.
124
125    let mut polynomials: Vec<Felt> =
126        h.coefficients.iter().map(|a| Felt::from(a.value() as u32)).collect();
127    polynomials.extend(s2.coefficients.iter().map(|a| Felt::from(a.value() as u32)));
128    polynomials.extend(pi.iter().map(|a| Felt::new(*a)));
129
130    let digest_polynomials = Rpo256::hash_elements(&polynomials);
131    let challenge = (digest_polynomials[0], digest_polynomials[1]);
132
133    let mut result: Vec<Felt> = vec![challenge.0, challenge.1];
134    result.extend_from_slice(&polynomials);
135    result.extend_from_slice(&nonce.to_elements());
136
137    result.reverse();
138    Some(result)
139}
140
141#[cfg(not(feature = "std"))]
142pub fn falcon_sign(
143    _pk_sk: &[miden_core::Felt],
144    _msg: miden_core::Word,
145) -> Option<alloc::vec::Vec<miden_core::Felt>> {
146    None
147}
148
149// TESTS
150// ================================================================================================
151
152#[cfg(test)]
153mod tests {
154    use miden_assembly::LibraryPath;
155
156    use super::*;
157
158    #[test]
159    fn test_compile() {
160        let path = "std::math::u64::overflowing_add".parse::<LibraryPath>().unwrap();
161        let stdlib = StdLibrary::default();
162        let exists = stdlib.0.module_infos().any(|module| {
163            module
164                .procedures()
165                .any(|(_, proc)| module.path().clone().append(&proc.name).unwrap() == path)
166        });
167
168        assert!(exists);
169    }
170}
miden_stdlib/lib.rs

miden_stdlib/
lib.rs
