The Old Fee Market is Broken, Long Live the New Fee Market

Problem with the Current Fee Mechanism

Under the current fee paradigm, a user wishing to submit a transaction must figure out an appropriate fee. This turns out to be a very difficult task.

This seems straightforward, but there are problems.

Fees and Cognitive Load

The first problem is the cognitive load on the user: it is difficult to decide exactly how much to bid, whether to go over or under. Surely, if the value of the transaction to the user is X, then her bids will be capped at the utility of the transaction to that user (say, X mBTC). But between 0 and X, there are many options, and picking the right one depends on a lot of other factors. Exactly how important is this transaction to me right now? How full is the mempool? What are the competing bids? Given that there will be, in expectation, another 10 minutes of transactions streaming in to the miners before the next block is discovered, how low a fee can she get away with while still getting her transaction included in the blockchain? These are clearly difficult questions. Doing the right thing involves watching the chain closely and monitoring the transaction until it is included, an act that detracts from the hassle-free use of one's money. One may be tempted to just go through a middleman, such as an exchange, to handle it all, which creates centralization and simply recreates the current banking system except with unregulated exchanges as centralized custodians. This has, historically, led to a stream of exit scams and other SFYL-events [2].

Broken Attempts

But the real problem is much more fundamental, and it stems from the fact that the fee mechanism in Bitcoin and other currencies is implemented as a pay-what-you-bid, or multi-unit first-price, auction. This fee behavior will lead to "sticky" and unnecessarily high fees, followed by sudden fee collapses, just as we have seen over the course of the last few years.

To see why, imagine a universe where everyone is using a simple historical fee estimator. Specifically, imagine a fee estimator that looks back on historical transactions and suggests a fee based on what happened on average in the past. If transactions were paying an average of 100 satoshis per byte in the recent past, then a user will simply attach a fee of 100 or more satoshis per byte.

This approach is completely broken. During times of congestion, the fees to get included will naturally go up, as they should. If the transactions momentarily arrive faster than blocks are found, the fees attached will go up. But they will remain high even after the congestion has ended. If, for instance, the rate of arrival for transactions is exactly equal to the rate at which blocks clear them, the system should be able to support 0-fees. And yet this approach will force the users to pay fees as if they were operating at the height of congestion. The fee structure that arises during congestion is ensconced in the system even though the conditions have changed, an artifact of bad mechanism design.

One can imagine other fee estimation heuristics, such as underbidding on purpose to explore if one can get away with paying less, that would yield better results. But it all is up to the vagaries of other people's choices of fee estimators that would determine the prices. A smart user who notices that the fee estimators are broken would have little recourse except to pay the prevailing fees. The system would provide no mechanism by which optimal choices are made. And of course, the mavericks who do try to explore paying lower fees, just to see if the entire ensemble of users could move to a lower price point, will have to deal with stuck transactions and transaction delays.

Blockchains are not the only place where similar auction mechanisms have led to poor user experiences. When ad placement in search engines was based on first price auctions, researchers observed similar patterns. Advertisers would compete with each other in order to get a better placement, driving the fees sky high. This would be followed by many participants quitting the game, which would cause a precipitous drop, only to restart the unstable cycle all over again.

A Better Fee Market

In a new paper, we propose a new mechanism to charge for transactions. This mechanism is only a slight code change away from the old mechanism, but it has the potential to yield a much more stable fee market, a much better user experience as well as a big savings in fees, and a more predictable revenue stream for miners.

Our proposed mechanism is fairly simple: transactions specify a fee, just like before, and miners place transactions in a block, just like before. Except, instead of charging each transaction the fee it bid, we charge each transaction the lowest fee charged to any transaction in that block. Any surplus fees a transaction offered are returned to that user, to a designated address they specify. Hence, a transaction in effect says "I am willing to pay up to $30 for this transaction," but is charged only $5 if the lowest fee transaction in that block paid $5. The remaining $25 are returned to the user.

Our proposed mechanism brings insights from multi-unit second price auctions to the world of cryptocurrenices where currently multi-unit first price auctions are the norm. Whereas before, fee selection was a stressful and difficult task, with our mechanism, users can simply attach to their transaction the true maximum value they would be happy to pay. This is because they are not going to be charged that value: instead, they are charged whatever the minimum was to get into that block. In essence, the lowest paying transaction establishes just how little it took to get into that block, and everyone within that block is charged the same amount per byte. This is not only equitable and fair, but it takes away pressure to play games with fee selection. As an additional bonus, the benefit from playing such games decreases as the blockchain gets more popular, further disincentivizing strategic fee selection. Note also that it picks the highest-paying transactions, just like first-price auctions, though it charges them strictly less than what they would be willing to bear.

Our proposal couples this idea with three other mechanisms to provide a comprehensive solution that prevents malicious behavior by miners. First, if a miner fails to fill a block, they cannot charge any fees. So a miner cannot take a high-paying transaction, ignore the rest of the mempool, and collect the entirety of the fee paid by that transaction while refusing to fill a block. They are, of course, free to fill the rest of the block with their own synthetic transactions, but they will have to pay out of their own pockets for those (and the next point addresses why the miner cannot just pay those additional fees directly to himself). Second, a miner is rewarded the average fee collected from the last B blocks, not just the fees from block they themselves mined. This ensures that miners also have little incentive to act strategically. Instead their best interests are aligned with maximizing the number of high-value transactions cleared per second. Finally, we propose that every block reserves some space, around 20%, which are exempt from this mechanism. This enables a miner to include transactions of high importance to themselves, such as those used for pool rewards, without affecting the fee mechanism and without being penalized. This addresses the miners' needs and provides a simple migration path from the current state of affairs.

Our mechanism brings order to the chaotic fee market of today. During the dramatic Bitcoin price increase in December 2017, we estimate that users would have saved over $272 million in transaction fees and miners would have a much more predictable fee revenue, reducing their daily fee variance an average of 7.4 times. These gains are not surprising -- our mechanism enables transaction fees to correspond to the true demand that users have for block space. This will make the fee markets more predictable. As a result, users can just bid their true value and know that they are not going to be overpaying for block space. Thus, this removes a painful strategic element to simply using cryptocurrencies today.

If you are designing new cryptocurrencies or are an active user of existing currencies, we highly encourage you to push for this fee mechanism instead of unstable first-price auctions.

Footnotes

Related

Ron Lavi, Or Sattath, and Aviv Zohar have proposed a similar protocol to ours, however they differ in a few fundamental ways. Similar to our proposal, they propose a protocol in which the winning miner places transactions into a block and charges all transactions the lowest fee proposed by any transaction placed in that block. Lavi, Sattah and Zohar assume a single monopolistic miner, and strive to maximize revenue from fees at a cost of lower social welfare. In contrast, our work explicitly targets maximizing social welfare, and operates under a model with many miners. In their system, the monopolistic miner is incentivized to leave transactions offering positive fees out of the block even if there is space in the block as including them reduces the uniform price he can charge. This, of course, maximizes miner revenue, but we believe that the first criterion for a viable protocol must be to use the blockchain efficiently, as otherwise users are discouraged from participation. Their non-manipulation result is stronger than the one we obtain from our mechanism since we only obtain declining gain from manipulation as the system grows, but it comes at a cost of lower social welfare and desirable metrics such as transaction throughput and latency. Finally, in both our protocol and the protocol proposed by Lavi, Sattah and Zohar, users’ incentive to behave strategically vanishes as the number of users grows.

Vitalik Buterin has proposed an alternative approach based on miners estimating, and dynamically adjusting, a single fee that is charged uniformly to all transactions within a block, coupled with dynamically varying the block size to accommodate demand. This approach differs from ours in a few key ways. First, it does not aim to maximize social welfare, and instead adopts heuristics to modify two independent variables, fees and block size. The former goal, adopted by our work, will maximize transactions cleared subject to any desired block size constraint, determined by any desirable mechanism. Since block size is a primary determinant of security and centralization, we believe it is prudent to decouple its management from the fee mechanism. Second, it assumes that the demand curve is known to the protocol, though it makes no assumptions about its behavior. If the demand curve could be inferred accurately such that all transactions whose utility exceeds the block fee can always be accommodated, then Buterin's proposal would have no incentive issues. However, inferring demand curves is difficult in adversarial, Byzantine environments, which is why auction mechanisms are used. Finally, this approach has not been proven to be resistant to manipulation by users and miners. If it is not resistant to manipulation, then this mechanism will suffer from the same problem as the current first price mechanism, where users have to solve the fee selection problem all over again.