MEV Makes Everyone Happy under Greedy Sequencing Rule

We first argue that it suffices for the miner to execute at most one transaction. This is because if miner executes two transactions with the same type (say $\texttt{Sell}(\mathcal{X},q_{1})$ and $\texttt{Sell}(\mathcal{X},q_{2})$), then it is equivalent to execute $\texttt{Sell}(\mathcal{X},q_{1}+q_{2})$; if miner executes two transactions with different types (say $\texttt{Sell}(\mathcal{X},q_{1})$ and $\texttt{Sell}(\mathcal{Y},q_{2})$), then it is better to replace them by one single transaction since miner can avoid additional cost of trading fees.

So next we consider the case where the miner executes one of its transactions TX. Suppose that $\textsf{TX}=\texttt{Sell}(\mathcal{X},q)$, then miner’s profit is

We show below that when $x^{*}\geq L_{x}$, $U(\mathcal{X},q)\leq 0$ for all $q\geq 0$.

Symmetrically we can define $U(\mathcal{Y},q)$ when miner executes $\texttt{Sell}(\mathcal{Y},q)$ and conclude that when $x^{*}\leq R_{x}$, $U(\mathcal{Y},q)\leq 0$ for all $q\geq 0$. This finishes the proof that when $x^{*}\in[L_{x},R_{x}]$, miners cannot obtain positive profits.

Then we consider what is an optimal attack when $x^{*}\not\in[L_{x},R_{x}]$. Suppose that $x^{*}<L_{x}$, then by previous argument, the miner should not execute $\texttt{Sell}(\mathcal{Y},\cdot)$ (as $x^{*}<L_{x}\leq R_{x}$). So let’s focus on the case where the miner executes $\texttt{Sell}(\mathcal{X},q)$.

Letting $x^{\prime}=x^{*}+(1-f)q$, note that

where $\left(\int_{x^{*}}^{L_{x}}r(x)dx\right)\cdot p_{y}-(L_{x}-x^{*})/(1-f)\cdot p_{x}$ is the profits that miner can get by executing $\texttt{Sell}(\mathcal{X},(L_{x}-x^{*})/(1-f))$ as states in the lemma. Next we show that

for all $x^{\prime}$.

Note that

So we have

which is a decreasing function as $r(x^{\prime})$ is decreasing. Since $g^{\prime}(L_{x})=0$, we have the maximal value of $g$ is at $L_{x}$, which is 0.

This finishes the proof. ∎

Fix arbitrary sequence of (users’ and miner’s) transactions $(\textsf{TX}^{\tau(1)},\cdots,\textsf{TX}^{\tau(k)})$, where $\textsf{TX}^{\tau(i)}$ is a user’s transaction if $\tau(i)\in[n]$ and it is the miner’s transaction otherwise. Let $s_{i}=(x_{i},y_{i})$ be the state after executing $\textsf{TX}^{\tau(i)}$. Without loss of generality, we assume that $\textsf{TX}^{\tau(i)}=\texttt{Sell}(\mathcal{X},\cdot)$ if and only if $x_{i-1}\leq x_{0}$ and $\textsf{TX}^{\tau(i)}=\texttt{Sell}(\mathcal{Y},\cdot)$ if and only if $y_{i-1}\leq y_{0}$ for all $i\in\{2,\cdots,k\}$. To see it, suppose that for $k^{\prime}<k$ we have $\textsf{TX}^{\tau(i)}=\texttt{Sell}(\mathcal{X},\cdot)$ and $x_{i-1}>x_{0}$ for all $i\in\{k^{\prime}+1,\cdots,k\}$. Then by Lemma 1, we know that miner’s profit obtained from $\textsf{TX}^{\tau(k^{\prime}+1)},\cdots\textsf{TX}^{\tau(k)}$ is at most 0 (and possibly negative). It means the miner can always choose not to execute these transactions and the profit is as good as before.

We will inductively show that after executing the first $i$ transactions, the miner’s profit $U_{i}\leq V_{i}\coloneqq\sum_{j\in[i],\tau(j)\in[n]}\texttt{AP}(s_{0},\textsf{TX}^{\tau(j)})$. This will imply that after executing all $k$ transactions, miner’s profit is upper bounded by $\sum_{i\in[n]}\texttt{AP}(s_{0},\textsf{TX}^{i})$.

We define $\phi_{i}$ as follows:

We will show that $(U_{i}+\phi_{i})-(U_{i-1}+\phi_{i-1})\leq V_{i}-V_{i-1}=\texttt{AP}(s_{0},\textsf{TX}^{\tau(i)})$ for all $i\in[k]$, which will imply our desired statement $U_{i}\leq V_{i}$ as $\phi_{i}\geq 0$ for all $i\in[k]$. (Here we define $\texttt{AP}(s_{0},\textsf{TX}^{\tau(i)})=0$ if it is a miner’s transaction.)

The basis of the induction is trivial as $U_{0}+\phi_{0}=0$. For the induction step, let’s consider arbitrary $i\in[k]$.

Case 1: $\textsf{TX}^{\tau(i)}$ is a user’s transaction. Then we have $U_{i}=U_{i-1}$. So it suffices for us to show $\phi_{i}-\phi_{i-1}\leq\texttt{AP}(s_{0},\textsf{TX}^{\tau(i)})$. Suppose that $\textsf{TX}^{\tau(i)}=\texttt{Sell}(\mathcal{X},q)$. Then it must be the case $x_{i-1}<=x_{0}$ due to the greedy sequencing rule. (The other case $\textsf{TX}^{\tau(i)}=\texttt{Sell}(\mathcal{Y},q)$ will be symmetric.) If $x_{i}\leq x_{0}$, then we have that $\phi$ in fact didn’t increase, which means $\phi_{i}-\phi_{i-1}\leq 0\leq\texttt{AP}(s_{0},\textsf{TX}^{\tau(i)})$. If $x_{i}>x_{0}$, then since $x_{i-1}\leq x_{0}$, we have $x_{i}\leq\max\left\{x_{0}+(1-f)q,R_{x}\right\}$. So that $\phi_{i}\leq\texttt{AP}(s_{0},\textsf{TX}^{\tau(i)})$, concluding the first case.

Case 2: $\textsf{TX}^{\tau(i)}$ is a miner’s transaction. Then we have $V_{i}=V_{i-1}$. So it suffices for us to show $U_{i}-U_{i-1}+\phi_{i}-\phi_{i-1}\leq 0$. Suppose that $\textsf{TX}^{\tau(i)}=\texttt{Sell}(\mathcal{X},q)$, then it must be the case $x_{i-1}<=x_{0}$ due to the greedy sequencing rule. (Again, the other case $\textsf{TX}^{\tau(i)}=\texttt{Sell}(\mathcal{Y},q)$ will be symmetric.)

If $x_{i-1}\leq x_{i}\leq L_{x}$, then we have in fact $U_{i}-U_{i-1}+\phi_{i}-\phi_{i-1}=0$ since $U_{i}-U_{i-1}=\phi_{i-1}-\phi_{i}=-(x_{i}-x_{i-1})/(1-f)\cdot p_{x}+\left(F_{y}(x_{i-1})-F_{y}(x_{i})\right)\cdot p_{y}.$

Now, let’s consider the case $L_{x}\leq x_{i}$. To simplify the analysis, we consider an intermediate state $s^{\prime}$ with $U^{\prime}$ and $\phi^{\prime}$. If $x_{i-1}\geq L_{x}$, then we just set $s^{\prime}=s_{i-1}$ with $U^{\prime}=U_{i-1}$ and $\phi^{\prime}=\phi_{i-1}$. If $x_{i-1}<L_{x}$, we split $\textsf{TX}^{\tau(i)}$ into two transactions: $\textsf{TX}^{\prime}=\texttt{Sell}(\mathcal{X},(L_{x}-x_{i-1})/(1-f))$ and $\textsf{TX}^{\prime\prime}=\texttt{Sell}(\mathcal{X},(x_{i}-L_{x})/(1-f))$, and we define $s^{\prime}$, $U^{\prime}$ and $\phi^{\prime}$ as that after executing $\textsf{TX}^{\prime}$.

Note that we have $U^{\prime}-U_{i-1}=\phi_{i-1}-\phi^{\prime}$. So we only need to show $U_{i}-U^{\prime}\leq\phi^{\prime}-\phi_{i}$. Note that in fact $\phi^{\prime}=0$.

If $x_{i}\leq R_{x}$, then $\phi_{i}=\phi^{\prime}=0$. In addition, by Lemma 1, we know that $U_{i}-U^{\prime}\leq 0$. So we conclude $U_{i}-U^{\prime}\leq\phi^{\prime}-\phi_{i}$ as desired.

The last possibility is that $x_{i}>R_{x}$, where we have

Moreover, by Lemma 1, we know that $U_{i}-U^{\prime}\leq(R_{x}-x_{i})/(1-f)\cdot p_{x}+\left(F_{y}(R_{x})-F_{y}(x_{i})\right)\cdot p_{y}<-\phi_{i}$.

This finishes the proof. ∎

We first show that the sequence given by Algorithm 1 satisfies the greedy sequencing rule. Note that after executing each user’s transaction $\textsf{TX}^{\tau(i)}$, we always execute a miner’s transaction with the opposite direction, shown between line 1 and 1. Besides, at the end of $i$-th iteration, we have the state $s_{2i}=s_{0}$ (we use $2i$ because we execute two transactions in each iteration). So our sequence satisfies the greedy sequencing rule. Furthermore, during the $i$-th iteration, we obtain exactly $\texttt{AP}(s_{0},\textsf{TX}^{\tau(i)})$ profits by executing the transaction on line 1 or 1. Then the optimality follows from the same upper bound provided by Lemma 2. ∎

The NP-membership is easy. Given any strategy, we can efficiently simulate the execution of the sequence of transactions and check if the final profit is $M(s_{0},\{\textsf{TX}^{i}\}_{i\in[n]})$ or not.

For the NP-hardness, we reduce the Partition problem to our problem. Recall that the instance of the partition problem contains $n$ positive integers and ask if it can be partitioned into two subsets $S_{1}$ and $S_{2}$ such that the sum of numbers in $S_{1}$ equals that in $S_{2}$.

Suppose we are given arbitrary $n$ positive integers $\{a_{1},\cdots,a_{n}\}$. Let $t$ be half of the sum of these integers, i.e., $\frac{1}{2}\sum_{i=1}^{n}a_{i}$. Without loss of generality, we assume that $a_{i}\leq t$ for all $i\in[n]$ otherwise the answer to the decision problem will directly be “no”.

We first construct a CFMM $A$ and initial state $s_{0}$. Concretely, we can consider the constant curve of $A$ as $F(x,y):xy=k$, and our goal is to choose parameters such that $x_{0}-L_{x}=(1-f)t$. Precisely, we know that $L_{x}=\sqrt{1-f}x_{0}$, since $r(L_{x})=\frac{1}{1-f}r(x_{0})$. This means $x_{0}-L_{x}=(1-\sqrt{1-f})x_{0}$. So choosing $x_{0}=\frac{1-f}{1-\sqrt{1-f}}t$ would suffice.

Next, we construct users’ transactions. For each integer $a_{i}$, we construct $\textsf{TX}^{i}=\texttt{Sell}(\mathcal{X},a_{i})$. Clearly, we have $\texttt{AP}(s_{0},\textsf{TX}^{i})=0$ as $(1-f)a_{i}\leq(1-f)t=x_{0}-L_{x}\leq R_{x}-x_{0}$. Then we construct two $\texttt{Sell}(\mathcal{Y},\cdot)$ transactions. Precisely, we construct $\textsf{TX}^{n+1}=\textsf{TX}^{n+2}=\texttt{Sell}(\mathcal{Y},q^{*})$ where $q^{*}$ is large enough such that $F_{x}(y_{0}+(1-f)q^{*})<L_{x}$. Then we know $\texttt{AP}(s_{0},\textsf{TX}^{n+1})=\texttt{AP}(s_{0},\textsf{TX}^{n+2})>0$. This finishes the construction. And we know $M(s_{0},\{\textsf{TX}^{i}\}_{i\in[n+2]})=2\texttt{AP}(s_{0},\textsf{TX}^{n+1})$.

Finally, we argue that there exists a strategy obtaining profits $M(s_{0},\{\textsf{TX}^{i}\}_{i\in[n+2]})$ if and only if there exists a subset $S\subseteq[n]$ such that the sum of the numbers in $S$ equal $t$. And this will conclude the theorem.

One direction is easy: if there exists $S\subseteq[n]$ such that the sum of the numbers in $S$ equal $t$, then we execute transactions as follows:

1. 1.

   Execute user’s transaction $\textsf{TX}^{n+1}$; Execute miner’s transaction $\texttt{Sell}(\mathcal{X},\frac{L_{x}-F_{x}\left(y_{0}+(1-f)q^{*}\right)}{1-f})$;

2. 2.

   Execute $\textsf{TX}^{i}$ for all $i\in S$;

3. 3.

   Repeat item (1) except replacing $\textsf{TX}^{n+1}$ by $\textsf{TX}^{n+2}$.

It is easy to verify that this sequence satisfies the greedy sequencing rule, and the miner can obtain $M(s_{0},\{\textsf{TX}^{i}\}_{i\in[n+2]})$.

For the other direction, we show that the sequence of transactions constructed above is essentially the only way to obtain $M(s_{0},\{\textsf{TX}^{i}\}_{i\in[n+2]})$. So a miner can obtain $M(s_{0},\{\textsf{TX}^{i}\}_{i\in[n+2]})$ only if the answer to the given Partition problem is “yes”.

We adopt a proof scheme similar to that of Lemma 2. Fix a sequence of (users’ and miner’s) transactions $(\textsf{TX}^{\tau(1)},\cdots,\textsf{TX}^{\tau(k)})$ such that miner’s profit $U=2\texttt{AP}(s_{0},\textsf{TX}^{n+1})$. Recall that in the proof of Lemma 2, we defined $\phi_{i}$ and showed $U_{i}+\phi_{i}-(U_{i-1}+\phi_{i-1})\leq\texttt{AP}(s_{0},\textsf{TX}^{i})$ for all $i\in[k]$. Since $U_{k}=2\texttt{AP}(s_{0},\textsf{TX}^{n+1})$ at the end, it must be the case $U_{i}+\phi_{i}=V_{i}$ for all $i\in[k]$ and $\phi_{k}=0$. As a result, the sequence of transactions must satisfy that

• •

  The miner does not lose profit for any transaction; otherwise the loss of the profit is strictly larger than the gain of the $\phi$ function, and this will result in $U_{i}+\phi_{i}<V_{i}$ for some $i$.

• •

  There are $i_{1}\neq i_{2}\in[k]$ such that $\phi_{i_{1}}=\phi_{i_{2}}=\texttt{AP}(s_{0},\textsf{TX}^{n+1})$. This means when execute $\textsf{TX}^{n+1}$ and $\textsf{TX}^{n+2}$, the corresponding state must be $(x_{0},y_{0})$.

To achieve both items simultaneously, it must be $(x_{i_{1}-1},y_{i_{1}-1})=(x_{0},y_{0})$ and $\textsf{TX}^{n+1}$ is executed as $\textsf{TX}^{\tau(i_{1})}$. To get the first $\texttt{AP}(s_{0},\textsf{TX}^{n+1})$ profit, miner executes $\texttt{Sell}(\mathcal{X},\frac{L_{x}-F_{x}\left(y_{0}+(1-f)q^{*}\right)}{1-f})$ in the $(i_{1}+1)$-th iteration. To make sure that $(x_{i_{2}-1},y_{i_{2}-1})=(x_{0},y_{0})$ (and $\textsf{TX}^{n+2}$ is executed as $\textsf{TX}^{\tau(i_{2})}$) while the miner does not loss any profit in this process, we must use users’ transactions to change the state from $x_{i_{1}}=L_{x}$ to $x_{i_{2}-1}=x_{0}$, which means we need a subset $S$ of users’ transactions such that the sum of numbers in $S$ is exactly $t$.

This finishes the proof. ∎