Caching Approach for AToken Snapshotting about flexible-voting HOT 8 CLOSED

Really great writeup!

Based on my understanding from the writeup, the Governor-initiated Checkpoints (GIC) feels like the clear choice. Overriding the propose function to also call aToken.snapshotReserves() is a very simple change to the governor, and since we're already upgrading the governor this doesn't feel like an issue.

The Aave-initiated checkpoints (AIC) feel like a suitable workaround only if we can't upgrade the governor for some reason:

• GIC: very small governor change, no increase in cost of regular protocol usage, cheap voting since it's O(1) lookups to get voting weight.
• AIC: significant AToken (or Pool?) changes to hook on every method that changes the relevant reserve params, which (1) increases costs of regular protocol usage, (2) makes voting more expensive since you have to binary search a huge array, and (3) the larger change surface and binary search code makes errors/bugs more likely

Only the governor would be able to call this function [aToken.snapshotReserves()].

I think you could even make this permissionless. Since the snapshot is a mapping from block number to data, no binary search is needed when retrieving data. So even if someone takes a snapshot every block it has no effect on lookup costs. Given that, feels like we may as well make it permissionless, because other interesting use may cases come out of enabling these snapshots.

Edit: after discussing + per below comments, I misunderstood some intent/goals and now agree AToken approach is the right move

from flexible-voting.

do i understand correctly that this route removes the necessity to keep our own snapshots in the AToken contract? at AToken:castVote time, might we simply look up the Token:ERC20Votes snapshot and call our own getNormalizedIncome on it, or am i missing something? let me know if that's not clear, and i'll rearticulate with better references

nvm!

from flexible-voting.

Here's what I'm thinking for how this could be done.

We need checkpointed, rebased balances

The issue is that we need to know the rebased token balance for users at arbitrary points in time -- specifically: at proposal snapshots. This is difficult because the rate at which aTokens rebase is constantly changing based upon token supply/demand within the Aave pool.

The aToken's balanceOf function is implemented as follows:

    super.balanceOf(user).rayMul(POOL.getReserveNormalizedIncome(_underlyingAsset));

And the pool's getReserveNormalizedIncome function is implemented like this:

    uint40 timestamp = reserve.lastUpdateTimestamp;
    if (timestamp == block.timestamp) return reserve.liquidityIndex;
    return MathUtils.calculateLinearInterest(reserve.currentLiquidityRate, timestamp).rayMul(
      reserve.liquidityIndex
    );

Putting these together, the rebasing token balance depends on 4 pieces of information:

• balanceOf[user]
• reserve.lastUpdateTimestamp
• reserve.liquidityIndex
• reserve.currentLiquidityRate

Reserve data call be pulled with this pool function.

In an ideal scenario -- in which the reserve data was checkpointed in the same block as the proposal was made -- it'd be possible to calculate the rebased balance with just two checkpointed values:

• the raw, stored value of balanceOf(user), accessed like this
• the value of POOL.getReserveNormalizedIncome(token)

Otherwise, we need all of the data above -- since the rate will have changed since the snapshot.

So, how do we checkpoint the information we need?

We are already checkpointing balances in the naive implementation, and I think it works fine for what we need. So I'll ignore that here.

I see two opportunities for checkpointing the reserve data we need:

1. Governor-initiated. The governor contract reaches into the atoken to assist with checkpointing.
2. Aave-initiated. Aave pool interactions trigger checkpoints to be written.

More about each approach is below.

Governor-initiated Checkpoints

For this approach we would modify Governor.propose() so that each time a proposal is created, the governor calls a function on the aToken, e.g. aToken.snapshotReserves(). Only the governor would be able to call this function.

The function would make the atoken take a snapshot of the reserve-normalized income at the proposal timestamp. This would have the benefit of keeping snapshots to a bare minimum -- both in terms of number of snapshots per proposal (just 1) as well as the amount of information captured (just the reserveNormalizedIncome). It would also make snapshot retrieval trivial -- no binary search needed, just retrieve the reserve-normalized income with the proposal snapshot block number as the key.

The main drawback to this appraoch is that it involves more modifications to the governance system: a governor that knows about the atoken. But since we're already assuming a governor upgrade to GovernorCountingFractional, that doesn't seem like so much of a stretch.

Aave-initiated Checkpoints

As mentioned above, reserve data is constantly changing. It changes any time assets are deposited, borrowed, withdrawn, etc. Since all of these operations ultimately require the pool to call into the aToken (e.g. to mint, burn, transfer balances) we have pre-built hooks into the events we care about.

We could simply write a new checkpoint each time the relevant events occur. Since there's no guarantee that we'll be checkpointing on the same blocks as proposals are issued, we'd need to checkpoint the all of reserve data mentioned above (i.e. not just reserveNormalizedIncome).
This could obviously get expensive quickly.

The benefit of this approach is that it would not require an additional complexity in the governor.

The downsides are increased gas costs (we'd be writing lots of checkpoints, which would mean binary searching across lots of checkpoints) and complexity -- it'd likely be tricky to figure out how to checkpoint the relevant data for any operation that potentially changes aToken rebasing rates.

from flexible-voting.

I don't disagree with any of the technical points made here. In a vacuum, for one specific DAO that wanted this functionality, modifying the Governor would be a logical choice. Unfortunately, though, given the actual context of what we're building, I don't think we can go this route.

The pitch to DAOs adopting Flexible Governance isn't, "you should adopt Flexible Governance because you get this one specific use case." Instead, the pitch is, "By adopting a Governor with this one simple additional abstraction, you give developers the ability to build all kinds of new use cases that can integrate with your governance. And by the way, we've already built some of those for you, such as AToken voting."

The changes made to the Governor, therefore, need to be minimal, use-case agnostic, and stable. Hopefully sometime soon, we'll have the core Flexible Governor audited and used in production for one or more real DAOs. That version of the Governor needs to remain basically unchanged, and use cases that we (and others) build need to simply integrate with it. In effect, we're trying to bootstrap a new standard that will be widely adopted by 3rd party devs, DAOs, and tooling.

One thing worth considering is whether the abstraction we have in place is in fact sufficient, given that we're encountering this challenge. We should think more carefully about this, but I'm inclined to say it is. Aave is a weird beast because of its dynamic balance, and that is specifically what is creating the challenge here. When we think of other possible use cases we're considering (other DeFi protocols, L2 bridge voting, shielded voting, cheaper off chain voting, etc...) none of them would have this problem, and a simple balance checkpoint would do the job.

I think the path forward is to implement the Aave-initiated approach and then compare it to our eventual implementation of #9 to understand which set of tradeoffs work best for AToken style voting.

from flexible-voting.

We chatted about this yesterday. Taking some notes here so we don't forget what was discussed.

One thing worth considering is whether the abstraction we have in place is in fact sufficient, given that we're encountering this challenge.

We considered whether there might be a more general need for a post-proposal hook -- one which we should just add to the governor.

Ultimately we decided against going this route since it adds non-trivial security risks. E.g. if the governor had a whitelist of addresses to call post-proposal, it would be possible for one of those addresses to become malicious and "return bomb" the governor, i.e. returning a ton of unnecessary data (which solidity will copy to memory, making the governor run out of gas). Further, assuming the governor would require a successful proposal in order to remove such a malicious post-proposal address from its whitelist, that address could effectively brick the entire governance system forever.

There are ways around these problems. But the fact that the problems exist just confirms that it's a non-trivial change which would need to be weighed very carefully.

I think the path forward is to implement the Aave-initiated approach

We also discussed ways that we could potentially reduce the cost of the Aave-initiated approach. One option was to use fixed-sized checkpoint arrays with a ring buffer. This would bound the cost of binary searches with the downside that we could end up deleting checkpoints that we care about.

from flexible-voting.

I dug into Aave a bit more to figure out where/when it updates the relevant reserve values that we need to have checkpointed, then looked into whether or not there are subsequent aToken calls that would allow us to checkpoint the values at those times.

Functions we need to add checkpointing to are any that changes these values:

• raw aToken.balanceOf(user) (i.e. the stored value)
• reserve.lastUpdateTimestamp
• reserve.currentLiquidityRate
• reserve.liquidityIndex

So I looked at them one at a time.

aToken.balanceOf(user)

This gets updated by the aToken itself, in the following functions:

• _mintScaled
• _burnScaled
• _transfer

Updating these functions to checkpoint the balance is trivial because they are all aToken functions and we're overriding the aToken contract.

reserve.lastUpdateTimestamp

The reserve.lastUpdateTimestamp gets written by ReserveLogic.updateState which calls ReserveLogic._updateIndexes. The former gets called in:

• BridgeLogic.executeBackUnbacked (❌ NO aToken hook is called)
• BridgeLogic.executeMintUnbacked (calls atoken.mint after updating reserve)
• SupplyLogic.executeWithdraw (calls atoken.burn after updating reserve)
• SupplyLogic.executeSupply (calls atoken.mint after updating reserve)
• FlashLoanLogic.executeFlashLoan (calls handleRepayment after updating reserve)
• FlashLoanLogic.executeFlashLoanSimple (calls _handleRepayment after updating reserve)
• LiquidationLogic.executeLiquidationCall (calls _handleRepayment, need to clarify which aToken this is for...)
• BorrowLogic.executeBorrow (❌ only SOMETIMES calls transferUnderlyingTo)
• BorrowLogic.executeRepay (calls burn or handleRepayment)
• BorrowLogic.executeSwapBorrowRateMode (❌ NO aToken hook)

reserve.currentLiquidityRate

The reserve's currentLiquidityRate gets updated in ReserveLogic.updateInterestRates() from the values calculated in IReserveInterestRateStrategy.calculateInterestRates()

updateInterestRates is called by:

• BridgeLogic.executeBackUnbacked (❌ NO aToken hook is called)
• BridgeLogic.executeMintUnbacked (calls atoken.mint after updating rates)
• LiquidationLogic.executeLiquidationCall (calls handleRepayment or burn, need to clarify which aToken this is for...)
• SupplyLogic.executeWithdraw (calls atoken.burn after updating rates)
• SupplyLogic.executeSupply (calls atoken.mint after updating rates)
• FlashLoanLogic.executeFlashLoanSimple (calls handleRepayment at the very end)
• FlashLoanLogic.executeFlashLoan (calls handleRepayment at the very end)
• BorrowLogic.executeBorrow (❌ only SOMETIMES calls transferUnderlyingTo)
• BorrowLogic.executeRepay (calls burn or handleRepayment)
• BorrowLogic.executeRebalanceStableBorrowRate (❌ NO hooks into atoken)
• BorrowLogic.executeSwapBorrowRateMode (❌ NO aToken hook)

reserve.liquidityIndex

The reserve's liquidityIndex gets updated in cumulateToLiquidityIndex and _updateIndexes (covered above). cumulateToLiquidityIndex is called by:

• BridgeLogic.executeBackUnbacked (❌ NO aToken hook is called)
• FlashLoanLogic.executeFlashLoanSimple (calls handleRepayment at the very end)
• FlashLoanLogic.executeFlashLoan (calls handleRepayment at the very end)

from flexible-voting.

Based on the above, I think adding checkpointing to these functions will cover all of the reserve changes that we're capable of capturing:

• _mintScaledWithCheckpoint
  • this function was added in the naive implementation #11
  • it already has balance checkpointing, so reserve checkpointing should be trivial to add
• burn
  • deposit checkpointing was added in #11, so reserve checkpointing should be trivial to add
• handleRepayment
  • currently a no-op and virtual, this should be trivial to add checkpointing to
• transferUnderlyingTo
  • simple implementation and virtual
• _transfer
  • if someone transfers their aToken balance to someone else, their checkpointed deposit balance should also proportionately transfer
  • _transfer is virtual (defined in IncentivizedERC20) but it is overridden AToken
  • it's fine to override _transfer, we will just need to make sure we preserve the Atoken-specific changes

We'll need to think more about the cases above that we can't handle, i.e. where we don't have a hook to update the reserves. My guess is that they constitute a rounding error and cannot be taken advantage of by anyone to skew atoken voting weight maliciously. But we should confirm

from flexible-voting.

I was thinking about this more today and I feel pretty stupid, because I don't think we actually need to store any of the reserve data after all 🤦. Here's what I'm thinking...

We want to know rebased balances at arbitrary block numbers so that vote weight can be accurate. This is needed to solve the problem of two users with identical deposits at materially different times. If user A deposits X a year (say) before user B deposits X, then user A should have more voting weight than user B because user A's rebased balance would be higher than user B's.

As noted above, the formula for rebased balance is:

super.balanceOf(user).rayMul(POOL.getReserveNormalizedIncome(_underlyingAsset));

Put another way, the formula for rebased balance at a given block is just:

storedBalance(block) x rebaseFactor(block)

So, if you want to compare rebased balances of userA and userB at an arbitrary block it's natural to think you need both stored balances and rebaseFactors at that block, but that's not true for two reasons. First, because what we really care about when it comes to determining voting weights is the ratio between userA and userB's balance. Second, because they are both being scaled up by the same rebase factor. So, you can just ignore the rebase factor when computing their ratio. It just divides out anyway.

But how does this solve our problem with user A and user B? If we ignore the rebase factor, wouldn't they end up with the same balance if they each deposited the same amount? No! That's what I'd been missing. Because of how Aave's rebasing works, deposited values are scaled down when they are stored by the same factor that is used to determine rebased balance:

• when a user supplies, the pool calls atoken.mint, passing in the liquidityIndex (which is effectively a measure of the total interest earned by the pool)
• the atoken then scales the deposited amount by the liquidity index and stores that value as the balance
• that same liquidity index is then multiplied by the stored balance to determine the rebased balance

So userB will have a proportionally smaller stored balance than userA despite having deposited the same amount.

Here's a toy example of how it works to make things more concrete:

• suppose the pool has overall earned 5% interest over its lifetime
• Ben deposits $100
• the pool stores his balance as 100 / 1.05 == 95.23
• if Ben immediately withdrew his money his rebased balance would be: storedBalance * totalPoolInterest, i.e. 95.23 * 1.05 == $100, what we expect
• a year goes by and the pool earns another 5% interest, so the new overall pool rate is 1.05 * 5% == 1.1025
• I now deposit $100
• the pool stores my balance as 100 / 1.1025 == 90.70
• if I immediately withdrew, my rebased balance would be 90.70 * 1.1025 == $100, i.e. exactly what I put in
• Ben's rebased balance at this point would be 95.23 * 1.1025 == $105
• so he'd have 5% more underlying than me, as expected (since the pool as a whole earned 5% while he had his money in it)
• but notice we can just compare the base balances and get the same result 95.23 / 90.70 == 1.05, i.e. Ben has 5% more than me
• this is because we multiply both by the same factor to determine rebased balance!
• but what about at an arbitrary block in the past or future? We have no idea what total cumulative interest might be (or have been). True, but it doesn't matter because (again) both numbers are scaled up by that same rate. So it won't effect their ratio (which is all we care about when determining voting weight).

from flexible-voting.