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

miden_stdlib/
lib.rs
