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(2);
40
41 /// Domain separator for map storage slots in delta and patch commitments.
42 const DOMAIN_MAP: Felt = Felt::new_unchecked(3);
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 in ascending slot ID order.
104 ///
105 /// The order is guaranteed by the [`BTreeMap`] backing this patch, whose keys are ordered by
106 /// their slot IDs.
107 pub fn slots(&self) -> impl Iterator<Item = (&StorageSlotName, &StorageSlotPatch)> {
108 self.patches.iter()
109 }
110
111 /// Returns an iterator over the value slot patches in this storage patch.
112 pub fn values(&self) -> impl Iterator<Item = (&StorageSlotName, &StorageValuePatch)> {
113 self.patches.iter().filter_map(|(slot_name, slot_patch)| match slot_patch {
114 StorageSlotPatch::Value(value_patch) => Some((slot_name, value_patch)),
115 StorageSlotPatch::Map(_) => None,
116 })
117 }
118
119 /// Returns an iterator over the map slot patches in this storage patch.
120 pub fn maps(&self) -> impl Iterator<Item = (&StorageSlotName, &StorageMapPatch)> {
121 self.patches.iter().filter_map(|(slot_name, slot_patch)| match slot_patch {
122 StorageSlotPatch::Value(_) => None,
123 StorageSlotPatch::Map(map_patch) => Some((slot_name, map_patch)),
124 })
125 }
126
127 /// Returns true if storage patch contains no patches.
128 pub fn is_empty(&self) -> bool {
129 self.patches.is_empty()
130 }
131
132 /// Returns `true` if any slot patch is not a
133 /// [`StoragePatchOperation::Create`](crate::account::StoragePatchOperation::Create), i.e. it
134 /// updates or removes an existing slot.
135 pub(in crate::account) fn contains_non_create_ops(&self) -> bool {
136 self.patches.values().any(|slot_patch| !slot_patch.patch_op().is_create())
137 }
138
139 // MUTATORS
140 // --------------------------------------------------------------------------------------------
141
142 /// Merges another patch into this one, with the entries of `other` taking precedence.
143 ///
144 /// Each patch represents an atomic state change of account storage. This state change could be
145 /// from a transaction, batch or block, as the latter two merge individual patches into a single
146 /// one. Since the transaction is the lowest member in this hierarchy, the merge behavior is
147 /// modelled so that whatever is valid (or invalid) to do in one transaction after another is
148 /// also valid (or invalid) to merge.
149 ///
150 /// In general the operations have the following meaning:
151 /// - `Create` takes the slot from absent to present.
152 /// - `Update` requires the slot is present and updates it.
153 /// - `Remove` takes the slot from present to absent.
154 ///
155 /// The nine permutations of `(current, incoming)` resolve as follows:
156 ///
157 /// - `(Create, Create)`: Errors because the second create assumes the slot is absent, but the
158 /// first already makes it present.
159 /// - `(Create, Update)`: Merged to `Create`. The slot stays newly created, but carries the
160 /// updated value.
161 /// - `(Create, Remove)`: Cancels out, so the slot patch is dropped entirely. A slot created and
162 /// then removed validly results in the slot being absent. This normalizes away such patches
163 /// and makes the patch not commit to a no-op (removing a slot that doesn't exist).
164 /// - `(Update, Create)`: Errors because the create assumes the slot is absent, but the update
165 /// already requires it is present.
166 /// - `(Update, Update)`: Merged to `Update`, keeping the latest value.
167 /// - `(Update, Remove)`: Merged to `Remove`.
168 /// - `(Remove, Create)`: Merged to `Create`. A slot removed and then re-created nets to a
169 /// (re-)creation carrying the new value. The resulting `Create` is applied to a base state
170 /// that still has the slot, so this re-creates an existing slot with the carried value.
171 /// - `(Remove, Update)`: Errors because the update requires a present slot, but the remove left
172 /// it absent.
173 /// - `(Remove, Remove)`: Errors because the second remove requires a present slot, but the
174 /// first already makes it absent.
175 ///
176 /// Value and map slots behave the same at the operation level, but map entries are merged
177 /// entry-wise instead of being fully replaced.
178 ///
179 /// The error cases never occur when merging patches coming out of transactions or patches that
180 /// were aggregated from transactions, as these are exactly the cases that would not be allowed
181 /// by the transaction kernel. For instance, updating a slot in tx 2 when tx 1 removed it would
182 /// be rejected in tx 2, since it would not exist.
183 pub fn merge(&mut self, other: Self) -> Result<(), AccountPatchError> {
184 for (slot_name, slot_patch) in other.patches {
185 match self.patches.get_mut(&slot_name) {
186 None => {
187 self.patches.insert(slot_name, slot_patch);
188 },
189 Some(existing) => {
190 if let MergeOutcome::Remove = existing.merge(&slot_name, slot_patch)? {
191 self.patches.remove(&slot_name);
192 }
193 },
194 }
195 }
196
197 if self.patches.len() > AccountStorage::MAX_NUM_STORAGE_SLOTS {
198 return Err(AccountPatchError::TooManyStorageSlotPatches(self.patches.len()));
199 }
200
201 Ok(())
202 }
203
204 /// Consumes self and returns the underlying map of the storage patch.
205 pub fn into_map(self) -> BTreeMap<StorageSlotName, StorageSlotPatch> {
206 self.patches
207 }
208
209 // COMMITMENT
210 // --------------------------------------------------------------------------------------------
211
212 /// Appends the storage slot patches to the given `elements` from which the delta or patch
213 /// commitment is computed.
214 pub(in crate::account) fn append_patch_elements(&self, elements: &mut Vec<Felt>) {
215 for (slot_name, slot_patch) in self.patches.iter() {
216 let slot_id = slot_name.id();
217
218 match slot_patch {
219 StorageSlotPatch::Value(value_patch) => {
220 elements.extend_from_slice(&[
221 Self::DOMAIN_VALUE,
222 Felt::from(value_patch.patch_op().as_u8()),
223 slot_id.suffix(),
224 slot_id.prefix(),
225 ]);
226 elements.extend_from_slice(value_patch.committed_value().as_elements());
227 },
228 StorageSlotPatch::Map(map_patch) => {
229 let num_changed_entries = if let Some(map_entries) = map_patch.entries() {
230 for (key, value) in map_entries.as_map() {
231 elements.extend_from_slice(key.as_elements());
232 elements.extend_from_slice(value.as_elements());
233 }
234
235 map_entries.num_entries() as u64
236 } else {
237 // If the map slot was removed the number of removed entries is unknown and
238 // so we commit to 0 changed entries.
239 0
240 };
241 let num_changed_entries = Felt::try_from(num_changed_entries).expect(
242 "number of changed entries should not exceed max representable felt",
243 );
244
245 let omit_trailer =
246 map_patch.patch_op().is_update() && num_changed_entries == Felt::ZERO;
247 if !omit_trailer {
248 elements.extend_from_slice(&[
249 Self::DOMAIN_MAP,
250 Felt::from(map_patch.patch_op().as_u8()),
251 slot_id.suffix(),
252 slot_id.prefix(),
253 ]);
254 elements.extend_from_slice(&[
255 num_changed_entries,
256 Felt::ZERO,
257 Felt::ZERO,
258 Felt::ZERO,
259 ]);
260 }
261 },
262 }
263 }
264 }
265}
266
267impl Default for AccountStoragePatch {
268 fn default() -> Self {
269 Self::new()
270 }
271}
272
273impl Serializable for AccountStoragePatch {
274 fn write_into<W: ByteWriter>(&self, target: &mut W) {
275 let num_slots = u8::try_from(self.patches.len()).expect("number of slots should fit in u8");
276 target.write_u8(num_slots);
277 target.write_many(self.slots());
278 }
279
280 fn get_size_hint(&self) -> usize {
281 let mut size = 0u8.get_size_hint();
282 for (slot_name, slot_patch) in self.patches.iter() {
283 size += slot_name.get_size_hint() + slot_patch.get_size_hint();
284 }
285 size
286 }
287}
288
289impl Deserializable for AccountStoragePatch {
290 fn read_from<R: ByteReader>(source: &mut R) -> Result<Self, DeserializationError> {
291 let num_slots = source.read_u8()? as usize;
292 let entries = source
293 .read_many_iter::<(StorageSlotName, StorageSlotPatch)>(num_slots)?
294 .collect::<Result<Vec<_>, _>>()?;
295
296 Self::from_entries(entries)
297 .map_err(|err| DeserializationError::InvalidValue(err.to_string()))
298 }
299}