Tracking Issue for multi-block election + dedicated election system parachain

[kianenigma]

Non-technical overview

• read if you want to know how Polkadot's NPoS works and why it is complicated: https://hackmd.io/wC6XTy36QsCmkfolX38Miw
• Monthly update report on the progress of staking: https://gist.github.com/kianenigma/aa835946455b9a3f167821b9d05ba376

parent of paritytech/substrate#6242.

Task List

(expect this to grow and change over time)

• WIP branch: https://github.com/paritytech/substrate/tree/kiz-multi-block-election
• Repo for e2e testing: https://github.com/kianenigma/election-provider-playground

Main track

• [x] Step 0: Paginated ElectionDataProvider:
  • Add remaining: PageIndex to the interfaces, and make pallet-staking understand it.
  • Bags-list will need to support an iter_from() for this to work.
  • https://github.com/paritytech/substrate/pull/11105
• [ ] Step 1: Bounded ElectionProvider: @emostov
  • Change return type of fn elect to BoundedSupportsOf<_>.
  • Add MaxBackersPerWinner.
  • Will bring us a huge step closer to allowing storage_info for staking.
  • https://github.com/paritytech/substrate/pull/11229
• [ ] Step 2: Paginated ElectionProvider:
  • add remaining: PageIndex to the interface and make pallet-staking understand it.
  • add MaxWinnersPerPage.
• [ ] Step 3: The almighty pallet-election-provider-multi-block
  • .. which will be further broken down into 4 pallets:
  • pallet-election-provider-multi-block: takes care of phase rotation and snapshot management
  • pallet-verifier: takes care of verifying solutions in one or more blocks
  • pallet-signed.
  • pallet-unsigned.

Other misc. worthy of being backported

• [ ] moderate: backport sort and remove_weakest_sorted from NposSolution. Test them well, but don't use them anywhere.

Nice to have

• [x] Implement MaxEncodedLength for NposSolution: https://github.com/paritytech/substrate/pull/11032
• [ ] trivial: at the end: set VoterIndex = u16. Unless of voter page per snapshot is more than 65k, which it will never be, we can drastically reduce the size of the solution via this simple tweak.
• [x] easy: deprecate supportMap and its associated functions: https://github.com/paritytech/substrate/pull/9674
• [ ] documentation: ensure staking-miner can generate correct, feasible, bounded single-page, emergency solutions, with instructions and wiki on how to submit it.
• [x] https://github.com/paritytech/substrate/issues/8641
• [ ] https://github.com/paritytech/polkadot-sdk/issues/462
• [ ] Runtime Task scheduler for a nicer interface of doing stuff in multiple blocks paritytech/substrate#8197
• [ ] Allow more memory usage in offchain workers paritytech/substrate#8885
• [x] backport: recursive election provider as fallback: https://github.com/paritytech/substrate/pull/9648
• [x] Migrate ElectionProvider and ElectionDataProvider to use associated types for AccountId and BlockNumber, for nicer visuals and consistent API. https://github.com/paritytech/substrate/pull/10475
• [ ] moderate: Move creation of ErasStakersClipped to on_idle. We have a full era to make sure it is filled, and even if not, it is not a consensus critical operation.

Hygiene

• [x] Staking should be able to stop iteration and pick it up later, for multi-block snapshot. paritytech/substrate#9313
• [x] Rename CompactSoltuion to anything else that does not have the keyword Compact in it. That's very confusing. paritytech/substrate#9442
• [x] Remove weight from the ElectionProvider and ElectionDataProvider traits, instead to the benchmarking accurately. https://github.com/paritytech/substrate/pull/9569

[kianenigma]

Monthly update notes: https://gist.github.com/kianenigma/aa835946455b9a3f167821b9d05ba376

[kianenigma]

Almost everything needed for this work is now done and tested in my WIP branch. I've updated the main task list with 4 major steps of how this should be backported to the master branch.

[kianenigma]

about reading relay chain state from parachain: https://github.com/paritytech/polkadot-sdk/issues/82

[kianenigma]

@gpestana @Ank4n is this still needed? If you have a newer version, please close and link here.