Allow users to submit proven batches

[Mirko-von-Leipzig]

Originating comment:

We could allow people to build and submit their own batches. End users are unlikely to do that, but apps might. For example, if I'm running a CLOB, I could collect transactions from users, put them all into a batch (which supposedly would erase a bunch of notes, and give me fees), and send the proven batch to the node.

[Mirko-von-Leipzig]

Architecturally we aren't really setup for this at the moment because our DAG is split into separate transaction and batch DAGs.

Whether we need to restructure will depend on the interplay between a user-batch and normal transactions. The issue is that normal transactions can then build on-top of these erased transactions from the user-batch and we don't have a way of modeling that with separate DAGs.

Essentially we would need to erase the difference between transactions and batches - they all just become nodes in a single DAG, where batches are an overlay on existing transactions.

There may also be a different perspective, e.g. a transaction is just a smaller "unproven batch" which may be aggregated into larger batches. While this makes sense from a graph perspective (nodes amalgamating into a larger node), coding this up will be difficult because pointers/references/indices will become invalid if we're not careful with our abstractions.

[Mirko-von-Leipzig]

What's the difference between a user-batch which erases its transactions, and a single transaction aggregating them all? The latter would of course require allowing transactions to affect multiple accounts.

[bobbinth]

There a couple of use cases I can think of:

1. There are multiple accounts involved and we want to perform updates "atomically." This may even be extended to transactions which would not be accepted into the mempool individually (e.g., transaction A produces not x and consumes note y, and transaction B produces note y and consumes note x).
2. We want to process transactions faster than blocktimes would allow. That is, some app could be collecting transactions directly from users and making the results (i.e., output notes) immediately available to its users. This then would form transaction dependency chains (e.g., transaction C builds on the results of B, which builds on the results of A etc.), and the app operator(s) would batch all of these transactions together (this system does create a risk that if the user invalidates a transaction early in the chain somehow, then the entire chain would be invalidated, but there may be some ways of dealing with this).

[Mirko-von-Leipzig]

Is there a world in which we have them all be the same thing? As in, a batch is actually just a transaction made up of erased transactions. Or maybe a transaction is just a tiny batch.

I'm more thinking from a node/mempool perspective - if everything is just a transaction then we don't need to distinguish between transactions, batches and user-batches.

If in general a proven tx is attestation that

1. Initial state is correct and in the chain,
2. code was executed,
3. resulting in the final state

then this applies equally to transactions, batches and even blocks - though the latter has some special casing for connecting blocks together.

[bobbinth]

I think the main logical distinction between transactions and batches right now (from the mempool standpoint) is that we can build batches from transactions, but we do not build batches from other batches. If we can somehow erase this distinction, then we can probably treat them the same. Basically, currently we allow only the following transition:

• [tx1, tx2] $\rightarrow$ batch1

But we'd need to support:

• [tx1, tx2] $\rightarrow$ batch1
• [tx1, batch1] $\rightarrow$ batch2
• [batch1, batch2] $\rightarrow$ batch3

Or, more generally, a batch kernel would need to go from verifying aggregation of transactions to verifying an aggregation of transactions and batches. This should be possible, but also probably introduces quite a bit of complexity into the batch kernel (cc @PhilippGackstatter). On the positive side, this would make things quite a bit more flexible overall (e.g., would allow building batches "incrementally": [tx1, tx2] $\rightarrow$ batch1, [batch1, tx3] $\rightarrow$ batch2 or even in concurrently: [tx1, tx2] $\rightarrow$ batch1, [tx3, tx4] $\rightarrow$ batch2, [batch1, batch2] $\rightarrow$ batch3 ).

One other consideration here is how this would affect the fee mechanism (it might not). So, we should probably figure out fee mechanism first, and then see how this fits into it.

[PhilippGackstatter]

Interesting idea! I think if we have the choice of handling something outside or inside the VM, then outside would be preferable unless we can support something new with this (like concurrent batch building, but see below). This is just because it is way easier to write logic in Rust than in MASM.

One question I have is whether the cost of ZK proving make building batches incrementally/concurrently actually useful in practice? If I build batch1 from tx1, tx2 and batch2 from tx3, tx4 each of them has to be proven individually and then the merged batch3 build from batch1 and batch2 must verify and prove again. Isn't that a lot of overhead? I realize these are just small-scale example, but even at large scales (hundreds of transactions), isn't the cost of proving rather significant?

then this applies equally to transactions, batches and even blocks - though the latter has some special casing for connecting blocks together.

Yes, as you mentioned, I don't think this applies to blocks since, contrary to transactions or batches, they are a global state update. They update the chain MMR, nullifier tree and account tree, all of which are global data structures.