cfmm_router_rs is a Rust library for optimal routing of trades across a network of Constant Function Market Makers (CFMMs). It is inspired by the functionality of the Julia library CFMMRouter.jl. The primary goal is to find the sequence of trades that maximizes a user-defined objective function, such as arbitrage profit against a set of reference prices or maximizing the amount of a specific token received.
The library provides tools to:
- Define different types of CFMMs (e.g., constant product pools like Uniswap V2).
- Specify objective functions (e.g., linear profit maximization, maximizing a specific token).
- Route trades across a collection of CFMMs to achieve the specified objective.
It uses a dual decomposition approach to solve the routing problem, with the L-BFGS-B algorithm (via the argmin crate) employed to solve the dual problem.
CFMMTrait: An abstraction for any constant function market maker. Implementors of this trait define their specific trading logic and how to solve the arbitrage subproblem for given dual variables (prices).ProductTwoCoinCFMM: A concrete implementation for two-token constant product pools.
ObjectiveFunctionTrait: An abstraction for the user's utility function U(Ψ), where Ψ is the net trade vector. The router aims to maximize this function.LinearNonnegative: Maximizep^T Ψfor a given price vectorp.MaximizeToken: Maximize the amount of a specific target token in Ψ.
Router: The main struct that orchestrates the optimization. It takes a set of CFMMs and an objective function, then solves for the optimal dual variables and reconstructs the primal trade solution.Solver: The underlying optimization algorithm. Currently, this library uses an L-BFGS-B implementation from theargmincrate, adapted to handle non-negativity constraints on dual variables via a transformation (ν_k = exp(α_k)).
- Abstraction via Traits: Core components like CFMMs and Objective Functions are defined using traits, allowing for extensibility with new pool types or optimization goals.
- Pure Rust Solver: Utilizes the
argmincrate for optimization, avoiding complex C/Fortran dependencies for the solver itself (though BLAS linkage is needed forndarray-linalg). - Arbitrage Subproblem Solution: Includes analytical solutions for common CFMM types (e.g., two-coin constant product).
- Example Usage: Provides an example (
arbitrage_example.rs) demonstrating how to set up and run the router.
The library is organized into several modules within the src directory:
lib.rs: The main library crate root, re-exporting key components.types.rs: Defines core data structures (e.g.,Token,Amount,Price,Reserves,ArbitrageResult,RouterResult,CfmrError).cfmm.rs: Contains theCFMMtrait and implementations likeProductTwoCoinCFMM.objective.rs: Contains theObjectiveFunctiontrait and implementations likeLinearNonnegativeandMaximizeToken.router.rs: Defines theRouterstruct and itsroutemethod, which ties everything together.solvers.rs: Implements the optimization logic, including the wrapper forargminand the transformation for handling constrained dual variables.
Key dependencies include:
argmin: For the L-BFGS-B optimization algorithm.argmin-math: Provides math traits forargmin, withndarrayas the backend.ndarray: For numerical vector and matrix operations.ndarray-linalg: For BLAS-powered linear algebra operations used byargmin.- This library is configured to link against a BLAS provider. The
Cargo.tomlis currently set up to attempt static linking with OpenBLAS (openblas-staticfeature). Ensure OpenBLAS is installed and discoverable on your system. Alternatively, for macOS, you might consider using theacceleratefeature by changingndarray-linalg's features inCargo.tomland addingaccelerate-srcas a dependency.
- This library is configured to link against a BLAS provider. The
approx: For floating-point comparisons in tests.
- Install Rust: If you haven't already, install Rust and Cargo from rustup.rs.
- BLAS Dependency:
- If using
openblas-static(current default inCargo.tomlafter your last change): Ensure OpenBLAS (including static libraries and headers) is installed on your system. You might need to set environment variables likeOPENBLAS_PATHorOPENBLAS_LIB_DIRandOPENBLAS_INCLUDE_DIRif Cargo cannot find it automatically. - If you switch to
accelerateon macOS: Addaccelerate-src = "0.3.2"to[dependencies]and changendarray-linalgfeatures to["accelerate"]. This usually works out-of-the-box on macOS.
- If using
- Build: Navigate to the
cfmm_router_rsdirectory and run:For a release build:cargo build
cargo build --release
To run the provided arbitrage example:
cargo run --example arbitrage_exampleTo run the unit tests:
cargo testHere's a conceptual overview of how to use the router (see examples/arbitrage_example.rs for a runnable version):
use cfmm_router_rs::cfmm::{ProductTwoCoinCFMM, CFMM};
use cfmm_router_rs::objective::LinearNonnegative;
use cfmm_router_rs::router::Router;
use cfmm_router_rs::types::{Token, Price, Reserves}; // Adjust imports as needed
use std::collections::HashMap;
fn main() -> Result<(), Box<dyn std::error::Error>> {
// 1. Define tokens
let token_a = "TOKEN_A".to_string();
let token_b = "TOKEN_B".to_string();
// 2. Create CFMMs
let mut reserves1 = HashMap::new();
reserves1.insert(token_a.clone(), 1000.0);
reserves1.insert(token_b.clone(), 1000.0);
let cfmm1 = ProductTwoCoinCFMM::new(reserves1, 0.003)?;
let cfmms: Vec<Box<dyn CFMM>> = vec![Box::new(cfmm1)];
// 3. Define an objective function
let mut prices = HashMap::new();
prices.insert(token_a.clone(), 1.0);
prices.insert(token_b.clone(), 1.01); // Target price for Token B slightly higher
let objective = Box::new(LinearNonnegative::new(prices));
// 4. Create and run the router
let router = Router::new(objective, cfmms, 100, 1e-6);
match router.route() {
Ok(result) => {
println!("Objective value: {}", result.objective_value);
println!("Net trades: {:?}", result.net_trades);
// Process other results...
}
Err(e) => {
eprintln!("Routing error: {:?}", e);
}
}
Ok(())
}Contributions are welcome! Please feel free to submit issues or pull requests.
This project is licensed under the MIT License