Allow representing creation and removal of slots in storage delta

[PhilippGackstatter]

This is essentially a follow-up to the things discovered while implementing the fix in #2077.

As mentioned there, the account storage delta we currently have was designed for representing a change to existing slots, while with #1879 and, in the future, account storage updates (e.g. creating new slots or removing existing ones), this structure should be updated to better allow for representing these states. In particular, this is intended to replace the fix from #2077.

One idea for a structure to represent such storage deltas in the Rust API could be (part of this is taken from #2025 and assumes we implement this after named storage slots):

pub struct AccountStorageDelta {
    /// The updates to the value slots of the account.
    values: BTreeMap<SlotName, StorageValueDelta>,
    /// The updates to the map slots of the account.
    maps: BTreeMap<SlotName, StorageMapDelta>,
}

pub enum SlotDeltaOperation {
    /// Represents a new slot being created in account storage.
    ///
    /// A slot with the associated slot name must not exist.
    Create = 0,
    /// Represents an update to an existing slot in the account storage.
    ///
    /// A slot with the associated slot name must exist.
    Update = 1,
    /// Represents the removal of an existing slot in the account storage.
    ///
    /// A slot with the associated slot name must exist.
    Remove = 2,
}

pub struct StorageValueDelta {
    operation: SlotDeltaOperation,
    value: Word,
}

pub struct StorageMapDelta {
    operation: SlotDeltaOperation,
    entries: BTreeMap<LexicographicWord, Word>,
}

For the storage part of the delta commitment, we could have the following updates:

• Storage Slots are sorted by slot name ID and are iterated in this order. For each slot, depending
  on the slot type:
  • Value Slot
    • Append [[domain = 2, delta_op, name_id_suffix, name_id_prefix], NEW_VALUE] where:
      • NEW_VALUE is the new value of the slot
      • name_id_{suffix, prefix} are the slot name identifiers of the slot.
      • delta_op indicates whether the slot was created (0), updated (1) or removed (2).
  • Map Slot
    • For each key-value pair, sorted by key, whose new value is different from the previous
      value in the map:
      • Append [KEY, NEW_VALUE].
    • Append [[domain = 3, delta_op, name_id_suffix, name_id_prefix], [num_changed_entries, 0, 0, 0]], where:
      • delta_op indicates whether the slot was created (0), updated (1) or removed (2).
      • name_id_{suffix, prefix} are the slot name identifiers of the slot.
      • num_changed_entries is the number of entries that have changed.
        • If delta_op is Update, the map header must only be included if num_changed_entries != 0. This allows normalizing away such no-op updates.

A bit more thought needs to be put into:

• the security of this, i.e. whether it creates ambiguities in the commitment format.
• whether this is easy to implement in MASM.
• What num_changed_entries should be set to when delta_op is Remove (probably 0 as we won't have the number of removed entries available?).

Other open points are:

• Where to store the delta operation in kernel memory (probably in ACCOUNT_DELTA_STORAGE_MAP_SECTION)
• How to do storage updates more broadly, which may make sense to think about before implementing this to make sure it is compatible.

As part of this we can also try to address this TODO: https://github.com/0xMiden/miden-base/blob/c532ae91fdf711ac2f8b253342c253ee2eac0bed/crates/miden-objects/src/account/delta/mod.rs#L355-L366.

[PhilippGackstatter]

As part of this, we can address some small outstanding comments from #2075 and #2077:

• Introduce memory::is_account_new fix: skip value slot normalization for new account's deltas #2075 (comment)
• Reconsider naming for AccountStorageDelta::insert_empty_map_delta (though this may simply go away as part of this) fix: new account map delta #2077 (comment)
• Use consistent terminology (e.g. "full state delta" or "new account"). Since this refactor is about the delta, it seems better to use "full state" terminology, because "new account" is not very well-defined in the delta context as we typically don't have access to the absolute nonce value of the account (only the relative nonce delta which doesn't imply whether it's a new or existing account) fix: new account map delta #2077 (comment)

[PhilippGackstatter]

This is currently blocked on #2025 which refactors part of the delta and I'd like to avoid even more merge conflicts. So this is best addressed after that PR or the named storage slots feature (#1724) in general.

[PhilippGackstatter]

As part of this, we can look into refactoring the delta to a slightly different structure, e.g. using BTreeMap<SlotName, StorageSlotDelta> instead of separate fields for each slot type (#2025 (comment)).

A small downside is that this no longer statically enforces that, e.g. set_map_item cannot set or overwrite a value slot, though we can return errors (or consider panicking) in these cases. In general, the delta cannot validate that a slot name exists or is of the right type as the account to which it "belong", so this is not a big deal.
On the other hand, we require the above structure in AccountStorageDelta::append_delta_elements anyway, and so this structure would be nicer for that.

The other thing to think about is how it affects "getter" APIs and if they'd get significantly worse.