We created CFMMRouter.jl for convex optimization enthusiasts, twitter anons, and Tarun Chitra to easily find the optimal way to execute trades across a network of decentralized exchanges.

Why Routing?

In general, decentralized exchanges, such as Uniswap, Balancer, Curve, among many others, are organized as CFMMs—a particular type of automated market maker, whose behavior is mathematically defined by a trading function. A trader can then use a CFMM to trade a basket of assets (sometimes known as tokens) for another desired basket of assets, so long as the desired trade satisfies some conditions.

While there may be many assets in a network, in practice, individual CFMMs trade only a small number of these assets. This fact leads to several interesting problems when trading.

In one simple scenario, a trader might want to trade some amount x of token A for token B. It is then reasonable to ask: what is the largest amount of token B that can be received given this amount x of token A? If the trader is only allowed to trade with a single market of their choosing, the solution to this problem is easy—the trader simply checks how much of token B, given quantity x of token A, they expect to receive from each market that trades tokens A and B, and picks the market that gives the maximum amount of token B. When they are allowed to trade against any number of markets, as is usually the case in decentralized finance, the problem becomes substantially more complicated. In this case, an optimal solution could involve not only splitting an order across numerous individual markets trading tokens A and B, but also including sequential trades across any combination of markets which include other tokens. Finding the best way to execute this order is known as the optimal routing problem.

The optimal routing problem can often be phrased as a convex optimization problem. Problems of this form can generally be quickly and robustly solved in practice, even for relatively large problem instances. Inspired by this structure, we created CFMMRouter.jl, a package for optimal routing. The package uses the convexity of the routing problem and exploits some additional structure present in the optimal routing problem to further speed up problem solving. More details about this approach can be found in the documentation. While the solution method is somewhat technical, using this package requires very little optimization knowledge.

Technical approach

We use a common approach in large scale optimization: we decompose the large, difficult-to-solve routing problem into many small, easy-to-solve subproblems.

To do this, we form a dual problem, which has the same optimal value as the original optimal routing problem. At each iteration, we compute a set of market clearing prices. Using these prices, we compute the optimal arbitrage trade for each individual CFMM independently. This computation is fast and closed form solutions often exist. We then use these trades to update the market clearing prices. We repeat this process until we converge to the optimal solution.

For the mathematical details, check out the methods section of the docs.

What comes next?

This proof-of-concept implementation makes several simplifying assumptions. For example, we ignore gas fees and assume flash loans are available at zero cost to execute transactions. Furthermore, we leave a number of common CFMMs, including Uniswap v3 and Curve, unimplemented. Some of these can be implemented with the primitives we provide and some require more care. Stay tuned for more. PRs welcome!

Update (February 9, 2023)

We just released a paper that describes the approach used in the CFMMRouter.jl package. If you’re interested in how to quickly solve these problems in practice, the paper is now available. Additionally, this new implementation now includes Uniswap v3 as a constant function market maker that can be routed through. The implementation is relatively efficient and can even be used to learn how Uniswap v3 behaves. Finally, the experiments from the paper are open sourced and available at our GitHub repository.

If you’re interested in the details of this approach, check out the GitHub repo, read the documentation, and don’t hesitate to reach out to @theo_diamandis and @GuilleAngeris on Twitter.