Suboptimal arbitrage implementation

[c4-bot-8]

Lines of code

https://github.com/code-423n4/2024-01-salty/blob/53516c2cdfdfacb662cdea6417c52f23c94d5b5b/src/arbitrage/ArbitrageSearch.sol#L101-L136

Vulnerability details

Impact

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:

1. In some scenarios, arbitrage profits are missed completely.
2. In most cases, arbitrage profits are not optimal.
3. It could be profitable to sandwich-attack certain swaps. The pre-transaction would push the pools into scenario 1., then the post-transaction would recover the investment + arbitrage, capturing the arbitrage profits that were meant for the DAO.

This issue may look like a mere optimization. However, if the math presented next is correct, I'd 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.

Proof of Concept

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:

• $$a$$ (a.k.a. bestArbAmountIn) is the amount of WETH to be "sold" for arbToken2 in the first step of the arbitrage path weth -> arbToken2 -> arbToken3 -> weth.
• $$n_1 = C1 B1 A1$$
• $$n_2 = C0 B0 A0$$
• $$m = C0 B0 + C0 A1 + B1 * A1$$

Note that:

1. $$f(0) = 0$$
2. $$f(\inf) = -\inf$$
3. $$max{f(a)}_{a>0} > 0$$ only if $$n_1 > n_2$$. If this is not obvious at first sight, derive $$f$$ and find its roots for $$a>0$$.

So, when $$n_1 > n_2$$, we know there is an arbitrage opportunity which maximizes at:

$$a = \frac{\sqrt{A0A1B0B1C0*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 we've seen how to improve the arbitrage calculation to properly maximize profits. What's 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 (let's 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 protocol's 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<x<\frac{C1}{127B1A1}(C0B0 + C0A1 - 255B1A1)$$

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.

Tools Used

Manual Review

Recommended Mitigation Steps

Consider replacing _bisectionSearch() with something similar to computeBestArbitrage(). Beware that computeBestArbitrage() is not overflow-proof.

Assessed type

Other

[c4-judge]

Picodes marked the issue as primary issue

[c4-sponsor]

othernet-global (sponsor) confirmed

[othernet-global]

Works great! Thank you!

I modified the calculations to reduce overflow risk:

        uint256 n0 = A0 * B0 * C0;
        uint256 n1 = A1 * B1 * C1;
        if (n1 <= n0)
            return 0;

        uint256 m = A1 * ( B1 + C0 ) + C0 * B0;
        uint256 z = PoolMath._sqrt( (n0 / m) * (n1 / m) );

        bestArbAmountIn = z - n0 / m;

[othernet-global]

Added an MSB shift to prevent overflow: https://github.com/othernet-global/salty-io/commit/a54656dd18135ca57eef7c4bf615b7cdff2613a7 https://github.com/othernet-global/salty-io/commit/53feaeb0d335bd33803f98db022871b48b3f2454

    uint256 maximumMSB = _maximumReservesMSB( A0, A1, B0, B1, C0, C1 );

        // Assumes the largest number should use no more than 80 bits.
        // Multiplying three 80 bit numbers will yield 240 bits - within the 256 bit limit.
        uint256 shift = 0;
        if ( maximumMSB > 80 )
            {
            shift = maximumMSB - 80;

            A0 = A0 >> shift;
            A1 = A1 >> shift;
            B0 = B0 >> shift;
            B1 = B1 >> shift;
            C0 = C0 >> shift;
            C1 = C1 >> shift;
            }

        // Each variable will use less than 80 bits
        uint256 n0 = A0 * B0 * C0;
        uint256 n1 = A1 * B1 * C1;

        if (n1 <= n0)
            return 0;

        uint256 m = A1 *  B1 + C0 * ( B0 + A1 );

        // Calculating n0 * n1 directly would overflow under some situations.
        // Multiply the sqrt's instead - effectively keeping the max size the same
        uint256 z = Math.sqrt(n0) * Math.sqrt(n1);

        bestArbAmountIn = ( z - n0 ) / m;

[c4-judge]

Picodes marked the issue as satisfactory

[Picodes]

Considering the value-added for the sponsor and the fact that this report:

• is actually saving funds for the protocol
• shows that a functionality is in some specific case broken (which we know as the bisection search isn't exact) could be fixed relatively easily

I think Med severity is appropriate.

[c4-judge]

Picodes marked the issue as selected for report