Challenges surrounding sub-second order-book performance on Miden

[daedlock]

Spending future notes allows transactions to consume notes that are created during the transaction, in addition to being able to pre-compute output note ids for a transaction consuming a particular input note.

The goal is to allow KEOM to receive and batch multiple fulfillments in the same block.

Below is a graphical representation of a limit order, Bob starts by creating a limit order note, Alice partially consumes the limit order, resulting in 2 output notes (A clone of the limit order with the unconsumed amount and a P2ID note consumable by the original maker -Bob-). This flow repeats until the original limit order is fully consumed or until the original maker cancels/recalls their order.

Limit Orders

Below is a sequence diagram describing the flow and interactions during a limit order creation. It's straight forward, a trader asks KEOM how to build the transaction, KEOM responds with a serialized transaction, the trader then executes and submits the transaction directly to the operator. KEOM polls the operator to see if the note is included in order to update it's internal order book state accordingly.

Market Order

The sequence diagram below describes the flow and interaction of a market order. A trader wants to buy some asset and they don't care about the price. The trader asks KEOM which then responds with the notes they should consume in a serialized format. The trader proceeds to consume the order by executing the transaction then submitting it to the operator.

Problem

The order book performance in the above design is bound to the block time of Miden since KEOM backend has to wait for inclusion proofs from the Node Operator before it can consider an order filled/consumed

Workaround

Traders to submit their transactions to KEOM instead of directly to the operator. This would allow KEOM to keep tighter track of inclusion status of notes. It would also allow KEOM to make use of future notes features. In the case of partial order consumption, KEOM would be able to respond with future NoteIds to different traders without waiting for the original note to be included. This is because KEOM has full visibility and control of the sequence of transactions/submissions to the operator, unlike the current scenario where KEOM has to trust users to submit their orders to the operator on time.

The problem with this workaround is that it assumes full trust that users won't submit their transactions directly to the node operator rendering KEOMs transactions invalid.

One solution is to have the limit orders be multi-signed by the trader and KEOM specific special account. Since this is not available in miden yet. I have created this issue to braistorm potential workarounds/solutions that would allow the order book to achieve subsecond TPS performance with the existing tool-chain.

[bobbinth]

This is super cool! Thank you for writing it up. Some preliminary thoughts:

• As long as the user is the one executing a transaction (a property I think we want to preserve), I don't see a way to avoid a multi-sig-like solution.
• I think for the near future (i.e., next couple of months) - it is OK to trust the user not to do malicious things. In this time (i.e., by the end of summer) we can try to implement multi-sig support and enable a proper solution.
• We should flash out what specifically we want to do with multiple signers. For example, I'm not sure the issue is that the user can submit their transaction directly to the node, but rather that the user could try to execute a different transaction involving the same note. So, then the questions become:
  • How can we make sure the user can execute only the transaction they built with the help of the DEX? (here is probably where multi-sig comes in).
  • How can we keep the system non-custodial? i.e., how can the user recall their note if the DEX stops cooperating (this may involve some kind of time locks).

[Dominik1999]

Thanks for the issue and the question.

The problem with this workaround is that it assumes full trust that users won't submit their transactions directly to the node operator rendering KEOMs transactions invalid.

So, if everything is routed via the KEOM frontend, it should be okay, right? If there is a frontend where traders need to log in and trade, then you can easily build it so that users submit the transactions to KEOM and not to the operator—at least for a PoC. A user can still "hack" around it, import the transactions into his / her own client, and submit them to the operator. But as Bobbin said, for the first couple of months that might be ok.

One solution is to have the limit orders be multi-signed by the trader and KEOM specific special account. Since this is not available in miden yet. I have created this issue to braistorm potential workarounds/solutions that would allow the order book to achieve subsecond TPS performance with the existing tool-chain.

Another solution might be to add another optional field secret to the TransactionResult here.

pub struct TransactionResult {
    transaction: ExecutedTransaction,
    relevant_notes: Vec<InputNoteRecord>,
    secret: (Digest, Word)
}

Then, the user would create the TransactionResult locally, and submit it to KEOM. KEOM adds the secret which gets verified by the Miden operator. Then, KEOM might have different regulatory responsibilities, because it can block a user transaction. So maybe, you need to use a Hash-Time-Lock instead and say after 10 blocks, the user can submit the transaction even without the preimage to the secret.

[daedlock]

By the way, apart from the security aspect. I am trying to assess if KEOM can run as a sequencer/intermediary. For this, KEOM would need to submit multiple transactions as a batch via the client. I assume this is only possible if the following conditions are met:

1. miden-node to have an gRPC method for submitting a bundle of transactions (in the correct order) to the node
2. miden supports executing and proving transactions with input notes that have not been mined in a block yet

[bobbinth]

2. miden supports executing and proving transactions with input notes that have not been mined in a block yet

This is already in progress and should be available relatively soon.

1. miden-node to have an gRPC method for submitting a bundle of transactions (in the correct order) to the node

We can add this as well. Will require some modifications in the miden-node - so, not sure we'll have it done in the next couple of weeks - but definitely doable in the next month or so.

However, I'm not sure these two would solve the issue. Specifically, I think the issue is the following:

1. A user creates a note which corresponds to a limit order.
2. A chain of transactions is built (with the help of KEOM) such that the first transaction in the chain consumes this note. KEMO submits this chain of transactions to the node.
3. At the same time, the user creates a separate transaction which consumes his note and also submits it to the node.

Here, we'd end up with a race condition: only one of these transactions can go through. If the user's transaction goes though it would cancel the chain of transactions built by KEOM in point 2.

[daedlock]

I agree. Bundles will not solve the race issues. But I think we need it anyways to run as a sequencer/blockbuilder. Then we have to figure out how to submit transactions from user's and KEOM side! One solution you suggested is to Timelock tx execution and give exclusivity to KEOM in that window of time. I think this works, we just need to check if it's legally viable.