Spending future notes

[pestopoppa]

@Dominik1999 and I have been discussing numerous bottlenecks to order-book development on Miden. One big one that pops up in numerous contexts, is that sometimes multiple transactions need to be able to spend the same note without waiting for a new block to be validated.

Imagine Alice initially spends to Note 'A', holding 100 ETH, whose spending script allows consuming the note to trade DAI for ETH at 1:1 exchange rate (for convenience).

To consume the note, Bob must prove that a new Note 'B' has been created (or direct payment to Alice's account), redeemable by Alice, with some amount X of DAI. If X=100 everything is pretty and simple, but what if X<100?

In this scenario, a new Note 'C' should also be created, carrying the same spending script of Note A (effectively a clone), holding 100-X ETH. Note C can now handle further swaps of Alice's funds.

Now, suppose the transaction has been submitted by Bob but the block hasn't been mined yet. Technically speaking, Note A still has 100-X ETH available to be purchased. This is implied by the fact that Bob's transaction, will create a Note C in the future once it gets validated.

What is stopping a new user, Charlie, from already submitting a transaction, similar to Bob's, attempting to consume Y ETH of Note C?
If it were possible to monitor transactions being submitted at the sequencer level, Charlie could submit his transaction. When validators later validate Bob's transaction, the Note C required by Charlie's transaction will be created, thus allowing Charlie's transaction to go through also.

Obviously, if validators follow a different sequence of events (i.e. attempt to validate Charlie's before Bob's), Charlie's transaction will fail and only Bob's will go through. This, however, is the current state of things anyways so it's not a big deal.

Alternatively, if Note C carries the same Note ID as the consumed Note A, then it wouldn't even matter in which order Charlie's and Bob's transactions are processed. All that would matter is that X+Y<100.

How hard would it be to implement this? Enabling this kind of feature would allow much more efficient sub-blocktime operations to be executed.

[bobbinth]

Thank you for the detailed write-up! I think supporting something like this would indeed be super useful, and there are a couple of ways to go about it (both with their trade-offs).

First, let me provide a bit of context for why we currently require for a note to be included in a block before it can be consumed in a transaction.

When we consume a note in a transaction, among other things, we need to do the following:

1. Make sure the note was created at some point in the past. This is done by checking that the note is a part of Notes database (every block header contains a commitment to this database).
2. Make sure the note hasn't been consumed yet. This is done by checking that the note's nullifier is not in the Nullifier database (every block header also contains a commitment to the Nullifier database).

Checking that the note is a part of the notes database is done when we execute a transaction. Checking that the note hasn't been consumed yet is done when a transaction is included in a block. We separate these two steps to enable privacy. Specifically, to perform the first step, one needs to know a lot about the note, but to perform the second step, one needs to know only the note's nullifier. So, in the context of private transactions, the user proves that the note was created at some point in the past, and then the block producer proves that the note's nullifier hasn't been consumed yet. This way, the block producer does not learn anything about the details of the note.

So, if we'd have the block producer perform both tasks, we'd give up quite a bit of privacy (and will also require the block producer to perform more work). But, for one, this is only relevant for private transactions (so, public transactions could conceptually work differently), but also, we could enable consumption of un-recorded notes in private transactions.

Ephemeral local notes

Exploring the latter approach first, we could support functionality where a note is created and consumed within the same transaction. Such notes would never be recorded in the Note's database and the block producer would not even know that they were ever created/consumed.

Applying this to the scenario described in the original post, we could have a single transaction which processes many trades. Some of these trades produce extra notes which then get immediately consumed in the same transaction.

In fact, we may be able to update transaction execution semantics to skip such ephemeral notes altogether. For example, let's say we have 3 notes describing the following trades:

1. From A: sell 10x for 5y.
2. From B: sell 1y for 2x.
3. From C: sell 3y for 6x.

We should be able to process these trades in a single transaction which consumes these notes and produces the following notes:

1. Send 4y to A.
2. Send 2x to B.
3. Send 6x to C.
4. From A: sell 2x for 1y.

This fulfills trades from B and C, and partially fulfills trade from A (creating a new trade with the part which couldn't be fulfilled).

I think providing functionality to make something like this possible would be independently useful. The main thing to solve here is to figure out how to "tell" the first note that it needs to perform a "partial trade". One potential way to do it is to introduce something like dynamic note inputs - but I'll need to think more about this.

Ephemeral public notes

The idea here would be to delegate proving that a note has been created before it is being consumed to the block producer. For this, we'd need to do the following:

1. Update transaction execution semantics such that we can skip proving existence for some notes. This means that in addition to the list of nullifiers for consumed notes, a transaction would output a list of notes which have been consumed but whose existence hasn't been verified.
2. Update batch and block aggregation logic to perform the checks that were skipped at the transaction level.

The above is just a high-level sketch, and we'll need to carefully think through all the implications. It for sure will add quite a bit of complexity - but maybe this complexity is worth it.

[bobbinth]

I've created two issues which address the above points:

• Enable transaction-specified inputs for notes #338
• Delegated note inclusion proofs #353

It will take some time to update the protocol (and then the node) to support these, but once these are implemented, I believe spending notes which haven't been recorded yet on chain should be possible (as long as such notes are consumed in the same block they are created in).

[bobbinth]

Closing as this has already been implemented.