NoteTag requirements and simplification

[PhilippGackstatter]

Note tags might be a bit more complicated than they need to be and @bobbinth mentioned an alternative approach:

Specifically, having 4 different variants seems a bit arbitrary. And I wonder if we could get rid of the 2-bit prefixes somehow. For this, we'd need to change account ID encoding a bit (which we went back and forth on a couple of times) - so, not sure it'll be worth it, but one potential scheme could be:

There are no 2 bit prefixes and instead the value of the tag "organically" defines its variant:

• For network account targets, the value of the tag would be just the 32 most significant bits of the account ID.
• For local account targets, the value of the tag would be the 14 (or w/e) most significant bits of the account ID.

For this to work, we could impose the following rules on the account ID encoding:

• Account ID always starts with 1. So, if the tag starts with 0, we know it is not directed to an account.
• The first byte of the account ID contains either network bit or account type bits. This way, looking a the first byte, we can tell if the note is directed to the network account or not.

Taking a step back, one open questions for me is whether there is an exhaustive set of requirements that the note tag should fulfill. Is it basically this?

• Identify what account a note is targeted at, if any.
  • E.g. it is targeted at a network account, so the node can build network transactions for it.
  • E.g. it is targeted at a private/public account, so a client of a user account can find a P2ID note intended for that account.
• Identify what use case a note is for, if any.
  • E.g. it is a SWAP note targeted at whoever wants to consume it. This helps clients of the network to find notes for such specific "use cases".

If that's the two main uses, then I think this simplification should work well. Note tags starting with 1 are directed for accounts and those starting with 0 are use cases. The main questions for me are around the use case tags.

Use Cases

I wonder if having a use case ID is necessary. A use case tag for a SWAP note could also be [SWAP_SCRIPT_ROOT | offered_asset_faucet_id[..16] | requested_asset_faucet_id[..16]]. Basically, all use cases tags would be of size 32 + 4 bytes, but the NoteTag for a use case note would only contain the latter 4 bytes. So the main change would be that for use cases, clients would request the script root + the note tag, while for account targets they would request just the note tag.

Network Use Case

Currently we also have NoteTag::NetworkUseCase, which identifies a use case note that should be consumed by network accounts. If network accounts expose the set of script roots they are willing to consume and with the above use-case changes, is that a sufficient replacement? Overall, the script root is a better use-case identifier than a note tag anyway, because a script root commits to the actual code while a tag could be (maliciously) crafted as well.

If it's not sufficient, then network accounts would probably also have to expose a set of note tag use cases they are willing to consume, otherwise I'm not sure how a node would figure out which use case notes to put into a network transaction. A good example for this is a matcher account (deployed as a network account) for SWAP(P) notes as mentioned in #1333. Though such a matcher account is probably interested in all SWAP(P) notes, and not just a specific POL/ETH pair.

---

One additional thing to discuss in this context is the trade-off between the note tag and the aux value in the note metadata. For instance, we could swap the representations of the tag and the aux value, i.e. make the note tag from a Felt and reduce the aux to a u32.
That would allow having the NoteTag::NetworkAccount contain a full account ID prefix which would, at least currently, uniquely identify an account. This would eliminate any ambiguity in the node when figuring out which account is targeted by a certain network note. Something that is not clear to me is what the aux value should be used for and what size is sufficient.
I'm a bit hesitant about this though because I don't necessarily want us to further commit to "account ID prefixes are unique" as we could lift this restriction if we were to refactor assets. We could potentially come back to this after we've discussed programmable assets.

[bobbinth]

• Identify what account a note is targeted at, if any.
  • E.g. it is targeted at a network account, so the node can build network transactions for it.
  • E.g. it is targeted at a private/public account, so a client of a user account can find a P2ID note intended for that account.
• Identify what use case a note is for, if any.
  • E.g. it is a SWAP note targeted at whoever wants to consume it. This helps clients of the network to find notes for such specific "use cases".

That's basically it.

Network Use Case

Currently we also have NoteTag::NetworkUseCase, which identifies a use case note that should be consumed by network accounts. If network accounts expose the set of script roots they are willing to consume and with the above use-case changes, is that a sufficient replacement? Overall, the script root is a better use-case identifier than a note tag anyway, because a script root commits to the actual code while a tag could be (maliciously) crafted as well.

I agree with this: for network notes, script root is a better use case identifier. We just need to know that a given public note is a network note - but for this a single bit should be sufficient. Beyond this, the tag may not be really necessary.

I wonder if having a use case ID is necessary. A use case tag for a SWAP note could also be [SWAP_SCRIPT_ROOT | offered_asset_faucet_id[..16] | requested_asset_faucet_id[..16]]. Basically, all use cases tags would be of size 32 + 4 bytes, but the NoteTag for a use case note would only contain the latter 4 bytes. So the main change would be that for use cases, clients would request the script root + the note tag, while for account targets they would request just the note tag.

One challenge with using the tag for non-network notes is that we want to minimize node complexity. So, there are only 2 ways users can query notes:

• By sender ID - this is useful when querying notes that we've issued.
• By note tag - this is useful for querying notes that were sent to us.

We could add ability to query by script as well, but that means the node will need to index notes by script roots too, and the RPC API will need to support it.

Moreover, script roots are available only for public notes. Though, there is argument to be made that retrieving private notes by use case tag is not super useful (unless we already know note details).

One additional thing to discuss in this context is the trade-off between the note tag and the aux value in the note metadata. For instance, we could swap the representations of the tag and the aux value, i.e. make the note tag from a Felt and reduce the aux to a u32.

Maybe we should re-think the aux value as well. First, it is only meaningful in the context of private notes (for public notes, all relevant info can be in note inputs). So, public and network notes don't really need the aux field (maybe for network notes we could combine tag + aux into a single field).

For private notes, having just 64 bits for the aux field may be pretty limiting. One way to test this is to try to implement the partial swap note and see if we can really make meaningful use of the aux field - or if we should make the amount of attached metadata flexible somehow.

[bobbinth]

Currently, the primary use is to get note authentication paths without revealing too much info about the notes we are interested in. So, the scenario is:

• Alice creates a private note and sends it via a side channel to Bob.
• At the same time, Alice submits a transaction to the network.
• Bob uses note's tag to periodically sync with the network, and once he sees the note's authentication path, he stores it locally to be able to consume the note in the future.

In the future, we'll also use the tag for encrypted notes. For these, there won't be any channel to communicate any note data beforehand.

[PhilippGackstatter]

I see, thanks!

Would it add too much complexity to be able to query by note ID and/or sender ID? The node already has indices on sender and note ID, so it wouldn't require additional ones from the DB side afaict (but I'm also not deeply familiar with the node).

Or is privacy the concern? The note tag, due to containing a limited amount of account ID bits could match more notes, so this protects Bob (in your scenario) from revealing which account ID he has and which notes exactly he would be able to consume.

Querying by sender would also protect Bob as Alice could have sent more unrelated notes to other parties. Though this would establish a (weak) link between Bob's account ID and Alice's account ID nonetheless. There could perhaps be some ways to make this an even weaker link, like querying by partial sender ID so it matches not only Alice's account, but maybe this would return too many notes.

Querying by full note ID would of course fully reveal to the node which note Bob is interested in, but could we support querying for a note ID prefix to get a similar level of privacy as with note tags? (Granted this would require a new index/column in the note DB afaict).

I think if we could find a different way to query for private notes than tags that would definitely simplify the tag.

[bobbinth]

Yeah, privacy is the main concern here. If we query by note ID, there is basically very little privacy: it will be very easy to build a transaction graph. The details of the transaction would remain private, but the fact that two accounts are interacting will be basically public.

Querying by sender ID is not much better. Unless an account is doing a lot of transactions, it will be pretty easy to infer that two accounts are interacting by keeping track of the time. For example, if account A sent a note, and account B queries for notes of account A a few mins later, it is pretty easy to infer that they are doing something together. With statistical analysis, this can be made more robust.

There are other ways to break linkability between transactions, but they are much more complex than the tagging system (with much worse performance, though, arguably better privacy guarantees).

[bobbinth]

If we are willing to give up on breaking linkability, then we don't need the whole nullifier structure and the whole design becomes way easier. Though, I'm not sure its a good idea.

[PhilippGackstatter]

Got it, thanks for elaborating! I definitely wouldn't get rid of the privacy guarantees.

[PhilippGackstatter]

I think we can split this in roughly two high-level categories:

• Network Notes: One bit flag needed to identify a note as a network note.
  • Account Target: note tag contains as many account ID bits as possible to make it as unambiguous as possible to identify the target network account.
  • Use Case Target: Script root identifies use case. Remainder of note tag unused, i.e. zeroized.
• Non-Network Notes
  • Account Target: note tag contains a small prefix of the target account ID for privacy.
  • Use Case Target: TBD

The private use case is not clear to me yet.

When receiving a private use case note such as a SWAP note, wouldn't the tag also be useful to retrieve note authentication paths with some privacy guarantees, similar to when the note is targeted at a private account ID?

One way to test this is to try to implement the partial swap note and see if we can really make meaningful use of the aux field - or if we should make the amount of attached metadata flexible somehow.

Would the note tag look the same as the SWAP tag, i.e. contain the requested and offered asset? And what would the aux value be used for?

[bobbinth]

Yes, it looks like we may want to make this a bit more flexible. I imagine one WORD of data may be enough for such use cases?

This is not clear to me yet. I'd like to think this through on the example of a partial swap note that @partylikeits1983 tried to build a while back and see if we can indeed do it with just one word or if we'd need more. The basic setup here is as follows:

1. Alice creates a PSWAP note which contains 1 ETH that she wants to swap for 3000 USDC. This note is public.
2. Bob only has 1500 USDC, so, he consumes this note claiming 0.5 ETH. This process generates two notes:
   a. A new PSWAP note with 0.5 ETH swappable for 1500 USDC. b. A private P2ID` note that goes back to Alice with 1500 USDC.

Now, Alice will detect the P2ID note resulting from this transaction (because the note would use Alice's tag) - but since the note is private, Alice doesn't know the note's details and so she can't consume it (or even tell for sure that the note is for her).

The two pieces of info that Alice really needs to get are:

• What was the initial PSWAP note that generated this P2ID note.
• What is the amount that is contained in this P2ID note (i.e., 1500 in this case).

Everything else can be derived. The data doesn't need to be precise either (I think). Like the first 32 or 64 bits of the initial PSWAP note should be enough for Alice to check locally if she knows of this note.

[partylikeits1983]

I think it is possible to derive a private P2ID note that was created by a private SWAPP note. Although things get complicated quickly :)

Its simple enough to precompute all the possible future P2ID serial numbers and P2ID recipient digests for a given SWAPP note. However, its not possible to derive the P2ID note if you don't know the asset it contains. This means the tag would need to somehow signal at least the amount of the asset (we don't need the faucet id, although it wouldn't hurt).

For simplicity sake, the CLOB demo I wrote I only use public SWAPP and public P2ID notes. The SWAPP note definitely works and I have been able to match batches of SWAPP notes against each other (up to 50 SWAPP notes in a single tx on testnet). Here's the SWAPP note masm code for 0.10.0: https://github.com/partylikeits1983/CLOB/blob/main/masm/notes/SWAPP.masm

[PhilippGackstatter]

Its simple enough to precompute all the possible future P2ID serial numbers and P2ID recipient digests for a given SWAPP note.

How would that work? How are the P2ID serial numbers derived based on the initial SWAPP note?

---

So let's take the example of Alice creating a SWAPP note and it is partially filled. That results in a P2ID' and SWAPP' note.

For Alice to derive the note details for P2ID', she needs to compute the NoteDetails, which consists of NoteAssets and NoteRecipient.

NoteAssets

In order for Alice to figure out which requested asset was sent to her, she needs to know which SWAPP note of her was consumed and resulted in the creation of that note (she could have many SWAPP notes). As @bobbinth mentioned, a 32 to 64 bit prefix of the note ID of the SWAPP note should be enough for this.

Once she knows the faucet ID, she needs to know what amount of the requested asset is contained in P2ID'. This information must be passed along the note itself, since it cannot be derived. The amount takes up a Felt worth of space and would then be part of the AUX value.

NoteRecipient

She also needs to compute the recipient, which consists of:

• serial_num
  • This must be deterministically derived from the initial SWAPP note that Alice creates. Alice knows the initial SWAPP note based on the faucet ID prefix mentioned above, so no additional information should be necessary.
• script_root
  • This statically known to be the P2ID script.
• input_commitment
  • These are the inputs to the P2ID' note, which will be Alice' account ID.

So none of these should have to be part of the AUX value, afaict.

Assumptions

I'm assuming that if the SWAPP note is consumed and results in a SWAPP' note, Alice client will be aware of this note and track it. That way, the same process above should apply once the SWAPP' note is consumed, resulting in SWAPP'', and so on.

Sidetrack: I do wonder how Alice' client generally differentiates between a private note sent to her with the details provided via a side-channel versus a note that is the result of a SWAPP. Without further information, the client may have to try all kinds of derivations to see if one of them results in the note ID that was sent to her. Maybe a use case ID could be useful for this still? I'm mentioning this because further above in the discussion I said that for public notes, the script root would replace the use case ID. But it seems like for private notes, a use case ID is still useful, unless I'm missing something.

Conclusion

Based on this, it seems like the faucet ID prefix (let's say 32 bits) plus the amount (a Felt) should be enough. Maybe additionally a use case ID of 32 bits is not absolutely required but useful for the client. So overall roughly two Felts worth of space may be enough, and so a Word would fit that use case. There may be other use cases where a Word is not large enough, but I don't know if it's worth optimizing for that unknown use case yet.

I think it might be worth trying this out in practice and seeing if the above is correct. With the current 64-bit aux value, we may be able to try this by storing the amount in aux, and assuming that the client magically knows which SWAPP note the P2ID note resulted from (so we don't need to store the faucet ID prefix in aux). We would also ignore the use case ID. If that works, then I think we know that a WORD-sized aux should be sufficient for the SWAPP use case.

[bobbinth]

There is another use case that comes to mind - encrypted notes. These would basically be private notes with additional data attached to them (i.e., the actual encrypted content of the note). I'm thinking maybe we can kill two birds with one stone here.

Currently, we define a note as note details + note metadata, and the commitment to the note (i.e., what goes into the note tree is):

hash(NOTE_ID, METADATA)

We could re-define it as:

hash(NOTE_ID, hash(METADATA, AUX_DATA))

Where AUX_DATA (using this name as a placeholder for now) is a commitment to arbitrary amount of data (within reason). If there is no such data, AUX_DATA would be just an empty word, or it could be used just as a single word (kind of like we can use note/tx script args either as data or as commitment to more data).

Unlike note inputs (soon to be renamed into note data), AUX_DATA is not something that can be programmatically accessed from within the note script. But, the transaction kernel commits to AUX_DATA as a part of an output note. The content of AUX_DATA is not enforced by the protocol - so, the user is free to put w/e they want there.

This enables us to address the use case we were discussing above - we can put up to 32 bytes directly into AUX_DATA, and we could do more if the use case required.

One such use case is encrypted notes. To send an encrypted note on chain, the user then would do the following:

1. Create a regular private note.
2. Encrypt note contents in the VM. This needs to be thought through more because we may want to encrypt additional details (e.g., full serial number, more than just script root) - but that's a separate discussion.
3. Hash the encrypted data (we actually have an efficient way to both encrypt and hash at the same time, cc @Al-Kindi-0 if I'm misremembering this). This would be our AUX_DATA.
4. Put the encrypted data into the advice map under AUX_DATA key.
5. Attach AUX_DATA to the note.

Then, this AUX_DATA (and the actual underlying data), will be sent with the transaction and will go on-chain. It can then be retrieved by the intended recipients and interpreted in w/e way they find useful.

To summarize, our note becomes:

• Note details - same as now: assets, script, inputs, serial number.
• Note metadata:
  • Sender ID: 2 elements
  • Note type: 2 bits
  • Note tag: 32 bits
  • aux template: 16 bits? - provides info about the AUX_DATA.
  • Execution hint: 1 element
• Aux data
• Optional pre-image of the aux data.

Open questions

• Do we still need Encrypted note type?
• What is the format of the aux template? At the very least, we'd need it to answer the following questions:
  • Is aux data attached to the note?
  • If it is attached, is it "raw data" or is it a commitment to more data?
  • If it is a commitment to more data, what is the size of that data (in words)?
  • If there is more data, maybe we also want to specify somehow what it contains?
• Should we have the same format of aux/metadata for all notes? Or should they be different per note type?

For example, for network notes we could define metadata as:

• Sender ID: 2 elements
• Note type: 2 bits
• Execution hint: 1 element
• Target account: 1 element (or maybe the whole 2 elements)

We don't need to define the note tag because we could infer the use case from the script root. Also, we probably don't need AUX_DATA because we have note inputs which are public.

Similarly, maybe public notes also don't need AUX_DATA - though, it probably doesn't hurt to maintain consistency.

[PhilippGackstatter]

I think the overall approach makes sense, but I have some questions/comments about details.

Then, this AUX_DATA (and the actual underlying data), will be sent with the transaction and will go on-chain.

A ProvenTransaction doesn't contain advice data, so the encrypted data needs to be stored somewhere. I imagine this needs to be part of the Note? Unless we want to introduce PrivateNote, PublicNote, etc. I imagine a good place for differentiation between notes would be NoteMetadata. As you alluded to, we could have different formats for metadata for different note types, and I think that's a good idea. We could make it an enum (which could replace NoteType):

pub enum NoteMetadata {
  Private(PrivateNoteMetadata),
  Public(PublicNoteMetadata),
  Encrypted(EncryptedNoteMetadata),
  Network(NetworkNoteMetadata),
}

These would contain different things as you mentioned:

• Private & Public
  • Sender ID: 2 elements
  • Note type: 2 bits
  • Note tag: 32 bits
  • aux data size in words: 16 bits
  • Execution hint: 1 element (?)
  • AUX_DATA: User-defined, raw or pre-image
• Encrypted
  • Sender ID: 2 elements
  • Note type: 2 bits
  • Note tag: 32 bits
  • aux data size in words: 16 bits
  • Execution hint: 1 element (?)
  • AUX_DATA pre-image: arbitrary number of elements (within reason), AUX_DATA itself can be derived
• Network
  • Sender ID: 2 elements (~120 bits)
  • Note type: 2 bits
  • Execution hint: 32 bits or more
  • AUX_DATA: Specifies target account, e.g. 2 elements

Comments:

• Private and public notes allow for user-defined aux data.
• Encrypted note metadata contains the AUX_DATA pre-image, i.e the encrypted note data.
• Network metadata uses aux data to include the full target account ID. If we can include the full two elements, then the only remaining roadblock for lifting the "account ID prefix uniqueness" in the account tree are the assets, but we may be able to solve that as well.
• I've renamed "aux template" to "aux data size" here.
  • If the size is equal to 0, we could assume there to be no pre-image in the advice provider and AUX_DATA is raw data.
  • If the size is > 0, we could assume there to be a pre-image in the advice provider and AUX_DATA is the hash of that data.
• Question: Do we actually need the execution hint for any other notes than network notes? If not, we could save some data there. For locally executed transactions, it should be relatively cheap to dry-run a transaction to see if notes are executable, which will be much more reliable than the execution hint, which could be set to anything, so a client would have to dry-run anyway.
  • If we remove it, then we could include more "aux template" things like a hint as to what the data is, but not sure yet whether it's needed.
• The metadata for private/public/encrypted turned out to be almost the same. Though for encrypted notes, it may be beneficial to interpret aux data directly as encrypted data and only as arbitrary data for private/public notes. NetworkNoteMetadata would be different from the others, and so it may still make sense to have the above Rust definition of NoteMetadata, with dedicated metadata types for each note type.
• On the naming front, my suggestion would be:
  • aux data => note attachment
  • aux template => note attachment metadata
  • Attachment seems like a fitting term, since it's an optional additional thing in the note.

[partylikeits1983]

How would that work? How are the P2ID serial numbers derived based on the initial SWAPP note?

Great question let me explain:

1. Computing serial numbers in the SWAPP note

object	on-chain formula	who already knows the inputs?
next SWAPP serial	swapp_serial′ = swapp_serial₀ + k (increment by 1 after each fill)	Alice (she set swapp_serial₀)
P2ID serial	p2id_serialₖ = hash(swapp_serial, k)	Alice (she can iterate k = 1…M)

k is the “fill number,” i.e. how many times the SWAPP note has been filled since creation.

Because both operands for computing serial numbers are deterministic, Alice can pre-compute the entire sequence {p2id_serial₁,…, p2id_serial_M} the moment she posts the original order.

2. NoteRecipient can be cached up-front

NoteRecipient {
  serial_num       = p2id_serial_k    // from table above
  script_root      = P2ID_SCRIPT_ROOT   // constant
  input_commitment = hash(AliceAccountId)    // constant
}

All three fields already live on Alice’s machine, so discovery is effectively O(1). Its easy for Alice to compute all future NoteRecipients for the output P2ID notes.

3. What still has to ride along in the tag

The only thing Alice cannot derive is the filled amount. The faucet ID is implicit because she knows the SWAPP note and its requested asset; the tag just needs to carry the amount of that asset that ended up in the P2ID note (in this case the P2ID note carries exactly one asset).

[PhilippGackstatter]

Thank you!

So if Alice can figure out which SWAPP note created a newly received P2ID note, she can fetch the SWAPP note details from her client's storage (or worst case from chain (since they are all public)). Then she can take the serial number of that SWAPP note together with its SWAPP_COUNT_INPUT note input (which is equivalent to k, iiuc) and derive the P2ID's serial number by hashing the two.

The faucet ID is implicit because she knows the SWAPP note and its requested asset

I guess technically you're right and the faucet ID prefix isn't necessary. But if Alice created multiple SWAPP notes, I don't see a simple strategy yet to derive all the P2ID notes. For example, consider a scenario where she has created two SWAPP notes SWAPP_0 and SWAPP_1 and both were consumed. She has now received two P2ID notes P2ID_A and P2ID_B. It's not immediately clear which P2ID note corresponds to which SWAPP note:

• If we look at the consumed SWAPP notes, we can derive the NoteRecipient of the corresponding P2ID note, but not the NoteAssets.
• If we look at the P2ID notes, we can derive the NoteAssets, based on the amount from the aux value, but not the NoteRecipient.

So we'd have to see which combination of NoteRecipient and NoteAssets results in one of the P2ID note IDs. There are four combinations but only 2 P2ID notes, and this would get worse if more SWAPP notes were consumed. So my point is that this seems cumbersome to implement and a hint for the original SWAPP note may be useful to simplify this process. Or maybe there is a simple way to avoid this that I'm not seeing.