1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103

// This file is part of Substrate.

// Copyright (C) 2020-2021 Parity Technologies (UK) Ltd.
// SPDX-License-Identifier: Apache-2.0

// Licensed under the Apache License, Version 2.0 (the "License");
// you may not use this file except in compliance with the License.
// You may obtain a copy of the License at
//
// 	http://www.apache.org/licenses/LICENSE-2.0
//
// Unless required by applicable law or agreed to in writing, software
// distributed under the License is distributed on an "AS IS" BASIS,
// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
// See the License for the specific language governing permissions and
// limitations under the License.

//! Fuzzing for phragmms.

mod common;

use common::*;
use honggfuzz::fuzz;
use rand::{self, SeedableRng};
use sp_npos_elections::{
	assignment_ratio_to_staked_normalized, is_score_better, phragmms, to_supports,
	to_without_backing, EvaluateSupport, VoteWeight,
};
use sp_runtime::Perbill;

fn main() {
	loop {
		fuzz!(|data: (usize, usize, usize, usize, u64)| {
			let (mut target_count, mut voter_count, mut iterations, mut to_elect, seed) = data;
			let rng = rand::rngs::SmallRng::seed_from_u64(seed);
			target_count = to_range(target_count, 100, 200);
			voter_count = to_range(voter_count, 100, 200);
			iterations = to_range(iterations, 5, 30);
			to_elect = to_range(to_elect, 25, target_count);

			println!(
				"++ [voter_count: {} / target_count:{} / to_elect:{} / iterations:{}]",
				voter_count, target_count, to_elect, iterations,
			);
			let (unbalanced, candidates, voters, stake_of_tree) = generate_random_npos_result(
				voter_count as u64,
				target_count as u64,
				to_elect,
				rng,
				ElectionType::Phragmms(None),
			);

			let stake_of = |who: &AccountId| -> VoteWeight { *stake_of_tree.get(who).unwrap() };

			let unbalanced_score = {
				let staked = assignment_ratio_to_staked_normalized(
					unbalanced.assignments.clone(),
					&stake_of,
				)
				.unwrap();
				let winners = to_without_backing(unbalanced.winners.clone());
				let score = to_supports(&winners, &staked).unwrap().evaluate();

				if score[0] == 0 {
					// such cases cannot be improved by balancing.
					return
				}
				score
			};

			let balanced = phragmms::<AccountId, sp_runtime::Perbill>(
				to_elect,
				candidates,
				voters,
				Some((iterations, 0)),
			)
			.unwrap();

			let balanced_score = {
				let staked =
					assignment_ratio_to_staked_normalized(balanced.assignments.clone(), &stake_of)
						.unwrap();
				let winners = to_without_backing(balanced.winners);
				to_supports(winners.as_ref(), staked.as_ref()).unwrap().evaluate()
			};

			let enhance = is_score_better(balanced_score, unbalanced_score, Perbill::zero());

			println!(
				"iter = {} // {:?} -> {:?} [{}]",
				iterations, unbalanced_score, balanced_score, enhance,
			);

			// The only guarantee of balancing is such that the first and third element of the score
			// cannot decrease.
			assert!(
				balanced_score[0] >= unbalanced_score[0] &&
					balanced_score[1] == unbalanced_score[1] &&
					balanced_score[2] <= unbalanced_score[2]
			);
		});
	}
}