#[derive(Encode, Decode, Clone, PartialEq, Eq, RuntimeDebug, TypeInfo)]

	Local,

	Remote,

#[derive(Encode, Decode, Clone, PartialEq, Eq, RuntimeDebug, TypeInfo)]

	Valid,

	Invalid,

	fn reward_dispute_statement(_: SessionIndex, _: impl IntoIterator<Item = ValidatorIndex>) {}

	fn punish_for_invalid(

		_: SessionIndex,

		_: CandidateHash,

		_: impl IntoIterator<Item = ValidatorIndex>,

		_: impl IntoIterator<Item = ValidatorIndex>,

	) {

	}

	fn punish_against_valid(

		_: SessionIndex,

		_: CandidateHash,

		_: impl IntoIterator<Item = ValidatorIndex>,

		_: impl IntoIterator<Item = ValidatorIndex>,

	) {

	}

	fn initializer_initialize(_now: BlockNumber) -> Weight {

		Weight::zero()

	}

	fn initializer_finalize() {}

	fn initializer_on_new_session(_: SessionIndex) {}

fn dispute_ordering_compare<T: DisputesHandler<BlockNumber>, BlockNumber: Ord>(

	a: &DisputeStatementSet,

	b: &DisputeStatementSet,

) -> Ordering

where

	T: ?Sized,

{

	let a_local_block =

		<T as DisputesHandler<BlockNumber>>::included_state(a.session, a.candidate_hash);

	let b_local_block =

		<T as DisputesHandler<BlockNumber>>::included_state(b.session, b.candidate_hash);

	match (a_local_block, b_local_block) {

		(None, Some(_)) => Ordering::Greater,

		(Some(_), None) => Ordering::Less,

		(Some(a_height), Some(b_height)) =>

			a_height.cmp(&b_height).then_with(|| a.candidate_hash.cmp(&b.candidate_hash)),

			let session_ord = a.session.cmp(&b.session);

			if session_ord == Ordering::Equal {

				a.candidate_hash.cmp(&b.candidate_hash)

				session_ord

}

			Err(())

	fn is_frozen() -> bool {

		false

	}

	fn deduplicate_and_sort_dispute_data(

		statement_sets: &mut MultiDisputeStatementSet,

	) -> Result<(), ()> {

		statement_sets.clear();

		Ok(())

	}

	fn filter_dispute_data(

		_set: DisputeStatementSet,

		_post_conclusion_acceptance_period: BlockNumber,

	) -> Option<CheckedDisputeStatementSet> {

		None

	}

	fn process_checked_multi_dispute_data(

		_statement_sets: &CheckedMultiDisputeStatementSet,

	) -> Result<Vec<(SessionIndex, CandidateHash)>, DispatchError> {

		Ok(Vec::new())

	}

	fn note_included(

		_session: SessionIndex,

		_candidate_hash: CandidateHash,

		_included_in: BlockNumber,

	) {

	}

	fn included_state(

		_session: SessionIndex,

		_candidate_hash: CandidateHash,

	) -> Option<BlockNumber> {

		None

	}

	fn concluded_invalid(_session: SessionIndex, _candidate_hash: CandidateHash) -> bool {

		false

	}

	fn initializer_initialize(_now: BlockNumber) -> Weight {

		Weight::zero()

	}

	fn initializer_finalize() {}

	fn initializer_on_new_session(_notification: &SessionChangeNotification<BlockNumber>) {}

	fn filter_dispute_data(

		set: DisputeStatementSet,

		post_conclusion_acceptance_period: BlockNumberFor<T>,

	) -> Option<CheckedDisputeStatementSet> {

		pallet::Pallet::<T>::filter_dispute_data(&set, post_conclusion_acceptance_period)

			.filter_statement_set(set)

	}

	fn note_included(

		session: SessionIndex,

		candidate_hash: CandidateHash,

		included_in: BlockNumberFor<T>,

	) {

		pallet::Pallet::<T>::note_included(session, candidate_hash, included_in)

	}

	fn included_state(

		session: SessionIndex,

		candidate_hash: CandidateHash,

	) -> Option<BlockNumberFor<T>> {

		pallet::Pallet::<T>::included_state(session, candidate_hash)

	}

	fn concluded_invalid(session: SessionIndex, candidate_hash: CandidateHash) -> bool {

		pallet::Pallet::<T>::concluded_invalid(session, candidate_hash)

	}

	fn force_unfreeze() -> Weight {

		Weight::zero()

	}

	#[pallet::without_storage_info]

	#[pallet::event]

	#[pallet::generate_deposit(pub fn deposit_event)]

		/// A dispute has been initiated. \[candidate hash, dispute location\]

		DisputeInitiated(CandidateHash, DisputeLocation),

		/// A dispute has concluded for or against a candidate.

		DisputeConcluded(CandidateHash, DisputeResult),

		/// A dispute has concluded with supermajority against a candidate.

		Revert(BlockNumberFor<T>),

	#[pallet::error]

		/// Duplicate dispute statement sets provided.

		DuplicateDisputeStatementSets,

		/// Ancient dispute statement provided.

		AncientDisputeStatement,

		/// Validator index on statement is out of bounds for session.

		ValidatorIndexOutOfBounds,

		/// Invalid signature on statement.

		InvalidSignature,

		/// Validator vote submitted more than once to dispute.

		DuplicateStatement,

		/// A dispute where there are only votes on one side.

		SingleSidedDispute,

		/// A dispute vote from a malicious backer.

		MaliciousBacker,

		/// No backing votes were provides along dispute statements.

		MissingBackingVotes,

		/// Unconfirmed dispute statement sets provided.

		UnconfirmedDispute,

			Frozen::<T>::set(None);

			Ok(())

	fn from_state<BlockNumber>(state: &DisputeState<BlockNumber>) -> Self {

		// Only correct since `DisputeState` is _always_ initialized

		// with the validator set based on the session.

		let n = state.validators_for.len();

		let byzantine_threshold = byzantine_threshold(n);

		let supermajority_threshold = supermajority_threshold(n);

		let mut flags = DisputeStateFlags::default();

		let all_participants = state.validators_for.clone() | state.validators_against.clone();

		if all_participants.count_ones() > byzantine_threshold {

			flags |= DisputeStateFlags::CONFIRMED;

		}

		if state.validators_for.count_ones() >= supermajority_threshold {

			flags |= DisputeStateFlags::FOR_SUPERMAJORITY;

		}

		if state.validators_against.count_ones() > byzantine_threshold {

			flags |= DisputeStateFlags::AGAINST_BYZANTINE;

		}

		if state.validators_against.count_ones() >= supermajority_threshold {

			flags |= DisputeStateFlags::AGAINST_SUPERMAJORITY;

		}

		flags

	}

#[derive(RuntimeDebug, PartialEq, Eq)]

#[derive(RuntimeDebug, Copy, Clone, PartialEq, Eq)]

	fn from(statement: &DisputeStatement) -> Self {

		if statement.is_backing() {

			Self::Backing

		} else if statement.indicates_validity() {

			Self::ExplicitValid

			Self::Invalid

	}

	fn is_valid(&self) -> bool {

		match self {

			Self::Backing | Self::ExplicitValid => true,

			Self::Invalid => false,

	}

	fn is_backing(&self) -> bool {

		match self {

			Self::Backing => true,

			Self::Invalid | Self::ExplicitValid => false,

	}

	fn from(e: VoteImportError) -> Self {

		match e {

			VoteImportError::ValidatorIndexOutOfBounds => Error::<T>::ValidatorIndexOutOfBounds,

			VoteImportError::DuplicateStatement => Error::<T>::DuplicateStatement,

			VoteImportError::MaliciousBacker => Error::<T>::MaliciousBacker,

	}

#[derive(RuntimeDebug, PartialEq, Eq)]

	fn new(

		state: DisputeState<BlockNumber>,

		backers: BTreeSet<ValidatorIndex>,

		now: BlockNumber,

	) -> Self {

		let pre_flags = DisputeStateFlags::from_state(&state);

		let new_participants = bitvec::bitvec![u8, BitOrderLsb0; 0; state.validators_for.len()];

		for i in backers.iter() {

			debug_assert_eq!(state.validators_for.get(i.0 as usize).map(|b| *b), Some(true));

		let pre_state = state.clone();

		let pre_backers = backers.clone();

		DisputeStateImporter {

			state,

			backers,

			now,

			new_participants,

			pre_flags,

			pre_state,

			pre_backers,

		}

	}

	fn import(

		&mut self,

		validator: ValidatorIndex,

		kind: VoteKind,

	) -> Result<ImportUndo, VoteImportError> {

		let (bits, other_bits) = if kind.is_valid() {

			(&mut self.state.validators_for, &mut self.state.validators_against)

			(&mut self.state.validators_against, &mut self.state.validators_for)

		match bits.get(validator.0 as usize).map(|b| *b) {

			None => return Err(VoteImportError::ValidatorIndexOutOfBounds),

				match (kind.is_backing(), self.backers.contains(&validator)) {

						return Err(VoteImportError::DuplicateStatement),

					(false, true) => return Err(VoteImportError::MaliciousBacker),

					(true, false) => {},

			Some(false) => {},

		debug_assert!((validator.0 as usize) < self.new_participants.len());

		let mut undo =

			ImportUndo { validator_index: validator, vote_kind: kind, new_participant: false };

		bits.set(validator.0 as usize, true);

		if kind.is_backing() {

			let is_new = self.backers.insert(validator);

			// invariant check

			debug_assert!(is_new);

		}

		if other_bits.get(validator.0 as usize).map_or(false, |b| !*b) {

			undo.new_participant = true;

			self.new_participants.set(validator.0 as usize, true);

		}

		Ok(undo)

	}

	fn undo(&mut self, undo: ImportUndo) {

		if undo.vote_kind.is_valid() {

			self.state.validators_for.set(undo.validator_index.0 as usize, false);

		} else {

			self.state.validators_against.set(undo.validator_index.0 as usize, false);

		}

		if undo.vote_kind.is_backing() {

			self.backers.remove(&undo.validator_index);

		}

		if undo.new_participant {

			self.new_participants.set(undo.validator_index.0 as usize, false);

		}

	}

	fn finish(mut self) -> ImportSummary<BlockNumber> {

		let pre_flags = self.pre_flags;

		let post_flags = DisputeStateFlags::from_state(&self.state);

		let pre_post_contains = |flags| (pre_flags.contains(flags), post_flags.contains(flags));

		let slash_against = match pre_post_contains(DisputeStateFlags::FOR_SUPERMAJORITY) {

				if self.state.concluded_at.is_none() {

					self.state.concluded_at = Some(self.now.clone());

				}

				self.state

					.validators_against

					.iter_ones()

					.map(|i| ValidatorIndex(i as _))

					.collect()

				self.state

					.validators_against

					.iter_ones()

					.filter(|i| self.pre_state.validators_against.get(*i).map_or(false, |b| !*b))

					.map(|i| ValidatorIndex(i as _))

					.collect()

				log::error!("Dispute statements are never removed. This is a bug");

				Vec::new()

			(false, false) => Vec::new(),

		let slash_for = match pre_post_contains(DisputeStateFlags::AGAINST_SUPERMAJORITY) {

				if self.state.concluded_at.is_none() {

					self.state.concluded_at = Some(self.now.clone());

				}

				self.state.validators_for.iter_ones().map(|i| ValidatorIndex(i as _)).collect()

				let new_backing_vote = |i: &ValidatorIndex| -> bool {

					!self.pre_backers.contains(i) && self.backers.contains(i)

				};

				self.state

					.validators_for

					.iter_ones()

					.filter(|i| {

						self.pre_state.validators_for.get(*i).map_or(false, |b| !*b) ||

							new_backing_vote(&ValidatorIndex(*i as _))

					})

					.map(|i| ValidatorIndex(i as _))

					.collect()

				log::error!("Dispute statements are never removed. This is a bug");

				Vec::new()

			(false, false) => Vec::new(),

		ImportSummary {

			state: self.state,

			backers: self.backers,

			slash_against,

			slash_for,

			new_participants: self.new_participants,

			new_flags: post_flags - pre_flags,

		}

	}

	fn filter_statement_set(

		self,

		mut statement_set: DisputeStatementSet,

	) -> Option<CheckedDisputeStatementSet> {

		match self {

			StatementSetFilter::RemoveAll => None,

			StatementSetFilter::RemoveIndices(mut indices) => {

				indices.sort();

				indices.dedup();

				for index in indices.into_iter().rev() {

					// `swap_remove` guarantees linear complexity.

					statement_set.statements.swap_remove(index);

				}

				if statement_set.statements.is_empty() {

					None

					Some(CheckedDisputeStatementSet::unchecked_from_unchecked(statement_set))

	}

	fn remove_index(&mut self, i: usize) {

		if let StatementSetFilter::RemoveIndices(ref mut indices) = *self {

			indices.push(i)

		}

	}

			let dispute_target = {

				let statement_set = statement_set.as_ref();

				(statement_set.session, statement_set.candidate_hash)

			};

			if Self::process_checked_dispute_data(

				statement_set,

				config.dispute_post_conclusion_acceptance_period,

			)? {

				fresh.push(dispute_target);

			}

	fn filter_dispute_data(

		set: &DisputeStatementSet,

		post_conclusion_acceptance_period: BlockNumberFor<T>,

	) -> StatementSetFilter {

		let mut filter = StatementSetFilter::RemoveIndices(Vec::new());

		// Dispute statement sets on any dispute which concluded

		// before this point are to be rejected.

		let now = frame_system::Pallet::<T>::block_number();

		let oldest_accepted = now.saturating_sub(post_conclusion_acceptance_period);

		let session_info = match session_info::Sessions::<T>::get(set.session) {

			Some(s) => s,

			None => return StatementSetFilter::RemoveAll,

		let config = configuration::ActiveConfig::<T>::get();

		let n_validators = session_info.validators.len();

		let dispute_state = {

			if let Some(dispute_state) = Disputes::<T>::get(&set.session, &set.candidate_hash) {

				if dispute_state.concluded_at.as_ref().map_or(false, |c| c < &oldest_accepted) {

					return StatementSetFilter::RemoveAll

				}

				dispute_state

				DisputeState {

					validators_for: bitvec![u8, BitOrderLsb0; 0; n_validators],

					validators_against: bitvec![u8, BitOrderLsb0; 0; n_validators],

					start: now,

					concluded_at: None,

				}

		let backers =

			BackersOnDisputes::<T>::get(&set.session, &set.candidate_hash).unwrap_or_default();

		let summary = {

			let mut importer = DisputeStateImporter::new(dispute_state, backers, now);

			for (i, (statement, validator_index, signature)) in set.statements.iter().enumerate() {

				let validator_public = match session_info.validators.get(*validator_index) {

						filter.remove_index(i);

						continue

					Some(v) => v,

				};

				let kind = VoteKind::from(statement);

				let undo = match importer.import(*validator_index, kind) {

					Ok(u) => u,

						filter.remove_index(i);

						continue

				if let Err(()) = check_signature(

					&validator_public,

					set.candidate_hash,

					set.session,

					statement,

					signature,

					// This is here to prevent malicious nodes of generating

					// `ValidDisputeStatementKind::ApprovalCheckingMultipleCandidates` before that

					// is enabled, via setting `max_approval_coalesce_count` in the parachain host

					// config.

					config.approval_voting_params.max_approval_coalesce_count > 1,

				) {

					log::warn!("Failed to check dispute signature");

					importer.undo(undo);

					filter.remove_index(i);

					continue

				};

			importer.finish()

		};

		// Reject disputes which don't have at least one vote on each side.

		if summary.state.validators_for.count_ones() == 0 ||

			summary.state.validators_against.count_ones() == 0

			return StatementSetFilter::RemoveAll

		}

		// Reject disputes containing less votes than needed for confirmation.

		if (summary.state.validators_for.clone() | &summary.state.validators_against).count_ones() <=

			byzantine_threshold(summary.state.validators_for.len())

			return StatementSetFilter::RemoveAll

		}

		filter

	}

	fn process_checked_dispute_data(

		set: &CheckedDisputeStatementSet,

		dispute_post_conclusion_acceptance_period: BlockNumberFor<T>,

	) -> Result<bool, DispatchError> {

		// Dispute statement sets on any dispute which concluded

		// before this point are to be rejected.

		let now = frame_system::Pallet::<T>::block_number();

		let oldest_accepted = now.saturating_sub(dispute_post_conclusion_acceptance_period);

		let set = set.as_ref();

		let session_info = match session_info::Sessions::<T>::get(set.session) {

			Some(s) => s,

			None => return Err(Error::<T>::AncientDisputeStatement.into()),

		let n_validators = session_info.validators.len();

		let (fresh, dispute_state) = {

			if let Some(dispute_state) = Disputes::<T>::get(&set.session, &set.candidate_hash) {

				ensure!(

					dispute_state.concluded_at.as_ref().map_or(true, |c| c >= &oldest_accepted),

					Error::<T>::AncientDisputeStatement,

				(false, dispute_state)

				(

					true,

					DisputeState {

						validators_for: bitvec![u8, BitOrderLsb0; 0; n_validators],

						validators_against: bitvec![u8, BitOrderLsb0; 0; n_validators],

						start: now,

						concluded_at: None,

					},

				)

		let backers =

			BackersOnDisputes::<T>::get(&set.session, &set.candidate_hash).unwrap_or_default();

		let summary = {

			let mut importer = DisputeStateImporter::new(dispute_state, backers, now);

			for (statement, validator_index, _signature) in &set.statements {

				let kind = VoteKind::from(statement);

				importer.import(*validator_index, kind).map_err(Error::<T>::from)?;

			importer.finish()

		};

		// Reject disputes which don't have at least one vote on each side.

		ensure!(

			summary.state.validators_for.count_ones() > 0 &&

				summary.state.validators_against.count_ones() > 0,

			Error::<T>::SingleSidedDispute,

		ensure!(

			(summary.state.validators_for.clone() | &summary.state.validators_against).count_ones() >

				byzantine_threshold(summary.state.validators_for.len()),

			Error::<T>::UnconfirmedDispute,

		let backers = summary.backers;

		// Reject statements with no accompanying backing votes.

		ensure!(!backers.is_empty(), Error::<T>::MissingBackingVotes);

		BackersOnDisputes::<T>::insert(&set.session, &set.candidate_hash, backers.clone());

		// AUDIT: from now on, no error should be returned.

		let DisputeStatementSet { ref session, ref candidate_hash, .. } = set;

		let session = *session;

		let candidate_hash = *candidate_hash;

		if fresh {

			let is_local = Included::<T>::contains_key(&session, &candidate_hash);

			Self::deposit_event(Event::DisputeInitiated(

				candidate_hash,

				if is_local { DisputeLocation::Local } else { DisputeLocation::Remote },

		}

			if summary.new_flags.contains(DisputeStateFlags::FOR_SUPERMAJORITY) {

				Self::deposit_event(Event::DisputeConcluded(candidate_hash, DisputeResult::Valid));

			}

			if summary.new_flags.contains(DisputeStateFlags::AGAINST_SUPERMAJORITY) {

				Self::deposit_event(Event::DisputeConcluded(

					candidate_hash,

					DisputeResult::Invalid,

				));

			}

		T::RewardValidators::reward_dispute_statement(

			session,

			summary.new_participants.iter_ones().map(|i| ValidatorIndex(i as _)),

		);

		// Slash participants on a losing side.

		{

			// a valid candidate, according to 2/3. Punish those on the 'against' side.

			T::SlashingHandler::punish_against_valid(

				session,

				candidate_hash,

				summary.slash_against,

				backers.clone(),

			);

			// an invalid candidate, according to 2/3. Punish those on the 'for' side.

			T::SlashingHandler::punish_for_invalid(

				session,

				candidate_hash,

				summary.slash_for,

				backers,

			);

		}

		Disputes::<T>::insert(&session, &candidate_hash, &summary.state);

		// Freeze if the INVALID votes against some local candidate are above the byzantine

		// threshold

		if summary.new_flags.contains(DisputeStateFlags::AGAINST_BYZANTINE) {

			if let Some(revert_to) = Included::<T>::get(&session, &candidate_hash) {

				Self::revert_and_freeze(revert_to);

			}

		}

		Ok(fresh)

	}

	pub(crate) fn disputes() -> Vec<(SessionIndex, CandidateHash, DisputeState<BlockNumberFor<T>>)>

	{

		Disputes::<T>::iter().collect()

	}

	pub(crate) fn note_included(

		session: SessionIndex,

		candidate_hash: CandidateHash,

		included_in: BlockNumberFor<T>,

	) {

		if included_in.is_zero() {

			return

		}

		let revert_to = included_in - One::one();

		Included::<T>::insert(&session, &candidate_hash, revert_to);

		if let Some(state) = Disputes::<T>::get(&session, candidate_hash) {

			if has_supermajority_against(&state) {

				Self::revert_and_freeze(revert_to);

			}

		}

	}

	pub(crate) fn included_state(

		session: SessionIndex,

		candidate_hash: CandidateHash,

	) -> Option<BlockNumberFor<T>> {

		Included::<T>::get(session, candidate_hash)

	}

	pub(crate) fn concluded_invalid(session: SessionIndex, candidate_hash: CandidateHash) -> bool {

		Disputes::<T>::get(&session, &candidate_hash).map_or(false, |dispute| {

			// A dispute that has concluded with supermajority-against.

			has_supermajority_against(&dispute)

		})

	}

	pub(crate) fn revert_and_freeze(revert_to: BlockNumberFor<T>) {

		if Frozen::<T>::get().map_or(true, |last| last > revert_to) {

			Frozen::<T>::set(Some(revert_to));

			// The `Revert` log is about reverting a block, not reverting to a block.

			// If we want to revert to block X in the current chain, we need to revert

			// block X+1.

			let revert = revert_to + One::one();

			Self::deposit_event(Event::Revert(revert));

			frame_system::Pallet::<T>::deposit_log(

				ConsensusLog::Revert(revert.saturated_into()).into(),

			);

		}

	}

fn has_supermajority_against<BlockNumber>(dispute: &DisputeState<BlockNumber>) -> bool {

	let supermajority_threshold = supermajority_threshold(dispute.validators_against.len());

	dispute.validators_against.count_ones() >= supermajority_threshold

}

fn check_signature(

	validator_public: &ValidatorId,

	candidate_hash: CandidateHash,

	session: SessionIndex,

	statement: &DisputeStatement,

	validator_signature: &ValidatorSignature,

	approval_multiple_candidates_enabled: bool,

) -> Result<(), ()> {

	let payload = match statement {

			ExplicitDisputeStatement { valid: true, candidate_hash, session }.signing_payload(),

		DisputeStatement::Valid(ValidDisputeStatementKind::BackingSeconded(inclusion_parent)) =>

			CompactStatement::Seconded(candidate_hash).signing_payload(&SigningContext {

				session_index: session,

				parent_hash: *inclusion_parent,

			}),

		DisputeStatement::Valid(ValidDisputeStatementKind::BackingValid(inclusion_parent)) =>

			CompactStatement::Valid(candidate_hash).signing_payload(&SigningContext {

				session_index: session,

				parent_hash: *inclusion_parent,

			}),

			ApprovalVote(candidate_hash).signing_payload(session),

			candidates,

		)) =>

			if approval_multiple_candidates_enabled && candidates.contains(&candidate_hash) {

				ApprovalVoteMultipleCandidates(candidates).signing_payload(session)

				return Err(())

			ExplicitDisputeStatement { valid: false, candidate_hash, session }.signing_payload(),

	let start = get_current_time();

	let res =

		if validator_signature.verify(&payload[..], &validator_public) { Ok(()) } else { Err(()) };

	let end = get_current_time();

	METRICS.on_signature_check_complete(end.saturating_sub(start)); // ns

	res

}