On chain note storage formats

[bobbinth]

As implemented in #5, notes consist of 3 components:

• note script
• note vault
• serial number

We need to know all details of these components to consume a note in a transaction, but how the notes are actually recorded on chain could be quite different. Some options are discussed below.

Basic formats

Note hash only

This is by far the most compact way to represent a note on-chain. No information about the script, the vault, or the serial number is recorded - only the note's hash goes on chain. To consume this note, the recipient will need to know all the details, which will probably need to be communicated off-chain. A note stored in this way can be consumed in:

• a local transaction - i.e., assuming the user has all the details, they can consume the note and generate a proof.
• a network transaction - in this case, the note's details would need to be included in the transaction, and then the executing node would verify that all the details match the note's hash. This is similar to P2SH transactions in Bitcoin.

Full note details

The opposite of the above approach is to store all note details on chain. This could take up quite a bit of space, especially if the script is complex (the script will be recorded in the serialized Miden assembly format). However, the upside is that no off-chain communication is needed - anyone observing the chain will be able to process this note.

Potential additional formats

It may be desirable to define some additional formats which are more compact than recording all note details on chain, but at the same time require no off-chain communication. Some examples are below.

Simple transfer

If a note just transfers assets to a single account, we can record the following components:

• Serial number: $32$ bytes.
• All assets in the note's vault: $32 \cdot n$ bytes where $n$ is the number of assets.
• Recipient account ID: $21$ bytes.

Seeing this type of a note, the recipient will assume that a standard script is executed. The script could be something like:

begin
  assert(account.get_id() == <recipient account id>)
  for a in note.assets
    account.receive_asset(a)
  end
end

The MAST of this script can be constructed based on the account ID recorded on chain. This format is somewhat similar to P2PKH in Bitcoin.

Simple transfer with recall

We can make transfers safer by adding a recall condition. That is, if I sent assets to a non-existent address, I could recall the note after some time. Such a note can be recorded as follows:

• Serial number: $32$ bytes.
• All assets in the note's vault: $32 \cdot n$ bytes where $n$ is the number of assets.
• Recipient account ID: $21$ bytes.
• Sender account ID: $21$ bytes.
• Recall block height: $8$ bytes.

A standard script for this note type could look like:

begin
  let block_height = chain.get_block_height()
  if block_height > recall_block_height
    assert(account.get_id() == <recipient account id> || account.get_id() == <sender account id>)
  else
    assert(account.get_id() == <recipient account id>)
  end
  
  for a in note.assets
    account.receive_asset(a)
  end
end

Encoding note type

Instead of adding a new field to identify the type of a note, we could just grind on the serial number until the note hash has a certain structure. For example, we could encode the type in the first 6 or 8 bits of the note hash. This would give us between 64 and 256 available types, and the time needed to grind 6 or 8 bits is negligible.

Open questions

• Do we actually need additional note formats? Yes, the scripts in the above examples are not huge - they are probably under 100 bytes each (though I might be wrong). And if we are saving only a few dozen bytes, is the extra complexity worth it?
• If we do want to have additional formats, what are the examples of scripts that we'd want to standardize.
• The above discussion didn't cover how a given note would be discoverable by the recipient. Naively, we can assume that someone scans all newly created notes to check if any of these notes are sent to them. But this is not practical and we need a better mechanism for specifying note recipients. The question is whether this mechanism would somehow affect the design of note formats.

[bobbinth]

The more I think about this, the more I lean toward not supporting additional formats. The reasoning for this is two-fold:

1. The savings over scripts are probably not that significant. I tried to put together a full script for "simple transfer with recall". I didn't get it all flashed out, but I believe we should be able to have a script for this which would serialize into 100 or 150 bytes. Thus, overall savings would be somewhere between 10% and 50%. This is not huge in my opinion.
2. There could be quite a few scripts which could make sense to standardize, but i'm a bit hesitant about doing this at the protocol level because (a) this could result in a large number of scripts being enshrined, (b) people will constantly come up with better ways of doing things, and thus, some of the enshrined scripts may become abandoned over time.

[frisitano]

Regarding the run.{0x123456789} pattern of using well-know scripts, could we use MAST's from public accounts as a source for this. E.g. When a new account is created on the backend in the account db table we store only the MAST hash with the account:

pub struct Account {
    id: AccountId,
    vault: AccountVault,
    storage: AccountStorage,
    code_hash: CodeHash,
    nonce: Felt,
}

We then have a separate Code db table which maps CodeHash to CodeMAST. This also reduces unnecessary duplication of code in storage for different accounts with the same code. Then if a user executing a local transaction that requires a particular CodeMAST they can query a node asking for the CodeMAST for a particular CodeHash. As long as one public account has been created with this CodeMAST then it will be available in the db and easily retrievable as it's key is the CodeHash. Similarly when a block producer needs to execute an on-chain transaction they first look up the account, then look up the CodeMAST associated with the accounts CodeHash and for any additional run.{0x123456789} statements they look them up in the Code table. This also provides a permission-less way of providing common MAST's that anyone can use. To take this further and prevent DOS attacks from tx's requesting on-chain transactions with run.{0x123456789} commands specifying MAST's which don't exist we would need to maintain a Code SMT. This way in the tx kernel we could prove that the required MAST is not available to the block producer and therefore the tx can not be completed but they will still be charged. I think this Code db / SMT could form the basis for on-chain library / code sharing.

[bobbinth]

Yes, I think something like this would be useful, but I think we need to look how this would work in different contexts. Specifically:

• I'm not sure this is really needed for off-chain accounts, as the user would be responsible for maintaining all the code associated with the account locally.
• This could help a lot for public accounts, where instead of storing the full program on-chain, we could store parts of the program which internally make references to other on-chain account code. We'll need to think through all the details here because we don't want to rely on accounts with updatable code here.
• This could also help block producers to compile program. Here, we could have multiple heuristics of how block producers build up a "cache" or pre-compiled programs.

In general, the structure for managing scripts/code is still an open question in my mind.

[frisitano]

Yes, I think something like this would be useful, but I think we need to look how this would work in different contexts. Specifically:

• I'm not sure this is really needed for off-chain accounts, as the user would be responsible for maintaining all the code associated with the account locally.

I agree, it's probably not needed for off-chain accounts. My statement was more referring to on-chain accounts with transactions being executed / proven off-chain. Users would only need to take their keys with them (hardware wallets) everything else could be sourced from the chain at the time of execution / proving.

• This could help a lot for public accounts, where instead of storing the full program on-chain, we could store parts of the program which internally make references to other on-chain account code. We'll need to think through all the details here because we don't want to rely on accounts with updatable code here.

Yeah good point. If we introduce the Code db then maybe we could create a transaction type that is exclusively concerned with inserting immutable code in the db. Or if we don't want to create a new db then create an account type which has immutable code.

[hackaugusto]

We then have a separate Code db table which maps CodeHash to CodeMAST

I like the idea, I would also consider having it as a general key map, it could be used to store code for a given hash, but also a public key for an address, etc.

[bobbinth]

This kind of already exists in the Assembler (e.g., here) - so, we just need to have a way to store and provide this info to the assembler.

[bobbinth]

A few thoughts about the 3rd open question: how would someone discover a note which was sent to them (or to a specific account).

As described in the original post, the naive solution would be to examine each newly created note and see if its script could be executed against a specific account. For high-throughput systems this approach is completely impractical. For one, this can never be done on a smartphone or even a laptop. But also, it required $m \cdot n$ work, where $n$ is the number of notes and $m$ is the number of accounts.

There are actually two broad use cases for why we want note targets to be easily discoverable:

• For user-to-user interaction. For example, if user A creates a note for user B to consume, we'd want user B to discover this note on a low-end machine and without sacrificing much privacy.
• For network transactions. Here, we'd want the operators to easily identify which notes are intended to be processed by them, and also to figure out how they should process these notes (i.e., in a context of which account).

User-to-user interactions

User-to-user interactions break down further into two categories:

1. There is a separate channel between the users - i.e., they can communicate off-chain. In this case the recipient could engage in an interactive protocol with the sender and by the end of this interaction they would know the exact hash of the note that the sender is going to put on chain.
2. There is no separate channel between the users - i.e., the sender can get some pre-determined information from the recipient (e.g., by scanning a QR code) but they cannot make any custom queries to the recipient and the recipient cannot provide any additional info to the sender.

As mentioned above, we assume that the recipient is not powerful enough to scan all incoming notes, and therefore, they must delegate this scanning to someone else (i.e., a full node). If the recipient knows the exact hash of the note, they could make periodic requests to a full node to see if a note with this hash has been created. Or, they could register this hash with the full node, and once the full node sees a note with this hash, they could forward this note to the recipient.

From the full node's perspective, the work would be pretty simple: check if a note with a given hash exists (a full node will probably maintain such an index anyway) and send the note to the recipient. However, this approach is undesirable for two reasons:

1. The recipient needs to update the full node for every note they are interested in.
2. The full node learns exactly which notes are intended for a given client - thus, limiting privacy.

The second issue could be mitigated by using bloom filters, but I think there is a better solution which addresses both issues. Specifically, the sender could craft a note in such a way that the note's hash has a specific prefix. Then, the recipient would register this prefix with a full node, and any time the full node sees a note with a given prefix, they would forward this note to the recipient.

Let's say the recipient sets the prefix to be 10 bits. Then, they would get roughly every 1000th note. For a 16-bit prefix, they would get roughly every 65000th note. The smaller the prefix, the more "false positives" (i.e., notes which were not actually intended for the recipient) will be sent to the recipient - but that's the price to pay for flexibility and privacy.

This prefix-based approach can be used for the second category as well (i.e., no separate channel between users). For example, a QR code may contain the desired prefix. Then the sender would get this info and use it to construct the note for recipient.

Notes for network transactions

As mentioned above, with notes for network transactions, we want to achieve two things:

1. Easily identify if a note is intended for a network transaction or not.
2. Figure out how to process the note as easily as possible.

The first part is easily solved by slightly modifying the note format bits described in #7 (reply in thread). Specifically, we could define the values which these bits encode like this:

• 00 - hash-only format.
• 01 - reserved for future use.
• 10 - hash + details format, note intended for local execution.
• 11 - hash + details format, note intended for network execution.

Now, by examining the first two bits of a note, a block producer will be able to tell whether they should try to process the note themselves or not.

To figure out how the note is to be processed, we could also apply the same note prefix idea as before, but add a bit more structure to it. The exact design probably deserves a much more thorough analysis, but we it could look something like this:

• If the prefix is 111, the following $n$ bits (e.g., $n$ could be 13, 14, 16 or something like that) identify the prefix of the account for which the note is intended.
• If the prefix is 110, the note is not indented for any specific account and can be consumed by any account which satisfies some interface. Then the following $n$ bits could be a sort of a "tag" which would indicate the specific use case (e.g., a note is intended to be a bid in a DEX).

Computing the prefix

One thing I didn't describe above is how does the sender ensure that a note's hash has the required prefix. The methodology here is pretty simple: grind on the note's serial number (i.e., try many different serial numbers) until the hash has the required structure. Since computing a note's hash requires 4 invocations of the hash function, the average complexity of finding the right $n$ bit prefix is $2^{n+2}$. So, to find the right 16-bit prefix, we'd need to execute the hash function $2^{18}$ times, on average.

This is actually not so bad. Assuming we use RPO as a hash, on a laptop this can be done in a fraction of a second. I haven't measured this on a smart phone, but my guess is that it should take slightly less than a second on a modern mid-range smart phone. Of course, if we use something more efficient than RPO, then this can be done faster.

Thus, for practical settings, we could have something like this:

• Hash-only format: 00 + 14-bit user-defined tag.
• Detailed note for local execution: 10 + 14-bit user-defined tag.
• Detailed note for network execution:
  • Against a specific account: 111 + first 13 bits of the target account's ID.
  • Against any account: 110 + 13-bit tag identifying a use case.

It is important to point out that at the protocol level we define meaning only for the first 2 bits. All other bits are defined "by convention". There is no reason, for example, why a specific user would not use a smaller (or a bigger) tag. For example, I can set my tag at 10 bits (rather than 14), but in this case, I would have to process every 1000th note instead of every 16000th note.

Conversely, I could set my tag to 16-bits, and then I would need to process only every 65000th note, but then senders might have to spend a bit more time finding the right prefix (which may be fine in the future as hash functions or hardware becomes faster).

[hackaugusto]

I have two questions:

• I assumed the sequence number was being used to order a user's transactions. So that a sequencer would know how to order them, but it form this description it seems value is more of a nonce, like in a POW, and instead of having leading zeros we have some special data format. In that case, how are user transactions ordered?
• I'm not sure if I understood what we gain with this approach, is the goal here to hide the recipient of a note? can't we just do this without the PoW? Something like, zeroing the lower bits of a recipient. And then if it is a network transaction, just leaving the address full so that operator knows the exact target account?

[hackaugusto]

The full node learns exactly which notes are intended for a given client - thus, limiting privacy.

Is this important? For users that care about privacy the best they can do is use a out-of-band communication channel. Isn't that good enough?

Edit: just to clarify, what I'm asking is: Do we really want to support the use case that users want privacy and don't have out-of-band communication?

[bobbinth]

I assumed the sequence number was being used to order a user's transactions. So that a sequencer would know how to order them, but it form this description it seems value is more of a nonce, like in a POW, and instead of having leading zeros we have some special data format. In that case, how are user transactions ordered?

Do you mean a serial number (rather than a sequence number)? If so, yes - its purpose is not ordering. It actually has dual use (at least for now):

• Make the note hash and note nullifier un-linkable. So, serial number is the entropy which is used to make sure we can't guess which not hash and nullifier belong to the same note.
• As a PoW nonce to "shape" note hash to simplify note discovery for nodes/users.

I'm not sure if I understood what we gain with this approach, is the goal here to hide the recipient of a note? can't we just do this without the PoW?

Without PoW we'd need to introduce an additional element (like a note tag or something like that). It is totally doable and actually may have some advantages over PoW approach. The main advantage of the PoW approach is that when only note hashes are stored on chain, we don't need any additional data to help user figure out which notes are addressed to them.

Is this important? For users that care about privacy the best they can do is use a out-of-band communication channel. Isn't that good enough?

Edit: just to clarify, what I'm asking is: Do we really want to support the use case that users want privacy and don't have out-of-band communication?

I think this is actually unrelated to out-of-band channels. Basically, what we trying to do is make sure the operator doesn't learn which users are interested in which notes (i.e., they can't say this IP address was interested in notes X, Y, Z). Instead, they can only say that this IP address is interested in prefix A which could include many other notes. It does reduce anonymity somewhat, but if the prefix is short enough (e.g., under 16 bits) - I think it is still pretty good.

[frisitano]

I think including a tag in notes will simplify the protocol significantly, especially for network transactions. I'm not sure how grinding will work in practice for on-chain smart contract protocols. Lets consider the case of an on-chain dex. Something equivalent to uniswap. Lets assume the dex is processing 300 input notes (swaps) in a block and has to generate 300 output notes intended for 300 different accounts. Will the dex contract have to grind 300 serial numbers to produce the correct note hashes? Will this be done as part of the on-chain contract, provided as input? I think the grinding method makes sense in many cases but having an additional tag for cases when less privacy is required would make sense as well.

[bobbinth]

Will the dex contract have to grind 300 serial numbers to produce the correct note hashes?

No - grinding would need to be done by the users - but you are right, in this case it won't quite work. The issue is that note hash depends on the vault hash, which, in turn, depends on the assets included in the note. This works fine when you know the exact assets to be included in the note - but that's not the case with something like uniswap (there, the exact amount of the returned asset is not known ahead of time). However, something like an order-book exchange may not have a similar problem.

I don't mind adding some meta data to a note - and a tag could be included in such metadata (anther thing which could be included is note sender as described in #23). But it does complicate things a bit - or at least requires us thinking through a bit more complexity.

For example, I don't think this metadata should be a part of note hash (although, it would be good to spell out all pros and cons). Thus, each note will now be defined by a tuple (note_hash, note_metadata). This means when we store a note in the Notes DB, we'll need to do an extra round of hashing. Also, the output of transaction kernel won't be just a sequential hash of created notes, but a sequential hash of these tuples above.

On the other hand having this extra metadata could simplify other things (i.e., removing grinding is a good thing) - so, definitely something to explore.

[hackaugusto]

Updates

The discussion has been split up into multiple issues, for reference they are:

• Account IDs length may change from the 21 bytes mentioned
  • Consider reducing account ID size to 16 bytes or smaller #8
• The format of a note may change to include inputs, so the MAST script would be ready, and won't need to be construct:
  • Add script inputs to note object #9
• The content of the default scripts is being outlined:
  • Write Miden assembly for P2ID and P2IDR scripts #12

Proposal

Here is my summary of the discussion:

Types of execution:

• local: transaction and proof done locally
• network: transaction and proof done by an operator
  • stateful: the note data is available on-chain
  • stateless: the note data has been pruned, or was private, so it must be provided by the user

Two types of transactions:

• private: requires local execution, proof and note hash are published
• public: local or network execution, proof and complete note data are published

Here is how the execution and transaction types related to each other and the note format:

	local	network (stateful/stateless)	on-chain note format
private	x		hash only
public	x	x	complete, pruned

The serial_number is used to:

• Prevent linking of the note with its nullifier. Required for privacy, so that Bob can consume Alice's note and that would be unknown to the public.
• The serial_number is akin to a nonce, each note has its own unique value. This number is not sequential and can be used to do PoW. The goal of the PoW is to:
  • Determine the hash(note) prefix, the first bits are used to:
    • determine the note type to the network
    • provide a tag, used by the target of a note to find it
  • Prevent spamming of an operator

The hash(note) prefix bits have the following function:

• flag the type of note (hash only or complete data)
• flag if the note is for network execution

[hackaugusto]

I tried to summarize the prefix bits too, but their usage has been inconsistent. The gist is that:

• one bit determines the type of note (hash only or complete)
• another bit determines if the note is to be executed by the network
• some other undefined amount of bits is used as a tag to filter note broadcasting

[bobbinth]

This is larger accurate. A coupe of clarifications.

Two types of transactions:

• private: requires local execution, proof and note hash are published
• public: local or network execution, proof and complete note data are published

I'd also add a 3rd type: stateless transactions. This is where only note hashes are published but the execution is done by the network. In this case, the user will need to provide all note details together with transaction data so that the operator can execute them.

I tried to summarize the prefix bits too, but their usage has been inconsistent. The gist is that:

• one bit determines the type of note (hash only or complete)
• another bit determines if the note is to be executed by the network
• some other undefined amount of bits is used as a tag to filter note broadcasting

This is correct, but I'd say at the protocol level only 2 bits have relevance. One of the tables in the comments describes the scheme, but pasting it here as well:

• 00 - only note hash is stored on chain. Such notes can still be included in transactions executed by the network, but the user will need to prepare such transactions so that they contain all relevant details.
• 01 - reserved for future use.
• 10 - full note details are stored on chain, note intended for local execution. Such notes can also be executed by the network, but the user will be responsible for preparing the transactions (i.e., operators will not pro-actively try to create transactions to consume such notes).
• 11 - full note details are stored on chain, note intended for network execution.

Actually, it might make sense to re-shuffle the bits like so:

• 00 - full detail on chain, intended for network execution.
• 01 - full detail on chain, intended for local execution.
• 10 - only hash is on chain.
• 11 - reserved for future use.

[hackaugusto]

I'd also add a 3rd type: stateless transactions. This is where only note hashes are published but the execution is done by the network.

This can also be because of state pruning of notes, correct? So it would either be 1. a note that was initially intended for private execution, that is being leaked by the recipient, or 2. a note that has been pruned.

But this does't add a new type of on-chain note representation, only a new execution type, correct? It just means that either there was only the note hash, or the complete note state has been pruned and now only the note hash if available.

I have updated the summary with this execution type.