reduce/
reduce.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//! Fuzzing for the reduce algorithm.
19//!
20//! It that reduce always return a new set og edges in which the bound is kept (`edges_after <= m +
21//! n,`) and the result must effectively be the same, meaning that the same support map should be
22//! computable from both.
23//!
24//! # Running
25//!
26//! Run with `cargo hfuzz run reduce`. `honggfuzz`.
27//!
28//! # Debugging a panic
29//!
30//! Once a panic is found, it can be debugged with
31//! `cargo hfuzz run-debug reduce hfuzz_workspace/reduce/*.fuzz`.
32
33use honggfuzz::fuzz;
34
35mod common;
36use common::to_range;
37use rand::{self, Rng, RngCore, SeedableRng};
38use sp_npos_elections::{reduce, to_support_map, ExtendedBalance, StakedAssignment};
39
40type Balance = u128;
41type AccountId = u64;
42
43/// Or any other token type.
44const KSM: Balance = 1_000_000_000_000;
45
46fn main() {
47	loop {
48		fuzz!(|data: (usize, usize, u64)| {
49			let (mut voter_count, mut target_count, seed) = data;
50			let rng = rand::rngs::SmallRng::seed_from_u64(seed);
51			target_count = to_range(target_count, 100, 1000);
52			voter_count = to_range(voter_count, 100, 2000);
53			let (assignments, winners) =
54				generate_random_phragmen_assignment(voter_count, target_count, 8, 8, rng);
55			reduce_and_compare(&assignments, &winners);
56		});
57	}
58}
59
60fn generate_random_phragmen_assignment(
61	voter_count: usize,
62	target_count: usize,
63	avg_edge_per_voter: usize,
64	edge_per_voter_var: usize,
65	mut rng: impl RngCore,
66) -> (Vec<StakedAssignment<AccountId>>, Vec<AccountId>) {
67	// prefix to distinguish the voter and target account ranges.
68	let target_prefix = 1_000_000;
69	assert!(voter_count < target_prefix);
70
71	let mut assignments = Vec::with_capacity(voter_count as usize);
72	let mut winners: Vec<AccountId> = Vec::new();
73
74	let all_targets = (target_prefix..(target_prefix + target_count))
75		.map(|a| a as AccountId)
76		.collect::<Vec<AccountId>>();
77
78	(1..=voter_count).for_each(|acc| {
79		let mut targets_to_chose_from = all_targets.clone();
80		let targets_to_chose = if edge_per_voter_var > 0 {
81			rng.gen_range(
82				avg_edge_per_voter - edge_per_voter_var..avg_edge_per_voter + edge_per_voter_var,
83			)
84		} else {
85			avg_edge_per_voter
86		};
87
88		let distribution = (0..targets_to_chose)
89			.map(|_| {
90				let target =
91					targets_to_chose_from.remove(rng.gen_range(0..targets_to_chose_from.len()));
92				if winners.iter().all(|w| *w != target) {
93					winners.push(target);
94				}
95				(target, rng.gen_range(1 * KSM..100 * KSM))
96			})
97			.collect::<Vec<(AccountId, ExtendedBalance)>>();
98
99		assignments.push(StakedAssignment { who: (acc as AccountId), distribution });
100	});
101
102	(assignments, winners)
103}
104
105fn assert_assignments_equal(
106	ass1: &Vec<StakedAssignment<AccountId>>,
107	ass2: &Vec<StakedAssignment<AccountId>>,
108) {
109	let support_1 = to_support_map::<AccountId>(ass1);
110	let support_2 = to_support_map::<AccountId>(ass2);
111	for (who, support) in support_1.iter() {
112		assert_eq!(support.total, support_2.get(who).unwrap().total);
113	}
114}
115
116fn reduce_and_compare(assignment: &Vec<StakedAssignment<AccountId>>, winners: &Vec<AccountId>) {
117	let mut altered_assignment = assignment.clone();
118	let n = assignment.len() as u32;
119	let m = winners.len() as u32;
120
121	let edges_before = assignment_len(assignment);
122	let num_changed = reduce(&mut altered_assignment);
123	let edges_after = edges_before - num_changed;
124
125	assert!(
126		edges_after <= m + n,
127		"reduce bound not satisfied. n = {}, m = {}, edges after reduce = {} (removed {})",
128		n,
129		m,
130		edges_after,
131		num_changed,
132	);
133
134	assert_assignments_equal(&assignment, &altered_assignment);
135}
136
137fn assignment_len(assignments: &[StakedAssignment<AccountId>]) -> u32 {
138	let mut counter = 0;
139	assignments
140		.iter()
141		.for_each(|x| x.distribution.iter().for_each(|_| counter += 1));
142	counter
143}
reduce/reduce.rs

reduce/
reduce.rs
