Gas fee model

[maxgillett]

This note discusses at a high level how gas fees could work in Polygon Miden, and assumes familiarity with the discussions/issues here: #192 #222 #231

Gas metering could be done directly within the VM by counting the number of rows used in the main trace and for each of the coprocessors. Because coprocessor traces share rows with the main processors, we primarily need to be concerned with overall trace length. However, as each coprocessor may carry an additional computational overhead, we may need to weight each row type according to its computational cost.

To determine the row count of the main processors, one could add a column to the main trace that is incremented by $1$ at each step and is enforced by a continuity constraint. The final value could be read out through an assertion or permutation product column. There may be a more efficient approach.

To track coprocessor usage, there are at least two solutions:

• To track usage at a granular level, we can introduce an additional "Gas Meter" coprocessor that is tasked solely with counting the number and type of other coprocessor instructions. This could be achieved by introducing constraints that force coprocessors to multiply their permutation product by an additional value encoding the instruction type when certain computations are completed. This value must then be divided out by the Gas Meter to satisfy the final assertion on the permutation product column, with constraints in place to ensure that division counts are available to other processors.
• To track usage at a less granular level, we can take advantage of the incremented column of accesses available in some auxiliary traces (for example, in the hash coprocessor). Instead of tracking the counts of coprocessor calls, we could enforce a constraint at the coprocessor boundary (the final row in its trace) that multiplies the permutation product by the row count value, and as described in the previous bullet point, divides out this value in a separate metering coprocessor. This might incur less overhead than tracking operations within the coprocessor at the expense of losing some information about the distribution of operation types applied within a given coprocessor.

To pay the gas fee to the sequencer, a kernel call pay_gas_fee could be made in the epilogue of the transaction. For example, this call could use the counts available in the Gas Meter coprocessor described above to compute the fee, and decrease (increase) the asset balance in the vault of the account (sequencer) by this amount directly. Alternatively, a note could be produced by the account with the fee amount containing a script root that restricts consumption to the sequencer. In this case, the sequencer will need to be able to efficiently aggregate these for consumption if they each contain only a very small amount of fees.

Open questions:

• Can we safely assume that run time is linearly related with overall trace length and just ignore details of trace construction? If not, then:
  • How carefully do we need to track the usage of the various coprocessors?
  • Which operations in each coprocessor are expected to dominate run time?
  • Should parallelizable transactions be given a fee discount? How would this be achieved?
• The sequencer will need to make available the latest execution costs (e.g.fee_per_row) which may need to be updated as hardware matures and costs decrease. One possibility is to keep these values in storage variables of the sequencer's account, and expose them through getter functions in the kernel.
• Transactions might have more than one account input, in which case we need to specify which account is paying the fee. Furthermore, we need to keep track of whether the selected account has authorized a fee to be paid. Should this authorization be implicitly provided in account code and note scripts, or explicitly given when constructing the transaction? At the very least, it is probably wise to add a max_fee field to the transaction to place a cap on the gas fee paid.
• Should we support meta transactions, where other smart contracts can pay on the transacting account's behalf for some or all of the gas fee? If a smart contract wants to pay only for its portion of execution trace, then we may need to add something like a gasleft kernel operation.
• This section did not discuss how writing to state stored on L1 should be charged. The mechanism to track writes could be similar to that proposed above for coprocessors, but specifics may depend on the storage model, and will be left for a later discussion.

[bobbinth]

Thank you for starting this! A few thoughts from my end:

Can we safely assume that run time is linearly related with overall trace length and just ignore details of trace construction?

I'm hoping that we can. It would be really nice if the fee was driven by as few factors as possible, and taking the overall length of the execution trace as one of these factors would be a pretty clean way to do it. My initial thinking is that the difference between different co-processor rows is fairly small as compared to the overall proof generation process. So, maybe this difference won't play any meaningful role (i.e., if the difference between a more accurate and a less accurate methodology is 5% - 10%, I think we can safely go with the less accurate one). But more thinking is needed on this.

Another component in this is that we'd actually have two different parts which could affect fees:

1. Transaction execution fees - these are for network transactions. Basically, for transactions which don't include a ZKPs attesting to the correct execution of related scripts, someone needs to generate these ZKPs. Most straightforwardly, it would be the block producer - though, there could be other interesting ways of handling this. So, the block producer would need to be compensated for their work.
2. Transaction aggregation fees - these are for (recursively) aggregating transaction proofs into block-level proofs. Basically, given $n$ transactions proofs (some of which could have been generated locally, but others could have been generated by the block producer as described in the previous point), the block producer would need to generate a proof attesting to the correct verification of all these $n$ proofs.

I think considerations for handling these would be quite different.

Conceptually, aggregation fees are relatively simple. A few thoughts on these:

1. Variance between verification costs of transaction-level proofs would be relatively small. This is because STARK verification costs grow logarithmically with the complexity of computations. So, for example, even if executing transaction A is 1000x more expensive than executing transaction B, verifying a proof of A could be just 2x more expensive than verifying a proof of B (these numbers are just to illustrate a point, actual numbers may be different). We'll need to come up with a measure of estimating complexity or proof verification - but I think that should be fairly straightforward: there are only 19 possible options (for traces between $2^{10}$ and $2^{29}$ rows) and cost of verifying any two proofs at the same level is exactly the same.
2. We need to impose a limit on the max complexity of the verification of block-level proofs. Conceptually this is similar to imposing some gas limit for an entire block - but I think our task is much simpler here. This is also because computation needed to verify a block proof is pretty cheap (i.e., probably not more than a few dozen milliseconds). My guess is that bigger cost components would be: (a) propagating a block through the network, and (b) updating the local storage (account, note, nullifier databases). One simple (though imperfect) way to handle both is to impose a block size limit for the proof + associated public inputs.

Handling transaction execution fees is probably a bit more complex. A few thoughts on these:

1. As mentioned above, these are only relevant for network transactions (not for local transactions).
2. I don't believe we need to impose a "max gas limit" on these. Meaning, a transaction could be arbitrarily complex (though, this complexity is capped by the maximum number of cycles of $2^{29}$), and a block producer could chose to execute it based on the fee included with the transaction.
3. I think fee_per_row might be too granular. For proof generation purposes we always have to round up to the next power of two. So, while the trace itself could be any number of rows, the difference in complexity between generating a proof for a computation requiring 1025 rows vs. 2046 rows is pretty negligible. So, here again we probably have just 19 possible "fee buckets".
4. I like the idea of pay_gas_fee kernel call. This would basically mean that the fee becomes another output item of transaction execution process (similar to updated account storage, created notes, and new nullifiers). This approach could work well for both types of fees (transaction execution and aggregation). But I think we need to flash it out a bit more to see how it would actually be used in different types of transactions.

Should we support meta transactions, where other smart contracts can pay on the transacting account's behalf for some or all of the gas fee?

I'd like to support this. Basically, ideally, the fee would be just one of the outputs of a transaction, and then it would be up to a specific note/account logic to figure out how to make sure that the fee is attractive for the block producer to execute and aggregate this transaction into a block. I think the challenge here would be to provide enough machinery to make fee estimation as simple as possible. Maybe we should start with simple transaction types (transfers between two accounts) and see how it could work, and then expand to more complicated scenarios.

Another consideration: I think there are benefits to having the general fee structure be similar to how it now works in Ethereum where we have a base fee, which gets burned, and then a tip which is paid to the block producer. But I haven't thought too much about how it could work in our context (this might be especially difficult if we support fees payable in any asset).

[maxgillett]

My initial thinking is that the difference between different co-processor rows is fairly small as compared to the overall proof generation process.

Ok, that's reassuring to hear. It seems like some amount of metering at the coprocessor level will still need to be done to track L1 state-related expenses, such as storage updates and (if not in a Validium mode) calldata, but I'd like to hear if you have different thoughts about this. This is also getting at a deeper question which I didn't directly address above, which is how much of the fee logic should be constrained by the AIR versus market-driven and estimated offline. I can see arguments for both sides.

Another component in this is that we'd actually have two different parts which could affect fees:

Yes, one possibility is to pass fees up the "stack." For example, to interact with a DEX, a user would submit a note that would be batched together with other users interacting with the same contract. The transaction prover would construct the transaction that orders the consumption of these notes as well as the accompanying transaction proof. Each of these notes would contain fee logic that would direct fees to the transaction prover (e.g. pay_prover_gas_fee). The transaction prover would take a cut of the aggregate fees according to the bucketed trace length, and pay the rest to the block producer/sequencer (e.g. pay_sequencer_gas_fee could achieve this) to account for their costs associated with L1 state updates and recursive proof verification. Any dust left over can be returned to the user in each output note of the transaction (along with the swapped tokens). I'm imagining that both the prover and sequencer account IDs are provided as public inputs to the transaction.

I don't believe we need to impose a "max gas limit" on these.

I was mainly thinking about how to prevent high unanticipated gas fees. Perhaps this could be solved through gas estimation in a wallet, but I could imagine cases in which gas usage is not deterministic when the user takes an action (for example, in the DEX note example above). This might only be a problem in those situations, and can just be handled in note scripts.

I think fee_per_row might be too granular.

Yes, I agree that bucketing is better, also given that proof generation time doesn't linearly scale with trace length. Charging a fee per row would make more sense in a bootloader approach, where traces of scripts/programs are appended and a single proof is generated over a very large trace.

I think there are benefits to having the general fee structure be similar to how it now works in Ethereum where we have a base fee, which gets burned, and then a tip which is paid to the block producer

Yes, I agree, especially given how much research went into the mechanism in EIP 1559. The main difference in our context is that there is higher overhead for the sequencer, but this would just be reflected in a higher priority fee.

[bobbinth]

It seems like some amount of metering at the coprocessor level will still need to be done to track L1 state-related expenses, such as storage updates and (if not in a Validium mode) calldata, but I'd like to hear if you have different thoughts about this.

I haven't thought about it too much yet. But yes, I agree, transaction fees would need to be informed by L1 costs in some way. I wonder if this can be estimated relatively simply though. I think most of transaction-dependent L1 costs would be calldata costs and should be directly proportional to the size of public inputs needed to verify transaction execution.

how much of the fee logic should be constrained by the AIR versus market-driven and estimated offline

I tend to think that the more can be pushed to market-driven estimation the better. One crucial thing here is that this estimation should be pretty straightforward (which, I hope, will be easier to achieve in our context as compared to others).

The transaction prover would take a cut of the aggregate fees according to the bucketed trace length, and pay the rest to the block producer/sequencer (e.g. pay_sequencer_gas_fee could achieve this) to account for their costs associated with L1 state updates and recursive proof verification.

I think this would be very cool to do it this way - but I think there might be some challenges as well. One thing we should probably do sooner rather than later is to describe the overall execution model (I have it on my TODO list, but haven't gotten to this yet). Basically, who are the entities, what their roles are, how they process different types of transactions etc.

Charging a fee per row would make more sense in a bootloader approach, where traces of scripts/programs are appended and a single proof is generated over a very large trace.

Yep, I think we lose some efficiency by not following this approach, but I think we gain in simplicity and flexibility.

Perhaps this could be solved through gas estimation in a wallet, but I could imagine cases in which gas usage is not deterministic when the user takes an action

Yes - I think we need to be able to handle these situations. We probably need an instruction that gets the current trace length (we already have a column in the trace which tracks this, but it is not exposed to the user), and probably a procedure that does something like next_power_of_two. Based on this info and some public inputs which give info about average fees from last block (or something similar) it should be possible to estimate fees dynamically. But more thought is needed here.

[frisitano]

I haven't thought about it too much yet. But yes, I agree, transaction fees would need to be informed by L1 costs in some way. I wonder if this can be estimated relatively simply though. I think most of transaction-dependent L1 costs would be calldata costs and should be directly proportional to the size of public inputs needed to verify transaction execution.

I tend to think that the more can be pushed to market-driven estimation the better. One crucial thing here is that this estimation should be pretty straightforward (which, I hope, will be easier to achieve in our context as compared to others).

Does this mean that the validator set / sequencers market-driven estimations can influence the behaviour inside of the VM? Does this introduce potential security vulnerabilities?

I wonder if there should be a separation of concerns. The virtual machine could be exclusively focused on executing VM state transitions and metering compute usage. This compute usage report can be an output provided to the outer runtime. It is then the responsibility of the runtime to combine compute usage report, storage usage, IO usage and market-driven estimations of L1 costs to determine a final fee. This fee would then be payed in a native token that exists on the runtime layer and verified by consensus.

To think a little more on this - how do you anticipate decentralisation working in this model where the native token exists within the VM. Does this mean that all of the platforms consensus / finality logic would have to be implemented inside of the virtual machine? How can we slash a dishonest sequencer in a PoS model for example?

[bobbinth]

Does this mean that the validator set / sequencers market-driven estimations can influence the behaviour inside of the VM? Does this introduce potential security vulnerabilities?

I am not sure it does. To clarify what I meant by "market-driven estimation", let's consider this simplified model:

• Let's say a transaction would pay fee x to the block producer if the block producer includes it in a block.
• Let's also say that this transaction would result in L1 fee of y if it gets included in a block.
• If x is less than y, block producers should not process the transaction. So, the task of the transaction originator is to estimate such a fee x that it would exceed y.

Basically, the "influence" of a block producer should be limited to selecting a set of transactions which they deem attractive enough to process. The tricky part is to make estimation of x as strait-forward as possible to ensure that it is always greater than y but at the same time is not too much greater.

Another tricky part is how to handle temporal fee variability. There could be a substantial delay between when a block producer process a transaction and when a proof is submitted to L1. The value of y in the example above could change significantly during this time. This is still an open question.

Does this mean that all of the platforms consensus / finality logic would have to be implemented inside of the virtual machine?

In principle I don't see an issue with this. If the logic is deterministic and can be executed on a Turning-complete VM, then we can generate a proof that it was executed correctly. However, I'm sure there is a lot of complexity in the details - and I haven't really spent much time thinking them through.

In general, the approach we are taking is to first build the rollup using a centralized block producer, and then, once this is up and running, figure out the best path toward decentralized block production. Decentralization is definitely the end goal - but we are taking it one step at a time.

I wonder if there should be a separation of concerns.

Yes, absolutely. The way we are thinking about this is to have two different "kernels" for the VM. One kernel for executing transactions, and the other one for aggregating transactions and ensuring correctness of higher-level logic.

[frisitano]

I am not sure it does. To clarify what I meant by "market-driven estimation", let's consider this simplified model:

• Let's say a transaction would pay fee x to the block producer if the block producer includes it in a block.
• Let's also say that this transaction would result in L1 fee of y if it gets included in a block.
• If x is less than y, block producers should not process the transaction. So, the task of the transaction originator is to estimate such a fee x that it would exceed y.

Basically, the "influence" of a block producer should be limited to selecting a set of transactions which they deem attractive enough to process. The tricky part is to make estimation of x as strait-forward as possible to ensure that it is always greater than y but at the same time is not too much greater.

Another tricky part is how to handle temporal fee variability. There could be a substantial delay between when a block producer process a transaction and when a proof is submitted to L1. The value of y in the example above could change significantly during this time. This is still an open question.

Yeah this makes sense. I wasn't sure how the temporal variability of L1 settlement was accounted for and assumed that the suggestion was allow the sequencer to inject some sort of fee multiplier that would account for this but your explanation makes sense.

In principle I don't see an issue with this. If the logic is deterministic and can be executed on a Turning-complete VM, then we can generate a proof that it was executed correctly. However, I'm sure there is a lot of complexity in the details - and I haven't really spent much time thinking them through.

I think it should be possible and if I am not mistaken I believe Solana have their consensus implemented using their smart contract execution engine. However, I wonder what the overhead will be in terms of performance.

[bobbinth]

Another thing to note is that the above actually implies that we need two different kernels:

1. A kernel for transaction-level execution (this is the one with transaction prologue, epilogue etc.).
2. A kernel for aggregating transactions-level proofs into block-level proofs.