Potential asset model

[maxgillett]

This note builds upon discussions #192 and #222, and outlines one potential mechanism for native asset support on Miden. We first discuss how assets are represented in accounts and notes, and then how they can be implemented in more detail in the VM.

Assets

Asset accounts can be used to represent fungible and non-fungible token contracts through the issuance of notes containing asset balances or item hashes, respectively. Item hashes can represent arbitrary metadata (e.g. ticket information, or a particular item's attributes). Any regular account can act as an asset by issuing these notes -- there is no distinction made in the state representation of these accounts. Below we sometimes refer to asset IDs, but this is just another name for account IDs that are being treated as assets.

Vaults

Assets reside in a vault, which is composed of a subvault for each asset type (fungible and non-fungible):

• A fungible subvault is a map between an account ID and mutable balance
• A non-fungible subvault is a map between an immutable item hash and account ID

All keys and values are represented by 256-bit words so as to maintain compatibility with EVM-based assets that may be bridged to the rollup.

Account vault

Each account subvault is stored as a sparse Merkle trie. The hash of an account vault is equal to hash([balance_subvault_root, item_subvault_root]) .

Note vault

Each note subvault is stored as a list, where the hash of the subvault is given by a sequential hash of the contents. For example, to represent a note subvault containing three fungible assets, we would compute the hash according to: balance_subvault_hash = hash(hash(hash(hash(h_0, h_a), h_b), h_c), 3), where h_i = hash(amount_i, asset_i), h_0 = hash(0,0) is used to mark the beginning of the vault, and the final hashed value 3 indicates the number of assets. A similar sequential hash can be computed for non-fungible assets, where h_i = hash(item_hash_i, asset_i).

The hash of a note vault is equal to hash([balance_subvault_hash, item_subvault_hash]).

Asset safety

Unlike EVM-based architectures, information about asset balances does not need to be stored in the storage of the smart contract account representing the asset, but can be distributed across user accounts, residing in each user's account vault. These vaults are simply another form of local account storage, so we need to ensure that an increase (decrease) in an account vault balance is matched with a decrease (increase) in a note vault balance. These safety checks do not apply when an asset account manipulates asset balances or item hashes that map to its own account ID.

These safety checks can be achieved by breaking transaction execution into three steps, as suggested in a previous discussion:

1. Prologue: The contents of the account and all input notes are combined in a new map (to be used in the epilogue).
2. Execution: The transaction program tx_program (also referred to as tx_script) is executed, which is responsible for consuming notes and executing note programs (if they exist).
3. Epilogue: A new map is constructed with the combined contents of the account and all output notes, and compared to the map constructed during the prologue. If these two maps do not match then the transaction fails.

Implementation in Miden VM

Asset creation

Asset balances can be created by calling a kernel function mint_balance(amount), which adds amount to accountID in the account's balance subvault. To move this newly created amount to a produced note, a kernel function create_note(serial_num, program_root, vault_root) must be called. A higher-level function such as create_asset_note(amount, recipient) can be used to set program_root to one that restricts consumption to recipient, and vault_root to one that contains only the amount of the asset.

Item hashes can be created by calling mint_item(hash), which adds a hash to the account's item subvault. The actual hash stored in the item subvault will look something like H(hash, accountID) so as to prevent collisions. Moving this item hash to a produced note can work similarly to an asset balance, as described above.

Asset safety

Asset safety can be enforced through the following kernel functions (to be called in order): execute_tx_prologue, execute_tx_program, execute_tx_epilogue, each of which is documented below. For simplicity, only asset balances (i.e. fungible tokens) will be discussed below, but item hashes (i.e. non-fungible tokens) can be handled in a similar fashion.

Instead of iterating through every asset in the account vault (which may be prohibitively large), we instead track changes made to account and note vaults, and operate on those difference values. This still places an upper bound on the amount of assets that can be processed, but for those rare instances in which this is an issue, processing can be split among multiple smaller vaults. With this approach, there are no explicit checks on modifications made to the account vault during code execution, and no overhead in repeatedly modifying vault balances.

Prologue: execute_tx_prologue

We need to store a list of any assets that will be manipulated during transaction execution as well as their respective pre-execution amounts in a region of kernel memory. These values will be checked for consistency with the post-execution summed asset balances in the epilogue. As mentioned above, this bookkeeping needs to be done for both note and account vaults, and so we handle each case separately. When input notes are consumed, the whole content of their vault must be credited to the account, so all asset IDs in a note vault need to be added to this list. We also need to add the IDs of any asset that will be debited from the account (i.e. moved to an output note vault).

• Note vault iteration
  • For each input note, we iterate first over an advice set that is claimed to represent the inventory of that note vault. Recall that a note vault is described by a sequential hash. At each iteration step we do the following:
    • Read in the asset ID and amount from the advice set provider
    • Compute the next hash value in the sequence using these two values and the previous hash (or h_0 if at the start)
    • Increase the value in kernel memory corresponding to asset_i by amount_i
  • When finished iterating over an advice set, compute the final hash using the vault length, and assert that the final sequential hash value equals the note vault hash.
• Account vault iteration
  • We iterate over an advice set that claims to represent a subset of assets in the account vault, specifically those assets that will be increased by input note consumption and/or decreased by output note production during the execution phase. Recall that an account vault is described by a Merkle trie hash. At each step of the iteration we do the following:
    • Read in the asset ID and amount from the advice set provider
    • Read in a Merkle proof of the account vault balance from a separate advice set provider, and verify this proof
    • Increase the value in kernel memory corresponding to asset_i by amount_i

Execution: execute_tx_program

At the end of the execution, an advice set needs to be constructed containing an ordered sequence of Merkle update proofs for each asset's final new balance. Note that the proof path for the first update will be identical to the committed vault (pre-execution), except that the root hash of the path will differ (the leaf is not contained in the Merkle proof). For subsequent updates, two proof paths will need to be provided: one demonstrating a path to the original asset balance, and another to its updated balance.

Epilogue: execute_tx_epilogue

The epilogue needs to check the following:

• That all notes have been successfully consumed. This can be achieved by reading from a counter of consumed notes stored in kernel memory, and exposing this memory value as a public output using the advice tape.
• That each summed asset balance stored in kernel memory in the prologue equals the summed balance computed in the epilogue. This proceeds similarly to the prologue (by iterating over output notes and a subset of the account vault). The main difference being that we need to verify that the sequence of Merkle update proofs constructed during the execution program match the claimed vault asset balances (and that the final root of the account vault matches the claimed new root).

In all three of these kernel functions, we do not keep track of any asset balances in which the asset ID of a vault matches the account ID of the transaction context. This allows assets to be issued or destroyed when code is executed in the context of an asset account.

[bobbinth]

This is great! Thank you! A few preliminary thoughts:

Any regular account can act as an asset by issuing these notes

I wonder if this may complicate things. Specifically, in some cases we may need to do extra checks for asset-issuing accounts. For example, in the case of an account issuing NFTs, we need to ensure that the account can issue a given NFT only once. This could be done by recording all issued NFTs in a subtree of the account's storage and restricting access to this subtree only to kernel code.

It may be better to clearly separate accounts which could issue assets from regular accounts (if we do this, we should come up with a name for such accounts - e.g., something like "issuers" or "faucets"). This can be done by enforcing some rules around account IDs. One scheme that I was thinking about could work as follows:

1. Account ID for an account which can issue non-fungible assets must end with 32 zeros.
2. Account ID for an account which can issue fungible assets must end with 31 zeros followed by a single 1.

The reason for this scheme is that it would make it very easy to figure out which account is which. All we need to do is to use u32split instruction on the least significant element of the account ID and then check if the top element of the stack is $0$, $1$, or neither.

For example, the code to check if an account can issue NFTs could look like so:

# assuming [a3, a2, a1, a0, ...] is the current state of the stack, with a3 being the most significant
# limb of the account's ID

dup.3
u32split
drop
eq.0
if.true
  # the account can issue NFTs
else
  # the account cannot issue NFTs
end

The above check should take about 4 VM cycles.

To create accounts which can issue assets, users will need to grind the first 32 bits of the account ID - but that shouldn't be too difficult (probably would take under 20 mins on most laptops).

Assets reside in a vault, which is composed of a subvault for each asset type (fungible and non-fungible)

I like the idea of separating vaults into sub-vaults - especially, for account vaults. This will give us flexibility to potentially optimize differently for different sub-vaults as I think number of assets in fungible asset vault would usually be pretty small, while the number of assets in a NFT-vault could be quite larger.

All keys and values are represented by 256-bit words so as to maintain compatibility with EVM-based assets that may be bridged to the rollup.

I am not sure about this yet. Being able to store assets in a single word (4 elements) could have a number of nice advantages. For example, in some situations it may be desirable to pass around a self-contained asset instead of vault roots (e.g., a procedure which takes an asset as a parameter). In a case of fungible assets this would be asset ID + amount, which would mean that asset ID could be 24 bytes and amount 8 bytes. This does make bridging assets from Ethereum more complicated, but the trade-off might be worth it.

A couple of other advantages of fitting assets into a single word:

• Hashing/unhashing of note vaults would be about 2x more efficient (btw, we still need to figure out how to do this most efficiently as discussed in Memory pre-loading #336 )
• A single asset will neatly fit into a single memory address.

A scheme to store assets in a single words could work as follows:

• For fungible assets, we define asset ID as the first 3 elements of the issuing account's ID. Even though this means that asset ID is only 24 bytes, we should actually get close to 110 bits of collision resistance because of the grinding mentioned above. Then, the word representing the full asset would look like: [a3, a2, a1, balance]
• For non-fungible assets, we compute the asset word as:
  • First compute hash(item_hash, account_id) - same as you've described.
  • Then, set the least significant 32 bits of the second least significant element to all 0s. For example, if the hash from the step above is: [h3, h2, h1, h0], we set the least significant 32 bits of h1 to $0$. This can also be done pretty efficiently using u32split instruction.

The reason to set the least significant 32 bits of h1 to $0$ is to make differentiation between fungible and non-fungible assets very easy. For example, the script for checking asset type could look like so:

# assume the stack looks like [a3, a2, a1, a0] for some asset A

dup.2
u32split
drop
eq.0
if.true
  # this is a non-fungible asset
else
  # this is a fungible asset
end

It does mean that we'll need to impose an extra rule on fungible account IDs, to make sure they don't have these bits set to $0$ - but that would be easy to do.

As in the case with fungible assets, the assets in the above scheme still have ~110 bit collision resistance (because we discard only 32 bits out of 256).

[maxgillett]

For example, in the case of an account issuing NFTs, we need to ensure that the account can issue a given NFT only once. This could be done by recording all issued NFTs in a subtree of the account's storage and restricting access to this subtree only to kernel code.

I like the idea, but I wonder if it should be the responsibility of the NFT-issuing account to ensure this, and just be specified in its account code. I would make the argument that users of an asset will need to inspect public account code anyway (or trust auditors), and that NFT-issuing accounts can just use standardized code that implements this functionality. We don't provide a similar protection to fungible assets (i.e. that an infinite amount of tokens can't be minted), so I'm hesitant to give NFT some special protections at the cost of additional complexity. Are there other motivations aside from this one to distinguish between asset and regular accounts? I think one potentially interesting effect of not making this distinction is that it allows native "social token" support, where a user account has the ability to issue things like IOUs or their own currency, without having to create a separate asset-issuing account whose ownership then needs to be established.

I am not sure about this yet. Being able to store assets in a single word (4 elements) could have a number of nice advantages. For example, in some situations it may be desirable to pass around a self-contained asset instead of vault roots (e.g., a procedure which takes an asset as a parameter). In a case of fungible assets this would be asset ID + amount, which would mean that asset ID could be 24 bytes and amount 8 bytes. This does make bridging assets from Ethereum more complicated, but the trade-off might be worth it.

I do like this scheme, but I'd be more comfortable if we have a concrete idea of how we then handle bridged tokens that can't fit into 8 bytes (e.g. an ETH balance above ~18.5, which has 18 decimal places). Do we just throw out the least significant digits and have some dust accumulate in the bridge? That seems somewhat clunky to me, but maybe there is a better solution.

[bobbinth]

We don't provide a similar protection to fungible assets (i.e. that an infinite amount of tokens can't be minted),

Actually, I'm wondering if we should put in a safeguard here as well to make sure that the total issued supply does not exceed $2^{63}$. This would save us from needing to check for overflow everywhere else and would make situations where a note can't be processed because processing it would result in an overflow impossible.

That seems somewhat clunky to me, but maybe there is a better solution.

Another potential option is not to accept any transfer with an amount which non-zero values in the 10 least significant decimal places. Though, I'm not sure how costly this check would be.

[bobbinth]

To summarize main open question:

1. Should all accounts be able to issue assets or should this functionality be restricted to some (still permissionless) set of accounts?
   a. A sub-question: should the same account be able to issue both fungible and non-fungible assets?
2. Should we perform some safety checks at the VM when minting/burning assets? The two checks that we discussed so far are:
   a. For non-fungible assets: the same asset cannot be minted more than once.
   b. For fungible assets: total supply cannot exceed $2^{63}$.
3. For fungible assets, should we represent the amounts as 256-bit or 64-bit integers?

[bobbinth]

I've been thinking a bit about what procedures we might want to expose to the user to work with vaults and assets, and below is a rough sketch.

Form the account context, we might want to do the following (these procedures could live in miden::vault namespace):

• add_asset(Asset) - adds the specified asset (fungible or non-fungible) to the account's vault.
• get_balance(AssetID) -> Amount - retrieves balance of a fungible asset based on its ID. If the asset is not present in the vault, returns $0$.
• remove_balance(AssetID, Amount) -> Asset - removes the specified amount of the fungible asset based on its ID, and leaves the removed asset on the stack. If the vault does not contain the requested amount of the specified asset, the procedure fails.
• has_item(Asset) -> Bool - returns $1$ if the non-fungible asset is present in the vault, and $0$ otherwise.
• remove_item(Asset) -> Asset - removes the specified non-fungible asset from the vault, leaving the asset on the stack.

We probably also need a way to manipulate individual assets as well as note vault contents. I actually think that we should probably use a different name for note vaults because now they are structurally different from account vaults. I've used Crate below, but open to other suggestions. The below procedures could probably go into miden::assets namespace:

• pack(mem_ptr, num_assets) -> Crate - computes a sequential hash of assets located at the specified memory address, and leaves the hash on the stack.
• unpack(Crate, mem_ptr) -> u32 - "unhashes" the specified asset crate into memory starting at the specified address and leaving the number of assets on the stack.
• is_fungible(Asset) -> Bool - returns $1$ if the asset on the top of the stack is fungible, and $0$ otherwise.
• is_nonfungible(Asset) -> Bool - returns $1$ if the asset on the top of the stack is non-fungible, and $0$ otherwise.
• get_item_contents(Asset) -> (AssetID, Hash) returns contents of a non-fungible asset - i.e., asset ID and item hash.

I'm probably missing quite a few, but it's a start.