Motivation

Whenever you send cryptocurrencies to someone else, you need to pay a fee in order to prevent spam in permissionless blockchains. The higher the fee, the more likely your transaction is to get into an earlier block; the lower the fee, the less likely your transaction will be included in an earlier block (with fees low enough, or no fees, your transaction may never get included). This makes for terrible UX in that users can easily overpay to get their transactions included in a block and miners get unstable revenue from fees. In general, you can view this market as a first price auction for transaction space in a block. Miners auction off space in their block to users who want their transactions included.

Background

Before diving into the specific proposal, first we will go over first and second price auctions upon which the paper’s proposal modifies for a cryptocurrency context.

First Price Auctions

Generalized First Price auctions (GFPs) are what people generally think of when they hear the word “auction.” GFPs are auctions in which positions are sold to the highest bidder according to how “high” that position is. Each bidder pays in accordance to their bid. For example, in sponsored search, the highest bidder gets the highest slot on the webpage and pays their bidding price, the second highest bidder gets the second highest slot on the webpage and pays their bidding price, etc.

 

The main problem with GFPs is that they allow for strategic behavior and as such, don’t possess a pure Nash equilibrium. This is especially problematic in a blockchain context as all miners are pseudonymous and these miners operate under adversarial conditions. This results in a saw-tooth-like pattern for transaction fees.

Second Price Auctions

Generalized Second Price auctions (GSPs) are slightly different than GFPs. Just as in GFPs, the highest bidder gets the highest slot, the second highest bidder gets the second highest slot, etc. The main difference here is that the bidders don’t pay their original bidding price. They instead pay the price of the bidder below them. In other words, the highest bidder doesn’t pay the highest bid price that they bid but instead the second bidder’s price and so on for each subsequent bidder. Even though GSPs don’t have an equilibrium, in practice, they have produced more predictable and stable prices for bidders. Search engines such as Google use a modified GSP for selling ad slots for their webpages.

Model

In the model used to present the new fee market, each block has K slots, which represent transactions, N users where we assume that N > K and that the probability that a user has their transaction in the mempool is d. Each user is an identically and independently distributed random variable. Each user has a non-zero real-valued bid for their transaction, that is also non-zero and real-valued, to get included in a block.

 

A miner looking to make a profit will select the K highest bids or all available bids if there are less than K bids available. A miner only makes a profit if the block they mined actually gets included into the blockchain as per the usual blockchain protocol.

Alternative Fee Mechanism Proposal

The fee mechanism is actually quite simple, and can be broken down into a few steps:

1. Users attach a fee to their transaction (as they do now). Note that this fee is the maximum fee the user is willing to pay to have their transaction included.
2. All transactions in a block pay the minimum fee paid for any transaction in that block. This step is the one that bears similarities to a GSP.

The model used assumes that each transaction is equally-sized, with K total transactions per blocks. The above steps can be trivially modified to use something like “fee rate per byte” rather than “fee,” to account for differently-sized transactions.

The two steps above are potentially gameable by miners (or more generally block producers), as they can include transactions to themselves and ignore other transactions with lower fees to potentially raise the total fees collected per transactions (by raising the minimum fee in a block). In practice this isn’t actually an issue, as a miner that includes such a transaction is leaving actual fee-paying transactions on the table.

From a theoretical perspective, however, this issue needs to be remedied:

1. Miners of a block are paid the average fees of the last B blocks. This has the effect of smoothing out how fees are distributed to miners.
2. Miners always need to fill blocks.
3. A block is full if it has K transactions or it has fewer than K transactions and pays a fill penalty, which is (K – # of tx in block) * fee paid by each tx in block. Alternatively, the miner can declare that there are insufficient transactions to fill the block in the mempool, at which point all transactions in the block pay the minimum fee.
4. The minimum fee is set at the protocol level. It can be implemented as the minimum fee required for mempool inclusion and propagation.

The incentive for the fill penalty is that larger blocks are more likely to be orphaned by other miners (as they take longer to validate). Unfortunately, a metric for this negative incentive is not presented, so it’s unclear where exactly the balance lies. In addition, this negative incentive only exists for PoW cryptocurrencies. Most PoS-based consensus protocols do not have a race to broadcast blocks lest they be orphaned, so it’s unclear how this fee mechanism proposal can be extended for PoS.

Conclusion

In this edition, we presented an alternative proposal to improve fee markets for users and miners in cryptocurrencies. You can read the original paper here. While possibly not perfect, it does surely offer a vast improvement over the current fee mechanism used for most cryptocurrencies today.

If you liked what you read, you can subscribe to the Blockchain Research Newsletter to get these straight to your mailbox.