miden_protocol/account/patch/storage/storage_patch.rs
1use alloc::collections::BTreeMap;
2use alloc::string::ToString;
3use alloc::vec::Vec;
4
5use super::slot_patch::MergeOutcome;
6use crate::Felt;
7use crate::account::{
8 AccountStorage,
9 StorageMapPatch,
10 StorageSlotName,
11 StorageSlotPatch,
12 StorageValuePatch,
13};
14use crate::errors::AccountPatchError;
15use crate::utils::serde::{
16 ByteReader,
17 ByteWriter,
18 Deserializable,
19 DeserializationError,
20 Serializable,
21};
22
23// ACCOUNT STORAGE PATCH
24// ================================================================================================
25
26/// The [`AccountStoragePatch`] stores the changes between two states of account storage.
27///
28/// The patch consists of a map from [`StorageSlotName`] to [`StorageSlotPatch`], where each slot
29/// patch records whether the slot was created, updated, or removed (see [`StorageValuePatch`] and
30/// [`StorageMapPatch`]).
31#[derive(Clone, Debug, PartialEq, Eq)]
32pub struct AccountStoragePatch {
33 /// The patches to the slots of the account.
34 patches: BTreeMap<StorageSlotName, StorageSlotPatch>,
35}
36
37impl AccountStoragePatch {
38 /// Domain separator for value storage slots in delta and patch commitments.
39 const DOMAIN_VALUE: Felt = Felt::new_unchecked(5);
40
41 /// Domain separator for map storage slots in delta and patch commitments.
42 const DOMAIN_MAP: Felt = Felt::new_unchecked(6);
43
44 // CONSTRUCTORS
45 // --------------------------------------------------------------------------------------------
46
47 /// Creates a new, empty storage patch.
48 pub fn new() -> Self {
49 Self { patches: BTreeMap::new() }
50 }
51
52 /// Creates a new storage patch from the provided map of slot patches.
53 ///
54 /// Because the input is already a map keyed by slot name, slot name uniqueness holds by
55 /// construction. Use [`AccountStoragePatch::from_entries`] to build a patch from a sequence
56 /// that may contain duplicates.
57 ///
58 /// # Errors
59 ///
60 /// Returns an error if the number of patches exceeds
61 /// [`AccountStorage::MAX_NUM_STORAGE_SLOTS`].
62 pub fn from_raw(
63 patches: BTreeMap<StorageSlotName, StorageSlotPatch>,
64 ) -> Result<Self, AccountPatchError> {
65 if patches.len() > AccountStorage::MAX_NUM_STORAGE_SLOTS {
66 return Err(AccountPatchError::TooManyStorageSlotPatches(patches.len()));
67 }
68
69 Ok(Self { patches })
70 }
71
72 /// Creates a new storage patch from the provided sequence of slot patches.
73 ///
74 /// # Errors
75 ///
76 /// Returns an error if the same [`StorageSlotName`] appears more than once.
77 pub fn from_entries(
78 entries: impl IntoIterator<Item = (StorageSlotName, StorageSlotPatch)>,
79 ) -> Result<Self, AccountPatchError> {
80 let mut patches = BTreeMap::new();
81 for (slot_name, slot_patch) in entries {
82 if patches.insert(slot_name.clone(), slot_patch).is_some() {
83 return Err(AccountPatchError::DuplicateStorageSlotName(slot_name));
84 }
85 }
86
87 Self::from_raw(patches)
88 }
89
90 // ACCESSORS
91 // --------------------------------------------------------------------------------------------
92
93 /// Returns the patch for the provided slot name, or `None` if no patch exists.
94 pub fn get(&self, slot_name: &StorageSlotName) -> Option<&StorageSlotPatch> {
95 self.patches.get(slot_name)
96 }
97
98 /// Returns the number of slot patches.
99 pub fn num_slots(&self) -> usize {
100 self.patches.len()
101 }
102
103 /// Returns an iterator over the slot patches.
104 pub(crate) fn slots(&self) -> impl Iterator<Item = (&StorageSlotName, &StorageSlotPatch)> {
105 self.patches.iter()
106 }
107
108 /// Returns an iterator over the value slot patches in this storage patch.
109 pub fn values(&self) -> impl Iterator<Item = (&StorageSlotName, &StorageValuePatch)> {
110 self.patches.iter().filter_map(|(slot_name, slot_patch)| match slot_patch {
111 StorageSlotPatch::Value(value_patch) => Some((slot_name, value_patch)),
112 StorageSlotPatch::Map(_) => None,
113 })
114 }
115
116 /// Returns an iterator over the map slot patches in this storage patch.
117 pub fn maps(&self) -> impl Iterator<Item = (&StorageSlotName, &StorageMapPatch)> {
118 self.patches.iter().filter_map(|(slot_name, slot_patch)| match slot_patch {
119 StorageSlotPatch::Value(_) => None,
120 StorageSlotPatch::Map(map_patch) => Some((slot_name, map_patch)),
121 })
122 }
123
124 /// Returns true if storage patch contains no patches.
125 pub fn is_empty(&self) -> bool {
126 self.patches.is_empty()
127 }
128
129 /// Returns `true` if any slot patch is not a
130 /// [`StoragePatchOperation::Create`](crate::account::StoragePatchOperation::Create), i.e. it
131 /// updates or removes an existing slot.
132 pub(in crate::account) fn contains_non_create_ops(&self) -> bool {
133 self.patches.values().any(|slot_patch| !slot_patch.patch_op().is_create())
134 }
135
136 // MUTATORS
137 // --------------------------------------------------------------------------------------------
138
139 /// Merges another patch into this one, with the entries of `other` taking precedence.
140 ///
141 /// Each patch represents an atomic state change of account storage. This state change could be
142 /// from a transaction, batch or block, as the latter two merge individual patches into a single
143 /// one. Since the transaction is the lowest member in this hierarchy, the merge behavior is
144 /// modelled so that whatever is valid (or invalid) to do in one transaction after another is
145 /// also valid (or invalid) to merge.
146 ///
147 /// In general the operations have the following meaning:
148 /// - `Create` takes the slot from absent to present.
149 /// - `Update` requires the slot is present and updates it.
150 /// - `Remove` takes the slot from present to absent.
151 ///
152 /// The nine permutations of `(current, incoming)` resolve as follows:
153 ///
154 /// - `(Create, Create)`: Errors because the second create assumes the slot is absent, but the
155 /// first already makes it present.
156 /// - `(Create, Update)`: Merged to `Create`. The slot stays newly created, but carries the
157 /// updated value.
158 /// - `(Create, Remove)`: Cancels out, so the slot patch is dropped entirely. A slot created and
159 /// then removed validly results in the slot being absent. This normalizes away such patches
160 /// and makes the patch not commit to a no-op (removing a slot that doesn't exist).
161 /// - `(Update, Create)`: Errors because the create assumes the slot is absent, but the update
162 /// already requires it is present.
163 /// - `(Update, Update)`: Merged to `Update`, keeping the latest value.
164 /// - `(Update, Remove)`: Merged to `Remove`.
165 /// - `(Remove, Create)`: Merged to `Create`. A slot removed and then re-created nets to a
166 /// (re-)creation carrying the new value. The resulting `Create` is applied to a base state
167 /// that still has the slot, so this re-creates an existing slot with the carried value.
168 /// - `(Remove, Update)`: Errors because the update requires a present slot, but the remove left
169 /// it absent.
170 /// - `(Remove, Remove)`: Errors because the second remove requires a present slot, but the
171 /// first already makes it absent.
172 ///
173 /// Value and map slots behave the same at the operation level, but map entries are merged
174 /// entry-wise instead of being fully replaced.
175 ///
176 /// The error cases never occur when merging patches coming out of transactions or patches that
177 /// were aggregated from transactions, as these are exactly the cases that would not be allowed
178 /// by the transaction kernel. For instance, updating a slot in tx 2 when tx 1 removed it would
179 /// be rejected in tx 2, since it would not exist.
180 pub fn merge(&mut self, other: Self) -> Result<(), AccountPatchError> {
181 for (slot_name, slot_patch) in other.patches {
182 match self.patches.get_mut(&slot_name) {
183 None => {
184 self.patches.insert(slot_name, slot_patch);
185 },
186 Some(existing) => {
187 if let MergeOutcome::Remove = existing.merge(&slot_name, slot_patch)? {
188 self.patches.remove(&slot_name);
189 }
190 },
191 }
192 }
193
194 if self.patches.len() > AccountStorage::MAX_NUM_STORAGE_SLOTS {
195 return Err(AccountPatchError::TooManyStorageSlotPatches(self.patches.len()));
196 }
197
198 Ok(())
199 }
200
201 /// Consumes self and returns the underlying map of the storage patch.
202 pub fn into_map(self) -> BTreeMap<StorageSlotName, StorageSlotPatch> {
203 self.patches
204 }
205
206 // COMMITMENT
207 // --------------------------------------------------------------------------------------------
208
209 /// Appends the storage slot patches to the given `elements` from which the delta or patch
210 /// commitment is computed.
211 pub(in crate::account) fn append_patch_elements(&self, elements: &mut Vec<Felt>) {
212 for (slot_name, slot_patch) in self.patches.iter() {
213 let slot_id = slot_name.id();
214
215 match slot_patch {
216 StorageSlotPatch::Value(value_patch) => {
217 elements.extend_from_slice(&[
218 Self::DOMAIN_VALUE,
219 Felt::from(value_patch.patch_op().as_u8()),
220 slot_id.suffix(),
221 slot_id.prefix(),
222 ]);
223 elements.extend_from_slice(value_patch.committed_value().as_elements());
224 },
225 StorageSlotPatch::Map(map_patch) => {
226 let num_changed_entries = if let Some(map_entries) = map_patch.entries() {
227 for (key, value) in map_entries.as_map() {
228 elements.extend_from_slice(key.as_elements());
229 elements.extend_from_slice(value.as_elements());
230 }
231
232 map_entries.num_entries() as u64
233 } else {
234 // If the map slot was removed the number of removed entries is unknown and
235 // so we commit to 0 changed entries.
236 0
237 };
238 let num_changed_entries = Felt::try_from(num_changed_entries).expect(
239 "number of changed entries should not exceed max representable felt",
240 );
241
242 let omit_trailer =
243 map_patch.patch_op().is_update() && num_changed_entries == Felt::ZERO;
244 if !omit_trailer {
245 elements.extend_from_slice(&[
246 Self::DOMAIN_MAP,
247 Felt::from(map_patch.patch_op().as_u8()),
248 slot_id.suffix(),
249 slot_id.prefix(),
250 ]);
251 elements.extend_from_slice(&[
252 num_changed_entries,
253 Felt::ZERO,
254 Felt::ZERO,
255 Felt::ZERO,
256 ]);
257 }
258 },
259 }
260 }
261 }
262}
263
264impl Default for AccountStoragePatch {
265 fn default() -> Self {
266 Self::new()
267 }
268}
269
270impl Serializable for AccountStoragePatch {
271 fn write_into<W: ByteWriter>(&self, target: &mut W) {
272 let num_slots = u8::try_from(self.patches.len()).expect("number of slots should fit in u8");
273 target.write_u8(num_slots);
274 target.write_many(self.slots());
275 }
276
277 fn get_size_hint(&self) -> usize {
278 let mut size = 0u8.get_size_hint();
279 for (slot_name, slot_patch) in self.patches.iter() {
280 size += slot_name.get_size_hint() + slot_patch.get_size_hint();
281 }
282 size
283 }
284}
285
286impl Deserializable for AccountStoragePatch {
287 fn read_from<R: ByteReader>(source: &mut R) -> Result<Self, DeserializationError> {
288 let num_slots = source.read_u8()? as usize;
289 let entries = source
290 .read_many_iter::<(StorageSlotName, StorageSlotPatch)>(num_slots)?
291 .collect::<Result<Vec<_>, _>>()?;
292
293 Self::from_entries(entries)
294 .map_err(|err| DeserializationError::InvalidValue(err.to_string()))
295 }
296}