Crate frame_election_provider_support

Primitive traits for providing election functionality.

This crate provides two traits that could interact to enable extensible election functionality within FRAME pallets.

Something that will provide the functionality of election will implement ElectionProvider and its parent-trait ElectionProviderBase, whilst needing an associated ElectionProviderBase::DataProvider, which needs to be fulfilled by an entity implementing ElectionDataProvider. Most often, the data provider is the receiver of the election, resulting in a diagram as below:

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

It could also be possible that a third party pallet (C), provides the data of election to an election provider (B), which then passes the election result to another pallet (A).

Election Types

Typically, two types of elections exist:

1. Stateless: Election data is provided, and the election result is immediately ready.
2. Stateful: Election data is is queried ahead of time, and the election result might be ready some number of blocks in the future.

To accommodate both type of elections in one trait, the traits lean toward stateful election, as it is more general than the stateless. This is why ElectionProvider::elect has no parameters. All value and type parameter must be provided by the ElectionDataProvider trait, even if the election happens immediately.

Election Data

The data associated with an election, essentially what the ElectionDataProvider must convey is as follows:

1. A list of voters, with their stake.
2. A list of targets (i.e. candidates).
3. A number of desired targets to be elected (i.e. winners)

In addition to that, the ElectionDataProvider must also hint ElectionProvider at when the next election might happen (ElectionDataProvider::next_election_prediction). A stateless election provider would probably ignore this. A stateful election provider can use this to prepare the election result in advance.

Nonetheless, an ElectionProvider shan’t rely on this and should preferably provide some means of fallback election as well, in case the elect was called immaturely early.

Example

type AccountId = u64;
type Balance = u64;
type BlockNumber = u32;

mod data_provider_mod {
    use super::*;

    pub trait Config: Sized {
        type ElectionProvider: ElectionProvider<
            AccountId = AccountId,
            BlockNumber = BlockNumber,
            DataProvider = Pallet<Self>,
        >;
    }

    pub struct Pallet<T: Config>(std::marker::PhantomData<T>);

    impl<T: Config> ElectionDataProvider for Pallet<T> {
        type AccountId = AccountId;
        type BlockNumber = BlockNumber;
        type MaxVotesPerVoter = ConstU32<1>;

        fn desired_targets() -> data_provider::Result<u32> {
            Ok(1)
        }
        fn electing_voters(bounds: DataProviderBounds)
          -> data_provider::Result<Vec<VoterOf<Self>>>
        {
            Ok(Default::default())
        }
        fn electable_targets(bounds: DataProviderBounds) -> data_provider::Result<Vec<AccountId>> {
            Ok(vec![10, 20, 30])
        }
        fn next_election_prediction(now: BlockNumber) -> BlockNumber {
            0
        }
    }
}


mod generic_election_provider {
    use super::*;

    pub struct GenericElectionProvider<T: Config>(std::marker::PhantomData<T>);

    pub trait Config {
        type DataProvider: ElectionDataProvider<AccountId=AccountId, BlockNumber = BlockNumber>;
    }

    impl<T: Config> ElectionProviderBase for GenericElectionProvider<T> {
        type AccountId = AccountId;
        type BlockNumber = BlockNumber;
        type Error = &'static str;
        type DataProvider = T::DataProvider;
        type MaxWinners = ConstU32<{ u32::MAX }>;

    }

    impl<T: Config> ElectionProvider for GenericElectionProvider<T> {
        fn ongoing() -> bool { false }
        fn elect() -> Result<BoundedSupportsOf<Self>, Self::Error> {
            Self::DataProvider::electable_targets(DataProviderBounds::default())
                .map_err(|_| "failed to elect")
                .map(|t| bounded_vec![(t[0], Support::default())])
        }
    }
}

mod runtime {
    use super::generic_election_provider;
    use super::data_provider_mod;
    use super::AccountId;

    struct Runtime;
    impl generic_election_provider::Config for Runtime {
        type DataProvider = data_provider_mod::Pallet<Runtime>;
    }

    impl data_provider_mod::Config for Runtime {
        type ElectionProvider = generic_election_provider::GenericElectionProvider<Runtime>;
    }

}

Re-exports

• pub use bounds::DataProviderBounds;
• pub use traits::NposSolution;
• pub use weights::WeightInfo;

Modules

• bounds
  Types and helpers to define and handle election bounds.
• data_provider
  Types that are used by the data provider trait.
• onchain
  An implementation of ElectionProvider that uses an NposSolver to do the election. As the name suggests, this is meant to be used onchain. Given how heavy the calculations are, please be careful when using it onchain.
• traits
  Traits for the election operations.
• weights
  Autogenerated weights for pallet_election_provider_support_benchmarking

Macros

• _runtime_benchmarks_enabled
• _runtime_benchmarks_or_std_enabled
• generate_solution_type
  Re-export the solution generation macro. Generates a struct to store the election result in a small/compact way. This can encode a structure which is the equivalent of a sp_npos_elections::Assignment<_>.
• runtime_benchmarks_enabled
  Enable/disable the given code depending on feature = "runtime-benchmarks" being enabled for the crate or not.
• runtime_benchmarks_or_std_enabled
  Enable/disable the given code depending on any(feature = "runtime-benchmarks", feature = "std") being enabled for the crate or not.

Structs

• Assignment
  A voter’s stake assignment among a set of targets, represented as ratios.
• BalancingConfig
  Utility struct to group parameters for the balancing algorithm.
• BoundedVec
  A bounded vector.
• ElectionResult
  Final result of the election.
• IndexAssignment
  The IndexAssignment type is an intermediate between the assignments list (&[Assignment<T>]) and SolutionOf<T>.
• NoElection
  An election provider that does nothing whatsoever.
• PhragMMS
  A wrapper for [sp_npos_elections::phragmms()] that implements NposSolver. See the documentation of [sp_npos_elections::phragmms()] for more info.
• SequentialPhragmen
  A wrapper for [sp_npos_elections::seq_phragmen] that implements NposSolver. See the documentation of [sp_npos_elections::seq_phragmen] for more info.
• Support
  A structure to demonstrate the election result from the perspective of the candidate, i.e. how much support each candidate is receiving.
• Weight

Enums

• Error
  The errors that might occur in this crate and frame-election-provider-solution-type.

Traits

• Decode
  Trait that allows zero-copy read of value-references from slices in LE format.
• ElectionDataProvider
  Something that can provide the data to an ElectionProvider.
• ElectionProvider
  Elect a new set of winners, bounded by MaxWinners.
• ElectionProviderBase
  Base trait for types that can provide election
• Encode
  Trait that allows zero-copy write of value-references to slices in LE format.
• Get
  A trait for querying a single value from a type.
• IdentifierT
  an aggregator trait for a generic type of a voter/target identifier. This usually maps to substrate’s account id.
• InstantElectionProvider
  A (almost) marker trait that signifies an election provider as working synchronously. i.e. being instant.
• NposSolver
  Something that can compute the result to an NPoS solution.
• PerThing
  Re-export some type as they are used in the interface. Something that implements a fixed point ration with an arbitrary granularity X, as parts per X.
• PerThing128
  Aggregator trait for a PerThing that can be multiplied by u128 (ExtendedBalance).
• ScoreProvider
  Something that can provide the Score of an account. Similar to ElectionProvider and ElectionDataProvider, this should typically be implementing by whoever is supposed to use SortedListProvider.
• SortedListProvider
  A utility trait for something to implement ElectionDataProvider in a sensible way.

Type Aliases

• BoundedSupports
  Same as Supports but bounded by B.
• BoundedSupportsOf
  Same as BoundedSupports but parameterized by a ElectionProviderBase.
• ExtendedBalance
  A type in which performing operations on vote weights are safe.
• IndexAssignmentOf
  A type alias for IndexAssignment made from NposSolution.
• Supports
  A target-major representation of the the election outcome.
• VoteWeight
  A type which is used in the API of this crate as a numeric weight of a vote, most often the stake of the voter. It is always converted to ExtendedBalance for computation.
• Voter
  A voter, at the level of abstraction of this crate.
• VoterOf
  Same as Voter, but parameterized by an ElectionDataProvider.

Derive Macros

• Decode
  Derive parity_scale_codec::Decode and for struct and enum.
• Encode
  Derive parity_scale_codec::Encode and parity_scale_codec::EncodeLike for struct and enum.