Crate sp_npos_elections

A set of election algorithms to be used with a substrate runtime, typically within the staking sub-system. Notable implementation include:

• seq_phragmen: Implements the Phragmén Sequential Method. An un-ranked, relatively fast election method that ensures PJR, but does not provide a constant factor approximation of the maximin problem.
• phragmms: Implements a hybrid approach inspired by Phragmén which is executed faster but it can achieve a constant factor approximation of the maximin problem, similar to that of the MMS algorithm.
• balance: Implements the star balancing algorithm. This iterative process can push a solution toward being more “balanced”, which in turn can increase its score.

Terminology

This crate uses context-independent words, not to be confused with staking. This is because the election algorithms of this crate, while designed for staking, can be used in other contexts as well.

Voter: The entity casting some votes to a number of Targets. This is the same as Nominator in the context of staking. Target: The entities eligible to be voted upon. This is the same as Validator in the context of staking. Edge: A mapping from a Voter to a Target.

The goal of an election algorithm is to provide an ElectionResult. A data composed of:

• winners: A flat list of identifiers belonging to those who have won the election, usually ordered in some meaningful way. They are zipped with their total backing stake.
• assignment: A mapping from each voter to their winner-only targets, zipped with a ration denoting the amount of support given to that particular target.

// the winners.
let winners = vec![(1, 100), (2, 50)];
let assignments = vec![
    // A voter, giving equal backing to both 1 and 2.
    Assignment {
		who: 10,
		distribution: vec![(1, Perbill::from_percent(50)), (2, Perbill::from_percent(50))],
	},
    // A voter, Only backing 1.
    Assignment { who: 20, distribution: vec![(1, Perbill::from_percent(100))] },
];

// the combination of the two makes the election result.
let election_result = ElectionResult { winners, assignments };

The Assignment field of the election result is voter-major, i.e. it is from the perspective of the voter. The struct that represents the opposite is called a Support. This struct is usually accessed in a map-like manner, i.e. keyed by voters, therefor it is stored as a mapping called SupportMap.

Moreover, the support is built from absolute backing values, not ratios like the example above. A struct similar to Assignment that has stake value instead of ratios is called an StakedAssignment.

More information can be found at: https://arxiv.org/abs/2004.12990

Re-exports

pub use balancing::*;

pub use helpers::*;

pub use phragmen::*;

pub use phragmms::*;

pub use pjr::*;

pub use reduce::reduce;

pub use traits::IdentifierT;

pub use traits::NposSolution;

pub use traits::PerThing128;

pub use traits::__OrInvalidIndex;

Modules

balancing

Balancing algorithm implementation.

helpers

Helper methods for npos-elections.

node

(very) Basic implementation of a graph node used in the reduce algorithm.

phragmen

Implementation of the sequential-phragmen election method.

phragmms

Implementation of the PhragMMS method.

pjr

Implements functions and interfaces to check solutions for being t-PJR.

reduce

Rust implementation of the Phragmén reduce algorithm. This can be used by any off chain application to reduce cycles from the edge assignment, which will result in smaller size.

traits

Traits for the npos-election operations.

Macros

generate_solution_type

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<_>.

Structs

Assignment

A voter’s stake assignment among a set of targets, represented as ratios.

Candidate

A candidate entity for the election.

Edge

A vote being casted by a Voter to a Candidate is an Edge.

ElectionResult

Final result of the election.

IndexAssignment

The IndexAssignment type is an intermediate between the assignments list (&[Assignment<T>]) and SolutionOf<T>.

StakedAssignment

A voter’s stake assignment among a set of targets, represented as absolute values in the scale of ExtendedBalance.

Support

A structure to demonstrate the election result from the perspective of the candidate, i.e. how much support each candidate is receiving.

Voter

A voter entity.

Enums

Error

The errors that might occur in the this crate and solution-type.

Traits

EvaluateSupport

Extension trait for evaluating a support map or vector.

FlattenSupportMap

Helper trait to convert from a support map to a flat support vector.

TupleRef

A common wrapper trait for both (&A, &B) and &(A, B).

Functions

is_score_better

Compares two sets of election scores based on desirability and returns true if this is better than that.

setup_inputs

Converts raw inputs to types used in this crate.

to_support_map

Build the support map from the winners and assignments.

to_supports

Same as to_support_map except it calls FlattenSupportMap on top of the result to return a flat vector.

Type Definitions

CandidatePtr

A pointer to a candidate struct with interior mutability.

ElectionScore

The score of an assignment. This can be computed from the support map via EvaluateSupport::evaluate.

ExtendedBalance

A type in which performing operations on vote weights are safe.

IndexAssignmentOf

A type alias for IndexAssignment made from [crate::Solution].

SupportMap

Linkage from a winner to their Support.

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.

WithApprovalOf

A winner, with their respective approval stake.