.md

l have previously tested this issue with a POC and it isn't valid. The system may keep empty nodes when partially redeeming and reInserting, but at the end of the function when this empty nodes are removed from the sorted list, the partially redeemed Cdp is on the correct place in the list.

// SPDX-License-Identifier: UNLICENSED
pragma solidity 0.8.17;

import "forge-std/Test.sol";
import {eBTCBaseInvariants} from "./BaseInvariants.sol";

contract checkSorting is eBTCBaseInvariants {

    address wallet = address(0xbad455);

    function setUp() public override {
        super.setUp();

        connectCoreContracts();
        connectLQTYContractsToCore();

    }

    function testSorting() public {

        uint256 grossColl = 11e18 + cdpManager.LIQUIDATOR_REWARD();

        uint256 price = priceFeedMock.fetchPrice();

        uint256 debtMCR = _utils.calculateBorrowAmount(
            11e18,
            price,
            MINIMAL_COLLATERAL_RATIO
        );

        uint256 debtColl = _utils.calculateBorrowAmount(
            11e18,
            price,
            COLLATERAL_RATIO
        );

        // Cdp with the biggest NICR and the head of the sorted list
        bytes32 first = _openTestCDP(wallet, grossColl, debtColl - 10000);
        // Cdp with second best NICR in the sorted list
        bytes32 second = _openTestCDP(wallet, grossColl, debtColl - 7500);
        // Cdp with second lowest NICR in the sorted list
        bytes32 third = _openTestCDP(wallet, grossColl, debtColl - 5000);
        // Cdp with the lowest NICR and the tail of the sorted list
        bytes32 fourth = _openTestCDP(wallet, grossColl, debtMCR);

        vm.startPrank(wallet);

        // Check the TCR is above CCR
        assert(cdpManager.getCachedTCR(price) > CCR);

        // Lower the price so fourth node can go underwater
        // and the third node is the first hint for redeeming
        priceFeedMock.setPrice(price - 1e1);

        // Extra check to ensure:
        // Fourth node is underwater ICR < MCR
        // Third node has ICR > MCR
        assert(_getCachedICR(fourth) < MINIMAL_COLLATERAL_RATIO);
        assert(_getCachedICR(third) > MINIMAL_COLLATERAL_RATIO);

        (bytes32 hint, uint256 partialNICR, , ) = hintHelpers.getRedemptionHints((debtColl), priceFeedMock.fetchPrice(), 0);

        // Check the hint is the third node in the sorted list
        // Which is the node above the underwater Cdp
        assert(hint == third);

        // Approve cdp manager to use ebtc tokens
        eBTCToken.approve(address(cdpManager), eBTCToken.balanceOf(wallet));

        // Fully redeem the third node and partially redeem from the second node.        
        cdpManager.redeemCollateral(debtColl, hint, first, fourth, partialNICR, 0, 1e18);

        // Check the third node is fully redeemed and no longer exists in the list
        assert(!sortedCdps.contains(third));
        // Check the lowest NICR node is still the fourth node
        assert(fourth == sortedCdps.getLast());
        // Check the biggest NICR node is still the first node 
        assert(first == sortedCdps.getFirst());
        // Check the second node is correctly place before the first and fourth node
        assert(second == sortedCdps.getNext(first));
        assert(second == sortedCdps.getPrev(fourth));

        // Giving wrong hints and keeping the empty nodes doesn't lead to anything
        // In the end when both reInsert happens and the empty nodes are removed from the sorted list
        // The partially redeemed nodes will still be placed correctly in the node list
        vm.stopPrank();

    }

}

@CodingNameKiki I think code-423n4/2023-10-badger-findings#173 is a valid finding. Check below POC test

function testSortingForPartialRedemption() public {
        uint256 grossColl = 11e18 + cdpManager.LIQUIDATOR_REWARD();

        uint256 price = priceFeedMock.fetchPrice();

        uint256 debtMCR = _utils.calculateBorrowAmount(11e18, price, MINIMAL_COLLATERAL_RATIO);

        uint256 debtColl = _utils.calculateBorrowAmount(11e18, price, COLLATERAL_RATIO);

        address wallet = _utils.getNextUserAddress();

        // 5 Cdps with the biggest NICR and the head of the sorted list
        bytes32 zero = _openTestCDP(wallet, grossColl, debtColl - 20000);
        bytes32 first = _openTestCDP(wallet, grossColl, debtColl - 10000);
        bytes32 second = _openTestCDP(wallet, grossColl, debtColl - 7500);
        bytes32 third = _openTestCDP(wallet, grossColl, debtColl - 5000);
        bytes32 fourth = _openTestCDP(wallet, grossColl, debtMCR);

        vm.startPrank(wallet);

        // Check the TCR is above CCR
        assert(cdpManager.getCachedTCR(price) > CCR);

        // Lower the price so last node can go underwater
        // and the third node is the first hint for redeeming
        priceFeedMock.setPrice(price - 1e1);

        // Extra check to ensure:
        // Fourth node is underwater ICR < MCR
        // Third node has ICR > MCR
        assert(_getCachedICR(fourth) < MINIMAL_COLLATERAL_RATIO);
        assert(_getCachedICR(third) > MINIMAL_COLLATERAL_RATIO);

        uint256 _redeemAmt = debtColl + 10000;
        (bytes32 hint, uint256 partialNICR, , ) = hintHelpers.getRedemptionHints(
            (_redeemAmt),
            priceFeedMock.fetchPrice(),
            0
        );

        // Check the hint is the third node in the sorted list
        // Which is the node above the underwater Cdp
        assert(hint == third);

        // Approve cdp manager to use ebtc tokens
        eBTCToken.approve(address(cdpManager), eBTCToken.balanceOf(wallet));

        // Fully redeem a CDP and partially redeem another with wrong hint pair (first, fourth)
        // correct pair should be (zero, first)
        bytes32 _upperHintForPartialReinsert = first;
        bytes32 _lowerHintForPartailReinsert = fourth;
        cdpManager.redeemCollateral(
            _redeemAmt,
            hint,
            _upperHintForPartialReinsert,
            _lowerHintForPartailReinsert,
            partialNICR,
            0,
            1e18
        );

        // Check the third node is fully redeemed and no longer exists in the list
        assert(!sortedCdps.contains(third));
        // Check the lowest NICR node is still the fourth node
        assert(fourth == sortedCdps.getLast());
        // Check the biggest NICR node is still the first node
        assert(zero == sortedCdps.getFirst());

        // Check the second node is wrongly place
        // while its correct place should be a bit upper after redemption
        assert(second == sortedCdps.getNext(first));
        assert(second == sortedCdps.getPrev(fourth));

        uint256 _zeroNICR = cdpManager.getCachedNominalICR(zero);
        uint256 _firstNICR = cdpManager.getCachedNominalICR(first);
        uint256 _secondNICR = cdpManager.getCachedNominalICR(second);
        uint256 _fourthNICR = cdpManager.getCachedNominalICR(fourth);

        console.log("zero NICR:   %s", _zeroNICR);
        console.log("first NICR:  %s", _firstNICR);
        console.log("second NICR: %s", _secondNICR);
        console.log("fourth NICR: %s", _fourthNICR);

        assert(_secondNICR > _firstNICR);
        assert(_zeroNICR > _secondNICR);
        assert(_firstNICR > _fourthNICR);
        vm.stopPrank();
    }

Nice to meet you again @rayeaster :).

You have a point here, if l understand right the empty nodes aren’t causing the issue here and the system is working correctly when reInserting. Instead the problem is that the nicr of the partial redeemed node somehow goes above the nicr of its prev node in the sorted list.

However l am a bit confused on how the NICR goes up like that?

o

Yeah, mathematically after partial redemption, the partially redeemed CDP might have a higher NICR.

In the above POC example, the output looks likes the following:

  Before redemption
  first NICR:  2154011847065201038074
  second NICR: 2154011847065190493148
  After redemption
  zero NICR:   2154011847065243217774
  second NICR: 2154011847065214219349
  first NICR:  2154011847065201038074
  fourth NICR: 1480883144857296715131