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.as_chunks::<{ StorageSlot::NUM_ELEMENTS }>().0 {
172            // The first element of each slot record is reserved and must be zero.
173            if chunk[0] != Felt::ZERO {
174                return Err(AccountError::StorageSlotReservedElementNotZero(chunk[0]));
175            }
176
177            // Parse slot type from second element.
178            let slot_type_felt = chunk[1];
179            let slot_type = slot_type_felt.try_into()?;
180
181            // Parse slot ID from third and fourth elements.
182            let slot_id_suffix = chunk[2];
183            let slot_id_prefix = chunk[3];
184            let parsed_slot_id = StorageSlotId::new(slot_id_suffix, slot_id_prefix);
185
186            // Retrieve slot name from the map.
187            let slot_name = slot_names.get(&parsed_slot_id).cloned().ok_or(AccountError::other(
188                format!("slot name not found for slot ID {}", parsed_slot_id),
189            ))?;
190
191            // Parse slot value from last 4 elements.
192            let slot_value = Word::new([chunk[4], chunk[5], chunk[6], chunk[7]]);
193
194            let slot_header = StorageSlotHeader::new(slot_name, slot_type, slot_value);
195            slots.push(slot_header);
196        }
197
198        // Sort slots by ID.
199        slots.sort_by_key(|slot| slot.id());
200
201        Self::new(slots)
202    }
203
204    /// Returns the commitment to the [`AccountStorage`] this header represents.
205    pub fn to_commitment(&self) -> Word {
206        <Self as SequentialCommit>::to_commitment(self)
207    }
208}
209
210impl From<&AccountStorage> for AccountStorageHeader {
211    fn from(value: &AccountStorage) -> Self {
212        value.to_header()
213    }
214}
215
216// SEQUENTIAL COMMIT
217// ================================================================================================
218
219impl SequentialCommit for AccountStorageHeader {
220    type Commitment = Word;
221
222    fn to_elements(&self) -> Vec<Felt> {
223        self.slots().flat_map(|slot| slot.to_elements()).collect()
224    }
225}
226
227// SERIALIZATION
228// ================================================================================================
229
230impl Serializable for AccountStorageHeader {
231    fn write_into<W: ByteWriter>(&self, target: &mut W) {
232        let len = self.slots.len() as u8;
233        target.write_u8(len);
234        target.write_many(self.slots())
235    }
236}
237
238impl Deserializable for AccountStorageHeader {
239    fn read_from<R: ByteReader>(source: &mut R) -> Result<Self, DeserializationError> {
240        let len = source.read_u8()?;
241        let slots: Vec<StorageSlotHeader> =
242            source.read_many_iter(len as usize)?.collect::<Result<_, _>>()?;
243        Self::new(slots).map_err(|err| DeserializationError::InvalidValue(err.to_string()))
244    }
245}
246
247// STORAGE SLOT HEADER
248// ================================================================================================
249
250/// The header of a [`StorageSlot`], storing only the slot name (or ID), slot type and value of the
251/// slot.
252///
253/// The stored value differs based on the slot type:
254/// - [`StorageSlotType::Value`]: The value of the slot itself.
255/// - [`StorageSlotType::Map`]: The root of the SMT that represents the storage map.
256#[derive(Debug, Clone, PartialEq, Eq)]
257pub struct StorageSlotHeader {
258    name: StorageSlotName,
259    r#type: StorageSlotType,
260    value: Word,
261}
262
263impl StorageSlotHeader {
264    // CONSTRUCTORS
265    // --------------------------------------------------------------------------------------------
266
267    /// Returns a new instance of storage slot header.
268    pub fn new(name: StorageSlotName, r#type: StorageSlotType, value: Word) -> Self {
269        Self { name, r#type, value }
270    }
271
272    /// Returns a new instance of storage slot header with an empty value slot.
273    pub fn with_empty_value(name: StorageSlotName) -> StorageSlotHeader {
274        StorageSlotHeader::new(name, StorageSlotType::Value, Word::default())
275    }
276
277    /// Returns a new instance of storage slot header with an empty map slot.
278    pub fn with_empty_map(name: StorageSlotName) -> StorageSlotHeader {
279        StorageSlotHeader::new(name, StorageSlotType::Map, EMPTY_STORAGE_MAP_ROOT)
280    }
281
282    // ACCESSORS
283    // --------------------------------------------------------------------------------------------
284
285    /// Returns a reference to the slot name.
286    pub fn name(&self) -> &StorageSlotName {
287        &self.name
288    }
289
290    /// Returns the slot ID.
291    pub fn id(&self) -> StorageSlotId {
292        self.name.id()
293    }
294
295    /// Returns the slot type.
296    pub fn slot_type(&self) -> StorageSlotType {
297        self.r#type
298    }
299
300    /// Returns the slot value.
301    pub fn value(&self) -> Word {
302        self.value
303    }
304
305    /// Returns this storage slot header as field elements.
306    ///
307    /// This is done by converting this storage slot into 8 field elements as follows:
308    /// ```text
309    /// [[0, slot_type, slot_id_suffix, slot_id_prefix], SLOT_VALUE]
310    /// ```
311    pub(crate) fn to_elements(&self) -> [Felt; StorageSlot::NUM_ELEMENTS] {
312        let id = self.id();
313        let mut elements = [ZERO; StorageSlot::NUM_ELEMENTS];
314        elements[0..4].copy_from_slice(&[
315            Felt::ZERO,
316            self.r#type.as_felt(),
317            id.suffix(),
318            id.prefix(),
319        ]);
320        elements[4..8].copy_from_slice(self.value.as_elements());
321        elements
322    }
323}
324
325impl From<&StorageSlot> for StorageSlotHeader {
326    fn from(slot: &StorageSlot) -> Self {
327        StorageSlotHeader::new(slot.name().clone(), slot.slot_type(), slot.value())
328    }
329}
330
331// SERIALIZATION
332// ================================================================================================
333
334impl Serializable for StorageSlotHeader {
335    fn write_into<W: ByteWriter>(&self, target: &mut W) {
336        self.name.write_into(target);
337        self.r#type.write_into(target);
338        self.value.write_into(target);
339    }
340}
341
342impl Deserializable for StorageSlotHeader {
343    fn read_from<R: ByteReader>(source: &mut R) -> Result<Self, DeserializationError> {
344        let name = StorageSlotName::read_from(source)?;
345        let slot_type = StorageSlotType::read_from(source)?;
346        let value = Word::read_from(source)?;
347        Ok(Self::new(name, slot_type, value))
348    }
349}
350
351// TESTS
352// ================================================================================================
353
354#[cfg(test)]
355mod tests {
356    use alloc::collections::BTreeMap;
357    use alloc::string::ToString;
358
359    use assert_matches::assert_matches;
360    use miden_core::Felt;
361
362    use super::AccountStorageHeader;
363    use crate::Word;
364    use crate::account::{AccountStorage, StorageSlotHeader, StorageSlotName, StorageSlotType};
365    use crate::errors::AccountError;
366    use crate::testing::storage::{MOCK_MAP_SLOT, MOCK_VALUE_SLOT0, MOCK_VALUE_SLOT1};
367    use crate::utils::serde::{Deserializable, Serializable};
368
369    #[test]
370    fn test_from_account_storage() {
371        let storage_map = AccountStorage::mock_map();
372
373        // create new storage header from AccountStorage
374        let mut slots = vec![
375            (MOCK_VALUE_SLOT0.clone(), StorageSlotType::Value, Word::from([1, 2, 3, 4u32])),
376            (
377                MOCK_VALUE_SLOT1.clone(),
378                StorageSlotType::Value,
379                Word::from([
380                    Felt::from(5_u32),
381                    Felt::from(6_u32),
382                    Felt::from(7_u32),
383                    Felt::from(8_u32),
384                ]),
385            ),
386            (MOCK_MAP_SLOT.clone(), StorageSlotType::Map, storage_map.root()),
387        ];
388        slots.sort_unstable_by_key(|(slot_name, ..)| slot_name.id());
389
390        let expected_header = AccountStorageHeader::from_tuples(slots).unwrap();
391        let account_storage = AccountStorage::mock();
392
393        assert_eq!(expected_header, AccountStorageHeader::from(&account_storage))
394    }
395
396    #[test]
397    fn test_serde_account_storage_header() {
398        // create new storage header
399        let storage = AccountStorage::mock();
400        let storage_header = AccountStorageHeader::from(&storage);
401
402        // serde storage header
403        let bytes = storage_header.to_bytes();
404        let deserialized = AccountStorageHeader::read_from_bytes(&bytes).unwrap();
405
406        // assert deserialized == storage header
407        assert_eq!(storage_header, deserialized);
408    }
409
410    #[test]
411    fn test_to_elements_from_elements_empty() {
412        // Construct empty header.
413        let empty_header = AccountStorageHeader::new(vec![]).unwrap();
414        let empty_elements = empty_header.to_elements();
415
416        // Call from_elements.
417        let empty_slot_names = BTreeMap::new();
418        let reconstructed_empty =
419            AccountStorageHeader::try_from_elements(&empty_elements, &empty_slot_names).unwrap();
420        assert_eq!(empty_header, reconstructed_empty);
421    }
422
423    #[test]
424    fn test_to_elements_from_elements_single_slot() {
425        // Construct single slot header.
426        let slot_name1 = StorageSlotName::new("test::value::slot1".to_string()).unwrap();
427        let slot1 = StorageSlotHeader::new(
428            slot_name1,
429            StorageSlotType::Value,
430            Word::new([Felt::ONE, Felt::from(2_u32), Felt::from(3_u32), Felt::from(4_u32)]),
431        );
432
433        let single_slot_header = AccountStorageHeader::new(vec![slot1.clone()]).unwrap();
434        let single_elements = single_slot_header.to_elements();
435
436        // Call from_elements.
437        let slot_names = BTreeMap::from([(slot1.id(), slot1.name().clone())]);
438        let reconstructed_single =
439            AccountStorageHeader::try_from_elements(&single_elements, &slot_names).unwrap();
440
441        assert_eq!(single_slot_header, reconstructed_single);
442    }
443
444    #[test]
445    fn test_to_elements_from_elements_multiple_slot() {
446        // Construct multi slot header.
447        let slot_name2 = StorageSlotName::new("test::map::slot2".to_string()).unwrap();
448        let slot_name3 = StorageSlotName::new("test::value::slot3".to_string()).unwrap();
449
450        let slot2 = StorageSlotHeader::new(
451            slot_name2,
452            StorageSlotType::Map,
453            Word::new([Felt::from(5_u32), Felt::from(6_u32), Felt::from(7_u32), Felt::from(8_u32)]),
454        );
455        let slot3 = StorageSlotHeader::new(
456            slot_name3,
457            StorageSlotType::Value,
458            Word::new([
459                Felt::from(9_u32),
460                Felt::from(10_u32),
461                Felt::from(11_u32),
462                Felt::from(12_u32),
463            ]),
464        );
465
466        let mut slots = vec![slot2, slot3];
467        slots.sort_by_key(|slot| slot.id());
468        let multi_slot_header = AccountStorageHeader::new(slots.clone()).unwrap();
469        let multi_elements = multi_slot_header.to_elements();
470
471        // Call from_elements.
472        let slot_names = BTreeMap::from([
473            (slots[0].id(), slots[0].name.clone()),
474            (slots[1].id(), slots[1].name.clone()),
475        ]);
476        let reconstructed_multi =
477            AccountStorageHeader::try_from_elements(&multi_elements, &slot_names).unwrap();
478
479        assert_eq!(multi_slot_header, reconstructed_multi);
480    }
481
482    #[test]
483    fn test_from_elements_errors() {
484        // Test with invalid length (not divisible by 8).
485        let invalid_elements = vec![Felt::ONE, Felt::new_unchecked(2), Felt::new_unchecked(3)];
486        let empty_slot_names = BTreeMap::new();
487        assert!(
488            AccountStorageHeader::try_from_elements(&invalid_elements, &empty_slot_names).is_err()
489        );
490
491        // Test with invalid slot type.
492        let mut invalid_type_elements = vec![crate::ZERO; 8];
493        invalid_type_elements[1] = Felt::new_unchecked(5); // Invalid slot type.
494        assert!(
495            AccountStorageHeader::try_from_elements(&invalid_type_elements, &empty_slot_names)
496                .is_err()
497        );
498
499        // Test with a non-zero reserved element.
500        let mut reserved_elements = vec![crate::ZERO; 8];
501        reserved_elements[0] = Felt::ONE; // Reserved element must be zero.
502        let err = AccountStorageHeader::try_from_elements(&reserved_elements, &empty_slot_names)
503            .unwrap_err();
504        assert_matches!(err, AccountError::StorageSlotReservedElementNotZero(value) if value == Felt::ONE);
505    }
506
507    #[test]
508    fn test_from_elements_with_slot_names() {
509        use alloc::collections::BTreeMap;
510
511        // Create original slot with known name.
512        let slot_name1 = StorageSlotName::new("test::value::slot1".to_string()).unwrap();
513        let slot1 = StorageSlotHeader::new(
514            slot_name1.clone(),
515            StorageSlotType::Value,
516            Word::new([Felt::ONE, Felt::from(2_u32), Felt::from(3_u32), Felt::from(4_u32)]),
517        );
518
519        // Serialize the single slot to elements
520        let elements = slot1.to_elements();
521
522        // Create slot names map using the slot's ID
523        let mut slot_names = BTreeMap::new();
524        slot_names.insert(slot1.id(), slot_name1.clone());
525
526        // Test from_elements with provided slot names on raw slot elements.
527        let reconstructed_header =
528            AccountStorageHeader::try_from_elements(&elements, &slot_names).unwrap();
529
530        // Verify that the original slot names are preserved.
531        assert_eq!(reconstructed_header.slots().count(), 1);
532        let reconstructed_slot = reconstructed_header.slots().next().unwrap();
533
534        assert_eq!(slot_name1.as_str(), reconstructed_slot.name().as_str());
535        assert_eq!(slot1.slot_type(), reconstructed_slot.slot_type());
536        assert_eq!(slot1.value(), reconstructed_slot.value());
537    }
538}
miden_protocol/account/storage/header.rs

miden_protocol/account/storage/
header.rs
