Mechanism Design for Blockchain Order Books Against Selfish Miners

Yunshu Liu, Lingjie Duan

TL;DR

This paper tackles the issue of "selfish miners" in blockchain-based order book systems, where miners prioritize high-fee transactions, leading to suboptimal matches and social welfare loss. The authors propose an "Adjustable Block Size" (ABS) mechanism that dynamically optimizes block size to balance transaction throughput and the incentive to ignore desirable matches, achieving near-social optimum and significantly outperforming existing benchmarks.

What Problem Does This Paper Address?

Blockchain-based order book (BBOB) systems, used in decentralized exchanges (DEXs) and for non-fungible tokens (NFTs), facilitate secure, decentralized transactions. In these systems, buyers and sellers set transaction fees to incentivize miners to include their transactions in blocks. However, a critical problem arises from "selfish miners" who myopically prioritize transactions with higher fees, even if these matches lead to lower overall social welfare. Existing BBOB mechanisms often overlook this miner incentive, resulting in inefficient trades and significant social welfare losses. This paper aims to quantify this loss and propose a practical mechanism to mitigate it.

Methods

The authors employ a game-theoretical approach to model the interactions between buyers, sellers, and miners as a two-stage game.

  • Stage I (Fee Setting): Buyers and sellers set transaction fees, anticipating miners' myopic behavior. This is modeled as a non-cooperative game, where pure strategy Nash equilibria (PSNE) may not always exist, necessitating the analysis of mixed strategy Nash equilibria (MSNE).
  • Stage II (Miner Transaction Selection): Miners, acting myopically, select transactions to maximize their immediate fee revenue, prioritizing those with the highest fees, subject to block size constraints.

The core of their proposed solution is an Adjustable Block Size (ABS) mechanism. The system designer dynamically sets the block size before buyers and sellers decide on fees. This allows for a trade-off between accommodating more transactions (higher throughput) and potentially ignoring more socially beneficial matches due to miner incentives. The mechanism is designed to be practical and compatible with existing blockchain protocols.

Datasets

  • NFT trading data: Used for homogeneous-quantity trading experiments.
  • Bitcoin trading dataset: Used for heterogeneous-quantity trading experiments, including bid/ask prices, quantities, and trading times.

Key Insights and Ideas

  • Infinite Price of Anarchy (PoA): The paper demonstrates that without intervention, selfish miners can lead to an arbitrarily large social welfare loss, meaning the system's performance can degrade to near zero. This is a significant finding highlighting the severity of the problem.
  • Block Size as a Lever: The core idea is that the block size is a crucial parameter that can be adjusted to influence miner behavior and improve social welfare. A block size that is too large encourages miners to ignore good matches, while a block size that is too small incurs significant delay costs.
  • Trade-off Between Throughput and Welfare: The ABS mechanism explicitly models and addresses the trade-off between block size (affecting throughput and delay) and the incentive for miners to prioritize high fees over social welfare.
  • Practicality is Key: The proposed ABS mechanism is designed to be easily implementable within existing blockchain frameworks (like Ethereum) without requiring fundamental protocol changes.

Key Results

  • Quantified Social Welfare Loss: The analysis shows that selfish miners can cause an infinite Price of Anarchy (PoA), indicating arbitrarily large social welfare losses.
  • ABS Mechanism Performance:
    • For homogeneous-quantity trading (like NFTs), the ABS mechanism achieves social optimum (PoA = 1).
  • For heterogeneous-quantity trading (like Bitcoin), the ABS mechanism enhances social welfare by up to 3.7 times compared to existing benchmarks and achieves at least 60% of the social optimum.
  • Robustness: The ABS mechanism demonstrates robustness to random variations in the number of buyers and sellers.
  • Implementation Validation: The ABS mechanism was successfully implemented on a local Ethereum testbed, validating its practical applicability.

Limitations and Future Work

  • Complete vs. Incomplete Information: The paper analyzes scenarios with both complete information (buyer/seller utilities and quantities are known) and incomplete information (parameters are drawn from random distributions). The latter is more realistic but analytically challenging.
  • Miner Rationality: The current model assumes miners are myopic. Future work could explore different miner incentive structures that adapt to varying levels of miner rationality.
  • Strategic Decisions on Bid/Ask Prices: The current model focuses on transaction fees. Future work could incorporate participants making strategic decisions on bid and ask prices.
  • Network Bandwidth Limits: While block size limits due to network bandwidth are acknowledged, their impact is explored but not fully integrated into the core mechanism design in all scenarios.

Summary updated

Abstract

In blockchain-based order book systems, buyers and sellers trade assets, while it is miners to match them and include their transactions in the blockchain. It is found that many miners behave selfishly and myopically, prioritizing transactions with high fees and ignoring many desirable matches that could enhance social welfare. Existing blockchain mechanisms fail to address this issue by overlooking miners' selfish behaviors. To our best knowledge, this work presents the first analytical study to quantify and understand buyer and seller transaction fee choices and selfish miners' transaction matching strategies, proving an infinitely large price of anarchy (PoA) for social welfare loss. To mitigate this, we propose an adjustable block size mechanism that is easy to implement without altering the existing decentralized protocols and still allows buyers and sellers to freely decide transaction fees and miners to selfishly match. The analysis is challenging, as pure strategy Nash equilibria do not always exist, requiring the analysis of many buyers' or sellers' interactive mixed-strategy distributions. Moreover, the system designer may even lack information about each buyer's or seller's bid/ask prices and trading quantities. Nevertheless, our mechanism achieves a well-bounded PoA, and under the homogeneous-quantity trading for non-fungible tokens (NFT), it attains a PoA of 1 with no social welfare loss. We implement our mechanism on a local instance of Ethereum to demonstrate the feasibility of our approach. Experiments based on the realistic dataset demonstrate that our mechanism achieves social optimum for homogeneous-quantity trading like NFT. It can enhance social welfare up to 3.7 times compared to the existing order book benchmarks for heterogeneous-quantity trading of Bitcoin tokens. It exhibits robustness against random variations in buyers and sellers.
BibTeX
@article{liu2025mechanism,
  author = {Yunshu Liu and Lingjie Duan},
  title = {{Mechanism Design for Blockchain Order Books Against Selfish Miners}},
  journal = {IEEE Trans. Network Science \& Engineering},
  year = {2025},
  doi = {10.1109/tnse.2025.3544686},
}
Figure