REDESIGNING BITCOIN’SFEE MARKET
arXiv:1709.08881
Ron Lavi - Technion

Aviv Zohar - Hebrew U.

Or Sattath Ben-Gurion U.
Scaling Bitcoin 2017

CURRENT FEE MECHANISM IN BITCOIN• Miners can only include txs that fit in at most 1MB.
• Pay what you bid: users specify the fees, and they pay it only if they areincluded in a block.
• Miner’s inclusion strategy: include the highest transactions by theirfee/byte that fit into 1MB.
• From now on we assume all txs are of the same size in bytes.

WHAT IF HARDWARE PARAMETERS WEREN’T ANISSUE?
• Suppose there are negligible block rewards, and the bandwidth, CPUand disk-space get a x100 boost. How should Bitcoin be changed?
• First guess: increase the block-size by a factor of 100.
• Economically risky – tragedy of the commons / race to the bottom:• Blocks are not full
• Miners do not have incentives not to take ~0 fees.
• Users decrease fees to ~0• Revenue for the miners diminishes• Double spending becomes very cheap

DESIGN GOALS• Increasing the block-size can decrease the miners’ revenue• In the long run, fees are the main income for the miners.
• Design goal: maximize the revenue for the miners. In particular,increasing the bandwidth etc. should increase the miner’s revenue.
• The block size affects the security (orphaning rate, decentralization,etc.) and economic aspects (revenue for the miners).
• Design goal: decouple economic and security concerns.
• Design goal: a simple way for the user to decide on her fee.

BITCOIN MINING AS AN AUCTION• Bitcoin users willing to pay tx fees = Buyers• Miner = Auctioneer (+seller)• Auction theory standard assumptions: buyers do not collude & havestrong identities, auctioneer is trusted (but not the seller), and theauction is conducted once.

RESULTS: TWO BITCOIN FEE MECHANISMSRSOP MECHANISMMONOPOLISTIC PRICE MECHANISM• Beautiful but not very useful• Not so beautiful, but moreuseful• Sensitive to miners’
manipulation

MONOPOLISTIC REVENUE & PRICE•MONOPOLISTIC REVENUE & PRICE: EXAMPLE•CHALLENGE: MANIPULATIONS•RSOP AUCTION (Random Sampling Optimal Price)
Goldberg et al. 2006

A54321BRSOP AUCTION (Random Sampling Optimal Price)
Goldberg et al. 2006
•RSOP MECHANISM - BITCOIN• Users specify a maximal fee (they may pay less).
• Miner include all mempool tx in their block.
• Block hash used to randomly partition the bids [Bonneau-Clark-Goldfeder’15].
• Only txs that “win” according to the RSOP auction are considered valid.
• 2 problems:• Blocks are huge: including all the transactions is unrealistic• Prone to miners’ manipulation: Miners gain by including fake transactions /not including valid ones.

MONOPOLISTIC PRICE MECHANISM•MANIPULATING THE MONOPOLISTIC PRICE MECHANISM•MONOPOLISTIC PRICE MECHANISM MANIPULATIONS• Theorem (informal): For any finite support users’ valuation distribution, theworst discount ratio from a manipulation of a single player (assuming allothers are honest), goes to 0 as the number of users grow.
• Concerns we evaluated empirically:• How fast does the manipulation ratio decreases?
• What if the valuation distribution does not have finite support size?

MONOPOLISTIC PRICE MECHANISM:EMPIRICAL RESULTS• Theorem (informal): For any finite support users’ valuation distribution, themax. discount ration from a manipulation (assuming all others are honest),
goes to 0 as the number of bidders grow.
• Concerns we evaluated:• How fast does the manipulation ratio decreases?
• What if the valuation distribution does not have finite support size?

DISCUSSION & OPEN PROBLEMS• How much security should the Bitcoin network “buy”? Are we buying too
much / too little security in terms of hash-power?
• The current fee mechanism is not the most “natural” one• How can we get real data on the “willingness to pay” for the fees? Importantto understand how well this proposal would preform.
• An applicable RSOP mechanism?
• Bitcoin Dev. mailing list has an interesting discussion, also aboutimplementation.

THANK YOU!

MULTI-BID STRATEGY• Values: 5, 2, 1, 1.
• Everyone honest – first player wins, pays 5.
• If player two submits two bids with a value of 1, she gets in, everyone win
and she pays two.
• Non-trivial: we show an efficient O(n) algorithm to find the optimal multi-bidstrategy.
• In practice, barely happens: never happened during our simulations when
number of users ≥ ~10.