Creating Automated Profitable DeFi Trades with Weighted Graph Algos

14 min readAug 3, 2022

In this article, I explore methods that allows me to create automated profitable DeFi trades. Suppose you are a newbie in the world of DeFi, realistically, the chances for you to actually gain profits when trading is rare. But, it’s not impossible if you have the right set of tools and knowledge.

DeFi simply stands for Decentralized Finance which refers to financial systems that are not centralized. It is a blockchain-based system of finance management. It allows conducting financial operations such as payments, lending, borrowing, saving, margin trading, yield aggregation, and currency trading fast and securely on a P2P (peer to peer) model, thus excluding any third parties (e.g. banks or other financial institutions). The total value locked in DeFi has increased from $601 million at the start of 2020 to $239 billion so far in 2022, a nearly 40,000% rise, according to new research by Amberdata.

Currently, the most popular DeFi platforms are based on the Ethereum blockchain and its system of smart contracts, which gives rise to new applications that are mirrored and inspired by the traditional centralized finance system. Unlike traditional finance systems, DeFi platforms give one the ability to interoperate; e.g., one may borrow a cryptocurrency asset on one platform, exchange the asset on another, and for instance, lend the resulting asset on a third system. Since DeFi heavily relies on coded architecture, it also opened up opportunities for DeFi arbitrage. For example, if platform X offers 10% yields from a stablecoin but platform Y offers 12% yields, a trader can shift his funds from A to B to earn 2% higher yields.

In any other cases, a trader could also choose to deploy another strategy to spatial arbitrage across different decentralized exchanges. A trader would trade the digital asset across the DEXs to profit from the discrepancy. This has led to the emergence of chained trading and arbitrage opportunities.

From research, I found out there are two methods of detecting profitable opportunities in DeFi. They are;

Bellman Ford Algorithm: This is an algorithm that computes the shortest paths from a single source vertex to all of the other vertices in a directed graph. This can be used to find the quickest/shortest path, allowing us to find circular arbitrage trade. It can be applied easily to a graph of markets on a blockchain or exchange. Also, used for negative cycle detection and it’s been proven to work well in multiple markets & assets, as it is used in traditional finance as well.
Theorem Solver (SMT): Satisfiability modulo theories (SMT) is the decision problem of determining whether a mathematical formula is satisfiable. SMT solvers, therefore, are tools that aim to solve the SMT problem for a practical subset of inputs. As you can imagine, this is more complicated and requires that it is encoded in the DeFi model. It’s used for making more complex trades than arbitrages, applying heuristics for path pruning. But once a path is found, it can be very rewarding. It was used to perform the famous bzx attack on bsc.

In cross-DEX arbitrage, traders will typically continuously scan decentralized exchanges' order books to execute a series of trades sequentially between different trading venues with the goal to end up with more money than they started with. Below is an example of a triangular arbitrage trade between two decentralized exchanges, and the pairs DAI/MKR, MKR/WETH, and WETH/DAI which leads to a 1.6% profit.

Fig 1: Analysis for: 0xa595a252a5324d520d17de440e71ba23c622dbdaf8a5f6a3d88c866b0fbdf88c

The example above highlights the need for automated tools that can help traders maximize profit. These tools have to be designed to run in real-time: at every block, they can find (and execute) a new profit-generating transaction. Ethereum has an average block time of 13.5 seconds and from experience, the state of the blockchain and DeFi platforms may change at each block, so it is important to operate in real-time, otherwise the found trading opportunities might be outdated. I also see this kind of trade arbitrage as a zero-sum game, i.e. there is a finite amount of arbitrage opportunities per time and a lot of arbs are competing to find and execute them early(I might be wrong tho).

The main risks for a trader using these arbs that I consider within this mode are price volatility risks and blockchain transaction fees also known as Gas fees. While the forces that influence price volatility are beyond your control, the gas fees are, because to simply put it the more computational steps your transaction has, the more gas you will pay to execute it.

MODELING THE ARB

To create a system that automatically finds & makes profitable trades, one will need two models; a trader model, and a state transition model for interaction between DeFi platforms and a thorough understanding of the DeFi system. The entire system should consist of the DeFi market states, as well as the cryptocurrency asset balances of the trader. The transition model represents DeFi actions performed by the trader model on the respective DeFi platforms.

Background

Crypto assets: Assets are the medium of exchange within DeFi platforms (i.e., markets), such as exchanges, lending, and borrowing platforms. Each DeFi platform offers a set of actions, which can be triggered by a transaction. Actions take an asset as input and yield, or another asset as output. Multiple actions can be encapsulated in one transaction and executed atomically in sequence. A path is a sequence of actions across DeFi platforms. A strategy or transaction is a path with parameters for each action (such as coin amounts, etc.). Check. Fig 1 for an example.
Decentralized exchanges (DEX) are a type of cryptocurrency exchange that allows peer-to-peer cryptocurrency exchanges to take place securely online, without needing an intermediary.
DEX aggregators source liquidity from different DEXs and thus offer users better token swap rates than any single DEX.
Liquidity pool is a collection of funds locked in a smart contract to provide liquidity for DEXes. The advantage of a liquidity pool is that it doesn’t require matching orders between buyers and sellers but instead leverages a pre-funded liquidity pool with low slippage.
An Orderbook consists of a collection of bid-and-ask orders. Orders are matched and executed only when a bid and ask price are the same.
An Automated Market Maker (AMM) uses a liquidity pool instead of an orderbook and relies on mathematical formulas to price assets. The assets can be automatically swapped against the pool’s latest price, making it more efficient than traditional orderbooks.
Wrapped ETH (WETH) is the ERC20 tradable version of Ethereum. WETH is easier to trade within smart contracts than ETH is. Users can also revoke access to their WETH after sending it to an exchange, which is not possible with ETH.
Price slippage refers to the difference between the expected price of a trade and the price at which the trade is executed. It usually happens when the market is highly volatile within a short period of time or when the current trade volume exceeds the existing bid/ask spread.
Flash Loan is a type of uncollateralized loan that is only valid within a single transaction. It can be implemented through a smart contract. The transaction will be reverted if the execution result is not as expected.

Trader Model

A computationally bounded model that is capable of executing transactions across a set of DeFi platforms. As a trader, you’re capable of reading blockchain contents but you’re not expected to observe unconfirmed blockchain transactions on the network layer. The model is capable of placing a transaction ahead of other DeFi transactions within a future blockchain block. Practically, this requires you to pay a higher transaction fee, as most miners appear to order transactions based on gas price.

Based on Negative-cycle detection algorithms by Boris V. Cherkassky & Andrew V. Goldberg, it’s been proposed that negative-cycle detection algorithms such as the Bellman-Ford-Moore algorithm can be used to find arbitrage opportunities. In these algorithms, the exchange markets are modeled as a directed weighted graph. Every negative cycle in the graph then corresponds to an arbitrage opportunity. These algorithms combine the shortest path algorithm with a cycle detection strategy.

Cherkassky et al. studied various combinations of shortest path algorithms (Bellman-Ford-Moore, Goldfarb-Hao- Kai, Goldberg-Radzik, etc.) and cycle detection strategies (Walk to the root, Admissible graph search, Subtree traversal, etc.) and compared their relative performances. A natural question is whether these cycle detection algorithms can be directly applied to find profitable transactions in DeFi.

Model Strategy: The objective is to maximize the base cryptocurrency asset. An arbitrage cycle, however, may not consist of the base asset. Therefore, one has to convert the arbitrage revenue to the base cryptocurrency asset by the end of the execution. More concretely, we find all ‘connecting’ markets that support the conversion between one of the arbitrage assets and the base cryptocurrency asset. We perform the conversion using the ‘connecting’ markets with the best price.

In bid-ask markets, the price does not change if the trade volume is within the bid/ask size. DeFi AMM exchanges, however, follow a dynamic price based on the trade volume. Intuitively, the bigger the transaction size, the worse the trading price becomes. Hence, the algorithm needs to consider dynamic price changes and update the graph after every action. On a high level, a Bellman-Ford-Moore inspired algorithm repeatedly performs the following steps:

Define a graph: The first step is to define a graph representing the different DEXs, crypto assets, and prices. Each node in the graph represents a DEX, and the edges represent the prices between the markets.
Assign weights to the edges: The weight of each edge represents the price between two DEXs. In the case of arbitrage opportunities, the weight represents the profit that can be made by buying and selling the same asset in two different DEXs.
Run the Bellman-Ford algorithm: The Bellman-Ford algorithm is used to find the shortest path between two markets. In the context of arbitrage opportunities, the shortest path between two markets represents the most profitable sequence of trades that can be made.
Check for negative cycles: If a negative cycle is found during the Bellman-Ford algorithm, it indicates an arbitrage opportunity. A negative cycle is a cycle of edges that have a total weight that is less than zero, meaning that a trader can make a profit by following that cycle.
Execute the trades: Once an arbitrage opportunity is identified, the trader can execute the trades and profit from the price discrepancy between the two DEXs.

Here’s an example of a graph that represents different decentralized exchanges, cryptocurrencies, and prices, where each node represents a DEX and the edges represent the prices between two DEXs:

markdown 

   Uniswap   |    Sushiswap   |     Balancer
---------------------------------------------------
Uniswap   |      -       |   1.02/1.00   |    1.03/1.00
Sushiswap |  0.98/1.02   |      -       |    1.01/0.99
Balancer  |  0.97/1.03   |  0.99/1.01   |       -

In this example, I have three DEXs: Uniswap, Sushiswap, and Balancer. I have also included three cryptocurrencies: A, B, and C.

The graph is represented using an adjacency matrix, where each row and column represents a DEX, and the values represent the weight of the edges between them. For example, the weight of the edge between Uniswap and Sushiswap is 1.02/1.00, which means that the price of the cryptocurrency on Sushiswap is 1.02 times the price of the cryptocurrency on Uniswap.

This graph can be used to identify arbitrage opportunities and other trading strategies. For example, if the price of cryptocurrency A is 1 on Uniswap and 0.98 on Sushiswap, a trader could buy cryptocurrency A on Sushiswap and sell it on Uniswap for a profit. By analyzing the weights of the edges in the graph, traders can identify the most profitable sequence of trades to make.

Automating the process of identifying arbitrage opportunities onchain then involves writing a program that can interact with the blockchain network and the smart contracts of the decentralized exchanges. Here are the general steps to automate this process:

Identify the smart contracts: Identify the smart contracts of the decentralized exchanges you want to trade on. This can be done by researching the DEXs you want to trade on and finding the addresses of their smart contracts.
Query the blockchain: Write a program that can query the blockchain for the prices of the cryptocurrencies you want to trade. This can be done using a Web3 library such as Web3.py, which allows you to interact with the Ethereum network.
Calculate the prices: Use the prices obtained from the blockchain to calculate the prices of the cryptocurrencies on different DEXs. This can be done using the Bellman-Ford algorithm or other graph algorithms.
Identify arbitrage opportunities: Analyze the graph to identify arbitrage opportunities. This can be done by finding cycles in the graph that have a total weight of less than 1, which indicates that a profitable trade is possible.
Execute trades: Use the program to execute trades automatically on the DEXs you have identified. This can be done by sending transactions to the smart contracts of the DEXs.

To query the Ethereum blockchain, I suggest setting up a full archive Geth node (i.e., a node which stores all intermediate blockchain state transitions). Having in mind that speed is important, there are minimum hardware requirements to run this. A processor with a max boost clock of 4.3GHz, 64 cores, RAID0 NVMe Support, a 256GB RAM, and a high-performance SSD with at least 2TB free space to sync the Mainnet. You can find more on how to connect to the main Ethereum network here.

To perform concrete execution you would need a custom py-evm, which can be used to fork the Ethereum blockchain at any block height. You then decide the DEXs, you want to trade on and decide on the actions and assets, you’re working with. I typically decide on the assets based on ERC20 tokens listed on coinmarketcap with factors like the number of unique holders, the number of transfer transactions and the number of markets the asset is trading on. To enable action chaining, all considered assets must trade on all DEXs, for example, DAI trades on Uniswap, Bancor & dydx.

Example list of supported trade actions.

The model applies dependency-based state reduction which means stationary blockchain states are identified and skipped to avoid redundant computation and double counting of revenue. Translating the assets and actions into a graph with nodes and actions edges. Each node in the graph represents a cryptocurrency asset. While edges represent the movement of assets from input to output. Each edge’s weight is derived using the highest price found among all supporting markets, or 0 if there is no market. We then follow an algorithm to greedily extract arbitrage revenue as soon as one negative cycle is found. We use the Bellman-Ford-Moore algorithm and the Walk to the root cycle detection strategies to find negative cycles. For each arbitrage opportunity, the model gradually increases the input parameter (amount of base cryptocurrency asset) until the revenue ceases to increase.

Recall that the model greedily combines multiple asset paths into a single strategy. It’s generally believed that the revenue increases as the number of paths increases. This strategy requires minimal capital and it can be reduced if you use flash loans. The principal costs are the blockchain transaction fees, which remain below the revenue yielded by the strategy validated above. Note that a trading strategy may fail if the underlying market state changes before its execution. It’s also important that the transaction is broadcasted within 3-6 seconds, so it can reach the miners and be added to the block. But then there's a chance of MEV and someone frontrunning you.

Dealing with MEV

Miner Extractable Value (MEV) is a phenomenon that comes from block creators called “miners” having the ability to order the transactions contained within a block that they create however they wish. They also have an incentive to maximize their profits in terms of the transaction fees paid to them or by creating bots that exploit imbalanced prices or “slippage,” and the best way to accomplish this is to exploit the slippage before it happens. Large, fast trades on a cryptocurrency exchange like the model does will cause some slippage simply because it changes the supply of the asset being traded. So these bots exploit this by monitoring the blockchain network for transactions containing large trades that have not yet been added to a block by a miner. If a bot sees an upcoming buy, it will frontrun the buy, decreasing the asset’s supply and causing the price to go up. When the original trade goes through, supply decreases further and price increases even more. The bot can then sell its assets, making a tidy profit off the trade.

Looking beyond the financial gains of using a trader model like this, forks affect the blockchain consensus security, as they increase the risks of double-spending and selfish mining. Each time an MEV opportunity arises on the network layer, it’s generally assumed that the ‘honest’ miner succeeds in mining the MEV opportunity, and is yet to receive the reward initially. The miner, therefore, needs to decide whether to start to mine on a private chain, where he claims the MEV opportunity. It is been proven by the work of Arthur Gervias et al, that to solve for optimal MEV strategies we use the code, parametrizing using the current Ethereum stale block and also applying a binary search to find the lowest value for MEV in units of block rewards given a margin of error of 0.1.

I started this article by presenting two proven practical approaches that automatically extract revenue from the intertwined mesh of decentralized finance protocols. I tried to fully walk through the process & practical use of the first technique mainly suited for arbitrage trading. The technique applies to a real-time operation on blockchains with reasonably fast inter-block times (such as Ethereum), with an average search of 6.43 seconds. I also find that the capital requirements to generate revenues are minimal, at least when compared with mining. Not also neglecting some troubling security implications of profitable transactions on the blockchain consensus, quantifying the threshold value at which an MEV-aware rational miner will fork the blockchain if the miner does not succeed in claiming an unconfirmed MEV opportunity first is possible with the optimal adversarial strategy provided shared.

We have seen, heard, or read about multi-million-revenue trades that cleverly use the technique of flash loans to exploit the financial states in DeFi protocols. While exploiting these financial states, however, it is not a security attack in the traditional sense, the media often frames these high-revenue trades as “hacks.” When you investigate, you find out that the executing trader follows the rules set forth by the deployed smart contracts. Irrespective of the framing, liquidity providers engaging with DeFi experience millions of USD in unexpected losses. This highlights the need for automated tools that help traders, miners, protocol designers, and liquidity providers to understand arbitrage and financial implications in general when engaging with DeFi protocols.

Crypto arbitrage is just another way of making money in this precarious industry and there are different ways to go about it. When treated with due diligence and a learning mindset, you can automate spotting a difference in the pricing of a digital asset across two or more exchanges and make a series of transactions to take advantage of the difference.

I’m still learning, and open to collaborations & joint endeavors for great project ideas. So feel free to reach out if you need help getting started.