Cosmos-sdk: 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)
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 #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

• [X] Not duplicate issue
• [X] 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.