miden_stdlib/
lib.rs

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

miden_stdlib/
lib.rs
