Support submitting `ProvenBatch`

[Mirko-von-Leipzig]

We'd like to allow users to submit an entire ProvenBatch directly. This enables transaction sets which must be bundled together e.g. atomic swaps.

This will require a new RPC endpoint, some mempool improvements and some care in designing around this concept to ensure there are no untoward side-effects.

RPC

Add a SubmitProvenBatch analogue to SubmitProvenTransaction to both RPC and block-producer gRPC schemas.

The RPC implementation should verify the integrity of the batch before proxying it on (similar to what the SubmitProvenTransaction does).

Mempool

The current implementation doesn't really allow for this because it assumes the atomic building block is a ProvenTransaction.

A ProvenBatch contains the transaction headers, but not the raw transaction data and we therefore cannot deconstruct it back to "atoms" but instead this becomes a new atomic unit of sorts.

Open questions

1. What do we do if the submitted batch contains transactions already in the mempool?
2. What do we do if the submitted batch depends on transactions which are not already in batches? The current design operates on a DAG basis where the roots are those which are available to choose from. This should be allowed but could result in strangeness if we allow (1) as some txs could be stuck in limbo..

Its possible to brute force this and hope that we consider every edge case. Ideal would be a graph structure where this sort of property falls out naturally. This may mean consolidating the transaction and batch graphs into a more general graph - currently the batch graph is effectively an overlay graph on-top of the transaction DAG.

cc @bobbinth

[bobbinth]

1. What do we do if the submitted batch contains transactions already in the mempool?

I think the ideal approach here would be to mark this transactions as being in a batch but not remove them from the mempool. This way, they won't be selected for any other batches, but if the proven batch gets reverted for some reason, these transactions would become available for selection again.

2. What do we do if the submitted batch depends on transactions which are not already in batches? The current design operates on a DAG basis where the roots are those which are available to choose from. This should be allowed but could result in strangeness if we allow (1) as some txs could be stuck in limbo..

Initially, we can probably impose a simplifying restriction that that shouldn't happen. That is, if such a batch were to arrive, we would not accept it into the mempool.

In the longer run, would be nice to accept this batch into the mempool but somehow mark as not ready for processing. Once the transactions that this batch depend on make it into a different batch, we'd mark this batch as available for processing again. Here, we'd also need to track if a transaction on which the batch relies gets dropped from the mempool, we'd need to drop the dependent batch as well.

[Dominik1999]

might be releated 0xMiden/miden-proposals#7

[Mirko-von-Leipzig]

This issue is quite a bit more complex than it appears on the surface. I'll attempt to outline the problems I've run into; and also describe some options or simplifying assumptions we might make.

Overview

The node's mempool is responsible for accepting transactions from users, selecting from these transactions for transaction batch production, and then finally selecting from these batches to form blocks.

As per the OP, we want to allow users to submit entire transaction batches which would enable atomic batch use cases. However, this is somewhat in conflict with out current DAG based mempool model if we want to be maximally flexible ito what we allow.

Status quo

The mempool maintains a graph view of all inflight transactions and batches (these are not yet committed to the blockchain). A new transaction is accepted and added to this graph iff its state transition is valid wrt to the graph's current view of the inflight state. That is if:

1. The tx account's initial state matches the account's current state in the graph
2. All input notes are known and unconsumed
3. All output notes are new/unique

Once accepted, the inflight state view is updated with the new account commitment, input notes are marked as consumed/nullified and output notes are added as available. The transaction is added to the transaction DAG with edges to all its parent transactions i.e. transaction's upon who's state this transaction built aka the account's last tx + tx's which produced the required notes.

A transaction from this DAG is available for inclusion in a batch if all its parents were selected for inclusion already (in a previous batch, or in the current one). This batch is then inserted into a similar batch DAG with edges to its parent batches (formed by the batch's txs' parent txs). The batch DAG can therefore be thought of as an overlay graph ontop of the transaction DAG.

These DAGs are used to enforce ordering of transactions which ensures that batches in blocks are cohesive i.e. that they only rely on state from transactions already committed, or included in prior batches in the same block.

User batches

User submitted batches are a bit weird because the batch DAG is sort of in the middle of the process here, and challenge some of our assumptions implicit in the strict transaction ordering we get from the DAGs.

Problem: cyclic batch sets

Should we allow coupling between batches?

Batches are opaque and allow for unauthenticated notes to be verified at the block itself. This means its allowed (by protocol) to build a block where batch A depends on the outputs of batch B, and batch B depends on batch A. A basic example is by producing a note in each that is consumed in the other. This is of course not limited to N=2 batches, but could be any cycle of length N.

This is allowed by protocol at the proof level. However at the mempool level this is a dangerous game to play because this set of batches is only valid iff they all get included in the same block.

I suggest we disallow this. The current DAG based approach disallows this by construction because of the dependency-based selection ensures there are no backlinks. However, if we aren't careful, user batches can easily circumvent this. We need to either severely limit the external dependencies of user batches (e.g. can only reference committed state), or inspect the DAG to ensure no cycles are introduced.

Problem: existing txs

Should user batches be allowed to include existing transactions? And similarly, should transactions be allowed to submit after the batch. aka should we allow transactions to be Naked(ProvenTransaction) | UserBatch(TransactionHeader) | Both(_,_).

If we allow Both then the implication is that if the user batch reverts, then any transactions within this batch which were Naked should remain in the mempool if valid.

[wip...]

[PhilippGackstatter]

Problem: cyclic batch sets

As we've discussed in our call, there are likely valid use cases where a newly arrived batch A depends on an inflight batch B. And for that reason we allow batches to consume unauthenticated notes, i.e. ones that are not yet committed on chain. They are authenticated or erased at the block level. This may require a different way to select batches for inclusion in a block than currently (but I don't know those internals).

Allowing batches to reference committed state only may be too limiting, as you said elsewhere. But I agree that we don't need to allow batch B to also depend on batch A, i.e. a cyclic dependency, so rejecting such batches seems fine to me.

Problem: existing txs

My gut reaction is to disallow batches to reference existing transactions. As we've discovered in the call, this would allow a user to maliciously submit a transaction they know has been included in a batch, before the batch is submitted. That would cause the entire batch to be rejected then. Maybe that is fine initially, but longer-term that seems like a pretty bad attack vector. So it seems like allowing a user batch to reference any kind of transaction would be best.

If we allow Both then the implication is that if the user batch reverts, then any transactions within this batch which were Naked should remain in the mempool if valid.

Would it be possible to change the TransactionGraph to consist of DependencyGraph<TransactionId, TransactionKind> where:

pub enum TransactionKind {
    AuthenticatedTransaction(AuthenticatedTransaction),
    TransactionHeader(TransactionHeader)
}

• When the node selects a batch, it only considers TransactionKind::AuthenticatedTransaction for inclusion (because it doesn't have the full transaction data for the TransactionHeader variant).
• When a user batch comes in, which contains a bunch of OrderedTransactionHeaders, insert all unknown transactions into the graph, or if they exist as AuthenticatedTransaction, mark them as processed/pending/... When the batch reverts, the TransactionKind::AuthenticatedTransaction (aka existing transactions) are marked as available again, and the TransactionKind::TransactionHeader are purged from the graph.

This is probably too simplistic, but that's one idea to abstract over a) transactions submitted directly to the node and b) transactions submitted as part of a batch.

[Mirko-von-Leipzig]

When a user batch comes in, which contains a bunch of OrderedTransactionHeaders, insert all unknown transactions into the graph

A problem is that transactions in a user batch have no absolute ordering wrt note creation & consumption. This breaks the transaction dependency graph completely as they cannot be inserted in a DAG. A solution to this is treating the batch as an atomic unit already in the transaction graph. A side effect is that such atomic batches would not be able to include "naked" transactions.

[Mirko-von-Leipzig]

I'm starting to think the only proper way is to have a single graph where transactions/nodes can be combined into a batch node, and notably/difficultly ungrouped into transactions if the batch reverts again.

[PhilippGackstatter]

A problem is that transactions in a user batch have no absolute ordering wrt note creation & consumption.

I think I have a rough idea what you mean, but can you give an example where this creates problems?

I'm starting to think the only proper way is to have a single graph where transactions/nodes can be combined into a batch node, and notably/difficultly ungrouped into transactions if the batch reverts again.

Yeah, that's roughly what I was going for with my suggestion, basically abstracting over transactions and batches. But maybe this collapsing and expanding is necessary. In any case, it feels like it should be possible to abstract over txs and batches, since it should be possible to consider a batch as a "transaction" that modifies multiple accounts. I suppose that abstraction leaks when it references existing transactions 😕

[Mirko-von-Leipzig]

I think I have a rough idea what you mean, but can you give an example where this creates problems?

If you have a user submitted batch with co-dependent transactions a <-> b, and then these actually get submitted as individual txs, and the batch reverts, then you're left with a dependency cycle 🤷 You could probably get fancy and do cycle analysis in these situations.

You also cannot really treat them the same as the naked transactions, since all txs in a specific batch can only get marked as processed once all of their parents have been processed. They are effectively an atomic unit from the dependency perspective.