miden_protocol/account/storage/
header.rs

1use alloc::collections::BTreeMap;
2use alloc::format;
3use alloc::string::ToString;
4use alloc::vec::Vec;
5
6use super::map::EMPTY_STORAGE_MAP_ROOT;
7use super::{AccountStorage, Felt, StorageSlotType, Word};
8use crate::ZERO;
9use crate::account::{StorageSlot, StorageSlotId, StorageSlotName};
10use crate::crypto::SequentialCommit;
11use crate::errors::AccountError;
12use crate::utils::serde::{
13    ByteReader,
14    ByteWriter,
15    Deserializable,
16    DeserializationError,
17    Serializable,
18};
19
20// ACCOUNT STORAGE HEADER
21// ================================================================================================
22
23/// The header of an [`AccountStorage`], storing only the slot name, slot type and value of each
24/// storage slot.
25///
26/// The stored value differs based on the slot type:
27/// - [`StorageSlotType::Value`]: The value of the slot itself.
28/// - [`StorageSlotType::Map`]: The root of the SMT that represents the storage map.
29#[derive(Debug, Clone, PartialEq, Eq)]
30pub struct AccountStorageHeader {
31    slots: Vec<StorageSlotHeader>,
32}
33
34impl AccountStorageHeader {
35    // CONSTRUCTOR
36    // --------------------------------------------------------------------------------------------
37
38    /// Returns a new instance of account storage header initialized with the provided slots.
39    ///
40    /// # Errors
41    ///
42    /// Returns an error if:
43    /// - The number of provided slots is greater than [`AccountStorage::MAX_NUM_STORAGE_SLOTS`].
44    /// - The slots are not sorted by [`StorageSlotId`].
45    /// - There are multiple storage slots with the same [`StorageSlotName`].
46    pub fn new(slots: Vec<StorageSlotHeader>) -> Result<Self, AccountError> {
47        if slots.len() > AccountStorage::MAX_NUM_STORAGE_SLOTS {
48            return Err(AccountError::StorageTooManySlots(slots.len() as u64));
49        }
50
51        if !slots.is_sorted_by_key(|slot| slot.id()) {
52            return Err(AccountError::UnsortedStorageSlots);
53        }
54
55        // Check for slot name uniqueness by checking each neighboring slot's IDs. This is
56        // sufficient because the slots are sorted.
57        for slots in slots.windows(2) {
58            if slots[0].id() == slots[1].id() {
59                return Err(AccountError::DuplicateStorageSlotName(slots[0].name().clone()));
60            }
61        }
62
63        Ok(Self { slots })
64    }
65
66    /// Returns a new instance of account storage header initialized with the provided slot tuples.
67    ///
68    /// This is a convenience method that converts tuples to [`StorageSlotHeader`]s.
69    ///
70    /// # Errors
71    ///
72    /// Returns an error if:
73    /// - The number of provided slots is greater than [`AccountStorage::MAX_NUM_STORAGE_SLOTS`].
74    /// - The slots are not sorted by [`StorageSlotId`].
75    #[cfg(any(feature = "testing", test))]
76    pub fn from_tuples(
77        slots: Vec<(StorageSlotName, StorageSlotType, Word)>,
78    ) -> Result<Self, AccountError> {
79        let slots = slots
80            .into_iter()
81            .map(|(name, slot_type, value)| StorageSlotHeader::new(name, slot_type, value))
82            .collect();
83
84        Self::new(slots)
85    }
86
87    // PUBLIC ACCESSORS
88    // --------------------------------------------------------------------------------------------
89
90    /// Returns an iterator over the storage header slots.
91    pub fn slots(&self) -> impl Iterator<Item = &StorageSlotHeader> {
92        self.slots.iter()
93    }
94
95    /// Returns an iterator over the storage header map slots.
96    pub fn map_slot_roots(&self) -> impl Iterator<Item = Word> + '_ {
97        self.slots.iter().filter_map(|slot| match slot.slot_type() {
98            StorageSlotType::Value => None,
99            StorageSlotType::Map => Some(slot.value()),
100        })
101    }
102
103    /// Returns the number of slots contained in the storage header.
104    pub fn num_slots(&self) -> u8 {
105        // SAFETY: The constructors of this type ensure this value fits in a u8.
106        self.slots.len() as u8
107    }
108
109    /// Returns the storage slot header for the slot with the given name.
110    ///
111    /// Returns `None` if a slot with the provided name does not exist.
112    pub fn find_slot_header_by_name(
113        &self,
114        slot_name: &StorageSlotName,
115    ) -> Option<&StorageSlotHeader> {
116        self.find_slot_header_by_id(slot_name.id())
117    }
118
119    /// Returns the storage slot header for the slot with the given ID.
120    ///
121    /// Returns `None` if a slot with the provided slot ID does not exist.
122    pub fn find_slot_header_by_id(&self, slot_id: StorageSlotId) -> Option<&StorageSlotHeader> {
123        self.slots.iter().find(|slot| slot.id() == slot_id)
124    }
125
126    /// Indicates whether the slot with the given `name` is a map slot.
127    ///
128    /// # Errors
129    ///
130    /// Returns an error if:
131    /// - a slot with the provided name does not exist.
132    pub fn is_map_slot(&self, name: &StorageSlotName) -> Result<bool, AccountError> {
133        match self
134            .find_slot_header_by_name(name)
135            .ok_or(AccountError::StorageSlotNameNotFound { slot_name: name.clone() })?
136            .slot_type()
137        {
138            StorageSlotType::Map => Ok(true),
139            StorageSlotType::Value => Ok(false),
140        }
141    }
142
143    /// Converts storage slots of this account storage header into a vector of field elements.
144    ///
145    /// This is done by first converting each storage slot into exactly 8 elements as follows:
146    ///
147    /// ```text
148    /// [[0, slot_type, slot_id_suffix, slot_id_prefix], SLOT_VALUE]
149    /// ```
150    ///
151    /// And then concatenating the resulting elements into a single vector.
152    pub fn to_elements(&self) -> Vec<Felt> {
153        <Self as SequentialCommit>::to_elements(self)
154    }
155
156    /// Reconstructs an [`AccountStorageHeader`] from field elements with provided slot names.
157    ///
158    /// The elements are expected to be groups of 8 elements per slot:
159    /// `[[0, slot_type, slot_id_suffix, slot_id_prefix], SLOT_VALUE]`
160    pub fn try_from_elements(
161        elements: &[Felt],
162        slot_names: &BTreeMap<StorageSlotId, StorageSlotName>,
163    ) -> Result<Self, AccountError> {
164        if !elements.len().is_multiple_of(StorageSlot::NUM_ELEMENTS) {
165            return Err(AccountError::other(
166                "storage header elements length must be divisible by 8",
167            ));
168        }
169
170        let mut slots = Vec::new();
171        for chunk in elements.chunks_exact(StorageSlot::NUM_ELEMENTS) {
172            // Parse slot type from second element.
173            let slot_type_felt = chunk[1];
174            let slot_type = slot_type_felt.try_into()?;
175
176            // Parse slot ID from third and fourth elements.
177            let slot_id_suffix = chunk[2];
178            let slot_id_prefix = chunk[3];
179            let parsed_slot_id = StorageSlotId::new(slot_id_suffix, slot_id_prefix);
180
181            // Retrieve slot name from the map.
182            let slot_name = slot_names.get(&parsed_slot_id).cloned().ok_or(AccountError::other(
183                format!("slot name not found for slot ID {}", parsed_slot_id),
184            ))?;
185
186            // Parse slot value from last 4 elements.
187            let slot_value = Word::new([chunk[4], chunk[5], chunk[6], chunk[7]]);
188
189            let slot_header = StorageSlotHeader::new(slot_name, slot_type, slot_value);
190            slots.push(slot_header);
191        }
192
193        // Sort slots by ID.
194        slots.sort_by_key(|slot| slot.id());
195
196        Self::new(slots)
197    }
198
199    /// Returns the commitment to the [`AccountStorage`] this header represents.
200    pub fn to_commitment(&self) -> Word {
201        <Self as SequentialCommit>::to_commitment(self)
202    }
203}
204
205impl From<&AccountStorage> for AccountStorageHeader {
206    fn from(value: &AccountStorage) -> Self {
207        value.to_header()
208    }
209}
210
211// SEQUENTIAL COMMIT
212// ================================================================================================
213
214impl SequentialCommit for AccountStorageHeader {
215    type Commitment = Word;
216
217    fn to_elements(&self) -> Vec<Felt> {
218        self.slots().flat_map(|slot| slot.to_elements()).collect()
219    }
220}
221
222// SERIALIZATION
223// ================================================================================================
224
225impl Serializable for AccountStorageHeader {
226    fn write_into<W: ByteWriter>(&self, target: &mut W) {
227        let len = self.slots.len() as u8;
228        target.write_u8(len);
229        target.write_many(self.slots())
230    }
231}
232
233impl Deserializable for AccountStorageHeader {
234    fn read_from<R: ByteReader>(source: &mut R) -> Result<Self, DeserializationError> {
235        let len = source.read_u8()?;
236        let slots: Vec<StorageSlotHeader> =
237            source.read_many_iter(len as usize)?.collect::<Result<_, _>>()?;
238        Self::new(slots).map_err(|err| DeserializationError::InvalidValue(err.to_string()))
239    }
240}
241
242// STORAGE SLOT HEADER
243// ================================================================================================
244
245/// The header of a [`StorageSlot`], storing only the slot name (or ID), slot type and value of the
246/// slot.
247///
248/// The stored value differs based on the slot type:
249/// - [`StorageSlotType::Value`]: The value of the slot itself.
250/// - [`StorageSlotType::Map`]: The root of the SMT that represents the storage map.
251#[derive(Debug, Clone, PartialEq, Eq)]
252pub struct StorageSlotHeader {
253    name: StorageSlotName,
254    r#type: StorageSlotType,
255    value: Word,
256}
257
258impl StorageSlotHeader {
259    // CONSTRUCTORS
260    // --------------------------------------------------------------------------------------------
261
262    /// Returns a new instance of storage slot header.
263    pub fn new(name: StorageSlotName, r#type: StorageSlotType, value: Word) -> Self {
264        Self { name, r#type, value }
265    }
266
267    /// Returns a new instance of storage slot header with an empty value slot.
268    pub fn with_empty_value(name: StorageSlotName) -> StorageSlotHeader {
269        StorageSlotHeader::new(name, StorageSlotType::Value, Word::default())
270    }
271
272    /// Returns a new instance of storage slot header with an empty map slot.
273    pub fn with_empty_map(name: StorageSlotName) -> StorageSlotHeader {
274        StorageSlotHeader::new(name, StorageSlotType::Map, EMPTY_STORAGE_MAP_ROOT)
275    }
276
277    // ACCESSORS
278    // --------------------------------------------------------------------------------------------
279
280    /// Returns a reference to the slot name.
281    pub fn name(&self) -> &StorageSlotName {
282        &self.name
283    }
284
285    /// Returns the slot ID.
286    pub fn id(&self) -> StorageSlotId {
287        self.name.id()
288    }
289
290    /// Returns the slot type.
291    pub fn slot_type(&self) -> StorageSlotType {
292        self.r#type
293    }
294
295    /// Returns the slot value.
296    pub fn value(&self) -> Word {
297        self.value
298    }
299
300    /// Returns this storage slot header as field elements.
301    ///
302    /// This is done by converting this storage slot into 8 field elements as follows:
303    /// ```text
304    /// [[0, slot_type, slot_id_suffix, slot_id_prefix], SLOT_VALUE]
305    /// ```
306    pub(crate) fn to_elements(&self) -> [Felt; StorageSlot::NUM_ELEMENTS] {
307        let id = self.id();
308        let mut elements = [ZERO; StorageSlot::NUM_ELEMENTS];
309        elements[0..4].copy_from_slice(&[
310            Felt::ZERO,
311            self.r#type.as_felt(),
312            id.suffix(),
313            id.prefix(),
314        ]);
315        elements[4..8].copy_from_slice(self.value.as_elements());
316        elements
317    }
318}
319
320impl From<&StorageSlot> for StorageSlotHeader {
321    fn from(slot: &StorageSlot) -> Self {
322        StorageSlotHeader::new(slot.name().clone(), slot.slot_type(), slot.value())
323    }
324}
325
326// SERIALIZATION
327// ================================================================================================
328
329impl Serializable for StorageSlotHeader {
330    fn write_into<W: ByteWriter>(&self, target: &mut W) {
331        self.name.write_into(target);
332        self.r#type.write_into(target);
333        self.value.write_into(target);
334    }
335}
336
337impl Deserializable for StorageSlotHeader {
338    fn read_from<R: ByteReader>(source: &mut R) -> Result<Self, DeserializationError> {
339        let name = StorageSlotName::read_from(source)?;
340        let slot_type = StorageSlotType::read_from(source)?;
341        let value = Word::read_from(source)?;
342        Ok(Self::new(name, slot_type, value))
343    }
344}
345
346// TESTS
347// ================================================================================================
348
349#[cfg(test)]
350mod tests {
351    use alloc::collections::BTreeMap;
352    use alloc::string::ToString;
353
354    use miden_core::Felt;
355
356    use super::AccountStorageHeader;
357    use crate::Word;
358    use crate::account::{AccountStorage, StorageSlotHeader, StorageSlotName, StorageSlotType};
359    use crate::testing::storage::{MOCK_MAP_SLOT, MOCK_VALUE_SLOT0, MOCK_VALUE_SLOT1};
360    use crate::utils::serde::{Deserializable, Serializable};
361
362    #[test]
363    fn test_from_account_storage() {
364        let storage_map = AccountStorage::mock_map();
365
366        // create new storage header from AccountStorage
367        let mut slots = vec![
368            (MOCK_VALUE_SLOT0.clone(), StorageSlotType::Value, Word::from([1, 2, 3, 4u32])),
369            (
370                MOCK_VALUE_SLOT1.clone(),
371                StorageSlotType::Value,
372                Word::from([
373                    Felt::from(5_u32),
374                    Felt::from(6_u32),
375                    Felt::from(7_u32),
376                    Felt::from(8_u32),
377                ]),
378            ),
379            (MOCK_MAP_SLOT.clone(), StorageSlotType::Map, storage_map.root()),
380        ];
381        slots.sort_unstable_by_key(|(slot_name, ..)| slot_name.id());
382
383        let expected_header = AccountStorageHeader::from_tuples(slots).unwrap();
384        let account_storage = AccountStorage::mock();
385
386        assert_eq!(expected_header, AccountStorageHeader::from(&account_storage))
387    }
388
389    #[test]
390    fn test_serde_account_storage_header() {
391        // create new storage header
392        let storage = AccountStorage::mock();
393        let storage_header = AccountStorageHeader::from(&storage);
394
395        // serde storage header
396        let bytes = storage_header.to_bytes();
397        let deserialized = AccountStorageHeader::read_from_bytes(&bytes).unwrap();
398
399        // assert deserialized == storage header
400        assert_eq!(storage_header, deserialized);
401    }
402
403    #[test]
404    fn test_to_elements_from_elements_empty() {
405        // Construct empty header.
406        let empty_header = AccountStorageHeader::new(vec![]).unwrap();
407        let empty_elements = empty_header.to_elements();
408
409        // Call from_elements.
410        let empty_slot_names = BTreeMap::new();
411        let reconstructed_empty =
412            AccountStorageHeader::try_from_elements(&empty_elements, &empty_slot_names).unwrap();
413        assert_eq!(empty_header, reconstructed_empty);
414    }
415
416    #[test]
417    fn test_to_elements_from_elements_single_slot() {
418        // Construct single slot header.
419        let slot_name1 = StorageSlotName::new("test::value::slot1".to_string()).unwrap();
420        let slot1 = StorageSlotHeader::new(
421            slot_name1,
422            StorageSlotType::Value,
423            Word::new([Felt::ONE, Felt::from(2_u32), Felt::from(3_u32), Felt::from(4_u32)]),
424        );
425
426        let single_slot_header = AccountStorageHeader::new(vec![slot1.clone()]).unwrap();
427        let single_elements = single_slot_header.to_elements();
428
429        // Call from_elements.
430        let slot_names = BTreeMap::from([(slot1.id(), slot1.name().clone())]);
431        let reconstructed_single =
432            AccountStorageHeader::try_from_elements(&single_elements, &slot_names).unwrap();
433
434        assert_eq!(single_slot_header, reconstructed_single);
435    }
436
437    #[test]
438    fn test_to_elements_from_elements_multiple_slot() {
439        // Construct multi slot header.
440        let slot_name2 = StorageSlotName::new("test::map::slot2".to_string()).unwrap();
441        let slot_name3 = StorageSlotName::new("test::value::slot3".to_string()).unwrap();
442
443        let slot2 = StorageSlotHeader::new(
444            slot_name2,
445            StorageSlotType::Map,
446            Word::new([Felt::from(5_u32), Felt::from(6_u32), Felt::from(7_u32), Felt::from(8_u32)]),
447        );
448        let slot3 = StorageSlotHeader::new(
449            slot_name3,
450            StorageSlotType::Value,
451            Word::new([
452                Felt::from(9_u32),
453                Felt::from(10_u32),
454                Felt::from(11_u32),
455                Felt::from(12_u32),
456            ]),
457        );
458
459        let mut slots = vec![slot2, slot3];
460        slots.sort_by_key(|slot| slot.id());
461        let multi_slot_header = AccountStorageHeader::new(slots.clone()).unwrap();
462        let multi_elements = multi_slot_header.to_elements();
463
464        // Call from_elements.
465        let slot_names = BTreeMap::from([
466            (slots[0].id(), slots[0].name.clone()),
467            (slots[1].id(), slots[1].name.clone()),
468        ]);
469        let reconstructed_multi =
470            AccountStorageHeader::try_from_elements(&multi_elements, &slot_names).unwrap();
471
472        assert_eq!(multi_slot_header, reconstructed_multi);
473    }
474
475    #[test]
476    fn test_from_elements_errors() {
477        // Test with invalid length (not divisible by 8).
478        let invalid_elements = vec![Felt::ONE, Felt::new_unchecked(2), Felt::new_unchecked(3)];
479        let empty_slot_names = BTreeMap::new();
480        assert!(
481            AccountStorageHeader::try_from_elements(&invalid_elements, &empty_slot_names).is_err()
482        );
483
484        // Test with invalid slot type.
485        let mut invalid_type_elements = vec![crate::ZERO; 8];
486        invalid_type_elements[1] = Felt::new_unchecked(5); // Invalid slot type.
487        assert!(
488            AccountStorageHeader::try_from_elements(&invalid_type_elements, &empty_slot_names)
489                .is_err()
490        );
491    }
492
493    #[test]
494    fn test_from_elements_with_slot_names() {
495        use alloc::collections::BTreeMap;
496
497        // Create original slot with known name.
498        let slot_name1 = StorageSlotName::new("test::value::slot1".to_string()).unwrap();
499        let slot1 = StorageSlotHeader::new(
500            slot_name1.clone(),
501            StorageSlotType::Value,
502            Word::new([Felt::ONE, Felt::from(2_u32), Felt::from(3_u32), Felt::from(4_u32)]),
503        );
504
505        // Serialize the single slot to elements
506        let elements = slot1.to_elements();
507
508        // Create slot names map using the slot's ID
509        let mut slot_names = BTreeMap::new();
510        slot_names.insert(slot1.id(), slot_name1.clone());
511
512        // Test from_elements with provided slot names on raw slot elements.
513        let reconstructed_header =
514            AccountStorageHeader::try_from_elements(&elements, &slot_names).unwrap();
515
516        // Verify that the original slot names are preserved.
517        assert_eq!(reconstructed_header.slots().count(), 1);
518        let reconstructed_slot = reconstructed_header.slots().next().unwrap();
519
520        assert_eq!(slot_name1.as_str(), reconstructed_slot.name().as_str());
521        assert_eq!(slot1.slot_type(), reconstructed_slot.slot_type());
522        assert_eq!(slot1.value(), reconstructed_slot.value());
523    }
524}
miden_protocol/account/storage/header.rs

miden_protocol/account/storage/
header.rs
