Tracking issue for bounding `pallet-staking` storage items

[kianenigma]

related to https://github.com/paritytech/polkadot-sdk/issues/323 and https://github.com/paritytech/substrate/issues/9724

If we simply remove the pallet::without_storage_info, we get an error about the following items:

Full Errors

``` error[E0277]: the trait bound `std::vec::Vec<::AccountId>: parity_scale_codec::MaxEncodedLen` is not satisfied --> frame/staking/src/pallet/mod.rs:59:12 | 59 | #[pallet::pallet] | ^^^^^^ the trait `parity_scale_codec::MaxEncodedLen` is not implemented for `std::vec::Vec<::AccountId>` | = help: the following other types implement trait `parity_scale_codec::MaxEncodedLen`: () (TupleElement0, TupleElement1) (TupleElement0, TupleElement1, TupleElement2) (TupleElement0, TupleElement1, TupleElement2, TupleElement3) (TupleElement0, TupleElement1, TupleElement2, TupleElement3, TupleElement4) (TupleElement0, TupleElement1, TupleElement2, TupleElement3, TupleElement4, TupleElement5) (TupleElement0, TupleElement1, TupleElement2, TupleElement3, TupleElement4, TupleElement5, TupleElement6) (TupleElement0, TupleElement1, TupleElement2, TupleElement3, TupleElement4, TupleElement5, TupleElement6, TupleElement7) and 78 others = note: required because of the requirements on the impl of `StorageInfoTrait` for `frame_support::pallet_prelude::StorageValue<_GeneratedPrefixForStorageInvulnerables, std::vec::Vec<::AccountId>, frame_support::pallet_prelude::ValueQuery>` error[E0277]: the trait bound `StakingLedger: parity_scale_codec::MaxEncodedLen` is not satisfied --> frame/staking/src/pallet/mod.rs:59:12 | 59 | #[pallet::pallet] | ^^^^^^ the trait `parity_scale_codec::MaxEncodedLen` is not implemented for `StakingLedger` | = help: the following other types implement trait `parity_scale_codec::MaxEncodedLen`: () (TupleElement0, TupleElement1) (TupleElement0, TupleElement1, TupleElement2) (TupleElement0, TupleElement1, TupleElement2, TupleElement3) (TupleElement0, TupleElement1, TupleElement2, TupleElement3, TupleElement4) (TupleElement0, TupleElement1, TupleElement2, TupleElement3, TupleElement4, TupleElement5) (TupleElement0, TupleElement1, TupleElement2, TupleElement3, TupleElement4, TupleElement5, TupleElement6) (TupleElement0, TupleElement1, TupleElement2, TupleElement3, TupleElement4, TupleElement5, TupleElement6, TupleElement7) and 78 others = note: required because of the requirements on the impl of `StorageInfoTrait` for `frame_support::pallet_prelude::StorageMap<_GeneratedPrefixForStorageLedger, frame_support::Blake2_128Concat, ::AccountId, StakingLedger>` error[E0277]: the trait bound `RewardDestination<::AccountId>: parity_scale_codec::MaxEncodedLen` is not satisfied --> frame/staking/src/pallet/mod.rs:59:12 | 59 | #[pallet::pallet] | ^^^^^^ the trait `parity_scale_codec::MaxEncodedLen` is not implemented for `RewardDestination<::AccountId>` | = help: the following other types implement trait `parity_scale_codec::MaxEncodedLen`: () (TupleElement0, TupleElement1) (TupleElement0, TupleElement1, TupleElement2) (TupleElement0, TupleElement1, TupleElement2, TupleElement3) (TupleElement0, TupleElement1, TupleElement2, TupleElement3, TupleElement4) (TupleElement0, TupleElement1, TupleElement2, TupleElement3, TupleElement4, TupleElement5) (TupleElement0, TupleElement1, TupleElement2, TupleElement3, TupleElement4, TupleElement5, TupleElement6) (TupleElement0, TupleElement1, TupleElement2, TupleElement3, TupleElement4, TupleElement5, TupleElement6, TupleElement7) and 78 others = note: required because of the requirements on the impl of `StorageInfoTrait` for `frame_support::pallet_prelude::StorageMap<_GeneratedPrefixForStoragePayee, frame_support::Twox64Concat, ::AccountId, RewardDestination<::AccountId>, frame_support::pallet_prelude::ValueQuery>` error[E0277]: the trait bound `ValidatorPrefs: parity_scale_codec::MaxEncodedLen` is not satisfied --> frame/staking/src/pallet/mod.rs:59:12 | 59 | #[pallet::pallet] | ^^^^^^ the trait `parity_scale_codec::MaxEncodedLen` is not implemented for `ValidatorPrefs` | = help: the following other types implement trait `parity_scale_codec::MaxEncodedLen`: () (TupleElement0, TupleElement1) (TupleElement0, TupleElement1, TupleElement2) (TupleElement0, TupleElement1, TupleElement2, TupleElement3) (TupleElement0, TupleElement1, TupleElement2, TupleElement3, TupleElement4) (TupleElement0, TupleElement1, TupleElement2, TupleElement3, TupleElement4, TupleElement5) (TupleElement0, TupleElement1, TupleElement2, TupleElement3, TupleElement4, TupleElement5, TupleElement6) (TupleElement0, TupleElement1, TupleElement2, TupleElement3, TupleElement4, TupleElement5, TupleElement6, TupleElement7) and 78 others = note: required because of the requirements on the impl of `StorageInfoTrait` for `frame_support::pallet_prelude::CountedStorageMap, frame_support::Twox64Concat, ::AccountId, ValidatorPrefs, frame_support::pallet_prelude::ValueQuery>` error[E0277]: the trait bound `Nominations: parity_scale_codec::MaxEncodedLen` is not satisfied --> frame/staking/src/pallet/mod.rs:59:12 | 59 | #[pallet::pallet] | ^^^^^^ the trait `parity_scale_codec::MaxEncodedLen` is not implemented for `Nominations` | = help: the following other types implement trait `parity_scale_codec::MaxEncodedLen`: () (TupleElement0, TupleElement1) (TupleElement0, TupleElement1, TupleElement2) (TupleElement0, TupleElement1, TupleElement2, TupleElement3) (TupleElement0, TupleElement1, TupleElement2, TupleElement3, TupleElement4) (TupleElement0, TupleElement1, TupleElement2, TupleElement3, TupleElement4, TupleElement5) (TupleElement0, TupleElement1, TupleElement2, TupleElement3, TupleElement4, TupleElement5, TupleElement6) (TupleElement0, TupleElement1, TupleElement2, TupleElement3, TupleElement4, TupleElement5, TupleElement6, TupleElement7) and 78 others = note: required because of the requirements on the impl of `StorageInfoTrait` for `frame_support::pallet_prelude::CountedStorageMap<_GeneratedPrefixForStorageNominators, frame_support::Twox64Concat, ::AccountId, Nominations>` error[E0277]: the trait bound `ActiveEraInfo: parity_scale_codec::MaxEncodedLen` is not satisfied --> frame/staking/src/pallet/mod.rs:59:12 | 59 | #[pallet::pallet] | ^^^^^^ the trait `parity_scale_codec::MaxEncodedLen` is not implemented for `ActiveEraInfo` | = help: the following other types implement trait `parity_scale_codec::MaxEncodedLen`: () (TupleElement0, TupleElement1) (TupleElement0, TupleElement1, TupleElement2) (TupleElement0, TupleElement1, TupleElement2, TupleElement3) (TupleElement0, TupleElement1, TupleElement2, TupleElement3, TupleElement4) (TupleElement0, TupleElement1, TupleElement2, TupleElement3, TupleElement4, TupleElement5) (TupleElement0, TupleElement1, TupleElement2, TupleElement3, TupleElement4, TupleElement5, TupleElement6) (TupleElement0, TupleElement1, TupleElement2, TupleElement3, TupleElement4, TupleElement5, TupleElement6, TupleElement7) and 78 others = note: required because of the requirements on the impl of `StorageInfoTrait` for `frame_support::pallet_prelude::StorageValue<_GeneratedPrefixForStorageActiveEra, ActiveEraInfo>` error[E0277]: the trait bound `Exposure<::AccountId, ::CurrencyBalance>: parity_scale_codec::MaxEncodedLen` is not satisfied --> frame/staking/src/pallet/mod.rs:59:12 | 59 | #[pallet::pallet] | ^^^^^^ the trait `parity_scale_codec::MaxEncodedLen` is not implemented for `Exposure<::AccountId, ::CurrencyBalance>` | = help: the following other types implement trait `parity_scale_codec::MaxEncodedLen`: () (TupleElement0, TupleElement1) (TupleElement0, TupleElement1, TupleElement2) (TupleElement0, TupleElement1, TupleElement2, TupleElement3) (TupleElement0, TupleElement1, TupleElement2, TupleElement3, TupleElement4) (TupleElement0, TupleElement1, TupleElement2, TupleElement3, TupleElement4, TupleElement5) (TupleElement0, TupleElement1, TupleElement2, TupleElement3, TupleElement4, TupleElement5, TupleElement6) (TupleElement0, TupleElement1, TupleElement2, TupleElement3, TupleElement4, TupleElement5, TupleElement6, TupleElement7) and 78 others = note: required because of the requirements on the impl of `StorageInfoTrait` for `frame_support::pallet_prelude::StorageDoubleMap<_GeneratedPrefixForStorageErasStakers, frame_support::Twox64Concat, u32, frame_support::Twox64Concat, ::AccountId, Exposure<::AccountId, ::CurrencyBalance>, frame_support::pallet_prelude::ValueQuery>` error[E0277]: the trait bound `EraRewardPoints<::AccountId>: parity_scale_codec::MaxEncodedLen` is not satisfied --> frame/staking/src/pallet/mod.rs:59:12 | 59 | #[pallet::pallet] | ^^^^^^ the trait `parity_scale_codec::MaxEncodedLen` is not implemented for `EraRewardPoints<::AccountId>` | = help: the following other types implement trait `parity_scale_codec::MaxEncodedLen`: () (TupleElement0, TupleElement1) (TupleElement0, TupleElement1, TupleElement2) (TupleElement0, TupleElement1, TupleElement2, TupleElement3) (TupleElement0, TupleElement1, TupleElement2, TupleElement3, TupleElement4) (TupleElement0, TupleElement1, TupleElement2, TupleElement3, TupleElement4, TupleElement5) (TupleElement0, TupleElement1, TupleElement2, TupleElement3, TupleElement4, TupleElement5, TupleElement6) (TupleElement0, TupleElement1, TupleElement2, TupleElement3, TupleElement4, TupleElement5, TupleElement6, TupleElement7) and 78 others = note: required because of the requirements on the impl of `StorageInfoTrait` for `frame_support::pallet_prelude::StorageMap<_GeneratedPrefixForStorageErasRewardPoints, frame_support::Twox64Concat, u32, EraRewardPoints<::AccountId>, frame_support::pallet_prelude::ValueQuery>` error[E0277]: the trait bound `Forcing: parity_scale_codec::MaxEncodedLen` is not satisfied --> frame/staking/src/pallet/mod.rs:59:12 | 59 | #[pallet::pallet] | ^^^^^^ the trait `parity_scale_codec::MaxEncodedLen` is not implemented for `Forcing` | = help: the following other types implement trait `parity_scale_codec::MaxEncodedLen`: () (TupleElement0, TupleElement1) (TupleElement0, TupleElement1, TupleElement2) (TupleElement0, TupleElement1, TupleElement2, TupleElement3) (TupleElement0, TupleElement1, TupleElement2, TupleElement3, TupleElement4) (TupleElement0, TupleElement1, TupleElement2, TupleElement3, TupleElement4, TupleElement5) (TupleElement0, TupleElement1, TupleElement2, TupleElement3, TupleElement4, TupleElement5, TupleElement6) (TupleElement0, TupleElement1, TupleElement2, TupleElement3, TupleElement4, TupleElement5, TupleElement6, TupleElement7) and 78 others = note: required because of the requirements on the impl of `StorageInfoTrait` for `frame_support::pallet_prelude::StorageValue<_GeneratedPrefixForStorageForceEra, Forcing, frame_support::pallet_prelude::ValueQuery>` error[E0277]: the trait bound `std::vec::Vec::AccountId, ::CurrencyBalance>>: parity_scale_codec::MaxEncodedLen` is not satisfied --> frame/staking/src/pallet/mod.rs:59:12 | 59 | #[pallet::pallet] | ^^^^^^ the trait `parity_scale_codec::MaxEncodedLen` is not implemented for `std::vec::Vec::AccountId, ::CurrencyBalance>>` | = help: the following other types implement trait `parity_scale_codec::MaxEncodedLen`: () (TupleElement0, TupleElement1) (TupleElement0, TupleElement1, TupleElement2) (TupleElement0, TupleElement1, TupleElement2, TupleElement3) (TupleElement0, TupleElement1, TupleElement2, TupleElement3, TupleElement4) (TupleElement0, TupleElement1, TupleElement2, TupleElement3, TupleElement4, TupleElement5) (TupleElement0, TupleElement1, TupleElement2, TupleElement3, TupleElement4, TupleElement5, TupleElement6) (TupleElement0, TupleElement1, TupleElement2, TupleElement3, TupleElement4, TupleElement5, TupleElement6, TupleElement7) and 78 others = note: required because of the requirements on the impl of `StorageInfoTrait` for `frame_support::pallet_prelude::StorageMap<_GeneratedPrefixForStorageUnappliedSlashes, frame_support::Twox64Concat, u32, std::vec::Vec::AccountId, ::CurrencyBalance>>, frame_support::pallet_prelude::ValueQuery>` error[E0277]: the trait bound `std::vec::Vec<(u32, u32)>: parity_scale_codec::MaxEncodedLen` is not satisfied --> frame/staking/src/pallet/mod.rs:59:12 | 59 | #[pallet::pallet] | ^^^^^^ the trait `parity_scale_codec::MaxEncodedLen` is not implemented for `std::vec::Vec<(u32, u32)>` | = help: the following other types implement trait `parity_scale_codec::MaxEncodedLen`: () (TupleElement0, TupleElement1) (TupleElement0, TupleElement1, TupleElement2) (TupleElement0, TupleElement1, TupleElement2, TupleElement3) (TupleElement0, TupleElement1, TupleElement2, TupleElement3, TupleElement4) (TupleElement0, TupleElement1, TupleElement2, TupleElement3, TupleElement4, TupleElement5) (TupleElement0, TupleElement1, TupleElement2, TupleElement3, TupleElement4, TupleElement5, TupleElement6) (TupleElement0, TupleElement1, TupleElement2, TupleElement3, TupleElement4, TupleElement5, TupleElement6, TupleElement7) and 78 others = note: required because of the requirements on the impl of `StorageInfoTrait` for `frame_support::pallet_prelude::StorageValue<_GeneratedPrefixForStorageBondedEras, std::vec::Vec<(u32, u32)>, frame_support::pallet_prelude::ValueQuery>` error[E0277]: the trait bound `slashing::SlashingSpans: parity_scale_codec::MaxEncodedLen` is not satisfied --> frame/staking/src/pallet/mod.rs:59:12 | 59 | #[pallet::pallet] | ^^^^^^ the trait `parity_scale_codec::MaxEncodedLen` is not implemented for `slashing::SlashingSpans` | = help: the following other types implement trait `parity_scale_codec::MaxEncodedLen`: () (TupleElement0, TupleElement1) (TupleElement0, TupleElement1, TupleElement2) (TupleElement0, TupleElement1, TupleElement2, TupleElement3) (TupleElement0, TupleElement1, TupleElement2, TupleElement3, TupleElement4) (TupleElement0, TupleElement1, TupleElement2, TupleElement3, TupleElement4, TupleElement5) (TupleElement0, TupleElement1, TupleElement2, TupleElement3, TupleElement4, TupleElement5, TupleElement6) (TupleElement0, TupleElement1, TupleElement2, TupleElement3, TupleElement4, TupleElement5, TupleElement6, TupleElement7) and 78 others = note: required because of the requirements on the impl of `StorageInfoTrait` for `frame_support::pallet_prelude::StorageMap<_GeneratedPrefixForStorageSlashingSpans, frame_support::Twox64Concat, ::AccountId, slashing::SlashingSpans>` error[E0277]: the trait bound `SpanRecord<::CurrencyBalance>: parity_scale_codec::MaxEncodedLen` is not satisfied --> frame/staking/src/pallet/mod.rs:59:12 | 59 | #[pallet::pallet] | ^^^^^^ the trait `parity_scale_codec::MaxEncodedLen` is not implemented for `SpanRecord<::CurrencyBalance>` | = help: the following other types implement trait `parity_scale_codec::MaxEncodedLen`: () (TupleElement0, TupleElement1) (TupleElement0, TupleElement1, TupleElement2) (TupleElement0, TupleElement1, TupleElement2, TupleElement3) (TupleElement0, TupleElement1, TupleElement2, TupleElement3, TupleElement4) (TupleElement0, TupleElement1, TupleElement2, TupleElement3, TupleElement4, TupleElement5) (TupleElement0, TupleElement1, TupleElement2, TupleElement3, TupleElement4, TupleElement5, TupleElement6) (TupleElement0, TupleElement1, TupleElement2, TupleElement3, TupleElement4, TupleElement5, TupleElement6, TupleElement7) and 78 others = note: required because of the requirements on the impl of `StorageInfoTrait` for `frame_support::pallet_prelude::StorageMap<_GeneratedPrefixForStorageSpanSlash, frame_support::Twox64Concat, (::AccountId, u32), SpanRecord<::CurrencyBalance>, frame_support::pallet_prelude::ValueQuery>` error[E0277]: the trait bound `std::vec::Vec<(u32, bool)>: parity_scale_codec::MaxEncodedLen` is not satisfied --> frame/staking/src/pallet/mod.rs:59:12 | 59 | #[pallet::pallet] | ^^^^^^ the trait `parity_scale_codec::MaxEncodedLen` is not implemented for `std::vec::Vec<(u32, bool)>` | = help: the following other types implement trait `parity_scale_codec::MaxEncodedLen`: () (TupleElement0, TupleElement1) (TupleElement0, TupleElement1, TupleElement2) (TupleElement0, TupleElement1, TupleElement2, TupleElement3) (TupleElement0, TupleElement1, TupleElement2, TupleElement3, TupleElement4) (TupleElement0, TupleElement1, TupleElement2, TupleElement3, TupleElement4, TupleElement5) (TupleElement0, TupleElement1, TupleElement2, TupleElement3, TupleElement4, TupleElement5, TupleElement6) (TupleElement0, TupleElement1, TupleElement2, TupleElement3, TupleElement4, TupleElement5, TupleElement6, TupleElement7) and 78 others = note: required because of the requirements on the impl of `StorageInfoTrait` for `frame_support::pallet_prelude::StorageValue<_GeneratedPrefixForStorageOffendingValidators, std::vec::Vec<(u32, bool)>, frame_support::pallet_prelude::ValueQuery>` error[E0277]: the trait bound `Releases: parity_scale_codec::MaxEncodedLen` is not satisfied --> frame/staking/src/pallet/mod.rs:59:12 | 59 | #[pallet::pallet] | ^^^^^^ the trait `parity_scale_codec::MaxEncodedLen` is not implemented for `Releases` | = help: the following other types implement trait `parity_scale_codec::MaxEncodedLen`: () (TupleElement0, TupleElement1) (TupleElement0, TupleElement1, TupleElement2) (TupleElement0, TupleElement1, TupleElement2, TupleElement3) (TupleElement0, TupleElement1, TupleElement2, TupleElement3, TupleElement4) (TupleElement0, TupleElement1, TupleElement2, TupleElement3, TupleElement4, TupleElement5) (TupleElement0, TupleElement1, TupleElement2, TupleElement3, TupleElement4, TupleElement5, TupleElement6) (TupleElement0, TupleElement1, TupleElement2, TupleElement3, TupleElement4, TupleElement5, TupleElement6, TupleElement7) and 78 others = note: required because of the requirements on the impl of `StorageInfoTrait` for `frame_support::pallet_prelude::StorageValue<_GeneratedPrefixForStorageStorageVersion, Releases, frame_support::pallet_prelude::ValueQuery>` For more information about this error, try `rustc --explain E0277`. error: could not compile `pallet-staking` due to 15 previous errors ```

• Invulnerables
• StakingLedger
• Payee
• Validators / ValidatorPrefs
• Nominators / Nominations
• ErasStakers / ErasStakersClipped / Exposure
• ActiveEraInfo
• ErasRewardPoints
• Forcing
• UnappliedSlashes
• BondedEras
• SlashingSpans
• OffendingValidators
• Releases

I categorize these into 4 groups:

1. [Done] Trivial ones. These are generally 1 liner changes for the type to derive(MaxEncodedLen). This list includes:
2. [Done] Bounded by HistoryDepth. This includes only StakingLedger. Also, a number of storage maps and double maps have an invariant that the number of their keys should never exceed HistoryDepth. We should detect these, and make sure they are always respected (use try_state).
3. [Done] Bounding by MaxActiveValidators. These are storage item who's bound is missing because we don't enforce a bound on the maximum number of active validators.
   • This will eventually leak into election-provider-mutli-phase, and staking would express: type ElectionProvider<MaxWinners = Self::MaxActiveValidators>
   • This will eventually help staking pallet bound the number of validators into session as well. In other words
   • @Doordashcon started this with https://github.com/paritytech/substrate/pull/11967 and https://github.com/paritytech/substrate/pull/12125, but I think we should start from scratch based on my draft in https://github.com/paritytech/substrate/tree/kiz-properly-bound-staking-validators.
4. [Weakly bounded in this PR] Bounding by maximum number of active exposed nominators per validator, i.e. MaxBackersPerWinner. @ggwpez started doing this in paritytech/substrate#11935, we need someone to finish it.
5. Slashing related storage items. These are the more scary ones, and I am not sure if and how we should bound them. The slashing code needs an overhaul in any case.

So, these are the bounds we know:

• MaxActiveValidators:
  • Invulnerables
  • ErasRewardPoints
• MaxBackersPerWinner
  • ErasStakers / ErasStakersClipped / Exposure
• HistoryDepth
  • StakingLedger
• Trivial
  • ActiveEraInfo
  • Forcing
  • Payee
  • Validators / ValidatorPrefs
  • Nominators / Nominations -Releases
• Slashing, unknown
  • UnappliedSlashes
  • BondedEras
  • SlashingSpans
  • OffendingValidators

It is hard to predict all of these without actually writing the entire code. I might be wrong in some places.

• An easy action item, which I am happy to mentor for someone external is to take care of all the trivial ones.
• I am not sure about MaxActiveValidators. I might prefer doing it myself since it is rather important and touches a few pallets. Nonetheless, I am grateful for @Doordashcon's effort here so far and will acknowledge it.
• MaxBackersPerWinner needs completion by me and @ggwpez
• Slashing is a project of its own.

[Doordashcon]

Hello @kianenigma I'd like to keep working on MaxActiveValidators with guidance from you or anyone from your team.

As for the trivial ones, I'll look into that as well if that's alright with you.

[kianenigma]

Hello @kianenigma I'd like to keep working on MaxActiveValidators with guidance from you or anyone from your team.

Then you can close the existing PRs, and build on top of https://github.com/paritytech/substrate/commit/4682f3fbda7bce7e45d8efa06e5817e93368e3d8, thanks!

[kianenigma]

@Doordashcon please note that @Ank4n will be looking into HistoryDepth and generally push forward this tracking issue.

[Doordashcon]

Dropping this

[kianenigma]

This should be done as a part of https://github.com/paritytech/polkadot-sdk/issues/2199.

@Ank4n @gpestana please double-check that the above assumption is true. In this case, I don't see any room for mentoring here anymore.

[Ank4n]

Updated list of unbounded storage items

• Invulnerables: Initial set of validators. Ideally not more than 4. Can be bounded by some number in the range (4-10).
• [x] ErasStakers: This is deprecated and will be removed once 84 eras have passed after runtime (polkadot and kusama) is upgraded to 1.5.0. Handled in https://github.com/paritytech/polkadot-sdk/pull/5986.
• [x] ErasStakersClipped: Same as ErasStakers. Handled in https://github.com/paritytech/polkadot-sdk/pull/5986.
• ErasStakersPaged: Will be bounded once we reduce exposure page size to a low value (like 128 or 32).
• ClaimedRewards: Unbounded exposure pages. We could bound it to MaxNominatorsCount/page_size.
• ErasRewardPoints: unbounded validator count. Could be bounded to ValidatorCount.
• UnappliedSlashes: Need to bound reporters and pagify stakers to be slashed. Unbounded count of unapplied slashes. Can be bounded by Slash defer duration.
• BondedEras: Can be bounded by bounding duration.
• SlashingSpans: Slashing span is one or more eras. Can be bounded by unbonding duration.
• OffendingValidators: Unbounded by count of offending validators. Can be bounded by desired ValidatorCount.

Lot of the bounds that we need are storage items. We should probably convert them to config constants.