Stake precision loss / truncation after many liquidations

[RickGriff]

When a trove is created or updated, its stake is calculated by:

1. stake = _coll.mul(totalStakesSnapshot).div(totalCollateralSnapshot);

Its stake is what earns rewards it ETH and LUSD debt rewards in distributions from liquidations, i.e. in liquidations where the LUSD in the Stability Pool is less than the liquidated debt, and the liquidated collateral and debt is redistributed to all active troves.

Problem:

When a series of liquidations occur that trigger redistributions, the stakes of the liquidated troves are removed from the system, but the ETH collateral of the liquidated troves remains in the system - it just moves from ActivePool to DefaultPool. Thus totalStakes decreases but totalCollateral remains constant (ignoring gas compensation).

Over time, as liquidations occur, due to equation 1), fresh stakes become smaller and smaller for a given trove collateral size. Eventually, stakes can get so small and close in magnitude to 1e-18, such that they lose significant precision. Eventually new stakes may be truncated to 0, which breaks the proportional reward distribution mechanism.

The rate of decline of new stakes depends on how much is liquidated at each step - liquidating 10% of the system's collateral causes new stakes to decrease more quickly than liquidating 1% of the system collateral.

This may or may not be a problem depending on what numbers are "realistic" - i.e. the real liquidation throughput relative to system size.

Initial simulations suggest that stakes become very small (~1e-16) after on the order of 1e4 or 1e5 liquidations, where 10-20% of system collateral is commonly liquidated. This seems like potential cause for concern.

Possible fix:

• Represent stakes in a different numerical format, such that loss of precision or truncation to 0 is not an issue for a reasonable system lifetime, with realistic liquidation throughput.

[bingen]

Some more insights on this issue:

The problem

The main problem seems to be in this line of _redistributeDebtAndColl, called on liquidations:

dev/packages/contracts/contracts/TroveManager.sol

Line 1207 in 555b641

uint ETHRewardPerUnitStaked = ETHNumerator.div(totalStakes);

    uint ETHRewardPerUnitStaked = ETHNumerator.div(totalStakes);

when totalStakes is zero (revert) or very low (loss of precision).

It has its origin in this line of function _computeNewStake, called on trove creation or adjustment:

dev/packages/contracts/contracts/TroveManager.sol

Line 1184 in 555b641

stake = _coll.mul(totalStakesSnapshot).div(totalCollateralSnapshot);

    stake = _coll.mul(totalStakesSnapshot).div(totalCollateralSnapshot);

The main problem is that totalCollateralSnapshot keeps always growing, and it’s always >= totalStakesSnapshot. The intuition behind this is that the difference between the 2 accounts for the pending gains in collateral for older troves when a new one comes up.
Let’s distinguish 2 scenarios now:

There is at least one trove from the beginning, that remains untouched forever.

It’s not that relevant, but we can define “from the beginning” as “before the first liquidation happens”.
Then there would be little we can do, if there was a huge difference between the two amounts, it would be “real”.
It would be impossible for the first variant of the issue: totalStakes would always be at least the initial collateral of that trove.
But this is very unlikely to happen, and less unlikely to become an issue:

• Probably trove owner would be re-adjusting the trove, and on re-adjustment pending rewards are applied, so it’s essentially as if it was closed and re-opened.
• If the owner didn’t re-adjust, and assuming a high volume of liquidations, that initial trove would keep lowering the ICR and eventually be liquidated as well, before the snapshots issue becomes relevant. If there’s no big (relative) volume of liquidations, the difference between snapshots won’t probably matter either.

All the troves re-adjust frequently reacting to liquidations

To understand how this happens, let’s build up a simple scenario (code for the test reproducing it below):

• Initial Ether price is $200
• Alice opens a trove with no debt (other than gas reserve) and a small collateral amount.
• Bob opens a trove with only 0.5 ETH of collateral and no withdrawal
• Loop over the following events:
  • Whale opens a trove with only 50 ETH of collateral and withdraws 5,000 LUSD
  • Charlie opens a trove with only 0.5 ETH of collateral and no withdrawal
  • Ether price goes down to $100
  • Whale is liquidated
  • Bob is liquidated
  • Ether price goes up to $200
  • Bob re-opens the same trove as before
  • Ether price goes down to $100
  • Charlie is liquidated
  • Alice adjusts her trove so it’s at the initial state

After 9 iterations the liquidation of the whale fails because totalStakes is zero.
It could probably be simplified a little bit, but it’s what I came up with iterating tests and hopefully it’s useful to get the intuition.

Before failing, this is the state:

    Active Pool            : 51.500000000000000000
    Default Pool           : .000000000000000010
    RM:  true
    ----
    totalStakes            : .000000000000000041
    totalStakesSnapshot    : .000000000000000043
    totalCollateralSnapshot: 51.979545894703366078
    ----
    Whale stake            : .000000000000000041
    Alice stake            : .000000000000000000
    Bob stake              : .000000000000000000
    Charlie stake          : .000000000000000000
    ----
    Ratio collateral/stakes: 1208826648714031769.000000000000000000

The way I see it, the main problem is that the system behaves as if there always was a trove from the very beginning with pending rewards, i.e., like if we were in the previous scenario.

The code for that test is:

    it('try to bring totalStakes down, with an anchor, who reduces trove', async () => {
      const anchorColl = toBN(dec(5, 17))
      const anchorDebt = await borrowerOperations.LUSD_GAS_COMPENSATION()
      // anchor
      await borrowerOperations.openTrove(th._100pct, 0, accounts[2], accounts[2], { from: accounts[3], value: anchorColl })
      //await logTrove(accounts[3])
    
      // open an initial small trove
      await borrowerOperations.openTrove(th._100pct, 0, accounts[2], accounts[2], { from: accounts[2], value: dec(5, 17) })
    
      for(let i = 0; i < ITERATIONS; i++) {
        //console.log('\niteration: ', i)
        await priceFeed.setPrice(dec(200, 18))
    
        // open a big trove
        await borrowerOperations.openTrove(th._100pct, dec(5000, 18), whale, whale, { from: whale, value: dec(50, 'ether') })
        // open a new small trove
        await borrowerOperations.openTrove(th._100pct, 0, accounts[1], accounts[1], { from: accounts[1], value: dec(5, 17) })
        if (i == 0)
          await logState('init')
    
        await priceFeed.setPrice(dec(100, 18))
    
        console.log('\niteration: ', i)
        await logState('before')
    
        // liquidate whale
        await troveManager.liquidate(whale, { from: owner });
    
        // liquidate original small trove
        await troveManager.liquidate(accounts[2], { from: owner });
    
        await priceFeed.setPrice(dec(200, 18))
        // open original trove again
        await borrowerOperations.openTrove(th._100pct, 0, accounts[2], accounts[2], { from: accounts[2], value: dec(5, 17) })
    
        await priceFeed.setPrice(dec(100, 18))
        // liquidate new small trove
        await troveManager.liquidate(accounts[1], { from: owner });
    
        // force apply pending rewards
        await applyPendingRewards(accounts[3])
    
        // anchor repositions down
        await logTrove(accounts[3])
        const coll = await troveManager.getTroveColl(accounts[3])
        const debt = await troveManager.getTroveDebt(accounts[3])
        const collDiff = coll.sub(anchorColl)
        const debtDiff = debt.sub(anchorDebt).sub(toBN(1))
        await lusdToken.unprotectedMint(accounts[3], debtDiff)
        await borrowerOperations.adjustTrove(th._100pct, collDiff, debtDiff, false, ZERO_ADDRESS, ZERO_ADDRESS, { from: accounts[3] })
        await logTrove(accounts[3])
    
        await logState('after')
      }
    
      await logState('end')
    })

The solution

Still thinking about it, but somehow I think we should be able to reset totalCollateralSnapshot, so it starts counting from the oldest trove creation/adjustment event in the system.
An initial naive approach would be to keep a time ordered list of troves. The maintenance of the list would be easy:

• Each time a trove is opened it’s appended at the end.
• Each time a trove is adjusted, it’s removed from its position and appended at the end.
• Each time a trove is closed, it’s removed from the list.

Then we could implement something similar to what we do with S in StabilityPool, tracking the snapshot value for each trove.
Besides, to avoid scenario 1, with list we could make that on every trove adjustment (and maybe even on every liquidation), we get the oldest trove in the list, apply pending rewards to it and put it at the end of the list. This way we would progressively pruning the head of the list.
A lot of details to be worked out yet, plus we should make sure it keeps order and add it to the math proofs.

A simpler solution using scaling for the snapshot values is in the works by @RickGriff

[RickGriff]

Could this be a realistic problem for Liquity?

It seems not - for example, this test liquidates a constant fraction of total system collateral at each step:
#315

At 10% liquidated per step, it takes ~350 steps before fresh stakes get down to 1e-16:
https://docs.google.com/document/u/1/d/1b0Bbl1J5Z4w4oKU-JyC0JtqgXUulj2brXlK0dbcqsZ4/edit?usp=sharing

For a conservative (high) value of 10% total system collateral liquidated per month, it takes 350 / 12 = 29 years to get there.

How much would realistically be liquidated?

We've looked into some numbers for MakerDAO, and it seems very low:
https://duneanalytics.com/MatteoLeibowitz/makerdao-liquidations
By September 2020 they had only a total of $21m in liquidations, when their TVL was ~$1.4bn. So less than 2% of their total collateral had been liquidated in their system lifetime.

So we would expect a much lower liquidation fraction than 10% per month - even 1% per month seems high. Also a large proportion of liquidations will be absorbed by the Stability Pool - it is only redistributions that cause stake decline.

So it seems very unlikely that Liquity could suffer from stake precision loss / truncation within the first 50 years of operation.

[RickGriff]

Assessment from Trail of Bits (Gustavo, Slack message):

"In summary, we believe that issue #310 is not an immediate concern during the lifetime of the Liquity contracts, unless there some "black swan event" (e.g. something causing ether to crash a very large number of times, forcing an abnormally high amounts of liquidations per year). So, instead of making modifications in the code, we recommend to monitor the precision loss and have a emergency migration procedure ready in the unlikely case of need it."

So I'm closing this now.