# Unbonding queue rework

## Storage

We store the following, an `UnlockChunk` for each unbonding with an account:

`(unbonding_amount, unbonding_start_era,previous_unbonded_stake_in_era)`

For every era in the last 28 eras, globally we store

`lowest_third stake` - the stake backing of 1/3 of validators with the least backing

`total_unbond_in_era` - the amount of stake that started unbonding in that era

## What transactions do

### Unbonding

An unbonding transaction removes `unbonding_amount` from an accounts bond. It remains locked. This creates an `UnlockChunk` where `unbonding_start_era` is the current era and `previous_unbonded_stake_in_era` is the current `total_unbond_in_era(current_era)` for this era. Then the `total_unbond_in_era(current_era)` is incremented by `unbonding_amount`.

### Rebonding

A user who wants to cancel some or all of their unbonding, putting some of the locked `unbonding_amount` for one or more of their `UnlockChunk`s back into their staked bond, may do so. They provide a `restake_amount`, which must be no more than the sum of all their `unbonding_amount`s in their unbonding record.

Then in order from the most recent unbonding record, stake is subtracted from the `unbonding_amount` in an unbonding record. When this happens, the same amount of stake is subtracted from the `total_unbond_in_era` of the `unbonding_start_era` of the record if it is within the last 28 era. If all the `unbonding_amount` in an unbonding record is removed then the record is deleted, otherwise we keep it with a reduced `unbonding_amount`.

### Withdrawing

A `withdraw_unbonded` transaction must make the following check to see if we can unbond the `unbonding_amount` of an `UnlockChunk`. It computes the stake that started unbonding between each era in the last 28 eras and the unbonding transaction up to the era that includes the unbonding transaction and checks to see if this is under the `max_stake` for that era.

If current_era < unbonding_start_era+2 then fail
If unbonding_start_era >= current_era-27
    total_unbond=0
    For era from unbonding_start_era to current_era-27 decreasing by 1
        If era == unbonding_start_era
            total_unbond = min(total_unbond_in_era[era],previous_unbonded_stake_in_era+unbond_amount)
        Else 
            total_unbond +=    total_unbond_in_era[era]
        If total_unbond >= (1-MIN_SLASHABLE_SHARE) * lowest_third stake[era]
            fail

If this pseudocode does not `fail` then the check succeeds and the `unbonding_amount` is unlocked and the `UnlockChunk` deleted.

Note that `total_unbond_in_era[unbonding_start_era]` does not change: this stake includes both unbonding stake that has been withdrawn and that for which withdrawal is pending.

## The unbonding time: why and what a UI should say

We can compute an estimate the number of eras left before an `UnlockChunk` can be unlocked as follows:

If unbonding_start_era < current_era-27
    return 0

total_unbond=0
For era from unbonding_start_era to current_era-27 decreasing by 1
    If era == unbonding_start_era
        total_unbond = min(total_unbond_in_era[era],previous_unbonded_stake_in_era+unbond_amount)
    Else 
        total_unbond +=    total_unbond_in_era[era]
    If total_unbond >= (1-MIN_SLASHABLE_SHARE) * lowest_third stake[era]
        return max(0, unbonding_start_era+2-current_era, era+28-current_era)
return max(0, unbonding_start_era+2-current_era)

For a prospective unbonder, unbonding `unbond_amount`, the calculation is the same as above except `total_unbond = min(total_unbond_in_era[era],previous_unbonded_stake_in_era+unbond_amount)` is replaced by`total_unbond = total_unbond_in_era[era]+unbond_amount`.

Note that after an era, the `total_unbond_in_era` can only go down due to rebonding. Similarly the `unbonding_amount` of an `UnlockChunk` can only go down after it was created. Thus the account holder can definitely unbond by the unbonding era calculated above, but possibly they can unbond earlier with enough rebonding. This is why we calculated this amount when withdrawing and not with the original unbonding trasaction. The purpose of `previous_unbonded_stake_in_era` and the associated condition is to ensure that if a lot of stake starts unbonding after this unbonding transaction in the same era and therefore pushing up `total_unbond_in_era[unbonding_start_era]` does not push up the unbonding time of this unbonding transaction to higher than the UI showed.

## Proof that we never unstake more than a threshold in 28 days

Consider an era `era` in the last 28 eras. We need to show that no more than `(1-MIN_SLASHABLE_SHARE) * lowest_third stake[era]`stake from that era has been unbonded and withdrawn since that era. The idea is to consider the last unbonding transaction that has been subsequently withdrawn and show that if the withdrawing check passed, then we are safe. Specifically we show that the `total_unbond` that was at most `(1-MIN_SLASHABLE_SHARE) * lowest_third stake[era]` during the iteration for `era` includes all the stake that could have been unbonded and withdrawn since `era`.

We call the `UnlockChunk` from the latest unbonding transaction that was withdrawn before now the `Critical_UnlockChunk`. We consider three points in the execution of the chain:

A: Just after the unbonding transaction that created the `Critical_UnlockChunk`
B: Just before the withdarwal transaction that deleted the `Critical_UnlockChunk`
C: the current time.

which we will use a subscripts for variables.
In addition to the chain state, we imagine that an execution of the chain also keeps track of `unbonded_withdrawn_started_in_era` for each era. Concretely, for every `UnlockChunk` which is succesfully withdrawn and deleted, we increase `unbonded_withdrawn_started_in_era[unbonding_start_era]` by `unbonding_amount`.

We need to show that for every era `attack_era` in the last 28 eras at time C, we have $\sum_{\textrm{era}=\textrm{attack_era}}^{\textrm{current_era}_C} \textrm{unbonded_withdrawn_started_in_era}[\textrm{era}]_C \leq (1-\textrm{MIN_SLASHABLE_SHARE}) * \textrm{lowest_third_stake}[\textrm{attack_era}]$ . By rhe definition of the `Critical_UnlockChunk`, no unbonding starting in later eras than it is withdrawn so $\textrm{unbonded_withdrawn_started_in_era}[\textrm{era}]_C=0$ for $\textrm{era} > \textrm{Critical_UnlockChunk.unbonding_start_era}$

After an `era` has ended, `total_unbond_in_era[era]` can only go down due to rebonding. Also we have at any time that $\textrm{total_unbond_in_era}[\textrm{era}]=\textrm{unbonded_withdrawn_started_in_era}[\textrm{unbonding_start_era}] +$
$\sum_{\textrm{UnlockChunk}:\textrm{UnlockChunk.unbonding_start_era}=\textrm{era}} \textrm{UnlockChunk.unbonding_amount}$.
Thus we have for any era between `attack_era` and $\textrm{current_era}_B-2$, $\textrm{total_unbond_in_era}[\textrm{era}]_B \geq \textrm{total_unbond_in_era}[\textrm{era}]_C \geq \textrm{unbonded_withdrawn_started_in_era}[\textrm{era}]_C$.

Now consider the time A just after the `Critical_UnlockChunk` starts unbonding. We define the `critical_era` to be this chunks `unbonding_start_era` and $W$ as the set of `UnlockChunk`s whose `unbonding_start_era` is the same `critical_era` and are succesfully withdrawn before time C. By the definition of the `Critical_UnlockChunk`, it is the last such chunk to start unbonding and npne can withdraw until `critical_era`+2 so at time A, all the chunks in W are on chain. Their `unbonding_amount`s cannot increase, only maybe decrease due to rebonding, between the unbonding start transaction and the time they are withdrawn. `unbonded_withdrawn_started_in_era[critical_era]` at time C is the sum of the `unbonding_amount`s of these chunks at the time they were withdrawn. So we have
$$\textrm{Critical_UnlockChunk.previous_unbonded_stake_in_era}+\textrm{Critical_UnlockChunk.unbonding_amount}_B \geq \textrm{Critical_UnlockChunk.unbonding_amount}_B + \sum_{\textrm{UnlockChunk} \in W \setminus \{\textrm{Critical_UnlockChunk}\}} \textrm{UnlockChunk.unbonding_amount}_A \geq \textrm{unbonded_withdrawn_started_in_era[critical_era]}_C$$.

When the `Critical_UnlockChunk` is withdrawn, the tests for withdrawal must pass. This happens at time B. Starting with the check for `attack_era` in the loop, we have

\begin{align*}
& (1-\textrm{MIN_SLASHABLE_SHARE} \times \textrm{lowest_third stake[attack_era]} \\
& \geq \min(\textrm{total_unbond_in_era[critical_era]}_B,\textrm{Critical_UnlockChunk.previous_unbonded_stake_in_era}+\textrm{Critical_UnlockChunk.unbond_amount}_B) + \\
& \geq \sum_{\textrm{era}=\textrm{attack_era}}^{\textrm{critical_era}} \textrm{unbonded_withdrawn_started_in_era[era]}_C \\
& = \sum_{\textrm{era}=\textrm{attack_era}}^{\textrm{current_era}_C} \textrm{unbonded_withdrawn_started_in_era[era]}_C \\
\end{align*}

which was what we needed to show.

## Implementation Notes (WIP)

> @kianenigma / @ank4n

* Please provide `#[pallet::view_functions]` for the unbonding time, which is no longer trivially stored, with direct runtime APIs as backup, in case view-functions are not stabilized by then
* tell you when you will be unbonded: return something like the old `UnlockChunk`: `amount` and `scheduled_to_withdraw`.
* retuns a `Vec<UnlockChunk { amount, current_scheduled_at, real_scheduled_at }>`
* The biggest breaking change here would be that `type Ledger = StorageMap<_>` is changing.

We have two options here:
* Our primary option is to already migrate `StakingLedger` to the new format before AHM happens on Kusama. For the unbonding era, we migrate era indices to `x - BondingDuration`. For `previous_unbonded_stake_in_era`, we set `u32::MAX` for everyone. We (@ank4n) aim to already change this as a part of AHM for Polkadot and Kusama. We can take care of this ourselves, but BlockDeep has to be aware and plan around it.
* The `withdraw` and `unbond` transaction would slighly change to accomodate for this, but the user experience would be the same
* This would already mean that wallets can no longer look at `UnlockChunk` to know when you will be unbonded, but rather when you have unbonded, and they need to add `BondingDuration` to that.

* We would be to do a multi-block-migration. This would be useful to provide and execute on westend, which is already migrated to WAH, so it would need a manual migration.