Support Batch fee handling

[mmagician]

We need the batch builder to process the transaction fees. This involves:

• define the accepted batch fee assets (this issue assumes just one asset, the native asset, as a starting point)
• filtering out tx's which don't carry a fee note at all (TX_FEE)
• ensure the fee asset carried is accepted by the builder
• ensure the fee amount covers the tx exec cost
• consume the fee note for itself (batch builder's own account)

For an immediate follow-up, we should extend the list of accepted assets to other assets, and define conversion mechanics.

For future follow-ups, once block kernel implements fee handling, we also need the batch builder to pay enough fees to the block builder to cover the costs of the batch. For now though, the batch builder will just consume all the fees into its own account and not pass them on further.

[Mirko-von-Leipzig]

As discussed offline, our initial MVP can assume that batch building remains centralized for now.

The current implementation has the mempool as the controlling entity; it organises transactions into a DAG from which it hands out batches to the batch builder. The smallest step (imo) from here towards supporting fees, looks as follows:

1. Mempool remains the coordinator.
2. Fee checks are done in the RPC layer, and verified/asserted before the tx enters the mempool.
   • The assumption would be that all txs in the mempool are valid and paid for
   • This assumption breaks for dynamic fees
   • We can follow this up with additional rejections/checks at the batch and block building later
3. Batch builder now also owns a Miden account into which batch fees are accumulated.
4. Batch builder appends a pass-through tx to each batch from which it emits P2ID note containing the fees to its own account.
   • Initially this could be all fees, eventually this would separate into batch/block fee notes
5. Periodically, the batch builder creates a tx which consumes the P2ID notes.

P2ID note consumption

(4) and (5) perhaps require some explanation. We cannot immediately consume the P2ID notes in (4) because doing so would change the batch account's state. This in turn would invalidate all other concurrently built batches and would effectively force each batch account to build at most one batch at a time aka serially, and wait for them to commit before proceeding. One could also build them optimistically, but this also needs to account for batch ordering and coupling which is just complicated.

The solution @mmagician and I came to is to decouple batch creation from batch fee consumption entirely. Tx fee notes are accumulated into a single P2ID note targeting the batch builder's account, created by a pass-through tx. The batch builder defers collecting these, or rather, consumes them outside of the batch building process. The pass-through tx uses a separate account, who's state will never change. This prevents having to handle batch account state changes within the batch building process. A completely separate process can then monitor the chain for these P2ID notes, and consume them periodically.

TL;DR: Two batch builder accounts are required for seamless batch building.

1. Immutable account, used solely as the target of the pass-through P2ID txs created by the batch builder to pay itself.
2. Batch builder $$$ account. P2ID notes get paid here, and consumed by txs created out-of-band/separate process.

The immutable account could even be global and could actually be used for all stateless pass-through txs. I wonder if one could somehow guarantee that its (a) stateless, and (b) immutable? We can of course guarantee this to ourselves by simply deleting the account key but perhaps there is a neat way so that it could be known account?

[Mirko-von-Leipzig]

Re: fee checks. The batch builder cannot currently verify whether a tx includes enough fee money. A tx no longer commits to its cycle, which we could have used to estimate/check this. What alternatives do we have? @PhilippGackstatter @mmagician

[mmagician]

Thanks Mirko! This covers most of what we discussed offline ✅

One detail to clarify: there are two levels for fee checks:

1. verify that the TX_FEE note is present in each transaction (except, perhaps, the batch builder's own pass-through transaction)
2. verify that the fee asset & amount in TX_FEE note covers the actual execution cost

Check 1. can be done very cheaply by inspecting the notes present in a tx, and checking that the note script root matches the known TX_FEE script root. This should definitely be done before the tx reaches the mempool.

Check 2. is more complex, and ties in to what we had discussed a while back when designing the fee mechanism. Whether it's pre- or post- mempool, I think that's for the node team to know best.

The end state is coupled to the block kernel design, and IIRC (I don;t think this has ever been written up? cc @bobbinth) it would be something like:

• figure out how much onchain writes the batch performed (e.g. updating the accounts tree, nullifiers tree etc.). This would eventually be also covered by the batch kernel logic?
• calculate the amount that the batch builder must pay for this batch, as some function of the above number of onchain state writes
• that amount must be paid to the block builder, as part of a BATCH_FEE note (could potentially re-use most of the TX_FEE mechanism). The difference between what the batch builder collected from the users, and what they paid to the block builder, is pocketed by the batch builder.

The problem is that at the moment, in this model, tx fees and batch fees use different accounting:

• tx uses clock count
• batch would rely on chain storage updates

Which could lead to edge cases such as user tx being rejected because it performs a ton of writes, but uses very few cycles. Conversely, users with very high cycle count but no writes would heavily overpay for their tx. Both are bad, but the former leads to complete failure of inclusion (at least via the standard pricing methods).

We will eventually introduce fields to the FeeParameters that account for those writes - but ATM we don't have this, and won't have it before mainnet, so we need to figure out a way how to align the users' measured costs (what the user pays) with the batch builder costs (what the builder actually charges).

The simplest way is for the kernel to include the cycle count as an output of a transaction (I believe we used to have this in the past, but removed to simplify things). Then, the batch builder can inspect it, and, either in the kernel (later) or just in their trusted batch building logic, assert that the output cycle_count x verification_base_fee >= TX_FEE.amount (I'm assuming a single asset for now for simplicity as noted in the issue body)

[PhilippGackstatter]

Questions/Comments:

Batch builder appends a pass-through tx to each batch from which it emits P2ID note containing the fees to its own account.

Could we add the fees to the batch builder's account directly? This avoids one fee collection note per batch.

The problem is that at the moment, in this model, tx fees and batch fees use different accounting:

Why do we need to estimate the batch cost at this point, if batch building remains centralized per the assumption in @Mirko-von-Leipzig's post? I would've though it is sufficient for the batch to check that tx_fee_note.amount() >= tx.compute_fee(). My assumption is batch and block costs are covered by the operator for now.

figure out how much onchain writes the batch performed (e.g. updating the accounts tree, nullifiers tree etc.). This would eventually be also covered by the batch kernel logic?

Related to the above, the account and nullifier trees are updated by the block kernel. The batch builds the BatchNoteTree. So in that sense, the batch doesn't write directly, only indirectly through the block.

A tx no longer commits to its cycle, which we could have used to estimate/check this

Maybe I'm missing something, but I don't think we committed to these before.

ExecutedTransaction.measurements().total_cycles() exposes this, but I guess you need this on ProvenTransaction? For the latter I guess the TransactionVerifier would have to expose this, but I don't think it is accessible. I think https://docs.rs/miden-lifted-stark/latest/miden_lifted_stark/proof/struct.StarkProof.html#method.log_trace_heights contains the data, but not in nicely accessible form. If we need this, we probably need to get a new API exposed in miden-vm somewhere.

[Mirko-von-Leipzig]

Could we add the fees to the batch builder's account directly? This avoids one fee collection note per batch.

We cannot because that changes the account's state which prevents us from doing this concurrently

[mmagician]

ExecutedTransaction.measurements().total_cycles() exposes this, but I guess you need this on ProvenTransaction?

Yes we shouldn't trust the submitted transaction object, only the proven transaction.

But, now that I write this and realize that with training wheels we re-execute each transaction, we could just derive that information ourselves. My initial thinking was that we have to rely on whatever the user submitted (i.e. ProvenTransaction) but since this is not the case, maybe it simplifies a bunch of things @Mirko-von-Leipzig?
Of course, this only holds up now in the training-wheels mode, and we need to find a solution for ensuring sufficient fee coverage later anyway.

[Mirko-von-Leipzig]

This does mean batch builders need to trust the validators, but easy enough for now. I think as long as we work towards a more formal solution, then outsourcing this to the validator set is a good enough trust boundary in the interim

[igamigo]

The immutable account could even be global and could actually be used for all stateless pass-through txs. I wonder if one could somehow guarantee that its (a) stateless, and (b) immutable? We can of course guarantee this to ourselves by simply deleting the account key but perhaps there is a neat way so that it could be known account?

This should be doable through the account's auth component, I believe. We could check the account state was modified in any way and if it was, abort the transaction.

[Mirko-von-Leipzig]

How do pass through transactions pay for themselves?