Fee mechanism #1217

PhilippGackstatter · 2024-11-15T14:51:39Z

PhilippGackstatter
Nov 15, 2024
Collaborator

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 · 2024-11-16T09:55:19Z

bobbinth
Nov 16, 2024
Maintainer

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:

The base fee is burned.
The base fee goes to the operator.
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:

How do we protect operators from DOS attacks regardless of fees (i.e., a note script could fail at the last moment)?
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.

0 replies

bobbinth · 2024-11-24T00:45:50Z

bobbinth
Nov 24, 2024
Maintainer

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:

The tip part of the fee is still aggregated across transactions included in a batch.
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.
Batches become invalid after some time - though, maybe that's not actually a bad thing.

0 replies

PhilippGackstatter · 2024-11-25T14:23:00Z

PhilippGackstatter
Nov 25, 2024
Collaborator Author

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"?

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:

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.

0 replies

PhilippGackstatter · 2025-03-05T11:59:33Z

PhilippGackstatter
Mar 5, 2025
Collaborator Author

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.)

0 replies

bobbinth · 2025-03-06T08:32:51Z

bobbinth
Mar 6, 2025
Maintainer

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.

I am not against splitting fees into transient vs. non-transient, but the benefit is not immediately clear to me yet (I probably need to think this through a bit more). Basically, we'll need to compensate validators for storing data (though, in Miden case, validators may not need to store much as they would be able to check the validity of blocks by verifying ZK proofs - so, theoretically, we may even be able to have "stateless validators") but why could this not come from inflation rather than storage fund?

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.

I think we could try to be somewhere between Ethereum and Sui. The main issue I see with Sui's model is that in periods of high demand, the fee won't be able to adjust fast enough which would result in a lot of dropped or delayed transactions (i.e., we won't be able to use the fee as anti-congestion mechanism). At the same time, changing the base fee with every block by 12.5% could lead to a very rapid change in fees which would make fee prediction much less accurate. So, what we could do is set this limit to be lower - e.g., a fee can be changed by at most 1% (or some other small value) per block. This may be predictable enough and if a transaction wanted to increase the probability of making it into the block it could pay a slightly higher fee - e.g., paying 25% over the current base fee would guarantee that it would not fall below the base fee for the next 23 blocks.

Overall, I think we could keep the mechanism of setting the fee pretty flexible at the transaction level to accomodate 2 scenarios (this is similar to what you've proposed but there are also some differences):

The user executes a local transaction. In this context, the user should be able to set the fee to w/e they want regardless of the reference block used for the transaction. Maybe something like a pay_fee procedure could be used to do this (we'd need to define how this procedure works and what it accepts).
The network executes a transaction. In this case, the fee would probably need to be set "programmatically" either by note script or account code. To support this, we should allow querying of the base fees associated with the reference block for the transaction (base fees would be a part of the block header). We could provide a convenience procedure in the kernel that would compute the required base fee (e.g., something like compute_required_fee) and then the code could use pay_fee procedure to set the fee for the transaction.

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"?

Yeah, it is not clear to me if there is a good way to support "max fee". My current thinking is that the overall model could work as follows:

One of the outputs of a transaction would be a fee (expressed as a fungible asset), this fee could be specified during transaction execution using one of the two methods described above (maybe there are also other ways to do it). At the transaction level, we do not force the fee consistent with base fee requirements.
When a batch is built, the batch must be anchored not too far away from the chain tip (e.g., maybe within 16 blocks). At the batch level, we enforce that all included transactions satisfy the base fee of the anchor block and the base fee of transactions is burned. w/e remains is treated as a tip part of the fee. So, basically, by the time we build a batch, we are guaranteed that:
- All transactions in the batch satisfy the base fee requirements and can be included in a block if a batch is included in the block.
- The batch can be included in the block as long as it is within a given distance form the chain tip (e.g. 16 blocks) because all transactions have satisfied the base fee.
When we build a block, we just need to check that included batches are within the allow threshold from the chain tip which would automatically mean that their transactions have satisfied the base fee requirements. The block producer then gets to keep the tip coming from the batches (+ maybe some additional reward from inflation).

A couple of open questions:

The incentive for the block producer is pretty clear - they get the tip part of the fee and maybe we'll have other consensus-related reasons for why they'd want to include batches into blocks. By what is the incentive for the batch builders to build batches? (they get neither the base fee nor the tip) It doesn't matter in the centralized setting, but in a decentralized setting there would need to be some clear incentive for why batch builders want to build batches.
How to handle fees paid in "non-native" assets. One potential approach is to leave this responsibility to the batch builder. Basically, a transaction is paying a fee in asset X and the batch builder can decided whether the paid fee is worth it compared to the current base fee expressed in the native assets. In a way, the butch builder could keep the asset X and pay the fee for a given transaction in the native asset. This probably need to be through through a bit more though.

0 replies

PhilippGackstatter · 2025-03-06T16:12:49Z

PhilippGackstatter
Mar 6, 2025
Collaborator Author

Basically, we'll need to compensate validators for storing data

I'm not sure yet what entity exactly would store public account and note data, but I assume those who store it should be compensated for it, to have an incentive for storage in the first place. I don't have a clear picture of Miden post-centralization yet, which makes this a bit difficult.

but why could this not come from inflation rather than storage fund?

It definitely can come from inflation. The storage fund is just one option and inflation is another. My main point was about separating storage costs out from transient costs.

So, what we could do is set this limit to be lower - e.g., a fee can be changed by at most 1% (or some other small value) per block. This may be predictable enough

In my mind, Ethereum's model works best if the "max fee" mechanism is in place. Unfortunately, I don't see a reasonable way to support refunds at the protocol level, unless we calculate the base fee in the transaction.

If we don't want to do this, then indeed the second best option to make things more predictable is to change the "base fee change" parameter, as you mentioned. If we assume a 15s block time in Ethereum and a 3s block time in Miden, then Miden is five times faster than Ethereum. So to get the equivalent "reactiveness" to changes in demand of EIP-1559 in Miden, we would have to set that parameter to 12.5% / 5 = 2.5%. So we could start with something like that, or lower (like 1%) to make things more predictable. In any case, I agree this would be a parameter we could tweak to improve UX at the cost of reactiveness.

Still, this would mean that transactions can technically reference any block, but some block header close to the chain tip would have to be fetched as well to get an up-to-date base fee reference from which to set the transaction's fee (but to be clear, this recent header is used for informational purposes only).

The network executes a transaction. [...] To support this, we should allow querying of the base fees associated with the reference block for the transaction (base fees would be a part of the block header).

Yeah, I think implicitly requiring that network transactions reference a recent block is fine, so that it can calculate the fees in the most precise way possible. I assume such transactions would not be offline signed or in other ways slow from creation to reaching the mempool.

B[ut] what is the incentive for the batch builders to build batches?

I thought that the block builder does not necessarily have to get the entire tip. The batches could be in competition with each other too and keep some of the tip I imagine? Or is there a reason why the entire tip should be paid forward? As long as the batch kernel ensures that the base fee of each included transaction was burnt, there could be a parameter that specifies what fraction or absolute number of the tip the batch should output for the block builder.

Since building a block in Miden is basically an effort supported by the batch and block builder, my initial thought was that if we have some kind of "block reward" it would be split amongst those two. Not necessarily in equal parts, since building blocks requires more infrastructure to be maintained and data to be stored, but technically both could get their fair share of that reward (e.g. from inflation).

How to handle fees paid in "non-native" assets.

This would have to be handled as part of the batch kernel. And this question could be answered in the larger context of how the batch or block builder would receive rewards, since the mechanism for the batch builder's account to receive new funds as part of the batch might use a similar mechanism as how to get some funds from the account "into the batch". Maybe with a regular transaction, or maybe with a more built-in mechanism. I'll think about this.

0 replies

bobbinth · 2025-03-06T19:23:23Z

bobbinth
Mar 6, 2025
Maintainer

Still, this would mean that transactions can technically reference any block, but some block header close to the chain tip would have to be fetched as well to get an up-to-date base fee reference from which to set the transaction's fee (but to be clear, this recent header is used for informational purposes only).

I was thinking this info could be provided in a variety of ways. For example, a wallet provider could have an API to retrieve the current base fee that would not require the user to sync to the chain tip (or download the latest block) to get this info.

I thought that the block builder does not necessarily have to get the entire tip. The batches could be in competition with each other too and keep some of the tip I imagine? Or is there a reason why the entire tip should be paid forward? As long as the batch kernel ensures that the base fee of each included transaction was burnt, there could be a parameter that specifies what fraction or absolute number of the tip the batch should output for the block builder.

Since building a block in Miden is basically an effort supported by the batch and block builder, my initial thought was that if we have some kind of "block reward" it would be split amongst those two. Not necessarily in equal parts, since building blocks requires more infrastructure to be maintained and data to be stored, but technically both could get their fair share of that reward (e.g. from inflation).

Yes, we can definitely split the tip part between the block producer and the batch producer. In fact, we could let the batch producer claim the entire tip from the transaction fees and then decide separately how much of a tip they can include with the batch. This would effectively mean that transactions pay the fee to batch builders and batch builders pay fees to block producers but these two are determined/set separately. But we should probably think though this a bit more holistically in case there are some unintended consequences.

Splitting block rewards is also possible, but we'll need to think about this more carefully so that there no incentive for batch builders to produce empty batches.

Another thing to note is that batch builders could benefit from note erasure since at the time a transaction is created, the user cannot know whether an unauthenticated note will be erased and so would need to cover the base fee associated consuming a note. In case the note can be erased, this fee can then be claimed by the batch producer. Whether this ends up being a material component of batch builder compensation is probably something we won't know until the system is running and we have some "real-world" data.

0 replies

PhilippGackstatter · 2025-03-12T15:05:33Z

PhilippGackstatter
Mar 12, 2025
Collaborator Author

Incentives

Block Producer

We allow empty blocks so the chain can make progress even in the absence of transactions or batches. Block producers receive a block reward (tbd) independent of the block size. If the reward was tied to the block size it would just incentivize the block producer to produce useless transactions and batches themselves to fill it up, in the absence of useful transactions, which would be bad for the network.
The only proper incentive for block producers to fill blocks (usefully for the network) is through tips on batches. That is, including batches with a non-zero tip will result in a greater total block reward (i.e. block reward + sum of batch tips) that the block producer receives than if it produced empty blocks in the presence of batches with non-zero tips.

Including batches comes with more work than an empty block, but the tip should be high enough to compensate for that additional work and the risk that another block producer would produce a block faster (i.e. the uncle risk in Ethereum). Although since there is just a single block producer for now, that is an irrelevant point.

There is also a weak incentive for block producers to have an interest in a functioning network. Although individual block producers may exploit this still for a quick profit, which is why it is weak.

Another weak incentive is that block producers would benefit in tiny ways from burnt fees through overall deflation. So the higher the burnt base fees the better, which is an incentive to include transactions/batches that are not created by the block producer itself, because burning its own fees would be a net loss.

Batch Producer

Contrary to blocks, we don't have to allow empty batches and the current Rust batch kernel already disallows those. So at least one transaction must be included. Batch producers are incentivized to fill batches, i.e. include transactions through the tip of the transaction.
Since batches must themselves give a tip to the block to increase their likelihood of inclusion (and to disincentivize empty blocks on the protocol level), the difference between the sum of transaction tips and the tip for the block must be high enough to be an incentive for the batch producer.

Splitting block rewards is also possible, but we'll need to think about this more carefully so that there no incentive for batch builders to produce empty batches.

Good point, thanks for bringing that up. It seems to me like giving rewards to batch producers would be a problematic incentive and I can't come up with a remedy.

If each batch is eligible for a reward independent of the transaction content, then this would mean that by default blocks would be filled with as many batches a possible and transactions would be as distributed over these batches as possible (e.g. one transaction per batch, and 64 batches per block), since that would maximize the reward of batch and block producers. We don't need to incentivize empty batch creation in the same way as empty block creation, so this does not seem like a useful incentive.

Making the batch reward dependent on the number of transactions would mean batch producers would create useless transactions themselves to fill up their own batches, so this is not a good incentive either.

Because of the aforementioned necessity for the block producer to get a reward independent of block size, we can't incentivize the block producer to maximize the ratio of transactions to batches, or some other similar metric, which would seem like it would have a positive effect on the batch producer to mitigate this above problem.

This is a complex problem, so I might be easily missing something, but at this time I don't see a viable option for protocol-generated batch rewards. The most natural option is for the batch and block producer to split the tips in some way (again, not necessarily in equal parts). I'm not sure how to estimate whether this would be significant enough to incentivize batch and block producers without making transaction tips very high.

Another thing to note is that batch builders could benefit from note erasure

I agree, there should be an incentive for batch builders to erase notes. This implies we should calculate base fees in the batch based on the final number of input and output notes, so the batch producer has to burn fewer base fees than the sum of all transaction's base fees. The batch producer could pocket the excess.

The same may also apply to transactions executed against the same account that can be aggregated. For example, if there are ten transactions against the same account and each updates the same set of key-value pairs in a storage map, then the intermediate transactions can be erased. Because each transaction paid the base fee for the individual update, the batch producer can keep the excess after aggregation. This would only meaningfully apply to public account updates and then only to those that can be meaningfully aggregated. But this is a good incentive for batch producers to aggregate as many transactions against the same account as possible which is good for the network, as it lessens the load.

The note erasure incentive could also apply to the block builder. One the one hand, it should also be incentivized to erase notes, on the other hand, this puts the block producer somewhat in competition with the batch producers. The block producer would profit more from a set of batches that erase fewer notes than a set of batches that erase more notes. I'm not sure how significant that is. Since the block producer is essentially forced to erase the notes from batches through the execution of the block kernel and it receives a block reward anyway, I would err on the side of caution and not incentivize the block producer to erase notes in the same way as batch producers.

Summary

So to summarize:

I agree we should let the batch producer claim the entire tip and then pay a tip of their own choosing forward.
- This is what I mean by "splitting the transaction tips", because that's what it effectively would mean I think.
I would not use a protocol-generated reward for the batch producer.
Block producers should most likely get a protocol-generated reward.
Batch producers should be incentivized to do note erasure and account aggregation and block producers shouldn't.

Pay Fee Procedure

Local Transactions

For regular non-network transactions, users can call a pay_fee procedure with an asset with which they want to pay for fees. I think this procedure would usually be called in the transaction script, at some point before the transaction is signed. This procedure would take an ASSET as a parameter, which would itself be a transaction script input, which the procedure verifies to be a fungible asset and removes from the account's vault and stores at some memory location. That asset is also removed from the input vault by pay_fee, since it won't appear in the final account vault or any output note. That should make the asset preservation check work as-is. The epilogue will then take the asset from the memory location and make it a transaction output.

Network Transactions

For network transactions we have an additional estimate_base_fee procedure which estimates the base fee based on the parameters in the transaction's reference block header and returns it. The transaction script can then take that estimation and add a tip, which is provided as a transaction script input. This amount is used to construct an ASSET which is passed to pay_fee.

I'm assuming that network transactions are executed against accounts that do not require authentication, so calculating fees at the end of the tx script should be quite accurate in terms of the number of cycles of the transaction (that go into the fee calculation). This is accurate as long as the reference block is recent.

Still it could happen that a network transaction calculates the base fee with the current clk showing 4000 cycles, i.e. less than $2^{12}$. But the epilogue has yet to run and once it does the transaction will move into the next cycle bucket with less than $2^{13}$ cycles. To calculate the final fee in the batch kernel we should consider calculating the maximum number of cycles the transaction kernel epilogue can possibly take and always subtract it from the number of cycles of the transaction. This would basically always be an overestimation, but it would make it possible to calculate the fee in the tx script without risk of the final transaction falling into a different bucket and the base fee changing. This is just an idea - whether or not the difference in buckets would even create an actual problem or not remains to be seen with the concrete implementation.

Block Producer Reward

I think as part of building the block we can add a procedure in the block kernel that can be called at most once that mints the rewards of the block and adds it to a provided account's delta.
The limitation would be that only public accounts can be specified for this, but that seems fine. The incentive for the block producer is clearly to modify an account under their own control, so there is no risk of modifying other unrelated accounts, and even then, the state is public and accessible so I don't think it would be any kind of attack vector.

0 replies

Mirko-von-Leipzig · 2025-03-12T17:42:45Z

Mirko-von-Leipzig
Mar 12, 2025
Collaborator

The note erasure incentive could also apply to the block builder. One the one hand, it should also be incentivized to erase notes, on the other hand, this puts the block producer somewhat in competition with the batch producers. The block producer would profit more from a set of batches that erase fewer notes than a set of batches that erase more notes. I'm not sure how significant that is. Since the block producer is essentially forced to erase the notes from batches through the execution of the block kernel and it receives a block reward anyway, I would err on the side of caution and not incentivize the block producer to erase notes in the same way as batch producers.

Is this not solved with a form of free market? Note erasure is opaque to the transaction so the batch builder gets incentivized to build efficient batches and thereby pockets the excess as you suggest. The batch builder should then pass some percentage of this excess on to the block builder to increase his odds of inclusion.

Or put differently - can the relationship between transactions and batches not be roughly the same as batches to blocks? You increase your odds of inclusion by increasing the "tip".

Side note: efficient batches includes stacking txs from the same account as well as note erasure imo.

0 replies

Mirko-von-Leipzig · 2025-03-12T17:48:45Z

Mirko-von-Leipzig
Mar 12, 2025
Collaborator

Because of the aforementioned necessity for the block producer to get a reward independent of block size, we can't incentivize the block producer to maximize the ratio of transactions to batches, or some other similar metric, which would seem like it would have a positive effect on the batch producer to mitigate this above problem.

Is the incentive not simply that it is more time efficient to build bigger blocks? An empty block would give some pittance that just about covers the proving cost (which itself is minimal for an empty block). But given that blocks are limited to one per slot it makes sense for them to assemble the maximum profit per slot and not necessarily the most efficient. As in its better to sell a million compute units at a lower rate for a larger total profit than less units at a better rate but less total profit.

0 replies

bobbinth · 2025-03-13T08:34:06Z

bobbinth
Mar 13, 2025
Maintainer

The only proper incentive for block producers to fill blocks (usefully for the network) is through tips on batches.

I think there could be other incentives as well. For example, there could be some consensus-specific incentives to include batches - e.g., batches carry validator signatures or some other "weight" such that including more batches means higher probability that the block will be accepted by the network (e.g., something like the FruitChain protocol).

Although since there is just a single block producer for now, that is an irrelevant point.

Maybe we should skip block rewards entirely for now and introduce them only when we start working on decentralization/consensus. With a centralized block producer, there is a very strong incentive for the block producer to produce blocks and follow the protocol.

So to summarize:

I agree we should let the batch producer claim the entire tip and then pay a tip of their own choosing forward.

This is what I mean by "splitting the transaction tips", because that's what it effectively would mean I think.

I would not use a protocol-generated reward for the batch producer.

Block producers should most likely get a protocol-generated reward.

Batch producers should be incentivized to do note erasure and account aggregation and block producers shouldn't.

I agree with this with the only comment that (as mentioned above), I'd delay thinking about protocol-generated rewards for block producers till later (i.e., when we start thinking about decentralization).

For regular non-network transactions, users can call a pay_fee procedure with an asset with which they want to pay for fees. I think this procedure would usually be called in the transaction script, at some point before the transaction is signed. This procedure would take an ASSET as a parameter, which would itself be a transaction script input, which the procedure verifies to be a fungible asset and removes from the account's vault and stores at some memory location. That asset is also removed from the input vault by pay_fee, since it won't appear in the final account vault or any output note. That should make the asset preservation check work as-is. The epilogue will then take the asset from the memory location and make it a transaction output.

Largely agree, but a couple of comments:

It may be better that pay_fee does not remove the asset from the account vault but rather assume that the asset has already been removed. This could give us flexibility as to the source of the fee (e.g., the fee could come from note assets). An alternative could be making the procedure name more specific - e.g., pay_fee_from_account and maybe we could add other "flavors" of this procedure in the future.
We need to think what would happen if pay_fee is called more than once. The rules could be pretty simple: (1) the subsequent calls must be done with the same asset and (2) the subsequent calls will add to the already existing fee.

To calculate the final fee in the batch kernel we should consider calculating the maximum number of cycles the transaction kernel epilogue can possibly take and always subtract it from the number of cycles of the transaction.

I think there could be a pretty accurate way of estimating how many cycles the epilogue for a given transaction takes (e.g., based on the number of output notes and account delta size). We could make sure that it is always a slight over-estimate - but overall, it shouldn't be too far off.

I think as part of building the block we can add a procedure in the block kernel that can be called at most once that mints the rewards of the block and adds it to a provided account's delta.
The limitation would be that only public accounts can be specified for this, but that seems fine. The incentive for the block producer is clearly to modify an account under their own control, so there is no risk of modifying other unrelated accounts, and even then, the state is public and accessible so I don't think it would be any kind of attack vector.

As I mentioned above, I'd probably skip the block rewards for now - but this does bring up a good point about how batch and block builders claim their portions of the tip.

For block builders, it could be similar to what you described above. An alternative could be to create a note (probably a private note) in the block kernel which would include the tip and send it to w/e account the block producer choses. Similar could be done at the batch level - i.e., as a part of the batch kernel, batch producers would create a note which carries their portion of the tip to the account of their choosing.

There could be other ways to do this too - e..g, keep track of "pending" rewards at the block header level and pay them out periodically (e.g., once per epoch). Though, this probably adds too much complexity.

0 replies

PhilippGackstatter · 2025-03-14T15:38:33Z

PhilippGackstatter
Mar 14, 2025
Collaborator Author

Or put differently - can the relationship between transactions and batches not be roughly the same as batches to blocks? You increase your odds of inclusion by increasing the "tip".

I agree, that relationship should be similar. The difference is that transactions pay the base fee, while batches don't. In terms of incentives for the batch to include TXs and the block to include batches, it does seem equivalent though (i.e. tip = incentive).

Side note: efficient batches includes stacking txs from the same account as well as note erasure imo.

Fully agree, I did not mean those to be separate or in competition to one another.

Is the incentive not simply that it is more time efficient to build bigger blocks?

That's an interesting angle and I think its true. My main concern is that tips may not be significant enough by the time they get to the block producer, i.e. the sum of tips may be much smaller compared to the block reward. Once we have some more concrete ideas for how to calculate base fees and what the tip might be, then we'll have a better picture of this.

It may be better that pay_fee does not remove the asset from the account vault but rather assume that the asset has already been removed. This could give us flexibility as to the source of the fee (e.g., the fee could come from note assets).

Good point. I think having just a single kernel procedure for fee payment that can be used with assets from accounts and notes is preferable.

We need to think what would happen if pay_fee is called more than once.

Right, and to support this we may need to be able to query the current fee asset as well, so that scripts can get the asset and add to it if the asset type matches or not do anything otherwise (instead of aborting if they would call pay_fee).

Block Producer Tip Claiming

how batch and block builders claim their portions of the tip. [...] An alternative could be to create a note (probably a private note) in the block kernel which would include the tip and send it to w/e account the block producer choses.

That would work, too. The implementation details on this are not quite clear to me yet. The BlockNoteTree can contain at most 2^16 notes and that will probably never be reached in practice, because that would mean each batch is maxed out. We'd still have to handle the theoretical case of a block output notes tree being full. It could also happen that some batch's output notes are full, so there is no obvious index in the tree where we could always insert the note unconditionally. I think we'd have to search through the output note tree to find an unoccupied entry and add the reward note there. This search could start from (batch_idx 63, note_idx 1023) and iterate through all batches and indices (in that order) in a backwards fashion. If it doesn't find an entry, it aborts. Since the batch producer already has to take care not to select a set of transactions whose sum of output notes exceeds MAX_OUTPUT_NOTES_PER_BATCH, it can just set this condition to MAX_OUTPUT_NOTES_PER_BATCH - 1. That still seems a bit messy to implement overall.

On the other hand, if a block happens to already contain 2^16 account updates that is not even a theoretical problem because that is just a list instead of a tree, so appending another account update is just fine.

As discussed in our call, if we want to restrict access to the reward for block producers, then with notes we can very easily restrict the reward by using a time or block height locked P2ID note where the reward only becomes available after some time. That doesn't seem very easy with accounts. The note could also be private which would be more appropriate because it's intended for a single account to consume anyway and therefore doesn't have to be public (which the account has to be). It also seems better for the network over time. If each block creates a public note that adds up whereas private notes impose less load.

In Ethereum, stake withdrawals cannot happen immediately. 16 withdrawal requests are processed in each block, so it would take days for all validators to withdraw fully. This, afaict, is done to prevent sudden mass exits and avoid validators evading slashing or penalties. However, tips are available immediately to the validator.

If we don't deal with staking / block rewards right now and only have the tips, then tips being spendable immediately is fine, so the note and account approach would work. The account approach may be simpler from the implementation POV, but private notes would impose less burden on the network. Both mechanisms are exceptions to the rule: Notes are created by TXs and accounts are modified by TXs. Either approach would violate one of those rules.

I don't see a clear winner, but would propose going with the note option. That results in a somewhat messy implementation, but the overall protocol and network benefits a bit more and it would fairly easily enable timelocking in the future.

Batch Producer Tip Claiming

The batch producer must also be able to claim the tips of transactions. This has basically the same considerations as the block producer claiming tips. Whatever we conclude there applies here as well I believe. The note and account concerns are essentially the same.

Non-native assets in batches

When transactions pay fees in non-native assets, the batch producer must be able to 1) transfer the tips to itself somehow and 2) put up a large enough amount of the native fee asset that covers the base fees of the transactions.

A solution that works out of the box would be for the batch producer to create and include a transaction itself in the batch that outputs a large enough FEE asset. The downside is that the batch producer has the overhead of transaction creation and most importantly, would also pay the base fee in that transaction which would be a net loss for it. Some mitigating factors are:

This is not so bad if the batch producer needs to transact regularly anyway, but I don't think we can generally make that assumption.
This can also imply that the transactions paying in non-native assets must make up for this loss.
- For "sponsored transactions" where the batch producer is actually the sponsor this would not be a problem.
The batch producer's transaction including the native asset can be a private one and be very minimal (no input and output notes, executed against private account), so its base fee should be relatively small.

Avoiding the base fee burn

A mechanism that avoids this base fee burn would still be desirable to not disincentivize and penalize batch producers from offering this conversion service. One approach is to allow the batch producer to exempt a base fee from a transaction like above and prove that it is theirs via authentication (plus some other restrictions, similar to below). However the authentication alone would add a lot of cycles, so maybe there's a better way.

Another approach could be to allow batch producers (generally) to provide a tip_account_id and a tip_tx_id. These are used as follows:

The batch does not have to burn a base fee equivalent to tx_base_fee, where tx_base_fee is the base fee of tip_tx_id.
- It is required that the account against which tip_tx_id is executed matches tip_account_id.
- tip_tx_id must not consume input and not create output notes.
- The batch producer must prove that the tip_tx_id's account delta consists only of removal of some amount of the native fee asset and a nonce increment. I think this can be proven against the TX ID or against the ACCOUNT_UPDATE_COMMITMENT in the future (Transaction authentication should commit to account delta #1198).
The tip_account_id account will receive the tips (either as a note or directly, subject to the discussion above).

This should have the following desirable properties:

Using the tip_account_id account to receive the tips incentivizes the batch producer to use its own account.
This then implies that the tip_tx_id will also be its own TX or none.
- It could be none in case the batch doesn't convert non-native fees to native ones.
Requiring the minimal account delta avoids this becoming an exploitable "free transaction" mechanism for the batch producer and should mean this is only used for exactly that purpose.
The batch producer can overpay the native asset on the tip_tx_id TX because any excess would flow back to it through tips receival.
It avoids authentication and should work with incentives.

This approach makes the batch kernel more complicated. I think it might be worth it to not disincentivize conversion of non-native fees into native fees, which would be a nice feature.

One practical issue with using a transaction may be that the batch producer needs multiple accounts to choose from when building batches. While a batch is inflight with some transaction against account A the batch producer can't be sure that it will be included in a block and so it can't build the next batch's tip_tx_id with the same account A. Probably easily solvable with a pool of accounts.

Here are some other ideas for completeness / future reference, but they're too complex or impossible (unformatted).

Executing a batch against an account is a messy, but probably possible option. This account must exist, so we don't have to deal with account creation here. The `ACCOUNT_INIT_STATE_COMMITMENT` could be another input of the batch kernel to facilitate this. We'd probably also need an equivalent `ACCOUNT_FINAL_STATE_COMMITMENT` output or a general `ACCOUNT_UPDATES_COMMITMENT` where this can be included (see also this). The only operations supported against the account would then be to remove an asset from its vault and call its authentication procedure. That would then imply supporting passing a `TransactionAuthenticator` to a batch executor to support getting that signature. We should be able to enforce in the batch kernel "epilogue" that only the native fee asset was removed from an account's vault and that its nonce was incremented. Anything else would abort. I'm probably still overlooking something about this - the complexity of this option is high.

Somehow letting the batch consume a note directly is an impossible option. Note consumption by definition requires an account to execute against and since it's not there, the procedures from the note script won't be able to execute.

4 replies

bobbinth Mar 15, 2025
Maintainer

Batch Producer Tip Claiming

For batches, could we not designate the first note in the batch to be a "coinbase note" - i.e., always created by the batch itself to claim the tip? (this would always be a note with index 0)

We could do something similar for the block as well but designate the first "subtree" in the block note tree to be the one that contains the block's "coinbase note".

Another approach is that "coinbase notes" would be a separate output of each batch (one note per batch) and then the block producer will aggregate them into the first subtree of the block note tree. With this approach we'd have the ability to have up to 1024 "coinbase" notes - but the max number of batches per block will be reduced to 255 (from 256) - which I think should be fine.

It could look something like this:

The note could also be private which would be more appropriate because it's intended for a single account to consume anyway and therefore doesn't have to be public (which the account has to be). It also seems better for the network over time. If each block creates a public note that adds up whereas private notes impose less load.

Yes, I think we should actually enforce that coinbase notes must be private.

As discussed in our call, if we want to restrict access to the reward for block producers, then with notes we can very easily restrict the reward by using a time or block height locked P2ID note where the reward only becomes available after some time.

Let's create an issue for adding time locks to P2ID/P2IDR notes. Even if we don't use it for coinbase notes, it may be a good thing to have for other reasons.

Another approach could be to allow batch producers (generally) to provide a tip_account_id and a tip_tx_id.

We may be able to take this approach a step further and get rid of the tip_tx_id. Basically, the batch itself would be able to update the state of the "tip account" directly. That is, the "tip account" for the batch becomes something like the native account for the transaction. Then somewhere in the batch kernel, we'd be able to add/remove assets from the account's vault - and maybe this account would have a special interface (e.g., analogous to "basic wallet"). This also would remove the need for coinbase notes mentioned above - and overall may be a cleaner approach.

The main issue here, as you mentioned, is that in the decentralized setting, the batch builder would not know if their batch makes it into a block and so may need to have multiple accounts with sufficient funds to perform the asset exchange. This is inconvenient, but probably not terribly so and maybe we'll find a better way to address this in the future.

bobbinth Mar 15, 2025
Maintainer

One other thing to consider is that handling non-native assets will make things quite a bit more complicated when we'd need to decentralize and handle some form of batch reconciliation. That is, if batches a and b contain the same transaction, we may need to somehow merge them together while ensuring we don't create new tokens. If we know how much tip each transaction pays, we can apply relatively simple strategies to handle that - but with non-native assets this becomes quite a bit more difficult.

This also could mean that creating coinbase notes in the block kernel may be a better approach as then the block kernel would figure out how to assign tip to batch builders in case the same transaction is in both batches. Though, there is probably a whole host of other things we'll need to figure out here and maybe we can delay resolving them to the future.

PhilippGackstatter Mar 18, 2025
Collaborator Author

Another approach is that "coinbase notes" would be a separate output of each batch (one note per batch) and then the block producer will aggregate them into the first subtree of the block note tree.

Yes, I like that approach for the tip claiming part. It's very clean.

Basically, the batch itself would be able to update the state of the "tip account" directly.

I think this could introduce quite a bit of complexity for that somewhat narrow use case (converting non-native fees into native fees), but maybe I'm overestimating the complexity. Aside from that, for the batch this could be the best option to both be able to take out assets from the account and to insert the tip assets into the account, without needing any notes. It would require authentication via a Falcon signature.

Using the tip_account_id account to receive the tips incentivizes the batch producer to use its own account.

From my "avoiding the base fee burn proposal". I realized that this is not a sound incentive. For example if there happens to be a transaction from account A which is eligible to be exempt from the base fee burn then a malicious batch builder could use that transaction to pay the fees while including many of its own transactions with some useless non-native asset that is being converted into native assets. A would end up paying the base fees of all transactions in the batch and receives a useless non-native asset for it. So overall, authentication seems unavoidable.

One other thing to consider is that handling non-native assets will make things quite a bit more complicated when we'd need to decentralize and handle some form of batch reconciliation. [...]
This also could mean that creating coinbase notes in the block kernel may be a better approach as then the block kernel would figure out how to assign tip to batch builders in case the same transaction is in both batches.

Good point. We could start with the "native account update in batch" approach, to enable the non-native asset conversion. Initially the batch could also transfer the tip fees directly into the account using that approach. Later, we can reconsider whether the batch should instead output the tips so the block kernel can process them further. Maybe during implementation a reason becomes apparent why we even want to do that righ away. The block kernel can then either add the tips to the batch's account directly (which should be fine, since it was authenticated in the batch) or alternatively it can use the coinbase note approach. In any case, that should be a flexible approach.

bobbinth Mar 21, 2025
Maintainer

We could start with the "native account update in batch" approach, to enable the non-native asset conversion. Initially the batch could also transfer the tip fees directly into the account using that approach. Later, we can reconsider whether the batch should instead output the tips so the block kernel can process them further.

Yes, sounds like a good iterative approach. I would even say that as the first step, we could even burn the entire fee (i.e., not have the tip), if this simplifies things. For a centralized operator that controls both block and batch production, this shouldn't make a difference. Once the mechanism is working, we could add the next step of handling the fee. Or maybe even to make this even more gradual:

Fee can be paid only in native token and the entire fee is burned.
Allow for fees to be paid in other tokens, but the entire fee is still burned.
Add handling of tips.

PhilippGackstatter · 2025-03-20T15:41:37Z

PhilippGackstatter
Mar 20, 2025
Collaborator Author

To calculate the actual fees of a transaction I would suggest the following approach.

On the highest level, I think it makes sense to price computation and storage separately, as mentioned previously. This means we'll have a computation_base_fee and a storage_base_fee. Correspondingly, a transaction requires a certain number of computation_units and a certain number of storage_units to be processed. The total fee of the transaction is simply computation_base_fee * computation_units + storage_base_fee * storage_units.

At first let's deal with computation in isolation. The following transaction metrics add to the total computation units of a transaction:

num_cycles: The total number of cycles of the transaction.
num_notes_consumed: The total number of consumed notes.
num_notes_created: The total number of created notes.
created_public_notes_byte_size: The byte size of all public notes.
public_account_delta_byte_size: The byte size of the public account delta. 0 for private account deltas.

All the public data processed by the transaction incurs a small computational cost for the network that we could reflect in the computational cost. We could also not do this and price this completely in the storage units. For now I included it.

I wrote a Python script (https://github.com/0xPolygonMiden/miden-base/blob/pgackst-fee-calculator/scripts/feecalc.py) to experiment with the parameters, but the quick overview is this:

import math
# math.ceil might be unnecessary since I think num_cycles is already always a power of two?
cycle_bucket = math.ceil(math.log2(num_cycles))
# Should we use kibibytes instead (e.g. 1024 bytes instead of 1000?)
kilo_bytes = math.ceil((created_public_notes_byte_size + public_account_delta_byte_size) / 1000)

cycle_units = cycle_bucket * COMPUTATION_UNIT_PER_CYCLE_BUCKET,
notes_consumed_units = num_notes_consumed * COMPUTATION_UNIT_PER_CONSUMED_NOTE,
notes_created_units = num_notes_created * COMPUTATION_UNIT_PER_CREATED_NOTE,
data_units = kilo_bytes * COMPUTATION_UNIT_PER_KILO_BYTE,

total_computation_units = cycle_units + notes_consumed_units + notes_created_units + data_units

All the COMPUTATION_UNIT_PER_* are constants that we have to set. These have to be chosen so everything has its appropriate influence on the total computation units.

Here are some examples of the total computation units with a variety of transactions. The number in parentheses is the computation units contributed by that column. To keep the combinatorial explosion reasonable this always has account delta = 0, because the influence of the data is already reflected through the public notes.

Cycle Bucket	Notes Consumed	Notes Created	Public Note/Account Data	Computation Units
16 (8_000)	5 (150)	5 (250)	0 (0)	8_400
16 (8_000)	5 (150)	5 (250)	6_500 (105)	8_505
16 (8_000)	5 (150)	5 (250)	40_000 (600)	9_000
16 (8_000)	5 (150)	250 (12_500)	0 (0)	20_650
16 (8_000)	5 (150)	250 (12_500)	325_000 (4_875)	25_525
16 (8_000)	5 (150)	250 (12_500)	2_000_000 (30_000)	50_650
16 (8_000)	250 (7_500)	5 (250)	0 (0)	15_750
16 (8_000)	250 (7_500)	5 (250)	6_500 (105)	15_855
16 (8_000)	250 (7_500)	5 (250)	40_000 (600)	16_350
16 (8_000)	250 (7_500)	250 (12_500)	0 (0)	28_000
16 (8_000)	250 (7_500)	250 (12_500)	325_000 (4_875)	32_875
16 (8_000)	250 (7_500)	250 (12_500)	2_000_000 (30_000)	58_000
20 (10_000)	5 (150)	5 (250)	0 (0)	10_400
20 (10_000)	5 (150)	5 (250)	6_500 (105)	10_505
20 (10_000)	5 (150)	5 (250)	40_000 (600)	11_000
20 (10_000)	5 (150)	250 (12_500)	0 (0)	22_650
20 (10_000)	5 (150)	250 (12_500)	325_000 (4_875)	27_525
20 (10_000)	5 (150)	250 (12_500)	2_000_000 (30_000)	52_650
20 (10_000)	250 (7_500)	5 (250)	0 (0)	17_750
20 (10_000)	250 (7_500)	5 (250)	6_500 (105)	17_855
20 (10_000)	250 (7_500)	5 (250)	40_000 (600)	18_350
20 (10_000)	250 (7_500)	250 (12_500)	0 (0)	30_000
20 (10_000)	250 (7_500)	250 (12_500)	325_000 (4_875)	34_875
20 (10_000)	250 (7_500)	250 (12_500)	2_000_000 (30_000)	60_000

Main questions/thoughts:

Is the order of magnitude of each column correct? Should something contribute much more/less?
The cycle bucket difference between $2^{16}$ and $2^{20}$ is 25% here, while @bobbinth mentioned further above it is logarithmic but also a roughly 10% difference. So I'm not sure if the difference between the two is correct (i.e. it is logarithmic here) or if we should further adjust somehow.
Do we also want a specific constant to be added for account creation?

Once we have an idea on the order of magnitude of computation units we can come up with the appropriate base fee calculation.

8 replies

PhilippGackstatter Mar 24, 2025
Collaborator Author

Thanks! However, I think I don't understand why pricing these independently is actually useful for the network/protocol.

For example, say we have two blocks that are the same except for:

Block A contains the maximum number of transactions each of which consumes no notes and create the max number of notes.
Block B contains the maximum number of transactions each of which consumes the max number of notes and creates no notes.

Let's assume that note creation and consumption impose the exact same load on a node. Then, what is the difference for the network (or a node) between a stream of blocks [A, A, A, ...] and [B, B, B, ...]? The computational load is the same, and that scarce resource (next to bandwidth, storage) is what we want to price with fees, right? So I don't understand why pricing note creation and consumption differently would help the network/nodes.

I should mention that in practice note creation and consumption impose different computational loads, but in the model I described above that's what would be captured by the different constant weights. So for the purpose of computational costs I think it's fine to assume the same load in the above example. Public note creation also additionally imposes storage costs, but these would be captured by the separate computation cost for the data units plus the completely separate storage fees.

So overall, my point is that if the main resources of a node are computation and storage, then it should be sufficient to price these at that level. How each block fills up the computation and storage units is not really important to the node anyway, which is why I don't understand why this would be good:

If the number of notes rises over some base level, the base fee needs to go up to discourage transactions which produce many notes

bobbinth Mar 25, 2025
Maintainer

However, I think I don't understand why pricing these independently is actually useful for the network/protocol.

At lest the way we have them defined now, these are independent resources because we put an upper limit on how many nullifiers and notes can be created per block, how many accounts can be updated per block etc. At least for the notes created there is a hard limit because of the block note tree structure - i.e., we can't go over $2^{16}$ notes per block.

If we go with the compute/storage resources, then we need to define the limits in such a way that they would comply with these constraints. For example, if we say that a single created note consumed 50 compute units, then max limit of compute units per block would be about 3.3M. If we now say that each consumed nullifier is 500 compute units (because nullifiers are computationally more expensive to process), we impose a de-facto limit on the number of consumed notes per block at ~6.5K.

The issue here is that from computation standpoint (and here I'm thinking about the cost of building a block in a block kernel), marginal cost of a new note is almost negligible (because all we need to do is combine note sub-trees into a single block note tree) but the cost of inserting a new nullifier is pretty high (because we need to update the nullifier tree). So, trading off consumed notes for created notes don't really make too much sense.

This is not to say that this approach never makes sense. For example, updating the account tree is basically the same amount of work as updating the nullifier tree and so we can say that a transaction which updates an account and consumes 3 notes is equivalent to 2 transactions where only 1 note is consumed in each, or 4 transactions where no notes are consumed. So, maybe the resource here is the number of smt_updates per block rather then the number of nullifiers or accounts updated.

Basically, I think it could be OK to "collapse" some of the parameters into a single resource, but we shouldn't do it across independent resources. So, I guess the main complexity here is to define which resources are really independent and define limits in terms of these. Though, I would say that conceptually, it is a bit easer to think of "a block can consume up to 100 notes and have at most 100 transactions" vs. "a block can perform 200 SMT updates" - even if the latter is a more optimal way to structure things.

btw, once we align on the resources, the way I'm imagining this would work is that for each resource we need to define 3 parameters:

Upper limit - the maximum units of the resource that can be consumed per block.
Target level - if the resource usage is above this level, the base fee increases, if it is below this level, the base fee decreases.
Minimum base fee - the minimum possible base fee, even if the resource utilization has been under the target level for a while.

I believe Ethereum model has the first two, but not the last one.

PhilippGackstatter Mar 26, 2025
Collaborator Author

Thanks, that makes sense. If we define the block limit of computation units and then divide by the limit, we'll get the same cost for a consumed and created note, which does not accurately captures that these have in fact different costs.

Multiple Base Fees

So then that leaves us the different base fees as the best option. Modifying your previous suggestion:

verification_base_fee: Verification of a transaction. Proportional to the log of the number of cycles a transaction took to execute.
- Each tx pays this once.
tree_base_fee: Upsert operation into an SMT of depth 64, i.e. nullifier or account updates.
- Each tx pays this once for the account it updates plus the number of consumed notes.
note_base_fee: Fee per created note.
- Each tx pays this for the number of created notes.
data_processing_base_fee: Price per 10 bytes of public data the transaction produces. This is the cost for processing the data, not for storing it - the latter is charged separately.
- Each tx pays this for its public data (notes, account).

I think the target level could be the one at which that base fee's dimension contributes 1/4th of an optimal block (because we have four dimensions), where we could define the optimal block proving time to be, say, 500ms (a half-full block) on the hardware that we want to run nodes on. So if a block is filled with txs/batches where each dimension contributes dimension_target, then it'll result in a 500ms proving time. Like in EIP-1559, we have variable size blocks and allow a block to go up to target * 2.

To figure these numbers out, we could try to run benchmarks that isolate each dimension on a best-effort basis. For example, to determine the "tree base fee" target level we can run a benchmark to see what number of consumed notes results in a 500ms proving time, while having a negligible amount of transactions with few cycles, no created notes and no public data. If we determine that an isolated 40,000 consumed notes result in a 500ms proving time we set the target to 10,000. In the absence of the MASM block kernel we'd have to use the Rust code (at least to figure out the relative differences), but once we have the kernel we could rerun those benchmarks.

An approach that shouldn't really work is to set the target at half the maximum of the existing limits, e.g.:

Dimension	Min	Target	Max
Average Tx Cycles	10	20	29
Created Notes	0	$2^{15}$	$2^{16}$
Consumed Notes	0	$2^{15}$	$2^{16}$
Public Data (bytes)	0	500 KiB	1 MiB

(Public Data isn't defined anywhere, I just guessed numbers).
But this could result in just about any number of block proving time, so while it uses half the available space it's not really protecting the block producer from overload.

I'm unsure what the best way is here. The benchmark approach seems brittle and it's not easy to isolate every dimension.

Base Fee Scope

One other question it raises is whether the base fees should reflect the cost only for the block, or also for the batch. One the one hand we were discussing verification base fees for transactions, which is the batch prover's job, and on the other hand we've said that the cost of a created note is small because we only need to combine note sub-trees into a single block note tree. Transaction verification does not concern the block producer directly while combining sub-trees does concern it, and vice versa for the batch producer.
Ultimately, a transaction's cost to the network is the cost it incurs for the batch and the block, so from that standpoint it would be fair to say that each created note incurs the cost of a SimpleSmt<DEPTH: 10> update plus a 1/1024th of a SimpleSmt<DEPTH: 16> update. So should we capture the cost for batch and block in the base fees?

Data

The byte size of a block is primarily determined by the public data it contains. Miden potentially needs a higher block size than other chains because transactions are not re-executed against a known state, so the resulting state delta is instead provided as part of the block. On the other hand, Miden also has private state, and it should be preferred so public data should come at a premium.

Aside: One inefficiency we currently have (afaict) is that each Note contains its entire script's code. If we have 500 P2ID notes, then each of these will take up ~1 KiB of data just for the script. It would be ideal if we could deduplicate Mast forests in a block. Even with heterogeneous notes, just deduplicating miden lib or stdlib would be very helpful. Then we would get much further with the same limits. The difficulty with this is that we'd have to do this deduplication in the block kernel so that the optimized size can be used for the base fee calculation. This could be a post-mainnet optimization though, I think and this has probably been discussed somewhere already.

bobbinth Mar 27, 2025
Maintainer

I think the target level could be the one at which that base fee's dimension contributes 1/4th of an optimal block (because we have four dimensions), where we could define the optimal block proving time to be, say, 500ms (a half-full block) on the hardware that we want to run nodes on. So if a block is filled with txs/batches where each dimension contributes dimension_target, then it'll result in a 500ms proving time. Like in EIP-1559, we have variable size blocks and allow a block to go up to target * 2.

I think this makes sense. I'd probably go a bit higher on the "target proving time" - maybe even ~2 seconds (until we have hardware acceleration, even this would result in pretty low throughput).

Dimension Min Target Max

Average Tx Cycles 10 20 29

Created Notes 0 $2^{15}$ $2^{16}$

Consumed Notes 0 $2^{15}$ $2^{16}$

Public Data (bytes) 0 500 KiB 1 MiB

I think the table didn't render correctly in the original comment but seems to be rendering fine in the quote. A few comments:

For created/consumed notes, I'd probably set a limit at first to be fairly conservative - maybe at 256 target and 512 max (or something in this range). Then, once we have some empirical data, we can fine tune this.
For tx cycles, I'm not quite sure how to think about this yet. Basically, if we want the block kernel to be executed in ~2 seconds, we know that the block kernel should take $n$ cycles, where right now this $n$ is pretty low (e.g., $2^{18}$ and with some work we could get it to $2^{19}$, and beyond that, we probably need hardware acceleration). Every proof we verify requires some number of cycles and this depends logarithmically on the number of cycles proven. For example, if a transaction took $2^{20}$ cycles to execute, it may take $2^{16}$ cycles to verify. and if it took $2^{16}$ cycles to execute, it may require $2^{15}$ cycles to verify (but we'll need to confirm these numbers once recursive verifier is fully implemented). And so, we should "judge" the transaction not based on how many cycles it took to execute, but how many cycles it would take to verify.

One other question it raises is whether the base fees should reflect the cost only for the block, or also for the batch. One the one hand we were discussing verification base fees for transactions, which is the batch prover's job, and on the other hand we've said that the cost of a created note is small because we only need to combine note sub-trees into a single block note tree. Transaction verification does not concern the block producer directly while combining sub-trees does concern it, and vice versa for the batch producer.
Ultimately, a transaction's cost to the network is the cost it incurs for the batch and the block, so from that standpoint it would be fair to say that each created note incurs the cost of a SimpleSmt<DEPTH: 10> update plus a 1/1024th of a SimpleSmt<DEPTH: 16> update. So should we capture the cost for batch and block in the base fees?

Good point: some things are more expensive for batches and for blocks, and we should take a more "wholistic" approach.

I was thinking a bit more about how we define resources, and maybe doing something more along your original proposal makes sense. Specifically, one of the resources that we care a lot about is how many extra cycles does a given transaction add to the batch/block kernel. And here, we could try to make an estimate - e.g., the number of cycles the transaction took to execute, the number of input and output notes, all contribute to this metric. So, maybe "verification cycles" is the main resource we care about for the transaction kernel.

The main difficulty here is how to estimate this correctly across batches and blocks. Specifically, estimating how many cycles a given transaction will require to verify in the batch kernel is not that difficult, but how many cycles it will take in the block kernel depends highly on how many other transactions are in the batch (i.e., a batch with 1 transaction takes almost the same effort to verify in the block kernel as a batch with 2 transactions).

There would be other resources as well, e.g., computation outside of the kernel (mostly related to the amount of hashes we'd need to do), storage etc. But we may end up with just 3 or so resources (e.g., kernel cycles, number of hashes, and storage).

PhilippGackstatter Mar 27, 2025
Collaborator Author

But we may end up with just 3 or so resources (e.g., kernel cycles, number of hashes, and storage).

I like the simplification of removing the "note base fee" and including it in the cycles as well as in the hashes (for batches), and I think that makes sense.

The main costs of a transaction should be:

Verification
- Batch Producer: Recursively verifies TX
- Block Producer: Recursively verifies batch
Hashes
- Batch Producer: Inserts output notes into batch note tree
- Block Producer: Inserts nullifiers into block note tree + aggregates batch note trees
Data
- Batch Producer: Aggregates public account updates in-kernel + processing outside
- Block Producer: Aggregates public account updates in-kernel + processing outside

Data

I think I would still like to have four base fees overall, the above ones and storage. I'm still not sure who will actually store public notes and accounts, but at least initially it will be the block producer. This long-term storage of data that can also be refunded to users. I think having a small incentive to clean up the public data is good.
Because of that I would split up these "data"-related ones into a data processing part (the one above) which is related to the public data that computations are run on, but transiently, and then separately the storage fee which is non-transient.
Whether we need the data one is debatable, but I'm leaning towards yes. It's probably less significant than the others, but somehow a huge update of a public account should probably incur a higher cost than the equivalent update of a private account.

Hashes

For the hashes, I think it could be fine to calculate those as 10 hashes for a created note in the block note tree plus the 64 hashes per consumed note for the nullifier tree and ignore the (1/1024 * 16) contribution of batch note aggregation.

Verification Cycles

We can't make the base fee dependent on how many other transactions are in the same batch because we should be able to estimate the base fee in the transaction kernel itself, so network transactions can compute the base fee as closely as possible. If we did that, it would only make the base fee computable at batch construction time, when it is known how many other transactions are in the batch.

The block producer's incentive is to fill up blocks as much as possible to maximize fees while at the same time minimizing the required effort. So if it can include few batches with many transactions it should prefer doing that over including many batches with few transactions. If that's a correct assumption then we could use the batch/tx ratio as a proxy for how many transactions are currently "available".

Include batch cost in base fee

We could try to reflect the cost of batch verification as part of the base fee update. The main idea here being that if the current batch/tx ratio is high, then most likely will the next batches also contain few transactions and so the contribution of each transaction to the cost of batch verification is higher than if the ratio was higher.

Instead of driving the verification base fee only through the transaction verification cycles, we could make that based on batch_tx_ratio + tx_verification_cycles:

next_base_fee(HIGH_BATCH_TX_RATIO, HIGH_TX_EXEC_CYCLES) => high increase
next_base_fee(HIGH_BATCH_TX_RATIO, LOW_TX_EXEC_CYCLES) => moderate increase or decrease
next_base_fee(LOW_BATCH_TX_RATIO, HIGH_TX_EXEC_CYCLES) => moderate increase or decrease
next_base_fee(LOW_BATCH_TX_RATIO, LOW_TX_EXEC_CYCLES)) => high decrease

So these both contribute to the block's overall "verification cycles" that determine the base fee of the next block and may also cancel each other out, depending on the scenario. We could also factor these so the batch-tx ratio only contributes 25% for example. In any case we'd have to factor these because ratio and cycles are on different orders of magnitude, but I hope that gets the point across.

Ignore batch verification cost

The simplest option is to ignore the batch verification cost for the transaction's base fees. The block producer will (later) receive a constant block reward anyway, independent of block content so that should compensate it for verifying batches. Moreover, it still has an incentive to include as many transactions in the block as long as the batch they're contained in has a worthwhile enough tip. It would be unfortunate if we can't capture this in the base fee, because it should be part of it.

I think I'd prefer this option, at least initially.

@bobbinth Do you think it makes sense to already start working on these benchmarks or should we wait for the recursive verifier and/or the batch and block kernels with this and use guesstimates until then? I guess even with the Rust code we could at least estimate the hashes and data part somewhat.

Mirko-von-Leipzig · 2025-03-27T08:16:35Z

Mirko-von-Leipzig
Mar 27, 2025
Collaborator

Something I'm not entirely understanding and that I've probably missed - but why do we care about the difference between batch and block proving costs? Or rather, why do we care about teasing them apart.

I'm ignoring token/fee burning because I feel like that's orthogonal to the problem at hand (but maybe this is where my misunderstanding comes in).

Why does the entire tip not go to the batch producer, who then selects how much of this tip to forward to the block producer to include the batch? If the batch producer is greedy then the batch is never included and this is enough incentive to split according to effort. Where cost of effort is determined by the market.

Is the issue that this depends on the consensus mechanism? e.g. if a block builder is pre-determined with staking then the builder has "complete" power for a block?

1 reply

PhilippGackstatter Mar 27, 2025
Collaborator Author

why do we care about the difference between batch and block proving costs?

Not sure if I fully understand the context of the question, but in my mind the main goal is for the base fees to capture the cost of a transaction for the protocol (i.e. batch and block producers). That's why for consumed/created notes we have to look at batches and blocks, because consuming notes is a cost for the block producer and created notes are primarily a cost for the batch producer. So we have to tease these apart so we know the individual contribution, so we can then, on transaction level, compute the combined cost. Does that make sense or is your point a different one?

Why does the entire tip not go to the batch producer, who then selects how much of this tip to forward to the block producer to include the batch?

That's basically how we left the batch reward discussion because I couldn't yet come up with a non-exploitable scheme for giving protocol-generated rewards to the batch producer.
I think now that it may be problematic if we include batch producer costs in the base fees as well as the block producer's ones, but then eventually only hand out protocol-generated rewards to the block producer. This may not be something that we have to figure out right now though.

PhilippGackstatter · 2025-03-31T10:02:48Z

PhilippGackstatter
Mar 31, 2025
Collaborator Author

I was thinking about network transactions, fees and incentives and wanted to write down some quick thoughts. Generally, each transaction needs to pay fees. Network transaction builders (NTB) are unlikely to build transactions and pay the fees themselves. Most likely, each note intended for consumption by a network transaction should include some payment that gets aggregated into the network transaction's fee, plus a tip for the NTB (the tip could be added later for the decentralized setting). I guess the NTB and the batch builder could be similar entities ultimately participating in building parts of blocks, and each must be incentivized to do so.

The main challenges with this are:

How does the NTB receive the tip? Probably by creating a P2ID note that contains the tip for its account.
How does the note creator estimate the tip?
- It could be that the note is the only one in the transaction, so it has to include enough to pay for the entire transaction.
- It could be that many other notes are in the same transaction, so a fraction of the total transaction's cost would be enough.
- Generally, the note creator won't know that, so it has to assume the worst-case scenario. This may result in overpaying by a lot.
- Ideally we'll have a refund mechanism for this so that a note could just include a large enough amount to cover the worst-case scenario, but ultimately only pay what is needed (+ tip). Unless there is another way, such a "refund note" may be needed.
- Perhaps we'll need a different set of APIs for network transactions that allow for this. E.g. pay_network_tx_fee(fee_asset: Asset, ntb_tip: u64).
  - This is called by all notes that are consumed in the network tx, or potentially by the network account.
  - Example: Say 3 notes call this procedure. The first note passes a fee of 30 and the others fees of 15 and each note an additional ntb_tip of 2. The NTB's tx script uses the tx kernel APIs to compute the estimated fee and comes out at a total fee of 21. Each note has to contribute 21 / 3 = 7 (ignoring rounding issues here). The first note author is refunded 30 - 7 - 2 = 21 and the others are refunded 15 - 7 - 2 = 6 in a P2ID note. The NTB can create a note for itself containing the aggregated tip of 3 * 2 = 6.
There is also the case where someone sends a note and it is never included in a network transaction, perhaps because its fee/tip was too low. I think this alone requires that each "network transaction note" should be recallable after some time, so those funds (and the note assets) aren't lost. We would have to communicate that to builders who design "public network accounts" and the corresponding notes, or we somehow try to allow this in the protocol.

5 replies

Mirko-von-Leipzig Mar 31, 2025
Collaborator

There is also the case where someone sends a note and it is never included in a network transaction, perhaps because its fee/tip was too low. I think this alone requires that each "network transaction note" should be recallable after some time, so those funds (and the note assets) aren't lost. We would have to communicate that to builders who design "public network accounts" and the corresponding notes, or we somehow try to allow this in the protocol.

Should we maybe enforce this requirement? As in, maybe all network notes must have a recovery account which can consume the note resources built into the note script. This could even be implemented as a simple builtin component (? unsure if this is the correct terminology).

PhilippGackstatter Mar 31, 2025
Collaborator Author

In principle I like that idea. Requiring that some code is present could be fine - the note author's are still aware it is there and it is not automatically added by the protocol (which I was thinking and concerend about). But I'm not sure we can enforce this very easily, because a note is just a Program, which is represented as a MAST root on the protocol level. So it's not just hardcoding the MAST root of the recall procedure and checking if it's there.
We could still hardcode that MAST root and require that a "merkle tree" like proof is presented that verifies that the recall procedure is part of the note script. It wouldn't guarantee that it can be executed though, because it could be in the else branch of an if true { ... } else { ... } statement. But I guess that may be good enough - users have to trust the network account and the network note if they send it.

The other side to this is that we'd need to be able to identify network notes so we can run the check. We may be able to sneek that into the note metadata.

Mirko-von-Leipzig Mar 31, 2025
Collaborator

The other side to this is that we'd need to be able to identify network notes so we can run the check. We may be able to sneek that into the note metadata.

This is already part of the note tag via the NoteExecutionMode - or is that also just a hint?

On a related note - how is a note's target identified? As in, how is the network account specified? We could also enforce that the target account must be a network account (once its possible to prove this via the program MAST tree). Though maybe that's a bit much - though it could mean we get to skip that check in the node - we can just assume the target account is a network account since the note must target one provably.

PhilippGackstatter Mar 31, 2025
Collaborator Author

This is already part of the note tag via the NoteExecutionMode - or is that also just a hint?

Yes, that is just a hint.

https://github.com/0xPolygonMiden/miden-base/blob/a5896ef212b0e5e3d236ef07f9b99b67b09cf8a8/crates/miden-objects/src/note/note_tag.rs#L20-L34

I think it would be great if we could make that a guarantee instead of a hint.

On a related note - how is a note's target identified?

Yeah the note tag can be used for that:
https://github.com/0xPolygonMiden/miden-base/blob/a5896ef212b0e5e3d236ef07f9b99b67b09cf8a8/crates/miden-objects/src/note/note_tag.rs#L86-L87

But the note tag also allows for use cases to be specified instead of accounts and I'm a bit unclear on how this interacts with network transactions. From that standpoint, though, having some identifier for network accounts in the ID would allow us to validate that network notes are sent only to network accounts (but again only if the note tag is "non-use case").

bobbinth Mar 31, 2025
Maintainer

How does the note creator estimate the tip?

While notes can contain fee payment logic in them, I was actually thinking it would be the network account that would pay the fee. For example, NTB would build a transaction consuming $n$ notes and include a transaction script which calls the authentication procedure for the account. This procedure could increment the nonce and also compute the fee to be paid for the transaction itself (i.e., like any regular transaction would) and to the NTB for building the transaction (e.g., via a note). Though, maybe there is a way to combine both into a single fee.

It would be then up to the network accounts how to charge fees from notes. For example, a DEX may collect fee per fulfilled order and then pay transaction fees from that. The tricky part would be to make the fee payment logic flexible enough, while keeping the number of well-known network account authentication scripts small.

There is also the case where someone sends a note and it is never included in a network transaction, perhaps because its fee/tip was too low. I think this alone requires that each "network transaction note" should be recallable after some time, so those funds (and the note assets) aren't lost. We would have to communicate that to builders who design "public network accounts" and the corresponding notes, or we somehow try to allow this in the protocol.

Agreed that making such notes "recallable" is a good idea in general - though, not sure if we can/should enforce it. Generally, I didn't think we'd need to refund the fee for such notes - i.e., if I put a note on-chain I pay a fee for this, and if I recall the note, I pay fees for this again. I think this could be a part of the mechanism for people not to create "unconsumable" network notes. Otherwise, I could create a bunch of notes which impose the burden on the network to try to execute them, and then get my fees refunded - which would make this attack free to me.

Dominik1999 · 2025-05-07T18:05:29Z

Dominik1999
May 7, 2025
Collaborator

I am a bit later to the party. I am trying to read everything.

One thought, and please ignore if this was already discussed and dismissed. Can we have a fee share mechanism between the smart contract used and the network?

I would love to incentivize products on Miden such that they get a share of the fee. That can mean, that whenever a user transfers USDC, the USDC contract owner gets 10% of the tx fee.

That mechanism will help applications to monetize faster. Which will help them raise due to an existing cashflow.

1 reply

PhilippGackstatter May 8, 2025
Collaborator Author

For network transactions, the account of that transaction is supposed to pay for the fees of the transaction. That enables it to do whatever it wants in terms of fees, including requiring royalties.

whenever a user transfers USDC, the USDC contract owner gets 10% of the tx fee.

I think this specifically would require programmable assets. If we have those, you could enforce that a transaction transferring USDC only succeeds if the tx also creates a note paying 10% of the moved value to some predefined contract.

So I think this should all be eventually possible.

PhilippGackstatter · 2025-05-09T06:55:23Z

PhilippGackstatter
May 9, 2025
Collaborator Author

Here is a summary of the most important points from the discussion so far.

Base Fees

EIP-1559-style fee mechanism. Fee of a transaction consists of:

a protocol-defined base fee,
a tip for priority, in case of congestion.

How does the base fee change?

Base fee increases if the last block took more time to prove than the target time.
Base fee decreases if the last block took less time to prove than the target time.
Base fee stays the same if the last block was proven in target time.

What is the target time?

The point at which a node can produce a block so we hit the block time we want (e.g. 3s).

This should make fees predictable because the base fee is protocol-defined and changes only according to protocol rules, while tips are only relevant under congestion.

What happens to the base fee?

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.

Tim Roughgarden (http://timroughgarden.org/papers/eip1559.pdf)

What happens to the tip?

Given to the batch producer as an incentive to include transactions.
The batch producer in turn has to give a tip to the block producer to incentivize inclusion of its batch.

So transactions are in competition with each other to be included in batches, while batches are in competition with each other to be included in blocks.

However, this competition should only really occur and matter under congestion. Otherwise, the block producer will be happy to include any batches at all, since it can pocket their tips.

(Non-)Transient Costs

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

Dimensions

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 produced on-chain notes.
Size of state delta of on-chain accounts.

These reduce to the following three major components, with the primary cost driver of each mentioned below:

ZK-Proof Verification
- Batch Producer: Recursively verifies TX
- Block Producer: Recursively verifies batch
Hashes
- Batch Producer: Inserts output notes into batch note tree
- Block Producer: Inserts nullifiers into nullifier tree (number of input notes) + inserts accounts into account tree (1 account per tx) + aggregates batch note trees into block note tree (at most 64 insertions)
Public Data
- Batch Producer: Aggregates public account updates in-kernel + processing outside
- Block Producer: Aggregates public account updates in-kernel + processing outside

Fee Kernel APIs

Local Transactions
- Client fetches base fee from latest available block.
- Calculates required base fee based on the relevant transaction parameters:
  - How many notes does it consume / create?
  - How much public data does it create?
  - How many cycles does it take to execute?
    - This implies how many cycles it will take to verify the tx.
- Set the calculated fee plus small tip (or higher based on current congestion levels) in the TX script. This asset is taken from the account's vault.
  - Uses the fn pay_fee(asset: Asset) kernel procedure to set the fee.
Network Transactions
- Calls a kernel procedure compute_required_fee which uses the base fee from reference block to calculate the fee of the current transaction and its relevant parameters (see above).
- Then calls pay_fee with an asset removed from the network account's vault.

Overview

Here is a visualization for a typical transaction inclusion in a block:

We have a series of blocks where each block's base fee increases by 1% compared to the previous block.
We have two transactions that use block 0 and 1 as reference blocks, respectively.
Note that the reference block of the transaction and which block the fee info is taken from are not the same. The reference block is a protocol-enforced concept, while the fee is something that is simply set in the transaction script. So it could also be set to an arbitrary value. Here, I'm assuming the client creating these transaction fetches the latest block at transaction creation time and uses that information.
These transactions are included in batch 0. The batch kernel verifies that all transactions pay the base fee of the reference block of the batch and burns them (except for the tip). So both tx 0 and 1 must pay the base fee of 104. These transactions have used a lower base fee to calculate their overall fees. So to make sure they can be included even if the base fee rises within a couple of blocks, they should set a slightly higher value.
- A transaction will typically pay the base fee and a tip. If the base fee rises compared to the base fee at tx creation time, then the tip part might still cover the rising base fee.
- Note: We currently don't have a max_fees mechanism like EIP-1559, because we don't have a simple, efficient refund mechanism. This means if the base fee decreases, the transaction will still pay the full amount it set as fee. The excess beyond the base fee would go as a tip to the batch/block producer. My preference would be to think more about a refund mechanism to avoid this situation.
The batch can be included in any block that satisfies inclusion_block_number <= batch_ref_block_num + 16.

Misc Notes

Transactions can pay fees in any asset that a batch producer is willing to accept. The batch producer converts that asset into the native fee asset.
The batch producer executes the batch against its own account, which allows it to remove assets directly without having to create a transaction itself. This is useful for the above fee conversion mechanism. Example: Batch includes two transactions paying fees in USDC. Batch producer moves USDC into its account and removes XYZ tokens (the native fee asset) from its account and uses it to pay fees.
The protocol allows the block producer to claim its tip (and later block reward) by including a note targeted at its account in the block.
The block kernel forces the block producer to create a note for each batch which contains its tip.

1 reply

bobbinth May 17, 2025
Maintainer

I also wrote up a summary here.

Dominik1999 · 2025-06-18T20:06:29Z

Dominik1999
Jun 18, 2025
Collaborator

I realize I’m quite late to this discussion, but after following the conversation, I wanted to share a perspective that might help simplify things.

I can’t shake the feeling that we might be overthinking the fee model at this stage. The assumptions I’m working with are:

For the first two years, we’ll operate in a centralized mode.
During this time, we should be actively subsidizing the network to drive adoption:
- The lower the cost, the higher the usage.
- The easier the user experience, the more traction we’ll get.
- The easier it is to build, the more applications we’ll see.
Some minimal fee mechanism is still needed for transaction prioritization.

With that in mind, a simple approach might be:

A. Prioritize transactions by the fee paid.
B. Allow fees in stablecoins, ETH, SOL, or Miden tokens.
C. Let the Miden Node return a fee estimate (e.g., average of the last 10 blocks).
D. The Miden Foundation covers ancillary services (delegated proving, private note transport, state management, etc.).

As we approach decentralization and need to properly incentivize batch/block builders and other stakeholders, we can revisit a more nuanced, multi-dimensional fee model—possibly even Ethereum-style. But for now, I’d advocate for keeping it simple. A complex fee model won’t move the needle in the short term and only adds friction for developers and users.

In these early years, our priority should be ease of use, not fee equilibrium. We're happy to subsidize—profitability of the centralized node isn't a concern right now. Adoption is.

2 replies

Dominik1999 Jun 18, 2025
Collaborator

Especially, when we think about the end-user experience, I don't quite understand at which stage we would simplify it for the user following the current approach.

When I imagine Alice who wants to interact with an App on Miden in a private way from her mobile phone:

Alice needs to think about a base fee
Alice needs to think about a priority fee
Alice needs to think about a fee for delegated proving (since she is on mobile)
Alice needs to think about a fee for the transport layer for private notes (she uses Miden privately)
Alice needs to think about a fee for the application itself (we can't expect apps to be free on Miden)

So either we have a terrible UX in many failing attempts - one of her estimates might be wrong or simply there is a transport error / payment error to one of the auxiliary services. Or we have a terrible DevEx and the WebClient or Wallet need to abstract all those estimates and different connections away. And we should not sacrifice on UX or DevEx, we should rather run non-profitable until we have traction and useful applications.

That being said, because of Miden's unique design of pushing state and execution to the edge, we need many more services than other blockchains that need to be incentivized. So only thinking about the core protocol and how we balance things out there might not be enough.

partylikeits1983 Jun 19, 2025
Collaborator

I’m a big fan of the long-term, EIP-1559-style, multi-dimensional model. We’ll absolutely need the fee granularity once the network is decentralized. But for v1 of the fee model I think something radically simpler is probably best to let early builders get their hands dirty right away.

Payment flow: node returns one number; the tx script pays it in a single P2ID note (ETH or Miden token).

Under the hood: the node can still break that lump sum into verification, storage, etc. so that users never have to juggle five separate fee fields.

TL;DR: I think starting with the simplest possible fee mechanism is best, let pioneers build against it, and iterate toward full EIP-1559 granularity once we are live and working towards a decentralized operator set.

Fee mechanism #1217

Uh oh!

Uh oh!

PhilippGackstatter Nov 15, 2024 Collaborator

Replies: 26 comments · 22 replies

Uh oh!

bobbinth Nov 16, 2024 Maintainer

Uh oh!

bobbinth Nov 24, 2024 Maintainer

Uh oh!

PhilippGackstatter Nov 25, 2024 Collaborator Author

Sponsored Transactions

Uh oh!

Uh oh!

Mirko-von-Leipzig Nov 28, 2024 Collaborator

Uh oh!

Uh oh!

bobbinth Dec 1, 2024 Maintainer

Uh oh!

bobbinth Dec 1, 2024 Maintainer

Uh oh!

PhilippGackstatter Feb 4, 2025 Collaborator Author

Uh oh!

Uh oh!

Mirko-von-Leipzig Feb 4, 2025 Collaborator

Uh oh!

PhilippGackstatter Feb 4, 2025 Collaborator Author

Uh oh!

bobbinth Feb 5, 2025 Maintainer

Uh oh!

Uh oh!

PhilippGackstatter Feb 26, 2025 Collaborator Author

Transient and Non-Transient Costs

Uh oh!

Uh oh!

PhilippGackstatter Mar 5, 2025 Collaborator Author

EIP-1559 in Miden

Fee computation

Base Fee Burn

Uh oh!

bobbinth Mar 6, 2025 Maintainer

Uh oh!

PhilippGackstatter Mar 6, 2025 Collaborator Author

Uh oh!

bobbinth Mar 6, 2025 Maintainer

Uh oh!

PhilippGackstatter Mar 12, 2025 Collaborator Author

Incentives

Block Producer

Batch Producer

Summary

Pay Fee Procedure

Local Transactions

Network Transactions

Block Producer Reward

Uh oh!

Mirko-von-Leipzig Mar 12, 2025 Collaborator

Uh oh!

Mirko-von-Leipzig Mar 12, 2025 Collaborator

Uh oh!

bobbinth Mar 13, 2025 Maintainer

Uh oh!

PhilippGackstatter Mar 14, 2025 Collaborator Author

Block Producer Tip Claiming

Batch Producer Tip Claiming

Non-native assets in batches

Avoiding the base fee burn

Uh oh!

bobbinth Mar 15, 2025 Maintainer

Uh oh!

bobbinth Mar 15, 2025 Maintainer

Uh oh!

PhilippGackstatter Mar 18, 2025 Collaborator Author

Uh oh!

bobbinth Mar 21, 2025 Maintainer

Uh oh!

PhilippGackstatter
Nov 15, 2024
Collaborator

Replies: 26 comments 22 replies

bobbinth
Nov 16, 2024
Maintainer

bobbinth
Nov 24, 2024
Maintainer

PhilippGackstatter
Nov 25, 2024
Collaborator Author

Mirko-von-Leipzig
Nov 28, 2024
Collaborator

bobbinth
Dec 1, 2024
Maintainer

bobbinth
Dec 1, 2024
Maintainer

PhilippGackstatter
Feb 4, 2025
Collaborator Author

Mirko-von-Leipzig
Feb 4, 2025
Collaborator

PhilippGackstatter
Feb 4, 2025
Collaborator Author

bobbinth
Feb 5, 2025
Maintainer

PhilippGackstatter
Feb 26, 2025
Collaborator Author

PhilippGackstatter
Mar 5, 2025
Collaborator Author

bobbinth
Mar 6, 2025
Maintainer

PhilippGackstatter
Mar 6, 2025
Collaborator Author

bobbinth
Mar 6, 2025
Maintainer

PhilippGackstatter
Mar 12, 2025
Collaborator Author

Mirko-von-Leipzig
Mar 12, 2025
Collaborator

Mirko-von-Leipzig
Mar 12, 2025
Collaborator

bobbinth
Mar 13, 2025
Maintainer

PhilippGackstatter
Mar 14, 2025
Collaborator Author

bobbinth Mar 15, 2025
Maintainer

bobbinth Mar 15, 2025
Maintainer

PhilippGackstatter Mar 18, 2025
Collaborator Author

bobbinth Mar 21, 2025
Maintainer