phragmen_pjr/
phragmen_pjr.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 which ensures that running unbalanced sequential phragmen always produces a result
19//! which satisfies our PJR checker.
20//!
21//! ## Running a single iteration
22//!
23//! Honggfuzz shuts down each individual loop iteration after a configurable time limit.
24//! It can be helpful to run a single iteration on your hardware to help benchmark how long that
25//! time limit should reasonably be. Simply run the program without the `fuzzing` configuration to
26//! run a single iteration: `cargo run --bin phragmen_pjr`.
27//!
28//! ## Running
29//!
30//! Run with `HFUZZ_RUN_ARGS="-t 10" cargo hfuzz run phragmen_pjr`.
31//!
32//! Note the environment variable: by default, `cargo hfuzz` shuts down each iteration after 1
33//! second of runtime. We significantly increase that to ensure that the fuzzing gets a chance to
34//! complete. Running a single iteration can help determine an appropriate value for this parameter.
35//!
36//! ## Debugging a panic
37//!
38//! Once a panic is found, it can be debugged with
39//! `HFUZZ_RUN_ARGS="-t 10" cargo hfuzz run-debug phragmen_pjr hfuzz_workspace/phragmen_pjr/*.fuzz`.
40
41#[cfg(fuzzing)]
42use honggfuzz::fuzz;
43
44#[cfg(not(fuzzing))]
45use clap::Parser;
46
47mod common;
48use common::{generate_random_npos_inputs, to_range};
49use rand::{self, SeedableRng};
50use sp_npos_elections::{pjr_check_core, seq_phragmen_core, setup_inputs, standard_threshold};
51
52type AccountId = u64;
53
54const MIN_CANDIDATES: usize = 250;
55const MAX_CANDIDATES: usize = 1000;
56const MIN_VOTERS: usize = 500;
57const MAX_VOTERS: usize = 2500;
58
59#[cfg(fuzzing)]
60fn main() {
61	loop {
62		fuzz!(|data: (usize, usize, u64)| {
63			let (candidate_count, voter_count, seed) = data;
64			iteration(candidate_count, voter_count, seed);
65		});
66	}
67}
68
69#[cfg(not(fuzzing))]
70#[derive(Debug, Parser)]
71#[command(author, version, about)]
72struct Opt {
73	/// How many candidates participate in this election
74	#[arg(short, long)]
75	candidates: Option<usize>,
76
77	/// How many voters participate in this election
78	#[arg(short, long)]
79	voters: Option<usize>,
80
81	/// Random seed to use in this election
82	#[arg(long)]
83	seed: Option<u64>,
84}
85
86#[cfg(not(fuzzing))]
87fn main() {
88	let opt = Opt::parse();
89	// candidates and voters by default use the maxima, which turn out to be one less than
90	// the constant.
91	iteration(
92		opt.candidates.unwrap_or(MAX_CANDIDATES - 1),
93		opt.voters.unwrap_or(MAX_VOTERS - 1),
94		opt.seed.unwrap_or_default(),
95	);
96}
97
98fn iteration(mut candidate_count: usize, mut voter_count: usize, seed: u64) {
99	let rng = rand::rngs::SmallRng::seed_from_u64(seed);
100	candidate_count = to_range(candidate_count, MIN_CANDIDATES, MAX_CANDIDATES);
101	voter_count = to_range(voter_count, MIN_VOTERS, MAX_VOTERS);
102
103	let (rounds, candidates, voters) =
104		generate_random_npos_inputs(candidate_count, voter_count, rng);
105
106	let (candidates, voters) = setup_inputs(candidates, voters);
107
108	// Run seq-phragmen
109	let (candidates, voters) = seq_phragmen_core::<AccountId>(rounds, candidates, voters)
110		.expect("seq_phragmen must succeed");
111
112	let threshold = standard_threshold(rounds, voters.iter().map(|voter| voter.budget()));
113
114	assert!(
115		pjr_check_core(&candidates, &voters, threshold).is_ok(),
116		"unbalanced sequential phragmen must satisfy PJR",
117	);
118}
phragmen_pjr/phragmen_pjr.rs

phragmen_pjr/
phragmen_pjr.rs
