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

miden_objects/account/delta/
storage.rs
