Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Interest does not compound consistently #81

Closed
pakim249CAL opened this issue Jul 9, 2023 · 26 comments · Fixed by #222
Closed

Interest does not compound consistently #81

pakim249CAL opened this issue Jul 9, 2023 · 26 comments · Fixed by #222

Comments

@pakim249CAL
Copy link
Contributor

Currently, interest is accumulated naively with a simple multiplication of time elapsed and borrow rate. This is a simple interest model. This can be improved by using something like a binomial expansion.

@Rubilmax
Copy link
Collaborator

It would require implementing WAD-based exponentiation, right?

@pakim249CAL
Copy link
Contributor Author

Using exponentiation would be as exact as possible, but also maybe unnecessarily costly. A 3 or 4 term binomial expansion might be cheaper in gas, and provide a satisfactory precision. (AAVE does this)

@Rubilmax
Copy link
Collaborator

Rubilmax commented Jul 13, 2023

If I'm not mistaken, binomial expansion requires summing over (n choose k), where n = timestamp diff?
How can we efficiently know the value of (n choose k), given that n is unbounded?

Wouldn't it actually be more costly than calculating the exponent using recursive smart exponentiation?

EDIT: it would come down to call FixedPointMathLib.rpow(WAD + rate, dTimestamp, WAD) - WAD. Give me time to quantify the gas cost.

@Rubilmax Rubilmax self-assigned this Jul 13, 2023
@Rubilmax
Copy link
Collaborator

Quantifying the gas cost of such a change made me realized that the current hardhat tests don't randomly mine blocks so interests are never accrued and the gas cost of all interactions may be underestimated (because interests are never accrued).

So I added a step randomly mining between 0 and 100 blocks between each user interaction.

Here is the gas diff of using rpow as I suggest above:

image

We notably see a significant increase in gas cost of supply (+1k), but other interactions are roughly untouched. I wonder why. Please check out my work to see if I made a mistake.

References for my work:

@MerlinEgalite
Copy link
Contributor

I don't get why we have such difference for the supply either... You said it was random, do both tests use the same salt?

@pakim249CAL
Copy link
Contributor Author

pakim249CAL commented Jul 13, 2023

If I'm not mistaken, binomial expansion requires summing over (n choose k), where n = timestamp diff? How can we efficiently know the value of (n choose k), given that n is unbounded?

Wouldn't it actually be more costly than calculating the exponent using recursive smart exponentiation?

EDIT: it would come down to call FixedPointMathLib.rpow(WAD + rate, dTimestamp, WAD) - WAD. Give me time to quantify the gas cost.

https://github.com/aave/aave-v3-core/blob/27a6d5c83560694210849d4abf09a09dec8da388/contracts/protocol/libraries/math/MathUtils.sol#L50

Even just 2-3 terms in a binomial expansion is a big improvement on compound interest calculations. Note that the base case of 1 term is simply a linear interest model.

Exponentiation necessarily requires some recursion. From what I understand about rpow, it does exponentiation by squaring which has a O(logN).

If we are okay with some recursion, then exponentiation is fine. A partial binomial approximation has the benefit of being O(1).

I would suggest a partial taylor approximation, linked here:

https://en.wikipedia.org/wiki/Binomial_approximation#Using_Taylor_series

Because a taylor approximation as n -> infinity approaches the correct compound interest, we can infer that the error is simply the sum of the missing terms in the expansion. So we can be sure of a couple things:

  • The interest accrued in an approximation will never exceed the true compounded interest.
  • The interest accrued in an approximation will never be below a simple interest model.
  • The error disappears into insignificance after only a few terms if x (the interest rate) is small and n is not exceedingly large.

@MerlinEgalite
Copy link
Contributor

I think the error with Aave's approximation was very low but can't find the document, @MathisGD I think you did the estimation one day no?

@pakim249CAL
Copy link
Contributor Author

pakim249CAL commented Jul 20, 2023

Another option for us to consider instead of my PR is to abstract away this kind of logic to the interest rates manager itself. An IRM function could be defined with inputs of total borrow, total supply and time elapsed, and output of total accrual which the total borrow and total supply will be incremented by. This allows any complex logic regarding compounding to be externalized to outside of Blue.

@morpho-labs/research @morpho-labs/onchain

@MerlinEgalite
Copy link
Contributor

This could be good idea tbh!

The argument against I see for now:

  • It might add a warm CALL to retrieve lastUpdate[id]
  • How the interest are accrued are not in the contract anymore so it's harder to read but at the same I don't expect to have many IRMs

@Rubilmax
Copy link
Collaborator

Rubilmax commented Jul 21, 2023

It might add a warm CALL to retrieve lastUpdate[id]

To ensure full flexibility, I'd rather give this as input to the IRM instead of the time elapsed as @pakim249CAL suggested

How the interest are accrued are not in the contract anymore so it's harder to read but at the same I don't expect to have many IRMs

That's correct: instead of only having to store Blue, an integrator would also have to have access to the IRM associated to a market they interact with. But the fact that the integrator is expected to interact with a market ensures that this integrator does have the full description of the market, which includes the IRM.

I am ok this kind of solution, which is what you implemented in your PoC @pakim249CAL.

Some additional thoughts: it seems it unlocks the possibility to have an IRM similar to Compound's Comet where spread is inversed at high utilization ; whereas it was previously impossible because the interests were equally accrued to both sides of the market.

To a larger extent, having interests on both sides of the market being accrued independently unlocks the possibility to manage the fee from the IRM. It has some implications:

  • the IRM can be upgradeable (do we want to whitelist upgradeable IRM? is it desirable, re Cap the fee to a maximum value #110 (the IRM can incur an uncapped fee)?)
  • this mechanism may be redundant with the fee shares currently implemented: we could account for the difference of interests accrued on both sides of a market into a dedicated variable that the fee recipient is allowed to withdraw (the "reserve")

To be clear: having the IRM have access to runtime variables to calculate accrued interests does not necessarily imply having interests accrued independently on both sides of the market (it's just a matter of return values of the IRM: whether there's a single one or two - for each side of the market). I'm just exposing my thoughts on the design of interests accrued independently on each side of the market, because I think it's worth considering.

@MerlinEgalite
Copy link
Contributor

Returning 2 different accruals would make the fee management at Blue level a bit irrelevant. I think I'm against it due to the fact that the "fee switch" would be less clear and it would add complexity (IRM will need an owner if we want to turn fees on).

Maybe I'm missing a clear usecase for having a 2 speed accrual.

@Rubilmax
Copy link
Collaborator

Agreed that having a fee switch would require additional permissions on the IRM, under such a design ; which separates the permission of enabling LLTVs and IRMs from changing the fee. It can have a benefit though: having another entity responsible for the fee switch with higher or lesser permissions than the one managing Blue.

Maybe I'm missing a clear usecase for having a 2 speed accrual.

Generic usecase: managing a reserve
Practical example: comet's latest IRM with inversed spread at high utilization

I'm not arguing towards or against having the IRM managing the fee, I'm just exploring and highlighting properties of both solutions so we make an appropriate design decision.

@MerlinEgalite
Copy link
Contributor

having another entity responsible for the fee switch with higher or lesser permissions than the one managing Blue.

For that part I don't think it's in the best interest of Morpho blue but that could be something a market creator would like to have. Invoking @PaulFrambot on that question.

PS: your comment is duplicated

@pakim249CAL
Copy link
Contributor Author

To ensure full flexibility, I'd rather give this as input to the IRM instead of the time elapsed as @pakim249CAL suggested

IMO this is not necessarily flexibility that we would like to provide to an IRM as this opens up the possibility for IRMs to update interest multiple times per block. I think if time elapsed is zero, interest should not be accrued at all. Otherwise I am concerned that there will be MEV attack vectors.

@Rubilmax
Copy link
Collaborator

Rubilmax commented Jul 21, 2023

this opens up the possibility for IRMs to update interest multiple times per block

How does passing only the time elapsed prevent accruing interests multiple times per block? It seems we never mentioned some kind of restriction to return 0 interests in the case timeElapsed == 0?

Besides, wouldn't it be enough to not call the IRM in the case block.timestamp == lastUpdate[id]?
Can you elaborate on MEV attack vectors you think about?

For completeness, I'm also actually challenging the need for lastUpdate[id] in the IRM context (that I acknowledged to be the most flexible): why would an IRM need it?

@pakim249CAL
Copy link
Contributor Author

How does passing only the time elapsed prevent accruing interests multiple times per block? It seems we never mentioned some kind of restriction to return 0 interests in the case timeElapsed == 0?

Yes, this does seem to be something that I overlooked in my suggestion. I would probably lean towards having logic in blue to skip interest accrual if it is not the first interest accrual in the block.

Can you elaborate on MEV attack vectors you think about?

If interest accrued is > 0 on multiple transactions in the same block, this opens up the possibility for differences in transaction execution for borrows or withdrawals depending on their order. It would be favorable to the borrower/withdrawer to have their transaction included at the very end of a block in this case. I'm not entirely sure what specific attack vectors there are, but my main point is that these differences do exist and will need to be investigated if we allow multiple accruals per block.

@Rubilmax
Copy link
Collaborator

Rubilmax commented Jul 21, 2023

I see, thanks.
So is the following solution the most flexible one, without compromises:

  • only accrue interests and call IRM if block.timestamp != lastUpdate[id]
  • pass lastUpdate[id] to IRM instead of time elapsed for maximum flexibility

Or do you disagree?

I'd also like to have thoughts of the rest of the team (incl. @QGarchery & @MathisGD) on expecting the IRM to return the amount of interests accrued instead of the rate.

I believe that the discussion I had above with @MerlinEgalite on whether we should expect independent amounts of accrued interests for each side of the market led to the conclusion that it is irrelevant for this version of Blue, because IRMs are expected to be developed by us and whitelisted by the DAO ; unless we plan on having an IRM similar to Comet's.

@pakim249CAL

This comment was marked as resolved.

@MerlinEgalite

This comment was marked as resolved.

@Rubilmax

This comment was marked as spam.

@pakim249CAL

This comment was marked as resolved.

@QGarchery
Copy link
Contributor

I think that:

  • we don't want to implement an IRM similar to Comet, see this thread for why
  • it's good to enforce that the interests do not accrue between transactions in the same block, for the reasons that @pakim249CAL mentioned, and because I don't see any clear use case
  • there is a natural use case for letting the IRM adjust the returned accrued interest, which you reminded me in this issue and that I forgot when doing the review of feat: approximate compound interest #135. The use case is to let the IRM adjust when there is a long period of over-utilization. I let @MathisGD and @MattLsb give more details on this once the research on IRM is done
  • the fee should not be decided by the market creator, and so it should not depend on the IRM. I think that the fee, if there is one, should utimately be decided by Morpho Blue governance. Letting the market creator decide the fee would potentially create liquidity fragmentation, when the risk-manager fee can be taken by vaults on top without this issue

@MerlinEgalite
Copy link
Contributor

So to sum up, the proposition is to move the whole computation of accrued interest from Blue to the IRM, right?

@MathisGD
Copy link
Contributor

MathisGD commented Aug 2, 2023

The idea of delegating the accruedInterest computation to the IRM is pretty interesting. But the only reason why we would do that is to allow different interests compounding methods, since we agree that we should not allow variable spread IRMs. And to me it's completely ok that Blue chooses a method for compounding interests. I don't see any case where this hardcoded choice would make the use of Blue impossible. So we should do it. A solution like the one proposed in #135 fits me well.

@pakim249CAL
Copy link
Contributor Author

The benefits are not limited to compounding. For example, It also allows for interest rates to take into account the amount of liquidity in the market rather than just the percentage utilized. This could allow powerful use cases such as making an interest rate model that gives less APR when there is more liquidity being borrowed in absolute terms. This is because total supply and total borrow simply have higher information entropy than utilization rate, as utilization rate is just a summary statistic of the two.

But I won't push it further. We can keep the IRM as is if you like.

@MathisGD
Copy link
Contributor

MathisGD commented Aug 3, 2023

It also allows for interest rates to take into account the amount of liquidity in the market rather than just the percentage utilized.

Yes but it's completely possible also if the IRM returns a rate

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
None yet
Projects
None yet
5 participants