miden_objects/account/storage/
map.rs

1use miden_crypto::merkle::EmptySubtreeRoots;
2
3use super::{
4    ByteReader, ByteWriter, Deserializable, DeserializationError, Digest, Serializable, Word,
5};
6use crate::{
7    account::StorageMapDelta,
8    crypto::{
9        hash::rpo::RpoDigest,
10        merkle::{InnerNodeInfo, LeafIndex, Smt, SmtLeaf, SmtProof, SMT_DEPTH},
11    },
12};
13
14// ACCOUNT STORAGE MAP
15// ================================================================================================
16
17/// Empty storage map root.
18pub const EMPTY_STORAGE_MAP_ROOT: Digest =
19    *EmptySubtreeRoots::entry(StorageMap::STORAGE_MAP_TREE_DEPTH, 0);
20
21/// Account storage map is a Sparse Merkle Tree of depth 64. It can be used to store more data as
22/// there is in plain usage of the storage slots. The root of the SMT consumes one account storage
23/// slot.
24#[derive(Debug, Clone, PartialEq, Eq)]
25pub struct StorageMap {
26    map: Smt,
27}
28
29impl StorageMap {
30    // CONSTANTS
31    // --------------------------------------------------------------------------------------------
32
33    /// Depth of the storage tree.
34    pub const STORAGE_MAP_TREE_DEPTH: u8 = SMT_DEPTH;
35
36    /// The default value of empty leaves.
37    pub const EMPTY_VALUE: Word = Smt::EMPTY_VALUE;
38
39    // CONSTRUCTOR
40    // --------------------------------------------------------------------------------------------
41
42    /// Returns a new [StorageMap].
43    ///
44    /// All leaves in the returned tree are set to [Self::EMPTY_VALUE].
45    pub fn new() -> Self {
46        StorageMap { map: Smt::new() }
47    }
48
49    pub fn with_entries(entries: impl IntoIterator<Item = (RpoDigest, Word)>) -> Self {
50        let mut storage_map = Smt::new();
51
52        for (key, value) in entries {
53            storage_map.insert(key, value);
54        }
55
56        StorageMap { map: storage_map }
57    }
58
59    // PUBLIC ACCESSORS
60    // --------------------------------------------------------------------------------------------
61
62    pub const fn depth(&self) -> u8 {
63        SMT_DEPTH
64    }
65
66    pub fn root(&self) -> RpoDigest {
67        self.map.root() // Delegate to Smt's root method
68    }
69
70    pub fn get_leaf(&self, key: &RpoDigest) -> SmtLeaf {
71        self.map.get_leaf(key) // Delegate to Smt's get_leaf method
72    }
73
74    pub fn get_value(&self, key: &RpoDigest) -> Word {
75        self.map.get_value(key) // Delegate to Smt's get_value method
76    }
77
78    pub fn open(&self, key: &RpoDigest) -> SmtProof {
79        self.map.open(key) // Delegate to Smt's open method
80    }
81
82    // ITERATORS
83    // --------------------------------------------------------------------------------------------
84    pub fn leaves(&self) -> impl Iterator<Item = (LeafIndex<SMT_DEPTH>, &SmtLeaf)> {
85        self.map.leaves() // Delegate to Smt's leaves method
86    }
87
88    pub fn entries(&self) -> impl Iterator<Item = &(RpoDigest, Word)> {
89        self.map.entries() // Delegate to Smt's entries method
90    }
91
92    pub fn inner_nodes(&self) -> impl Iterator<Item = InnerNodeInfo> + '_ {
93        self.map.inner_nodes() // Delegate to Smt's inner_nodes method
94    }
95
96    // DATA MUTATORS
97    // --------------------------------------------------------------------------------------------
98    pub fn insert(&mut self, key: RpoDigest, value: Word) -> Word {
99        self.map.insert(key, value) // Delegate to Smt's insert method
100    }
101
102    /// Applies the provided delta to this account storage.
103    pub fn apply_delta(&mut self, delta: &StorageMapDelta) -> Digest {
104        // apply the updated and cleared leaves to the storage map
105        for (&key, &value) in delta.leaves().iter() {
106            self.insert(key, value);
107        }
108
109        self.root()
110    }
111}
112
113impl Default for StorageMap {
114    fn default() -> Self {
115        Self::new()
116    }
117}
118
119// SERIALIZATION
120// ================================================================================================
121
122impl Serializable for StorageMap {
123    fn write_into<W: ByteWriter>(&self, target: &mut W) {
124        self.map.write_into(target)
125    }
126
127    fn get_size_hint(&self) -> usize {
128        self.map.get_size_hint()
129    }
130}
131
132impl Deserializable for StorageMap {
133    fn read_from<R: ByteReader>(source: &mut R) -> Result<Self, DeserializationError> {
134        let smt = Smt::read_from(source)?;
135        Ok(StorageMap { map: smt })
136    }
137}
138
139#[cfg(test)]
140mod tests {
141    use miden_crypto::{hash::rpo::RpoDigest, Felt};
142
143    use super::{Deserializable, Serializable, StorageMap, Word, EMPTY_STORAGE_MAP_ROOT};
144
145    #[test]
146    fn account_storage_serialization() {
147        // StorageMap for default types (empty map)
148        let storage_map_default = StorageMap::default();
149        let bytes = storage_map_default.to_bytes();
150        assert_eq!(storage_map_default, StorageMap::read_from_bytes(&bytes).unwrap());
151
152        // StorageMap with values
153        let storage_map_leaves_2: [(RpoDigest, Word); 2] = [
154            (
155                RpoDigest::new([Felt::new(101), Felt::new(102), Felt::new(103), Felt::new(104)]),
156                [Felt::new(1_u64), Felt::new(2_u64), Felt::new(3_u64), Felt::new(4_u64)],
157            ),
158            (
159                RpoDigest::new([Felt::new(105), Felt::new(106), Felt::new(107), Felt::new(108)]),
160                [Felt::new(5_u64), Felt::new(6_u64), Felt::new(7_u64), Felt::new(8_u64)],
161            ),
162        ];
163        let storage_map = StorageMap::with_entries(storage_map_leaves_2);
164
165        let bytes = storage_map.to_bytes();
166        assert_eq!(storage_map, StorageMap::read_from_bytes(&bytes).unwrap());
167    }
168
169    #[test]
170    fn test_empty_storage_map_constants() {
171        // If these values don't match, update the constants.
172        assert_eq!(StorageMap::default().root(), EMPTY_STORAGE_MAP_ROOT);
173    }
174}
miden_objects/account/storage/map.rs

miden_objects/account/storage/
map.rs
