Another simple Gas fee model: The "Escalator Algorithm" from the Agoric Papers

Economics
21

But you seem to engineer for this one very specific usecase (getting in high urgency transactions) without addressing everything else that EIP1559 does. EIP1559 actually makes sure that the amount of times blocks are full is very small, so this should be an exceedingly rare situation, whereas with your algorithm, this would still be the case most of the time (assuming a future network that is well used and so there are always low-value transactions that could fill up any “cheap” capacity).

It seems that your idea would be more of a possible extension of EIP1559: If blocks are full (as in actually 100% full), then you can add an escalating tip to your transaction to indicate it’s urgency. This seems to be much better than your proposal (but I don’t really know if it’s worth it because blocks being full for more than a few blocks can’t really happen in EIP1559 unless someone wants to pay through their nose for it).

22

Just to clarify: I did not author the escalator algorithm, it was authored in 1988 by Mark Miller and Eric Drexler. Miller is cited in the original Ethereum Yellow Paper for being a pioneer of the concept of smart contracts. So this algorithm is not authored in response to eip-1559.

In the EIP I wrote suggesting an Ethereum-version of the escalator algorithm I compare 1559, current gas auction, and the escalator algorithm under a variety of conditions, not just block fullness under volatile conditions. I responded in this case about volatile conditions because I was responding to a post that suggested block capacity was my primary motivation.

Just because there aren’t any transactions left offering the current price tier doesn’t mean there isn’t a huge backlog of transactions at a more common price tier. And at each price tier, all transactions offering it or higher are treated as peers, and no priority is given to any transactions for a higher price other than the tip, which is meant to be unrelated to urgency.

To me this seems like more than “just one situation”, this is about the fundamental role of transaction pricing in blockchains.

23

Well the problem is it doesn’t. In a future where Ethereum has grown to a large amount of usage, and with first price auctions (and the escalator algorithm is still a first price auction, just with automatic bidding), there is just no such situation as “blocks being half full”. There is always someone who would fill blocks up at a low enough transaction price, no matter what.

Compared to that, EIP1559 guarantees that blocks will almost always be half full and the marginal cost of another transaction is almost perfectly predictable. However, In this case, you write about EIP1559: “User can wait for a better price, but may need to resubmit re-signed transactions.” – this is wrong! The user quotes the maximum basefee they are willing to pay, but they only expect to pay the current fee determined by consensus. This means they do not have to resubmit in the case where the basefee rises.

So it seems to me that in the normal operating mode, EIP1559 is far superiour to your suggestion. The only advantage your algorithm has is if you have a spike of many completely full blocks (should never really be more than 10-20 blocks in EIP1559, actually, because the price would rise very fast with it), and you have a transaction that absolutely cannot wait for those 10-20 blocks. Then you may have to bid a higher tip, and I can see how it would be an improvement to use the escalator algorithm to automate increasing the tip.

24

I meant for transactions that have cumulativeGasUsed >= the voted on block gas limit, rather than entire blocks. This could be fair because the miners have voted on the block gas limit. A single miner adding transactions beyond this voted upon gas limit, increases the resources required for other miners to catch up, and thus should burn the fees to reimburse all other miners that must download and validate these larger-than-normal blocks.

This was just an idea about how to handle the surge volume, not a fully thought out proposal. I think surge volume should be addressed after this EIP, because it may not even be an issue if people can adequately express the urgency of their transactions.

By “the user can’t adequately express the desired gas price” I’m referring to the current state. Because a user cannot express the min/max fee they wish to pay and how long they would wait today, they often pick the highest fee they would pay in times of congestion to avoid getting into a stuck transaction state or having to resubmit transactions. They end up either hugely overpaying, or it’s too late by the time the transaction is included. This is the most pertinent UX issue that needs to be solved IMO.

First price auction already works great when there is less than spikey usage and for non-urgent transactions. The UX isn’t bad either–wallets either hide it completely and choose a reasonable gas price, or give you a slider. It’s only when transaction volume is spiking that the UX degrades into something unusable (arbitrary inclusion times, dropping from mempool, resubmitting with different gas prices). So it seems wise to try to address this particular situation with a simpler (less different) solution before completely changing how gas prices work for a bevy of other improvements which may or may not work how we expect.

25

Wow, that’s not my experience at all – I have had transactions stuck for hours using transaction fees by current wallets/dapps. So I’d definitely disagree with “works great”!

And you forget there are two components for this – UX and the fees paid by users. You can have a great UX right now if you always bid 1000 GWei gas. But that would be very expensive. EIP1559 will also make the fees come down by not making every block a first price auction.

26

You’ve taken this quote out of context. The quote you’ve selected is specifically addressing what the ideal user strategy is in a situation where a user wants a better price than the current base_fee and is willing to wait for a longer confirmation time. Under 1559, this scenario gives a user no choice but to bid below the current price, which puts them at risk of needing to re-submit a bid in the case that their time preference is closing.

This is another example of how “time preference” is not represented in the current 1559 models. Many situations, especially ending auctions, have higher urgency at the end of a time period, and a user may want the best price they can get within that time period.

Other than the benefits I highlighted in my EIP, a couple new benefits were made apparent to me in today’s implementer’s call:

  • 1559 has backwards-compatibility issues that make the transition process difficult.
  • Since miners select the transactions to include, they can collude to always select half-full blocks to push the base fee down, converting the tip parameter to be a a single-price auction like today, thus reducing 1559 to the current mechanism.

That second concern seems pretty alarming to me. I do not think we should be casual about adopting protocol changes where we are actively discovering new flaws in.

27

Sorry, this is correct, I misread that. So the advantage would be for users who want to get a transaction below the current basefee included. How often this is the case in EIP1559-land, when the basefee would be representing a moving average, is at least dubious to me. Basically this would happen when you want a non-urgent transaction included in a usage surge.

What are these?

However, in this process, they would be forgoing all the tips that are sent to them otherwise. That seems to necessitate a large number of miners colluding.
If we assume this, then I think the current algorithm and the escalator algorithm would also degenerate and miners could extract much larger value. For example miners could just collude to generally only include transactions which pay more than 100 GWei gas.

28

Typical gas prices are less than 50 Gwei and typical time to inclusion is on the order of minutes. These also usually scale well with how much you’re willing to pay. In my experience, the system only breaks down during times of congestion.

If a particular wallet has a bad UX or picks bad gas prices and gets stuck, IMO that’s because today it’s particularly difficult to pick a fixed ‘correct’ gas price for the transaction, and to know when the transaction should be resubmitted. This EIP makes that a much easier problem in 2 ways: transactions expire after a wallet specified timestamp, and gas price can be a function of time allowing the supply side to participate in selecting the ‘correct’ gas price.

If EIP 1559 is not superior in times of congestion, where the UX suffers the most, is it worth a complete overhaul of the gas price system? Especially when compared to a much simpler backwards compatible feature that is strictly better than the current state?

29

I think that is a mischaracterization of EIP1559. It would only perform worse for extremely urgent transactions (that need to be included in very few, like <10) blocks. If a transaction is that urgent and valuable, it feels like the sender could easily include a large tip to remedy this problem.

30

In times of congestion, lots of people have urgent and valuable transactions (e.g. keeper auctions, borrowers avoiding liquidation, oracle updates, arbitrageurs), otherwise they wouldn’t bother with 200 Gwei gas prices. How does tip then not just turn into a first price auction in times of congestion?

31

I think the concern was that because 1559 transactions are not equivalent to current transactions, there is a challenge in how to migrate all software gracefully over. One way is to temporarily support both types, but it seemed to be undefined how the two transaction types would both be supported at once.

That might be true, I’m not sure. Was just highlighting it since it was raised as another possible concern.

This seems like a large leap of logic to me that doesn’t follow. The escalator algorithm doesn’t suffer from the same miner-collusion concerns because it isn’t trying to withhold a portion of the transaction fee from miners.

I think this may be an important key point that highlights a challenge that EIP-1559 faces, along with the type of uniform-priced auction it is based on: They both try to enforce a type of second-price auction at the protocol level.

Second-price auctions typically require closed-bids, and in this case (a public blockchain) not only are the bids open, but the bids are processed by the recipient, who has the ability to add and withhold bids freely to manipulate the outcome. I think this may indicate that closed-bid auctions (like second-price auctions) are effectively impossible to enforce under these conditions, which may be why many of these threads come down to “Well then you can just use the tip parameter”, and “But isn’t that just reproducing the current structure?”.

1 Like
32

vs.

The last quote seems to be where the misunderstanding on your part is. EIP1559 is very carefully crafted to make rational miners behave in a way that they will enforce this, without the need of closed-bid auctions. If you’re “not sure” how this works, then you probably haven’t understood the mechanism.

33

Sorry, I hadn’t reviewed that point closely. Your points are consistently not adding up.

I can now say confidently: “That” is not true. If miners were to collude to only submit half-full blocks to reduce the base_fee so that more funds would be free for the tip parameter, they would not forego the tips for the transactions they included, and so obviously they would not forego “all the tips” like you suggested, and I’m surprised you would suggest something so absurd, while throwing around “you must not understand 1559” claims.

A plausible scenario: Miners normalize the practice of only including half-full blocks, and prioritizing by tip, which reduces 1559 to the current first-price auction mechanic. This is possible because the miners are not incentive-aligned with the fee that users are paying in 1559. By trying to withhold the fee at the protocol level, 1559 introduces an incentive to side-game the auction. This is in direct contrast with 1559’s stated goal:

“Our goal is to discourage the development of complex miner strategies
and complex transaction sender strategies in general, including both
complex client-side calculations and economic modeling as well as
various forms of collusion; the latter especially is dangerous as it
creates an incentive for staking pools that can centrally manage the
process of extracting gains from collusion.”

The fact that there are no proofs regarding 1559’s behavior, and we can casually speculate new complex strategies that it makes possible, proves that it has not achieved its goal of simple safety, and the burden of proof that it is a good idea should rest on its advocates, not me for pointing out issues.

34

Hi all,

I think there are two types of congestion that needs to be considered for EIP-1559:

  • Non-urgent congestion. There is a small spike / temporary congestion of the network. e.g. there are 1000+ transactions in the pending pool, but this is due to a small spike in usage.
  • Urgent congestion. There is a significant spike / temporary congestion on the network. There are more urgent transactions in the pending pool (10,000+) than what the underling blockchain can process. e.g. a Black Thursday event with 200+ gwei fees.

The EIP has two mechanisms for dealing with congestion:

  • Self-inspect congestion. A consensus protocol can self-inspect blocks to detect congestion (e.g. more transactions are processed than average use).
  • Increasing burn rate. A mechanism to deterministically increase the fee base rate when the network is congested.

Note the EIP mentions the inefficiency of first-priced auctions, but I will argue that since “tip” can freely be set by the user, then EIP-1559 is still has a first-priced auction mechanism - it only becomes useful/apparent during urgent congestion.

So I think its worth evaluating how the two mechanisms impact each goal.

Non-urgent congestion & the mechanisms. I believe the EIP is focused solely on this case and its goal is to smooth out the gas price spikes if there is a slight spike in usage. Generally, it is assumed that most users place a bid at price X and they are happy to pay at most price Y. If the network becomes slightly congested, then the price moves from X -> Y. All transactions get confirmed in a timely manner since the network still has capacity to deal with the slight spike in congestion.

My gut tells me the EIP works ok for this case. Although, if there really is 6 million gas in extra capacity that is safe to use, then you might as well use it. There is no need for a gas-size war here or “nudging” behaviour. Just let people pay the price X instead of Y (i.e. KISS principle)

Urgent congestion & the mechanisms. As we have seen with Black Thursday (and several other congestion events), there are times of wide-spread urgency to use the blockchain. For example, users may want to save CDPs or deposit your coins into an exchange before the price crashes. During times of urgency, users participate in gas price auctions and front-run each other to get their transaction in first. The EIP facilitates this first-priced auction / front running with the “tip”.

From the miners perspective, they will always include transactions that pay them the most money. One simply strategy is for the miners to sort all pending transactions by the “tip” and process them one-by-one. Now the EIP has an in-built mechanism to gradually burn base fee until one of two things happen:

I suspect after the “super super super 1000 gwei transactions” are processed, we would see some convergence on users giving up (e.g. pending 200 gwei fees) and miners giving up. The network just ends up with empty blocks and most likely an ever-increasing pending pool. That doesn’t seem like a great outcome for either party.

Now there was one argument by @dankrad that is worth exploring around miner collusion and the urgent congestion scenario. One argument is that there is a tragedy of the commons. e.g. in the long term all miners want to collect most rewards, but in the short-term they want to maximise their profit. One long-term strategy for the miners to collude and only mine 10m gas blocks. The end-result is that it will maximise their profit as the transaction fees are not burnt and the pending pool continues to grow in size. Of course, in the short-term, the argument is that miners will just include transactions above the 10m gas limit, even if the tip is small, to maximise their reward. Assuming miners cannot coordinate, latter short-term case should happen.

There are two things to highlight for the collusion case:

  • Revert via soft-fork. If the miners collude, then reverting to the pre-EIP1559 mechanism is a soft-fork, especially since the “tip” is set by the user. There is no consensus rule to stop it and that is a problem for the EIP.
  • Miners do collude. If we look at 2015-2017 era of Bitcoin and the “blocksize/segwit wars”, there are countless examples of when it was industry + miners vs a fraction of the bitcoin community. In fact, at Scaling Bitcoin HK over 80% of the hashrate (~7 dudes) sat on a panel. As well, I think they went to the pub together. I’m not fully familiar with the Ethereum mining community, but I have no reason to believe it will be any different, especially as the mining industry becomes more competitive with tight-margin profit. At some point, we should expect them to collude and somehow defend against it.

My assessment above could be missing some fundamental assumption. But I feel it covers at least 90% of EIP-1559. My biggest fear and please take this with a pinch of salt, is that EIP-1559 might end up like GasToken or the Uncle Rewards issue. There may be some unintended consequence of changing the fee marketing that is for the worse, especially since it does not ultimately get rid of the first-priced auction mechanism (it only alleviates it in the non-urgent congestion case).

2 Likes
35

I thought I’d do some quick back-of-the-envelope math to see what the cost of this tx-withholding attack would be:

What would be the cost for an attack where miners deliberately submit under-half-full blocks, to force down the base_fee so that the tip parameter becomes the primary transaction-ordering mechanism?

The EIP suggests:

For most users post 1559 implementation the base fee will be estimated
by their wallet and a small gas premium- which acts as a ‘tip’ to
compensate miners (e.g. 0.5 gwei)

Current block reward is 2 ether.
Transactions per block range up to ~180, let’s say that was constant.

So if wallets submitted a tip similar to what the EIP suggests, wallets would only need to forego 0.0000045% of their income to soft-fork vote to eliminate the fee burn, and force users to pay more of their tx fees to miners.

End-users meanwhile have basically no real incentive to protect the fee burn: They are losing money either way, and generally just want their transaction included in a reasonable timeframe.

So, how high would wallet tips need to be for miners to prefer to keep transactions rather than prefer a single-price auction? Is that the kind of math we want wallets to have to do?

If we wanted it to be a substantial portion of the miner’s rational incentive, it would need to be a substantial portion of the transaction fee. And as we increase that ratio, we approach reverting to a first-price auction again.

36

Important questions are raised that I think would benefit from a bit more clarity on the user tip (really the “gas premium”) vs. actual miner revenue. The user specifies both a gas premium and a fee cap. The miner receives either the whole gas premium, or the fee cap minus the prevailing basefee, whichever is lower. Unless miners artificially depress the basefee to recreate a first-price auction, the basefee and the miner revenue are only interacting or in conflict when basefee + premium > fee cap for a tx.

In a tale of two users, say A’s tip is set to 2 Gwei and B’s to 1 Gwei. Take basefee = 5 Gwei. A sets the fee cap to 7 Gwei (they are not willing to pay more than the current basefee and their tip), while B sets the fee cap to 10. Suppose the network is congested and basefee jumps to 6.5. The miner including A’s tx would receive 0.5 Gwei (feecap 7 - basefee 6.5) while including B’s yields 1 Gwei (B’s premium), so B would have the advantage. I give another worked example here where a miner who knows they will mine the next two blocks can optimise their rewards by controlling the basefee.

In this sense, fee cap expresses some of the time preference that the escalator is able to more fully describe, in that higher fee cap => less chance of your transaction premium eaten away by the basefee => your transaction “drops out” later than others. I expect that the fee cap, by default, would be set at least to current basefee + gas premium (although there hasn’t been much discussion on how fee cap would be set, implicitly it seems people use the “fee cap = current basefee + gas premium + a small margin in case basefee goes up” heuristic, but to me this is underexplored atm), except in very high congestion cases (the super super 1000 Gwei txs) where a wallet could warn you that the current price levels are in the .01% top quantile historically. In any case the “tip” has more complicated dynamics than a once and for all user-set value.

  • If fee cap > current basefee + gas premium, miners do not get anything from lowering the basefee, as they still only get the full gas premium only.
  • If fee cap < current basefee + gas premium, as a user I am expressing that the current price level is too high, but I would be willing to get in later. Miners might still include my transaction if basefee < fee cap, though they may not reap the whole gas premium. That they might “game” the basefee to get the whole gas premium does not seem like it goes contrary to the mechanism’s intent in this case: if as a user I wanted to get in faster, I should have set a higher fee cap than I did.

In this light, let’s try to address the intuition that by keeping basefee arbitrarily low, miners can reproduce a first-price auction setting. In a non-congested setting, it doesn’t seem to me that miners can push users to a bidding war and from the point of view of gas premiums/fee caps, there is no reason why miners shouldn’t eat their whole cake either, whether they depress the basefee or not.

In a high congestion setting, miners can observe users’ willingness to pay by looking at the fee caps (or some lower bound of WTP at the very least, since it’s unlikely users would consistently set the fee cap above their WTP). With this observation, they can gauge “how much money is on the table”. Whether they can consistently depress the basefee is unclear, since as they do so, gas premiums would tend towards true WTP, in which case the “money on the table” keeps increasing. Does it reach a point where artificially not including these transactions becomes more unprofitable than being greedy and playing the short term strategy of simply maxing out your rewards? Likely it does, though this is something more thorough analysis could tell us.

Assuming for instance that all miners are colluding and have common beliefs about the WTP which they can all observe, as the premiums go up, it degenerates quickly to a game of Corvid as @danfinlay tweeted about :slight_smile: What if you knew and you knew everybody knew that premiums were at 80% of the WTP? Would you care to wait much longer? But if you knew that people wouldn’t wait much longer, wouldn’t you move a bit earlier? etc. etc. Unless people could durably censor your blocks (“tit-for-tat”) I think collusions are very unstable in this scenario.

2 Likes
37

Thanks as usual for some of the most thoughtful commentary in this discussion. I have a pretty stacked day lined up but will try to find time between things to read these.

1 Like
38

I think we should calm down this discussion a bit, as clearly some wild accusations are going around. But there are some points I need to correct because @danfinlay’s math is wrong:

I don’t suggest they leave “all the tips”, clearly they would get the tips for the transactions they are including. The point is that it is irrational behaviour not to include transactions that they would get a tip for.

The tip is per gas, not per transaction, right? This suggests your math is off by a factor of ca. 50,000 here. I get that they would get ca. 0.5% income at a tip of 1 GWei.

1 Like
39

Oh good, you’re right. So if we multiply by 50,000x, then the statement would update to (corrected instance of wallets to miners)

miners would only need to forego 0.225 % of their income to soft-fork vote to eliminate the fee burn, and force users to pay more of their tx fees to miners.

That still sounds pretty bad to me.

40

Miners have the ability to collude to push gas costs of users higher already; they could just start decreasing the gas limit to push fees up. Harms from this strategy are long-term, by which point those miners will be gone anyway (even without the PoS switch there’s hardware depreciation etc). So I think we should avoid assuming even the current system is especially robust. Hostile soft forks can do much worse (profitable) things than even that, eg. steal from fraud proof systems.

Meanwhile manipulation of transaction inclusion without outright soft forking is difficult because the worst you can do is extort people who really care about urgent inclusion; everyone else will just wait until a non-colluding miner includes the transaction in their block.

I suspect after the “super super super 1000 gwei transactions” are processed, we would see some convergence on users giving up (e.g. pending 200 gwei fees) and miners giving up. The network just ends up with empty blocks and most likely an ever-increasing pending pool. That doesn’t seem like a great outcome for either party.

The fee can decrease by a factor of 20 every 5 minutes ((1-1/8) ** (300 / 13) ~= 0.04589). On “Black Thursday” we saw txfees increase from ~10 gwei to ~200 gwei. So even after that kind of scenario if no one transacts it would only take about 5 minutes for fees to drop back to normal levels. Of course in reality it might take 10 minutes as there would still be some users willing to pay higher fees to send urgent transactions on the way down, but if that’s the case then the extra waiting by some users is balanced out by zero wait times for those users paying higher fees.

Another thing worth mentioning is that I think the narrative that “EIP 1559 is useful during non-urgent congestion but useless during urgent congestion” is wrong, because the two types of congestion are multiplicative. Even during the multi-hour-long 200-gwei spike, there was high local volatility in transaction fees, and high losses from users due to bad fee setting algos. If we had EIP 1559 during that spike, we would have seen an orderly fee market at the ~100-200 gwei level, and the extra losses from waiting and volatility on top of that (eg. users paying 400 gwei when they could have paid 100 gwei) could have been avoided.

BTW one possible modification to the proposal if we want to try to mitigate longer spikes as well is to modify the target so instead of being a constant (10 million), it’s a variable: target = 1000000 * log10(basefee), so higher basefees would automatically lead to temporary increases in capacity. The general EIP 1559 framework, by exposing an on-chain transaction fee level oracle that can only be manipulated at high cost (as opposed to reading gasprices on chain today, which could be manipulated by miners including dummy transactions), opens the door to these kinds of tricks down the line.