## `TargetList` sorted by approvals stake

➡️ Implementation at https://github.com/paritytech/polkadot-sdk/pull/1933

We want to maintain the list of staking targets sorted by their approvals stake and ensure that the list is *updated and sorted at all times*. The [stake tracker pallet](https://github.com/paritytech/polkadot-sdk/pull/1654) implements the `OnStakingUpdate` interface and will be used as the event handler that keeps both `VoterList` and `SortedList` (both implemented as bags lists) up to date.

It is important to keep the target list up to date with regard to the approvals stake when the number so that in case the number of registered validators is larger than the number of validators that are

However, updating the approvals stakes at the time of rewards (i.e. `Call::payout_stakers`) may be infeasible given the computation and storage writes required to keep the approvals up to date. Note that for each nominator payout, *all* the nominated validators need to get their approvals stake score up dated.

**Complexity**: Assuming that the approvals stakes are *all* updated at the time of rewards, a call to `payout_stakers` touching `N` (unbounded) nominators, each nominating `V` validators (bounded by the max nominations per nominator) requires `O(N * V)` approval votes updates. Since `N` is unbounded, this is an issue.

### Option 1. Update validators' approvals stake from nominator rewards lazily

For each ledger update related to _nominator_ rewards, the approvals stakes of the nominated validators are not updated automatically. Instead, a reward counter in the nominator's ledger, `approvals_queued`, is updated. The nominator rewards that have not been tallied as target approvals score will be kept in the ledger as queued approvals rewards counter.

The `approvals_queued` are settled and added to the validator's approvals score of the nominated whenever an action is performed on a nominator's ledger (`nominate`, etc).

pub struct StakingLedger<T: Config> {
    // ...
    approvals_queued: Balance, // probably better to keep track of this *outside* of the ledger, tbd
}

impl<T: Config> StakingLedger<T> {
    fn increase_queued_approvals(mut self, Balance) {}
    fn reset_queued_approvals(mut self) {}
}

In addition, we could expose a way for validators to explicitly request the settement of queued approvals from a bounded vec of nominators through an extrinsic.

**Complexity**: With this design, a call to `payout_stakers` touching `N` (unbounded) nominators, each nominating `V` validators (bounded by the max nominations per nominator) requires `O(1)` approval votes updates (the validator that is being rewarded only). When a nominator ledger is updated, there are `O(V)` score updates. Since `V` is bounded, we're gold.

**Advantages**
- The target approvals score will *eventually* be updated implicitly;
- The difference of approvals across validators due to the queued approvals will most likely spread out evenly across all the validators, which is fair and will potentially lead to a relative correct sorting of the targets list.
- Lazily updating the approvals score helps spreading the blockspace required to update the approvals scores;
- Less fees for caller of `stakers_payout` to pay, compared to full stakes update.
- Eventual update of the approvals happens implicitly without requiring extra actions from any staker.

**Disadvantages**
- The approvals score will be slightly out of date (but the diff will spread out and balance relatively evenly across the most popular validators);
- The nominator actions where the queued approvals are settled will be more expensive (perhaps we could selectively remove the fees to pay related to the queued approvals settlement, while still accounting for the block weight required to update the approvals score).

### Option 2. Let anyone update the approvals stake of validators

Expose an extrinsic where anyone could pay for a approvals score update of a validator given a bounded list of nominators. This way, the approvals score will be based on a subset of nominators only. The validator has the incentives to call the `set_approvals` when their current score is lower than the potential one.

impl<T: Config> Pallet<T> {
    
	#[pallet::call_index(X)]
	#[pallet::weight(T::WeightInfo::set_aprovals())]
	pub fn set_approvals(
		origin: OriginFor<T>,
        target: AccountId, 
		nominations: BoundedVec<T::AccountId, T::SomeMax>,
	) -> DispatchResult {
        
        let mut approvals_score: Balance = Zero::zero();
        
        for nominator in nominations.into_iter() {
            // if nominator is exposed to target, add staked 
            // ledger funds to the `approvals_score` accumulator.   
        }
        
        <T::TargetList as SortedListProvider>::set_score_of(
            target,
            approvals_score,
        );
    }
}

**Disadvantages**:
- The validator has no incentive to call `set_approvals` when the new score is *lower* than the current one in the list;
- Depending on the long tail of nominatied stake, it's possible that a large part of the approvals stake is left out of the calculation due to the limits of the number of nominators that can be accounted for. In this case, validators with skewed nominations (i.e. fewer nominators with large stake) will have an advantage. This may add preverse centralization incentivizes.

### Option 3. Require validators to explicitly and periodically request the update of their approvals

We can create a game where the validators are required/incentivized to update their approvals score even when their score degrades by *requiring* them to request an update to the approvals score.

The approvals score can have a TTL that invalidates/zeroes the approvals score after a given time. This way, if the validator does not explicitly request to update the approvals score, it will be put at the end of the queue.

**Disadvantages**:
- To ensure the TTL, the validator's score in the target list needs to be implicitly updated to 0 whenever the `Call::set_approvals` was not called within the TTL. This may be expensive and take a long time to sync the approvals score of the no-show validators.
- If there are too many "no-shows", i.e. a considerable number of good validators do not call `Call::set_approvals` on time, the economic security of the chain will be affected (since those vaidators would be dropped to the tail of the list and not selected for election, although the real approvals score would be high). There are some ways we could automate the call to set approvals through tooling, but it may be dangerous to piggy back economic security on tooling.

### Option Long term - Staking parachain

In the future, with the rewrite of staking pallet and the increase in blockspace in the context of the staking parachain, we may be able to process `stakers_payout` (or similar) on idle and/or periodically and design a mechanism where the approvals score can be reasonably updated automatically.

---

(from the PR @ [c7ad6bf3fe2fc60e074f4b9dfb7384dba3f6baa8](https://github.com/paritytech/polkadot-sdk/pull/1933/commits/c7ad6bf3fe2fc60e074f4b9dfb7384dba3f6baa8), removed)
## Deferring updates at nominator payout

Updating the approvals stakes in `TargetList` at the time of reward payout (i.e. `Call::payout_stakers`) may be infeasible given the computation and storage writes required to keep the approvals up to date. Note that for each nominator payout, *all* the nominated targets need to get their approvals stake score updated. In this scenario, the complexity of a `payout_stakers` can easily blow up:

> **Complexity**: Assuming that the approvals stakes are *all* updated at the time of rewards, a call to `payout_stakers` touching `N` (unbounded) nominators, each nominating `V` validators (bounded by the max nominations per nominator) requires `O(N * V)` approval votes updates. Since `N` is unbounded, this is an issue.

**Solution**: The solution is to buffer the updates to the target list when nominators are being paid out. Notice, however, that the nominator's staking ledger is *always* updated at the time of payout. Thus, there will be a slight inconsistency between the staking ledgers and the target list score state. The inconsistency will be settled eventually, per staking ledger, in one of two ways: 1) manually by calling an extrinsic `Call::settle_untracked_stake` or 2) automatically when a stash with inconsistencies changes the state of its ledger/nominations.

A new storage item, `UntrackedStake`, keeps track of the last stake of a stash which has been reflected in both target list and ledger.

/// Map from all the stashes with untracked stakes and the latest synced stake between the ledger
/// and the event listeners.
///
/// Untracked stake is the ledger stake that hasn't been propagated to `T::EventListeners`.
#[pallet::storage]
pub type UntrackedStake<T: Config> =
  StorageMap<_, Blake2_128Concat, T::AccountId, Stake<BalanceOf<T>>>;

At the time of settling the buffered untracked stake of a stash, the `OnStakingUpdate::on_stake_update` is called, where the previous stake is the one stored in the `UntrackedStake` storage item. This will update the target and voter list and bring it up to sync with the ledger's state.

<T::EventListeners as OnStakingUpdate<T::AccountId, BalanceOf<T>>>:::on_stake_update(&ledger.stash, Some(untracked_stake));

With the new design, the complexity of calling `payout_stakers` remains reasonable:

> **Complexity**: With this design, a call to `payout_stakers` touching `N` (unbounded) nominators, each nominating `V` validators (bounded by the max nominations per nominator) requires `O(1)` approval votes updates (the validator that is being rewarded only). When a nominator ledger is updated, there are `O(V)` score updates. Since `V` is bounded, we're gold.

---