On chain account storage formats

[bobbinth]

Just as for notes, we need to define how accounts are going to be recorded on chain. With accounts we have two cases:

• Only account hash is recorded on-chain.
• Full account state is recorded on-chain.

Full state of an account consists of the following components:

• Account ID - I'm going to assume that we go with 64-bit account IDs described in #8..
• Vault - which can probably be recorded simply as a list of assets.
• Storage - which will probably need to be recorded as a list of key-value pairs. Also, it might make sense to record additional data for each key-value pair. For example, if a key itself contains a list of values, we probably should record these values as well.
  • This actually raises a question about potentially encoding leaf values differently based on the underlying data type.
• Code - which will be recorded as a MAST root + Miden assembly module which when compiled resolves to the specified MAST root.
• Nonce - which is a single 64-bit value.

Similar to the the approach taken with notes, we can use account ID itself to specify whether just the hash, or the full state should be recorded on chain. This is already discussed in #13, but to be more specific, we need account IDs to contain the following info:

• Account type - I'm thinking we can go with 4 types and in this case we'd need 2 bits to encode this info. The types could be:
  • 00 - regular account with updatable code.
  • 01 - regular account with immutable code.
  • 10 - fungible faucet, the code is immutable.
  • 11 - no-fungible faucet, the code is immutable.
• Storage format, and for this we need just a single bit. For example:
  • 0- full details are stored on chain.
  • 1 - only account hash is stored on chain.

Thus, we can use 3 most significant bits of the account ID to encode all relevant info. One question is whether these should be most or least significant bits. For example, most significant bits define the path in the account DB tree - so, there might be some implications to how the accounts will be distributed in the SMT - but ultimately, it probably doesn't matter too much.

With 3 bits taken up by meaningful info, we still have 61 bits for the actual account ID, which I think should be plenty.

[hackaugusto]

Having the account and storage types as part of the account ID would imply that this can not be changed after an account is created. Wouldn't it be better to have these defined externally?

The storage format could be implicitly defined, i.e. if there is no on-chain data for the given account, it is by definition off-chain. The faucet could be implicitly define by the account's code. I think immutability is different and should be part of the account ID. Also, IIUC state prunning is possible for the account and note DBs, so IMO the account ID is not a good fit to determine the account storage type.

Question: If we do have account prunning, what is the incentive for an operator to keep the state around? Will there be a fee model to incentivize keeping account's state on-chain? IOW, what determines when an account is removed from on-chain?

Idea: An user could generate a few notes in advance, each claimable after a given block in the future, and only by the block's operator. And to consume the note the operator would have to provide a proof of state. (I haven't thought about how to implement this, just dropping the idea on how to pay fees to maintain an account on-chain).

Observations: 1. If we do have state pruning, it is very important to have a mechanism to backup an account's state 2. Also, I would say full on-chain state is a special case of stateless state.

[bobbinth]

The storage format could be implicitly defined, i.e. if there is no on-chain data for the given account, it is by definition off-chain.

I'm not sure it'll work in a decentralized setting. When an operator gats a block from another operator they should be able to easily tell whether they need to get full account details or just account hash for a given account. Otherwise, an operator could withhold data for accounts which are supposed to be stored on chain - and other operators would not be able to tell.

The faucet could be implicitly define by the account's code.

This will also not work as we need to have a very easy way to identify if an account is a faucet or not. This is needed, for example, inside a transaction kernel to figure out if an account can mint assets.

Having the account and storage types as part of the account ID would imply that this can not be changed after an account is created. Wouldn't it be better to have these defined externally?

An alternative could be to have a separate filed for account settings - but I think this has some undesirable properties:

• This field needs to be available even for accounts where we store only the hash. This will complicate account hashing procedure somewhat and also will make bookkeeping a bit more difficult.
• We'd need to spend a full field element even though we just need ~3 bits. For accounts with on-chain storage, the increase is probably not significant. But when we store hash only, this would imply 20% increase in storage requirements.

I'm actually not sure if updating either the type or the storage format is desirable. For example, I don't think it should be possible to change a faucet into a regular account or vise versa. Also, changing immutable code account into a mutable one should not be allowed. Maybe changing storage format could be an interesting feature, but I'm hesitant to add this much extra complexity for this use case alone.

Question: If we do have account pruning, what is the incentive for an operator to keep the state around? Will there be a fee model to incentivize keeping account's state on-chain? IOW, what determines when an account is removed from on-chain?

My current thinking is that there is not special incentive model - but there is still an incentive. Specifically, if an operator prunes an account data for an on-chain account, they won't be able to execute transactions against this account - so, they'll miss out on potential transaction fees. This should naturally incentivize pruning of accounts which have become stale - but when to do that would be up to specific operators.

Observations: 1. If we do have state pruning, it is very important to have a mechanism to backup an account's state 2. Also, I would say full on-chain state is a special case of stateless state.

Agreed! Though I think this mechanism is not a part of the protocol (and there could actually be many such mechanisms - ranging from storing it on Google drive to storing it in a blockchain-based data availability system).

[hackaugusto]

When an operator gats a block from another operator they should be able to easily tell whether they need to get full account details or just account hash for a given account. Otherwise, an operator could withhold data for accounts which are supposed to be stored on chain - and other operators would not be able to tell.

AFAIU the prefix doesn't fix this problem either. The prefix does not guarantee the data is available, because of state pruning. Unless I'm missing something, it is possible for the following to happen:

1. account is created with on-chain storage
2. enough time passes by that the operator prunes the state
3. user has state locally and execute a transaction locally
4. operator adds the transaction to a block

For the block created at 4, the lack of a state is not because the data is being withheld, it just doesn't exist.

I suppose we can fix this by requiring the user to provide the state to the operator, even though the transaction was executed locally. But then we have a problem that there is no guarantee of when the data is pruned, then we are in a situation that it may be better to just provide the account data together with every transaction. Or am I missing something?

[hackaugusto]

This will also not work as we need to have a very easy way to identify if an account is a faucet or not. This is needed, for example, inside a transaction kernel to figure out if an account can mint assets.

I don't follow. The change is from account.id.starts_with(faucet_prefix) to account.code.contains(faucet_api), how much more expensive would account.contains.contains be? I suppose ATM this is supposed to be a root of a MAST, which would need some merkle proof of sorts. Maybe we should instead have it be a public list of supported APIs, I guess this can be implemented with 1. a list of the supported APIs, as a hash(api_definition), and then the contains check should be trivial, followed by a commitment to some implementation of the given API, in the form of a merkelized key-value tree.

[bobbinth]

I don't follow. The change is from account.id.starts_with(faucet_prefix) to account.code.contains(faucet_api), how much more expensive would account.contains.contains be?

This could take 100+ cycles because we need to verify Merkle inclusion proofs. I'm trying to make sure that the check can be done in less than 5 cycles.

[bobbinth]

• account is created with on-chain storage
• enough time passes by that the operator prunes the state
• user has state locally and execute a transaction locally
• operator adds the transaction to a block

I think in this scenario the user would include all the data required for an operator who has kept the account state to make necessary updates (i.e., a new item added to storage, or an asset removed from vault).

The key question here is how can we ensure that the user has provided all the required data. For an operator who has maintained the full account state, verifying that all required data is included is trivial (they just update their local data and verify that hashes match). But for operators who pruned the data this verification is no longer possible.

I think this is an independent and more general thing to solve: can we ensure that a block contains all required detail for accounts required to update on-chain states of accounts.

I do want to say that this is an issue only when: (a) there is a decentralized set of operators, and (b) some operators prune data which other operators don't.