The reserves used for arbitrage profit testing are incorrect

[c4-bot-10]

Lines of code

https://github.com/othernet-global/salty-io/blob/53feaeb0d335bd33803f98db022871b48b3f2454/src/arbitrage/ArbitrageSearch.sol#L137-L146

Vulnerability details

Comments

The original implementation used _bisectionSearch() to figure out the best arbitrage opportunity, which is inefficient and may completely miss arbitrage profits.

Mitigation

commit a54656d commit 53feaeb The best arbitrage value can be calculated by a simple formula. The mitigation used the suggested formula to find out the arbitrage opportunity. If necessary, all reserves will be right shifted before calculation to prevent overflow. Once the arbitrage value exists, all reserves will be left shifted to verify the result.

New issue

The result of arbitrage verification could be incorrect due to precision loss caused by shifting.

Links to affected code

https://github.com/othernet-global/salty-io/blob/53feaeb0d335bd33803f98db022871b48b3f2454/src/arbitrage/ArbitrageSearch.sol#L137-L146

Vulnerability details

The mitigation didn't utilize the original reserves to verify if arbitrage profit exists. If a shift occurred, all reserves could be less than the original values after right-shifting then left-shifting, resulting in an incorrect result.

Tools Used

Manual review

Recommended Mitigation Steps

Use the original reserve values for arbitrage verification:

    function _bestArbitrageIn( uint256 A0, uint256 A1, uint256 B0, uint256 B1, uint256 C0, uint256 C1 ) public pure returns (uint256 bestArbAmountIn)
        {
+               (uint a0, uint a1, uint b0, uint b1, uint c0, uint c1) = (A0, A1, B0, B1, C0, C1);
        // When actual swaps along the arbitrage path are executed - they can fail with insufficient reserves
        if ( A0 <= PoolUtils.DUST || A1 <= PoolUtils.DUST || B0 <= PoolUtils.DUST || B1 <= PoolUtils.DUST || C0 <= PoolUtils.DUST || C1 <= PoolUtils.DUST )
            return 0;

        // This can be unchecked as the actual arbitrage that is performed when this is non-zero is checked and duplicates the check for profitability.
        // testArbitrageMethodsLarge() checks for proper behavior with extremely large reserves as well.
        unchecked
            {
            // Original derivation: https://github.com/code-423n4/2024-01-salty-findings/issues/419
            // uint256 n0 = A0 * B0 * C0;
            //  uint256 n1 = A1 * B1 * C1;
            //  if (n1 <= n0) return 0;
            //
            //  uint256 m = A1 * B1 + C0 * B0 + C0 * A1;
            //  uint256 z = Math.sqrt(A0 * C1);
            //  z *= Math.sqrt(A1 * B0);
            //  z *= Math.sqrt(B1 * C0);
            //  bestArbAmountIn = (z - n0) / m;

            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;
            if ( bestArbAmountIn == 0 )
                return 0;

            // Convert back to normal scaling
            bestArbAmountIn = bestArbAmountIn << shift;

            // Needed for arbitrage profit testing
-           A0 = A0 << shift;
-           A1 = A1 << shift;
-           B0 = B0 << shift;
-           B1 = B1 << shift;
-           C0 = C0 << shift;
-           C1 = C1 << shift;

-           uint256 amountOut = (A1 * bestArbAmountIn) / (A0 + bestArbAmountIn);
-           amountOut = (B1 * amountOut) / (B0 + amountOut);
-           amountOut = (C1 * amountOut) / (C0 + amountOut);
+           uint256 amountOut = (a1 * bestArbAmountIn) / (a0 + bestArbAmountIn);
+           amountOut = (b1 * amountOut) / (b0 + amountOut);
+           amountOut = (c1 * amountOut) / (c0 + amountOut);

            // Make sure bestArbAmountIn arbitrage is actually profitable
            if ( amountOut < bestArbAmountIn )
                return 0;
            }
        }

Assessed type

Math

[c4-judge]

Picodes marked the issue as satisfactory

[c4-judge]

Picodes marked the issue as duplicate of #101

[genesiscrew]

Hi @Picodes! Thanks for your continous work!

Just thought i would add that a few points here given tnat this issue was labeled as a duplicate of #101 :

Although both issues revolve around the bit shifting mechanism, this issue claims that due to shifting up and then down, the function might return an incorrect value due to precision loss. I'll have to also add I'm not convinced of the severity of this issue, a POC would have helped bolster the claims made.

Mine describes another issue altogether, where the function can return 0 via conditional check in line 120(n1 <= n0), due to bit shifting 'imbalanced' pools. It also provides a working POC.

The mitigation required for both issues will also be completely different. Indeed, the sponsor confirmed and mitigated my issue specifically. This issue is yet to be mitigated if any.

Happy to hear your thoughts on this!

[Picodes]

@genesiscrew isn't #101 issue about precision loss as well? Both issues revolve around the fact that the last shifted bits of the reserves are forgotten.

When the values of any of the shifted variables are small after shifting, the precision loss is maximal and we are at risk of either reverting as shown here, finding an incorrect value in bestArbAmountIn, or even finding 0 in the extreme cases as in #101.

As far as mitigation is concerned, unless I am missing something the current mitigation proposed by the sponsor does not mitigate fully the precision loss but tries to minimize it so the issues may still occur.

Note that in both cases, the impact should remain minimal unless one of the tokens as way less decimals than the other

[genesiscrew]

Yes you are correct. After some thoought it seems the essence of both issues is the same. Thanks!