parachains.rs

		DownwardMessageQueue::<T>::mutate(id, |v| {
			if processed > v.len() {
				v.clear();
			} else {
				*v = v.split_off(processed);
			}
		});
	}

	/// Update routing information from the parachain heads. This queues upwards
	/// messages to the relay chain as well.
	fn update_routing(
		heads: &[AttestedCandidate],
	) {
		// we sort them in order to provide a fast lookup to ensure we can avoid duplicates in the
		// needs_dispatch queue.
		let mut ordered_needs_dispatch = NeedsDispatch::get();

		for head in heads.iter() {
			let id = head.parachain_index();
			Heads::insert(id, &head.candidate.head_data);

			// Queue up upwards messages (from parachains to relay chain).
			Self::queue_upward_messages(
				id,
				&head.candidate.commitments.upward_messages,
				&mut ordered_needs_dispatch,
			);
		}

		NeedsDispatch::put(ordered_needs_dispatch);
	}

	/// Place any new upward messages into our queue for later dispatch.
	///
	/// `ordered_needs_dispatch` is mutated to ensure it reflects the new value of
	/// `RelayDispatchQueueSize`. It is up to the caller to guarantee that it gets written into
	/// storage after this call.
	fn queue_upward_messages(
		id: ParaId,
		upward_messages: &[UpwardMessage],
		ordered_needs_dispatch: &mut Vec<ParaId>,
	) {
		if !upward_messages.is_empty() {
			RelayDispatchQueueSize::mutate(id, |&mut(ref mut count, ref mut len)| {
				*count += upward_messages.len() as u32;
				*len += upward_messages.iter()
					.fold(0, |a, x| a + x.data.len()) as u32;
			});

			upward_messages.iter().for_each(|m| RelayDispatchQueue::append(id, m));

			if let Err(i) = ordered_needs_dispatch.binary_search(&id) {
				// same.
				ordered_needs_dispatch.insert(i, id);
			} else {
				sp_runtime::print("ordered_needs_dispatch contains id?!");
			}
		}
	}

	/// Simple FIFO dispatcher. This must be called after parachain fees are checked,
	/// as dispatched messages may spend parachain funds.
	fn dispatch_upward_messages(
		max_queue_count: usize,
		watermark_queue_size: usize,
		mut dispatch_message: impl FnMut(ParaId, ParachainDispatchOrigin, &[u8]),
	) {
		let queueds = NeedsDispatch::get();
		let mut drained_count = 0usize;
		let mut dispatched_count = 0usize;
		let mut dispatched_size = 0usize;
		for id in queueds.iter() {
			drained_count += 1;

			let (count, size) = <RelayDispatchQueueSize>::get(id);
			let count = count as usize;
			let size = size as usize;
			if dispatched_count == 0 || (
				dispatched_count + count <= max_queue_count
					&& dispatched_size + size <= watermark_queue_size
			) {
				if count > 0 {
					// still dispatching messages...
					RelayDispatchQueueSize::remove(id);
					let messages = RelayDispatchQueue::take(id);
					for UpwardMessage { origin, data } in messages.into_iter() {
						dispatch_message(*id, origin, &data);
					}
					dispatched_count += count;
					dispatched_size += size;
					if dispatched_count >= max_queue_count
						|| dispatched_size >= watermark_queue_size
					{
						break
					}
				}
			}
		}
		NeedsDispatch::put(&queueds[drained_count..]);
	}

	/// Calculate the current block's duty roster using system's random seed.
	/// Returns the duty roster along with the random seed.
	pub fn calculate_duty_roster() -> (DutyRoster, [u8; 32]) {
		let parachains = Self::active_parachains();
		let parachain_count = parachains.len();

		// TODO: use decode length. substrate #2794
		let validator_count = Self::authorities().len();
		let validators_per_parachain =
			if parachain_count == 0 {
				0
			} else {
				(validator_count - 1) / parachain_count
			};

		let mut roles_val = (0..validator_count).map(|i| match i {
			i if i < parachain_count * validators_per_parachain => {
				let idx = i / validators_per_parachain;
				Chain::Parachain(parachains[idx].0.clone())
			}
			_ => Chain::Relay,
		}).collect::<Vec<_>>();

		let mut seed = {
			let phrase = b"validator_role_pairs";
			let seed = T::Randomness::random(&phrase[..]);
			let seed_len = seed.as_ref().len();
			let needed_bytes = validator_count * 4;

			// hash only the needed bits of the random seed.
			// if earlier bits are influencable, they will not factor into
			// the seed used here.
			let seed_off = if needed_bytes >= seed_len {
				0
			} else {
				seed_len - needed_bytes
			};

			BlakeTwo256::hash(&seed.as_ref()[seed_off..])
		};

		let orig_seed = seed.clone().to_fixed_bytes();

		// shuffle
		for i in 0..(validator_count.saturating_sub(1)) {
			// 4 bytes of entropy used per cycle, 32 bytes entropy per hash
			let offset = (i * 4 % 32) as usize;

			// number of roles remaining to select from.
			let remaining = sp_std::cmp::max(1, (validator_count - i) as usize);

			// 8 32-bit ints per 256-bit seed.
			let val_index = u32::decode(&mut &seed[offset..offset + 4])
				.expect("using 4 bytes for a 32-bit quantity") as usize % remaining;

			if offset == 28 {
				// into the last 4 bytes - rehash to gather new entropy
				seed = BlakeTwo256::hash(seed.as_ref());
			}

			// exchange last item with randomly chosen first.
			roles_val.swap(remaining - 1, val_index);
		}

		(DutyRoster { validator_duty: roles_val, }, orig_seed)
	}

	/// Get the global validation schedule for all parachains.
	pub fn global_validation_schedule() -> GlobalValidationSchedule {
		let now = <system::Module<T>>::block_number();
		GlobalValidationSchedule {
			max_code_size: T::MaxCodeSize::get(),
			max_head_data_size: T::MaxHeadDataSize::get(),
			block_number: T::BlockNumberConversion::convert(if now.is_zero() {
				now
			} else {
				// parablocks included in this block will execute in the context
				// of the current block's parent.
				now - One::one()
			}),
		}
	}

	/// Get the local validation schedule for a particular parachain.
	pub fn local_validation_data(id: &ParaId, perceived_height: T::BlockNumber) -> Option<LocalValidationData> {
		if perceived_height + One::one() != <system::Module<T>>::block_number() {
			// sanity-check - no non-direct-parent blocks allowed at the moment.
			return None
		}

		let code_upgrade_allowed: Option<BlockNumber> = (|| {
			match T::Registrar::para_info(*id)?.scheduling {
				Scheduling::Always => {},
				Scheduling::Dynamic => return None, // parathreads can't upgrade code.
			}

			// if perceived-height were not the parent of `now`, then this should
			// not be drawn from current-runtime configuration. however the sanity-check
			// above prevents that.
			let min_upgrade_frequency = T::ValidationUpgradeFrequency::get();
			let upgrade_delay = T::ValidationUpgradeDelay::get();

			let no_planned = Self::code_upgrade_schedule(id)
				.map_or(true, |expected: T::BlockNumber| expected <= perceived_height);

			let can_upgrade_code = no_planned &&
				Self::past_code_meta(id).most_recent_change()
					.map_or(true, |at| at + min_upgrade_frequency < perceived_height);

			if can_upgrade_code {
				let applied_at = perceived_height + upgrade_delay;
				Some(T::BlockNumberConversion::convert(applied_at))
			} else {
				None
			}
		})();

		Self::parachain_head(id).map(|parent_head| LocalValidationData {
			parent_head,
			balance: T::ParachainCurrency::free_balance(*id),
			code_upgrade_allowed,
		})
	}

	/// Returns the `DownwardMessage`'s for the given parachain.
	pub fn downward_messages(id: ParaId) -> Vec<DownwardMessage<T::AccountId>> {
		DownwardMessageQueue::<T>::get(id)
	}

	/// Get the local validation data for a particular parent w.r.t. the current
	/// block height.
	pub fn current_local_validation_data(id: &ParaId) -> Option<LocalValidationData> {
		let now: T::BlockNumber = <system::Module<T>>::block_number();
		if now >= One::one() {
			Self::local_validation_data(id, now - One::one())
		} else {
			None
		}
	}

	/// Fetch the code used for verifying a parachain at a particular height.
	pub fn parachain_code_at(id: &ParaId, at: T::BlockNumber) -> Option<ValidationCode> {
		// note - we don't check that the parachain is currently registered
		// as this might be a deregistered parachain whose old code should still
		// stick around on-chain for some time.
		Self::past_code_meta(id).code_at(at).and_then(|to_use| match to_use {
			UseCodeAt::Current => Self::parachain_code(id),
			UseCodeAt::ReplacedAt(replaced_at) =>
				<Self as Store>::PastCode::get(&(*id, replaced_at)),
		})
	}

	/// Get the currently active set of parachains.
	pub fn active_parachains() -> Vec<(ParaId, Option<(CollatorId, Retriable)>)> {
		T::ActiveParachains::active_paras()
	}

	/// Verify the signatures of all candidates.
	///
	/// Returns `false` if a signature is not correct.
	fn verify_candidate_signatures(
		candidate: &AttestedCandidate,
		authorities: &[ValidatorId],
		validator_group: &[(usize, ParaId)],
		signing_context: &SigningContext,
	) -> DispatchResult {
		let mut expected_votes_len = 0;
		let mut encoded_implicit = None;
		let mut encoded_explicit = None;
		let candidate_hash = candidate.candidate().hash();

		for (vote_index, (auth_index, _)) in candidate.validator_indices
				.iter()
				.enumerate()
				.filter(|(_, bit)| **bit)
				.enumerate()
		{
			let validity_attestation = match candidate.validity_votes.get(vote_index) {
				None => Err(Error::<T>::NotEnoughValidityVotes)?,
				Some(v) => {
					expected_votes_len = vote_index + 1;
					v
				}
			};

			if validator_group.iter().find(|&(idx, _)| *idx == auth_index).is_none() {
				Err(Error::<T>::WrongValidatorAttesting)?
			}

			let (payload, sig) = match validity_attestation {
				ValidityAttestation::Implicit(sig) => {
					let payload = encoded_implicit.get_or_insert_with(|| localized_payload(
						Statement::Candidate(candidate_hash), signing_context,
					));

					(payload, sig)
				}
				ValidityAttestation::Explicit(sig) => {
					let payload = encoded_explicit.get_or_insert_with(|| localized_payload(
						Statement::Valid(candidate_hash), signing_context,
					));

					(payload, sig)
				}
			};

			ensure!(
				sig.verify(&payload[..], &authorities[auth_index]),
				Error::<T>::InvalidSignature,
			);
		}

		if candidate.validity_votes.len() == expected_votes_len {
			Ok(())
		} else {
			Err(Error::<T>::UntaggedVotes.into())
		}
	}

	// check the attestations on these candidates. The candidates should have been checked
	// that each candidates' chain ID is valid.
	fn check_candidates(
		schedule: &GlobalValidationSchedule,
		attested_candidates: &[AttestedCandidate],
		active_parachains: &[(ParaId, Option<(CollatorId, Retriable)>)]
	) -> sp_std::result::Result<IncludedBlocks<T>, sp_runtime::DispatchError> {
		let authorities = Self::authorities();
		let (duty_roster, random_seed) = Self::calculate_duty_roster();

		// computes the omitted validation data for a particular parachain.
		//
		// pass the perceived relay chain height of the para-block. This is the block number of
		// `abridged.relay_parent`.
		let full_candidate = |
			abridged: &AbridgedCandidateReceipt,
			perceived_height: T::BlockNumber,
		|
			-> sp_std::result::Result<CandidateReceipt, sp_runtime::DispatchError>
		{
			let para_id = abridged.parachain_index;
			let local_validation = Self::local_validation_data(&para_id, perceived_height)
				.ok_or(Error::<T>::ParentMismatch)?;

			let omitted = OmittedValidationData {
				global_validation: schedule.clone(),
				local_validation,
			};

			Ok(abridged.clone().complete(omitted))
		};

		let sorted_validators = make_sorted_duties(&duty_roster.validator_duty);

		let relay_height_now = <system::Module<T>>::block_number();
		let parent_hash = <system::Module<T>>::parent_hash();
		let signing_context = Self::signing_context();
		let code_upgrade_delay = T::ValidationUpgradeDelay::get();

		let mut validator_groups = GroupedDutyIter::new(&sorted_validators[..]);

		let mut para_block_hashes = Vec::new();

		for candidate in attested_candidates {
			let para_id = candidate.parachain_index();
			let validator_group = validator_groups.group_for(para_id)
				.ok_or(Error::<T>::NoValidatorGroup)?;

			// NOTE: when changing this to allow older blocks,
			// care must be taken in the availability store pruning to ensure that
			// data is stored correctly. A block containing a candidate C can be
			// orphaned before a block containing C is finalized. Care must be taken
			// not to prune the data for C simply because an orphaned block contained
			// it.

			ensure!(
				candidate.candidate().relay_parent.as_ref() == parent_hash.as_ref(),
				Error::<T>::UnexpectedRelayParent,
			);

			// Since we only allow execution in context of parent hash.
			let perceived_relay_block_height = <system::Module<T>>::block_number() - One::one();

			ensure!(
				candidate.validity_votes.len() >= majority_of(validator_group.len()),
				Error::<T>::NotEnoughValidityVotes,
			);

			ensure!(
				candidate.validity_votes.len() <= authorities.len(),
				Error::<T>::VotesExceedsAuthorities,
			);

			ensure!(
				schedule.max_head_data_size as usize >= candidate.candidate().head_data.0.len(),
				Error::<T>::HeadDataTooLarge,
			);

			let full_candidate = full_candidate(
				candidate.candidate(),
				perceived_relay_block_height,
			)?;

			// apply any scheduled code upgrade.
			if let Some(expected_at) = Self::code_upgrade_schedule(&para_id) {
				if expected_at <= perceived_relay_block_height {
					let new_code = FutureCode::take(&para_id);
					<Self as Store>::FutureCodeUpgrades::remove(&para_id);

					Self::do_code_upgrade(para_id, perceived_relay_block_height, &new_code);
				}
			}

			if let Some(ref new_code) = full_candidate.commitments.new_validation_code {
				ensure!(
					full_candidate.local_validation.code_upgrade_allowed.is_some(),
					Error::<T>::DisallowedCodeUpgrade,
				);
				ensure!(
					schedule.max_code_size >= new_code.0.len() as u32,
					Error::<T>::ValidationCodeTooLarge,
				);

				if code_upgrade_delay.is_zero() {
					Self::do_code_upgrade(para_id, perceived_relay_block_height, new_code);
				} else {
					<Self as Store>::FutureCodeUpgrades::insert(
						&para_id,
						&(perceived_relay_block_height + code_upgrade_delay),
					);
					FutureCode::insert(
						&para_id,
						new_code,
					);
				}
			}

			let fees = full_candidate.commitments.fees;

			ensure!(
				full_candidate.local_validation.balance >= full_candidate.commitments.fees,
				Error::<T>::CannotPayFees,
			);

			T::ParachainCurrency::deduct(para_id, fees)?;

			Self::verify_candidate_signatures(candidate, &authorities, validator_group, &signing_context)?;

			para_block_hashes.push(candidate.candidate.hash());
		}

		Ok(IncludedBlocks {
			actual_number: relay_height_now,
			session: <session::Module<T>>::current_index(),
			random_seed,
			active_parachains: active_parachains.iter().map(|x| x.0).collect(),
			para_blocks: para_block_hashes,
		})
	}

	/// Checks all signatures from all given `candidates`.
	///
	/// Returns an error if any signature verification failed.
	fn check_candidates_signatures(candidates: &[AttestedCandidate]) -> DispatchResult {
		let authorities = Self::authorities();
		let duty_roster = Self::calculate_duty_roster().0;
		let sorted_validators = make_sorted_duties(&duty_roster.validator_duty);
		let signing_context = Self::signing_context();
		let mut validator_groups = GroupedDutyIter::new(&sorted_validators[..]);

		candidates.iter().try_for_each(|c| {
			let para_id = c.parachain_index();
			let validator_group = validator_groups.group_for(para_id)
				.ok_or(Error::<T>::NoValidatorGroup)?;

			Self::verify_candidate_signatures(c, &authorities, validator_group, &signing_context)
		})
	}

	fn initialize_authorities(authorities: &[ValidatorId]) {
		if !authorities.is_empty() {
			assert!(Authorities::get().is_empty(), "Authorities are already initialized!");
			Authorities::put(authorities);
		}
	}

/*
	// TODO: Consider integrating if needed. (https://github.com/paritytech/polkadot/issues/223)
	/// Extract the parachain heads from the block.
	pub fn parachain_heads(&self) -> &[CandidateReceipt] {
		let x = self.inner.extrinsics.get(PARACHAINS_SET_POSITION as usize).and_then(|xt| match xt.function {
			Call::Parachains(ParachainsCall::set_heads(ref x)) => Some(&x[..]),
			_ => None
		});

		match x {
			Some(x) => x,
			None => panic!("Invalid polkadot block asserted at {:?}", self.file_line),
		}
	}
*/
}

impl<T: Trait> sp_runtime::BoundToRuntimeAppPublic for Module<T> {
	type Public = ValidatorId;
}

impl<T: Trait> session::OneSessionHandler<T::AccountId> for Module<T> {
	type Key = ValidatorId;

	fn on_genesis_session<'a, I: 'a>(validators: I)
		where I: Iterator<Item=(&'a T::AccountId, Self::Key)>
	{
		Self::initialize_authorities(&validators.map(|(_, key)| key).collect::<Vec<_>>());
	}

	fn on_new_session<'a, I: 'a>(changed: bool, validators: I, _queued: I)
		where I: Iterator<Item=(&'a T::AccountId, Self::Key)>
	{
		if changed {
			<Self as Store>::Authorities::put(validators.map(|(_, key)| key).collect::<Vec<_>>());
		}
	}

	fn on_disabled(_i: usize) { }
}

pub type InherentType = Vec<AttestedCandidate>;

impl<T: Trait> ProvideInherent for Module<T> {
	type Call = Call<T>;
	type Error = MakeFatalError<inherents::Error>;
	const INHERENT_IDENTIFIER: InherentIdentifier = NEW_HEADS_IDENTIFIER;

	fn create_inherent(data: &InherentData) -> Option<Self::Call> {
		let data = data.get_data::<InherentType>(&NEW_HEADS_IDENTIFIER)
			.expect("Parachain heads could not be decoded.")
			.expect("No parachain heads found in inherent data.");

		// Temporary solution for:
		// https://github.com/paritytech/polkadot/issues/1327
		if Self::check_candidates_signatures(&data).is_ok() {
			Some(Call::set_heads(data))
		} else {
			Some(Call::set_heads(Vec::new()))
		}
	}
}

/// Ensure that the origin `o` represents a parachain.
/// Returns `Ok` with the parachain ID that effected the extrinsic or an `Err` otherwise.
pub fn ensure_parachain<OuterOrigin>(o: OuterOrigin) -> result::Result<ParaId, BadOrigin>
	where OuterOrigin: Into<result::Result<Origin, OuterOrigin>>
{
	match o.into() {
		Ok(Origin::Parachain(id)) => Ok(id),
		_ => Err(BadOrigin),
	}
}


/// Ensure that double vote reports are only processed if valid.
#[derive(Encode, Decode, Clone, Eq, PartialEq)]
pub struct ValidateDoubleVoteReports<T>(sp_std::marker::PhantomData<T>);

impl<T> sp_std::fmt::Debug for ValidateDoubleVoteReports<T> where
{
	fn fmt(&self, f: &mut sp_std::fmt::Formatter) -> sp_std::fmt::Result {
		write!(f, "ValidateDoubleVoteReports<T>")
	}
}

impl<T> ValidateDoubleVoteReports<T> {
	/// Create a new `ValidateDoubleVoteReports` struct.
	pub fn new() -> Self {
		ValidateDoubleVoteReports(sp_std::marker::PhantomData)
	}
}

/// Custom validity error used while validating double vote reports.
#[derive(RuntimeDebug)]
#[repr(u8)]
pub enum DoubleVoteValidityError {
	/// The authority being reported is not in the authority set.
	NotAnAuthority = 0,

	/// Failed to convert offender's `FullIdentificationOf`.
	FailedToConvertId = 1,

	/// The signature on one or both of the statements in the report is wrong.
	InvalidSignature = 2,

	/// The two statements in the report are not conflicting.
	NotDoubleVote = 3,

	/// Invalid report. Indicates that statement doesn't match the attestation on one of the votes.
	InvalidReport = 4,

	/// The proof provided in the report is not valid.
	InvalidProof = 5,
}

impl<T: Trait + Send + Sync> SignedExtension for ValidateDoubleVoteReports<T> where
	<T as system::Trait>::Call: IsSubType<Call<T>>
{
	const IDENTIFIER: &'static str = "ValidateDoubleVoteReports";
	type AccountId = T::AccountId;
	type Call = <T as system::Trait>::Call;
	type AdditionalSigned = ();
	type Pre = ();

	fn additional_signed(&self)
		-> sp_std::result::Result<Self::AdditionalSigned, TransactionValidityError>
	{
		Ok(())
	}

	fn validate(
		&self,
		_who: &Self::AccountId,
		call: &Self::Call,
		_info: &DispatchInfoOf<Self::Call>,
		_len: usize,
	) -> TransactionValidity {
		let r = ValidTransaction::default();

		if let Some(local_call) = call.is_sub_type() {
			if let Call::report_double_vote(report) = local_call {
				let validators = <session::Module<T>>::validators();

				let expected_session = report.signing_context.session_index;
				let session = report.proof.session();

				if session != expected_session {
					return Err(InvalidTransaction::BadProof.into());
				}

				let authorities = Module::<T>::authorities();
				let offender_idx = match authorities.iter().position(|a| *a == report.identity) {
					Some(idx) => idx,
					None => return Err(InvalidTransaction::Custom(
						DoubleVoteValidityError::NotAnAuthority as u8).into()
					),
				};

				if T::FullIdentificationOf::convert(validators[offender_idx].clone()).is_none() {
					return Err(InvalidTransaction::Custom(
						DoubleVoteValidityError::FailedToConvertId as u8).into()
					);
				}

				report
					.verify::<T>()
					.map_err(|e| TransactionValidityError::from(InvalidTransaction::Custom(e as u8)))?;
			}
		}

		Ok(r)
	}
}


#[cfg(test)]
mod tests {
	use super::*;
	use super::Call as ParachainsCall;
	use bitvec::{bitvec, vec::BitVec};
	use sp_io::TestExternalities;
	use sp_core::{H256, Blake2Hasher, sr25519};
	use sp_trie::NodeCodec;
	use sp_runtime::{
		impl_opaque_keys,
		Perbill, curve::PiecewiseLinear,
		traits::{
			BlakeTwo256, IdentityLookup, SaturatedConversion,
			OpaqueKeys, Extrinsic as ExtrinsicT,
		},
		testing::TestXt,
	};
	use primitives::v0::{
		CandidateReceipt, ValidityAttestation, ValidatorId, Info as ParaInfo,
		Scheduling, CandidateCommitments,
		BlockNumber, Header,
	};
	use keyring::Sr25519Keyring;
	use frame_support::{
		impl_outer_origin, impl_outer_dispatch, assert_ok, assert_err, parameter_types,
		traits::{OnInitialize, OnFinalize},
		weights::DispatchInfo,
	};
	use crate::parachains;
	use crate::registrar;
	use crate::slots;
	use session::{SessionHandler, SessionManager};
	use staking::EraIndex;

	// result of <NodeCodec<Blake2Hasher> as trie_db::NodeCodec<Blake2Hasher>>::hashed_null_node()
	const EMPTY_TRIE_ROOT: [u8; 32] = [
		3, 23, 10, 46, 117, 151, 183, 183, 227, 216, 76, 5, 57, 29, 19, 154,
		98, 177, 87, 231, 135, 134, 216, 192, 130, 242, 157, 207, 76, 17, 19, 20
	];

	impl_outer_origin! {
		pub enum Origin for Test {
			parachains
		}
	}

	impl_outer_dispatch! {
		pub enum Call for Test where origin: Origin {
			parachains::Parachains,
			staking::Staking,
		}
	}

	impl_opaque_keys! {
		pub struct TestSessionKeys {
			pub parachain_validator: super::Module<Test>,
		}
	}

	#[derive(Clone, Eq, PartialEq)]
	pub struct Test;
	parameter_types! {
		pub const BlockHashCount: u32 = 250;
		pub const MaximumBlockWeight: Weight = 4 * 1024 * 1024;
		pub const MaximumBlockLength: u32 = 4 * 1024 * 1024;
		pub const AvailableBlockRatio: Perbill = Perbill::from_percent(75);
	}

	impl system::Trait for Test {
		type BaseCallFilter = ();
		type Origin = Origin;
		type Call = Call;
		type Index = u64;
		type BlockNumber = BlockNumber;
		type Hash = H256;
		type Hashing = BlakeTwo256;
		type AccountId = u64;
		type Lookup = IdentityLookup<u64>;
		type Header = Header;
		type Event = ();
		type BlockHashCount = BlockHashCount;
		type MaximumBlockWeight = MaximumBlockWeight;
		type DbWeight = ();
		type BlockExecutionWeight = ();
		type ExtrinsicBaseWeight = ();
		type MaximumExtrinsicWeight = MaximumBlockWeight;
		type MaximumBlockLength = MaximumBlockLength;
		type AvailableBlockRatio = AvailableBlockRatio;
		type Version = ();
		type ModuleToIndex = ();
		type AccountData = balances::AccountData<u128>;
		type OnNewAccount = ();
		type OnKilledAccount = ();
		type SystemWeightInfo = ();
	}

	impl<C> system::offchain::SendTransactionTypes<C> for Test where
		Call: From<C>,
	{
		type OverarchingCall = Call;
		type Extrinsic = TestXt<Call, ()>;
	}

	parameter_types! {
		pub const Period: BlockNumber = 1;
		pub const Offset: BlockNumber = 0;
		pub const DisabledValidatorsThreshold: Perbill = Perbill::from_percent(17);
	}

	/// Custom `SessionHandler` since we use `TestSessionKeys` as `Keys`.
	pub struct TestSessionHandler;
	impl<AId> SessionHandler<AId> for TestSessionHandler {
		const KEY_TYPE_IDS: &'static [KeyTypeId] = &[PARACHAIN_KEY_TYPE_ID];

		fn on_genesis_session<Ks: OpaqueKeys>(_: &[(AId, Ks)]) {}

		fn on_new_session<Ks: OpaqueKeys>(_: bool, _: &[(AId, Ks)], _: &[(AId, Ks)]) {}

		fn on_before_session_ending() {}

		fn on_disabled(_: usize) {}
	}

	impl session::Trait for Test {
		type Event = ();
		type ValidatorId = u64;
		type ValidatorIdOf = staking::StashOf<Self>;
		type ShouldEndSession = session::PeriodicSessions<Period, Offset>;
		type NextSessionRotation = session::PeriodicSessions<Period, Offset>;
		type SessionManager = session::historical::NoteHistoricalRoot<Self, Staking>;
		type SessionHandler = TestSessionHandler;
		type Keys = TestSessionKeys;
		type DisabledValidatorsThreshold = DisabledValidatorsThreshold;
		type WeightInfo = ();
	}

	impl session::historical::Trait for Test {
		type FullIdentification = staking::Exposure<u64, Balance>;
		type FullIdentificationOf = staking::ExposureOf<Self>;
	}

	parameter_types! {
		pub const MinimumPeriod: u64 = 3;
	}
	impl timestamp::Trait for Test {
		type Moment = u64;
		type OnTimestampSet = ();
		type MinimumPeriod = MinimumPeriod;
		type WeightInfo = ();
	}

	mod time {
		use primitives::v0::{Moment, BlockNumber};
		pub const MILLISECS_PER_BLOCK: Moment = 6000;
		pub const EPOCH_DURATION_IN_BLOCKS: BlockNumber = 1 * HOURS;
		// These time units are defined in number of blocks.
		const MINUTES: BlockNumber = 60_000 / (MILLISECS_PER_BLOCK as BlockNumber);
		const HOURS: BlockNumber = MINUTES * 60;
	}
	parameter_types! {
		pub const EpochDuration: BlockNumber = time::EPOCH_DURATION_IN_BLOCKS;
		pub const ExpectedBlockTime: u64 = time::MILLISECS_PER_BLOCK;
	}

	impl babe::Trait for Test {
		type EpochDuration = EpochDuration;
		type ExpectedBlockTime = ExpectedBlockTime;

		// session module is the trigger
		type EpochChangeTrigger = babe::ExternalTrigger;

		type KeyOwnerProofSystem = ();

		type KeyOwnerProof = <Self::KeyOwnerProofSystem as KeyOwnerProofSystem<(
			KeyTypeId,
			babe::AuthorityId,
		)>>::Proof;

		type KeyOwnerIdentification = <Self::KeyOwnerProofSystem as KeyOwnerProofSystem<(
			KeyTypeId,
			babe::AuthorityId,
		)>>::IdentificationTuple;

		type HandleEquivocation = ();
	}

	parameter_types! {
		pub const ExistentialDeposit: Balance = 1;
	}

	impl balances::Trait for Test {
		type Balance = u128;
		type DustRemoval = ();
		type Event = ();
		type ExistentialDeposit = ExistentialDeposit;
		type AccountStore = System;
		type WeightInfo = ();
	}

	pallet_staking_reward_curve::build! {
		const REWARD_CURVE: PiecewiseLinear<'static> = curve!(
			min_inflation: 0_025_000u64,
			max_inflation: 0_100_000,
			ideal_stake: 0_500_000,
			falloff: 0_050_000,
			max_piece_count: 40,
			test_precision: 0_005_000,
		);
	}

	parameter_types! {
		pub const SessionsPerEra: sp_staking::SessionIndex = 3;
		pub const BondingDuration: staking::EraIndex = 3;
		pub const SlashDeferDuration: staking::EraIndex = 0;
		pub const AttestationPeriod: BlockNumber = 100;
		pub const RewardCurve: &'static PiecewiseLinear<'static> = &REWARD_CURVE;
		pub const MaxNominatorRewardedPerValidator: u32 = 64;
		pub const ElectionLookahead: BlockNumber = 0;
		pub const StakingUnsignedPriority: u64 = u64::max_value() / 2;
	}

	pub struct CurrencyToVoteHandler;

	impl Convert<u128, u128> for CurrencyToVoteHandler {
		fn convert(x: u128) -> u128 { x }
	}

	impl Convert<u128, u64> for CurrencyToVoteHandler {
		fn convert(x: u128) -> u64 { x.saturated_into() }
	}

	impl staking::Trait for Test {
		type RewardRemainder = ();
		type CurrencyToVote = CurrencyToVoteHandler;
		type Event = ();
		type Currency = Balances;
		type Slash = ();
		type Reward = ();
		type SessionsPerEra = SessionsPerEra;
		type BondingDuration = BondingDuration;
		type SlashDeferDuration = SlashDeferDuration;
		type SlashCancelOrigin = system::EnsureRoot<Self::AccountId>;
		type SessionInterface = Self;
		type UnixTime = timestamp::Module<Test>;
		type RewardCurve = RewardCurve;
		type MaxNominatorRewardedPerValidator = MaxNominatorRewardedPerValidator;
		type NextNewSession = Session;
		type ElectionLookahead = ElectionLookahead;
		type Call = Call;
		type UnsignedPriority = StakingUnsignedPriority;
		type MaxIterations = ();
		type MinSolutionScoreBump = ();
		type WeightInfo = ();
	}

	impl attestations::Trait for Test {
		type AttestationPeriod = AttestationPeriod;
		type ValidatorIdentities = ValidatorIdentities<Test>;
		type RewardAttestation = ();
	}

	parameter_types!{
		pub const LeasePeriod: BlockNumber = 10;
		pub const EndingPeriod: BlockNumber = 3;
	}

	impl slots::Trait for Test {
		type Event = ();
		type Currency = Balances;
		type Parachains = registrar::Module<Test>;
		type EndingPeriod = EndingPeriod;
		type LeasePeriod = LeasePeriod;
		type Randomness = RandomnessCollectiveFlip;
	}

	parameter_types! {
		pub const ParathreadDeposit: Balance = 10;
		pub const QueueSize: usize = 2;
		pub const MaxRetries: u32 = 3;
	}

	impl registrar::Trait for Test {
		type Event = ();
		type Origin = Origin;
		type Currency = Balances;
		type ParathreadDeposit = ParathreadDeposit;
		type SwapAux = slots::Module<Test>;
		type QueueSize = QueueSize;
		type MaxRetries = MaxRetries;
	}

	parameter_types! {
		pub OffencesWeightSoftLimit: Weight = Perbill::from_percent(60) * MaximumBlockWeight::get();
	}

	impl offences::Trait for Test {
		type Event = ();
		type IdentificationTuple = session::historical::IdentificationTuple<Self>;
		type OnOffenceHandler = Staking;
		type WeightSoftLimit = OffencesWeightSoftLimit;
		type WeightInfo = ();
	}

	parameter_types! {
		pub const MaxHeadDataSize: u32 = 100;
		pub const MaxCodeSize: u32 = 100;

		pub const ValidationUpgradeFrequency: BlockNumber = 10;
		pub const ValidationUpgradeDelay: BlockNumber = 2;
		pub const SlashPeriod: BlockNumber = 50;
	}

	// This is needed for a custom `AccountId` type which is `u64` in testing here.
	pub mod test_keys {
		use sp_core::{crypto::KeyTypeId, sr25519};
		pub const KEY_TYPE: KeyTypeId = KeyTypeId(*b"test");

		mod app {
			use sp_application_crypto::{app_crypto, sr25519};
			use super::super::Parachains;

			app_crypto!(sr25519, super::KEY_TYPE);

			impl sp_runtime::traits::IdentifyAccount for Public {
				type AccountId = u64;

				fn into_account(self) -> Self::AccountId {
					Parachains::authorities().iter().position(|b| *b == self.0.clone().into()).unwrap() as u64
				}
			}
		}

		pub type ReporterId = app::Public;
		pub struct ReporterAuthorityId;
		impl system::offchain::AppCrypto<ReporterId, sr25519::Signature> for ReporterAuthorityId {
			type RuntimeAppPublic = ReporterId;
			type GenericSignature = sr25519::Signature;