User-to-user transaction flow

[bobbinth]

In this note I'd like to outline how users could transfer assets between each other on Polygon Miden. This is probably one of the simplest use cases, but even here, there are a few nuances which are important. Also, this is just an illustrative example, many choices of concrete values could end up being different in the actual system.

As described in #7 (comment), there are two basic scenarios for user-to-user transactions, and we'll cover both them. The scenarios are:

• There is no off-chain channel between the users.
• There is an off-chain channel between the users.

Before diving into interaction flows, let's lay out some basic assumptions and terminology.

Assumptions

• There are two users: Alice and Bob.
• Both of them have accounts which implement a basic wallet interface. Specifically, they expose send_asset and receive_asset functions.
  • send_asset function creates a note which can be claimed by the specified recipient.
  • receive_asset adds the specified asset to an account's vault.
• There is a well-know script which can be used to move note assets into a specific account. The pseudo-code for this script could look as follows:

begin
  if chain.get_block_height() > note.inputs[0]
    assert(account.get_id() == note.inputs[1] || account.get_id() == note.inputs[2])
  else
    assert(account.get_id() == note.inputs[1])
  end
  
  for a in note.assets
    account.receive_asset(a)
  end
end

The above script assumes that note inputs are arranged as follows:

• input[0] contains block height after which the note can be reclaimed by the sender.
• input[1] contains the recipient's account ID.
• input[2] contains the sender's account ID.

We'll refer to this script as P2IDR (pay to account ID with recall).

No off-chain interaction

Let's say Alice wants to send some asset X to Bob, but Bob is not online (or Alice doesn't know how to contact Bob). All Alice has is a QR code from Bob. The transfer of asset X could be accomplished as follows.

Alice creates a note for Bob

1. Alice scans Bob's QR code. This QR code contains the following info:
   a. Bob's tag (14 bits).
   b. Bob's account ID (168 bits).
2. Alice creates a transaction which calls send_asset function on her account and creates a new note. This note will look as follows:
   a. Note script represented by the MAST root of P2IDR.
   b. Script inputs set to some future block height, Bob's account ID, and Alice's account ID.
   c. Vault with a single asset X.
   d. A serial number which Alice will pick in such a way that the first 2 bits of the note's hash are set to 10 and the following 14 bits are set to Bob's tag. To find such a serial number, Alice would need to perform $2^{18}$ hashes on average.
3. Alice executes this transaction locally against her account, generates the execution proof, and send the proof together with transaction data to the operator.
4. The operator verifies that the transaction proof is valid, and includes the transaction into the next block. The effect of this is that:
   a. Alice's account is updated to remove asset X from the account's vault.
   b. A new note with asset X is added to the note's database. Because the first two bits of the note's hash are 10, the operator will also record the full note details on chain.

Note that step 3 could have been different. Alice could have sent the transaction to the network, in which case the operator would have executed and generated a transaction proof. But this change would not have any effect on step 4.

Bob consumes the note created by Alice

1. After the note is included in a block, the operator checks if the note's prefix has been registered with anyone. Let's assume that Bob had previously registered this prefix with the operator. Thus, the operator will notify Bob that a new note waiting for him.
   a. I will skip the detail of how this notification happens. The options could range from push notifications to Bob making an RPC call to retrieve all notes with a given prefix.
2. Once Bob comes online, he will retrieve the note's details and check if in fact the note was addressed to him.
   a. To check this, Bob will look at the note's script and realize that this is a P2IDR script. Then, Bob will check the second input field to see if the ID matches his own account ID. Both of these checks should be very light-weight.
3. Bob creates a transaction which consumes the note sent by Alice in the context of his own account.
4. Bob executes this transaction locally, generates the execution proof, and sends the proof together with required transaction details to the operator.
5. The operator verifies that the transaction proof is valid, and includes the transaction into the next block. The effect of this is that:
   a. The note created by Alice is consumed.
   b. Bob's account is updated to add asset X to its vault.

Note that step 4 could have been different. Bob could have sent the transaction to the network, in which case the operator would have executed and generated a transaction proof. But this change would not have any effect on step 5.

Privacy guarantees

This transaction flow is not private. Anyone observing the chain will know all the details about the transaction. Specifically:

• They will know that asset X was removed from Alice's account.
• They will know that the same asset X was added to Bob's account.

With off-chain interaction

Let's now say that there is a separate channel between Alice and Bob. The interaction flow could look as follows.

Alice creates a note for Bob

1. Alice engages in an interactive protocol with Bob to define basic parameters of the note. Specifically, they agree:
   a. That asset X is being transferred.
   b. That P2IDR script will be used.
   c. What serial number to use. The serial number will be chosen in such a way that the hash of the note starts with 00 and is followed by Bob's 14-bit tag. Either Alice or Bob could compute the serial number, but both must know the serial number at the end.
2. Alice creates a transaction which calls send_asset function on her account and creates the agreed upon note.
3. Alice executes this transaction locally against her account, generates an execution proof, and send the proof together with the required transaction data to the operator.
4. The operator verifies that the transaction proof is valid, and includes the transaction into the next block. The effect of this is that:
   a. Alice's account is updated to remove asset X from the account's vault.
   b. A new note with asset X is added to the note's database. Because the first two bits of the note's hash are 00, only the hash of the new note is recorded on-chain.

Note that in step 3, Alice didn't have to execute the transaction locally. Instead, she could have sent the transaction to the operator. In this case, the operator would know the details of the transaction, but these details would not be recorded on chain.

Bob consumes the note created by Alice

1. After the note is included in a block, the operator checks if the note's prefix has been registered with anyone. As before, let's assume that Bob had previously registered this prefix with the operator. Thus, the operator will notify Bob that a new note waiting for him.
2. Once Bob comes online, he will check if the hash of the note matches a hash of a note which he previously agreed upon with someone. This could be as simple as a lookup in a map of expected notes. If a match is found, Bob will know all the details of the note (i.e., the script, the inputs, the vault's contents, and the serial number).
3. Bob creates a transaction which consumes the note sent by Alice in the context of his own account.
4. Bob executes this transaction locally, generates an execution proof, and sends the proof together with required transaction details to the operator.
5. The operator verifies that the transaction proof is valid, and includes the transaction into the next block. The effect of this is that:
   a. The note created by Alice is consumed.
   b. Bob's account is updated to add asset X to its vault.

Note that in step 4, Bob didn't have to execute the transaction locally. Instead, he could have sent the transaction to the operator. In this case, the operator would know the details of the transaction, but these details would not be recorded on chain.

Privacy guarantees

Depending on how the transaction is executed and how Alice's and Bob's accounts are recorded on chain, we get different privacy guarantees:

First, let's assume Alice and Bob record only hashes of their accounts on-chain and maintain full account states locally. In this case:

• If both Alice and Bob executed and proved transactions locally, 3rd parties won't be able to learn much about what happened. What will be know is that Alice created some note (with unknown content) and that Bob consumed some note (with unknown content and not necessarily the same not as the one Alice created).
• If instead Alice and Bob delegate execution to the operator, the operator will know the full details of the transaction. But because the details are not recorded on chain, everyone else won't learn anything besides what is described in the previous point.

Next, let's assume Alice and Bob record full states of their accounts on chain. In this case, observers may be able to determine the details of the transaction as they will see that asset X was removed from Alice's account and added to Bob's account. And the more unique X is the easier it will to determine what happened.

It is worth noting that in either case both Alice and Bob know who the counter-party in the transaction is. If this is undesirable, additional measures can be taken to hide the sender from the recipient and/or the recipient from the sender - but some compromises may need to be made. For example, if we want to hide the recipient (i.e., Alice wouldn't learn which account consumed the note), then we can't use a recallable note. This is because for a note to be recallable Alice must know its serial number. But knowing of the serial number implies that Alice will be able to compute the note's nullifier and, thus, will know which transaction consumed a note.

[grjte]

This is very helpful. One small note - it seems like you're now referring to the prefix that a user registers with the operator as their "tag", but the terminology isn't used consistently, so I wanted to clarify (or be corrected).

A serial number which Alice will pick in such a way that the first 2 bits of the note's hash are set to 10 and the following 14 bits are set to Bob's tag

After the note is included in a block, the operator checks if the note's prefix has been registered with anyone. Let's assume that Bob had previously registered this prefix with the operator. Thus, the operator will notify Bob that a new note waiting for him.

This registered prefix is Bob's tag, as described here, right?

A serial number which Alice will pick in such a way that the first 2 bits of the note's hash are set to 10 and the following 14 bits are set to Bob's tag.

A final bit of clarification (and perhaps this would be better in #7) - in the off-chain interaction case, the operator doesn't necessarily know the length of the tag part of the note's serial number, and should therefore notify for any matching serial number of any length, right? For example, Bob's tag could in theory have been 10 bits instead of 14 (according to my understanding of #7), so Alice could have used a serial number of 00 plus a 10-bit tag, so even if she did use a 14-bit tag as described above, the operator wouldn't know that this was the case. Therefore, if Charlie has a 10-bit tag registered with the operator, then Charlie should receive this note, right? Do we have a range limit on lengths of tags that people can register? Could I set a 1-bit tag and force the operator to do a lot of extra notifications (however they're implemented)?

[bobbinth]

Yeah - I haven't been very consistent (and I'm up for re-defining terminology if it makes things more clear). My current thinking is:

• The first two bits specify note type.
• For types 00 and 10, some number of subsequent bits define a tag. This number is not set by the protocol - so, it could be anything (0 or more bit).

The facts that the protocol does not define the size of the tag does not mean that an operator will allow users to register any tags. It will be up to a specific operator to set the limit (or define a conditions under which they would allow a tag of a specific size). For example, some operators may set the minimum tag size at 10, others at 16 etc. There is nothing preventing an operator from allowing tags of size 0 (in which case they'll just forward all notes with type 00 and 10 to the client) - but my guess is that in most cases they won't do it.

For our initial operator I'm thinking we'll set the minimum at 14. It is small enough where finding a serial number to form this tag is not a huge amount of work (should be less than 0.5 sec in vast majority of cases), and at the same time large enough to meaningfully restrict the flow of notes to specific clients (i.e,. on average only one out of 65K unintended notes get forwarded to each client).

[Dominik1999]

As always, this is super clearly described. So I tried to put what I have digested into a diagram:

So in the case of A, there is no problem to be solved in the initial phase, right? Bob can check all incoming notes and then execute them against the correct ones. If we only would have 2 TPS in the first year, Bob should be able to sync with RPC provider, or he could ask the sequencer if there is a note for Bob.

In cases B and C, we need a protocol for Bob to know that there is a note and to be able to receive his asset.

For B I understand the protocol that you have outlined. The question to me is, do we want to provide such a channel? In theory, this could be any off-chain communication channel, even WhatsApp or email. And in that case, what would a 3rd party know if either Alice or Bob stores the account data on-chain with the sequencer? I assume 3rd parties would only see that the account vault increases or decreases after a note with a certain hash are executed. Is that correct?

For C I understand the problem and the solution that you propose. I do have some clarification questions here:

• "Alice creates a note for Bob" Step 3 / 4:

3. Alice executes this transaction locally against her account, generates the execution proof, and send the proof together with transaction data to the operator.
4. The operator verifies that the transaction proof is valid, and includes the transaction into the next block. The effect of this is that:
   a. Alice's account is updated to remove asset X from the account's vault.
   b. A new note with asset X is added to the note's database. Because the first two bits of the note's hash are 10, the operator will also record the full note details on chain.

If Alice is executing the transaction locally against her account, why is the account being updated in 4a) and not yet in step 3)? Especially when we assume that the operator only stores the account hashes. (Maybe that also points to different layers of finality).

• Privacy guarantees in C (1):

There might be a subcase where the transaction can stay partially private (or correct me if I am wrong). If Bob knows that Alice sends something to him in a certain time window, couldn't Bob observe all new notes and still grind? Especially when he somehow would know the asset or the amount (because he only accepts 10 USDC, and Alices knows that). Maybe in the beginning that might be sufficient as a protocol (in case it is too hard to find a suitable one?).

• Privacy guarantees in C (2):

I don't understand why "[A]anyone observing the chain will know all the details about the transaction." If Alice or Bob only stores their Account data off-chain, then the operator only knows the account hash. So any observer would only see that Alice's hash changed, and then at a later point in time, Bob's account hash changes. I am sure I am missing something, but can you elaborate?

---

On a more general note:

1. Is there a way to define this protocol as open and only implement a base case? Then we can adjust to focus on whatever user needs are. And on the other hand, other teams and developers could also implement a standard for off-chain interactions as they like. Something similar happened on the Lightning network. There might also be hybrid models for decentralized sequencers (Sequencer A knows Alice's account data, Sequencer B Bob's) or a service that I trust collects tx and bundles them.

We could also add those four privacy modes step-by-step - whatever is easiest for the MVP:

• Everyone knows everything
• The operator knows everything
• Only Alice and Bob know everything
• No one knows anything

2. The user-to-user transaction flow with respect to privacy is an important use case. However, especially in the beginning, we want to market Miden as "developers are able to build advanced applications using client-side proving". So maybe solving problem C is at the beginning, not as important as other questions? E.g. what kind of computation can you prove locally and what is the benefit for the user?

[bobbinth]

Great summary (and graphic)! To answer your questions:

So in the case of A, there is no problem to be solved in the initial phase, right? Bob can check all incoming notes and then execute them against the correct ones. If we only would have 2 TPS in the first year, Bob should be able to sync with RPC provider, or he could ask the sequencer if there is a note for Bob.

Kind of. Even at 2 TPS (assuming full utilization), if you've been offline for an extended period of time (say a couple of weeks), processing all accumulated noted may take significant amount of time (i.e., over 30 mins). So, it would be nice to have a mechanism for narrowing down the set of notes to be processed. The scheme I described with prefixes should work , though I'm a bit concerned about its efficiency (especially on not very powerful devices). The nice thing is that this scheme is not part of the core protocol - so, if we come up with something better, getting rid of this one shouldn't be too complicated.

For B I understand the protocol that you have outlined. The question to me is, do we want to provide such a channel? In theory, this could be any off-chain communication channel, even WhatsApp or email.

I think we can definitely work on this - but in my mind, this could be a good candidate for something like an "improvement proposal" (i.e., similar to BIPs and EIPs). There could be many ways to accomplish it. For example, if the interaction is initiated by the recipient, the protocol could be pretty simple: the recipient sends something like an invoice to the sender, and as you've mentioned, this could be done over any channel (WhatsApp, email etc.).

The opposite flow is a bit more complicated as the sender needs to notify the recipient about the amount sent, the serial number chosen etc. In this case, I'm not sure any channel would work (but I could be wrong).

And in that case, what would a 3rd party know if either Alice or Bob stores the account data on-chain with the sequencer? I assume 3rd parties would only see that the account vault increases or decreases after a note with a certain hash are executed. Is that correct?

Third parties would see:

• Alice's account created a note. The assets in the note could be pretty easy to determine since changes to Alice's account are publicly visible (they may be somewhat obfuscated by creating multiple notes in the same transaction).
• Bob's account received the asset - but which note was consumed may not be clear. Of course, if the asset transferred is pretty unique, it is easy to determine that Alice's account sent the asset and Bob's account received it.

If Alice is executing the transaction locally against her account, why is the account being updated in 4a) and not yet in step 3)?

While the transaction is executed locally, there is no guaranteed that it will be recorded by the operator. So, we can be sure that the account has been updated only after the operator records the transaction.

If Bob knows that Alice sends something to him in a certain time window, couldn't Bob observe all new notes and still grind? Especially when he somehow would know the asset or the amount (because he only accepts 10 USDC, and Alices knows that).

If the amount and the type of the script used are known, the only thing left is guessing the serial number. If there is a way for Bob to guess it (or be convinced that the note wasn't intended for him) with a relatively small number of tries - than this could work. But I haven't thought about how this could be accomplished.

Privacy guarantees in C (2):

I actually didn't cover case C (only note hashes stored on chain, no-off chain channel) in the original post. This case is more complex and I didn't want to go into it yet. The cases I covered:

1. Full note details stored on chain.
2. Only note hashes stored on chain.
   a. Only account hashes stored on chain.
   b. Full account detail stored on chain.

So, in case 2b it may be possible to figure out who is transacted by looking at how account vaults change.

1. Is there a way to define this protocol as open and only implement a base case?

Yes, this is what I attempted to do in #7 (comment). There even the tagging scheme is not really a part of the protocol. In general, anything that needs to be done off-chain does not need to be a part of the protocol and can evolve separately.

We could also add those four privacy modes step-by-step - whatever is easiest for the MVP:

• Everyone knows everything
• The operator knows everything
• Only Alice and Bob know everything
• No one knows anything

That's exactly how I was thinking about it as well. My hope is that for testnet we can cover the first two, and the other two will come much later (i.e., after decentralization).

2. The user-to-user transaction flow with respect to privacy is an important use case. However, especially in the beginning, we want to market Miden as "developers are able to build advanced applications using client-side proving". So maybe solving problem C is at the beginning, not as important as other questions? E.g. what kind of computation can you prove locally and what is the benefit for the user?

Agreed, and as mentioned above, I didn't even attempt to address case C for now. In general, addressing C requires making a lot of decisions at the protocol level which require in-depth study.

[Dominik1999]

Thanks a lot for the detailed answers. To summarize everything:

• For case A (on-chain: full note details), we can use your scheme using the prefixes described in "No off-chain interaction
  " in the original post. We can change it in the future if we find something better.
• For case B (on-chain: note hashes - off-chain channel exists), we can use your scheme using the prefixes described in "With off-chain interaction". We have two sub-cases B.1 (on-chain: account details) and B.2 (on-chain: account hashes) with different privacy guarantees.
• For case C we don't have a solution yet. For our MVP we can neglect this case for now.

We start working on case A and then B following the broader scheme "implementing privacy step-by-step":

• Everyone knows everything
• The operator knows everything
• Only Alice and Bob know everything
• No one knows anything

[bobbinth]

@Dominik1999 - yes, all seems correct. Though I think A and B will be enabled very close to each other.

[hackaugusto]

Question: the examples above say that execution of the transaction could be done by the network. One case was for Alice when she sent some asset to Bob. The document said:

Note that step 3 could have been different. Alice could have sent the transaction to the network, in which case the operator would have executed and generated a transaction proof. But this change would not have any effect on step 4.

My question is, what data would Alice have sent to the network to allow the transaction execution? I assume it is some sort of signature, but I haven't seen a scheme for that yet.

[bobbinth]

Alice would need to send the following things:

• Relevant parts of her account state: account interface, method to be called, vault and storage access proofs (Merkle paths) etc.
• Relevant info for the note to be created: vault content, recipient.
• Signature over transaction inputs, outputs, and account state changes. I'll describe this in detail when I describe simple wallet design.

[ub-tech]

Hi - for 2a (only account hashes stored on chain), want to ensure I understand, double spends (erroneous state transitions) are prevented b/c the MidenVM must be used to create the transaction to be proved. so if Alice and Bob agree on the script, then its not possible to create a valid proof of incorrect state transition? the trust anchor becomes the VM in this case since the account hash must accompany every transaction (so alice can't use multiple account hashes to perform a double spend).

[bobbinth]

Yes, this is largely correct. More precisely, every transaction is a result of executing a transaction kernel on Miden VM. This transaction kernel takes one account and zero or more notes as inputs and produces the new account state (and zero or more notes) as output.

The transaction kernel ensures that the transaction is executed correctly - e.g., correct note scripts are executed, correct account interface procedures are called etc. etc. There is some more info on this here.

Regarding trust - there are multiple levels here. Starting from the STARK proving system, to Miden VM, to transaction kernels. To ensure correct execution of transaction, all of these need to work correctly.