Submitted by fnanni, also found by t0x1c
The bestArbAmountIn estimated in _bisectionSearch() can be calculated with a simple formula. Roughly estimating bestArbAmountIn instead of deriving its exact value has the following consequences:
This issue may look like a mere optimization. However, if the math presented next is correct, Id argue that this is a medium issue. Built-in arbitrage is the main feature and competitive advantage of Salty.IO. Missing arbitrage profits due to a flawed implementation should not happen.
Notation
The notation used is equal to the one found in the Salty.IO smart contracts, in particular in ArbitrageSearch.sol. For convenience, $reservesXN$ is replaced with just $XN$. For example, $A1$ should be read as $reservesA1$.
Some of the math steps were omitted to simplify this submission, but I invite you to verify the derivation of the formulas.
Max arbitrage profit formula
The arbitrage function is given by $f(a) = \frac{n\_1a}{n\_2 + ma} - a$, where:
Note that:
So, when $n\_1 > n\_2$, we know there is an arbitrage opportunity which maximizes at:
$a = \frac{\sqrt{A0*A1*B0*B1*C0\*C1} - n\_2}{m}$
Using similar methods as currently in PoolMath.sol, overflow can be avoided and the formula above can be used to execute the arbitrage feature optimally.
Missing arbitrage profits completely
So far weve seen how to improve the arbitrage calculation to properly maximize profits. Whats more interesting is that certain pools could get into states in which arbitrage opportunities are missed entirely. This should be concerning taking into account that built-in arbitrage is the main feature of the protocol and thus should always be available.
Let $a\_0>0$ be a root of the arbitrage function such that $f(a\_0)=0$ and $f(a>a\_0)<0$. The solution is given by $a\_0=\frac{n\_1-n\_2}{m}$. For simplicity, now assume that (i) the pools in the arbitrage path are balanced and (ii) a user wants to swap weth (lets call this amount $x$) for arbToken3. We are interested in finding a pool structure such that 1/128th of $x$ is greater than $a\_0$. This would mean that the protocols bisection search will test a range of $f$ which is not profitable, when there are actually values that are profitable.
The formula we get from the mentioned assumptions is:
$0\

which means that:
$C0>255\frac{B1\*A1}{A1+B0}$
These conditions are a bit restrictive, but we can still find realistic scenarios in which they hold. To test the idea, add these functions to TestArbitrageSearch.sol and then add the this test to TestArbitrageSearch.t.sol. In the tested example, the protocol misses profits at least in the range of 2-2000 ETH<>BTC swaps for the given pools state.
Consider replacing _bisectionSearch() with something similar to computeBestArbitrage(). Beware that computeBestArbitrage() is not overflow-proof.
othernet-global (Salty.IO) confirmed and commented:
Picodes (Judge) commented:
Status: Mitigated with an Error. Full details in report from zzebra83, and also included in the Mitigation Review section below.
