Rethinking Bitcoin’s Fee Market

How Auction Theory and Algorithmic Game Theory Can Improve Bitcoin’s Transaction Fee Mechanism

In a new paper (pdf) that we (Ron Lavi, Or Sattath, and Aviv Zohar) just published online, we apply techniques from the field of Algorithmic Game Theory to Bitcoin’s fee market. Our goal is to improve several key aspects of the market:

1. Simplify fee determination for users.
2. Improve (or at least maintain) the revenue miners collect from fees, which in turn attracts more mining and thus improves security.
3. Separate the issue of block size from the mechanism that determines fees as much as possible (in this way, the block size can be set simply to satisfy other security requirements such as relatively low block propagation time without worrying so much about the effect on fees).

There are plenty of other properties you might want from a fee mechanism (we outline more in the paper). Another important requirement is to be resilient to various manipulations by miners and users (such as adding additional transactions in which the miner sends money to himself).

As Bitcoin’s block reward decreases (halving approximately every four years), transaction fees start to matter more. We hope that they will eventually suffice to attract enough mining to have a high level of security in the system.

Bitcoin’s current mechanism is a pay-your-bid auction in which transactions simply include take-it-or-leave-it offers to miners for a given fee. We propose two alternative mechanisms in the paper. The primary one is The monopolistic price mechanism (The second one is based on the beautiful RSOP auction due to Goldberg et al., but unfortunately is more prone to manipulation, and a bit harder to implement in practice).

Disclaimer: The mechanisms that we propose are naturally still largely untested, and much closer scrutiny by the community is needed. We hope that our work will lead to more interest in the design of the fee market. Perhaps it will inspire even better alternatives.

Now, before we go on to describe the mechanism, let’s first discuss why we feel some modification is needed.

What’s wrong with Bitcoin’s current pay-your-bid mechanism?

First, we should start by saying that a lot about the pay-your-bid mechanism is just right. It’s a simple mechanism, that is easy to implement, and generally sets incentives for miners to include higher paying transactions first.

It does however have two main faults:

1. The fees that users set depend on other unconfirmed transactions.
   To save money, users do not typically set the maximal fee they are willing to pay. Instead, they engage in so-called bid shading, paying just enough to get into one of the next blocks. In practice, this means that wallet software tries to estimate the right fee to pay. Fee estimation is hard, and the status of the mempool can change, especially if the next block is delayed (after all, block creation is somewhat random). Users suffer in several ways:
   - Transactions that set a high fee end up over-paying (sometimes by a lot).
   - Transactions that set a low fee by mistake get delayed and may need to be adjusted (via replace-by-fee mechanisms for example), which also requires you to stay online to monitor your transactions.
2. The revenue for miners is far from optimal.
   If blocks are for some reason not full, then users can get away with setting extremely low fees. These provide very low revenue to the miners.

To emphasize the absurdity of this situation, imagine for example, an airline that suddenly found a way to make a bigger better airplane that carries more passengers. Selling all seats on the plane would necessitate a drop in the price of each seat which may lead to less revenue for the airline, e.g., if the price drops by half, but the number of passengers grew by less than a factor of two. (In reality, airlines may choose not to sell all seats on the plane, and in fact select prices differently).

Twitter is filled with evidence of this

And fee estimation is notoriously hard to get right

Auction Theory and Algorithmic Game Theory to the rescue!

The mechanism that we propose in the paper is called “The Monopolistic Price Mechanism”. Its rules are as follows:

1. Users specify in the transaction the maximal amount of fees that they are willing to pay.
2. Miners choose which transactions to include in the block (up to the block size limit). They do not have to fill up the entire block.
3. All transactions in the block pay the same amount: the lowest fee that was specified by any of them.

Notice that with this mechanism as well, miners have an incentive to include higher-paying transactions first. If transactions are sorted from highest fee to lowest, every additional transaction that the miner adds pays, but also decreases the price for others. Miners find the sweet-spot which sets the best price and overall revenue (which is known as the monopolist’s price) and maximize their revenue according to the rule above.

So, What’s so Appealing About this Mechanism?

• Users pay the marginal cost of entering a block.
• No need to readjust your transaction if the mempool is congested (if you agreed to pay enough, you will be charged the marginal price, if not, you never really wanted to transact with such high fees anyway).
• Miners have an incentive to follow the mechanism (it is set to maximize their reward, at least in the short term).
• If the block size is increased miners can still include the same set of transactions as before and collect the same revenue. We actually show that this mechanism collects more revenue for miners than pay-your-bid would.

Caveats, Limitations, and Some of the Fine Print

There are some situations where users can gain from lowering their bids. We show in the paper that they gain very little from such “sniping” (especially when the number of users grows).

Our analysis only considers impatient users — we did not account for users that want to get in, say, sometime in the next day or so.

Lots of further analysis is needed, especially when considering how persisting lower fee transactions affect the distribution of fees and the mechanism.

In general, we’d appreciate feedback, comments, and suggestions for further improvements. To reach out to us or to see what else we’re up to, visit our websites: Ron, Or, and Aviv.