Eta X V1: Conservation Function and Pathfinding-based DEX Aggregation and Smart Order Routing
Contents
· Contents
· Introduction
· What is Eta X?
· Why is Eta X Important for Crypto’s Future?
· How Does Eta X Work?
∘ On-chain Data Collection
∘ Liquidity Pools and Swap-hops as Bidirectional Network Graphs
∘ Pathfinding Algorithms for Order Routing
∘ Price Impact Calculation and Route Selection
· Future Work
∘ Expanding DEX Support
∘ Data Collection Optimization
∘ Order Splitting
∘ Larger Graphs and More Powerful Pathfinding Algorithms
∘ Predictive Analytics
∘ Order Execution
· References
Introduction
This article outlines Deeplink’s latest project, Eta X. This version of Eta X is a proof of concept intended to demonstrate our smart order routing techniques but can be used analytically to inform a user of optimal trade paths, and can even highlight arbitrage opportunities across pools and exchanges. Some preliminary reading on the subjects discussed below can be found in our Medium publications:
- Smart Order Routing: A Comprehensive Guide
- Pathfinding Algorithms for DEX Aggregation and Smart Order Routing
- Machine Learning Applications in DEX Aggregation and Smart Order Routing
What is Eta X?
Eta X is an open-source initiative to build an agnostic decentralized exchange (DEX) aggregator and price discovery engine/smart order router (SOR). It has been designed from first principles to be universal, scalable, and unbiased via an adaptable method of reverse engineering the conservation functions employed in the automated market maker (AMM) algorithms of DEX liquidity pools.
A live demonstration of Eta X V1 can be found here:
The source code can be found here:
Why is Eta X Important for Crypto’s Future?
As decentralized finance (DeFi) grows, so does the number of exchanges on which blockchain-based assets can be traded. DEXs are seeing more and more adoption as the community trends towards trustless solutions in light of a string of centralized sources of fraud throughout the crypto ecosystem in recent years. In alignment with the philosophy of blockchains, DEXs address this issue by providing platforms that are resilient to manipulation by malicious insiders via distributed systems, algorithmic market making, open-source code review, and the Darwinian-esque selection of trustworthy and useful tools by the free market.
A DEX aggregator is a service that brings liquidity pools from multiple DEXs together in one platform and is generally packaged with some form of SOR. These aggregators can be compared analogously with services from other industries such as Google Flights or Digg. However, (much like many aggregators in other industries) DEX aggregators are generally not agnostic and have built-in biases that reward certain parties involved. This often takes the form of routing orders through liquidity pools which have reward schemes set up in favor of the protocol doing the routing, or via agreements with DEXs who wish to have more volume through their pools (which is proportional to revenue from fees).
Eta X strives to provide entirely unbiased DEX aggregation and SOR by abstaining entirely from engaging in such practices. Eta X will always provide the best possible routes as calculated by reverse engineering publicly available smart contracts and their respective AMM conservation functions.
How Does Eta X Work?
At its core, Eta X V1 is a pathfinding algorithm that uses AMM conservation functions to identify the best prices for exchanging one crypto asset for another by trading across a selection of routes across DEXs. Conservation functions are the largest factor in determining the profitability of trading within a given liquidity pool, to surmise, the conservation function determines the percentage by which you will change the price of the assets in the pool when you make a trade in it, this percentage change incurs a loss on your end. This iteration of the service is primarily designed around the XYK conservation function but has been designed with modularity and scalability in mind, and other functions such as constant mean product are being integrated presently.
On-chain Data Collection
Version 1 of Eta X relies on subgraphs provided by The Graph, an indexing protocol for querying blockchain networks (Ethereum, in this case). Currently, the service queries Uniswap V2 and SushiSwap, as they are similar in design and both use the XYK conservation function.
A user inputs two crypto assets, one which they wish to sell, and one which they wish to buy, along with the amount that they wish to sell. Queries are then sent which find pools that correspond to the relevant permutations of the two given assets, these permutations can be seen in the table below, where pools contain token0 and token1, and we are selling token A for token B:
These tokens are queried and sorted for values such as liquidity in USD or reserves in USD, as these are generally a somewhat decent indicator of their resistance to price impact and volatility-induced slippage. It is worth noting that Not Token A: Not Token B and Not Token B: Not Token A are not included but likely will be in future iterations, as they were found to increase query times without generally providing better paths. It may be the case that some set theory principles may be employed to collect pools that are not a given token but are also selected from the list of ‘not given tokens’ retrieved in queries 1 and 3, however, this complexity would also increase query times — further testing is required to evaluate the effectiveness of these approaches.
Liquidity Pools and Swap-hops as Bidirectional Network Graphs
One of the best ways to negate losses to price impact is to distribute your order across liquidity pools. This can be accomplished either by breaking your order down into smaller parts and trading smaller amounts through multiple pools, by using intermediate pools to bridge a trade across multiple pools (sometimes called swap-hops), or a combination of both.
Swap -hops are best understood by a real-world example, swapping UNI for LINK can be done directly in one pool if such a pool exists on the given exchange. Assuming this pool exists, it may have low liquidity, which would result in large losses to price impact — low liquidity/reserves can also be indicative of volatility, a primary factor in losses to slippage. If there exist at least two pools containing at least one of the two given assets, a swap-hop can potentially facilitate a trade route that is less susceptible to both price impact and slippage. For example, WETH-UNI and WETH-LINK pools could be used to make a trade as follows:
- Sell UNI for WETH in the first pool
- Take that WETH and sell it for LINK in the second pool
In this case, if we were to swap 1,000 UNI ($6256) for LINK directly in the Uniswap UNI-LINK pool we would incur a 9.7% loss to price impact, receiving 87 LINK and paying 0.0007 ETH in gas fees. Whereas the route traversing UNI-WETH → WETH-LINK across Uniswap pools only incurs a 0.075% price impact, receiving 97.5 LINK and paying 0.0014 ETH in gas fees. In this real-world scenario, Eta X has saved the user $68.86 worth of UNI.
In order to find these swap-hop routes, Eta X creates a bidirectional network graph of relevant liquidity pools, where each node in the graph represents a liquidity pool. Each pool is then connected to any other pool with one or more assets in common, for example, a DAI-USDC pool would connect to a DAI-WETH pool, but not a WETH-UNI pool. This is explained in more depth in our article on pathfinding for SOR, the following graph depicts the graph derived from a set of pools queried from a USDC and WETH trade query, pools in this visualization are sized by their total locked value (TVL, a strong indicator of resistance to price impact and slippage):
Pathfinding Algorithms for Order Routing
Network graphs are an optimal representation of data for pathfinding optimization, as such, representing liquidity pools in this fashion opens our system up to the many well-established pathfinding algorithms of graph theory. While the number of DEXs factored into calculations are limited to single digits, simple-yet-effective pathfinding algorithms such as Bellman-Ford suffice in negligible runtime. Despite the O(V3) time complexity for our near V2 worst-case scenario, the graphs are small enough to negate this impact.
However, simply implementing the Bellman-Ford algorithm in its original form raises some issues with path validity. For example, while the traditional Bellman-Ford algorithm may see a path selling USDC for WETH along the route of pools USDC-DAI → USDC-LINK → LINK-WETH as valid, it is not actually valid for our purposes, as this path represents the following sequence of swaps:
- Sell USDC for DAI in the USDC-DAI pool
- Take that DAI and sell it in the USDC-LINK pool — here we see our issue, this pool does not accept DAI
Therefore, we have to include some extra checks to ensure path validity. In this system, a path is valid if the token being sold in the current pool must exist in the next pool, and if the final output token is the token being purchased. A single node is also considered a valid path if it contains both of the assets involved in the swap.
The algorithm for this process is as follows:
- Enter the first node with the asset being sold
- Take the partner asset of that node to the next node, if the partner symbol does not exist in that node, the path is invalid
- Repeat this until reaching the final node, if the final output asset is not the asset being purchased, the path is invalid
Price Impact Calculation and Route Selection
Now that we have created a graph and a modified Bellman-Ford algorithm to traverse and validate paths from the token being sold to the token being bought, we need to evaluate the profitability of each path identified. While there are certainly other factors that contribute to the profitability of an order route, price impact, slippage, and gas fees are two of the most important. As such, for each exchange, we have reverse-engineered the AMM conservation function to calculate a minimum return and price impact percentage and grab gas fee estimates directly from the Ethereum network.
For DEXs using the XYK conservation in their pools such as Uniswap V2 and SushiSwap V2, assets are priced via the following equation:
Where x is the reserves of token0, y is the reserves of token1 and k is a constant. Let’s say we want to swap token x for token y, we can use the following equations to determine the impacted price, minimum return, and price impact percentage:
Where x_new is the new reserve of token x after depositing x_input, y_new is the new reserve of token y after adjusting to maintain the constant k, r_min is the minimum amount of token y returned from the swap, p_y, and p_y_new are the prices of token y before and after the swap respectively, and P is the price impact percentage.
Using these equations our pathfinding algorithm is modified further to calculate the price impact of each swap in each route. These calculations are done after the simple paths are calculated, so as to avoid calculating price impact for invalid routes, which means that even though we are doubling over the small list of valid routes, we are not wasting computations on price impact calculations for the many invalid routes.
These routes are then sorted by returns and a list of recommended routes is returned to a user in descending order of highest returns.
Future Work
Having proven the concept and effectiveness of SOR by price impact-based pathfinding techniques, development on Eta X can be further improved along several verticals.
Expanding DEX Support
One of the most obvious ways to extend the capabilities of Eta X is to simply include more DEXs. The system has been designed such that doing so is a relatively streamlined and modular process, however, some work is required to reverse engineer the ever-increasingly complex conservation functions of emerging DeFi protocols. SushiSwap is a fork of Uniswap and has been seamlessly integrated with Eta X as of now, Balancer is next on the roadmap on account of its popularity and solid subgraph support.
Price impact calculation algorithms have already been written for Balancer’s multi-asset pools, which use a constant mean product conservation function, as opposed to the standard constant product conservation function devised by Uniswap. While the change may appear inconsequential at first glance, there are some major differences in the calculation of price impact. Balancer’s pools are kept in correct ratios by the following equation:
Where V is a constant, Bt is the balance of token t, and Wt is the proportional weight of that token in the pool. Balancer pools can hold up to 8 tokens in a liquidity pool, where each token is assigned a weight from 0–100. For example, a pool containing:
- 200 WETH with a weight of 60
- 100,000 USDC with a weight of 20
- 100,000 DAI with a weight of 20
The constant V is given by:
The amount of tokens received in a Balancer pool swap is given by the following formula:
Where A_O is the amount of token being swapped out of the pool, A_i is the amount of token 1 in, Bi is the balance of token being swapped into the pool, s is the swap fee of the pool, Wi is the weight of the token being swapped in, and WO is the weight of the token being swapped out.
Community Suggestions
While we will be working to add the most popular and useful exchanges through our own vetting method, we would like to invite the community to suggest their own additions to Eta X’s DEX pool. To achieve this, Eta X V2 will include a DEX suggestion form where users can import a DEX and request its addition to Eta X.
Data Collection Optimization
As powerful as The Graph is, it is not without some latency limitations. Fetching pool data is by far the biggest bottleneck in the current iteration of the system, constituting up to 80% of the runtime per query in worst-case scenarios. In response to this, we are looking into tighter integration with L3 Atom for faster and more reliable feeds by grabbing data directly from Ethereum via Infura and deriving the relevant values manually. Additionally, we may also be able to squeeze more out of The Graph by either migrating over to their decentralized subgraphs or by hosting our own subgraphs.
Additionally, caching methods may improve the latency of the current implementation by querying large sums of pool data periodically and retrieving this data per user input, as opposed to the current PoC method of querying subgraphs with each user input.
Order Splitting
Order splitting is a crucial piece of SOR, and will be a major area of focus for Eta X V2. Order splitting involves breaking an order down into smaller parts to be distributed across multiple pools or routes. This concept is currently in the research stage of development, in which we are exploring options such as dynamic algorithms for splitting orders by liquidity, total value locked (TVL), and other such factors. We are also exploring the possibility of leveraging deep reinforcement learning (DRL) for order splitting purposes, in this process, a DRL agent would be tasked with splitting orders using the algorithms of Eta X in such a way that maximizes returns. This can be done off-chain in such a way that does not require any actual crypto to be transferred, thanks to the use of price-impact calculations. However, this may miss some important caveats of volatility and slippage, factors that may need to be considered as parameters in our model.
Larger Graphs and More Powerful Pathfinding Algorithms
As we add DEXs to the search space of routes, the number of nodes in a given graph will expand rapidly. This may mean that dynamic algorithms such as Bellman-Ford will begin to struggle to find paths within a reasonable timeframe. In this case, we may need to employ algorithms more suited to large graphs. The intricacies of pathfinding algorithms for this problem are explored in more depth in this article. While still an example of dynamic programming, the Floyd-Warshall algorithm is particularly effective for worst-case scenarios of v2 graphs, where Bellman-Ford takes is O(v3) for each node, Floyd-Warshall is O(v3) for the entire graph.
Another promising approach would be the inclusion of heuristic algorithms such as ant colony optimization or genetic algorithms, both of which are particularly effective at finding near-optimal paths through large graphs.
Predictive Analytics
While price impact calculations go a long way in estimating the profitability of an order route, we will likely want to factor in other datapoints to account for potential slippage losses to volatility. This may be an area in which complex data collection and machine learning could benefit the system greatly. For instance, we may be able to attribute risk scores to pools by assessing their liquidity and volume over time, this may even allow us to identify malicious or faulty pools (which most certainly do exist on many DEXs).
Were models to be trained via historical datapoints, it may even be possible to predict data somewhat ahead of time by using Ethereum’s mempool data to retrieve transaction information before they are processed by the blockchain and their target smart contracts.
Order Execution
Early iterations of Eta X are intended to demonstrate the methodology and capabilities of the SOR algorithms designed in-house by Deeplink, while also being an analytical tool through which users can identify trade opportunities. Later stages of Eta X are intended to facilitate the execution of these trade opportunities via wallet and smart contract integration.
