closes https://github.com/paritytech/substrate/issues/9440
polkadot companion https://github.com/paritytech/polkadot/pull/3413
Notes for reviewers
Below is a table describing how an extrinsic would affect an account (relative to SortedListProvider
and CounterForNominators
) given its role in staking:
| extrinsic | Chilled | Nominator | Validator |
|:------------------:|:----------------------:|:----------------------:|------------------------|
| chill, chill_other | nothing, nothing | on_remove, dec counter | nothing, nothing |
| nominate | on_insert, inc counter | nothing, nothing | on_insert, inc counter |
| validate | nothing, nothing | on_remove, dec counter | nothing, nothing |
| bond_extra | nothing, nothing | on_update, nothing | nothing, nothing |
| rebond | nothing, nothing | on_update, nothing | nothing, nothing |
| unbond | nothing, nothing | on_update, nothing | nothing, nothing |
TODO:
- [x] update benchmarks of extrinsics that call
do_rebag
to force a rebag (relates to some work done in https://github.com/paritytech/substrate/pull/9529)
- [x] Check the benchmark values for snapshot creation. There are some tests that tell us how many snapshot items we can take in a 2 second block. https://github.com/paritytech/substrate/pull/9507#issuecomment-899466440
- [x] Write a remote-externalities-based test that checks the state of polkadot and substrate, and populates the list. Same as testing the migration basically: Done in companion.
- [x] Test migration
- [ ] (seperate_pr) Make all staking tests work with and without bags-list. For now we use bags-list only, and we do this in a follow up, to prevent a single super big PR.
- [x] rename and fix docs, avoid using
voter
in bags-list
, it should be id
and vote-weight
. Ideally we could also use something like priority
instead of vote-weight
.
- [ ] (maybe+separate PR) Write a fuzzer/quick test that just bombards the
SortedListProvider
with random data and calls, and the internal state of the pallet should always remain correct. (https://github.com/paritytech/substrate/pull/9851)
- [ ] (seperate pr) weight refunds for when the operation does not affect nominators (and thus not the bags list)
- [ ] (separate PR) Allow the ability to reorder yourself within a bag.
original description for #9081 below:
Problem: there are too many nominators, we can't keep all of them.
Solution: truncate the list by stake.
Problem: an attacker can kick out as many people as they can afford to; those people at the low end would need to re-nominate.
Solution: don't actually take them out of the nominator set, but compute the top N members at runtime.
Problem: computing the top N at runtime is expensive.
Solution: create many bags, each of which holds voters within a particular stake range. Each bag is a linked list, so it can be added to and removed from in O(1)
. We can then iterate over the bags in order and truncate anywhere we desire. Given a realistic distribution of stake, it doesn't matter where we stop; the final bag is the one with the lowest-staked individuals.
polkadot companion: https://github.com/paritytech/polkadot/pull/3413
A0-pleasereview B7-runtimenoteworthy E1-runtimemigration C1-low π D1-audited π