miden_objects/account/delta/
storage.rs

1use alloc::collections::BTreeMap;
2use alloc::collections::btree_map::Entry;
3use alloc::string::ToString;
4use alloc::vec::Vec;
5
6use super::{
7    AccountDeltaError,
8    ByteReader,
9    ByteWriter,
10    Deserializable,
11    DeserializationError,
12    Serializable,
13    Word,
14};
15use crate::account::{StorageMap, StorageSlotType};
16use crate::{EMPTY_WORD, Felt, LexicographicWord, ZERO};
17
18// ACCOUNT STORAGE DELTA
19// ================================================================================================
20
21/// [AccountStorageDelta] stores the differences between two states of account storage.
22///
23/// The delta consists of two maps:
24/// - A map containing the updates to value storage slots. The keys in this map are indexes of the
25///   updated storage slots and the values are the new values for these slots.
26/// - A map containing updates to storage maps. The keys in this map are indexes of the updated
27///   storage slots and the values are corresponding storage map delta objects.
28#[derive(Clone, Debug, PartialEq, Eq)]
29pub struct AccountStorageDelta {
30    /// The updates to the value slots of the account.
31    values: BTreeMap<u8, Word>,
32    /// The updates to the map slots of the account.
33    maps: BTreeMap<u8, StorageMapDelta>,
34}
35
36impl AccountStorageDelta {
37    /// Creates a new, empty storage delta.
38    pub fn new() -> Self {
39        Self {
40            values: BTreeMap::new(),
41            maps: BTreeMap::new(),
42        }
43    }
44
45    /// Creates a new storage delta from the provided fields.
46    ///
47    /// # Errors
48    ///
49    /// Returns an error if:
50    /// - Any of the updated slot is referenced from both maps, which means a slot is treated as
51    ///   both a value and a map slot.
52    pub fn from_parts(
53        values: BTreeMap<u8, Word>,
54        maps: BTreeMap<u8, StorageMapDelta>,
55    ) -> Result<Self, AccountDeltaError> {
56        let delta = Self { values, maps };
57        delta.validate()?;
58
59        Ok(delta)
60    }
61
62    /// Returns the slot type of the provided slot index or `None` if no such slot exists.
63    pub(crate) fn slot_type(&self, slot_index: u8) -> Option<StorageSlotType> {
64        if self.values().contains_key(&slot_index) {
65            Some(StorageSlotType::Value)
66        } else if self.maps().contains_key(&slot_index) {
67            Some(StorageSlotType::Map)
68        } else {
69            None
70        }
71    }
72
73    /// Returns a reference to the updated values in this storage delta.
74    pub fn values(&self) -> &BTreeMap<u8, Word> {
75        &self.values
76    }
77
78    /// Returns a reference to the updated maps in this storage delta.
79    pub fn maps(&self) -> &BTreeMap<u8, StorageMapDelta> {
80        &self.maps
81    }
82
83    /// Returns true if storage delta contains no updates.
84    pub fn is_empty(&self) -> bool {
85        self.values.is_empty() && self.maps.is_empty()
86    }
87
88    /// Tracks a slot change
89    pub fn set_item(&mut self, slot_index: u8, new_slot_value: Word) {
90        self.values.insert(slot_index, new_slot_value);
91    }
92
93    /// Tracks a map item change
94    pub fn set_map_item(&mut self, slot_index: u8, key: Word, new_value: Word) {
95        self.maps.entry(slot_index).or_default().insert(key, new_value);
96    }
97
98    /// Inserts an empty storage map delta for the provided slot index.
99    ///
100    /// This is useful for full state deltas to represent an empty map in the delta.
101    pub fn insert_empty_map_delta(&mut self, slot_index: u8) {
102        self.maps.entry(slot_index).or_default();
103    }
104
105    /// Merges another delta into this one, overwriting any existing values.
106    pub fn merge(&mut self, other: Self) -> Result<(), AccountDeltaError> {
107        self.values.extend(other.values);
108
109        // merge maps
110        for (slot, update) in other.maps.into_iter() {
111            match self.maps.entry(slot) {
112                Entry::Vacant(entry) => {
113                    entry.insert(update);
114                },
115                Entry::Occupied(mut entry) => entry.get_mut().merge(update),
116            }
117        }
118
119        self.validate()
120    }
121
122    /// Checks whether this storage delta is valid.
123    ///
124    /// # Errors
125    ///
126    /// Returns an error if:
127    /// - Any of the updated slot is referenced from both maps, which means a slot is treated as
128    ///   both a value and a map slot.
129    fn validate(&self) -> Result<(), AccountDeltaError> {
130        for slot in self.maps.keys() {
131            if self.values.contains_key(slot) {
132                return Err(AccountDeltaError::StorageSlotUsedAsDifferentTypes(*slot));
133            }
134        }
135
136        Ok(())
137    }
138
139    /// Returns an iterator of all the cleared storage slots.
140    fn cleared_slots(&self) -> impl Iterator<Item = u8> + '_ {
141        self.values.iter().filter(|&(_, value)| value.is_empty()).map(|(slot, _)| *slot)
142    }
143
144    /// Returns an iterator of all the updated storage slots.
145    fn updated_slots(&self) -> impl Iterator<Item = (&u8, &Word)> + '_ {
146        self.values.iter().filter(|&(_, value)| !value.is_empty())
147    }
148
149    /// Appends the storage slots delta to the given `elements` from which the delta commitment will
150    /// be computed.
151    pub(super) fn append_delta_elements(&self, elements: &mut Vec<Felt>) {
152        const DOMAIN_VALUE: Felt = Felt::new(2);
153        const DOMAIN_MAP: Felt = Felt::new(3);
154
155        let highest_value_slot_idx = self.values.last_key_value().map(|(slot_idx, _)| slot_idx);
156        let highest_map_slot_idx = self.maps.last_key_value().map(|(slot_idx, _)| slot_idx);
157        let highest_slot_idx =
158            highest_value_slot_idx.max(highest_map_slot_idx).copied().unwrap_or(0);
159
160        for slot_idx in 0..=highest_slot_idx {
161            let slot_idx_felt = Felt::from(slot_idx);
162
163            // The storage delta ensures that the value slots and map slots do not have overlapping
164            // slot indices, so at most one of them will return `Some` for a given slot index.
165            match self.values.get(&slot_idx) {
166                Some(new_value) => {
167                    elements.extend_from_slice(&[DOMAIN_VALUE, slot_idx_felt, ZERO, ZERO]);
168                    elements.extend_from_slice(new_value.as_elements());
169                },
170                None => {
171                    if let Some(map_delta) = self.maps().get(&slot_idx) {
172                        for (key, value) in map_delta.entries() {
173                            elements.extend_from_slice(key.inner().as_elements());
174                            elements.extend_from_slice(value.as_elements());
175                        }
176
177                        let num_changed_entries = Felt::try_from(map_delta.num_entries()).expect(
178                            "number of changed entries should not exceed max representable felt",
179                        );
180
181                        elements.extend_from_slice(&[
182                            DOMAIN_MAP,
183                            slot_idx_felt,
184                            num_changed_entries,
185                            ZERO,
186                        ]);
187                        elements.extend_from_slice(EMPTY_WORD.as_elements());
188                    }
189                },
190            }
191        }
192    }
193
194    /// Consumes self and returns the underlying parts of the storage delta.
195    pub fn into_parts(self) -> (BTreeMap<u8, Word>, BTreeMap<u8, StorageMapDelta>) {
196        (self.values, self.maps)
197    }
198}
199
200impl Default for AccountStorageDelta {
201    fn default() -> Self {
202        Self::new()
203    }
204}
205
206#[cfg(any(feature = "testing", test))]
207impl AccountStorageDelta {
208    /// Creates an [AccountStorageDelta] from the given iterators.
209    pub fn from_iters(
210        cleared_values: impl IntoIterator<Item = u8>,
211        updated_values: impl IntoIterator<Item = (u8, Word)>,
212        updated_maps: impl IntoIterator<Item = (u8, StorageMapDelta)>,
213    ) -> Self {
214        Self {
215            values: BTreeMap::from_iter(
216                cleared_values.into_iter().map(|key| (key, EMPTY_WORD)).chain(updated_values),
217            ),
218            maps: BTreeMap::from_iter(updated_maps),
219        }
220    }
221}
222
223impl Serializable for AccountStorageDelta {
224    fn write_into<W: ByteWriter>(&self, target: &mut W) {
225        let cleared: Vec<u8> = self.cleared_slots().collect();
226        let updated: Vec<(&u8, &Word)> = self.updated_slots().collect();
227
228        target.write_u8(cleared.len() as u8);
229        target.write_many(cleared.iter());
230
231        target.write_u8(updated.len() as u8);
232        target.write_many(updated.iter());
233
234        target.write_u8(self.maps.len() as u8);
235        target.write_many(self.maps.iter());
236    }
237
238    fn get_size_hint(&self) -> usize {
239        let u8_size = 0u8.get_size_hint();
240        let word_size = EMPTY_WORD.get_size_hint();
241
242        let mut storage_map_delta_size = 0;
243        for (slot, storage_map_delta) in self.maps.iter() {
244            // The serialized size of each entry is the combination of slot (key) and the delta
245            // (value).
246            storage_map_delta_size += slot.get_size_hint() + storage_map_delta.get_size_hint();
247        }
248
249        // Length Prefixes
250        u8_size * 3 +
251        // Cleared Slots
252        self.cleared_slots().count() * u8_size +
253        // Updated Slots
254        self.updated_slots().count() * (u8_size + word_size) +
255        // Storage Map Delta
256        storage_map_delta_size
257    }
258}
259
260impl Deserializable for AccountStorageDelta {
261    fn read_from<R: ByteReader>(source: &mut R) -> Result<Self, DeserializationError> {
262        let mut values = BTreeMap::new();
263
264        let num_cleared_items = source.read_u8()? as usize;
265        for _ in 0..num_cleared_items {
266            let cleared_slot = source.read_u8()?;
267            values.insert(cleared_slot, EMPTY_WORD);
268        }
269
270        let num_updated_items = source.read_u8()? as usize;
271        for _ in 0..num_updated_items {
272            let (updated_slot, updated_value) = source.read()?;
273            values.insert(updated_slot, updated_value);
274        }
275
276        let num_maps = source.read_u8()? as usize;
277        let maps = source.read_many::<(u8, StorageMapDelta)>(num_maps)?.into_iter().collect();
278
279        Self::from_parts(values, maps)
280            .map_err(|err| DeserializationError::InvalidValue(err.to_string()))
281    }
282}
283
284// STORAGE MAP DELTA
285// ================================================================================================
286
287/// [StorageMapDelta] stores the differences between two states of account storage maps.
288///
289/// The differences are represented as leaf updates: a map of updated item key ([Word]) to
290/// value ([Word]). For cleared items the value is [EMPTY_WORD].
291///
292/// The [`LexicographicWord`] wrapper is necessary to order the keys in the same way as the
293/// in-kernel account delta which uses a link map.
294#[derive(Clone, Debug, Default, PartialEq, Eq)]
295pub struct StorageMapDelta(BTreeMap<LexicographicWord, Word>);
296
297impl StorageMapDelta {
298    /// Creates a new storage map delta from the provided leaves.
299    pub fn new(map: BTreeMap<LexicographicWord, Word>) -> Self {
300        Self(map)
301    }
302
303    /// Returns the number of changed entries in this map delta.
304    pub fn num_entries(&self) -> usize {
305        self.0.len()
306    }
307
308    /// Returns a reference to the updated entries in this storage map delta.
309    ///
310    /// Note that the returned key is the raw map key.
311    pub fn entries(&self) -> &BTreeMap<LexicographicWord, Word> {
312        &self.0
313    }
314
315    /// Inserts an item into the storage map delta.
316    pub fn insert(&mut self, raw_key: Word, value: Word) {
317        self.0.insert(LexicographicWord::new(raw_key), value);
318    }
319
320    /// Returns true if storage map delta contains no updates.
321    pub fn is_empty(&self) -> bool {
322        self.0.is_empty()
323    }
324
325    /// Merge `other` into this delta, giving precedence to `other`.
326    pub fn merge(&mut self, other: Self) {
327        // Aggregate the changes into a map such that `other` overwrites self.
328        self.0.extend(other.0);
329    }
330
331    /// Returns a mutable reference to the underlying map.
332    pub fn as_map_mut(&mut self) -> &mut BTreeMap<LexicographicWord, Word> {
333        &mut self.0
334    }
335
336    /// Returns an iterator of all the cleared keys in the storage map.
337    fn cleared_keys(&self) -> impl Iterator<Item = &Word> + '_ {
338        self.0.iter().filter(|&(_, value)| value.is_empty()).map(|(key, _)| key.inner())
339    }
340
341    /// Returns an iterator of all the updated entries in the storage map.
342    fn updated_entries(&self) -> impl Iterator<Item = (&Word, &Word)> + '_ {
343        self.0.iter().filter_map(|(key, value)| {
344            if !value.is_empty() {
345                Some((key.inner(), value))
346            } else {
347                None
348            }
349        })
350    }
351}
352
353#[cfg(any(feature = "testing", test))]
354impl StorageMapDelta {
355    /// Creates a new [StorageMapDelta] from the provided iterators.
356    pub fn from_iters(
357        cleared_leaves: impl IntoIterator<Item = Word>,
358        updated_leaves: impl IntoIterator<Item = (Word, Word)>,
359    ) -> Self {
360        Self(BTreeMap::from_iter(
361            cleared_leaves
362                .into_iter()
363                .map(|key| (LexicographicWord::new(key), EMPTY_WORD))
364                .chain(
365                    updated_leaves
366                        .into_iter()
367                        .map(|(key, value)| (LexicographicWord::new(key), value)),
368                ),
369        ))
370    }
371
372    /// Consumes self and returns the underlying map.
373    pub fn into_map(self) -> BTreeMap<LexicographicWord, Word> {
374        self.0
375    }
376}
377
378/// Converts a [StorageMap] into a [StorageMapDelta] for initial delta construction.
379impl From<StorageMap> for StorageMapDelta {
380    fn from(map: StorageMap) -> Self {
381        StorageMapDelta::new(
382            map.into_entries()
383                .into_iter()
384                .map(|(key, value)| (LexicographicWord::new(key), value))
385                .collect(),
386        )
387    }
388}
389
390impl Serializable for StorageMapDelta {
391    fn write_into<W: ByteWriter>(&self, target: &mut W) {
392        let cleared: Vec<&Word> = self.cleared_keys().collect();
393        let updated: Vec<(&Word, &Word)> = self.updated_entries().collect();
394
395        target.write_usize(cleared.len());
396        target.write_many(cleared.iter());
397
398        target.write_usize(updated.len());
399        target.write_many(updated.iter());
400    }
401
402    fn get_size_hint(&self) -> usize {
403        let word_size = EMPTY_WORD.get_size_hint();
404
405        let cleared_keys_count = self.cleared_keys().count();
406        let updated_entries_count = self.updated_entries().count();
407
408        // Cleared Keys
409        cleared_keys_count.get_size_hint() +
410        cleared_keys_count * Word::SERIALIZED_SIZE +
411
412        // Updated Entries
413        updated_entries_count.get_size_hint() +
414        updated_entries_count * (Word::SERIALIZED_SIZE + word_size)
415    }
416}
417
418impl Deserializable for StorageMapDelta {
419    fn read_from<R: ByteReader>(source: &mut R) -> Result<Self, DeserializationError> {
420        let mut map = BTreeMap::new();
421
422        let cleared_count = source.read_usize()?;
423        for _ in 0..cleared_count {
424            let cleared_key = source.read()?;
425            map.insert(LexicographicWord::new(cleared_key), EMPTY_WORD);
426        }
427
428        let updated_count = source.read_usize()?;
429        for _ in 0..updated_count {
430            let (updated_key, updated_value) = source.read()?;
431            map.insert(LexicographicWord::new(updated_key), updated_value);
432        }
433
434        Ok(Self::new(map))
435    }
436}
437
438// TESTS
439// ================================================================================================
440
441#[cfg(test)]
442mod tests {
443    use anyhow::Context;
444
445    use super::{AccountStorageDelta, Deserializable, Serializable};
446    use crate::account::StorageMapDelta;
447    use crate::testing::storage::AccountStorageDeltaBuilder;
448    use crate::{ONE, Word, ZERO};
449
450    #[test]
451    fn account_storage_delta_validation() {
452        let delta = AccountStorageDelta::from_iters(
453            [1, 2, 3],
454            [(4, Word::from([ONE, ONE, ONE, ONE])), (5, Word::from([ONE, ONE, ONE, ZERO]))],
455            [],
456        );
457        assert!(delta.validate().is_ok());
458
459        let bytes = delta.to_bytes();
460        assert_eq!(AccountStorageDelta::read_from_bytes(&bytes), Ok(delta));
461
462        // duplicate across cleared items and maps
463        let delta = AccountStorageDelta::from_iters(
464            [1, 2, 3],
465            [(2, Word::from([ONE, ONE, ONE, ONE])), (5, Word::from([ONE, ONE, ONE, ZERO]))],
466            [(1, StorageMapDelta::default())],
467        );
468        assert!(delta.validate().is_err());
469
470        let bytes = delta.to_bytes();
471        assert!(AccountStorageDelta::read_from_bytes(&bytes).is_err());
472
473        // duplicate across updated items and maps
474        let delta = AccountStorageDelta::from_iters(
475            [1, 3],
476            [(2, Word::from([ONE, ONE, ONE, ONE])), (5, Word::from([ONE, ONE, ONE, ZERO]))],
477            [(2, StorageMapDelta::default())],
478        );
479        assert!(delta.validate().is_err());
480
481        let bytes = delta.to_bytes();
482        assert!(AccountStorageDelta::read_from_bytes(&bytes).is_err());
483    }
484
485    #[test]
486    fn test_is_empty() {
487        let storage_delta = AccountStorageDelta::new();
488        assert!(storage_delta.is_empty());
489
490        let storage_delta = AccountStorageDelta::from_iters([1], [], []);
491        assert!(!storage_delta.is_empty());
492
493        let storage_delta =
494            AccountStorageDelta::from_iters([], [(2, Word::from([ONE, ONE, ONE, ONE]))], []);
495        assert!(!storage_delta.is_empty());
496
497        let storage_delta =
498            AccountStorageDelta::from_iters([], [], [(3, StorageMapDelta::default())]);
499        assert!(!storage_delta.is_empty());
500    }
501
502    #[test]
503    fn test_serde_account_storage_delta() {
504        let storage_delta = AccountStorageDelta::new();
505        let serialized = storage_delta.to_bytes();
506        let deserialized = AccountStorageDelta::read_from_bytes(&serialized).unwrap();
507        assert_eq!(deserialized, storage_delta);
508
509        let storage_delta = AccountStorageDelta::from_iters([1], [], []);
510        let serialized = storage_delta.to_bytes();
511        let deserialized = AccountStorageDelta::read_from_bytes(&serialized).unwrap();
512        assert_eq!(deserialized, storage_delta);
513
514        let storage_delta =
515            AccountStorageDelta::from_iters([], [(2, Word::from([ONE, ONE, ONE, ONE]))], []);
516        let serialized = storage_delta.to_bytes();
517        let deserialized = AccountStorageDelta::read_from_bytes(&serialized).unwrap();
518        assert_eq!(deserialized, storage_delta);
519
520        let storage_delta =
521            AccountStorageDelta::from_iters([], [], [(3, StorageMapDelta::default())]);
522        let serialized = storage_delta.to_bytes();
523        let deserialized = AccountStorageDelta::read_from_bytes(&serialized).unwrap();
524        assert_eq!(deserialized, storage_delta);
525    }
526
527    #[test]
528    fn test_serde_storage_map_delta() {
529        let storage_map_delta = StorageMapDelta::default();
530        let serialized = storage_map_delta.to_bytes();
531        let deserialized = StorageMapDelta::read_from_bytes(&serialized).unwrap();
532        assert_eq!(deserialized, storage_map_delta);
533
534        let storage_map_delta = StorageMapDelta::from_iters([Word::from([ONE, ONE, ONE, ONE])], []);
535        let serialized = storage_map_delta.to_bytes();
536        let deserialized = StorageMapDelta::read_from_bytes(&serialized).unwrap();
537        assert_eq!(deserialized, storage_map_delta);
538
539        let storage_map_delta =
540            StorageMapDelta::from_iters([], [(Word::empty(), Word::from([ONE, ONE, ONE, ONE]))]);
541        let serialized = storage_map_delta.to_bytes();
542        let deserialized = StorageMapDelta::read_from_bytes(&serialized).unwrap();
543        assert_eq!(deserialized, storage_map_delta);
544    }
545
546    #[rstest::rstest]
547    #[case::some_some(Some(1), Some(2), Some(2))]
548    #[case::none_some(None, Some(2), Some(2))]
549    #[case::some_none(Some(1), None, None)]
550    #[test]
551    fn merge_items(
552        #[case] x: Option<u32>,
553        #[case] y: Option<u32>,
554        #[case] expected: Option<u32>,
555    ) -> anyhow::Result<()> {
556        /// Creates a delta containing the item as an update if Some, else with the item cleared.
557        fn create_delta(item: Option<u32>) -> anyhow::Result<AccountStorageDelta> {
558            const SLOT: u8 = 123;
559            let item = item.map(|x| (SLOT, Word::from([x, 0, 0, 0])));
560
561            AccountStorageDeltaBuilder::new()
562                .add_cleared_items(item.is_none().then_some(SLOT))
563                .add_updated_values(item)
564                .build()
565                .context("failed to build storage delta")
566        }
567
568        let mut delta_x = create_delta(x)?;
569        let delta_y = create_delta(y)?;
570        let expected = create_delta(expected)?;
571
572        delta_x.merge(delta_y).context("failed to merge deltas")?;
573
574        assert_eq!(delta_x, expected);
575
576        Ok(())
577    }
578
579    #[rstest::rstest]
580    #[case::some_some(Some(1), Some(2), Some(2))]
581    #[case::none_some(None, Some(2), Some(2))]
582    #[case::some_none(Some(1), None, None)]
583    #[test]
584    fn merge_maps(#[case] x: Option<u32>, #[case] y: Option<u32>, #[case] expected: Option<u32>) {
585        fn create_delta(value: Option<u32>) -> StorageMapDelta {
586            let key = Word::from([10u32, 0, 0, 0]);
587            match value {
588                Some(value) => {
589                    StorageMapDelta::from_iters([], [(key, Word::from([value, 0, 0, 0]))])
590                },
591                None => StorageMapDelta::from_iters([key], []),
592            }
593        }
594
595        let mut delta_x = create_delta(x);
596        let delta_y = create_delta(y);
597        let expected = create_delta(expected);
598
599        delta_x.merge(delta_y);
600
601        assert_eq!(delta_x, expected);
602    }
603}
miden_objects/account/delta/storage.rs

miden_objects/account/delta/
storage.rs
