reduce/
common.rs

Help
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//! Common fuzzing utils.
19
20// Each function will be used based on which fuzzer binary is being used.
21#![allow(dead_code)]
22
23use rand::{self, seq::SliceRandom, Rng, RngCore};
24use sp_npos_elections::{phragmms, seq_phragmen, BalancingConfig, ElectionResult, VoteWeight};
25use sp_runtime::Perbill;
26use std::collections::{BTreeMap, HashSet};
27
28/// converts x into the range [a, b] in a pseudo-fair way.
29pub fn to_range(x: usize, a: usize, b: usize) -> usize {
30	// does not work correctly if b < 2 * a
31	assert!(b >= 2 * a);
32	let collapsed = x % b;
33	if collapsed >= a {
34		collapsed
35	} else {
36		collapsed + a
37	}
38}
39
40pub enum ElectionType {
41	Phragmen(Option<BalancingConfig>),
42	Phragmms(Option<BalancingConfig>),
43}
44
45pub type AccountId = u64;
46
47/// Generate a set of inputs suitable for fuzzing an election algorithm
48///
49/// Given parameters governing how many candidates and voters should exist, generates a voting
50/// scenario suitable for fuzz-testing an election algorithm.
51///
52/// The returned candidate list is sorted. This sorting property should not affect the result of the
53/// calculation.
54///
55/// The returned voters list is sorted. This enables binary searching for a particular voter by
56/// account id. This sorting property should not affect the results of the calculation.
57///
58/// Each voter's selection of candidates to vote for is sorted.
59///
60/// Note that this does not generate balancing parameters.
61pub fn generate_random_npos_inputs(
62	candidate_count: usize,
63	voter_count: usize,
64	mut rng: impl Rng,
65) -> (usize, Vec<AccountId>, Vec<(AccountId, VoteWeight, Vec<AccountId>)>) {
66	// cache for fast generation of unique candidate and voter ids
67	let mut used_ids = HashSet::with_capacity(candidate_count + voter_count);
68
69	// always generate a sensible desired number of candidates: elections are uninteresting if we
70	// desire 0 candidates, or a number of candidates >= the actual number of candidates present
71	let rounds = rng.gen_range(1..candidate_count);
72
73	// candidates are easy: just a completely random set of IDs
74	let mut candidates: Vec<AccountId> = Vec::with_capacity(candidate_count);
75	for _ in 0..candidate_count {
76		let mut id = rng.gen();
77		// insert returns `false` when the value was already present
78		while !used_ids.insert(id) {
79			id = rng.gen();
80		}
81		candidates.push(id);
82	}
83	candidates.sort();
84	candidates.dedup();
85	assert_eq!(candidates.len(), candidate_count);
86
87	let mut voters = Vec::with_capacity(voter_count);
88	for _ in 0..voter_count {
89		let mut id = rng.gen();
90		// insert returns `false` when the value was already present
91		while !used_ids.insert(id) {
92			id = rng.gen();
93		}
94
95		let vote_weight = rng.gen();
96
97		// it's not interesting if a voter chooses 0 or all candidates, so rule those cases out.
98		let n_candidates_chosen = rng.gen_range(1..candidates.len());
99
100		let mut chosen_candidates = Vec::with_capacity(n_candidates_chosen);
101		chosen_candidates.extend(candidates.choose_multiple(&mut rng, n_candidates_chosen));
102		chosen_candidates.sort();
103		voters.push((id, vote_weight, chosen_candidates));
104	}
105
106	voters.sort();
107	voters.dedup_by_key(|(id, _weight, _chosen_candidates)| *id);
108	assert_eq!(voters.len(), voter_count);
109
110	(rounds, candidates, voters)
111}
112
113pub fn generate_random_npos_result(
114	voter_count: u64,
115	target_count: u64,
116	to_elect: usize,
117	mut rng: impl RngCore,
118	election_type: ElectionType,
119) -> (
120	ElectionResult<AccountId, Perbill>,
121	Vec<AccountId>,
122	Vec<(AccountId, VoteWeight, Vec<AccountId>)>,
123	BTreeMap<AccountId, VoteWeight>,
124) {
125	let prefix = 100_000;
126	// Note, it is important that stakes are always bigger than ed.
127	let base_stake: u64 = 1_000_000_000_000;
128	let ed: u64 = base_stake;
129
130	let mut candidates = Vec::with_capacity(target_count as usize);
131	let mut stake_of: BTreeMap<AccountId, VoteWeight> = BTreeMap::new();
132
133	(1..=target_count).for_each(|acc| {
134		candidates.push(acc);
135		let stake_var = rng.gen_range(ed..100 * ed);
136		stake_of.insert(acc, base_stake + stake_var);
137	});
138
139	let mut voters = Vec::with_capacity(voter_count as usize);
140	(prefix..=(prefix + voter_count)).for_each(|acc| {
141		let edge_per_this_voter = rng.gen_range(1..candidates.len());
142		// all possible targets
143		let mut all_targets = candidates.clone();
144		// we remove and pop into `targets` `edge_per_this_voter` times.
145		let targets = (0..edge_per_this_voter)
146			.map(|_| {
147				let upper = all_targets.len() - 1;
148				let idx = rng.gen_range(0..upper);
149				all_targets.remove(idx)
150			})
151			.collect::<Vec<AccountId>>();
152
153		let stake_var = rng.gen_range(ed..100 * ed);
154		let stake = base_stake + stake_var;
155		stake_of.insert(acc, stake);
156		voters.push((acc, stake, targets));
157	});
158
159	(
160		match election_type {
161			ElectionType::Phragmen(conf) =>
162				seq_phragmen(to_elect, candidates.clone(), voters.clone(), conf).unwrap(),
163			ElectionType::Phragmms(conf) =>
164				phragmms(to_elect, candidates.clone(), voters.clone(), conf).unwrap(),
165		},
166		candidates,
167		voters,
168		stake_of,
169	)
170}
reduce/common.rs

reduce/
common.rs
