Batch-level fees

[mmagician]

Summary

We no longer remove tx_fee from the account vault during the transaction kernel, and instead only output fee computation parameters. The batch kernel sums the computed base fees across included txs (batch_fee = sum of all tx_fees), and requires that the batch kernel burns >= batch_fee.

As part of miden-standards, each tx further outputs a single erasable FeeNote carrying any asset of the user's choosing, and with the batch builder set as the NoteRecipient. This is the canonical way to pay fees, but users can get their tx included in the batch by non-standard channels if they wish, such as offchain payments to the builder.

To support FeeNote we enhance (which is also independently useful), the current mechanism of erasable notes. Specifically, we add an optional MustBeErased marker on output notes, which serves two purposes:

• its presence changes the fee computation (not inserted into the note tree, no long-term onchain storage)
• transactions which include non-erased notes with the marker are rejected in the batch kernel*
  This marker, combined with a simple analysis of batch builder incentives guarantees erasure of the FeeNote at the batch level.

End-to-end flow

1. User dry-runs tx and computes tx_fee
2. Wallet converts fee into any builder-accepted asset of user's choice
3. User appends a new MustBeErased-marked FeeNote to their tx, payable to the batch builder
4. Batch kernel erases the FeeNote
5. Batch kernel computes aggregate resource fees as batch_fee, and burns it
6. Builder collects the difference from the Σ FeeNote.asset_i - batch_fee

---

This proposal shares some design principles with the Flashbot bundles, except that it's defined at the protocol layer rather than the application layer.

Background

Today the tx kernel does most of the fee work:

• compute_fee derives the fee from clk and verification_base_fee.
• compute_and_remove_fee builds a fee asset and removes it from the account's vault as the last step; this means the fee is not part of the asset preservation checks.
• The pre-fee delta is what we commit to;
• Currently a single asset (the fee_faucet_id) is accepted.

This shape forces a number of designs that wouldn't otherwise be needed:

• Pre/post-fee delta gymnastics (PR #1705).
• A fee script / fee procedure to support paying in multiple currencies (#2551).
• An open question about how to bind the fee/fee asset to the auth signature (#2765).
• An open question about validating fees in the batch (#1689) and rewarding the batch builder (#1687).
• Erased notes result in fee savings downstream of the transaction kernel (for the block builder, not currently implemented), but nobody passes the savings on to users (i.e. users still end up paying for erased notes as-if they were fully included onchain)

Proposed mechanism

(protocol) Transaction kernel emits a fee summary

compute_and_remove_fee goes away, with only compute_fee left, with the extra simplifications/modifications:

• compute_fee can be called at the end of the epilogue
• compute_fee doesn't care about ESTIMATED_AFTER_COMPUTE_FEE_CYCLES anymore
• calculates tx_fee as:

tx_fee = 
base_fee_cycles x clk_count +
base_fee_note x expected_output_notes +
base_fee_nullifier x nullifiers

• outputs FEE_COMPUTATION_PARAMS = [tx_fee, clk_count, 0, 0] (optionally, replace 0, 0 with expected_output_notes, nullifiers for explicit accounting)

(standards) Every tx outputs one erasable fee note

The canonical way to pay fees becomes a miden-standards FeeNote with the batch builder as the designated recipient.

From a protocol standpoint, the note carries whatever asset the user wants. This flexibility at the protocol level is tightened in practice, because ultimately it's the batch builder who will decide if they accept the transaction in their proposed batch. So the user and the batch builder enter a sort of implicit agreement, which can be as simple as:

• the batch builder publishes: 1) fixed set of accepted assets; and 2) conversion rates from non-fee -> fee assets.

Or more complex such as:

• "When you pay in AssetA, you will be charged premiumA, but when you pay in AssetB, you can underpay the fee because it's sponsored by AssetB issuer"

In any case, the user's tx includes a FeeNote carrying one of these assets with the expectation that the builder includes their tx. This naturally drives competition among batch builders.

The selection of the batch builder happens at the application level, e.g. via the wallet: The Miden Wallet would canonically route the requests to the "best" builder (by some heuristic, e.g. cheapest), with the optionality to manually select builders and how the transactions are communicated to them (e.g. standard mempool vs. private inclusion).

The NoteRecipient is either a fixed builder account or a builder-flexible mechanism. See "Open Questions".

(protocol) Batch kernel accounting

The batch kernel will include the following logic:

1. Reads each included tx's FEE_COMPUTATION_PARAMS.
2. Verifies all unauthenticated notes are erased, just as today. In addition, it enforces that all MustBeErased notes are indeed erased.
3. Tracks the following fee resource aggregates:

total_cycles = Σ clk_count_i over all included txs (erased & non-erased)
total_output_notes = count of entries in OUTPUT_NOTES_SMT_ROOT (post-erasure)
total_nullifiers = count of nullifier entries in INPUT_NOTES_COMMITMENT (post-erasure)

4. Computes the required burn amount batch_fee as:

batch_fee = 
base_fee_cycles × total_cycles + 
base_fee_note × total_output_notes + 
base_fee_nullifier × total_nullifiers

Notice that this cost will be greater or equal to the raw sum of tx_fees, with the potential mismatch coming from total_output_notes >= expected_output_notes (see footnote*).

5. "Burns" the batch_fee amount. We don't yet have a mechanism for this, but it could be similar to today's removal of the fee from the vault - except lifted a layer up, from the transaction to the batch kernel. Another mechanism could be a special BatchBurn note.
6. Builder's profit = Σ assets collected from fee notes − batch_fee.

(standards) Fee estimation

The user picks some fee asset they wish to pay the batch builder in, sets its value to some arbitrary amount (e.g. FeeNote.asset.amount = 1), and dry-runs the tx to compute the real tx_fee cost.
Since the FeeNote is standardized, and assuming that moving an asset from the user's vault is amount-independent, this lets the user obtain the tx_fee exactly, since now compute_fee runs at the very end of the epilogue.

Now that the user knows the exact tx_fee (in native fee asset) that the batch builder must burn as enforced by the batch kernel, they can set the FeeNote.asset.amount = convert(builder_id, tx_fee, FeeNote.asset_id).

(application) Fee estimation

Now as mentioned above, convert function may be builder dependent and is called at the application level. For example:

fn convert(builder_id: BuilderId, tx_fee_amount: AssetAmount, builder_fee_asset_id: AccountId) -> AssetAmount {
    if builder_fee_asset_id == PROTOCOL_FEE_ASSET_ID {
        return tx_fee_amount;
    }

    // fetch the static or dynamic asset conversion data for this builder, and an optional premium, denominated in builder_fee_asset_id
    let (conversion_rate, premium) =  fetch_conversion_data(builder_id, builder_fee_asset_id);
    let converted_amount = conversion_rate * tx_fee_amount + premium;

    converted_amount
}

This might be handled by the client and made very efficient by caching most of the parameters for the "default" choice of the builder.

(protocol) Pricing the FeeNote itself

The FeeNote has its own resource cost, which is taken into account in compute_fee, but without special protocol-level provisions (it's a standard, so any MustBeErased note is priced like this). The FeeNote incurs:

• cycle costs to construct the note
• zero cost for batch note tree insertion - the note is erased within the batch and never enters the block-level note tree.

There is also zero cost per-nullifier for erased notes, but its paying tx would be the consumer, not the producer. So whether or not the note is nullified doesn't directly affect the cost of the tx that outputs this note.

So unlike the current mechanism for removing assets from vault after compute_fee, this proposed mechanism is simpler and doesn't have privileged treatment.

---

Why do we need all this?

1. Multi-asset fees fall out for free. The tx kernel never sees a fee asset, so there's nothing to be opinionated about. The user picks the asset and the builder accepts or rejects the transaction based on the FeeNote following the market dynamics. This subsumes #2551.

2. The tx kernel shrinks. We can simplify/remove/avoid/ a lot of logic such as:

• remove compute_and_remove_fee
• avoid asset-preservation bypass
• avoid pre/post-fee delta split
• avoid implementing fee script
• avoid InsufficientFee error

3. Multi-dimensional fees are natively part of the proposal This proposal assumes per-resource base fees (#1685) with cycle counts and at least one more dimension for number of output notes. With only a single fee like we have today, the design still works but foregoes the "erased notes are cheaper" win, since there's nothing to charge for those slots in the first place. I think the multi-dimensional fee mechanism fits very nicely with this proposal and we can almost get the multi-dimensionality for free.

4. User-defined batches handle their own fees. A user submitting their own batch can simplify things and completely avoid FeeNote, as long as the batch pays its required batch_fee.

5. Erased notes' savings get passed on to the user, which is only possible with a) MustBeErased-marker, or; b) refunds. While a) doesn't address the problem for all erased notes, it covers most use cases (the batch might still erase some notes which the user didn't mark as MustBeErased).

6. #2765 (auth doesn't bind fee) gets simpler. The tx kernel doesn't compute a fee, so there's no fee for a malicious prover to inflate. Cycle-griefing via tx-script swap is still a concern, but the consequence is bounded - the user paid for a fee note ahead of time at their estimated cost, and the inflated cycle count becomes the builder's "problem" to either reject or absorb (not really a problem, it will just be decided by the fee market).

Open questions

• How to encode the NoteRecipient of the FeeNote? Builder-flexible recipients are interesting in their own right and may deserve a separate discussion. Could we come up with a recipient that encodes "any account that owns the batch's coinbase note can claim this FeeNote"? It would couple nicely to the #1687 coinbase mechanism. Other options are "hardcoded to a single builder account?" An OR(...) chain of accepted builders? The Flashbots-bundle analogy suggests the user should be able to target a specific builder; the public-good analogy suggests builder-flexible. Since this is intended to be an application-layer choice, we might be able to support multiple mechanisms here.
• What does burning of the fees at the batch level look like?
• It still doesn't solve refunds (not that other proposals do AFAIK)

Footnotes

*I wonder if we can skip this check in the batch kernel, because the batch-builder incentives would already soft-enforce this. Specifically, if the builder includes the tx with, but fails to erase, the MustBeErased-note, then they will end up paying out-of-pocket for the difference between the tx-kernel-computed lower expected_output_notes and whatever the batch kernel actually computes, which is total_output_notes.

So first of all, the batch builder will want to collect the fee from FeeNote, but if for some reason they decide not to, they will actually be penalized for it.

[PhilippGackstatter]

Thank you for writing this up!

User dry-runs tx and computes tx_fee

I think there is an unfortunate problem we have with this, which is described in more detail in Fee API Approach in 0xMiden/rust-sdk#1956 (comment). In summary, we cannot easily dry-run a transaction to the end to get its number of cycles without providing a valid signature (assuming the standard local wallet use case; not a problem for network transactions). The final transaction would need a different signature, and so the end result is that we have to ask the user for a signature twice, which is bad enough UX that I think it prohibits us from using dry-runs for fee estimation. The way starknet handles this problem was discussed briefly in 0xMiden/rust-sdk#1956 (reply in thread), and may be a solution we could adapt.

It could also be that I'm overstating the problem 😅, but in any case, I think good dry-run support would simplify a lot of things, including enabling very flexible fee estimation and payments as described in your post and good (meaning proportional to the tx) service fees (0xMiden/rust-sdk#1956). Maybe we should investigate the "signature dummy verification" approach.

[bobbinth]

I was thinking about this, and maybe the current approach is over optimized for precision and we could make it a bit more relaxed. Here is the reasoning:

• The only thing that really changes after the auth procedure is executed is the number of cycles. Number of consumed/produced notes, amount of public data produced by the transaction, account mutations are not affected by any code that comes after it (the current fee payment mechanism excluded).
• The number of cycles is likely to be a relatively small component of the overall fee (it is the only component now, but as we add other components, its relevance will greatly diminish).
• Moreover, we actually take a log of the number of cycles (because that's what we care about) and so, the difference between something like 8K cycles and 128K cycles is 30% (i.e., 13 vs. 17) - and not 16x.

So, putting this together, even if we are relatively lax with the number of cycles estimation, the overall fee effect is probably going to be pretty small (e.g., 5% - 10% difference), and I'm not sure all extra complexity is worth this extra precision.

One way we can simplify things is to compute and pay the fee in the auth procedure, and then verify that the computed fee is sufficient in the epilogue. If the fee was estimated incorrectly, we'd need to get a new signature from the user - and that would be pretty bad UX - so, it is important to make such miss-estimations as rare as possible.

To do this, we could provide an estimated number of cycles that we expect to execute after the fee has been computed. For example, if we know that we need to verify a Falcon signature, we could add 128K extra cycles (even though Falcon only takes 70K cycles). If we have a 2 of 3 multisig - we assume that we have all 3 signatures to verify and add 400K extra cycles. This is aggressive, but again, the overall impact on the fee is likely to be under 5% in most cases.

There could still be more sophisticated strategies that make things even better - but I just wanted to illustrate the general idea that maybe we don't need to be super precise with the number of cycles estimation, if this allows us to simplify things.

[bobbinth]

Thank you for writing this up! I like the general direction but I think there are a few things to clarify. I haven't thought this through completely - but a few preliminary comments:

User dry-runs tx and computes tx_fee

As @PhilippGackstatter mentioned, this would be highly non-trivial (especially in the context of network transactions) - but I think there are some workarounds that can make paying fees in the auth procedure possible (see #2899 (reply in thread)).

User appends a new MustBeErased-marked FeeNote to their tx, payable to the batch builder

Making FeeNote payable to a batch builder will complicate things because the user may not know who the batch builder will be. But we also don't really need to make it payable to anyone. The FeeNote could be consumable by anyone and this means that the batch builder will naturally consume it during batch construction.

We also don't really need the MustBeErased marker. The batch builder is naturally incentivized to erase the note - otherwise, the'll have to pay fees for it. So, all we need is to make it easy for the batch builder to consume fee notes during batch construction - and this could be a part of the batch kernel.

Batch kernel computes aggregate resource fees as batch_fee, and burns it

I'm not yet sure if the fees should be burned at the batch level of block level. The way I imagined this originally was that users pay fees to batch builders, and batch builders pay fees to block builders, and then the protocol-level fees are applied at the block level.

avoid pre/post-fee delta split

The pre- and post-delta may still be desirable. Or rather, it would be good to have a mechanism where users can authorize transactions before the fees are taken out. This is especially relevant in the context of multisig accounts: collecting signatures would happen asynchronously and we don't want to have the first signer commit to a specific fee because by the time the last signer signs, the fee requirements may be different.

But I think we may be able to solve this at the standards level rather than at the protocol level.

Every tx outputs one erasable fee note

Is the "one fee note" part something we want to enforce at the protocol level? It would be nice to do so - but not sure if this can be done easily.

---

One other thing we should keep in mind is how this all going to work in network transactions. The auth procedure there is considerably simpler - so, fee estimation should be way more precise. But I think we'd still need to provide some thing like an estimate_fee kernel procedure that would compute what the fee for a transaction would have to be to be accepted but a batch builder under current network conditions.

[mmagician]

the user may not know who the batch builder will be. But we also don't really need to make it payable to anyone. The FeeNote could be consumable by anyone and this means that the batch builder will naturally consume it during batch construction.

A FeeNote that is consumable by anyone could work. This is probably the simplest strategy to address the Open Question #.1 above. I can't think of any attack vector ATM: if someone else tries to consume the FeeNote associated with tx1, then simply tx1 won't be included in the batch as it doesn't pay fees.

But there is an arbitrage vector:

• tx1 includes FeeNote in AssetA
• tx2 snipes tx1.FeeNote, and outputs a combined tx2.FeeNote in AssetB
• both AssetA and AssetB must be in currencies accepted by the batch builder
• but tx2 can take advantage of exchange rate differences (e.g. if they know a builder uses an outdated source), and potentially still make it look like accepting tx2.FeeNote is more profitable to the builder, whereas they profit from arbitrage.
• but maybe this is ok, just market dynamics that leads to more efficient batch builders

The batch builder is naturally incentivized to erase the note

Yes, and I noted as much in the footnote. But the issue is that the user will end up paying more for a non-erasable note than an erasable note (once we have multi-dimensional fees, which we want).
Without the marker:

• user pays for the note as-if it was committed onchain
• but the note is erased at the batch level, and the cost to the batch builder is lower than what the user paid them. The batch builder pockets the difference, and the saving is never passed on to the user.

Is the "one fee note" part something we want to enforce at the protocol level? It would be nice to do so - but not sure if this can be done easily.

No, I would keep this as a standard, rather than enforcing it. It opens the door to alternative tx-inclusion channels, which goes in the direction of Flashbot bundles. It is desirable for private order flow etc. to enable offchain agreements between the user and the batch builder.

I'm not yet sure if the fees should be burned at the batch level of block level.

Sure, I think this doesn't fundamentally change the proposal. I think we could even re-use the FeeNote mechanism and have the batch builder pay the block builder, but other mechanisms are also possible.

[pre/post-fee delta split] But I think we may be able to solve this at the standards level rather than at the protocol level.

I find the split very confusing. While it currently works, it introduces lots of complexity, and if we can avoid the split then I'd very much root for it.

[bobbinth]

the issue is that the user will end up paying more for a non-erasable note than an erasable note (once we have multi-dimensional fees, which we want). Without the marker:

• user pays for the note as-if it was committed onchain
• but the note is erased at the batch level, and the cost to the batch builder is lower than what the user paid them. The batch builder pockets the difference, and the saving is never passed on to the user.

I don't think user over-paying slightly is a big issue. In general, perfectly estimating which notes will be erased and which won't is not going to be possible because it depends on what other transactions someone else could at the same time. So, we need to accept some degree of imprecision.

But we can also make a provision for this in the compute_fee procedure. For example, the parameters could look like so:

#! Inputs:  [num_extra_cycles, SKIP_NOTES_COMMITMENT]
#! Outputs: [fee_amount]
pub proc compute_fee
    ...
end

Where:

• num_extra_cycles is the "cycle buffer" mentioned in Batch-level fees #2899 (reply in thread).
• SKIP_NOTES_COMMITMENT is a commitment to the IDs of output notes for which fees are to be assumed to be zero.

I find the split very confusing. While it currently works, it introduces lots of complexity, and if we can avoid the split then I'd very much root for it.

Agreed - but I do think there is real value in being able to authorize the transaction without committing to exact fees to be paid. For example, we could include max_fee in transaction summary, and then, as long as the actual fee charged doesn't exceed this max fee, the transaction would be able to proceed (this would also address #2765).

We could even maybe use one of the elements of the salt in TransactionSummary for this. It could look something like:

pub struct TransactionSummary {
    account_delta: AccountDelta,
    input_notes: InputNotes<InputNote>,
    output_notes: RawOutputNotes,
    max_fee: AssetAmount, // though, maybe this should be a more abstract unit like Gas
    salt: [Felt; 3],
}

[PhilippGackstatter]

tx_fee = 
base_fee_cycles x clk_count +
base_fee_note x expected_output_notes +
base_fee_nullifier x nullifiers

outputs FEE_COMPUTATION_PARAMS = [tx_fee, clk_count, 0, 0]

I think the transaction's fee must be checked against the fee parameters from the reference block of the batch, not the transaction. Using the transaction's ref block means the tx creator could pick an arbitrarily old block (that satisfies the remaining constraints) that has the lowest fee parameters, but this would prevent dynamic fees from protecting the network.

So, as you alluded to, I think we need to output all the tx fee parameters that the batch needs to compute the transaction's fee: cycle_count, num_output_notes, num_input_notes, ...

I tried to capture (almost) everything that was said and tried to put it into a sequential flow of executing a transaction from start to inclusion in a batch. I'm not sure I ended up with exactly what was discussed, though. In any case, this is how I now think it could work:

Dry Run

• User picks asset X to pay fees in, which they know to be accepted by a batch builder.
• User dry-runs a transaction and sets the to-be-created fee to asset X with amount 1, for dry-run purposes.
• Transaction executes up to the auth procedure, but fails with TransactionExecutorError::Unauthorized(TransactionSummary).
• Let's suppose that this error variant is enriched with the number of cycles tx_aborted_cycles at the time the tx was aborted.
• Client catches this error and estimates the total_cycles by summing:
  • tx_aborted_cycles
  • the estimated cycles of the auth procedure, defined somewhere on the auth component itself.
    • This is different per auth component, but the assumption is that the client knows the account's auth component.
  • the protocol-supplied estimated number of epilogue-cycles.
    • This depends on how many notes there are (i.e. cycles are affected by how many times we need to loop to compute the output notes commitment, and similar things). Initially, this could be a worst-case constant, but we could improve this over time to become a better estimation by taking num output notes as inputs, etc.
• Client passes total_cycles and other required transaction parameters to a compute_fee API that works against FeeParameters from a recent block header for estimation. This results in estimated_fee.

Execution

• Client gets a signature from the authenticator, then runs the actual transaction with the fee designated for FeeNote set to estimated_fee.
• The actual fee note is created as the last action of the tx script or in the auth procedure (see below), using estimated_fee as the fee asset.
• Since we have a valid signature, we get past the auth procedure now.
• Epilogue collects the required fee parameters (cycle_count, num_output_notes, num_input_notes, ...). These are part of the transaction's public outputs (replacing the current fee asset).
  • I think the epilogue does not need to compute the actual fee at all now. The only reason to do so, is to check it against the user-provided fee, but the tx kernel cannot check that the fee in the fee note matches or exceeds the computed fee:
    • The tx kernel does not know the concept of a FeeNote (and shouldn't, I think), and iiuc, we want to leave the kernel agnostic and open for other future mechanisms (which I think is a good idea).
    • Even if it could obtain the fee asset, say 2 USDC, it could not trivially check that these USDC cover the computed fee of say 1000 computation units and 2000 storage units. It would need a conversion mechanism, and since that needs to be user-provided, it defeats the point of a kernel-level check.
  • Since the batch kernel ultimately computes the required fee against the fee parameters from its reference block (which is likely different from the transaction's ref block), the tx-kernel fee check would anyway be an imperfect one. E.g., the tx kernel might accept 2 USDC as the fee, but due to changed fee parameters, the batch requires 2.01 USDC.

Batch

Outside batch kernel

• Batch builder selects a recent enough reference block from which it will use the fee_parameters.
• Batch builder selects transactions based on whether the transaction's fee note contains an asset that matches or exceeds the transaction's required fee, as calculated against the fee_parameters.
  • Assumption: Batch builder also includes transactions which do not technically pay enough fees to cover the fee note, but since it will be erased and it is the batch builder's payment, it includes the transaction anyway. This is essentially the idea of SKIP_NOTES_COMMITMENT. The more general idea here is that batch builders will include the transaction so long as they make a profit, they do not need to check whether the fee note wasn't paid for or something else, it's a transaction-global check.

In batch kernel

• Batch includes the user's transaction and converts the transaction-provided fee asset into the protocol-required one.
  • It does this without further checks since it has previously (i.e. outside the kernel) checked that the transaction contained sufficient fees.
  • This is what supports multi-asset fee payments.
• The batch consumes the fee note of the transaction and so erases it.
• Out of scope: Batch kernel fee check and "passing the fee" to the block.

Open Questions

MustBeErased
The above doesn't take the MustBeErased marker into account. I think the marker would be nice to avoid at the protocol level. Basically, before we introduce it, it would be useful to understand how much savings this would actually bring the user per transaction. My assumption is that a FeeNote is relatively cheap and that we would optimize it as much as possible to keep its cost low. Ideally, we can omit it now, observe fees under real network conditions and introduce it at a later point if savings are meaningful.

Max Fee
I'm not sure how to support max_fee with this either, given that the epilogue doesn't compute the fee, although it could. Even if, would max_fee be specified in protocol-defined computation/storage units or in the actual chosen asset?

Tx script vs. Auth Procedure

Should the tx script or the auth procedure create the fee note? Both can do it theoretically, but there are trade-offs:

• The tx script can be arbitrarily generated by a client, leaving the fee payment fully up to it.
• If the auth procedure does it, then every single auth component needs to support the complexity of fees (in addition to the complexity of auth).
• If the tx script creates the fee note, fees estimated during the dry-run, include the cost of the fee note.
• If the auth procedure does it, it can technically create the note after it has created the tx summary, meaning it can deliberately exclude the fee note from the tx summary, which may have benefits (e.g. async signature collection in multisig contexts).
  • This also naturally supports something like SKIP_NOTES_COMMITMENT: When the auth procedure aborts during the dry-run, the created tx summary naturally doesn't include the fee for the fee note. In the tx script case, we'd have to subtract some amount from the estimated_fee to achieve the same, which would be difficult to estimate.
• The tx script needs to load the estimated fee from advice, and the auth procedure again for inclusion in the tx summary. Ensuring these are the same value must necessarily go through the kernel.

So, there seem to be quite a few benefits to letting the auth procedure handle this, even though gut-feeling wise I'd very much like to avoid bundling fees and authentication.

[bobbinth]

Thank you for writing this up! I agree with many points/conclusions. A few comments from my end:

Should the tx script or the auth procedure create the fee note?

I don't think we need to enforce this. I do anticipate that in most cases it'll probably be the auth procedure, but I can imagine other options as well. For example, I could see a scenario where a note script creates the fee note (e.g., in a case of "pass-through" transactions that don't want to update the account state).

The bottom line is that developers can use different approaches that as appropriate for their specific use cases.

Max Fee

This too can be left to developers (and standards) to decide as appropriate. For example, in a single-sig auth component, there is probably no need for max fee at all. In a multi-sig scenario, this could be useful and there are probably several ways to implement it (most likely enforced by the auth procedure).

Dry Run

I don't think the dry run step is needed (at least in most cases). In cases where the auth procedure handles fee note generation, auth procedure is well-positioned to estimate the free required, and so, can create this note w/o the need to first dry run the transaction.

In other cases, fee estimation logic could be run out of the VM and the fee parameters could be provided non-deterministically.

I think the transaction's fee must be checked against the fee parameters from the reference block of the batch, not the transaction.

Agreed. I would even say that at the protocol level, there is no such thing a "transaction fee" any more. The batch needs to pay a fee to the block, but how the batch gets fees from transactions is a separate concern.

What we do need to provide is a way for network transactions to easily estimate the fee that a batch builder would be willing to accept. In most cases, such estimates would not be precise and such transactions will likely overpay in fees (to make sure they are profitable enough to get included in a block) - but I think that's OK.

I think the epilogue does not need to compute the actual fee at all now.

Agreed. As I mentioned above, the only thing we need to provide is the estimate_fee (or compute_fee) kernel procedure. This would be a "pure" procedure (i.e., would not mutate anything). The benefit of providing this procedure as a kernel procedure (rather than a standard library procedure) is twofold:

• It will be more efficient and the overall surface of the kernel API should be smaller.
• More importantly, the estimation procedure can be updated together with the kernel without breaking user code.

---

Here are a couple of examples of how I imagine the fees to work under different scenarios:

3-of-5 multisig account

• A user runs the transaction, similar to how they do now, to generate a transaction summary. This transaction summary, in addition to what it includes now, also includes something like max_tx_cycles field, and maybe something like a "priority" field (e.g., a numerical value 1, 2, or 3).
  • max_tx_cycles would be set by the auth procedure itself when it builds the tx summary. To do so, it would just take the current number of cycles + some estimated buffer. For example, for a 3-of-5 multisig using Falcon signatures, it would add something like extra 256K cycles (which is a big overestimate).
  • The priority could be provided by the user nondeterministically as args for the auth procedure.
• This summary is then circulated amongst the signers and signatures are collected. Important to note that the signers sign off on both the max_tx_cycles and the priority.
• Once the signatures are collected, the user executes the transaction again. Right after the signature checks pass, the auth procedure does the following:
  • Checks that the num_current_cycles < max_tx_cycles - if not, aborts.
  • Runs estimate_fee kernel procedure. This procedure returns the estimated fee in native tokens.
  • Multiplies the fee by the committed priority - e.g., 1.1, 1.2, or 1.3, for low, medium, and high, respectively.
  • If needed, converts the native token amount into a different asset. This could be done by making an FPI call to an oracle (but there could also be other ways to do it).
  • Creates the FEE note with the asset computed in the above step.
• This concludes the auth procedure, and then the epilogue runs, but it doesn't do anything about fees.

A few notes about this flow:

• The user cannot "inflate" the fee by executing some expensive tx script because of the max_tx_cycles limit.
• The estimate_fee provides the "best-effort" estimate of the fee given "current" network conditions (e.g., conditions of the anchor block), but the user can adjust this estimate by using the priority. This could account for any changes of network conditions in the short term.
• The user also ever-estimates the number of cycles needed by a large margin. The impacts on fees in going to be small (as explained in one of the above comments), but it does mean that the user is unlikely to trip the max_tx_cycles check.

Network account

• Towards the end, the auth_network_transaction procedure would call the estimate_fee kernel procedure. Same as above, this would return the estimated fee in _native tokens`.
• Then the auth procedure would apply some adjustment factor - e.g., 1.2. This factor could be a part of the config of the auth procedure, and could be updatable by the owner of the account. In some cases, maybe this factor could be dynamically estimated based on the nature of the transaction (e.g., by examining the notes that were consumed).
• Then, if needed, the auth procedure would convert the estimate from native tokens to some other token - mostly likely also relying on config of the account + FPI call to an oracle.
• Finally, the FEE note would be created.

[mmagician]

@PhilippGackstatter

[MustBeErased] Basically, before we introduce it, it would be useful to understand how much savings this would actually bring the user per transaction.

Agreed, that's very pragmatic 👍🏼

---

Out of scope: Batch kernel fee check and "passing the fee" to the block.

I think we need this already; it will inform how we do multi-asset fee payments [see below]

In batch kernel

Batch includes the user's transaction and converts the transaction-provided fee asset into the protocol-required one.
It does this without further checks since it has previously (i.e. outside the kernel) checked that the transaction contained sufficient fees.
This is what supports multi-asset fee payments.

The original proposal assumed that the batch builder simply erases the fee-payment notes by consuming them with their account; and that separately, they burn the protocol-required fee asset, enforced in the epilogue of the batch kernel.

I think this leaves the batch kernel much leaner than doing the conversion:

• there's no need to do in-kernel asset conversions (how do you get the price?)
• no need to convert every single FeeNote; instead the batch builder consumes each FeeNote themselves and perform a single burn.

The batch consumes the fee note of the transaction and so erases it.

As written just above - I think it should be the batch builder's account that consumes the FeeNote's, not the batch program itself.

---

@bobbinth

I would even say that at the protocol level, there is no such thing a "transaction fee" any more. The batch needs to pay a fee to the block, but how the batch gets fees from transactions is a separate concern.

Maybe this was implied in your comment, but let me verify that we have consensus: The batch eventually needs to pay a batch_fee equivalent to the cost of all its included transactions. So the batch kernel still needs to be "told" how much each transaction costs in isolation, then sum it up. The way that I imagine a tx "tells" the batch kernel is by outputting FEE_COMPUTATION_PARAMS = [tx_fee, clk_count, 0, 0]. Here, tx_fee is NOT an actual fee asset, but rather some aggregate "base-fee-like" value of clk_count, expected_output_notes, nullifiers, e.g.:

tx_fee = 
base_fee_cycles x clk_count +
base_fee_note x expected_output_notes +
base_fee_nullifier x nullifiers

However, as @PhilippGackstatter pointed out:

transaction's fee must be checked against the fee parameters from the reference block of the batch, not the transaction.

But the tx doesn't know the reference block of the batch - so maybe instead of outputting the aggregate tx_fee, in the tx kernel epilogue we'd instead output the individual components that make up the tx cost:
FEE_COMPUTATION_PARAMS = [clk_count, expected_output_notes, nullifiers, 0]

and then defer the multiplication of those by (batch's reference-block-anchored-)base_fee_cycles to the batch kernel.