miden_objects/account/delta/mod.rs
1use alloc::{string::ToString, vec::Vec};
2
3use super::{
4 Account, ByteReader, ByteWriter, Deserializable, DeserializationError, Felt, Serializable,
5 Word, ZERO,
6};
7use crate::{AccountDeltaError, Digest, EMPTY_WORD, Hasher, account::AccountId};
8
9mod lexicographic_word;
10pub use lexicographic_word::LexicographicWord;
11
12mod storage;
13pub use storage::{AccountStorageDelta, StorageMapDelta};
14
15mod vault;
16pub use vault::{
17 AccountVaultDelta, FungibleAssetDelta, NonFungibleAssetDelta, NonFungibleDeltaAction,
18};
19
20// ACCOUNT DELTA
21// ================================================================================================
22
23/// [AccountDelta] stores the differences between two account states.
24///
25/// The differences are represented as follows:
26/// - storage: an [AccountStorageDelta] that contains the changes to the account storage.
27/// - vault: an [AccountVaultDelta] object that contains the changes to the account vault.
28/// - nonce: if the nonce of the account has changed, the _delta_ of the nonce is stored, i.e. the
29/// value by which the nonce increased.
30///
31/// TODO: add ability to trace account code updates.
32#[derive(Clone, Debug, PartialEq, Eq)]
33pub struct AccountDelta {
34 /// The ID of the account to which this delta applies. If the delta is created during
35 /// transaction execution, that is the native account of the transaction.
36 account_id: AccountId,
37 /// The delta of the account's storage.
38 storage: AccountStorageDelta,
39 /// The delta of the account's asset vault.
40 vault: AccountVaultDelta,
41 /// The value by which the nonce was incremented. Must be greater than zero if storage or vault
42 /// are non-empty.
43 nonce_delta: Felt,
44}
45
46impl AccountDelta {
47 // CONSTRUCTOR
48 // --------------------------------------------------------------------------------------------
49 /// Returns new [AccountDelta] instantiated from the provided components.
50 ///
51 /// # Errors
52 ///
53 /// - Returns an error if storage or vault were updated, but the nonce was either not updated or
54 /// set to 0.
55 pub fn new(
56 account_id: AccountId,
57 storage: AccountStorageDelta,
58 vault: AccountVaultDelta,
59 nonce_delta: Felt,
60 ) -> Result<Self, AccountDeltaError> {
61 // nonce must be updated if either account storage or vault were updated
62 validate_nonce(nonce_delta, &storage, &vault)?;
63
64 Ok(Self { account_id, storage, vault, nonce_delta })
65 }
66
67 /// Merge another [AccountDelta] into this one.
68 pub fn merge(&mut self, other: Self) -> Result<(), AccountDeltaError> {
69 let new_nonce_delta = self.nonce_delta + other.nonce_delta;
70
71 if new_nonce_delta.as_int() < self.nonce_delta.as_int() {
72 return Err(AccountDeltaError::NonceIncrementOverflow {
73 current: self.nonce_delta,
74 increment: other.nonce_delta,
75 new: new_nonce_delta,
76 });
77 }
78
79 self.nonce_delta = new_nonce_delta;
80
81 self.storage.merge(other.storage)?;
82 self.vault.merge(other.vault)
83 }
84
85 // PUBLIC ACCESSORS
86 // --------------------------------------------------------------------------------------------
87
88 /// Returns true if this account delta does not contain any vault, storage or nonce updates.
89 pub fn is_empty(&self) -> bool {
90 self.storage.is_empty() && self.vault.is_empty() && self.nonce_delta == ZERO
91 }
92
93 /// Returns storage updates for this account delta.
94 pub fn storage(&self) -> &AccountStorageDelta {
95 &self.storage
96 }
97
98 /// Returns vault updates for this account delta.
99 pub fn vault(&self) -> &AccountVaultDelta {
100 &self.vault
101 }
102
103 /// Returns the amount by which the nonce was incremented.
104 pub fn nonce_delta(&self) -> Felt {
105 self.nonce_delta
106 }
107
108 /// Returns the account ID to which this delta applies.
109 pub fn id(&self) -> AccountId {
110 self.account_id
111 }
112
113 /// Converts this storage delta into individual delta components.
114 pub fn into_parts(self) -> (AccountStorageDelta, AccountVaultDelta, Felt) {
115 (self.storage, self.vault, self.nonce_delta)
116 }
117
118 /// Computes the commitment to the account delta.
119 ///
120 /// The delta is a sequential hash over a vector of field elements which starts out empty and
121 /// is appended to in the following way. Whenever sorting is expected, it is that of a link map
122 /// key. The WORD layout is in memory-order.
123 ///
124 /// - Append `[[nonce_delta, 0, account_id_suffix, account_id_prefix], EMPTY_WORD]`, where
125 /// account_id_{prefix,suffix} are the prefix and suffix felts of the native account id and
126 /// nonce_delta is the value by which the nonce was incremented.
127 /// - Fungible Asset Delta
128 /// - For each **updated** fungible asset, sorted by its vault key, whose amount delta is
129 /// **non-zero**:
130 /// - Append `[domain = 1, was_added, 0, 0]`.
131 /// - Append `[amount, 0, faucet_id_suffix, faucet_id_prefix]` where amount is the delta by
132 /// which the fungible asset's amount has changed and was_added is a boolean flag
133 /// indicating whether the amount was added (1) or subtracted (0).
134 /// - Non-Fungible Asset Delta
135 /// - For each **updated** non-fungible asset, sorted by its vault key:
136 /// - Append `[domain = 1, was_added, 0, 0]` where was_added is a boolean flag indicating
137 /// whether the asset was added (1) or removed (0). Note that the domain is the same for
138 /// assets since `faucet_id_prefix` is at the same position in the layout for both assets,
139 /// and, by design, it is never the same for fungible and non-fungible assets.
140 /// - Append `[hash0, hash1, hash2, faucet_id_prefix]`, i.e. the non-fungible asset.
141 /// - Storage Slots - for each slot **whose value has changed**, depending on the slot type:
142 /// - Value Slot
143 /// - Append `[[domain = 2, slot_idx, 0, 0], NEW_VALUE]` where NEW_VALUE is the new value of
144 /// the slot and slot_idx is the index of the slot.
145 /// - Map Slot
146 /// - For each key-value pair, sorted by key, whose new value is different from the previous
147 /// value in the map:
148 /// - Append `[KEY, NEW_VALUE]`.
149 /// - Append `[[domain = 3, slot_idx, num_changed_entries, 0], 0, 0, 0, 0]`, except if
150 /// `num_changed_entries` is 0, where slot_idx is the index of the slot and
151 /// `num_changed_entries` is the number of changed key-value pairs in the map.
152 ///
153 /// # Rationale
154 ///
155 /// The rationale for this layout is that hashing in the VM should be as efficient as possible
156 /// and minimize the number of branches to be as efficient as possible. Every high-level section
157 /// in this bullet point list should add an even number of words since the hasher operates
158 /// on double words. In the VM, each permutation is done immediately, so adding an uneven
159 /// number of words in a given step will result in more difficulty in the MASM implementation.
160 ///
161 /// # Security
162 ///
163 /// The general concern with the commitment is that two deltas must never has to the same
164 /// commitment. E.g. a commitment of a delta that changes a key-value pair in a storage map
165 /// slot should be different from a delta that adds a non-fungible asset to the vault. If
166 /// not, a delta can be crafted in the VM that sets a map key but a malicious actor crafts a
167 /// delta outside the VM that adds a non-fungible asset. To prevent that, a couple of
168 /// measures are taken.
169 ///
170 /// - Because multiple unrelated contexts (e.g. vaults and storage slots) are hashed in the same
171 /// hasher, domain separators are used to disambiguate. For each changed asset and each
172 /// changed slot in the delta, a domain separator is hashed into the delta. The domain
173 /// separator is always at the same index in each layout so it cannot be maliciously crafted
174 /// (see below for an example).
175 /// - Storage value slots:
176 /// - since only changed value slots are included in the delta, there is no ambiguity between
177 /// a value slot being set to EMPTY_WORD and its value being unchanged.
178 /// - Storage map slots:
179 /// - Map slots append a header which summarizes the changes in the slot, in particular the
180 /// slot index and number of changed entries. Since only changed slots are included, the
181 /// number of changed entries is never zero.
182 /// - Two distinct storage map slots use the same domain but are disambiguated due to
183 /// inclusion of the slot index.
184 ///
185 /// **Domain Separators**
186 ///
187 /// As an example for ambiguity, consider these two deltas:
188 ///
189 /// ```text
190 /// [
191 /// ID_AND_NONCE, EMPTY_WORD,
192 /// [/* no fungible asset delta */],
193 /// [[domain = 1, was_added = 1, 0, 0], NON_FUNGIBLE_ASSET],
194 /// [/* no storage delta */]
195 /// ]
196 /// ```
197 ///
198 /// ```text
199 /// [
200 /// ID_AND_NONCE, EMPTY_WORD,
201 /// [/* no fungible asset delta */],
202 /// [/* no non-fungible asset delta */],
203 /// [[domain = 2, slot_idx = 1, 0, 0], NEW_VALUE]
204 /// ]
205 /// ```
206 ///
207 /// `NEW_VALUE` is user-controllable so it can be crafted to match `NON_FUNGIBLE_ASSET`. The
208 /// domain separator is then the only value that differentiates these two deltas. This shows the
209 /// importance of placing the domain separators in the same index within each word's layout
210 /// which makes it easy to see that this value cannot be crafted to be the same.
211 ///
212 /// **Number of Changed Entries**
213 ///
214 /// As an example for ambiguity, consider these two deltas:
215 ///
216 /// ```text
217 /// [
218 /// EMPTY_WORD, ID_AND_NONCE,
219 /// [/* no fungible asset delta */],
220 /// [[domain = 1, was_added = 1, 0, 0], NON_FUNGIBLE_ASSET],
221 /// [/* no storage delta */],
222 /// ]
223 /// ```
224 ///
225 /// ```text
226 /// [
227 /// ID_AND_NONCE, EMPTY_WORD,
228 /// [/* no fungible asset delta */],
229 /// [/* no non-fungible asset delta */],
230 /// [KEY0, VALUE0],
231 /// [KEY1, VALUE1],
232 /// [domain = 3, slot_idx = 0, num_changed_entries = 2, 0, 0, 0, 0, 0]
233 /// ]
234 /// ```
235 ///
236 /// The keys and values of map slots are user-controllable so `KEY0` and `VALUE0` can be crafted
237 /// to match `NON_FUNGIBLE_ASSET` and its metadata. Including the header of the map slot
238 /// additionally hashes the map domain into the delta, but if the header was included whenever
239 /// _any_ value in the map has changed, it would cause ambiguity about whether `KEY0`/`VALUE0`
240 /// are in fact map keys or a non-fungible asset (or any asset or a value storage slot more
241 /// generally). Including `num_changed_entries` disambiguates this situation, by ensuring
242 /// that the delta commitment is different when, e.g. 1) a non-fungible asset and one key-value
243 /// pair have changed and 2) when two key-value pairs have changed.
244 pub fn commitment(&self) -> Digest {
245 // The commitment to an empty delta is defined as the empty word.
246 if self.is_empty() {
247 return Digest::default();
248 }
249
250 // Minor optimization: At least 24 elements are always added.
251 let mut elements = Vec::with_capacity(24);
252
253 // ID and Nonce
254 elements.extend_from_slice(&[
255 self.nonce_delta,
256 ZERO,
257 self.account_id.suffix(),
258 self.account_id.prefix().as_felt(),
259 ]);
260 elements.extend_from_slice(&EMPTY_WORD);
261
262 // Vault Delta
263 self.vault.append_delta_elements(&mut elements);
264
265 // Storage Delta
266 self.storage.append_delta_elements(&mut elements);
267
268 debug_assert!(
269 elements.len() % (2 * crate::WORD_SIZE) == 0,
270 "expected elements to contain an even number of words, but it contained {} elements",
271 elements.len()
272 );
273
274 Hasher::hash_elements(&elements)
275 }
276}
277
278/// Describes the details of an account state transition resulting from applying a transaction to
279/// the account.
280#[derive(Clone, Debug, PartialEq, Eq)]
281pub enum AccountUpdateDetails {
282 /// Account is private (no on-chain state change).
283 Private,
284
285 /// The whole state is needed for new accounts.
286 New(Account),
287
288 /// For existing accounts, only the delta is needed.
289 Delta(AccountDelta),
290}
291
292impl AccountUpdateDetails {
293 /// Returns `true` if the account update details are for private account.
294 pub fn is_private(&self) -> bool {
295 matches!(self, Self::Private)
296 }
297
298 /// Merges the `other` update into this one.
299 ///
300 /// This account update is assumed to come before the other.
301 pub fn merge(self, other: AccountUpdateDetails) -> Result<Self, AccountDeltaError> {
302 let merged_update = match (self, other) {
303 (AccountUpdateDetails::Private, AccountUpdateDetails::Private) => {
304 AccountUpdateDetails::Private
305 },
306 (AccountUpdateDetails::New(mut account), AccountUpdateDetails::Delta(delta)) => {
307 account.apply_delta(&delta).map_err(|err| {
308 AccountDeltaError::AccountDeltaApplicationFailed {
309 account_id: account.id(),
310 source: err,
311 }
312 })?;
313
314 AccountUpdateDetails::New(account)
315 },
316 (AccountUpdateDetails::Delta(mut delta), AccountUpdateDetails::Delta(new_delta)) => {
317 delta.merge(new_delta)?;
318 AccountUpdateDetails::Delta(delta)
319 },
320 (left, right) => {
321 return Err(AccountDeltaError::IncompatibleAccountUpdates {
322 left_update_type: left.as_tag_str(),
323 right_update_type: right.as_tag_str(),
324 });
325 },
326 };
327
328 Ok(merged_update)
329 }
330
331 /// Returns the tag of the [`AccountUpdateDetails`] as a string for inclusion in error messages.
332 pub(crate) const fn as_tag_str(&self) -> &'static str {
333 match self {
334 AccountUpdateDetails::Private => "private",
335 AccountUpdateDetails::New(_) => "new",
336 AccountUpdateDetails::Delta(_) => "delta",
337 }
338 }
339}
340
341// SERIALIZATION
342// ================================================================================================
343
344impl Serializable for AccountDelta {
345 fn write_into<W: ByteWriter>(&self, target: &mut W) {
346 self.account_id.write_into(target);
347 self.storage.write_into(target);
348 self.vault.write_into(target);
349 self.nonce_delta.write_into(target);
350 }
351
352 fn get_size_hint(&self) -> usize {
353 self.account_id.get_size_hint()
354 + self.storage.get_size_hint()
355 + self.vault.get_size_hint()
356 + self.nonce_delta.get_size_hint()
357 }
358}
359
360impl Deserializable for AccountDelta {
361 fn read_from<R: ByteReader>(source: &mut R) -> Result<Self, DeserializationError> {
362 let account_id = AccountId::read_from(source)?;
363 let storage = AccountStorageDelta::read_from(source)?;
364 let vault = AccountVaultDelta::read_from(source)?;
365 let nonce_delta = Felt::read_from(source)?;
366
367 validate_nonce(nonce_delta, &storage, &vault)
368 .map_err(|err| DeserializationError::InvalidValue(err.to_string()))?;
369
370 Ok(Self { account_id, storage, vault, nonce_delta })
371 }
372}
373
374impl Serializable for AccountUpdateDetails {
375 fn write_into<W: ByteWriter>(&self, target: &mut W) {
376 match self {
377 AccountUpdateDetails::Private => {
378 0_u8.write_into(target);
379 },
380 AccountUpdateDetails::New(account) => {
381 1_u8.write_into(target);
382 account.write_into(target);
383 },
384 AccountUpdateDetails::Delta(delta) => {
385 2_u8.write_into(target);
386 delta.write_into(target);
387 },
388 }
389 }
390
391 fn get_size_hint(&self) -> usize {
392 // Size of the serialized enum tag.
393 let u8_size = 0u8.get_size_hint();
394
395 match self {
396 AccountUpdateDetails::Private => u8_size,
397 AccountUpdateDetails::New(account) => u8_size + account.get_size_hint(),
398 AccountUpdateDetails::Delta(account_delta) => u8_size + account_delta.get_size_hint(),
399 }
400 }
401}
402
403impl Deserializable for AccountUpdateDetails {
404 fn read_from<R: ByteReader>(source: &mut R) -> Result<Self, DeserializationError> {
405 match u8::read_from(source)? {
406 0 => Ok(Self::Private),
407 1 => Ok(Self::New(Account::read_from(source)?)),
408 2 => Ok(Self::Delta(AccountDelta::read_from(source)?)),
409 v => Err(DeserializationError::InvalidValue(format!(
410 "Unknown variant {v} for AccountDetails"
411 ))),
412 }
413 }
414}
415
416// HELPER FUNCTIONS
417// ================================================================================================
418
419/// Checks if the nonce was updated correctly given the provided storage and vault deltas.
420///
421/// # Errors
422///
423/// Returns an error if:
424/// - storage or vault were updated, but the nonce_delta was set to 0.
425fn validate_nonce(
426 nonce_delta: Felt,
427 storage: &AccountStorageDelta,
428 vault: &AccountVaultDelta,
429) -> Result<(), AccountDeltaError> {
430 if (!storage.is_empty() || !vault.is_empty()) && nonce_delta == ZERO {
431 return Err(AccountDeltaError::ZeroNonceForNonEmptyDelta);
432 }
433
434 Ok(())
435}
436
437// TESTS
438// ================================================================================================
439
440#[cfg(test)]
441mod tests {
442
443 use assert_matches::assert_matches;
444 use vm_core::{Felt, FieldElement, utils::Serializable};
445
446 use super::{AccountDelta, AccountStorageDelta, AccountVaultDelta};
447 use crate::{
448 AccountDeltaError, ONE, ZERO,
449 account::{
450 Account, AccountCode, AccountId, AccountStorage, AccountStorageMode, AccountType,
451 StorageMapDelta, delta::AccountUpdateDetails,
452 },
453 asset::{Asset, AssetVault, FungibleAsset, NonFungibleAsset, NonFungibleAssetDetails},
454 testing::account_id::{
455 ACCOUNT_ID_PRIVATE_SENDER, ACCOUNT_ID_REGULAR_PRIVATE_ACCOUNT_UPDATABLE_CODE,
456 AccountIdBuilder,
457 },
458 };
459
460 #[test]
461 fn account_delta_nonce_validation() {
462 let account_id = AccountId::try_from(ACCOUNT_ID_PRIVATE_SENDER).unwrap();
463 // empty delta
464 let storage_delta = AccountStorageDelta::new();
465 let vault_delta = AccountVaultDelta::default();
466
467 AccountDelta::new(account_id, storage_delta.clone(), vault_delta.clone(), ZERO).unwrap();
468 AccountDelta::new(account_id, storage_delta.clone(), vault_delta.clone(), ONE).unwrap();
469
470 // non-empty delta
471 let storage_delta = AccountStorageDelta::from_iters([1], [], []);
472
473 assert_matches!(
474 AccountDelta::new(account_id, storage_delta.clone(), vault_delta.clone(), ZERO)
475 .unwrap_err(),
476 AccountDeltaError::ZeroNonceForNonEmptyDelta
477 );
478 AccountDelta::new(account_id, storage_delta.clone(), vault_delta.clone(), ONE).unwrap();
479 }
480
481 #[test]
482 fn account_delta_nonce_overflow() {
483 let account_id = AccountId::try_from(ACCOUNT_ID_PRIVATE_SENDER).unwrap();
484 let storage_delta = AccountStorageDelta::new();
485 let vault_delta = AccountVaultDelta::default();
486
487 let nonce_delta0 = ONE;
488 let nonce_delta1 = Felt::try_from(0xffff_ffff_0000_0000u64).unwrap();
489
490 let mut delta0 =
491 AccountDelta::new(account_id, storage_delta.clone(), vault_delta.clone(), nonce_delta0)
492 .unwrap();
493 let delta1 =
494 AccountDelta::new(account_id, storage_delta, vault_delta, nonce_delta1).unwrap();
495
496 assert_matches!(delta0.merge(delta1).unwrap_err(), AccountDeltaError::NonceIncrementOverflow {
497 current, increment, new
498 } => {
499 assert_eq!(current, nonce_delta0);
500 assert_eq!(increment, nonce_delta1);
501 assert_eq!(new, nonce_delta0 + nonce_delta1);
502 });
503 }
504
505 #[test]
506 fn account_update_details_size_hint() {
507 // AccountDelta
508 let account_id = AccountId::try_from(ACCOUNT_ID_PRIVATE_SENDER).unwrap();
509 let storage_delta = AccountStorageDelta::new();
510 let vault_delta = AccountVaultDelta::default();
511 assert_eq!(storage_delta.to_bytes().len(), storage_delta.get_size_hint());
512 assert_eq!(vault_delta.to_bytes().len(), vault_delta.get_size_hint());
513
514 let account_delta =
515 AccountDelta::new(account_id, storage_delta, vault_delta, ZERO).unwrap();
516 assert_eq!(account_delta.to_bytes().len(), account_delta.get_size_hint());
517
518 let storage_delta = AccountStorageDelta::from_iters(
519 [1],
520 [(2, [ONE, ONE, ONE, ONE]), (3, [ONE, ONE, ZERO, ONE])],
521 [(
522 4,
523 StorageMapDelta::from_iters(
524 [[ONE, ONE, ONE, ZERO], [ZERO, ONE, ONE, ONE]],
525 [([ONE, ONE, ONE, ONE], [ONE, ONE, ONE, ONE])],
526 ),
527 )],
528 );
529
530 let non_fungible: Asset = NonFungibleAsset::new(
531 &NonFungibleAssetDetails::new(
532 AccountIdBuilder::new()
533 .account_type(AccountType::NonFungibleFaucet)
534 .storage_mode(AccountStorageMode::Public)
535 .build_with_rng(&mut rand::rng())
536 .prefix(),
537 vec![6],
538 )
539 .unwrap(),
540 )
541 .unwrap()
542 .into();
543 let fungible_2: Asset = FungibleAsset::new(
544 AccountIdBuilder::new()
545 .account_type(AccountType::FungibleFaucet)
546 .storage_mode(AccountStorageMode::Public)
547 .build_with_rng(&mut rand::rng()),
548 10,
549 )
550 .unwrap()
551 .into();
552 let vault_delta = AccountVaultDelta::from_iters([non_fungible], [fungible_2]);
553
554 assert_eq!(storage_delta.to_bytes().len(), storage_delta.get_size_hint());
555 assert_eq!(vault_delta.to_bytes().len(), vault_delta.get_size_hint());
556
557 let account_delta = AccountDelta::new(account_id, storage_delta, vault_delta, ONE).unwrap();
558 assert_eq!(account_delta.to_bytes().len(), account_delta.get_size_hint());
559
560 // Account
561
562 let account_id =
563 AccountId::try_from(ACCOUNT_ID_REGULAR_PRIVATE_ACCOUNT_UPDATABLE_CODE).unwrap();
564
565 let asset_vault = AssetVault::mock();
566 assert_eq!(asset_vault.to_bytes().len(), asset_vault.get_size_hint());
567
568 let account_storage = AccountStorage::mock();
569 assert_eq!(account_storage.to_bytes().len(), account_storage.get_size_hint());
570
571 let account_code = AccountCode::mock();
572 assert_eq!(account_code.to_bytes().len(), account_code.get_size_hint());
573
574 let account =
575 Account::from_parts(account_id, asset_vault, account_storage, account_code, Felt::ZERO);
576 assert_eq!(account.to_bytes().len(), account.get_size_hint());
577
578 // AccountUpdateDetails
579
580 let update_details_private = AccountUpdateDetails::Private;
581 assert_eq!(update_details_private.to_bytes().len(), update_details_private.get_size_hint());
582
583 let update_details_delta = AccountUpdateDetails::Delta(account_delta);
584 assert_eq!(update_details_delta.to_bytes().len(), update_details_delta.get_size_hint());
585
586 let update_details_new = AccountUpdateDetails::New(account);
587 assert_eq!(update_details_new.to_bytes().len(), update_details_new.get_size_hint());
588 }
589}