Vincent Danos

Hamza El Khalloufi

Julien Prat

Global order routing on exchange networks

We propose an abstract notion of networks of exchanges with an eye to modelling the global money market of DeFi (decentralised finance). We formalise routing and arbitrage on such networks as convex optimisation problems. We provide bounds with closed formulas in the specific case of Uniswap-like automated markets and a restricted form of cyclic arbitrage. We compute the associated lower bounds on actual data derived from the Ethereum blockchain.

Introduction

The global money market of DeFi (decentralised finance) allows traders to exchange assets represented by ERC20 tokens on the Ethereum blockchain. Each money market on a specific pair of tokens A/B can be seen as a 2-sided platform where liquidity providers transact with liquidity consumers. There are several implementations of such platforms. Some use the traditional form of the limit order book [START_REF] Abergel | A mathematical approach to order book modeling[END_REF], but most use the so-called constant function automated market makers (eg Uniswap v2 [START_REF] Adams | Uniswap v2 core[END_REF]) which compute prices algorithmically as a function of their current reserves in A and B. The intense competition for liquidity and high clonability of the said platforms has given rise to a dense and complex network (a tiny subgraph of which is shown in Fig. 5). Prior academic work on such networks [START_REF] Angeris | An analysis of uniswap markets[END_REF][START_REF] Angeris | Improved price oracles: Constant function market makers[END_REF] focusses on local questions, with the exception of the recent Ref. [START_REF] Ye | Cyclic arbitrage in decentralized exchange markets[END_REF] which looks at cyclic arbitrage (about which more later). Our contribution explores two global questions centred on liquidity consumers (also known as takers or traders).

The first question is routing: eg "Here I have a 100 ETH, how should I best convert them to DAIs". Unsurprisingly, direct routes may not always be best, and convex combination of routes may dominate any particular path. Fig. 1 gives an actual example of routing a 100 ETH in order to maximise the amount of DAIs obtained. One sees that the order is split among 7 distinct money markets.

The second question is arbitrage (aka price consistency): eg in a given state of the network "Is there any way I can chain operations leading to certain non-zero profit". We define in this paper a class of convex optimisation problems which encompasses both the global routing problem and the arbitrage problem. We show that problems in this class always have solutions. We also show that optimal arbitrage eliminates price inconsistencies. One can construe this result as saying that the global network 'learns' a consistent set of prices under optimal arbitrage.

For both questions we introduce tractable sub-problems. Specifically, we demonstrate that arbitraging along cycles, while sub-optimal in general can be efficiently tested and solved. This leads to computationally cheap lower bounds on profit. For Uniswap price functions, we derive a closed formula to compute the maximal extractible profit on any given cycle. Putting the two results together (cyclic arbitrage detection and explicit max profit), we look at actual Ethereum data and efficiently find lower bounds for several arbitrage opportunities. For routing we introduce the convex subproblem where one restricts to convex combinations of a given set of independent paths. It is possible to derive a simple algorithm for optimal convex combinations of Uniswap price functions, which is of independent interest and that we will publish elsewhere. Acknowledgments: The authors wish to thank Saad Bouhoud, Ayman Elyahmidi, and Vincent Bernardoff for data-related discussions, and for sharing code to obtain the relevant Uniswap data from an Ethereum node. The authors also wish to thank Jérôme de Tychey for numerous interesting discussions on the matters of this paper, and Ye Wang and co-authors for sharing an early version of their paper on cyclic arbitrage [START_REF] Ye | Cyclic arbitrage in decentralized exchange markets[END_REF].

Prices, Plans, Profits

Many price functions have been considered to define prices in algorithmic exchanges. We will use the specific Uniswap function (defined right below) to obtain closed form solutions for cyclic arbitrage. Up to that point all our development is generic and relies only on the following abstract definition.

Definition 1 A price function is a map f : R + → R + such that f (0) = 0, f is monotonically increasing, strictly concave, bounded, and continuous.

We also sometimes suppose our price functions are differentiable. It will be clear when we do. The requirements encapsulated in Def. 1 are natural for prices: f (0) = 0 means one gets nothing for nothing, increasing means one gets more for more, concave means returns decrease, and boundedness expresses the fact that liquidity reserves are finite.

Notice that a (half) order-book on an A/B pair -ie a price-sorted list of discrete offers (p i , V i ) where V i is an amount of Bs and p i the unit price to pay in A to take that offer-also defines a price function. It just happens to be piecewise affine (hence is not everywhere differentiable). Boundedness holds whether liquidity is provided via an order book or a constant function market-maker.

A simple example of price function is the Uniswap one. For an A/B pair it reads:

f (x) := [B](γx)/(γx + [A]) (1)
where [A], [B] > 0 are the local reserves (or pools) in tokens A and B. The γ parameter is such that 0 ≤ 1 -γ < 1, and 1 -γ represents the fee extracted by the liquidity providers for every transaction. It is easy to see that 0 ≤ f (x) < [B]. Hence a Uniswap pair never pays out more than the reserve however small. 3 This function satisfies all the requirements of a price function as defined above. The dual price function which specifies how many As one gets for a given amount of Bs is obtained simply by exchanging the roles of [A], [B] (not to be confused with f -1 which specifies how many As one needs to spend to obtain a given amount of Bs).

The reserves [A], [B] are modified by every transaction and therefore induce a modification of the price function -also known as the price impact of the transaction. 4The class of price functions is closed under: sum, composition, pre-and post-composition by positive scalar multiplication.

Definition 2 An exchange network consists of: -an undirected multi-graph G = (V, E), without loops -a fixed chosen orientation for each edge e in E -a family of price functions (f e ; e ∈ E)

We write s(e), t(e) ∈ V for the source and target of an edge e. Hence both s and t have type E → V ; and for A ∈ V , s -1 (A) is the set of edges emanating from A, while t -1 (A) is the set of edges pointing to A.

Given φ = e 1 , . . . , e n a simple path in G, set:

f φ = f en • • • • • f e1
f φ is a price function (by composition). The path has to be simple, else the first visit to an edge may change the reserves, and the second one will find an updated price function. In this paper, we only rarely consider specific update mechanisms, and almost always work with a given fixed state of the network of abstract price functions.

An example of such a structure is a snapshot of the Uniswap network. Nodes are ERC20s, edges are pairs with a chosen orientation. The level of reserves in each pair determines the price function f e . In reality, the graph part also changes slowly as new nodes and pairs are added.

We now define our main object of interest:

Definition 3 A transfer plan τ is an element of the standard cone E → R + (hence convex). The support of τ is the subset of E where τ is non-zero.

For each e, τ (e) ≥ 0 specifies the amount of s(e) injected in the price function f e . There are implicit restrictions in Def. 3 which are worth discussing. We do not consider sliced orders, ie repeated swaps on the same directed edge. It is known for constant function aMMs that slicing leads to sub-optimal plans [START_REF] Angeris | An analysis of uniswap markets[END_REF]. Also, we do not consider backtracking, ie transfer plans where an underlying edge is used twice with opposite orientations. This is because each edge is directed. 5 Finally, we do not incorporate in our notion of transfer plan the very real possibility which DeFi agents have, namely to modify the reserves (eg by depositing or withdrawing liquidity in the various pools of aMMs) and therefore the price functions while trading. It seems unlikely that backtracking or liquidity modifications could improve transfer plans relative to the objectives given below, but it remains to be seen.

A plan τ translates directly in a concrete Ethereum transaction. Because of the existence of flash loans, at least for most liquid tokens, the order in which each elementary swaps are performed is irrelevant. We neglect in this model gas costs and flash loan fees.

Given (G, f ) we can now define the profit map Ψ which maps a transfer plan (an E-vector), to its resulting balance (a V -vector): Definition 4 The profit map Ψ : R E + → R V derives from the data as follows:

Ψ (τ )(A) := Ψ + (τ )(A) -Ψ -(τ )(A) Ψ + (τ )(A) := e∈t -1 (A) f e (τ (e)) Ψ -(τ )(A) := e ∈s -1 (A) τ (e )
The first component Ψ + (τ )(A) is the amount of A returned by τ , while the second Ψ -(τ )(A) is the amount of A invested by τ . The difference Ψ (τ )(A) is the balance change of A as a result of executing τ -ie the profit (which can be negative!).

We see that: -Ψ + ( )(A) is concave, non-decreasing, bounded, differentiable (if edges are); it is only increasing and strictly concave in those components τ e such that t(e) = A.

-Ψ -( )(A) is a linear function R E + → R + ; -Ψ ( )(A) is a concave function bounded above by e∈t -1 (A) f e (∞) (sum of A's liquidities available in the network) and Ψ (0 E ) = 0 V . Say a node A is: -a source in τ if Ψ + (τ )(A) = 0, Ψ -(τ )(A) > 0, -a sink if Ψ + (τ )(A) > 0, Ψ -(τ )(A) = 0, -an intermediate if Ψ + (τ )(A) = Ψ -(τ )(A) > 0.
For differentiable price functions we can compute Ψ 's Jacobian:

Ψ (τ + h)(A) -Ψ (τ )(A) = e∈t -1 (A) (h e f e (τ (e)) + o(h e )) -e ∈s -1 (A) h e So the Jacobian matrix of Ψ of dimension V × E is: JΨ (τ )(A, e) =    f e (τ (e)) if e ∈ t -1 (A) -1 if e ∈ s -1 (A) 0 else
(Note that as G is loopless, no e is both in s -1 (A) and t -1 (A).) As said, a transfer plan also has a side effect (here a monoid action) on the price functions which we denote by f e → τ τ (e) • f e ; that is to say if f e is the price function of edge e, and the amount τ (e) is injected in e, we write τ (e) • f e for the new price function. We also write more generally τ • Ψ for the new profit function induced by the execution of plan τ . We leave this action implicit and just ask that it verifies the no-slicing property:

Ψ (τ 1 + τ 2 ) ≥ Ψ (τ 1 ) + τ 1 • Ψ (τ 2 )
This inequality expresses the fact that no profit can be made by simply slicing a plan in two parts. It is easy to see that Uniswap price functions satisfy no-slicing, and, therefore, so do profit functions derived from Uniswap price functions.

We can represent some of the plans defined above in a more diagrammatic way. Fig. 1 (retrieved from the 1inch price aggregator web site) gave an example with a unique source ETH and unique sink DAI and one intermediate node USDC (with zero balance). The plan τ invests at ETH and collects the returns at DAI: Diagrams are convenient ways to represent those plans that have only sources, sinks, and intermediates. Every diagram gives rise to a plan. Not every plan is a diagram, but with respect to some of the objectives functions presented in the next section, optimal ones will be.

Ψ -(τ )(ETH) = x, Ψ + (τ )(ETH) = 0; Ψ -(τ )(DAI) = 0, Ψ + (τ )(DAI)

Orders, routes, arbitrage

We define now a number of convex problems for transfer plans in standard form [5, §4.2.1]. In each case we ask whether the problem is feasible and has a bounded objective function. At the end of the section, we prove the existence of solutions for these problems (provided they are feasible). As profit functions are not strictly concave in all coordinates, the solutions may not be unique in general.

Smart order routing

Recall the routing question in the introduction: "what is the maximum amount of DAI I can get for 100ETH using all aMMs and dexes available?"

This question can be recast as the forward routing problem with A = B, a ∈ R + :

sor(a : A, B) = max Ψ (τ )(B) with Ψ (τ )(A) ≥ -a Ψ (τ )(C) ≥ 0, C = A, B (2)
For a plan to satisfy the constraints (aka be feasible), it should not cost more than a : A (but could invest more), and have non-negative balance for Cs which are neither A nor B. The zero plan 0 E satisfies the constraints, so the problem is feasible.

An optimal τ will have Ψ (τ )(A) = -a, iff A and B are connected in G. One says the constraint is active in this case. Indeed, pick any path φ from A to B in G, if there is some unspent A in τ , ie Ψ (τ )(A) > -a one can push the remainder a > 0 through φ to obtain f φ (a ) > 0 additional Bs. Conversely, if there is no possible way to use some A to get some B, the amount of A spent is indifferent. Likewise, the C constraints will be active for optimum τ if connected to B.

We also see that for the routing problem to be sensible, there must be a compatibility with the orientation of G in the sense that directed paths must exist between inputs and outputs of the problem. Else the problem is degenerate.

As the user may have several types of tokens on hand, it makes senses to generalise the above allowing for multiple inputs (but still one output):

sor(a 1 : A 1 , . . . , a n : A n , B) = max Ψ (τ )(B) with Ψ (τ )(A i ) ≥ -a i Ψ (τ )(C) ≥ 0, C = A i , B (3)
What about the inverse question "what is the minimum amount of ETH I need to spend to get 100DAI?". This question can also recast as the backward routing problem with A = B, with b ∈ R + :

sor(A, b : B) = max Ψ (τ )(A) with Ψ (τ )(B) ≥ b Ψ (τ )(C) ≥ 0, C = A, B (4)
A feasible plan is one that pays ≥ b tokens of type B and has positive balance on all Cs. Differently from the forward problem, the backward feasibility set may be empty. Suppose the only edge in G joins A to B and b > f e (∞). No matter how much money one injects on the A side, it will never obtain b. If the feasibility set is not empty, an optimum plan will strive to minimise the expense in A. Note that Ψ (τ )(A) will be negative at optimum, unless there is an arbitrage opportunity (which user could take, see below).

So far the objectives only concern one output. To generalise to multi-output plans, we can set a reference price p ∈ R V + and use it to scalarise the problem [5, §4.7.4]. For a ∈ R + , ψ 0 ≤ 0 V , we define:

sor(p, a : A) = max p, Ψ (τ ) with Ψ -(τ )(A) ≤ a Ψ (τ ) ≥ ψ 0 (5)
Here a feasible plan must invest no more than a : A, and respect an overall budget limit ψ 0 . Hence there is always the zero plan.

Arbitrage

On to the price consistency problem:

arb(A) = max Ψ (τ )(A) with Ψ (τ ) ≥ 0 (6)
A feasible plan is any that results in a non-negative balance for all tokens. It is feasible as 0 E satisfies constraints. The optimal value will therefore also be non-negative. Of course the interesting question is qualitatively whether there is a non-zero solution, and quantitatively how to compute it. As above one can prove that any solution will activate the constraints

Ψ (τ )(B) = 0 for B = A.
As in the routing problem, one can scalarise the multi-output version of this problem by maximising p, Ψ (τ ) under the free-lunch constraint Ψ (τ ) ≥ 0 V .

Assuming that Ψ satifies no-slicing:

Proposition 1 The arbitrage problem ( 6) is idempotent.

Proof: Let τ 1 , τ 2 be two successive optimal plans. We compute:

Ψ (τ 1 + τ 2 ) ≥ nsl Ψ (τ 1 ) + τ 1 • Ψ (τ 2 ) ≥ 0
where recall τ • Ψ is the profit function after the execution of τ . The sum τ 1 + τ 2 represents the fused plan. The first inequality is the no slicing condition defined earlier (joining orders on the same edge is always better). By definition, both terms on the rhs of this inequality are positive, and, therefore, so is the lhs. In other words τ 1 + τ 2 is feasible. It also follows that

Ψ (τ 1 + τ 2 ) ≥ Ψ (τ 1 )
, and, therefore, by optimality of τ 1 , it must be that τ 2 = 0.

In the differentiable case it is enough to look near the zero plan to detect non-zero arbitrage.

Proposition 2 There is a non-zero solution to the arbitrage problem iff there exists ≥ 0 E , such that JΨ (0)( ) ≥ 0 with at least one coordinate JΨ (0)( )(A) > 0.

Proof: The if part is clear. The only if part follows from the fact that Ψ is concave. To see this pick a τ (not necessarily optimal) such that Ψ (τ )(A) > 0, and choose t ∈ (0, 1):

Ψ (tτ ) = Ψ ((1 -t)0 E + tτ ) ≥ (1 -t)Ψ (0 E ) + tΨ (τ ) = tΨ (τ )
where we use the fact that Ψ is concave (in each argument) and Ψ (0 E ) = 0 V . By definition of the Jacobian:

Ψ (tτ ) = JΨ (0)(tτ ) + o( t 1 )
It follows that for t > 0 small enough, JΨ (0)( )(A) > 0, with = tτ . The criterion implies that at least one e > 0. Keep in mind that the arbitrage may be very small (see lower bound examples later). The criterion says nothing about its magnitude; it merely gives a direction in the cone of plans in which to look for one.

Using the expression obtained earlier for J(Ψ ), we can rephrase the criterion as follows:

Corollary 1 Problem ( 6) has a non-zero solution iff there is ∈ R E + such that for all A ∈ V :

e∈t -1 (A) f e (0) e ≥ e ∈s -1 (A) e
and for at least one A the inequality is strict.

For concrete price functions such as Uniswap's with derivatives at zero which are 0-homogenous in the reserves, a rescaling of these reserves by a positive coefficient leaves the criterion invariant.

Existence

Except for problem [START_REF] Stephen | Convex optimization[END_REF], problems considered so far have the following form: 7) is compact and non-empty in R E + ; therefore problem [START_REF] Ye | Cyclic arbitrage in decentralized exchange markets[END_REF] has solutions. ande n ∈ E such that τ n ∞ = τ n (e n ). As E is finite, there must a subsequence of e n which is constant and equal to some e 0 with source A. Let τ m be the associated subsequence of plans. By construction τ m (e 0 ) → ∞.

max h(Ψ (τ )) with Ψ (τ ) ≥ ψ 0 (7) with h : R V → R a continuous function, ψ 0 ≤ 0 V . Proposition 3 The feasible set C = {τ | Ψ (τ ) ≥ ψ 0 } of problem (
Proof: First C is non-empty as 0 E is in C. Second C = ∩ A Ψ (τ )(A) -1 [ψ 0 (A), ∞) is closed in R E + , as Ψ (τ )(A) is continuous. Suppose C is not bounded. Pick a sequence τ n ∈ C such that τ n ∞ ≥ n,
For general reasons, we have:

Ψ (τ )(A) ≤ E f e (∞) -τ (e 0 ) hence Ψ (τ m )(A) → -∞ which contradicts the budget constraint Ψ (τ )(A) ≥ ψ 0 (A).
As h • Ψ is continuous, the second point follows.

Lower bounds

The problems considered in the preceding section may have solutions, but the proof hardly tells us how to find them. In this section, we add new feasibility constraints and derive simpler and tractable subproblems which will give lower bounds to the original ones.

In the appendix we further specialise to Uniswap's price functions and obtain closed formulas.

Routing on independent paths

Let us return to the forward routing problem with source A and target B. Fix (φ i ; 0 ≤ i < n) a family of independent paths in G from A to B with underlying edge and node sets E ⊆ E, V ⊆ V , and strictly concave price functions. We restrict the forward A/B routing problem (2) by restricting plans to have their support included in E . This subproblem is again convex, evidently. All nodes C ∈ V {A, B} have non-negative balance by definition, but we have noticed already that optimal solutions of the original problem satisfy Ψ (τ )(C) = 0 (Cs are intermediates). This leads us to an alternative and equivalent formulation of the subproblem:

sor(a : A, φ 1 , . . . , φ n ) := max i f φi (t i a) with (t i ) ∈ ∆ n (8)
with ∆ n the simplex of dimension n -1, where n is the number of support paths. The quantity t i represents the fraction of the original budget a allocated to path φ i . Write Ψa (t) := i φ i (t i a) for the new objective function.

For any convex combination u

+ v = 1, u, v > 0: Ψa (u(t 1 , . . . , t n ) + v(s 1 , . . . , s n )) = i f φi ((ut i + vs i )a) = i f φi (ut i a + vs i a) ≥ i uf φi (t i a) + i vf φi (s i a) = u i f φi (t i a) + v i f φi (s i a) = u Ψa (t 1 , . . . , t n ) + v Ψa (s 1 , . . . , s n )
hence Ψa is stricly concave, as the φ i s are.

We have proved that for any choice of a family of paths:

Proposition 4

The restricted forward routing problem (8) has a unique solution t ; moreover, its optimum is a lower bound to that of the unrestricted forward routing problem [START_REF] Adams | Uniswap v2 core[END_REF].

Not every plan can be expressed as a sum of independent paths. There seems to be a natural intermediate and possibly tractable subproblem, where one maximises over diagrams. This is a larger subproblem as is evident from the example Fig. 1 which is not a sum of independent paths (because of the last USDC/DAI leg). Extending this proposition to diagrams would improve the lower bound. However, it is unclear how to do this as diagrams (say with one source, and one sink) do not form a convex subset of the plans.

Arbitraging simple cycles

Let us return to the arbitrage problem (6) with source A. Similarly to the routing problem, we restrict the arbitrage one. Specifically, we ask for plans which are supported by a given simple cycle going through A. The restricted problem is still convex as are all subproblems based on restriction on the support. Also, it is clear that the original problem has solutions that are not supported by a cycle, so this approach will only provide lower bounds, in general.

Let φ be a directed cycle in G. One needs only to direct edges in the cycle all in one direction or the other. As constraints will be active for solutions of the subproblem, we have an alternative and equivalent formulation:

arb(a : A, φ) := max f φ (a) -a with a ∈ R + (9)
Note that f φ (a) -a is the profit function associated to the unique plan τ with τ (e) = a for the only edge e in φ with source A, which induces a zero profit at every other node of the cycle. The only optimisation variable is now a. As f φ is a strictly concave price function:

Proposition 5 The cyclic arb subproblem has a unique solution (possibly trivial).

The arbitrage criterion simplifies to:

Proposition 6
The cyclic arbitrage problem ( 9) has a non-zero solution iff:

f φ (0) = e∈φ f e (0) > 1
Using the argument of the proof of Prop. 2, one can show that the set of as such that f φ (a) ≥ a is a compact interval of the form [0, a 0 ]. The solution is somewhere in between and is non-trivial iff 0 < a 0 .

Cyclic arbitrage: the Uniswap case

Consider again the Uniswap graph, where nodes are ERC20 tokens, edges are pairs of reserve pools with fees 0 ≤ 1 -γ 1 (possibly different in each direction). As above the reserves of an A/B edge are written [A], [B] and we define the ratio ρ AB = [B]/[A] -so that the marginal price of A in B is γ AB ρ AB .

Closed formulas for arbitrage

To simplify notations we consider triangular cycles on tokens A, B and C.

We have a profitable triangular arbitrage if:

a 0 Swap ---→ b Swap ---→ c Swap ---→ a 1 , with a 0 < a 1
We can specialise the arbitrage criterion of the main text as follows:

Lemma 1 (cyclic arbitrage):

A triangular cycle is arbitrage-free iff:

γ AB γ BC γ CA ≤ ρ AB ρ BC ρ CA ≤ (γ AB γ BC γ CA ) -1 (10)
Although we have already proven this result, it is instructive to redo the proof in this special case, as composition of Uniswap price functions can be computed explicitely. Specifically, we have:

a 1 = ρ CA ρ CB ρ BA γ CA γ BC γ AB 1 a0 + ρ CB ρ BA γ CA γ BC [A] AB + ρ CB γ CA [B] BC + 1 [C] CA
To have a non-zero arbitrage we need to have a 0 < a 1 :

a 1 = ρ CA ρ CB ρ BA γ CA γ BC γ AB 1 a0 + ρ CB ρ BA γ CA γ BC [A] AB + ρ CB γ CA [B] BC + 1 [C] CA > a 0 Equivalently: 0 < a 0 < γ AB γ BC γ CA ρ AB ρ BC ρ CA -1 γ AB [A] AB + γ BC γ AB ρ AB [B] BC + γ CA γ BC γ AB ρ AB ρ BC [C] CA
which can always be achieved by choosing a 0 small enough, provided γ AB γ BC γ CA ρ AB ρ BC ρ CA > 1, and the conclusion follows.

One sees that arbitrage can only exist in one orientation of the cycle.

In case of no fees, (γ AB = γ BC = γ CA = 1), in order for the triangular cycle to be arbitragefree, we need to have ρ AB ρ BC ρ CA = 1, meaning that the product of marginal prices should be equal to 1. In the presence of fees the no-arbitrage zone is 'thicker' so to speak.

The explicit calculation shows that the arbitrage condition itself is homogeneous (invariant under a rescaling of the reserves). Next, we compute the max extractable profit and will se that the actual reserve sizes do matter.

Proposition 7 In case of the existence of a triangular arbitrage, we obtain the following:

-The optimal input a * 0 that maximises the arbitrage profit is:

max a0 (a 1 -a 0 ) = max a0 ( γ CA γ BC γ AB ρ AB ρ BC ρ CA a 0 ( γ AB [A] AB + γ BC γ AB ρ AB [B] BC + γ CA γ BC γ AB ρ AB ρ BC [C] CA )a 0 + 1 -a 0 ) a * 0 = √ γ CA γ BC γ AB ρ AB ρ BC ρ CA -1 γ AB [A] AB + γ BC γ AB ρ AB [B] BC + γ CA γ BC γ AB ρ AB ρ BC [C] CA (11)
-The optimal output a * 1 that maximises the arbitrage profit obtained from this arbitrage operation is:

a * 1 = γ CA γ BC γ AB ρ AB ρ BC ρ CA - √ γ CA γ BC γ AB ρ AB ρ BC ρ CA γ AB [A] AB + γ BC γ AB ρ AB [B] BC + γ CA γ BC γ AB ρ AB ρ BC [C] CA (12)
-The maximum profit obtained from this arbitrage operation is:

P rof it * = a * 1 -a * 0 = ( √ γ CA γ BC γ AB ρ AB ρ BC ρ CA -1) 2 γ AB [A] AB + γ BC γ AB ρ AB [B] BC + γ CA γ BC γ AB ρ AB ρ BC [C] CA (13)
The above results can be obtained by straightforward computations. There are few things worth observing. If one rescales each reserves by a coefficient λ ≥ 0, the arbitrage profit is also multiplied by the same coefficient. In other words the max arbitrage profit is homogeneous of degree 1 in the size of the reserves.

Closed formulas for max profit for Uniswap price functions give explicit lower bounds on optimal values for the corresponding original problems. One would also think that lifting solutions of the subproblems may give good initialisers to the original ones.

If there is an arbitrage, the arbitrageur can choose to start from any origin of the cycle. One may wonder whether the relative variation of the arbitrageur's portfolio depends on this choice.

Proposition 8 If the external prices of the tokens present in the cycle do not change before and after the execution, then the maximum profit is independent from the origin.

Proof: We position ourselves from an arbitrageur perspective. We suppose as above that the cycle is a triangle to simplify the notations. We also suppose that the arbitrageur possesses in her/his portfolio a sufficient quantities of tokens A, B and C, greater than a * 0 , b * 0 and c * 0 respectively. Initially, we also assume the existence of an external liquid market where the arbitrageur can exchange its tokens against a reference token R (it can be euros or a stable coin for example). We suppose the existence of arbitrage, let X be one of A, B, C, x * 0 the optimal input quantity that maximises the arbitrage profit and p X R the price of X in R. We can express the value in R of the portfolio part containing X before and after the arbitrage execution (V X 0R and V X 1R respectively), as follows:

V X R0 = x * 0 p X R0 and V X R1 = x * 1 p X R1
The percentage variation in the value of the portfolio part containing X is given by:

∆ = V X 1R -V X 0R V X 0R = x * 1 x * 0 π p X R -1
where π p X R := p X R1 /p X R0 measures the change of price of X before and after the arbitrage.

From the preceding proposition we have:

x * 1 x * 0 = γ CA γ BC γ AB ρ AB ρ BC ρ CA - √ γ CA γ BC γ AB ρ AB ρ BC ρ CA √ γ CA γ BC γ AB ρ AB ρ BC ρ CA -1
Hence we can derive explicitly the relative change in wealth of the optimal arbitrageur:

∆ = √ γ AB γ BC γ CA ρ AB ρ BC ρ CA π p X R -1 which is positive if p X R1 ≥ p X R0
, and, if prices stay the same, is indeed independent of the choice of the origin X.

Some empirical results

As of the 15th of December 2020, Uniswap contained 26139 pairs (WETH being connected to more than 12365 tokens) and more than 965 triangular cycles. We analyzed the data obtained from Etherum blockchain from block 11299400 to 11360599 (from 21/11/2020 to 30/11/2020) for the 200 most liquid pairs. We selected 11 triangular cycles that generated the maximum profits per block during this period on Uniswap: For each block we look for arbitrageable triangular cycles. Once detected, we compute the maximum profit per cycle and per block during the whole period. We plot the maximum profit (measured in USD) per block for each of the 11 selected triangular cycles. One can see that some of the optimal arbitrage profits disappear instantly (ie have a one block life time). Others last longer. A key difference with Ref. [START_REF] Ye | Cyclic arbitrage in decentralized exchange markets[END_REF] is coverage. Their data covers Uniswapv2 for a much longer larger period of time and does not look for prediction of cyclic arbitrage on restricted set of tokens, as we do, but for detection thereof. And indeed, their findings show larger actual profits than the potential ones which our small scale data experiment predicts.

Conclusions

We have represented a class of global routing problems on networks of money markets as convex optimisation problems on a suitable domain of transfer plans. We have shown that feasible problems in this class have solutions (maybe not unique). We have also built tractable subproblems which allow one to find efficiently lower bounds to the original problems.

Preliminary data analysis shows the presence of non-trivial cyclic arbitrage opportunities (see appendix), and a fortiori general ones. There is also evidence of substantial gains from non-trivial routing (Fig. 1). So there is undeniably a practical interest in solving exactly or approximately, and efficiently, these global problems. All the more so if liquidity continues to fragment in DeFi, increasing the complexity of optimal routing. Substantial liquidity migrations on DeFi's money markets have happened, and it is unclear if and when liquidity will aggregate.

One limitation of our approach is that the problems before and after executing a given plan are related but here we do not exploit that information. So there is room for designing on-line versions of the above problems of which the amortised cost could be vastly improved -compared to resolving anew the problem at each update. A minimal way to exploit that relation would be to use a former optimum as initial data for a new gradient descent on the updated problem. Also we have ignored gas fees as well as the uncertainty generated by the asynchrony inherent on blockchain-based smart contracts: the state of the world at the time the problem is solved, may be very different from the state at the time the corresponding instructions are executed. It would be interesting to include both aspects of this uncertainty (gas costs and asynchrony) in the problem for more robustness.

A The Uniswap graph

Fig. 5 proposes a view of the global Uniswap money market [START_REF] Adams | Uniswap v2 core[END_REF] restricted the top 64 ERC20 tokens and their 283 Uniswap pairs. It is worth stressing that the actual graph of interest for routing and arbitrage is far more complex as it includes many more automated market makers (sometimes with considerable liquidity) as well as other forms of decentralised exchanges.

B Some empirical results

As of the 15th of December 2020, Uniswap contained 26139 pairs (WETH being connected to more than 12365 tokens) and more than 965 triangular cycles. We analyzed the data obtained from Etherum blockchain from block 11299400 to 11360599 (from 21/11/2020 to 30/11/2020) for the 200 most liquid pairs. We selected 11 triangular cycles that generated the maximum profits per block during this period on Uniswap:

For each block we look for arbitrageable triangular cycles. Once detected, we compute the maximum profit per cycle and per block during the whole period. We plot in Figure 7 the maximum profit (measured in USD) per block for each of the 11 selected triangular cycles. One can see that some of the optimal arbitrage profits disappear instantly (ie have a one block life time). Others last longer.

Fig. 1 :

 1 Fig.1: A transfer plan using 7 distinct money markets (blue edges). Notice that a third of the original 100 ETH travels through an indirect path.

  = y; y can be computed as the composite function of x indicated by the diagram.

  (a) In red arbitrageable cycles among all existing cycles. (b) Isolated arbitrageable cycles.

Fig. 2 :

 2 Fig. 2: Example of arbitrageable cycles in Uniswap.

[

  WETH, AKRO, USDC] [WETH, DAI, HEGIC] [WETH, sUSD, BASED] [WETH, USDC, TOMOE] [WETH, DAI, USDC] [WETH, DAI, USDT] [USDT, USDC, TOMOE] [WETH, USDT, TOMOE] [WETH, USDT, USDC] [WETH, WBTC, USDC] [WETH, USDT, YFV]

  (a) [WETH, AKRO, USDC]. (b) [WETH, DAI, HEGIC]. (c) [WETH, sUSD, BASED]. (d) [WETH, USDC, TOMOE]. (e) [WETH, DAI, USDC]. (f) [WETH, DAI, USDT].

Fig. 3 :

 3 Fig. 3: Maximum profit (USD) per cycle and per block.

  (a) [USDT, USDC, TOMOE]. (b) [WETH, USDT, TOMOE]. (c) [WETH, USDT, USDC]. (d) [WETH, USDT, YFV]. (e) [WETH, WBTC, USDC].

Fig. 4 :

 4 Fig. 4: Maximum profit (USD) per cycle and per block.

Fig. 5 :

 5 Fig. 5: The top 64 ERC20s (in market cap) and their pairs on Uniswapv2: there is an edge between two nodes if there exists a Uniswap pair between them (Nov 2020).

  (a) [WETH, AKRO, USDC]. (b) [WETH, DAI, HEGIC]. (c) [WETH, sUSD, BASED]. (d) [WETH, USDC, TOMOE]. (e) [WETH, DAI, USDC]. (f) [WETH, DAI, USDT].

Fig. 6 :

 6 Fig. 6: Maximum profit (USD) per cycle and per block.

  (a) [USDT, USDC, TOMOE]. (b) [WETH, USDT, TOMOE]. (c) [WETH, USDT, USDC]. (d) [WETH, USDT, YFV]. (e) [WETH, WBTC, USDC].

Fig. 7 :

 7 Fig. 7: Maximum profit (USD) per cycle and per block.

Actually one could redefine f as f (x) = f (∞)(xf (0))/(xf (0) + f (∞)) as f (∞) = [B] the total reserve in [B], and f (0) = γ[B]/[A] the marginal price of A in B.

One could call the Uniswap price function a 'price state machine' as it defines a price function for every state of its internal reserves.

To express backtracking plans and allow sequences of swaps on e with alternating orientations, one could use the larger cone of finite sequences E → n R n + .


Extending the results obtained in the case N odd, the effect of slightly relevant perturbations of the second parafermionic field theory with the symmetry Z N , for N even, are studied. The renormalization group equations, and their infra red fixed points exhibit the same structure in both cases. In addition to the standard flow from the p-th to the (p -2)-th model, another fixed point corresponding to the (p -1)-th model is found.

Conformal field theories describe critical points of some statistical system, i.e. the fixed point of the renomalization group. In order to get some insights into the neighborhood of this critical point, one can study the effects of slightly relevant perturbations of the correponding conformal field theory, using a renormalization group approach. Parafermionic conformal field theories describe systems enjoying an extended conformal symmetry : they possess an additional cyclic symmetry Z N . While the first series of parafermionic conformal field theories [1] are well studied and applied in various domains [2,3,4], far less is known about the second parafermionic series [5,6,7,8]. These conformal theories have a richer structure than the first parafermions. For a given N ≥ 5, there are infinitetely many second parafermionic theories Z

(2) N (p), labeled by the integer p ≥ N -1. These theories are unitary and correspond to degenerate representations of the corresponding parafermionic chiral algebra. The presence of the parameter p, for a given Z N , opens a way to reliable perturbative studies. It allows in particular to study the renormalisation group flows in the space of these conformal theory models, under various perturbations. This problem has already been adressed for the case N odd [17,18], where the effect of two slightly relevant perturbations were studied. In this letter these results are generalized to the case N even.

A particular case of this problem has already been treated. The second parafermionic theory Z

(2) N (p) with N even is a particular exemple of symmetric coset on a simply laced Lie algebra, and as such its perturbation by one particular relevant operator has been studied in [15]. It is already known that the corresponding renormalization group equations describe a flow from Z

(2)

N (p) to Z (2)
N (p -2). Guided by the results obtained for the case N odd, we consider a more general perturbation, and an additional fixed point is found.

The theory Z

(2) N (p) perturbed by two appropriate fields will exhibit two different infrared (IR) fixed points :

• one of these fixed point is described by the expected Z

(2)

N (p -2)
• the other fixed point corresponds to Z

(2)

N (p -1)
The details of the second Z N parafermionic theory with N even , N ≥ 6 can be found in [8]. The main difference between the odd and even cases lies in the coset construction of these CFT [13]:

Z (2) N (p) = SO(N) k ⊗ SO(N) 2 SO(N) k+2 p = k + N -2 (1)
Depending on the parity of N, the affine Lie algebra relevant to the coset construction will be either D

r , when N = 2r is even, or B

r , when N = 2r + 1. In both cases the central charge is :

c N (p) = (N -1) 1 - N(N -2) p(p + 2) (2)
The chiral algebra is made of

N -1 parafermionic currents Ψ k , k = 1..N -1 obeying
the following fusion rules :

Ψ k × Ψ l → Ψ k+l (3)
where the Z N charges k, l, k + l are defined modulo N.

The primary operators Φ ( n| n ′ ) are labeled by two vectors n, n ′ belonging to the weight lattice of the X r Lie algebra, where X r denotes either B r or D r . Their conformal dimension is given by :

∆ ( n| n ′ ) = ((p + 2) n -p n ′ ) 2 -4 ρ 2 2p(p + 2) + B Q (4)
where B Q is the boundary term which depend on the sector of the theory, i.e. on the Z N charge of the primary field, and ρ = i ω i is the Weyl vector of the corresponding Lie algebra.

When N is even, the second parafermionic theory Z

(2) [15] proved in that general framework that the perturbation by an appropriate operator A :

N (p) is a coset of the form G k ⊗ G l /G k+l on a simply laced Lie algebra G = D r . Fateev
A = A 0 + g d 2 x A(x) (5)
is integrable, and leads for g > 0 to an IR fixed point described by

G k-l ⊗ G l /G k , provided k ≫ 1.
In terms of the GKO construction [19], this appropriate operator field A(x) correspond to the branching [(k, id) ⊗ (l, id)/(k + l, ad)], and has a conformal dimension :

∆ A = 1 - g k + l + g (6)
g being the Coxeter number of the simply laced Lie algebra G. For the second parafermionic theory Z

(2)

N (p) theories (N even), this correspond to a Z N neutral field with dimension ∆ A = 1 -(N -2)/(p + 2). If the ultraviolet CFT is described by Z (2)
N (p), then the IR fixed point will correspond to Z

(2)

N (p -2).
In this letter a more general perturbation in considered, having in mind the results obtained for the odd case. Assuming A 0 to describe the second parafermionic field theory, the action of the perturbed CFT takes the following form :

A = A 0 + α g α d 2 x Φ α (x) (7)
In order to preserve the Z N symmetry, the relevant fields Φ α have to be neutral w.r.t.

Z N . Perturbatively well controlled domain of Z

N (p) theories is that of p ≫ 1, giving a small parameter ǫ ∼ 1/p. This is similar to the original perturbative renormalization group treatment of minimal models for Virasoro algebra based conformal theory [9,10].

In this domain, i.e. for p ≫ 1, one finds, in the lower part of the Kac table of Z

A =    Ψ -1 -1 3 Φ (111|122) for N = 6 Ψ -1 -2 N Φ (111...|121...) for N ≥ 8 (9) (8)
The first one is a Z N singlet and the second is a parafermionic algebra descendant of a doublet. They both belong to the neutral sector of Z N and they are both Virasoro primaries.

Their labeling as S and A is just our shortened notations for these fields, and the field A is precisely the operator Fateev used as a perturbation.

Their conformal dimensions are given by (4) :

∆ A = 1 -(2r -2)ǫ ∆ S = 1 -2rǫ ( 10
)
where ǫ is defined as follows:

ǫ = 1 p + 2 ≃ 1 p (11)
The fields S and A have the same structure as in the case N odd [17,18]. Going back to the parameter N rather than r, their conformal dimension for both cases , N odd and even, read :

∆ A = 1 -(N -2)ǫ ∆ S = 1 -Nǫ (12)
Perturbing with the fields S and A corresponds to taking the action of the theory in the form:

A = A 0 + 2g π d 2 xS(x) + 2h π d 2 xA(x) (13)
where g and h are the corresponding coupling constants; the additional factors 2 π are added to simplify the coefficients of the renormalization group equations which follow; we recall that A 0 is assumed to be the action of the unperturbed Z The operator algebra of the fields S and A is of the form:

S(x ′ )S(x) = D 1 |x ′ -x| 4∆ S -2∆ A A(x) + ... (14)
A(x ′ )A(x) = D 2 |x ′ -x| 2∆ A A(x) + ... (15)

S(x

′ )A(x) = D 1 |x ′ -x| 2∆ 1 S(x) + ... (16)
Only the fields which are relevant for the renormalization group flows are shown explicitly. The operator algebra expansions in ( 14)-( 16) and the constants D 1 and D 2 are obtained by the same fusion procedure as for the case N odd [17,18]. From these operator product expansions one derives in a standard way the renormalization group equations for the couplings g and h:

β g = dg dξ = 2(1 -∆ S )g -4D 1 gh (17)
β h = dh dξ = 2(1 -∆ A )h -2D 1 g 2 -2D 2 h 2 (18)
These are up to (including) the first non-trivial order of the perturbations in g and h.

All this analysis is valid for ǫ ≪ 1, and the above RG flow equations are valid in the region g, h ǫ.

These equations derive from a potential:

β g = ∂ g V (19
)

β h = ∂ h V (20)
with :

V (g, h) = (1 -∆ S )g 2 + (1 -∆ A )h 2 -2/3D 2 h 3 -2D 1 hg 2 (21)
This potential plays a central role in the renormalization group flows. Let us consider the function c(g, h) defined by c(g, h) = c 0 -V (g,h)

24

: this is the c-function introduced by Zamolodchikov, which decreases along the renormalization group flows, and coincide with the central charge at any fixed point. In order to analyse the presence of IR fixed points for the renormalization group, and predict the corresponding central charges, explicit values for the operator algebra constants D 1 and D 2 are required, at least in the leading order in ǫ : they are obtained by a fusion procedure. This amounts to relate the second parafermionic theory Z

N (p) to W D r theories through the coset identity :

SO k (N) × SO 2 (N) SO k+2 (N) × SO 1 (N) × SO 1 (N) SO 2 (N) = SO k (N) × SO 1 (N) SO k+1 (N) × SO k+1 (N) × SO 1 (N) SO k+2 (N) ( 22
)
with Z

(2)

N (p) = SO k (N) × SO 2 (N) SO k+2 (N) p = k + N -2 (23)
The two coset factors in the r.h.s., as well as the additional coset factor in the l.h.s. of ( 22), correspond to W D r theories [14]. For these theories the Coulomb gas representation is known. It is made of r bosonic fields, quantized with a background charge.

The equation ( 22) can be rewritten as

Z (2) 2r (p) × WD 1 r = WD k r × WD k+1 r p = k + N -2 (24)
This equation relates the representations of the corresponding algebras. But this equation allows also to relate the conformal blocs of correlation functions. In doing so one relates the chiral (holomorphic) factors of physical operators. This later approach has been developped and analyzed in great detail in the papers [11,12], for the SU(2)

coset theories.

As it was said above, the chiral factor operators are related to the conformal bloc functions, not to the actual physical correlators. On the other hand, the coefficients of the operator algebra expansions are defined by the three point functions. These latter are factorizable, into holomorphic -antiholomorphic functions. So that, when the relation is

The Coulomb gas representation of the WD r theory allows to calculate the operator product expansion of the fields in the r.h.s. of ( 25) and ( 26). The coefficient a and b in are determined in the process, by demanding consitency between the OPE ( 14),( 15), (16) and the decompositions (25),( 26) :

a = b = 1/ √ 2.
The following values, at the leading order in ǫ, are obtained for the constants D 1 and D 2 :

D 1 = 2 r 2r -1 (27) D 2 = 2(r -1) r(2r -1) (28)
Despite the technical differences in evaluating these coefficients, in the end these results are very similar to those obtained for N odd, and in both cases it boils down to :

D 1 = √ 2 N N(N -1) , D 2 = √ 2 N -2 N(N -1) (29)
At this point the analyse of the renormalization group flows becomes similar for all N, even or odd, and the phase diagram of constants g and h is essentially the same. It contains (Fig. 1) :

• the trivial UV fixed point g * 0 = h * 0 = 0, which corresponds to the unperturbed theory Z • the standard IR fixed point on the h axis:

(g * 1 , h * 1 ) = (0, N(N -1) 2 ǫ) (30)
described by Z

N (p -2)

• two additional IR fixed points for non-vanishing values of the two couplings, with a central charge agreeing with Z

(2)

N (p -1) (g * 2 , h * 2 ) = ( 1 2 (N -2)(N -1) 2 ǫ, 1 2 N(N -1) 2 ǫ), (31)
(g * 3 , h * 3 ) = (- 1 2 (N -2)(N -1) 2 ǫ, 1 2 N(N -1) 2 ǫ) (32)
The CFTs describing the different fixed points are identified using the c function related to (21).

For all N ≥ 5, the (g, h) phase diagramm is thus the same. In addition to the expected flow from Z

(2)

N (p) to Z (2)
N (p -2), another flow to Z

N (p -1) exists. However, to realize the last flow, a fine tuning of the coupling constants g, h is required.

It is interesting to compare these results with the case N = 3 [16]. The perturbation of the parafermionic model Z 3 (p) by two slightly relevant fields has been treated in [11,12] : the RG equations admit only one IR fixed point, corresponding to the expected

Z (2)
3 (p -4). No additional fixed point is present for N = 3. Finally, the case N = 4 is not considered here, since the corresponding second parafermionic theory can be factorized into two N = 1 superconformal theories, for which slighlty relevant perturbations have already been studied [20].

All the above analysis is valid for p large, and it would be interesting to know what happens for small values of p.

December 2008 .

 2008 Renormalization group flows for the second Z N parafermionic field theory for N even. Benoit Estienne LPTHE, CNRS, UPMC Univ Paris 06 Boîte 126, 4 place Jussieu, F-75252 Paris Cedex 05 estienne@lpthe.jussieu.fr Abstract.

  parafermionic theory, two Z N neutral fields which are slightly relevant and which close by the operator algebra. They are: S = Φ (11...|31...)

  established on the level of chiral factor operators, for the holomorphic three point functions, this relation could then be easily lifted to the relation for the physical correlation functions. With the relations for the chiral factor operators one should be able to define the square roots of the physical operator algebra constants.By matching the conformal dimensions of operators on the two sides of the coset equation (24) one finds the following decompositions for the operators S and A (here we give the results for N ≥ 8):

Figure 1 :

 1 Figure 1: Renormalization group flows. Only the part g ≥ 0 is shown, since the RG flows equations and thus the phase diagramm is symmetric under g → -g.

Acknowledgements: Very useful discussions with Vl. S. Dotsenko are gratefully acknowledged.