Appendix: Token conservation per order (aka Local token conservation)

Among other things, CIP-11 introduced a rather technical constraint, named "local token conservation", or "token conservation per order". In order to explain what this constraint is about, let's first look at the "token conservation per token" constraint, or what we call global token conservation; the fact that no token is created or destroyed during a settlement. We will now showcase why this global notion of conservation is oblivious about what happens in certain subgraphs, and turns out not to be sufficient.
To see this, consider the following example in which there are two user orders: user a sells 1 unit of token x for at least 1 unit of token y; user b sells 1 unit of token z for at least 1 unit of token y. A solver uses an external liquidity source to buy 2 units of token y against 1 unit of token x, and a different liquidity source to buy 1 unit of token y against 1 unit of token z.
A solution that returns 1 unit of token y to user a and 2 units of token y to user b satisfies both token conservation per token and has uniform prices. Nonetheless, at an intuitive level, it is unfair to user a: their unit of token x was used to generate 2 units of token y, but the solution allocates them only 1 unit of token y. The goal is to specify a constraint that rules out these situations.
To start, suppose that we have a solution that consists of a single trading cycle C of k trades
o1,o2,,oko_1, o_2, \ldots, o_k
. More precisely, trade
buys token
and sells token
, trade
buys token
and sells token
, and so on, and finally, trade
buys token
and sells token
, thus closing the cycle. We now define the exchange rate of a trade
in the standard way
as the ratio between quantity sold and quantity bought. Then by the "token conservation per token" constraint, it is easy to deduce that
p(C)oiCp(oi)=p(o1)p(o2)p(ok)=1.p(C) \coloneqq \prod_{o_i \in C} p(o_i) = p(o_1) \cdot p(o_2) \cdot \ldots \cdot p(o_k)= 1.
Inspired by the above equation that holds for a single cycle, we now generalize this in the case where a user trade is part of many trading cycles in the proposed solution. More specifically, we denote by
the set of all trading cycles containing the order o in a candidate solution. We require that:
CC(o)λCp(C)=1,\sum_{C \in \mathcal{C}(o)} \lambda_C \cdot p(C) = 1,
λC0\lambda_C \geq 0
is a non-negative number that is well-defined for each cycle C, such that
CC(o)λC=1\sum_{C \in \mathcal{C}(o)} \lambda_C= 1
. The above condition can 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 the weights
which intuitively should capture the extent to which a given trade is utilized in different trading cycles. To do so, we first define the execution graph G(o) of a user trade o as the union of all cycles containing the trade o, where we use the following convention: we have a node for each of the traded tokens, and for each order
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 remove the edge corresponding to trade o from the graph and call this updated graph the execution graph G(o) of trade o. Claim: It is easy to see that this graph is directed and acyclic (DAG). Correction: We clarify that the above claim, originally made in CIP-11, turns out to not always hold. So, the test mentioned here can only be applied in cases where indeed the execution graph is a DAG. From now on, we will assume this is the case.
Given this directed and acyclic graph G(o), we now associate each edge
α=(t,t)\alpha = (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)}
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
. Thus, we can now naturally define the
terms in the equation above as follows:
λCαCλα,\lambda_C \coloneqq \prod_{\alpha \in C} \lambda_\alpha,
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
CC(o)λCr(C)=1,\sum_{C \in \mathcal{C}(o)} \lambda_C \cdot r(C) = 1,
where the terms are defined as above. More details about the "token conservation per order" constraint and 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 in the slashing of a solver.