miden_stdlib/
lib.rs

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

miden_stdlib/
lib.rs
