miden_objects/account/delta/
storage.rs

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

miden_objects/account/delta/
storage.rs
