frame_election_provider_support/
onchain.rs

1// This file is part of Substrate.
2
3// Copyright (C) Parity Technologies (UK) Ltd.
4// SPDX-License-Identifier: Apache-2.0
5
6// Licensed under the Apache License, Version 2.0 (the "License");
7// you may not use this file except in compliance with the License.
8// You may obtain a copy of the License at
9//
10// 	http://www.apache.org/licenses/LICENSE-2.0
11//
12// Unless required by applicable law or agreed to in writing, software
13// distributed under the License is distributed on an "AS IS" BASIS,
14// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
15// See the License for the specific language governing permissions and
16// limitations under the License.
17
18//! An implementation of [`ElectionProvider`] that uses an `NposSolver` to do the election. As the
19//! name suggests, this is meant to be used onchain. Given how heavy the calculations are, please be
20//! careful when using it onchain.
21
22use crate::{
23	bounds::{DataProviderBounds, ElectionBounds, ElectionBoundsBuilder},
24	BoundedSupportsOf, Debug, ElectionDataProvider, ElectionProvider, ElectionProviderBase,
25	InstantElectionProvider, NposSolver, WeightInfo,
26};
27use alloc::collections::btree_map::BTreeMap;
28use core::marker::PhantomData;
29use frame_support::{dispatch::DispatchClass, traits::Get};
30use sp_npos_elections::{
31	assignment_ratio_to_staked_normalized, to_supports, BoundedSupports, ElectionResult, VoteWeight,
32};
33
34/// Errors of the on-chain election.
35#[derive(Eq, PartialEq, Debug)]
36pub enum Error {
37	/// An internal error in the NPoS elections crate.
38	NposElections(sp_npos_elections::Error),
39	/// Errors from the data provider.
40	DataProvider(&'static str),
41	/// Configurational error caused by `desired_targets` requested by data provider exceeding
42	/// `MaxWinners`.
43	TooManyWinners,
44}
45
46impl From<sp_npos_elections::Error> for Error {
47	fn from(e: sp_npos_elections::Error) -> Self {
48		Error::NposElections(e)
49	}
50}
51
52/// A simple on-chain implementation of the election provider trait.
53///
54/// This implements both `ElectionProvider` and `InstantElectionProvider`.
55///
56/// This type has some utilities to make it safe. Nonetheless, it should be used with utmost care. A
57/// thoughtful value must be set as [`Config::Bounds`] to ensure the size of the input is sensible.
58pub struct OnChainExecution<T: Config>(PhantomData<T>);
59
60#[deprecated(note = "use OnChainExecution, which is bounded by default")]
61pub type BoundedExecution<T> = OnChainExecution<T>;
62
63/// Configuration trait for an onchain election execution.
64pub trait Config {
65	/// Needed for weight registration.
66	type System: frame_system::Config;
67
68	/// `NposSolver` that should be used, an example would be `PhragMMS`.
69	type Solver: NposSolver<
70		AccountId = <Self::System as frame_system::Config>::AccountId,
71		Error = sp_npos_elections::Error,
72	>;
73
74	/// Something that provides the data for election.
75	type DataProvider: ElectionDataProvider<
76		AccountId = <Self::System as frame_system::Config>::AccountId,
77		BlockNumber = frame_system::pallet_prelude::BlockNumberFor<Self::System>,
78	>;
79
80	/// Weight information for extrinsics in this pallet.
81	type WeightInfo: WeightInfo;
82
83	/// Upper bound on maximum winners from electable targets.
84	///
85	/// As noted in the documentation of [`ElectionProviderBase::MaxWinners`], this value should
86	/// always be more than `DataProvider::desired_target`.
87	type MaxWinners: Get<u32>;
88
89	/// Elections bounds, to use when calling into [`Config::DataProvider`]. It might be overwritten
90	/// in the `InstantElectionProvider` impl.
91	type Bounds: Get<ElectionBounds>;
92}
93
94/// Same as `BoundedSupportsOf` but for `onchain::Config`.
95pub type OnChainBoundedSupportsOf<E> = BoundedSupports<
96	<<E as Config>::System as frame_system::Config>::AccountId,
97	<E as Config>::MaxWinners,
98>;
99
100fn elect_with_input_bounds<T: Config>(
101	bounds: ElectionBounds,
102) -> Result<OnChainBoundedSupportsOf<T>, Error> {
103	let (voters, targets) = T::DataProvider::electing_voters(bounds.voters)
104		.and_then(|voters| Ok((voters, T::DataProvider::electable_targets(bounds.targets)?)))
105		.map_err(Error::DataProvider)?;
106
107	let desired_targets = T::DataProvider::desired_targets().map_err(Error::DataProvider)?;
108
109	if desired_targets > T::MaxWinners::get() {
110		// early exit
111		return Err(Error::TooManyWinners)
112	}
113
114	let voters_len = voters.len() as u32;
115	let targets_len = targets.len() as u32;
116
117	let stake_map: BTreeMap<_, _> = voters
118		.iter()
119		.map(|(validator, vote_weight, _)| (validator.clone(), *vote_weight))
120		.collect();
121
122	let stake_of = |w: &<T::System as frame_system::Config>::AccountId| -> VoteWeight {
123		stake_map.get(w).cloned().unwrap_or_default()
124	};
125
126	let ElectionResult { winners: _, assignments } =
127		T::Solver::solve(desired_targets as usize, targets, voters).map_err(Error::from)?;
128
129	let staked = assignment_ratio_to_staked_normalized(assignments, &stake_of)?;
130
131	let weight = T::Solver::weight::<T::WeightInfo>(
132		voters_len,
133		targets_len,
134		<T::DataProvider as ElectionDataProvider>::MaxVotesPerVoter::get(),
135	);
136	frame_system::Pallet::<T::System>::register_extra_weight_unchecked(
137		weight,
138		DispatchClass::Mandatory,
139	);
140
141	// defensive: Since npos solver returns a result always bounded by `desired_targets`, this is
142	// never expected to happen as long as npos solver does what is expected for it to do.
143	let supports: OnChainBoundedSupportsOf<T> =
144		to_supports(&staked).try_into().map_err(|_| Error::TooManyWinners)?;
145
146	Ok(supports)
147}
148
149impl<T: Config> ElectionProviderBase for OnChainExecution<T> {
150	type AccountId = <T::System as frame_system::Config>::AccountId;
151	type BlockNumber = frame_system::pallet_prelude::BlockNumberFor<T::System>;
152	type Error = Error;
153	type MaxWinners = T::MaxWinners;
154	type DataProvider = T::DataProvider;
155}
156
157impl<T: Config> InstantElectionProvider for OnChainExecution<T> {
158	fn instant_elect(
159		forced_input_voters_bounds: DataProviderBounds,
160		forced_input_targets_bounds: DataProviderBounds,
161	) -> Result<BoundedSupportsOf<Self>, Self::Error> {
162		let elections_bounds = ElectionBoundsBuilder::from(T::Bounds::get())
163			.voters_or_lower(forced_input_voters_bounds)
164			.targets_or_lower(forced_input_targets_bounds)
165			.build();
166
167		elect_with_input_bounds::<T>(elections_bounds)
168	}
169}
170
171impl<T: Config> ElectionProvider for OnChainExecution<T> {
172	fn ongoing() -> bool {
173		false
174	}
175
176	fn elect() -> Result<BoundedSupportsOf<Self>, Self::Error> {
177		let election_bounds = ElectionBoundsBuilder::from(T::Bounds::get()).build();
178		elect_with_input_bounds::<T>(election_bounds)
179	}
180}
181
182#[cfg(test)]
183mod tests {
184	use super::*;
185	use crate::{ElectionProvider, PhragMMS, SequentialPhragmen};
186	use frame_support::{assert_noop, derive_impl, parameter_types};
187	use sp_npos_elections::Support;
188	use sp_runtime::Perbill;
189	type AccountId = u64;
190	type Nonce = u64;
191	type BlockNumber = u64;
192
193	pub type Header = sp_runtime::generic::Header<BlockNumber, sp_runtime::traits::BlakeTwo256>;
194	pub type UncheckedExtrinsic = sp_runtime::generic::UncheckedExtrinsic<AccountId, (), (), ()>;
195	pub type Block = sp_runtime::generic::Block<Header, UncheckedExtrinsic>;
196
197	frame_support::construct_runtime!(
198		pub enum Runtime {
199			System: frame_system,
200		}
201	);
202
203	#[derive_impl(frame_system::config_preludes::TestDefaultConfig)]
204	impl frame_system::Config for Runtime {
205		type SS58Prefix = ();
206		type BaseCallFilter = frame_support::traits::Everything;
207		type RuntimeOrigin = RuntimeOrigin;
208		type Nonce = Nonce;
209		type RuntimeCall = RuntimeCall;
210		type Hash = sp_core::H256;
211		type Hashing = sp_runtime::traits::BlakeTwo256;
212		type AccountId = AccountId;
213		type Lookup = sp_runtime::traits::IdentityLookup<Self::AccountId>;
214		type Block = Block;
215		type RuntimeEvent = ();
216		type BlockHashCount = ();
217		type DbWeight = ();
218		type BlockLength = ();
219		type BlockWeights = ();
220		type Version = ();
221		type PalletInfo = PalletInfo;
222		type AccountData = ();
223		type OnNewAccount = ();
224		type OnKilledAccount = ();
225		type SystemWeightInfo = ();
226		type OnSetCode = ();
227		type MaxConsumers = frame_support::traits::ConstU32<16>;
228	}
229
230	struct PhragmenParams;
231	struct PhragMMSParams;
232
233	parameter_types! {
234		pub static MaxWinners: u32 = 10;
235		pub static DesiredTargets: u32 = 2;
236		pub static Bounds: ElectionBounds = ElectionBoundsBuilder::default().voters_count(600.into()).targets_count(400.into()).build();
237	}
238
239	impl Config for PhragmenParams {
240		type System = Runtime;
241		type Solver = SequentialPhragmen<AccountId, Perbill>;
242		type DataProvider = mock_data_provider::DataProvider;
243		type WeightInfo = ();
244		type MaxWinners = MaxWinners;
245		type Bounds = Bounds;
246	}
247
248	impl Config for PhragMMSParams {
249		type System = Runtime;
250		type Solver = PhragMMS<AccountId, Perbill>;
251		type DataProvider = mock_data_provider::DataProvider;
252		type WeightInfo = ();
253		type MaxWinners = MaxWinners;
254		type Bounds = Bounds;
255	}
256
257	mod mock_data_provider {
258		use frame_support::traits::ConstU32;
259		use sp_runtime::bounded_vec;
260
261		use super::*;
262		use crate::{data_provider, VoterOf};
263
264		pub struct DataProvider;
265		impl ElectionDataProvider for DataProvider {
266			type AccountId = AccountId;
267			type BlockNumber = BlockNumber;
268			type MaxVotesPerVoter = ConstU32<2>;
269			fn electing_voters(_: DataProviderBounds) -> data_provider::Result<Vec<VoterOf<Self>>> {
270				Ok(vec![
271					(1, 10, bounded_vec![10, 20]),
272					(2, 20, bounded_vec![30, 20]),
273					(3, 30, bounded_vec![10, 30]),
274				])
275			}
276
277			fn electable_targets(_: DataProviderBounds) -> data_provider::Result<Vec<AccountId>> {
278				Ok(vec![10, 20, 30])
279			}
280
281			fn desired_targets() -> data_provider::Result<u32> {
282				Ok(DesiredTargets::get())
283			}
284
285			fn next_election_prediction(_: BlockNumber) -> BlockNumber {
286				0
287			}
288		}
289	}
290
291	#[test]
292	fn onchain_seq_phragmen_works() {
293		sp_io::TestExternalities::new_empty().execute_with(|| {
294			assert_eq!(
295				<OnChainExecution::<PhragmenParams> as ElectionProvider>::elect().unwrap(),
296				vec![
297					(10, Support { total: 25, voters: vec![(1, 10), (3, 15)] }),
298					(30, Support { total: 35, voters: vec![(2, 20), (3, 15)] })
299				]
300			);
301		})
302	}
303
304	#[test]
305	fn too_many_winners_when_desired_targets_exceed_max_winners() {
306		sp_io::TestExternalities::new_empty().execute_with(|| {
307			// given desired targets larger than max winners
308			DesiredTargets::set(10);
309			MaxWinners::set(9);
310
311			assert_noop!(
312				<OnChainExecution::<PhragmenParams> as ElectionProvider>::elect(),
313				Error::TooManyWinners,
314			);
315		})
316	}
317
318	#[test]
319	fn onchain_phragmms_works() {
320		sp_io::TestExternalities::new_empty().execute_with(|| {
321			assert_eq!(
322				<OnChainExecution::<PhragMMSParams> as ElectionProvider>::elect().unwrap(),
323				vec![
324					(10, Support { total: 25, voters: vec![(1, 10), (3, 15)] }),
325					(30, Support { total: 35, voters: vec![(2, 20), (3, 15)] })
326				]
327			);
328		})
329	}
330}
frame_election_provider_support/onchain.rs

frame_election_provider_support/
onchain.rs
