README.md

CFMMRouter

Overview

This package contains a fast solver for the CFMM Routing problem. We partially decompose the problem to enable fast solutions when the number of CFMMs is large relative to the number of tokens. We describe our algorithm in detail in our paper, An Efficient Algorithm for Optimal Routing Through Constant Function Market Makers.

For more information, also check out the documentation.

Quick Start

First, add the package locally.

using Pkg; Pkg.add("CFMMRouter")

Make some swap pools.

using LinearAlgebra
using CFMMRouter

equal_pool = ProductTwoCoin([1e6, 1e6], 1, [1, 2])
unequal_small_pool = ProductTwoCoin([1e3, 2e3], 1, [1, 2])
prices = ones(2)

Build a Router & route.

router = Router(
    LinearNonnegative(prices),
    [equal_pool, unequal_small_pool],
    2,
)
route!(router)

Check out the results.

Ψ = round.(Int, netflows(router))
println("Profit: $(dot(prices, Ψ))")

Performance

This routing algorithm scales approximately linearly in the number of swap pools for the arbitrage problem. These tests were run on a MacBook Pro with a 2.3GHz 8-Core Intel i9 processor. Several performance improvements are possible.

Citing

@article{diamandis2023efficient,
  title={An Efficient Algorithm for Optimal Routing Through Constant Function Market Makers},
  author={Diamandis, Theo and Resnick, Max and Chitra, Tarun and Angeris, Guillermo},
  journal={arXiv preprint arXiv:2302.04938},
  year={2023}
}

References

• T Diamandis, M Resnick, T Chitra, G Angeris. An Efficient Algorithm for Optimal Routing Through Constant Function Market Makers

• G Angeris, T Chitra, A Evans, and S Boyd. Optimal Routing for Constant Function Market Makers