Walraswap: equilibrium-based decentralized exchange integrating external AMM liquidity
This is an announcement of the research article with the same title and a brief informal intro for ethresear.ch.
A classic approach to tackling MEV in decentralized exchanges on Ethereum is to enable a mechanism that receives trade orders during a block interval and settles all the swaps in a batch following a fairness criterion.
It is an old problem. I imagine that an informed reader might feel somewhat skeptical. Thoughts of this kind were expressed in 2014 in this Reddit post.
CoW Swap, UniswapX, 1inch’s Fusion, Sorella’s Angstrom, and Propellerheads’ Turbine have all tackled the problem using batch trading in one way or another.
Walraswap started in 2023 at Flashbots, independently of the previous and closely related work by Ramseyer, Goyal, Goel, and Mazières: Augmenting Batch Exchanges… and SPEEDEX. The central feature in common: we treat the DEX problem from the point of view of the theory of equilibrium for an exchange economy with n tokens. To understand equilibrium in two sentences: given a finite set of trade orders, under mild hypotheses and neglecting transaction costs, there exists a price vector —an equilibrium— at which all the orders can be executed with no deficit or surplus of any token. Some of the orders may trade nothing at equilibrium.
What’s special about Walraswap?
First note that none of the Ethereum DEXs mentioned above are based on equilibrium. Not even CoW Swap, which for many years adopted the similar but weaker property of uniform clearing prices. We can visualize the difference as follows:
equilibrium = uniform clearing prices + inclusion of all the available trade orders
The second condition is tricky for a blockchain system. Any entity responsible for submitting batches will always have the ability to censor some of the orders to manipulate the outcome and potentially make a profit. Walraswap is the result of not giving up at this point. This difficulty can be addressed through governance: introduce a DAO that elects solvers. Build a smart contract mechanism such that the only damage that a solver can inflict is to censor some orders and therefore extract some MEV. Make the mechanism transparent enough so that whenever a solver does that, it can be easily detected. This leads to the unorthodox choice of public order flow. The repeated-game setting incentivizes solvers not to censor, just as block builders do not unbundle searchers’ bundles for an immediate profit. In both cases, the actor in question would jeopardize their position by misbehaving. For more details about the proposed mechanism, read the paper’s Section 8.
The theorems and mathematical framework
The article develops a mathematical framework based on the concept of supply function and includes several results about (roughly speaking) existence, uniqueness and computation.
The main theorem (Section 6) deals with trade orders and external AMMs. (Walraswap should have internal AMMs, but these can be represented as regular trade orders.) It prescribes a solution for finding a suitable clearing price vector for the trade orders together with suitable external swaps so that the batch leaves a nonnegative surplus of each token. The external swaps execute according to the AMMs’ own pricing rules rather than at the batch’s clearing prices. The solution is expressed as an equilibrium for a specified aggregate supply function. In Section 8, I explain why I expect this particular solution to be applicable to Walraswap.
The computation of this solution (Section 7) can be written as a problem of convex optimization. This formulation suggests that efficient computation should be feasible. See also SPEEDEX, Appendix F. Related to this, there is a nuanced discussion about the graph of tokens in Section 8.
For a supply function satisfying a monotonicity condition, the set of equilibrium vectors is convex. Its structure is further clarified in Section 4. Moreover, it is shown that the net trades at equilibrium are actually unique.
Feedback very much appreciated!
Let me know what you think in the comments.