Description

Liquidswap provides peripheral modules for interacting with the protocol. The liquidswap::stable_curve module exposes helper functions for computing exchange amounts.

Liquidity pools for correlated coins utilize a different curve. Specifically, if the reserves of two coins are x and y, then it maintains that c = x ^ 3 y + y ^ 3 x must increase across exchanges. To help compute quantities, the internal function stable_curve::get_y is used to find y given x and c.

fun get_y(x0: U256, xy: U256, y: U256): U256 {
    let i = 0;

    let one_u256 = u256::from_u128(1);

    while (i < 255) {
        let k = f(x0, y);
        let _dy = u256::zero();
        let cmp = u256::compare(&k, &xy);
        if (cmp == 1) {
            _dy = u256::add(
                u256::div(
                    u256::sub(xy, k),
                    d(x0, y),
                ),
                one_u256    // Round up
            );
            y = u256::add(y, _dy);
        } else {
            _dy = u256::div(
                u256::sub(k, xy),
                d(x0, y),
            );
            y = u256::sub(y, _dy);
        };
        cmp = u256::compare(&_dy, &one_u256);
        if (cmp == 0 || cmp == 1) {
            return y
        };

        i = i + 1;
    };

    y
}

This implementation uses Newton's method to iteratively find a y value given an initial guess. However, the criteria the function uses to find when it converges will result in slightly unstable outputs: The result of get_y differs slightly on different starting conditions. Consider the following:

get_y(u256::from_u128(138), u256::from_u128(200000000), u256::from_u128(40));
get_y(u256::from_u128(138), u256::from_u128(200000000), u256::from_u128(50));
get_y(u256::from_u128(138), u256::from_u128(200000000), u256::from_u128(60));

While the first and third return 63, the second returns 64. The true result should be approximately 62.98; the initial condition of 50 results in an incorrect result, even if we suppose get_y should round upwards.

Impact

The incorrect get_y values lead to slightly incorrect calculations by coin_in and coin_out. The goal of coin_out is to return the amount of output a user should receive given reserve states and an input quantity. However, the value it returns can be too low:

coin_out(47, 100000000, 100000000, 10000, 15674);

This call returns 47, but a user could actually extract 48 coins from the pool while still increasing the liquidity pool value.

Recommendations

First, the desired behavior of get_y should be better documented. At the moment, it is unclear whether it should round up or round down. Based on this decision, the update and stopping criteria for get_y should be adjusted. Currently, if the adjustment for y is less than or equal to one in a given iteration, the function assumes it has converged and returns.

Remediation

Pontem Network fixed this issue in commit 0b01ed6↗