non-convergence in get_y() function

[hats-bug-reporter]

Github username: --
Twitter username: --
Submission hash (on-chain): 0xc4ead87ddda12153a86481aa16b19a00e11698d8d7ea450d5f3afa1ae3ccfb02
Severity: medium

Description:
Description
The get_y function is responsible for calculating the amount of a target coin (j) that can be obtained by swapping a specified amount of a source coin (i). The function uses an iterative method to refine the estimate of the target coin amount. However, there is a issue where the function may not converge within the set iteration limit of 255 times, leading to inaccurate swap calculations and this function does not take checks or implement fallback mechanism to ensure convergence within the iteration limit.

below is the get_y() function

 function get_y(
        uint256 i,
        uint256 j,
        uint256 x,
        uint256[N_COINS] memory xp_
    ) internal view returns (uint256) {
        // x in the input is converted to the same price/precision
        require((i != j) && (i < N_COINS) && (j < N_COINS), "Illegal parameter");
        uint256 amp = get_A();
        uint256 D = get_D(xp_, amp);
        uint256 c = D;
        uint256 S_;
        uint256 Ann = amp * N_COINS;

        uint256 _x;
        for (uint256 k = 0; k < N_COINS; k++) {
            if (k == i) {
                _x = x;
            } else if (k != j) {
                _x = xp_[k];
            } else {
                continue;
            }
            S_ += _x;
            c = (c * D) / (_x * N_COINS);
        }
        c = (c * D) / (Ann * N_COINS);
        uint256 b = S_ + D / Ann; // - D
        uint256 y_prev;
        uint256 y = D;

        for (uint256 m = 0; m < 255; m++) {
            y_prev = y;
            y = (y * y + c) / (2 * y + b - D);
            // Equality with the precision of 1
            if (y > y_prev) {
                if (y - y_prev <= 1) {
                    break;
                }
            } else {
                if (y_prev - y <= 1) {
                    break;
                }
            }
        }
        return y;
    }

lets understand this issue with example below

1. Proof of Concept (PoC) File

Initial Setup:

• let's say a stable swap pool with two coins: Coin A and Coin B.
• Both coins have a balance of 1000 units in the pool.

User Action:

• user wants to swap 100 units of Coin A for Coin B.

Initial Calculation:

• The function starts with an initial estimate for y (the amount of Coin B the user will receive). This estimate is based on the pool's invariant D.

Iterative Refinement:

The function enters a loop to refine the estimate of y using a specific formula. The goal is to adjust y until the change between iterations is very small (less than or equal to 1).

NOW Iteration Process:

• Iteration 1: The function calculates a new y, changing from an initial guess (say 950) to a slightly adjusted value (e.g., 940).
• Iteration 2: y is recalculated and changes from 940 to 935.
• Iteration 3: y changes from 935 to 933.
• The process continues, with each iteration making smaller adjustments to y.

Non-Convergence Scenario:

• Suppose the function is unable to find a stable y within 255 iterations.
• If the loop exits without convergence, the function might return an inaccurate y. For example, if the accurate y should be 920 but the function exits with y as 933, the user receives more Coin B than they should.

2. Revised Code File (Optional)

• Implement additional checks or fallback mechanisms to ensure convergence within the iteration limit.

[Ghoulouis]

Same type of error as #52 so we count this as a duplicate case

[batmanBinary]

hi @Ghoulouis ,Thank you for your response. I noticed that you have marked this issue as a duplicate of issue 52. I believe this issue should not be considered a duplicate, as resolving issue 52 does not address issue 99. Both issues occur in different functions, and even if 52 is resolved, the problem persists in the get_y() function. I kindly request that you reconsider the labeling of this issue.

please refer the below docs for duplicate,

https://immunefisupport.zendesk.com/hc/en-us/articles/14493487499153-Duplicate-Reports#:~:text=In%20these%20situations%2C%20there%20are%20two%20questions%20that%20we%20ask%20to%20determine%20whether%20or%20not%20the%20second%20report%20is%20a%20duplicate%3A

[batmanBinary]

@Ghoulouis ?