Fee mechanism

[PhilippGackstatter]

We need a fee mechanism in Miden and this issue is the start of a description of it.

As mentioned here (#525 (comment)), the mechanism is intended to be multi-dimensional and depend on a number of parameters:

• Number of cycles it takes to execute the transaction.
• Number of notes consumed by the transaction.
• Number of notes produced by the transaction.
• Total size of produces on-chain notes.
• For on-chain accounts: size of state delta resulting from the transaction.

On the implementation side a transaction must be able to specify how it wants to pay its fees. One idea from @bobbinth was to have a procedure in the transaction kernel which users can call, likely from the transaction script, and pass a fungible asset. The fees will be payed with this fungible asset. The asset must be produced as a public output of the transaction kernel next to the current outputs [OUTPUT_NOTES_COMMITMENT, FINAL_ACCOUNT_HASH]. Presumably, this asset would be continue to be processed by the operator in the block kernel an, for example, moved to their account's asset vault.

The epilogue invariant that checks that no net asset creation or destruction happened must take this into account.

Open Questions

• How are fees set? If I understood correctly, we want to take EIP-1559 as inspiration and have a base fee and set it based on the activity on the network in the previous block(s). We may or may not want a priority mechanism as well.
  • Is it important that this base fee does not change too frequently so clients/wallets can assume a fixed value for at least some window of time such that, for example, their transactions do not become invalid too quickly in case the base fee increases? It's also a concern if transaction proving takes some non-trivial amount of time - if the base fee were to change too frequently it would invalidate those slow transactions as well. This is depends on whether we want users to be able to pay exactly the base fee and nothing more or if users are pretty much always expected to pay at least the base fee and a little on top.
• What happes to fees: Are they burned or are they given to the operator? This depends on how we want to incentivize operators, but perhaps while we have a single operator we may not need to think too much about this mechanism and have a temporary one in place like just giving the fees to the operator as a reward.
• Is "Number of cycles it takes to execute the transaction" relevant for local transactions because the proof size is dependent on the number of cycles (even though not linearly)?
• What would the kernel validate about the asset, if anything? I don't recall where I read it but I think the idea was that whatever asset the (or a) Miden operator accepts could be used to pay fees. In that case I assume the kernel could not validate much about the user-provided asset since how the base fee converts to different assets would not be known to the TX kernel.
• For network transactions how is an operator protected from DOS attacks of transactions that produce an invalid asset to pay fees from (e.g. no or too little fees, incorrect asset type, ...). A related question is how do the operator or user estimate how much fees to attach to or require from a transaction so that it passes the minimum threshold? A user could dry-run a transaction locally to estimate it. But an operator might not be able to without it becoming a DOS attack vector.
• I have yet to read through Gas fee model miden-vm#248 fully but it seems relevant at least so I just wanted to add it as context to this.

[bobbinth]

Thank you for the great write-up! This covers pretty much everything. A few comments below:

How are fees set? If I understood correctly, we want to take EIP-1559 as inspiration and have a base fee and set it based on the activity on the network in the previous block(s). We may or may not want a priority mechanism as well.

The general mechanism would be the same as on Ethereum: we define "base" level of resources and if a given block consumes more resources the base fee increases, but if a block consumes fewer resources, base fee decreases. For example, let's say we set the base for the number of output notes at 256 per block. If a block produces 512 notes, the fee per note will increase in the next block (the exact parameters TBD).

Is it important that this base fee does not change too frequently so clients/wallets can assume a fixed value for at least some window of time such that, for example, their transactions do not become invalid too quickly in case the base fee increases? It's also a concern if transaction proving takes some non-trivial amount of time - if the base fee were to change too frequently it would invalidate those slow transactions as well. This is depends on whether we want users to be able to pay exactly the base fee and nothing more or if users are pretty much always expected to pay at least the base fee and a little on top.

On Ethereum, the base fee can change by at most 12.5% from block to block (and this is the worst case if a block consumed 100% of allowed gas). We can use something similar or come up with a different value (but would probably need to think through the rationale).

What happens to fees: Are they burned or are they given to the operator? This depends on how we want to incentivize operators, but perhaps while we have a single operator we may not need to think too much about this mechanism and have a temporary one in place like just giving the fees to the operator as a reward.

On Ethereum, the base fee is burned and the "tip" part of the fee goes to the operator. In our case, the "tip" would be w/e remains after the base fee is satisfied. I think the tip can always go to the operator, but with the base fee we could have the following options:

1. The base fee is burned.
2. The base fee goes to the operator.
3. The base fee goes to the batch builder.

In the centralized setting, the operator and batch builders would be the same - so, options 2 and 3 are basically equivalent.

Is "Number of cycles it takes to execute the transaction" relevant for local transactions because the proof size is dependent on the number of cycles (even though not linearly)?

Yes, but the dependency is logarithmic. For example, it takes a bit more effort to validate a proof of 2^16 cycles vs a proof for 2^20 cycles - but the difference between these is like 10%.

What would the kernel validate about the asset, if anything? I don't recall where I read it but I think the idea was that whatever asset the (or a) Miden operator accepts could be used to pay fees. In that case I assume the kernel could not validate much about the user-provided asset since how the base fee converts to different assets would not be known to the TX kernel.

In the long run, we'd probably enforce something like that it is a valid (and maybe fungible) asset. In the short run, we'd probably dictate a specific asset (e.g., POL).

For network transactions how is an operator protected from DOS attacks of transactions that produce an invalid asset to pay fees from (e.g. no or too little fees, incorrect asset type, ...). A related question is how do the operator or user estimate how much fees to attach to or require from a transaction so that it passes the minimum threshold? A user could dry-run a transaction locally to estimate it. But an operator might not be able to without it becoming a DOS attack vector.

I think there are two parts here:

1. How do we protect operators from DOS attacks regardless of fees (i.e., a note script could fail at the last moment)?
2. How do network transactions pay fees?

DOS attacks for network transactions are still an open question. A while back we discussed it in #18 - but some things may have changed since then. One mitigating circumstance is that the attack is not "free" - i.e., a network transaction consumes notes which are already on-chain - and so, someone had to pay to put these notes there. Though, I think this is a relatively weak defense.

The second point also needs to be flashed out in more detail. One approach could be to have the account against which the notes are executed pay the fee (i.e., the account would expose a procedure for this). This procedure could calculate the fee based on the current base fee levels - and so, it may make sense to record base fee levels in a block header somehow.

---

One other open question which I think is important to think through is: how do fees work in the context of transaction batches? Specifically, batches are atomic and so we either include all transactions from a batch into a block or none. Thus, from a block's stand point, the fees are collected per batch rather than per transaction. And the issue is that ideally we don't want to put a transaction that pays high fees relative to the resources it consumes with a transaction which pays low fees into the same batch. But not sure if there is a good way to enforce it.

[bobbinth]

One other open question which I think is important to think through is: how do fees work in the context of transaction batches? Specifically, batches are atomic and so we either include all transactions from a batch into a block or none. Thus, from a block's stand point, the fees are collected per batch rather than per transaction. And the issue is that ideally we don't want to put a transaction that pays high fees relative to the resources it consumes with a transaction which pays low fees into the same batch. But not sure if there is a good way to enforce it.

One potential way to address this is to "anchor" each batch to some block already existing in the chain which is not too far from the tip. Then, transactions in the the batch would need to satisfy the base fees of the referenced block. The delta between the anchored block and the chain tip could be pretty low (e.g., 8 blocks). If a batch references a block which is bigger than this delta, it cannot be included in the chain.

This still leaves the following undesirable effects:

1. The tip part of the fee is still aggregated across transactions included in a batch.
2. There is some lag introduced between the current base fees and the base fee paid by a given transaction because it was referencing a block from the past.
3. Batches become invalid after some time - though, maybe that's not actually a bad thing.

[PhilippGackstatter]

a network transaction consumes notes which are already on-chain - and so, someone had to pay to put these notes there

Wouldn't this still allow an attacker to post many transactions that consume those notes but fail close to the end of execution to make the node/batch builder waste cycles on failing transactions?

Saw this in #18:

Forcing the user to pay fees even for failed transactions. Not clear how we can do this yet.

Indeed, this would be ideal. Other chains require the fee to be known "upfront" so to say. For example in Sui you need to attach a "gas object" that you own to the transaction from which the fees will be paid, and the fees will be deducted from it whether the transaction fails or not.
So I was thinking the transaction creator must provide the fee asset before any actual note script processing begins, so that this execution is paid for no matter what happens later. So basically a very early transaction script (or something like that) so that if the fee asset is invalid for some reason, execution aborts at this early point already. Something like that would still allow the fee to be provided programmatically, allowing for some flexibility here (e.g. sponsored transactions). This would be a pretty effective way to prevent DOS attacks.

Although after writing this I've realized that it's a problem here that there is no separation between the transaction kernel and note scripts in terms of aborting. I.e. if a note script fails and aborts, the kernel does too, right? So we would not get to finalize_transaction and thus could not produce a transaction proof which would allow the batch builder to collect the fee regardless of execution success or failure. So I might be on the wrong path with this. We would basically have to be able to prove that a transaction failed and that this allows the executor of the transaction to deduct a fee from some asset (e.g. from the account).

Specifically, batches are atomic and so we either include all transactions from a batch into a block or none. Thus, from a block's stand point, the fees are collected per batch rather than per transaction. And the issue is that ideally we don't want to put a transaction that pays high fees relative to the resources it consumes with a transaction which pays low fees into the same batch. But not sure if there is a good way to enforce it.

Why do we want to enforce it in the first place, instead of encourage it? We don't want to put high and low fee transactions into the same batch because then the batches' fees and tips will average out on those transactions, meaning that the batch won't be as likely to be included as a batch containing just high-fee transactions - is that the motivation? Isn't this best left as an optimization problem for the batch builder, which is what I mean by "encourage"?

Sponsored Transactions

I'm also wondering if we have to design for transaction sponsoring, i.e. how can transactions be sponsored by a third party? Even though we have client-side execution, local transactions still incur a fee, and for many use cases transactions (local or network) may want to be sponsored, because the transaction creator might not have gas tokens themselves and/or might not want to own tokens for legal reasons, so sponsoring seems essential in such cases.

The first idea that came to mind was that a gas sponsor could create many notes ("gas notes") with fungible assets containing the gas token. A user would ask the sponsor for a gas note and create their transaction with the gas note to pay the fee from. The sponsor provides a signature for the gas note which allows the user to consume a certain amount from it, according to the note script, which is defined by the sponsor. The note script would create a new note out of the remaining gas tokens after the gas fee is paid. There may be a circular dependency here between creating the transaction on user-side and giving the sponsor the transaction to produce a signature for its node (haven't thought it through in detail), but from a high-level it looks reasonable. A downside is that the gas notes must be "locked" on the sponsor side to prevent handing it out to different users, and I recall this being a tricky approach to get right from previous work.

[Mirko-von-Leipzig]

Although after writing this I've realized that it's a problem here that there is no separation between the transaction kernel and note scripts in terms of aborting. I.e. if a note script fails and aborts, the kernel does too, right? So we would not get to finalize_transaction and thus could not produce a transaction proof which would allow the batch builder to collect the fee regardless of execution success or failure. So I might be on the wrong path with this. We would basically have to be able to prove that a transaction failed and that this allows the executor of the transaction to deduct a fee from some asset (e.g. from the account).

This is in part why Starknet had the huge cairo -> Sierra code migration. To allow for provable failure, motivated largely by collecting fees from aborted transactions. I think at the time roughly 80% of transactions were invalid and being rejected post-execution. These often weren't even malicious; but simply bad dApp logic, poor fee estimation mechanisms, or fee fluctuations on L1. Effectively this meant that sequencer throughput was 5x from what was seen on-chain.

What Sierra does is essentially turn every panic into a Result, making all branches provable. Or alternatively, wrapping the code in a try-catch.

Gas remaining checks are also injected intelligently, allowing the kernel to abort once gas has been depleted in a provable way.

[bobbinth]

a network transaction consumes notes which are already on-chain - and so, someone had to pay to put these notes there

Wouldn't this still allow an attacker to post many transactions that consume those notes but fail close to the end of execution to make the node/batch builder waste cycles on failing transactions?

This wouldn't be a problem for the batch builder because by the time we get to the point of putting transactions into a batch, the transactions would be individually proven (and so they would be valid).

It would be a problem for building a single transaction which consumes many notes against a single account where some note may fail after a bunch of notes have already been executed. This is a more general problem though (executing a note may fail for legitimate reasons) and to handle it robustly we probably need to implement "checkpointing" in the VM. This would allow us, in case of a failure, to roll-back the VM state to some previously set check point without having to re-run the whole program from scratch.

Indeed, this would be ideal. Other chains require the fee to be known "upfront" so to say. For example in Sui you need to attach a "gas object" that you own to the transaction from which the fees will be paid, and the fees will be deducted from it whether the transaction fails or not. So I was thinking the transaction creator must provide the fee asset before any actual note script processing begins, so that this execution is paid for no matter what happens later. So basically a very early transaction script (or something like that) so that if the fee asset is invalid for some reason, execution aborts at this early point already. Something like that would still allow the fee to be provided programmatically, allowing for some flexibility here (e.g. sponsored transactions). This would be a pretty effective way to prevent DOS attacks.

Although after writing this I've realized that it's a problem here that there is no separation between the transaction kernel and note scripts in terms of aborting. I.e. if a note script fails and aborts, the kernel does too, right? So we would not get to finalize_transaction and thus could not produce a transaction proof which would allow the batch builder to collect the fee regardless of execution success or failure. So I might be on the wrong path with this. We would basically have to be able to prove that a transaction failed and that this allows the executor of the transaction to deduct a fee from some asset (e.g. from the account).

I think the problem is actually a bit broader here: it is very difficult to tell whether a note execution fails for a legitimate or illegitimate reasons. For example, let's say that we have a note which can be consumed only after block x. If the node tries to consume it before block x, the note script will abort - but I would argue the creator of the note should not be penalized for this (e.g., by losing some upfront fee).

But also, this is a problem only for notes where the node cannot check "statically" (i.e., without execution) if a given note can be applied to a given account. For example, for P2ID and P2IDR notes, no execution is needed to figure out under which conditions a note can be applied to an account.

Maybe a long-term solution here is for the node to somehow analyze incoming notes intended for public execution (based on note tags) to see under which conditions they can be executed. This will will probably limit how complex such notes can get though.

The first idea that came to mind was that a gas sponsor could create many notes ("gas notes") with fungible assets containing the gas token. A user would ask the sponsor for a gas note and create their transaction with the gas note to pay the fee from. The sponsor provides a signature for the gas note which allows the user to consume a certain amount from it, according to the note script, which is defined by the sponsor. The note script would create a new note out of the remaining gas tokens after the gas fee is paid. There may be a circular dependency here between creating the transaction on user-side and giving the sponsor the transaction to produce a signature for its node (haven't thought it through in detail), but from a high-level it looks reasonable. A downside is that the gas notes must be "locked" on the sponsor side to prevent handing it out to different users, and I recall this being a tricky approach to get right from previous work.

I think this should work, but agree that the user is basically relying on the sponsor not to "double-use" the note with someone else.

Another possible solution in the long run is to allow transactions to pay fees in any asset. Under this design, batches would still need to pay fees to the block in the native token, but transactions could pay fees to the batch in anything. It then would be the job of the batch builder to convert the fees paid by the transaction into w/e fees are needed to make the batch go through.

To give an example, let's say the native fee is POL and I want to pay transaction fee in USDC. I would include some amount in USDC as a fee with my transaction. The batch builder in the process of building the batch would pocket this USDC fee and would put up POL that would be necessary for including the batch into the block. Here again we run into the issue of "averaging fees across all transactions in a batch" though.

Specifically, batches are atomic and so we either include all transactions from a batch into a block or none. Thus, from a block's stand point, the fees are collected per batch rather than per transaction. And the issue is that ideally we don't want to put a transaction that pays high fees relative to the resources it consumes with a transaction which pays low fees into the same batch. But not sure if there is a good way to enforce it.

Why do we want to enforce it in the first place, instead of encourage it? We don't want to put high and low fee transactions into the same batch because then the batches' fees and tips will average out on those transactions, meaning that the batch won't be as likely to be included as a batch containing just high-fee transactions - is that the motivation? Isn't this best left as an optimization problem for the batch builder, which is what I mean by "encourage"?

Yeah, maybe that's not a bad idea but I haven't thought through the potential implications. For example, would this allow batch builders to include their (or someone else's) transactions into the batch "for free"? And is that a bad thing?

[bobbinth]

I think one thing so far that seems fairly certain is that we should update transaction kernel outputs to look something like this:

[OUTPUT_NOTES_COMMITMENT, FINAL_ACCOUNT_HASH, FEE, tx_expiration_block_num]

Where FEE is the asset that the transaction is going to pay in fees.

[PhilippGackstatter]

I have one question about the block kernel and it seems to be related to fees (if not, we can continue the discussion elsewhere too). The batch kernel implements this "note erasures" mechanism by which a note created by a transaction in the batch which is also consumed as an unauthenticated note by another transaction is erased in the sense that it doesn't appear in the input notes commitment or the output notes SMT.

Should the block kernel implement the same mechanism? Technically it would be possible to track inputs and output notes across all batches, but I wonder if this is useful from a "protocol perspective".

Incentive for unauthenticated notes on batch-level

I basically wonder how likely it is that this mechanism would be used in the block kernel in the first place.
Presumably, the number of input notes consumed and the number of output notes created by a batch will be a parameter determining the fees that the batch would have to pay to the block creator (aka operator).
If that's true, then batch builders are incentivized to build batches that (among other optimization parameters) maximize the number of unauthenticated notes that get erased. This is because notes that are erased as described above would not be part of the input notes commitment of a batch and don't appear in the output notes either, so they don't increase the fees of the batch.

So batch builders are incentivized to build batches in such a way, as it maximizes their rewards. Hence I assume they would rarely or never defer "note erasure" to the block kernel.

• One edge case might be that they "see" an inflight batch that creates a note that one of the transactions in the mempool consumes, but this seems pretty theoretical and impractical.
• It could also happen by accident that one batch creates and another batch consumes the same note, but also, rather unlikely?
• If a transaction creator wants to make use of the "note erasure" mechanism they will create the transactions and send them off at the same time to increase the likelihood that they're included in the same batch. There might even be a direct way for transaction creator's to communicate with batch builders in which case it would be basically certain.

Which is all to say, that it seems somewhat unlikely that "note erasure" would be used a lot in the block kernel. Overall, that raises the question whether it makes sense to implement this feature in the block kernel? Or am I missing an obvious common case?

One other question this brings up is why transaction creator's would make use of unauthenticated notes in the first place, but that's another thing to discuss.

[Mirko-von-Leipzig]

One other question this brings up is why transaction creator's would make use of unauthenticated notes in the first place, but that's another thing to discuss.

This just happens naturally when you submit multiple sequential transactions - I imagine this would happen all the time? So long as the transaction is accepted by RPC the caller either has to wait until it is onchain (latency), or just proceeds as if the transaction will be placed and submits the next one.

Which is all to say, that it seems somewhat unlikely that "note erasure" would be used a lot in the block kernel. Overall, that raises the question whether it makes sense to implement this feature in the block kernel? Or am I missing an obvious common case?

This will happen even in the single batch producer scenario just due to timing (iiuc). Batch gets built and sent off for proving, next transactions rolls in and would have been optimally included in the prior batch but alas.

This also means we're speculating that note erasure will be a major optimal strategy.

[PhilippGackstatter]

This just happens naturally when you submit multiple sequential transactions

Mh, could be. Maybe I can't think of the right use cases.

This will happen even in the single batch producer scenario just due to timing (iiuc). Batch gets built and sent off for proving, next transactions rolls in and would have been optimally included in the prior batch but alas.

That's a good point, thanks. Yeah that does seem like a common enough case for it to make sense to include note erasure in the block kernel.

[bobbinth]

Yes, "note erasure" at the block level is possible (of the reasons discussed above) - so, ideally, we should support it. The only reason maybe not to consider this is the potential complexity. That is, if the process of figuring out which notes cancel out adds too much complexity to the block kernel, we could consider making simplifying assumptions (at least for now).

One thing to note, by delegating note authentication to the batch/block producers, the users give up some privacy. Specifically, they reveal exactly which notes are being consumed in a given transaction (though, the contents of the notes could still remain private).

[PhilippGackstatter]

There are a lot of interesting resources on multi-dimensional fee design. For example:

• https://www.youtube.com/watch?v=J_BkdDOK8hg
• https://medium.com/aptoslabs/exploring-multidimensional-gas-markets-on-aptos-a-new-frontier-for-resource-management-95ca34278664
• https://vitalik.eth.limo/general/2024/05/09/multidim.html

And there are many others. There is no optimal solution and so it seems fairly likely that we will not come up with the ideal solution in the first implementation.

Transient and Non-Transient Costs

Still, one goal I think would be to make sure the design allows for sustainable network operation, even if parameters have to be tweaked. Because of that, on a high-level, what some other networks are doing is to split fees into two categories: transient and non-transient costs to the network.

• Transient costs are one-time costs like CPU, I/O or bandwidth.
• Non-transient costs are continuous costs like storage.

The rationale for this is from the medium post above:

One important distinction in our research is that we separate storage from MD-gas markets. Storage imposes non-transient costs on validators — future validators must also maintain stored data. This makes it unsuitable for the short-term, transaction-level pricing model of MD-gas markets. Instead, storage requires a different market design, one that accounts for the long-term nature of its costs, and ensures fair compensation for future validators as well as current ones.

Examples of where this is/was done:

• SUI: https://docs.sui.io/concepts/sui-architecture/sui-storage, https://docs.sui.io/concepts/tokenomics/gas-pricing
• Aptos: https://aptos.dev/en/network/blockchain/gas-txn-fee
• IOTA: https://github.com/iotaledger/tips/blob/tip47/tips/TIP-0047/tip-0047.md

For public accounts and notes I think this applies to Miden as well since the network has to assume it has to store that data in perpetuity, and so its costs should be covered. I think the SUI model of storage pricing could be interesting to follow, though ideally we'd look at other chains that do this to get a bigger picture. I think the main point is that storage costs are a separate dimension from the transient costs, since it must inherently be priced differently.

This is a good summary of the mechanism (but this is just one possibility):

As previously mentioned, SUI pays for the gas fees and data storage on the network. A potential problem arises, however, when new validators come on chain. Even though the validator is new, it still must pay the storage cost for activity that happened before it was part of the network.
Sui addresses this problem with the storage fund. The storage fund is essentially a cache of SUI that never fully depletes. Each on-chain transaction that adds data to the chain includes a fee for storage, which the protocol adds to the storage fund. The storage fund itself essentially has a stake in the network, so it collects rewards based on that stake, just like every other on-chain stakeholder. The protocol then regularly distributes those storage fund rewards to Sui validators to pay for storage. In this way, new validators to the network get paid for storing data from past transactions.
https://docs.sui.io/concepts/tokenomics#storage-fund

What do you think about this on a high level (the exact mechanism in Miden is tbd)? I mainly wanted to bring this up here so that, if you roughly agree, we can exclude this topic for this task. So at first, I would go for fees for transient costs which seems closer to what this issue is about and that way it's a slightly more managable task.

[PhilippGackstatter]

EIP-1559 in Miden

In EIP-1559 there are basically three parameters:

• the base fee, which is some amount of the fee token (gWei in Ethereum) that must always be paid by transactions to be included in a block,
• the tip, which is some amount of the fee token, that should be paid on top of the base fee,
• the max fee, which is some amount of the fee token, that should at most be paid in total (base fee + tip).

Users specify the tip and the max fee for a given transaction, and the base fee is protocol-defined. While building a block, if the base fee of the last block plus the tip end up exceeding the max fee, the transaction is not included. This gives users the ability to set a limit on the transaction fee they are willing to pay.

One of the tricky things with adapting EIP-1559 directly to Miden is that so far we said a transaction should pay an arbitrary asset as an output of the transaction. This is processed by the batch builder who will convert this into the fee token (let's say POL). The question is: How should a transaction creator determine the amount of the fee asset and can they specify an equivalent of "max fee"?

A previously mentioned approach could be:

One potential way to address this is to "anchor" each batch to some block already existing in the chain which is not too far from the tip. Then, transactions in the the batch would need to satisfy the base fees of the referenced block.

The main concern I have with this approach is a scenario like this: Account A creates a transaction with an old reference block and pays 200 POL as the entire fee, based on that reference block's base fee of 190 POL plus a tip of 10 POL. The batch builder computes the base fee from its reference blocks which results in 180 POL, i.e. the base fee has gone down. Now account A has already taken 200 POL out of their vault and because the account may be private, there is no way for the batch builder to refund 10 POL to account A. This is because to refund the account, at least the delta of the account would have to be known. So with this approach, the transaction creator would essentially simply pay 200 POL, i.e. 180 POL in base fee and 20 POL in tip, even though the tip was supposed to be just 10. In other words, transactions cannot specify a "max fee".

A worse scenario would be if the base fee goes up instead and the transaction no longer includes a high enough fee to be included at all.

Now we could argue that the transaction creator should just pick a more recent reference block to avoid this situation and be closer to the chain tip, but I think this would limit Miden's model somewhat arbitrarily. That is, if transactions can be executed against old reference blocks generally, but the only reason to stay close to the chain tip is to be up-to-date on fees, then this feels limiting. It also makes certain scenarios like offline signing harder, which may take some time.

So what I take away from this is:

• UX would be much better if fees did not change very frequently.
• Since we cannot refund accounts, transactions would benefit from the ability to compute rather than estimate base fees.
  • Side note: The tip is always determined by market conditions, but that's fine as long as the base fee can be computed.

Fee computation

In Ethereum, the base fee changes with every block, making the base fee react immediately to changes in demand. In Sui, the "reference price" is set once per epoch (~24h). In Sui then, it is therefore possible to compute the required fee, minus the tip, for a long period of time. One of the major annoyances with fees is unpredictability, as explored above and was one of the motivations for EIP-1559, and if we were to make it possible to compute fees for a stable period of time, that would help the UX a lot. Granted, the presence of the base fee alone makes it generally more predictable to estimate the total fees than in a complete first-price auction. However, I wonder if we can improve this situation further.

Could we instead allow transactions to compute their fee from their reference block? Yes, this would allow them to choose the price to a certain degree, and we could limit this by setting an oldest block limit. For example, we could make the protocol compute a new base fee every 100 blocks:

• Block 0: Fee 100
• Block 100: Fee 120
• Block 200: Fee 140
• ...

Transactions can choose any block tx_block which satisfies: batch_block - tx_block < 100, where batch_block is the reference block of the batch. The main idea here is that there is a sliding window of valid reference blocks that can be chosen, and fees are updated at a fixed interval. This avoids a hard cutoff point, i.e. where a transaction with reference block 199 pays base fee X and can no longer be included in block 201 because its base fee has increased to X+1 in block 200 and the transaction no longer pays enough. This again prioritizes UX over always being up to date with the latest block, since transactions can then always choose between the lower of two base fees.

This overall trades off two sides:

• a hard limit on transaction reference blocks and the ability to respond to changes in demand immediately,
• with the ability to compute fees in transactions and a predictable UX.

Note: How exactly the base fee is updated as well as the exact numbers used here is something that can be discussed later, if this idea should be explored further.

In the scenarios above, this approach would mean the transaction fee payment could work something like this:

• The TX script passes a tip amount and a fee asset to a pay_fee kernel procedure, whose amount is the "max fee".
• In the epilogue, the tx kernel computes the base fee from the reference block and deducts base fee + tip from the fee asset. Whatever is left is put back into the account, or if base fee + tip > max fee, the tx aborts.

That way, the transaction now pays exactly what the user intended or it won't suceed and should be fairly straightforward to work with programmatically. Moreover, the scenario where a transaction pays too much or too little, and cannot be included in a batch is very unlikely, if not impossible, at least when using the "native" fee asset. The only new condition that can happen is that a transaction becomes outdated.

Aside: There is a circular dependency with this approach if we start signing the delta (#1198). That is, we cannot refund the account some asset if the delta was already signed, but we can't compute fees if the most expensive part (signature verification) is not yet completed. Not sure yet how to resolve this, but there may be a way.

Base Fee Burn

As a mostly independent topic, based on this analysis of EIP-1559, I think we should also burn the base fee, even though collusion is not a concern in the centralized setting yet. If we know this will become a problem eventually, then we might as well design it to be compatible with that from the start.

The base fee revenues of a block must be burned or otherwise withheld from the block’s miner, as otherwise the miner could collude with users off-chain to costlessly simulate a first-price auction.
http://timroughgarden.org/papers/eip1559.pdf

(The extended argument is in Section 8.1 of that paper.)