Refunding unused but allocated gas

[ValarDragon]

Summary

We currently charge for all allocated gas, even if it was unused. This creates a tension between the amount gas simulation tells you you need, and the overhead you allow in case some state change makes you have to spend a bit more in order for your tx to remain in everyones mempool. We should refund in some capacity the allocated gas that wasn't used, as that incurred no cost to each node on the network. (Though it may have had some affect on block building -- more on that in the following)

Problem Definition

Why do we need this feature

I think it is going to be unnecessary extra decision / mental overhead of figuring out how much gas to use. (Do you use exactly the minimum which simulation says, and risk it not being propagated, do you do some multiplicative adjustment and just take the cost, do you try to use whats default and not worry about the money your inadvertently burning) This sort of decision fatigue is a serious concern, and may end up driving normal people away from the network. (Or at the very least, cause them to burn extra money which I think is bad)

What Ethereum does

Due to other design choices Ethereum has made, they only charge for the gas used, not gas allocated. (By refunding, but they cap refunds at 50% of provided gas limit, src: https://github.com/ethereum/wiki/wiki/Design-Rationale#gas-and-fees) I haven't been able to find a source online which indicates if they use gas allocated vs gas refunded to account for the block gas limit though.

However this means in the current model this is mental overhead our users have that they wouldn't have on other similar cryptocurrencies.

Problems that arise

The "Naive" solution of refund all unused gas has problems. An adversary could just set their allocated tx gas to be a large number, preventing other txs from getting into the block at no cost.

Proposal

Proposed solution to adversarially increasing gas allocated

I think this should be resolved with 2 mitigation techniques:

1. Limit the percentage refunded (what Ethereum does), this means the multiplicative factor by which a tx can overallocate gas is limited. (e.g. 1.5, or 2). gas_charged = max(gas_used, gas_wanted / 2)
2. Have the default mempool priority function be dependent on gas. So even if you overestimate your gas, you still have to increase your fee by some extent for network propagation / block inclusion. (Ref genesis: Ensure there are no duplicate accounts in genesis file #2275 for priority function)

Implementation details

We currently have no "EndTx" (AFAICT), so we can refund the gas in endblock. (We can append pointers to the gas meters in a linked list thats cached in the context, and empty this linked list / array in EndBlock)

We don't need to worry about the percentage operations taking lots of computation time, as they are on pure int64s. (We may even be able to do some stuff with SIMD as well)

I think this is something we should do soon after mempool sorting postlaunch.
/cc @cwgoes

---

For Admin Use

• Not duplicate issue
• Appropriate labels applied
• Appropriate contributors tagged
• Contributor assigned/self-assigned

[alexanderbez]

iirc, the block gas limit is based on each txs gas limit (allocated) and not the refunded amount.

[jackzampolin]

Is this something we still need to do?

[alexanderbez]

Yes, I do think it is something we should incorporate into the SDK/gaia. The mempool updates seem out of scope, but something similar to item (1) in the proposal is what we can accomplish for this feature.

[readygo586]

Is this feature ready to release now?

[alexanderbez]

We haven't implemented this yet @readygo586

[readygo586]

Got, thanks very much @alexanderbez

[alexanderbez]

A rough idea would be to track unused gas and refund during EndBlock.

[zmanian]

Just leaving a note here.

It's important to implement this in way that disincentivizes a denial of service attack where the attacker requests a large amount of gas at high prices and fills a block but the actual execution is much less gas and the entire amount is refunded.

[alexanderbez]

@zmanian, the DoS here is not allowing, otherwise valid txs, to be included in the block because the block's gas is filled to the max, correct?

[zmanian]

Yes the DOS is basically cheaply blocking access to the network.

Was explaining this to the LazyLedger team and wanted to make sure we recorded this.

[alexanderbez]

Noted! Do you have suggestions on how to approach this? I can't think of any immediately apart from the state-machine knowing the "average" gas prices for specific kinds of messages and then doing an inspection on a tx to potentially reject it.

[okwme]

@sunnya97 didn't we discuss this before? I'd suggested something about gas credits that could be used on subsequent transactions maybe? Can't remember exactly...

[alexanderbez]

It's trivial to refund gas. It's not trivial to design a measure against the DoS attack laid out.

[ValarDragon]

This problem is talked about in the original post for this issue under the problems that arise and proposed solution sections =/.

The proposed solution of this issue was to bound the degree to which you can over-allocate, and to still make gas allocation impact mempool prioritization. Supposing that one can only over-allocate c% of gas and get a refund, the amount of wasted gas in a block is at most c%.

(The details of how to impact mempool prioritization being left to a separate, more thorough mempool discussion)

There are other things you can do

1. Removing Variance from actual execution times
2. Always charge at maximal execution time
3. Always charge at average execution time (quite hard to do in the face of adversarial behavour)
4. Create a 'gas credits' system. Needs careful system engineering to ensure that the cost of executing refunds doesn't exceed the cost of the refund itself.

I am not aware of other solutions.

I'm vastly in favor of putting a multiplicative bound as a first-order solution, due to its simplicity, and empirically proven effectiveness. Its trivial to see what is the maximum potential wasted gas you can have under this with malicious behavior, and in exchange the actual users get to significantly benefit from refunds.

[ethanfrey]

This is a HUGE item for client side UX. Even allowing refunds for a 2x overcharge would make this much nicer for the client to estimate and not be a huge DoS vector.

[zmanian]

There is a some upperbound on how much gas refunding you can do until we improve the Tendermint mempool to enable Quality of Service under load. I think it's maybe 1.5x gas consumed but I agree that it would improve UX.

[xiangjianmeng]

There is a some upperbound on how much gas refunding you can do until we improve the Tendermint mempool to enable Quality of Service under load. I think it's maybe 1.5x gas consumed but I agree that it would improve UX.

Yes, I could not agree more

[alexanderbez]

One thing we did not cover in ProcessProposal in the Phase I of ADR ABCI 1.0, is the idea of "immediate execution", in fact, we state that we discard processProposalState.

We could make a modification to ProcessProposal to execute the entire block along with the transactions and keep the ephemeral processProposalState, which we'll commit when the ABCI client executes Commit (assuming we don't reject the proposal).

If we take this approach of "immediate execution", which would render DeliverTx void, then what we can do is utilize the entire gas consumed instead of wanted and mark that as the gas that's consumed for the entire block. Finally, we can safely and effectively refund any unused gas/fee for each tx and avoid any DoS issues.

cc @adu-crypto

---

@ValarDragon @marbar3778 what are your general thoughts on executing the entire block in ProcessProposal and making DeliverTx void?

[yihuang]

what are your general thoughts on executing the entire block in ProcessProposal and making DeliverTx void?

We've talked about this in ethermint before, that's the current ethereum behavior.

[alexanderbez]

@marbar3778 stated that he fears revising ProcessProposal in the Phase I ADR would introduce scope creep, so it seem we'll have to push this back to the release after 0.47.

[tac0turtle]

This would be amazing, but want to ship 0.47 fairly quickly in order to get much needed features to users

[dakom]

Naive question, I'm sure, but why does the block gas limit depend on gasWanted instead of gasUsed?

What I mean is - if the block limit only cared about the actual gas used, then refunds wouldn't matter and couldn't be used as a denial of service attack.

In general this seems like the way it should work at first glance. Fitting Txs in a block should ideally be a matter of the actual work that needs to be done, not a matter of a client's best-guess...

No doubt I'm missing something, but if it's more of a "it currently doesn't work that way" as opposed to "it can't ever work that way", might be worth thinking about?

[yihuang]

Naive question, I'm sure, but why does the block gas limit depend on gasWanted instead of gasUsed?

What I mean is - if the block limit only cared about the actual gas used, then refunds wouldn't matter and couldn't be used as a denial of service attack.

In general this seems like the way it should work at first glance. Fitting Txs in a block should ideally be a matter of the actual work that needs to be done, not a matter of a client's best-guess...

No doubt I'm missing something, but if it's more of a "it currently doesn't work that way" as opposed to "it can't ever work that way", might be worth thinking about?

Because currently it don't execute the tx before including into block, only do some fast checks, but with the new PrepareProposal protocol, it'll be possible

[dakom]

Oh, cool, interesting... I'll take a look at that. Thanks!

[robert-zaremba]

Also max gas is the most pessimistic scenario, most of the transactions shouldn't even use that.

[alexanderbez]

Oh, cool, interesting... I'll take a look at that. Thanks!

This will change soon-ish with the advent of ABCI 1.0 and optimistic execution.

[ethanfrey]

This will change soon-ish with the advent of ABCI 1.0 and optimistic execution

"optimistic execution"?
sounds exciting. tell me more.

[yihuang]

Now we have the PrepareProposal, what's plan to push forward this?

[robert-zaremba]

@yihuang I have draft implementation for Umee. We still need to test it (didn't have time). Few weeks ago I was proposing to port it to SDK, but @tac0turtle didn't want that.

[JayT106]

@yihuang I have draft implementation for Umee. We still need to test it (didn't have time). Few weeks ago I was proposing to port it to SDK, but @tac0turtle didn't want that.

@robert-zaremba do you have a link to share your proposal or the implementation? And what's the concerns porting it to the SDK from @tac0turtle?

[rootulp]

I have a few thoughts regarding the What Ethereum does section in the original issue.

By refunding, but they cap refunds at 50% of provided gas limit

I think this line meant to state "gas used" instead of "gas limit". Also note that in EIP-3529 which was included in the London upgrade, the MAX_REFUND_QUOTIENT changed from 2 => 5. Put another way, Ethereum gas refunds are capped at 20% of gas_used. See the rationale here.

However, that notion of gas refunds is applicable to clearing Ethereum account storage. Cosmos doesn't have a notion of clearing account storage. The gas refunds proposed in this issue pertain to gas remaining at the end of ordinary Cosmos transactions.

AFAICT this issue is more comparable to how Ethereum handles gas metering for ordinary transactions. I think these lines of EIP-1559 are more applicable. Ethereum gas refunds are gas remaining * gas price. Note this is also in line with the Ethereum Yellow Paper:

It is named gasLimit since any unused gas at the end of the transaction is refunded (at the same rate of purchase) to the sender’s account.

In conclusion, I think it is viable to cap the max gas refund for Cosmos transactions to some portion of gas_used but I want to clarify that this proposal doesn't exactly mirror Ethereum behavior.

[zramsay]

we ran into this issue with the Laconic testnet: https://git.vdb.to/cerc-io/laconicd/issues/55