How can the Substrate staking pallet be used in a parachain?

Question

Staking pallet allows a chain to elect validators/collators with respect to their stake. There are multiple ways in staking pallet to implement ElectionProvider (both on-chain and off-chain) which decides the next validator and nominator list based on stake; copying the Staking/ElectionProvider configuration of Polkadot/Kusama is not ideal for parachains.

What ideal configuration of the ElectionProvider and Staking pallet will work for parachains and solo chains?

Answer 1

Finally, the first draft of my write up about this complicated topic is done. This document would likely change, find the latest version here.

The following is the version as of June 2022.

---

In depth guide about configuring the Staking/Election pallet, targeting Substrate builders, and parachain teams.

Written by @kianenigma. Feel free to reach out for further questions, or ask them in Substrate stack exchange.

This is guide to help various teams building on top of substrate configure the staking system properly.

Before diving in any further, let's make sure two facts are known:

1. The staking system in Substrate is quite complex, and deploying it recklessly can have severe consequences.
2. The staking system in Substrate is not yet parachain-ready by default. Nonetheless, you can configure it such that it can work in a parachain as well.

---

The staking pallet can be roughly broken down into 4 parts:

1. Staking roles: the simplest part. Handles staker roles (validator, nominators, etc) and allows these roles to be set.
2. Rewards
3. Slashes
4. Validator selection, i.e. the Elections.

The most important (and error-prone) part to configure here is the last one. This is mainly done through implementing type ElectionProvider: ElectionProvider for the staking pallet.

To run any type of election, staking pallet needs to know how to select a subset of its validator and nominators as the election voters and targets (i.e. candidate). Initially the answer might seem trivial: All nominators are voters and all validators are candidates. But this does not always work: The staking pallet does not put any limit on the number of validators and nominators, and no election algorithm can work on an unbounded input. So the question remains: Between all nominators, which subset should we consider for elections (and similarly for validators). Answering this is done through type VoterList and type TargetList*. Both of these types should satisfy SortedListPorivider.

First, let's look at the latter.

VoterList and TargetList

As noted, the staking system can have a potentially unbounded number of nominators and validators, and by default it has no meaningful way of sorting them. You can either add this sorting mechanism, or leave it as is

1. NOT Sorting Staking Validators and Nominators

If you intend to use all of these validators and nominators for election, then there is no need to care about sorting them. In this case, you can use these two simple types. They basically iterate over the underlying maps in an unordered way.

1. UseNominatorsAndValidatorsMap, which should be used for type VoterList
2. UseValidatorsMap, which should be used for type TargetList.

* The TargetList interface is still in development and is being added in this PR. Everything said about VoterList is already implemented in substrate master.

The VERY IMPORTANT consequence of this is that now, the staking pallet would need to iterate over all nominators and validators at certain blocks. This clearly means that the number of validators and nominators MUST be bounded.

1.2 Bounding Validators and Nominators

There are 4 storage items, and 2 transactions, all of which together can help a chain put a cap on its validators and nominators, and maintain it. All of these live in pallet-staking.

1. MinValidatorBond and MinNominatorBond. As the name suggests, these dictate the amount of tokens that are needed to become a validator or nominator. By setting them to non-zero values, the influx of nominators and validators can be regulated. The higher the value is, the less influx is expected. These values can also be set such that the cost of any type of sybil attack (a whale spawning a million nominator accounts to mess with you) becomes more expensive.
2. MaxValidatorCount and MaxNominatorCount. The aforementioned limits don't actually restrict the count of nominators or validators, they just make it more expensive to create a very large number of them. Nonetheless, you might know that your system cannot, under any condition, tolerate more than 5000 nominator. In that case, these two storage items can be used. If either of the limits are reached, no new nominator/validator can be created.
3. The last two are enough to ensure system safety, but you could still have the situation where all of the e.g. nominator slots are filled, and this makes it impossible for any other account to become a nominator, even if they have a lot of tokens. To combat this, the permissionless chill_other transaction can be used. This transaction makes it possible to chill any validator/nominator who has less stake bonded than the corresponding limit, namely MinValidatorBond and MinNominatorBond. If no account is eligible for this, then the corresponding limit can be raised.
4. Lastly, set_staking_configs can be used to control all of the above through the root origin.

This method was used in Polkadot for a few months and this script was used to determine who could be chilled and do it.

I omitted a minor details called ChillThreshold here for the sake of simplicity.

2. Sorting Staking Validators and Nominators

If you need to sort the staking validators and nominators, then you need to use an instance of the bags-list pallet as the SortedListPorivider. bags-list is essentially an onchain sorted linked list that's kept up to date in a lazy manner. The staking pallet is configured to use bags-list, if it is provided, with the following rules:

1. The nominators and validators are both reported to the VoterList as a voter, and their active stake determines their position in the list. This means that each validator's self stake is analogous to a them nominating themselves.
2. All validators's are considered as targets, and their approval stake* determines their position in the list.

The approval stake of a validator is the sum of the entire stake all all nominators who nominated them.

With these two interfaces in place, the staking pallet essentially becomes capable of sorting its validators and nominators. Therefore, in principle, it can let them both grow to infinity in terms of count, but only consider a top subset for election when the time comes. For example, a system could consider the top 10,000 nominators and top 1000 validators, and let the bags-list take care of the sorting.

There is a LOT more detail to bags-list that we are not covering here. See the Polkadot wiki to learn more about them.

Note that if you start with the former approach and want to migrate to the latter, the bags-list needs to be migrated. Old migration codes used in Polkadot should be reusable for all other chains as well. See the v8 and v9 migration modules in pallet-staking.

3. Putting it All Together: ElectionDataProvider

Everything that I said so far was a prelude to reach to this last section: Staking implements the ElectionDataProvider trait with the help of its VoterList and TargetList.

The very important aspect of this trait is that the functions that are used to fetch the voters and targets, both have an optional maybe_max_len: Option<usize> argument. This is basically how the user of the ElectionDataProvider tells staking how many voters it wants. See fn electable_targets and fn electing_voters.

Who will decided what value is passed as this maybe_max_len? that will be the user of ElectionDataProvider, which is most often something that itself implements ElectionProvider.

                                         ElectionDataProvider
                          <------------------------------------------+
                          |                                          |
                          v                                          |
                    +-----+----+                              +------+---+
                    |          |                              |          |
 pallet-do-election |          |                              |          | pallet-needs-election
                    |          |                              |          |
                    |          |                              |          |
                    +-----+----+                              +------+---+
                          |                                          ^
                          |                                          |
                          +------------------------------------------+
                                         ElectionProvider

ElectionProvider

The main user of ElectionDataProvider is, as the name lamely suggests, something that wants to implement ElectionProvider. After all, if you want to provide an election service, you need to know its data.

There are generally two types of election providers, as explained further.

Onchain execution

This is the simpler type of election, and performs everything needed onchain, in a single block. The implication of this should be obvious: The number of voters and targets cannot be unbounded.

If this approach is used, a great deal of care should be given to making sure that either the stakers are well bounded, or that they are sorted and the onchain execution election that you configure is only selecting a small subset of them. All onchain executions are configured with two wrapper types that implement ElectionProvider:

1. BoundedExecution
2. UnboundedExecution.

They both accept a number of configuration parameters, such as which election algorithm to use, and which data provider to communicate with. But, the most important one (that also differentiates them) is that BoundedExecution also accepts two bounds for the number of voters and targets that it asks from its ElectionDataProvider via:

pub trait BoundedConfig: Config {
    /// Bounds the number of voters.
    type VotersBound: Get<u32>;
    /// Bounds the number of targets.
    type TargetsBound: Get<u32>;
}

In other words, these two values are later on passed to fn electing_voters and fn electable_targets.

Offchain execution

The bounded executions are probably enough for an election in the order of a few dozed candidates, and a few hundred voters.

To figure out the exact values, check the benchmarks of the onchain execution types, and match them against your block type. Moreover, you should also know that there is a maximum memory limit of 128 MiB in wasm, and a maximum allocation of 32 MiB. The whole election process should not violate these.

For anything beyond this, the election process needs to be moved offchain. This is done though the election-provider-multi-phase pallet, which also eventually implements ElectionProvider. The details of this pallet are quite complicated, but luckily its documentation is also extensive. Knowing the context provided in this document, reading that should clear a lot of things up for you. In this document, we only skim some of the more important aspects.

The main aspect of this pallet that correlate with what we have talked about here, is two type parameters, namely MaxElectingVoters and MaxElectableTargets. Similar to BoundedExecution above, these two values dictate how many voters and targets are fetched from the ElectionDataProvider, aka. pallet-staking in most cases.

---

With all of that said, either the ochain election, or the offchain election can be used in a parachain, as long as the number of voters and targets are bounded properly, either by sorting and taking the top portion, or by limiting them from the get go.