estimateIncrementalLiquidity may give incoherent result

Summary

The function to estimate the liquidity delta for the final step of a swap attempts to solve a second order equation in the case of swap with exact output.

However, the solvability is not checked and if the discriminant is negative there are no real solution. In that case, the output deltaL is a somewhat random value that does not satisfy the equation.

Vulnerability Detail

  function estimateIncrementalLiquidity(
    uint256 absDelta,
    uint256 liquidity,
    uint160 currentSqrtP,
    uint256 feeInFeeUnits,
    bool isExactInput,
    bool isToken0
  ) internal pure returns (uint256 deltaL) {
    if (isExactInput) {
      if (isToken0) {
        // deltaL = feeInFeeUnits * absDelta * currentSqrtP / 2
        deltaL = FullMath.mulDivFloor(
          currentSqrtP,
          absDelta * feeInFeeUnits,
          C.TWO_FEE_UNITS << C.RES_96
        );
      } else {
        // deltaL = feeInFeeUnits * absDelta * / (currentSqrtP * 2)
        // Because nextSqrtP = (liquidity + absDelta / currentSqrtP) * currentSqrtP / (liquidity + deltaL)
        // so we round up deltaL, to round down nextSqrtP
        deltaL = FullMath.mulDivFloor(
          C.TWO_POW_96,
          absDelta * feeInFeeUnits,
          C.TWO_FEE_UNITS * currentSqrtP
        );
      }
    } else {
      // obtain the smaller root of the quadratic equation
      // ax^2 - 2bx + c = 0 such that b > 0, and x denotes deltaL
      uint256 a = feeInFeeUnits;
      uint256 b = (C.FEE_UNITS - feeInFeeUnits) * liquidity;
      uint256 c = feeInFeeUnits * liquidity * absDelta;
      if (isToken0) {
        // a = feeInFeeUnits
        // b = (FEE_UNITS - feeInFeeUnits) * liquidity - FEE_UNITS * absDelta * currentSqrtP
        // c = feeInFeeUnits * liquidity * absDelta * currentSqrtP
        b -= FullMath.mulDivFloor(C.FEE_UNITS * absDelta, currentSqrtP, C.TWO_POW_96);
        c = FullMath.mulDivFloor(c, currentSqrtP, C.TWO_POW_96);
      } else {
        // a = feeInFeeUnits
        // b = (FEE_UNITS - feeInFeeUnits) * liquidity - FEE_UNITS * absDelta / currentSqrtP
        // c = liquidity * feeInFeeUnits * absDelta / currentSqrtP
        b -= FullMath.mulDivFloor(C.FEE_UNITS * absDelta, C.TWO_POW_96, currentSqrtP);
        c = FullMath.mulDivFloor(c, C.TWO_POW_96, currentSqrtP);
      }
      deltaL = QuadMath.getSmallerRootOfQuadEqn(a, b, c);
    }
  }

In the case isExactInput = false and isToken0, the equation to solve is a*x^2 - 2*b*x + c = 0 where:

a = fee
b = (1 - fee) * liquidity - absDelta * currentSqrtP = (1 - fee) * L - deltaX * sqrtPc
c = fee * L * deltaX * sqrtPc

There are no real solution if discriminant = (-2b)^2 - 4ac < 0, that is b² < ac:

(1 - fee)² * L² + deltaX² * sqrtPc² - 2(1 - fee) * L * deltaX * sqrtPc < fee² * L * deltaX * sqrtPc

It is not obvious that this is false under all conditions. As an example with the following approximations:

fees are really small and fees ≈ 0
L = sqrt(x*y) where x and y are the total balances of token0 and token1
deltaX = x that is the total amount of token0 is being swapped
Pc = y / x that is the scaling factor is 1

discriminant < 0 ⇔ L² + x² * Pc - 2 * L * x * sqrtPc < 0 ⇔ x*y + x² * y / x < 2 * x * sqrt(x*y) * sqrt(y/x) ⇔ 2 * x * y < 2 x * y

We can see that the two sides of the inequality can be approximated to the same value.

The left side of the inequality is growing in second order relative to L, sqrtPc, and deltaX while the right side grows literarily. There will be values of L, deltaX, sqrtPc, and fee that do not satisfy the solvability criteria, the returned value by getSmallerRootOfQuadEqn() will not correspond to the correct deltaL

  function getSmallerRootOfQuadEqn(
    uint256 a,
    uint256 b,
    uint256 c
  ) internal pure returns (uint256 smallerRoot) {
    smallerRoot = (b - sqrt(b * b - a * c)) / a;
  }

Impact

The delta liquidity to be added to the reinvest curve may not be what is expected to satisfy the invariant of the pool. Accountability of the pool will be broken which, in the long run will affect underlying token balances of the pool (LP trying to withdraw more than is available in balance) as well as price calculation. Global accounting of swap amounts will be broken over time.

Code Snippet

https://github.com/sherlock-audit/2023-07-kyber-swap/blob/main/ks-elastic-sc/contracts/libraries/QuadMath.sol#L8-L14

https://github.com/sherlock-audit/2023-07-kyber-swap/blob/main/ks-elastic-sc/contracts/libraries/SwapMath.sol#L198-L214

Tool used

Manual Review

Recommendation

Check the value of the discriminant in above calculation and revert when it is negative.

sherlock-audit / 2023-07-kyber-swap-judging

cducrest-brainbot - estimateIncrementalLiquidity may give incoherent result #68