  Blockchain-based cryptocurrencies prioritize transactions based on their
fees, creating a unique kind of fee market. Empirically, this market has failed
to yield stable equilibria with predictable prices for desired levels of
service. We argue that this is due to the absence of a dominant strategy
equilibrium in the current fee mechanism. We propose an alternative fee setting
mechanism that is inspired by generalized second price auctions. The design of
such a mechanism is challenging because miners can use any criteria for
including transactions and can manipulate the results of the auction after
seeing the proposed fees. Nonetheless, we show that our proposed protocol is
free from manipulation as the number of users increases. We further show that,
for a large number of users and miners, the gain from manipulation is small for
all parties. This results in users proposing fees that represent their true
utility and lower variance of revenue for miners. Historical analysis shows
that Bitcoin users could have saved $272,528,000 USD in transaction fees while
miners could have reduced the variance of fee income by an average factor of
7.4 times.
