miden_stdlib_sys/stdlib/collections/
smt.rs

1//! Bindings for the `std::collections::smt` module, which exposes sparse Merkle tree
2//! functionality from the Miden standard library.
3
4use crate::intrinsics::{Felt, Word, WordAligned};
5
6/// Result of [`smt_get`], containing the retrieved `value` and the (unchanged) `root`.
7#[derive(Debug, Clone, PartialEq, Eq)]
8pub struct SmtGetResponse {
9    pub value: Word,
10    pub root: Word,
11}
12
13/// Result of [`smt_set`], containing the `old_value` and the updated `new_root`.
14#[derive(Debug, Clone, PartialEq, Eq)]
15pub struct SmtSetResponse {
16    pub old_value: Word,
17    pub new_root: Word,
18}
19
20#[allow(improper_ctypes)]
21unsafe extern "C" {
22    /// Returns the value located under the specified `key` in the sparse Merkle tree defined by
23    /// the specified `root`.
24    ///
25    /// This maps to the `std::collections::smt::get` procedure.
26    ///
27    /// Inputs: `[key, root, ...]`
28    /// Outputs: `[value, root, ...]`
29    ///
30    /// Fails if the tree with the specified `root` does not exist in the VM's advice provider. When
31    /// no value has previously been inserted under `key`, the procedure returns the empty word.
32    #[cfg_attr(all(target_family = "wasm", miden), linkage = "extern_weak")]
33    #[link_name = "miden::core::collections::smt::get"]
34    fn extern_smt_get(
35        k0: Felt,
36        k1: Felt,
37        k2: Felt,
38        k3: Felt,
39        r0: Felt,
40        r1: Felt,
41        r2: Felt,
42        r3: Felt,
43        ptr: *mut (Word, Word),
44    );
45
46    /// Inserts `value` under `key` in the sparse Merkle tree defined by `root`.
47    ///
48    /// This maps to the `std::collections::smt::set` procedure.
49    ///
50    /// Inputs: `[value, key, root, ...]`
51    /// Outputs: `[old_value, new_root, ...]`
52    ///
53    /// On success, the prior value stored under `key` is returned along with the updated root. If
54    /// `value` is the empty word, the new tree state is equivalent to omitting the update.
55    ///
56    /// Fails if the tree with the specified `root` does not exist in the VM's advice provider.
57    #[cfg_attr(all(target_family = "wasm", miden), linkage = "extern_weak")]
58    #[link_name = "miden::core::collections::smt::set"]
59    fn extern_smt_set(
60        v0: Felt,
61        v1: Felt,
62        v2: Felt,
63        v3: Felt,
64        k0: Felt,
65        k1: Felt,
66        k2: Felt,
67        k3: Felt,
68        r0: Felt,
69        r1: Felt,
70        r2: Felt,
71        r3: Felt,
72        ptr: *mut (Word, Word),
73    );
74}
75
76/// Returns the value associated with `key` in the sparse Merkle tree rooted at `root` as tracked by
77/// the VM's advice provider. The returned [`SmtGetResponse`] contains the retrieved value and the
78/// (unchanged) root returned by the ABI.
79/// Fails if the tree with the specified `root` does not exist in the VM's advice provider. When
80/// no value has previously been inserted under `key`, the procedure returns the empty word.
81#[inline]
82pub fn smt_get(key: Word, root: Word) -> SmtGetResponse {
83    unsafe {
84        let mut ret_area = ::core::mem::MaybeUninit::<WordAligned<(Word, Word)>>::uninit();
85        let ptr = ret_area.as_mut_ptr() as *mut (Word, Word);
86        extern_smt_get(key[0], key[1], key[2], key[3], root[0], root[1], root[2], root[3], ptr);
87        let (value, returned_root) = ret_area.assume_init().into_inner();
88        SmtGetResponse {
89            value,
90            root: returned_root,
91        }
92    }
93}
94
95/// Inserts `value` at `key` in the sparse Merkle tree rooted at `root`, returning the prior value
96/// stored at `key` along with the new root. The returned [`SmtSetResponse`] contains
97/// the previous value stored under `key` and the updated root.
98/// Fails if the tree with the specified `root` does not exist in the VM's advice provider.
99#[inline]
100pub fn smt_set(value: Word, key: Word, root: Word) -> SmtSetResponse {
101    unsafe {
102        let mut ret_area = ::core::mem::MaybeUninit::<WordAligned<(Word, Word)>>::uninit();
103        let ptr = ret_area.as_mut_ptr() as *mut (Word, Word);
104        extern_smt_set(
105            value[0], value[1], value[2], value[3], key[0], key[1], key[2], key[3], root[0],
106            root[1], root[2], root[3], ptr,
107        );
108        let (old_value, new_root) = ret_area.assume_init().into_inner();
109        SmtSetResponse {
110            old_value,
111            new_root,
112        }
113    }
114}
miden_stdlib_sys/stdlib/collections/smt.rs

miden_stdlib_sys/stdlib/collections/
smt.rs
