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

• 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.
  • Multi-block election part 0: Paginated election data provider substrate#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.
  • Bounding ElectionProvider substrate#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

• Implement MaxEncodedLength for NposSolution: Implementing MaxEncodedLen for generate_solution_type substrate#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.
• easy: deprecate supportMap and its associated functions: clean the interface of supports map substrate#9674
• documentation: ensure staking-miner can generate correct, feasible, bounded single-page, emergency solutions, with instructions and wiki on how to submit it.
• Refactor election-provider-multi-phase solution checks substrate#8641
• Ensure saved offchain solution matches creation snapshop #462
• Runtime Task scheduler for a nicer interface of doing stuff in multiple blocks Runtime Task Executor + Example for staking slashing spans substrate#8197
• Allow more memory usage in offchain workers Allow separate max-heap-pages for offchain (non-consensus) execution context. substrate#8885
• backport: recursive election provider as fallback: Recursive election provider as fallback substrate#9648
• Migrate ElectionProvider and ElectionDataProvider to use associated types for AccountId and BlockNumber, for nicer visuals and consistent API. move generics of election trait to associated types substrate#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

• Staking should be able to stop iteration and pick it up later, for multi-block snapshot. Add methods to PrefixIterator to support iterating from a specific key substrate#9313
• Rename CompactSoltuion to anything else that does not have the keyword Compact in it. That's very confusing. Multi-Block Election part 0: preparation and some cleanup.  substrate#9442
• Remove weight from the ElectionProvider and ElectionDataProvider traits, instead to the benchmarking accurately. remove the uselsss weight return type from election provider API substrate#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: #82

[kianenigma]

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