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    #[link_name = "std::collections::smt::get"]
33    fn extern_smt_get(
34        k3: Felt,
35        k2: Felt,
36        k1: Felt,
37        k0: Felt,
38        r3: Felt,
39        r2: Felt,
40        r1: Felt,
41        r0: Felt,
42        ptr: *mut (Word, Word),
43    );
44
45    /// Inserts `value` under `key` in the sparse Merkle tree defined by `root`.
46    ///
47    /// This maps to the `std::collections::smt::set` procedure.
48    ///
49    /// Inputs: `[value, key, root, ...]`
50    /// Outputs: `[old_value, new_root, ...]`
51    ///
52    /// On success, the prior value stored under `key` is returned along with the updated root. If
53    /// `value` is the empty word, the new tree state is equivalent to omitting the update.
54    ///
55    /// Fails if the tree with the specified `root` does not exist in the VM's advice provider.
56    #[link_name = "std::collections::smt::set"]
57    fn extern_smt_set(
58        v3: Felt,
59        v2: Felt,
60        v1: Felt,
61        v0: Felt,
62        k3: Felt,
63        k2: Felt,
64        k1: Felt,
65        k0: Felt,
66        r3: Felt,
67        r2: Felt,
68        r1: Felt,
69        r0: Felt,
70        ptr: *mut (Word, Word),
71    );
72}
73
74/// Returns the value associated with `key` in the sparse Merkle tree rooted at `root` as tracked by
75/// the VM's advice provider. The returned [`SmtGetResponse`] contains the retrieved value and the
76/// (unchanged) root returned by the ABI.
77/// Fails if the tree with the specified `root` does not exist in the VM's advice provider. When
78/// no value has previously been inserted under `key`, the procedure returns the empty word.
79#[inline]
80pub fn smt_get(key: Word, root: Word) -> SmtGetResponse {
81    unsafe {
82        let mut ret_area = ::core::mem::MaybeUninit::<WordAligned<(Word, Word)>>::uninit();
83        let ptr = ret_area.as_mut_ptr() as *mut (Word, Word);
84        extern_smt_get(key[3], key[2], key[1], key[0], root[3], root[2], root[1], root[0], ptr);
85        let (value, returned_root) = ret_area.assume_init().into_inner();
86        SmtGetResponse {
87            value: value.reverse(),
88            root: returned_root.reverse(),
89        }
90    }
91}
92
93/// Inserts `value` at `key` in the sparse Merkle tree rooted at `root`, returning the prior value
94/// stored at `key` along with the new root. The returned [`SmtSetResponse`] contains
95/// the previous value stored under `key` and the updated root.
96/// Fails if the tree with the specified `root` does not exist in the VM's advice provider.
97#[inline]
98pub fn smt_set(value: Word, key: Word, root: Word) -> SmtSetResponse {
99    unsafe {
100        let mut ret_area = ::core::mem::MaybeUninit::<WordAligned<(Word, Word)>>::uninit();
101        let ptr = ret_area.as_mut_ptr() as *mut (Word, Word);
102        extern_smt_set(
103            value[3], value[2], value[1], value[0], key[3], key[2], key[1], key[0], root[3],
104            root[2], root[1], root[0], ptr,
105        );
106        let (old_value, new_root) = ret_area.assume_init().into_inner();
107        SmtSetResponse {
108            old_value: old_value.reverse(),
109            new_root: new_root.reverse(),
110        }
111    }
112}
miden_stdlib_sys/stdlib/collections/smt.rs

miden_stdlib_sys/stdlib/collections/
smt.rs
