Unify asset delta into one

[PhilippGackstatter]

See the parent issue for higher-level context.

The asset delta must be able to represent addition and removal of assets.

For non-fungible assets, it is relatively simple since they do not compose. So, we only need to be able to represent adding and removing a non-fungible asset, and validating that we do not add it twice or remove it twice.

For fungible assets, we need to compose them, e.g. adding 30 and 40 of the same asset to an account vault should give +70 at the end, or adding 30 and removing 40 should result in a delta that removes 10.

Suppose that:

• {} is the empty delta,
• { Add(x) } is a delta that adds asset x to the vault, analogously for Remove(x),
• x and y are assets with a matching vault key.
• merge(a, b) -> c is a procedure that runs c = a + b.
• split(a, b) -> c is a procedure that runs c = a - b, i.e. "split b off of a".
• ==, > and < are comparison operators on assets.
• merge, split and > and < panic for non-fungible assets, but == is implemented.

For a general asset delta, we need to handle the following cases:

• add(x, {}) = { Add(x) }
• remove(x, {}) = { Remove(x) }
• add(x, { Add(y) }) = { Add(merge(x, y)) }
• remove(x, { Remove(y) }) = { Remove(merge(x, y)) }
• add(x, { Remove(y) }) =
  • if y == x: {}
  • if y > x: Remove(split(y, x)) # "split X off Y"
  • if y < x: Add(split(x, y)) # "split Y off X"
• remove(x, { Add(y) }) =
  • if y == x: {}
  • if y > x: Add(split(y, x)) # "split X off Y"
  • if y < x: Remove(split(x, y)) # "split Y off X"

To illustrate with examples:

• For fungible assets:
  • add(30, { Remove(30) }) would result in an empty delta since the operations cancel.
  • add(30, { Remove(40) }) would result in Remove(10) since we get Remove(split(40, 30)), so we split 30 off of 40, leaving 10.
  • add(40, { Remove(30) }) would result in Add(10) since we call Add(split(40, 30)), same as above, just wrapped in Add.
  • remove(30, { Add(40) }) would result in Add(10) since we call Add(split(40, 30)).
  • remove(40, { Add(30) }) would result in Remove(10) since we call Remove(split(40, 30)).
• For non-fungible assets:
  • Adding or removing them to an empty delta works fine.
  • Cancel case: remove(x, add(x, {})) = {} , because x == x, i.e. both key and value match.
  • Cancel case: add(x, remove(x, {})) = {}, because x == x, i.e. both key and value match.
    • If we have x and y with a matching key but a different value, these cancel cases would correctly panic instead (since non-fungible assets cannot be ordered).

Delta Commitment

The delta commitment needs to updated as well since we can no longer assume fungible or non-fungible assets.

The delta needs to commit to 1) the delta operation (add, remove) and 2) the asset itself. The main difficulty is that the asset itself takes up 2 words already, and the delta op is essentially one bit.

Option 1: Commit to 4 words

The straightforward option is to add 4 words per entry (sorted by key):

• [[domain = 1, delta_op, 0, 0], [0, 0, 0, 0]]
• [ASSET_KEY, ASSET_VALUE]

This works, but results in roughly double the amount of hashing than other options.

Option 2: Split into Add/Remove delta

Another option is to iterate the asset delta twice and in the first round, commit to the added assets, skipping removed ones, and in the second round commit to the removed assets, skipping added ones:

• First round
  • Per Entry (sorted by key): [ASSET_KEY, ASSET_VALUE]
  • Once: [[domain = 1, num_added_assets, 0, 0], [0, 0, 0, 0]]
• Second round
  • Per Entry (sorted by key): [ASSET_KEY, ASSET_VALUE]
  • Once: [[domain = 2, num_removed_assets, 0, 0], [0, 0, 0, 0]]

This is more efficient in terms of hashing, but requires iterating twice (more cycles).

Option 3: Keep separate Add/Remove delta

To avoid iterating twice, we can maintain separate maps, one representing added and one representing removed assets. That way, we can do the same as the previous option but without having to skip entries.

The downside here is that, e.g. when mutating the delta, we need to access the removed and added map in order to maintain the delta correctly. In some cases we will need to remove an entry from the added delta and insert one into the removed delta, which seems like quite a bit of complexity in masm.

Option 4: Put delta op into asset key

We could encode the delta op bit into the unused 8 bits of the asset key, to commit to the delta op within the two asset words. This would probably constrain us from using that bit in the future, so this is probably not a good idea.

Option 5: Keep current approach and ignore custom assets

Make the delta uniform over fungible and non-fungible assets, but only those by keeping the current approach of not committing to the asset ID. The asset ID has predictable values for the native assets, but this constraint is unlikely to be true for custom assets in the future.

So we could use the current approach, but we'd then have to add a new delta for custom assets anyway, defeating a large part of the overall goal.

Summary

Generally we can:

• Optimize for the least cycles (option 1)
• Optimize for the least hashing
  • Option 2: Delta commitment computation more costly than mutation.
  • Option 3: Delta mutation more costly than commitment computation.

In terms of complexity, I think option 2 is likely lower than option 3 and we probably want to optimize for keeping the number of cycles per delta mutation lower than the commitment computation (which should be done rarely, ideally once per tx - and we could look into caching).

Rust

The same change would have to be done accordingly to the AssetVaultDelta in Rust.

[bobbinth]

There may be another approach as well. First, let's consider the case of "absolute" deltas:

For such deltas, we don't need to keep track of additions/removals because an EMPTY_WORD in asset value implies asset removal - and everything else implies asset addition. For example, given the following list of assets, we can unambiguously determine if we want to add or remove asset:

1. [K1, V1] - adding asset V1 under K1 key.
2. [K2, EMPTY_WORD] - removing asset with key K2.

Here, there is actually no differentiation between fungible, non-fungible, or custom assets. In fact, when applying an "absolute" delta to an account vault, we just need to insert the asset values under the corresponding keys (and maybe check that if we insert an EMPTY_WORD, the old value wasn't `EMPTY_WORD).

To convert this to "relative" deltas, we just need to allow the fungible asset values to be "negative". Basically, if we know that a given delta is a "relative" delta, we can always identify which asset is a fungible asset by looking at the asset key, and then, if the amount is positive, we know it is an addition, but if it is negative, we know it is a subtraction.

Conceptually, this could look something like:

/// The name is just illustrative
enum AssetDeltaWrapper {
    Absolute(AssetDelta),
    Relative(AssetDelta),
}

struct AssetDelta(Vec<Asset>);

struct Asset {
    key: AssetKey,
    value: Word,
}

impl Asset {
    /// Returns asset amount if the underlying asset is a fungible asset, and the value of the
    /// asset is positive.
    pub fn unwrap_amount(&self) -> Option<Felt> {
        ...
    }

    /// Returns an asset amount if the underlying asset is a fungible asset, and converts the
    /// amount into a positive or negative integer depending on the value of internal felt.
    pub fn unwrap_amount_delta(&self) -> Option<i64> {
        ...
    }
}

Serialization of assets could still be "specialized" so that we don't waste too much space for fungible assets and compress the serialization of EMPTY_WORD to a single bit - but that's a separate concern.

If the above works, we can simplify the asset concept significantly. The delta also becomes quite a bit simpler - but we do need to know, at the top level, if we are working with an absolute or a relative delta (so, there is some loss in type safety).

[PhilippGackstatter]

Thanks for the idea! I'm not sure, I fully understood how it is meant to be implemented, so I may be getting some things wrong, specifically is the idea is to have the tx kernel only produce one kind of delta from which we derive the other one?

Let's say an account has 100 USDC and a transaction sends 40 USDC out in a note, then the kernel needs to produce:

• the new value of "60 USDC" for the absolute delta
• and "remove 40 USDC" for the relative delta.

Afaict, in your approach, the tx kernel would still need to produce and commit to the relative and absolute deltas separately, because we cannot derive the relative from the absolute or the absolute from the relative delta. A commitment to "remove 40 USDC" is different from a commitment to "new value is 60 USDC".

That approach also means the tx kernel and the protocol still have the definitions of the fungible/non-fungible assets baked-in. To produce the relative delta, the kernel needs to know that fungible assets have amounts at index 0 of the value word and what the max amount is to produce negative amounts. That is essentially the approach we have in the kernel now.

My goal with this (and the parent issue) was to remove the concept of native assets from the protocol layer as much as possible, so the tx kernel can just treat assets as having a key with an issuer ID and an arbitrary value, exactly what you defined:

struct Asset {
    key: AssetKey,
    value: Word,
}

With your approach, I think we wouldn't be able to compute relative deltas for custom assets (this requires the use of merge, split and compare, afaict), since the kernel won't know how to produce "remove 40 USDC" if it is a custom asset.

Abstractions

For completeness: The only exception to having fully abstracted assets are the built-in compose functions for fungible assets (merge, split, compare), but that's it. If we implement absolute deltas before mainnet, there is no technical reason we couldn't remove that too and simplify the protocol's definitions of assets further to have only AssetCallbackFlag + AssetStructure (defining whether assets are word-sized or larger). This would be the cleanest state we could get to, at the cost of not being able to serialize fungible assets as efficiently as possible. Imo, the architecture is more important than the efficiency gained for one category of assets and that would be consistent with the rest of the major protocol parts:

• Notes
  • Protocol Layer: Storage + Code + Assets - abstract
  • Standards Layer: P2ID, PSWAP, etc. - concrete
• Account Components
  • Protocol Layer: Storage + Code + Vault - abstract
  • Standards Layer: BasicWallet, BasicFungibleFaucet, etc. - concrete
• Assets
  • Current State
    • Protocol layer: Fungible and Non-fungible assets - concrete
    • Standards Layer: None
  • "Ideal" State
    • Protocol layer: Generic assets - abstract
    • Standards Layer: Fungible and Non-fungible assets - concrete

Absolute Delta
Just to be clear, with this issue I hadn't considered absolute deltas at all, only relative ones, but I didn't state this very clearly. Specifically, the goal is to unify fungible and non-fungible asset deltas into one and at the same time come up with a structure that can handle custom assets in the future so we don't have to change the way the delta commitment is computed.

But, I think absolute deltas could be computed in the kernel based on the relative delta without tracking additional data:

• If the relative asset delta is empty, that means nothing has changed and so the absolute delta is also empty.
• If there is an entry in the relative asset delta for asset key ASSET_KEY1, then we know ASSET_KEY1 has changed and we append the new value of the asset to the absolute asset delta elements that we hash (retrieved via asset_vault::get_asset(ASSET_KEY1, account_vault_root_ptr)). This is independent of whether the relative change is "add" or "remove" since we don't care about this for the absolute delta.

The same would work for the storage delta for slot or map entries that have actually changed (not every entry in the storage map delta link map implies a change). Once we determine that a slot's value or map entry has changed, we similarly append the new value of that slot/map entry to the absolute delta elements.

So, I think we need to have account_delta::{compute_relative_commitment, compute_absolute_commitment} that share much of the change detection logic and are only different in whether they hash the relative operation or the absolute one.

[bobbinth]

Afaict, in your approach, the tx kernel would still need to produce and commit to the relative and absolute deltas separately, because we cannot derive the relative from the absolute or the absolute from the relative delta. A commitment to "remove 40 USDC" is different from a commitment to "new value is 60 USDC".

Yes, the commitment would be different, but the structure of the delta would be the same. Basically, I'm trying to have the same exact methodology for computing commitments for relative and absolute deltas. Here is an example:

Let's say we have two delta's "new value is 60 USDC" and "remove 40 USDC". Both of these could be represented using Vec<Asset> as follows:

For "new value is 60 USDC", the asset would be:

[key = USDS, value = [0, 0, 0, 60]]

For "remove 40 USDC", the asset would be:

[key = USDS, value = [0, 0, 0, -40]]

The commitment to these would be computed by building a list of elements and then hashing them. The elements would include a header + the list of assets (similar to how we handle storage maps now). For example, for the absolute delta the elements would be:

[domain_lo, domain_hi, num_changes = 1, is_absolute = 1, 0, 0, 0, 0]
[key = USDS, value = [0, 0, 0, 60]]

And for relative delta, the elements would be:

[domain_lo, domain_hi, num_changes = 1, is_absolute = 0, 0, 0, 0, 0]
[key = USDS, value = [0, 0, 0, 60]]

The idea of the domain here is that we'd pick something that can't collide with an account ID (but also, this is just a sketch, there could be other ways to handle things).

So, in both cases, the procedure for computing the delta is the same - but the result would obviously be different.

---

The way I think this could work in the transaction kernel:

1. While the transaction kernel is executing, we keep track of relative delta as we do now. This allows the user to sign the relative delta commitment in the auth procedure.
2. Then, once we get to the epilogue, we convert the relative delta into an absolute delta. The procedure for this should be pretty simple: just iterate over the asset entries, and for any fungible asset, just replace the fungible asset value with the value from the vault.
3. Then, we compute the absolute delta commitment using the same exact procedure as we used to compute the relative delta commitment. The only difference would be that we'd flip the is_absolute flag for the delta header.

---

In Rust, the delta could work roughly like so:

pub enum AccountVaultDelta {
    Absolute(Vec<Asset>),
    Relative(Vec<Asset>),
}

struct Asset {
    key: AssetVaultKey,
    value: Word, // this can be EMPTY_WORD which indicates absence/removal of the asset
}

impl Asset {
    /// Returns an asset amount if the underlying asset is a fungible asset, and converts the
    /// amount into a positive or negative integer depending on the value of internal felt.
    pub fn unwrap_amount_delta(&self) -> Option<i64> {
        ...
    }
}

// And then, in AssetVault


impl AssetVault {

    pub fn apply_delta(&mut self, delta: &AccountVaultDelta) -> Result<(), AssetVaultError> {

        match delta {
            AccountVaultDelta::Absolute(assets) => {
                for asset in assets {
                    // both insertions and deletions are handled by this organically
                    self.asset_tree.insert(asset.key.to_word(), asset.value)?;
                }
            },
            AccountVaultDelta::Relative(assets) => {
                for asset in assets {
                    match asset.unwrap_amount_delta() {
                        Some(amount_delta) => {
                            // special handling for relative amounts of fungible assets
                            // but both additions and removals are handled organically
                            let current_value = self.asset_tree.get_value(&asset.key.to_word());
                            let current_amount = current_value[0].as_canonical_u64() as i64;
                            let new_amount = current_amount + amount_delta;
                            let new_amount = Felt::new(new_amount as u64);
                            let new_value = Word::new([new_amount, ZERO, ZERO, ZERO]);
                            self.asset_tree.insert(asset.key.to_word(), new_value)?;
                        }
                        None => {
                            // this is a non-fungible asset
                            self.asset_tree.insert(asset.key.to_word(), asset.value)?;
                        }
                    }
                }
            },
        }
        
        Ok(())
    }
}

All of the above does assume that the kernel:

1. Can identify which asset is fungible.
2. Knows how to merge fungible assets.
3. Understand the structure of the fungible asset value - i.e., the fact that the list significant element is the amount and that this value must be in a certain range.

But I'm not sure if we get away from this anyways.

[PhilippGackstatter]

Just to note it down from the meeting, the only places in which we need a relative delta is the TransactionSummary, all other places can use an AbsoluteAccountDelta, so:

pub struct RelativeAccountDelta { ... }

pub struct AbsoluteAccountDelta { ... }

pub struct TransactionSummary {
    account_delta: RelativeAccountDelta,
    // remaining fields unchanged
}

pub struct ExecutedTransaction {
    account_delta: AbsoluteAccountDelta,
    // remaining fields unchanged
}

// Contained in ProvenTransaction
pub enum AccountUpdateDetails {
    Private,
    Delta(AbsoluteAccountDelta),
}