The Batch Auction Optimization Problem

In this section, we describe all the different components of the optimization problem that needs to be solved within each batch.
Tokens
The problem considers a set of tokens that users want to buy or sell in their orders. The key quantity describing each token t is its price p(t), which is one of the main variables to be determined in the optimization problem.
User Orders
We now turn to the type of orders that a user can submit to the Cow Protocol. The set of user orders is denoted as O, and a user order o is described by a tuple o=⟨bo,so,fo,co,To,Uo⟩o = \langle b_o, s_o, f_o, c_o, T_o, U_o \rangleo=⟨bo​,so​,fo​,co​,To​,Uo​⟩
, where:
​bo∈N>0b_o \in \mathbb{N}_{> 0}bo​∈N>0​
 denotes the token (e.g., ETH) the user wants to buy (extract out of the market).
​so∈N>0s_o \in \mathbb{N}_{> 0}so​∈N>0​
 denotes the token (e.g., COW) the user wants to sell (insert into the market).
​fo∈N≥0f_o \in \mathbb{N}_{\geq 0}fo​∈N≥0​
 specifies the fee that is paid for the service and the transaction costs, denominated in the sell token. In principle, the fee can depend on the user order, the traded amount etc., but for simplicity, we will treat it as a predetermined fee that might be different for each order.
​co∈N≥0c_o \in \mathbb{N}_{\geq 0}co​∈N≥0​
 is a fixed cost for settling the user's trade, denominated in some predefined reference token (ETH is usually selected as the reference token).
​To:R≥02→{true,false}T_o: \mathbb{R}_{\geq 0}^2 \to \{\mathtt{true}, \mathtt{false}\}To​:R≥02​→{true,false}
 is the trading predicate, that determines the set of buy (x) and sell (y) amounts for which the user is willing to participate in the market; __ if __ To(x,y)=trueT_o(x,y) = \mathtt{true}To​(x,y)=true
, then this means that the user is willing to sell y amount of the sell token and buy x amount of the buy token.
​Uo:R≥02→RU_o: \mathbb{R}_{\geq 0}^2 \to \mathbb{R}Uo​:R≥02​→R
 is the user's utility function. Utility measures how "happy" a user is with a particular buy (x) and sell (y) amount, given that To(x,y)=trueT_o(x,y) = \mathtt{true}To​(x,y)=true
; the larger the utility, the happier the user is with the trade. We note that if the utility is equal to zero, then the user is indifferent to the trade, so such a trade might or might not be executed.
We will now describe the different types of trading predicates that are allowed. We clarify that we always set T(x,y)≔falseT(x,y) \coloneqq \mathtt{false}T(x,y):=false
 if x = 0, and so from now on we only discuss the case where x > 0.
Limit Sell Orders
A limit sell order is specified by a maximum sell amount Y > 0, which indicates the maximum amount that the user is willing to sell. Moreover, there is a limit price π\piπ
, that corresponds to the worst-case exchange rate that the user is willing to settle for. More formally, if x denotes the (proposed) buy amount and y denotes the (proposed) sell amount of the order, the trading predicate is defined as
​T(x,y)≔(yx=π    and    y<Y)    or    (yx≤π    and    y=Y).T(x,y) \coloneqq \left(\frac{y}{x} = \pi\;\;\textrm{and}\;\; y < Y\right) \;\;\textrm{or}\;\; \left(\frac{y}{x} \leq \pi\;\;\textrm{and}\;\; y = Y\right).T(x,y):=(xy​=πandy<Y)or(xy​≤πandy=Y).
​
In words, a limit sell order is eligible for execution in two cases_:_ it either is fully executed and the limit price is respected, or it is partially executed and is traded at its limit price.
A limit sell order is allowed to be Fill-or-Kill; in such a case the order is not allowed to be partially filled. For this case, the trading predicate becomes
​T(x,y)≔(yx≤π    and    y=Y).T(x,y) \coloneqq \left(\frac{y}{x} \leq\pi \;\;\textrm{and}\;\; y = Y\right).T(x,y):=(xy​≤πandy=Y).
​
Given that the order is eligible for execution, the utility of the order is defined as the value of the difference between the amount of tokens the trader receives and the minimum amount that they were expecting to receive. Formally,
​U(x,y)≔(x−yπ)⋅p(b),U(x,y) \coloneqq \left(x - \frac{y}{\pi} \right) \cdot p(b),U(x,y):=(x−πy​)⋅p(b),
​
where p(b) denotes the price of the buy token.
Notice that currently all the sell orders submitted via the CoW Swap UI are Fill-or-Kill orders that are specified by the maximum sell amount Y and the minimum buy amount X. More precisely, when a user asks to sell Y amount of the sell token, then they get a promise that the buy amount will be at least some quantity X. Thus, the limit price π\piπ
 is only implicitly specified as π\piπ
 = Y/X. Nevertheless, it is more convenient to refer to this limit price π\piπ
 instead of the minimum buy amount X, as this naturally corresponds to the worst-case exchange rate that a user is willing to accept, and also allows us to generalize the concepts to partially fillable orders (i.e., orders that are not Fill-or-Kill).
Limit Buy Orders
A limit buy order is specified by a maximum buy amount X > 0, which indicates the maximum amount that the user is willing to buy. Much like a limit sell order, there is a limit price π\piπ
, that corresponds to the worst-case exchange rate that the user is willing to settle for. With x denoting the buy amount and y denoting the sell amount of the order, the trading predicate is defined as follows:
​T(x,y)≔(yx=π    and    x<X)    or    (yx≤π    and    x=X).T(x,y) \coloneqq \left(\frac{y}{x} =\pi \;\;\textrm{and}\;\; x < X\right) \;\; \textrm{or}\;\; \left(\frac{y}{x} \leq\pi \;\;\textrm{and}\;\; x = X\right).T(x,y):=(xy​=πandx<X)or(xy​≤πandx=X).
​
Again, limit buy orders are allowed to be Fill-or-Kill, meaning the trading predicate is restricted to
​T(x,y)≔(yx≤π    and    x=X).T(x,y) \coloneqq \left(\frac{y}{x} \leq \pi \;\;\textrm{and}\;\; x = X\right).T(x,y):=(xy​≤πandx=X).
​
If the conditions are met, the order can be executed. In both cases, the utility is then defined as the value of the difference between the amount of tokens that the trader would have been ready to spend and the amount they actually spend, or:
​U(x,y)=(xπ−y)⋅p(s),U(x,y) = (x \pi - y) \cdot p(s),U(x,y)=(xπ−y)⋅p(s),
​
where p(s) denotes the price of the sell token.
Liquidity Orders
A liquidity order looks identical to a user order, except that its utility is always equal to zero. This is because a liquidity order only cares about the execution of the trade and is oblivious to any (potential) surplus they might get. The set of liquidity order is denoted with L.
Automated Marker Makers (AMMs)
The set of AMMs that participate in a batch is denoted as M. An AMM is again described by a tuple, similar to user orders, and is determined by the trading predicate T in which the sell (y) and buy (x) amounts are related by an arbitrary concave function G:R≥0→R≥0G: \mathbb{R}_{\geq 0} \to \mathbb{R}_{\geq 0}G:R≥0​→R≥0​
, i.e, we have
​T(x,y)≔(y=G(x)).T(x,y) \coloneqq \left(y = G(x)\right).T(x,y):=(y=G(x)).
​
One example of such a function G is the constant-product ("Uniswap") invariant
​G(x)=xryx+rx,G(x) = \frac{xr_{y}}{x+r_{x}},G(x)=x+rx​xry​​,
​
where rx,ry∈R+r_{x},r_{y}\in\mathbb{R}^{+}rx​,ry​∈R+
 are the internal reserves of the token being bought and sold, respectively, by the AMM. Similar to a liquidity order, the utility function of an AMM is always equal to zero.
Objective Function
The key goal of a solver is to find solutions that maximize the utility of the users. However, in the objective, we also add a fee component for the service provided, and subtract costs that the transaction execution on the blockchain is expected to incur. Hence, our objective reads
maximize (total utility) + (total fees paid) - (total execution cost).
For a more formal description, we introduce an indicator variable z per (user/liquidity) order and AMM, that indicates whether the order is executed [z(o) = 1], or not [z(o) = 0]. Thus, the objective function is the following:
maximize ∑o∈OUo(x(o),y(o))⋅z(o)+∑o∈O∪Lfo⋅z(o)−∑α∈O∪L∪Mcα⋅z(α),\sum_{o \in O} U_o(x(o), y(o)) \cdot z(o) + \sum_{o \in O \cup L} f_o \cdot z(o) - \sum_{\alpha \in O \cup L \cup M} c_\alpha \cdot z(\alpha),∑o∈O​Uo​(x(o),y(o))⋅z(o)+∑o∈O∪L​fo​⋅z(o)−∑α∈O∪L∪M​cα​⋅z(α),
​
where the underlying variables to be determined are the indicator z-variables, the buy (x) and sell (y) amounts of each order, as well as the prices of the tokens.
Note: We stress here that in the computation of the utility of each executed order in the objective, we do not use the computed price of the traded token but an external price provided as part of the input. In other words, for an executed limit sell order, the utility is equal to

U(x,y)≔(x−yπ)⋅ext_price(b),U(x,y) \coloneqq \left(x - \frac{y}{\pi} \right) \cdot ext\_price(b),U(x,y):=(x−πy​)⋅ext_price(b),


where ext_price(b) is provided as part of the input as an estimate of the price of token b. Similarly, for an executed limit buy order, the utility is equal to

U(x,y)=(xπ−y)⋅ext_price(s),U(x,y) = (x \pi - y) \cdot ext\_price(s),U(x,y)=(xπ−y)⋅ext_price(s),


where, again, ext_price(s) is provided as part of the input as an estimate of the price of token s.

There are two reasons for using these external prices and not the computed prices in the solution. The first is that it simplifies the objective function (i.e., an order's utility is linear in the traded amounts and not quadratic in the amount and price), and, second, it ignores solutions that scale up prices of certain tokens in order to create "fake amounts of surplus".

Similarly, the terms of the objective that correspond to the total fees paid and execution costs are also computed with respect to these external prices.

As a final comment, these external prices can be treated as given weights that create a weighted sum of different terms in the objective function, and allow for a simple and well-defined maximization objective function.
Ranking of solutions
We now describe how different solutions are ranked. Given a candidate solution, in order to compute its objective value, we need to compute the total utility it generates for the orders it executed, the total fees collected and its execution cost. It is straightforward to compute the first two terms, as these only depend on the proposed clearing price vector the solution proposes (see "Uniform clearing prices" part of the "Constraints" section) and the orders selected for execution.

Regarding the computation of the execution cost, this is done as follows. The proposed solution is first simulated on the latest block. If the simulation succeeds, then the gas units needed, as computed by the simulation, will be used in order to evaluate the execution cost term of the objective function.

The above is done for every proposed solution, and among those that pass simulation, the one that maximizes the objective function is selected.
Constraints
Here, we briefly discuss all the constraints that must be satisfied so that a solution can be considered valid. Systematic violation of these rules might lead to penalizing, or even slashing (if the DAO decides so).
Trading predicate: An order or an AMM can only be executed/used if the proposed trading amounts satisfy its trading predicate.
Uniform clearing prices: The proposed trading amounts of all user orders must follow the same prices. I.e., if a user order is executed with a buy amount x and a sell amount y, the equation x⋅p(b)=y⋅p(s)x \cdot p(b) = y \cdot p(s)x⋅p(b)=y⋅p(s)
 must hold, where p(b) denotes the price of the buy token and p(s) denotes the price of the sell token. The above equation can also be rewritten as yx=p(b)p(s)\frac{y}{x} = \frac{p(b)}{p(s)}xy​=p(s)p(b)​
, which explicitly states that the exchange rate that a user order perceives is determined by the token prices (and thus, all users trading on the same token pair perceive the same exchange rate).

We stress here that the clearing price vector is a key component of a reported solution, as the way the smart contract computes the traded amounts is via this vector. For example, for a Fill-or-Kill sell order that sells a y amount of token A for some amount of token B, and assuming that its trading predicate is satisfied, then the executed buy amount of the order is computed as follows:

buy amount = y⋅p(A)/p(B)y \cdot p(A) / p(B)y⋅p(A)/p(B)
.

A similar computation is done in the case of buy orders.\
Token conservation per token: No token amounts can be created or destroyed. In other words, for every token, the total amount sold must be equal to the total amount bought of this token.

We stress here that settlements that end up violating token conservation are usually penalized in a soft way. More precisely, due to blockchain volatility, it can happen that AMM interactions do not return the exact amount that was expected. In most of these cases, this is indeed unintended (from a solver's perspective), and usually the deviations are not that large, so the protocol has chosen a soft penalty for such deviations, in the following form. A proper accounting per settled batch is done, and slippage (in both directions) is taken into account, added up (with the appropriate sign), and if the result ends up being negative (i.e., the solver "owing" money to the protocol), that amount is charged as penalty to the solver.

We also note that, although the protocol's approach is to not slash solvers that unintentionally might violate this constraint, systematic and intentional violations of it might result in flagging of a solver. In other words, the protocol and the DAO expects that solvers will report traded amounts as truthfully as they can.

A particular instance of intentionally violating the token conservation per token constraint with the goal to win more batches is the so-called pennying strategy, which has been thoroughly discussed here, and which has been banned (see CIP-13).
Maximum size of solution: The total number of executed orders and AMMs cannot exceed a certain number within each batch due to limitations regarding the size of a block on the blockchain.
Token conservation per order: One additional set of constraints that we impose follows as a generalization of the token conservation per token constraint, and is discussed in the next subsection.
Social consensus rules: These are "non-written" behavioral rules that solvers should follow, as voted in CIP-11. We now provide some examples of them:
Provision of unfair solutions. Uniform clearing prices computed by solvers should be in line (or even better) than what the users would get elsewhere. This becomes particularly relevant for solutions where CoW's happen, i.e., when some volume is settled as part of a CoW and not by routing through an AMM.
Inflation of the objective function. Using tokens for the sole purpose of inflating the objective value or maximizing the reward is forbidden (e.g., by creating fake tokens, or wash-trading with real tokens).
Illegal use of internal buffers. The internal buffers may only be used to replace legitimate AMM interactions available to the general public for the purpose of saving transaction costs. We discuss internal buffers in more detail in a subsequent section (here).
Failure to report correct transacted values for encoded transactions. Solvers may choose to include encoded transactions in their solution, by providing relevant calldata, but when doing so they must also truthfully specify the amounts transferred by each encoded transaction. This is required in order to verify token conservation constraints, and can be checked retrospectively. Again, this is discussed in more detail here.
Other malicious behavior. Malicious solver behavior is not limited to the above examples. Slashing can still happen for other reasons where there is intentional harm caused to the user and/or the protocol at the discretion of the CoW DAO.
Token conservation per order
The uniform clearing prices constraint ensures that all users will see the same price for each traded token, which is a very desirable property so as to avoid cases where a user is envious of another user because of the better exchange rate they got. However, only enforcing it to user orders might lead to some undesirable solutions. More precisely, it has been observed that, although allowing liquidity/AMM orders to have different exchange rates (compared to the ones imposed by the price vector) can be beneficial, as more surplus can be extracted for the users in many cases, there is also the danger that surplus shifts from one trading cycle to another one. This can be considered unfair, since an order that was necessary for generating such surplus might not end up "receiving" it.
The "token conservation per token" constraint ensures that no token is created or destroyed. However, this, in a way, is a global notion of conservation that is oblivious about what happens in certain subgraphs, and turns out not to be sufficient. As noted in the previous paragraph, at a high level, a desired notion of conservation would ensure that for any user order o, no external tokens "enter" or "exit" the trading cycles that contain the order o. For this reason, we introduce an additional constraint, which we call "token conservation per order" constraint, that prohibits solutions that violate this notion of conservation.
We start with a simple example, in order to motivate this new constraint, which is arguably the most technical among all of our constraints. For that, suppose that we have a solution that consists of a single trading cycle C that contains k orders α1,α2,…,αk\alpha_1, \alpha_2, \ldots, \alpha_kα1​,α2​,…,αk​
. More precisely, order α1\alpha_1α1​
 buys token t1t_1t1​
 and sells token t2t_2t2​
, order α2\alpha_2α2​
 buys token t2t_2t2​
and sells token t3t_3t3​
, and so on, and finally, order tkt_ktk​
 buys token tkt_ktk​
 and sells token t1t_1t1​
, thus closing the cycle. If we now define the exchange rate of an orderα\alphaα
 in the standard way, i.e., r(α)=as(α)ab(α)r(\alpha)= \frac{a_s(\alpha)}{a_b(\alpha)}r(α)=ab​(α)as​(α)​
, then by the "token conservation per token" constraint, it is easy to deduce that
​r(C)≔∏α∈Cr(α)=r(α1)⋅r(α2)⋅…⋅r(αk)=1.r(C) \coloneqq \prod_{\alpha \in C} r(\alpha) = r(\alpha_1) \cdot r(\alpha_2) \cdot \ldots \cdot r(\alpha_k)= 1.r(C):=∏α∈C​r(α)=r(α1​)⋅r(α2​)⋅…⋅r(αk​)=1.
​
Inspired by the above equation that holds for a single cycle, we now generalize this in the case where a user order is part of many trading cycles in the proposed solution. More specifically, for a user order o, if C(o)\mathcal{C}(o)C(o)
 denotes the set of all trading cycles containing the order o in a candidate solution, then, in order for that solution to be considered feasible, we require that the following condition holds:
​∑C∈C(o)λC⋅r(C)=1,\sum_{C \in \mathcal{C}(o)} \lambda_C \cdot r(C) = 1,∑C∈C(o)​λC​⋅r(C)=1,
​
where λC≥0\lambda_C \geq 0λC​≥0
 is a non-negative number that is well-defined for each cycle C, such that ∑C∈C(o)λC=1\sum_{C \in \mathcal{C}(o)} \lambda_C= 1∑C∈C(o)​λC​=1
. In words, we require that a certain convex combination of the products of exchange rates over all cycles that contain a user order o is equal to 1_._ This can also be viewed as an average-case version of the simpler equation that holds for a single cycle and is described above.
The only thing remaining to do is define these λ\lambdaλ
 terms that appear in the equation above. For that, we first define the execution graph G(o) of a user order o as the union of all cycles containing the order o, where we use the following convention: we have a node for each of the traded tokens, and for each order α\alphaα
 that buys token u and sells token v, we add a directed edge (u, v) from u to v. Thus, we end up with a directed graph G(o). To simplify things, we also remove the edge corresponding to order o from the graph, and call this updated graph the execution graph G(o) of order o. It is easy to see that this graph is directed and acyclic (DAG).
Given this directed and acyclic graph G(o), we now associate each edge α=(t,t′)\alpha = (t, t')α=(t,t′)
of the graph with the weight
​λα≔ab(α)∑β∈G(o):  tb(β)=tab(β)\lambda_\alpha \coloneqq \frac{a_b(\alpha)}{\sum_{\beta \in G(o):\; t_b(\beta) = t} a_b(\beta)}λα​:=∑β∈G(o):tb​(β)=t​ab​(β)ab​(α)​
.
Intuitively, this weight represents how token t is "distributed" in the orders that are buying token t, within the graph G(o).
We also define λo=1\lambda_o = 1λo​=1
 . Thus, we can now naturally define the λ\lambdaλ
 terms in the equation above as follows:
​λC≔∏α∈Cλα,\lambda_C \coloneqq \prod_{\alpha \in C} \lambda_\alpha,λC​:=∏α∈C​λα​,
​
for every cycle containing order o. It is now straightforward to prove that these terms now indeed sum up to 1.
To summarize, for a proposed solution, we require that for each executed user order o, we must have
​∑C∈C(o)λC⋅r(C)=1,\sum_{C \in \mathcal{C}(o)} \lambda_C \cdot r(C) = 1,∑C∈C(o)​λC​⋅r(C)=1,
​
where the terms are defined as above.

More details about the "token conservation per order" constraint, as well as a straightforward pseudocode implementation of a test that checks the constraint, can be found here.
We stress here that the constraint is not enforced when ranking solutions, but can be checked retrospectively, by inspecting the settlement onchain. Systematic and non-trivial violations of the constraint can result to slashing of a solver.
Introduction
Input: Batch auction instances
Last modified 5mo ago