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_ko1​,o2​,…,ok​
. More precisely, trade o1o_1o1​
 buys token t1t_1t1​
 and sells token t2t_2t2​
, trade o2o_2o2​
 buys token t2t_2t2​
and sells token t3t_3t3​
, and so on, and finally, trade oko_kok​
 buys token tkt_ktk​
 and sells token t1t_1t1​
, thus closing the cycle. We now define the exchange rate of a trade oio_ioi​
 in the standard way p(oi)p(o_i)p(oi​)
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)≔∏oi∈Cp(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.p(C):=∏oi​∈C​p(oi​)=p(o1​)⋅p(o2​)⋅…⋅p(ok​)=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 C(o)\mathcal{C}(o)C(o)
  the set of all trading cycles containing the order o in a candidate solution. We require that:
​∑C∈C(o)λC⋅p(C)=1,\sum_{C \in \mathcal{C}(o)} \lambda_C \cdot p(C) = 1,∑C∈C(o)​λC​⋅p(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
. 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 λC\lambda_CλC​
 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 ooo
 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')α=(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 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.
Last modified 1mo ago