An Improved Algorithm to Identify More Arbitrage Opportunities on Decentralized Exchanges

Paper: arXiv 2406.16573

Abstract

In decentralized exchanges (DEXs), the arbitrage paths exist abundantly in the form of both arbitrage loops (e.g. the arbitrage path starts from token A and back to token A again in the end, A, B,…, A) and non-loops (e.g. the arbitrage path starts from token A and stops at a different token N, A, B,…, N). The Moore-Bellman-Ford algorithm, often coupled with the ``walk to the root" technique, is commonly employed for detecting arbitrage loops in the token graph of decentralized exchanges (DEXs) such as Uniswap. However, a limitation of this algorithm is its ability to recognize only a limited number of arbitrage loops in each run. Additionally, it cannot specify the starting token of the detected arbitrage loops, further constraining its effectiveness in certain scenarios. Another limitation of this algorithm is its incapacity to detect non-loop arbitrage paths between any specified pairs of tokens. In this paper, we develop a new method to solve these problems by combining the line graph and a modified Moore-Bellman-Ford algorithm (MMBF). This method can help to find more arbitrage loops by detecting at least one arbitrage loop starting from any specified tokens in the DEXs and can detect the non-loop arbitrage paths between any pair of tokens. Then, we applied our algorithm to Uniswap V2 and found more arbitrage loops and non-loops indeed compared with applying the Moore-Bellman-Ford (MBF) combined algorithm. The found arbitrage profit by our method in some arbitrage paths can be even as high as one million dollars, far larger than that found by the MBF combined algorithm. Finally, we statistically compare the distribution of arbitrage path lengths and the arbitrage profit detected by both our method and the MBF combined algorithm, and depict how potential arbitrage opportunities change with time by our method.

Complexity vs Empirical Score

• Math Complexity: 7.5/10
• Empirical Rigor: 6.0/10 (capped from 7.0: no out-of-sample test; see penalty flags)
• Quadrant: Holy Grail — high math complexity, high empirical rigor

Why this score: The paper introduces a modified Moore-Bellman-Ford algorithm and line graph concepts, requiring advanced graph theory and discrete mathematics. It is heavily data-driven, using real historical Uniswap V2 data over three years, performing statistical comparisons, and presenting empirical results on arbitrage profits.

Research Flowchart

  flowchart TD
  A["Research Goal<br>Overcome MBF Limitations<br>Find More Arbitrage Loops & Paths"] --> B["Methodology<br>Line Graph + Modified MBF MMBF"]
  B --> C["Data & Inputs<br>Uniswap V2 DEX Token Graph"]
  C --> D["Computational Process<br>MMBF Detects Loops & Non-Loops<br>Specifying Start/End Tokens"]
  D --> E{"Key Outcomes"}
  E --> F["More Arbitrage Opportunities<br>Found vs. MBF"]
  E --> G["High-Value Profits<br>Up to $1M Detected"]
  E --> H["Statistical Analysis<br>Path Length & Profit Distribution"]

Cited References (19)

1. Decentralized Finance: Regulating Cryptocurrency Exchanges (2021)
2. An Empirical Study of Market Inefficiencies in Uniswap and SushiSwap (2022) — link
3. Trade or Trick?: Detecting and Characterizing Scam Tokens on Uniswap Decentralized Exchange (2022) — link
4. SoK: Decentralized Finance (DeFi) Attacks (2023) — link
5. Cyclic Arbitrage in Decentralized Exchanges (2023) — link
6. SoK: Decentralized Exchanges (DEX) with Automated Market Maker (AMM) Protocols (2023) — link
7. Detecting and identifying arbitrage in the spot foreign exchange market (2020)
8. On the just-in-time discovery of profit-generating transactions in defi protocols (2021)

0 of 19 cited works are in the corpus; resolved via arXiv source bundles, Semantic Scholar and OpenAlex. Corpus-wide: 2518 linked papers.