Files
biguint
chain_spec_builder
compact
fixed_point
fork_tree
frame_benchmarking
frame_benchmarking_cli
frame_election_provider_support
frame_executive
frame_metadata
frame_support
frame_support_procedural
frame_support_procedural_tools
frame_support_procedural_tools_derive
frame_support_test
frame_support_test_pallet
frame_system
frame_system_benchmarking
frame_system_rpc_runtime_api
frame_try_runtime
multiply_by_rational
node_bench
node_browser_testing
node_cli
node_executor
node_inspect
node_primitives
node_rpc
node_rpc_client
node_runtime
node_template
node_template_runtime
node_testing
normalize
pallet_assets
pallet_atomic_swap
pallet_aura
pallet_authority_discovery
pallet_authorship
pallet_babe
pallet_balances
pallet_bounties
pallet_collective
pallet_contracts
pallet_contracts_primitives
pallet_contracts_proc_macro
pallet_contracts_rpc
pallet_contracts_rpc_runtime_api
pallet_democracy
pallet_election_provider_multi_phase
pallet_elections
pallet_elections_phragmen
pallet_example
pallet_example_offchain_worker
pallet_example_parallel
pallet_gilt
pallet_grandpa
pallet_identity
pallet_im_online
pallet_indices
pallet_lottery
pallet_membership
pallet_mmr
pallet_mmr_primitives
pallet_mmr_rpc
pallet_multisig
pallet_nicks
pallet_node_authorization
pallet_offences
pallet_offences_benchmarking
pallet_proxy
pallet_randomness_collective_flip
pallet_recovery
pallet_scheduler
pallet_scored_pool
pallet_session
pallet_session_benchmarking
pallet_society
pallet_staking
pallet_staking_reward_curve
pallet_staking_reward_fn
pallet_sudo
pallet_template
pallet_timestamp
pallet_tips
pallet_transaction_payment
pallet_transaction_payment_rpc
pallet_transaction_payment_rpc_runtime_api
pallet_transaction_storage
pallet_treasury
pallet_uniques
pallet_utility
pallet_vesting
per_thing_rational
phragmen_balancing
phragmen_pjr
phragmms_balancing
reduce
remote_externalities
sc_allocator
sc_authority_discovery
sc_basic_authorship
sc_block_builder
sc_chain_spec
sc_chain_spec_derive
sc_cli
sc_client_api
sc_client_db
sc_consensus
sc_consensus_aura
sc_consensus_babe
sc_consensus_babe_rpc
sc_consensus_epochs
sc_consensus_manual_seal
sc_consensus_pow
sc_consensus_slots
sc_consensus_uncles
sc_executor
sc_executor_common
sc_executor_wasmi
sc_executor_wasmtime
sc_finality_grandpa
sc_finality_grandpa_rpc
sc_informant
sc_keystore
sc_light
sc_network
sc_network_gossip
sc_network_test
sc_offchain
sc_peerset
sc_proposer_metrics
sc_rpc
sc_rpc_api
sc_rpc_server
sc_runtime_test
sc_service
sc_service_test
sc_state_db
sc_sync_state_rpc
sc_telemetry
sc_tracing
sc_tracing_proc_macro
sc_transaction_pool
sc_transaction_pool_api
sp_api
sp_api_proc_macro
sp_application_crypto
sp_application_crypto_test
sp_arithmetic
sp_authority_discovery
sp_authorship
sp_block_builder
sp_blockchain
sp_consensus
sp_consensus_aura
sp_consensus_babe
sp_consensus_pow
sp_consensus_slots
sp_consensus_vrf
sp_core
sp_database
sp_debug_derive
sp_externalities
sp_finality_grandpa
sp_inherents
sp_io
sp_keyring
sp_keystore
sp_maybe_compressed_blob
sp_npos_elections
sp_npos_elections_solution_type
sp_offchain
sp_panic_handler
sp_rpc
sp_runtime
sp_runtime_interface
sp_runtime_interface_proc_macro
sp_runtime_interface_test
sp_runtime_interface_test_wasm
sp_runtime_interface_test_wasm_deprecated
sp_sandbox
sp_serializer
sp_session
sp_staking
sp_state_machine
sp_std
sp_storage
sp_tasks
sp_test_primitives
sp_timestamp
sp_tracing
sp_transaction_pool
sp_transaction_storage_proof
sp_trie
sp_utils
sp_version
sp_version_proc_macro
sp_wasm_interface
subkey
substrate
substrate_browser_utils
substrate_build_script_utils
substrate_frame_cli
substrate_frame_rpc_support
substrate_frame_rpc_system
substrate_prometheus_endpoint
substrate_test_client
substrate_test_runtime
substrate_test_runtime_client
substrate_test_runtime_transaction_pool
substrate_test_utils
substrate_test_utils_derive
substrate_test_utils_test_crate
substrate_wasm_builder
test_runner
test_runner_example
try_runtime_cli
  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
104
105
106
107
// 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 sequential phragmen with potential balancing.

mod common;

use common::*;
use honggfuzz::fuzz;
use rand::{self, SeedableRng};
use sp_npos_elections::{
	assignment_ratio_to_staked_normalized, is_score_better, seq_phragmen, 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, 0, 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::Phragmen(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.as_ref(), staked.as_ref()).unwrap().evaluate();

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

			if iterations > 0 {
				let balanced = seq_phragmen::<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]
				);
			}
		});
	}
}