Tracking issue for next generation pallet-staking and elections

[kianenigma]

I have had lots of ideas about how to improve staking, its election algorithm and its configurability lately. Here is a digest and a tracking issue about it.

Current State of Affairs

pallet-staking is currently at its most sophisticated state. Aside from basic staking ops ([un]bonding, setting intentions, maintaining eras and exposures), it handles rewards, slashing, and election, each of which being quite a complex piece of machinery. The problem is, this sophistication also translates to the code being bloated. At the time of this writing, staking's main lib.rs is ~3700 LoC. It worth noting the fact that most of the logic related to slashing and offchain workers are already placed in their own modules. Moreover, it has more than a hundred unit tests, some of which have been reported to be outdated already (#5838).

There are a few major problems with this code and how it is evolving.

1. Sooner or later, this monolith piece of code will accumulate too much technical debt and become increasingly hard to maintain.
2. Frame currently provides one and only one staking pallet which has all the aforementioned complexities that I named. It would be a major drawback not to have any configurability over this. I really don't think all the chains that get built by substrate need for instance the offchain worker logic of staking. Same could be arguably said about slashing and rewards as well.

That being said, there is a way to switch off the offchain workers, but the code is still very complicated and will be shipped to everyone who doesn't need it. Since there is a runtime check that disables the offchain machinery, the compiler will also have now way to know this and this will increase the wasm size by a small amount.

3. I am increasingly worried if the unit tests are sound and will prevent all the basic errors, specially at the boundaries of these logical components: i.e. slashing <-> election.

Aside from aesthetic refactoring, we also need a bunch more election algorithms. Indeed, they are no longer Phragmén-related in any sense, hence we also need to clean and rename the sp-phragmen crate into something more general. The current pipeline is:

Offchain: seq_phragmen() -> random iteration of balancing() (aka. equalise()) -> reduce() -> compact() -> submit to pool.
Onchain: un_compact() -> validity_checks()*.

The next generation pipeline will be:

Offchain: balanced_heuristic()* -> reduce() -> compact() -> submit to pool.
Onchain: un_compact() -> validity_checks() -> PJR_check().

We also need a PJR_enabler() implementation, only to be used if we reach the end of the era with no good submissions. In that case we run seq_phragmen() -> PJR_enabler().

• Validity checks are those that only make sure a solution is valid, and better than the best solution that we have had before. If we have no solutions for some reason, we accept any piece of sh*t solution as well.
• New election scheme developed by Web3 Foundation. see here for more details.

The Plan Ahead

Here are the steps that I think are necessary:

• 1. Rename sp_phragmen to something more general, and rename internal functions to reflect this. Now, since the crate is called sp_phragmen, seq_phragmen method is simply called elect(). This is wrong and should ba named seq_phragmen. Later on, we can add other algorithms to this list.

  • Would also be good to close this now: Document, clean and stabilise phragmen's behavior with dupe candiadtes and voters. #4593
  • Pull Request: Rename all the election operations #6245

• 2. Implement balanced_heuristic() aka phragmms. This will be first of the few new algorithms that we will need. My initial study concluded that implementing it will not have that much complexity and should be straightforward.

  • Pull request that adds the implementation PhragMMS election. #6685.

• 3. Clean all staking tests. Before making too much changes, I want to make sure that we have a solid army of unit tests to make sure any further change will not break anything.

  • Related Issues include but are not limited to: Clean Staking <-> Session tests and Use a Realistic Scenario #5244,
  • mega cleanup of staking tests #9516

• 4. Introduce ElectionProvider to staking and decouple staking from something that can provide a new set of election result at the end of an era. Something like the below sketch:

// Staking trait
trait Trait {
	type Election: ElectionProvider;
	// ...
}

impl<T: Trait> Module<T> {
	fn new_session(n: BlockNumber) -> Option<T::AccountId> {
		if somehow_time_to_trigger_new_era {
			// prepare inputs
			let validates = <Validators<T>>::iter().collect();
			let nominators = <Nominators<T>>::iter().collect();
			let inp = ElectionInput { validators, nominators };
			let let maybe_new_election_output = T::Election::elect(inp).map(|output| {
				// do some processing with output, such as updating exposures etc.

				// extract only the winners Vec<T::AccountId>
				output.winners
			})
		} else {
			None
		}
	}
}

/// Something that can elect a new set of validators at the end of an era.
trait ElectionProvider {
	/// Elect new validator set.
	// The SUPER TRICKY part here is to chose a worthwhile API for this to cover all the cases.
	// A bonus not to be forgotten is that I want to use this for elections-phragmen pallet as well.
	fn elect(input: ElectionInput) -> Option<ElectionOutput>;
}

// To have an OnChain phragmen only, we just need a simple type to implement this.
struct OnChainSeqPhragmen;

impl ElectionProvider for OnChainSeqPhragmen {
	fn elect(input: ElectionInput) -> Option<ElectionOutput> {
		// just proxy a call to the primitives crates with the elections. No further call should be
		// needed.
	}
}

// To implement the current offchain machinery we will need a new pallet named:
// OffChainElectionProvider.
// /frame/offchain-election-provider/lib.rs

// this module might need to depend on staking to check solutions. We need access to staking
trait Trait: system::Trait /* + staking::Trait */ {
	type ElectionLookahead: Get<Self::BlockNumber>;
	type Call: Dispatchable + From<Call<Self>> + IsSubType<Module<Self>, Self> + Clone;
	type MaxIterations: Get<u32>;
	type MinSolutionScoreBump: Get<Perbill>;
	type UnsignedPriority: Get<TransactionPriority>;
}

// all the storage items that are only for staking
decl_storage! {
	pub SnapshotValidators get(fn snapshot_validators): Option<Vec<T::AccountId>>;
	pub SnapshotNominators get(fn snapshot_nominators): Option<Vec<T::AccountId>>;

	pub QueuedElected get(fn queued_elected): Option<ElectionResult<T::AccountId, BalanceOf<T>>>;
	pub QueuedScore get(fn queued_score): Option<ElectionScore>;

	pub EraElectionStatus get(fn era_election_status): ElectionStatus<T::BlockNumber>;

	pub IsCurrentSessionFinal get(fn is_current_session_final): bool = false;
}

decl_module! {
	fn submit_election_solution()  {}
	fn submit_election_solution_unsigned() {}
}

impl<T: Trait> ElectionProvider for Module<T> {
	fn elect(input: ElectionInput) -> Option<ElectionOutput> {
		// same logic as we have now: return best queued solution, else fallback to onchain staking. 
		<QueuedElected<T>>::take().or_else(||
			Self::fallback_seq_phragmen()
		);
	}
}

Notable challenges here are:

• The offchain-election-provider module will need to read staking's storage to check values, unless if we pass every data that it needs to it. Not worth IMO.

• The offchain-election-provider will need to somehow still force staking to lock itself at some points in time.

• 5. Once this is done, we could optionally investigate stripping down rewards and slashing from staking as well. Ideally, I would like to have a core staking modules that only does, as mentioned above:

[un]bonding, setting intentions, maintaining eras and exposures

And the rest can be plugged to it as additional modules.

---

I the first 3 steps of the issue are somewhat mandatory to be done very soon in my opinion. The new election is a great security improvement (since we will check for PJR property) and the test cleanup has been due for a long time.

As for the refactor, if it is feasible to do, it would be much better to do it sooner than later, since it will require a complicated migration in storage. Perhaps if it can be done prior to Polkadot's staking enablement, it would be much easier to do the migration while there is still a sudo key at hand. Nonetheless, it is not a big issue as we have to ship this to Kusama first anyhow.

[kianenigma]

Also a good one to keep in mind: #3544

[kianenigma]

cc @thiolliere @shawntabrizi

[kianenigma]

[kianenigma]

As shown in the pictures above, we had some recent discussions about staking and npos with web3 foundation as well. Here I will write a small digest of this event and the conclusions.

The content here will overlap a bit with the original issue comment but I prefer to keep them separate for better visibility. Anyone reading the main issue should also continue until here to get the full picture.

Roadmap

As seen in the roadmap, PhragMMS #6685 is the last implementation that has been added. Aside from that, we have multiple tracks of improvements. The red ones are urgent, blues are sometime soon and the grey ones are more or less just an idea.

PJR-Check Track

This is the most important track that needs to be worked upon. It needs one PR to add the PJR_check function, potentially also the PJR enabler. This must then be integrated into the current offchain phragmen v1 pipeline and we expect to see no tangible changes here.

This must definitely added prior to the miner track, because we first want to have the PJR check in place for added security and then encourage external submissions.

Miner Track

I am working on this in parallel at the moment and I expect it to be not too much work.

1. Add MMS algorithm. Hopefully PhragMMS election. #6685 is merged by then and then this implementation will be rather trivial to add. This is a super slow algorithm that is only sensible to use offchain.
2. Audit the feasability-check() code.
3. put some small code on-chain that rewards the solutions.
4. Document and announce a Rust and a JS miner. Rust will be faster but I expect JS to also be useful.

ElectionProvider Track

This is more of a refactor, and has already been explained above. One change to this is that once staking and eleciton are decoupled, we can refactor the current OffchainElectionProvider to be TwoPhaseOffchainElectionProvier, as explained in the picture above.

[kianenigma]

Some other low hanging fruit in staking are the following concerns. These are generally easy to implement but it is still uncertain if we want them or not.

1. Slashing and Self Stake

The current system barely makes any difference between nominator stake and self stake. In fact, the distinction is only made when we build the Exposure where if a backing is coming from self, we add it to the own field rather than adding a new (AccountId, Balance) pair to others, which saves us a meager few bytes. As for slashing, self stake and nominator stake is essentially the same and makes not much difference.

We are looking for a way to allow validators to put forward some risk factor by having more self stake, and slashing first from the self stake and then from the pro-rate stake.

2. Events that should chill

1. There's already a rather ongoing dispute about keeping or chilling nominators when a non-zero slash happens here Full Slash Reversals #6835.

2. Now there's another case as well:

There is a bug in the current system around self stake: you can change it without loosing your nominations. We actually do need to fix that one sometime.

(cc @burdges)

3. Finally, it is arguable to request some chilling to happen when other parameters also change. What if a validator suddenly increase their reward precent to 100%, effectively ditching all nominators. Should we inform the nominator in this case?

[burdges]

If we've some suppression scheme, then we could suppress nominations by the factor the reward increased. This suppression continues until the nominator touches their span.

I've no particular justification for this, except that validators can then only increase their reward percentage when they've enough excess nominations, and nominators need not configure anything.

I'm also afraid that this suppression notion (a) sucks for phragmen, and (b) does not quite match the suppression notion suggested for slashing, but maybe some common ground exists.

[stale]

Hey, is anyone still working on this? Due to the inactivity this issue has been automatically marked as stale. It will be closed if no further activity occurs. Thank you for your contributions.

[kianenigma]

I am closing this with pretty much the last update about the state of staking, and will open a new tracking issue for the 2021 and onwards. The last note-worthy events:

• We pretty much shipped the whole ElectionProvider track. It allowed us to accept many more nominators, but in turn it also caused us to overlook the memory constrains and run into a few issues. Note worthy PRs:

  • Decouple Staking and Election - Part 3: Signed Phase #7910
  • Decouple Staking and Election - Part 2.1: Unleash Multi Phase #8113
  • Decouple Staking and Election - Part 2 Unsigned Phase #7909

• We launched a simple staking miner:

  • https://github.com/paritytech/polkadot/pull/3141/files

• We added a bunch of misc. addition to make the system fail safe:

  • add an absolute measure of election score on-chain as a parameter #8903
  • Emergency mode for elections.  #8918