miden_stdlib/
lib.rs

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

miden_stdlib/
lib.rs
