registrar.rs

// Copyright 2017-2020 Parity Technologies (UK) Ltd.
// This file is part of Polkadot.

// Polkadot is free software: you can redistribute it and/or modify
// it under the terms of the GNU General Public License as published by
// the Free Software Foundation, either version 3 of the License, or
// (at your option) any later version.

// Polkadot is distributed in the hope that it will be useful,
// but WITHOUT ANY WARRANTY; without even the implied warranty of
// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
// GNU General Public License for more details.

// You should have received a copy of the GNU General Public License
// along with Polkadot.  If not, see <http://www.gnu.org/licenses/>.

//! Module to handle which parachains/parathreads (collectively referred to as "paras") are
//! registered and which are scheduled. Doesn't manage any of the actual execution/validation logic
//! which is left to `parachains.rs`.

use sp_std::{prelude::*, result};
#[cfg(any(feature = "std", test))]
use sp_std::marker::PhantomData;
use codec::{Encode, Decode};

use sp_runtime::{
	transaction_validity::{TransactionValidityError, ValidTransaction, TransactionValidity},
	traits::{Hash as HashT, SignedExtension}
};

use frame_support::{
	decl_storage, decl_module, decl_event, decl_error, ensure,
	dispatch::{DispatchResult, IsSubType}, traits::{Get, Currency, ReservableCurrency},
	weights::{SimpleDispatchInfo, DispatchInfo},
};
use system::{self, ensure_root, ensure_signed};
use primitives::parachain::{
	Id as ParaId, CollatorId, Scheduling, LOWEST_USER_ID, SwapAux, Info as ParaInfo, ActiveParas,
	Retriable
};
use crate::parachains;
use sp_runtime::transaction_validity::InvalidTransaction;

/// Parachain registration API.
pub trait Registrar<AccountId> {
	/// Create a new unique parachain identity for later registration.
	fn new_id() -> ParaId;

	/// Checks whether the given initial head data size falls within the limit.
	fn head_data_size_allowed(head_data_size: u32) -> bool;

	/// Checks whether the given validation code falls within the limit.
	fn code_size_allowed(code_size: u32) -> bool;

	/// Register a parachain with given `code` and `initial_head_data`. `id` must not yet be registered or it will
	/// result in a error.
	///
	/// This does not enforce any code size or initial head data limits, as these
	/// are governable and parameters for parachain initialization are often
	/// determined long ahead-of-time. Not checking these values ensures that changes to limits
	/// do not invalidate in-progress auction winners.
	fn register_para(
		id: ParaId,
		info: ParaInfo,
		code: Vec<u8>,
		initial_head_data: Vec<u8>,
	) -> DispatchResult;

	/// Deregister a parachain with given `id`. If `id` is not currently registered, an error is returned.
	fn deregister_para(id: ParaId) -> DispatchResult;
}

impl<T: Trait> Registrar<T::AccountId> for Module<T> {
	fn new_id() -> ParaId {
		<NextFreeId>::mutate(|n| { let r = *n; *n = ParaId::from(u32::from(*n) + 1); r })
	}

	fn head_data_size_allowed(head_data_size: u32) -> bool {
		head_data_size <= <T as parachains::Trait>::MaxHeadDataSize::get()
	}

	fn code_size_allowed(code_size: u32) -> bool {
		code_size <= <T as parachains::Trait>::MaxCodeSize::get()
	}

	fn register_para(
		id: ParaId,
		info: ParaInfo,
		code: Vec<u8>,
		initial_head_data: Vec<u8>,
	) -> DispatchResult {
		ensure!(!Paras::contains_key(id), Error::<T>::ParaAlreadyExists);
		if let Scheduling::Always = info.scheduling {
			Parachains::mutate(|parachains|
				match parachains.binary_search(&id) {
					Ok(_) => Err(Error::<T>::ParaAlreadyExists),
					Err(idx) => {
						parachains.insert(idx, id);
						Ok(())
					}
				}
			)?;
		}
		<parachains::Module<T>>::initialize_para(id, code, initial_head_data);
		Paras::insert(id, info);
		Ok(())
	}

	fn deregister_para(id: ParaId) -> DispatchResult {
		let info = Paras::take(id).ok_or(Error::<T>::InvalidChainId)?;
		if let Scheduling::Always = info.scheduling {
			Parachains::mutate(|parachains|
				parachains.binary_search(&id)
					.map(|index| parachains.remove(index))
					.map_err(|_| Error::<T>::InvalidChainId)
			)?;
		}
		<parachains::Module<T>>::cleanup_para(id);
		Paras::remove(id);
		Ok(())
	}
}

type BalanceOf<T> =
	<<T as Trait>::Currency as Currency<<T as system::Trait>::AccountId>>::Balance;

pub trait Trait: parachains::Trait {
	/// The overarching event type.
	type Event: From<Event> + Into<<Self as system::Trait>::Event>;

	/// The aggregated origin type must support the parachains origin. We require that we can
	/// infallibly convert between this origin and the system origin, but in reality, they're the
	/// same type, we just can't express that to the Rust type system without writing a `where`
	/// clause everywhere.
	type Origin: From<<Self as system::Trait>::Origin>
		+ Into<result::Result<parachains::Origin, <Self as Trait>::Origin>>;

	/// The system's currency for parathread payment.
	type Currency: ReservableCurrency<Self::AccountId>;

	/// The deposit to be paid to run a parathread.
	type ParathreadDeposit: Get<BalanceOf<Self>>;

	/// Handler for when two ParaIds are swapped.
	type SwapAux: SwapAux;

	/// The number of items in the parathread queue, aka the number of blocks in advance to schedule
	/// parachain execution.
	type QueueSize: Get<usize>;

	/// The number of rotations that you will have as grace if you miss a block.
	type MaxRetries: Get<u32>;
}

decl_storage! {
	trait Store for Module<T: Trait> as Registrar {
		// Vector of all parachain IDs, in ascending order.
		Parachains: Vec<ParaId>;

		/// The number of threads to schedule per block.
		ThreadCount: u32;

		/// An array of the queue of set of threads scheduled for the coming blocks; ordered by
		/// ascending para ID. There can be no duplicates of para ID in each list item.
		SelectedThreads: Vec<Vec<(ParaId, CollatorId)>>;

		/// Parathreads/chains scheduled for execution this block. If the collator ID is set, then
		/// a particular collator has already been chosen for the next block, and no other collator
		/// may provide the block. In this case we allow the possibility of the combination being
		/// retried in a later block, expressed by `Retriable`.
		///
		/// Ordered by ParaId.
		Active: Vec<(ParaId, Option<(CollatorId, Retriable)>)>;

		/// The next unused ParaId value. Start this high in order to keep low numbers for
		/// system-level chains.
		NextFreeId: ParaId = LOWEST_USER_ID;

		/// Pending swap operations.
		PendingSwap: map hasher(twox_64_concat) ParaId => Option<ParaId>;

		/// Map of all registered parathreads/chains.
		Paras get(fn paras): map hasher(twox_64_concat) ParaId => Option<ParaInfo>;

		/// The current queue for parathreads that should be retried.
		RetryQueue get(fn retry_queue): Vec<Vec<(ParaId, CollatorId)>>;

		/// Users who have paid a parathread's deposit
		Debtors: map hasher(twox_64_concat) ParaId => T::AccountId;
	}
	add_extra_genesis {
		config(parachains): Vec<(ParaId, Vec<u8>, Vec<u8>)>;
		config(_phdata): PhantomData<T>;
		build(build::<T>);
	}
}

#[cfg(feature = "std")]
fn build<T: Trait>(config: &GenesisConfig<T>) {
	let mut p = config.parachains.clone();
	p.sort_unstable_by_key(|&(ref id, _, _)| *id);
	p.dedup_by_key(|&mut (ref id, _, _)| *id);

	let only_ids: Vec<ParaId> = p.iter().map(|&(ref id, _, _)| id).cloned().collect();

	Parachains::put(&only_ids);

	for (id, code, genesis) in p {
		Paras::insert(id, &primitives::parachain::PARACHAIN_INFO);
		// no ingress -- a chain cannot be routed to until it is live.
		<parachains::Code>::insert(&id, &code);
		<parachains::Heads>::insert(&id, &genesis);
		// Save initial parachains in registrar
		Paras::insert(id, ParaInfo { scheduling: Scheduling::Always })
	}
}

/// Swap the existence of two items, provided by value, within an ordered list.
///
/// If neither item exists, or if both items exist this will do nothing. If exactly one of the
/// items exists, then it will be removed and the other inserted.
pub fn swap_ordered_existence<T: PartialOrd + Ord + Copy>(ids: &mut [T], one: T, other: T) {
	let maybe_one_pos = ids.binary_search(&one);
	let maybe_other_pos = ids.binary_search(&other);
	match (maybe_one_pos, maybe_other_pos) {
		(Ok(one_pos), Err(_)) => ids[one_pos] = other,
		(Err(_), Ok(other_pos)) => ids[other_pos] = one,
		_ => return,
	};
	ids.sort();
}

decl_error! {
	pub enum Error for Module<T: Trait> {
		/// Parachain already exists.
		ParaAlreadyExists,
		/// Invalid parachain ID.
		InvalidChainId,
		/// Invalid parathread ID.
		InvalidThreadId,
		/// Invalid para code size.
		CodeTooLarge,
		/// Invalid para head data size.
		HeadDataTooLarge,
	}
}

decl_module! {
	/// Parachains module.
	pub struct Module<T: Trait> for enum Call where origin: <T as system::Trait>::Origin {
		type Error = Error<T>;

		fn deposit_event() = default;

		/// Register a parachain with given code. Must be called by root.
		/// Fails if given ID is already used.
		///
		/// Unlike the `Registrar` trait function of the same name, this
		/// checks the code and head data against size limits.
		#[weight = SimpleDispatchInfo::FixedOperational(5_000_000)]
		pub fn register_para(origin,
			#[compact] id: ParaId,
			info: ParaInfo,
			code: Vec<u8>,
			initial_head_data: Vec<u8>,
		) -> DispatchResult {
			ensure_root(origin)?;

			ensure!(
				<Self as Registrar<T::AccountId>>::code_size_allowed(code.len() as _),
				Error::<T>::CodeTooLarge,
			);

			ensure!(
				<Self as Registrar<T::AccountId>>::head_data_size_allowed(
					initial_head_data.len() as _
				),
				Error::<T>::HeadDataTooLarge,
			);
			<Self as Registrar<T::AccountId>>::
				register_para(id, info, code, initial_head_data)
		}

		/// Deregister a parachain with given id
		#[weight = SimpleDispatchInfo::FixedOperational(10_000)]
		pub fn deregister_para(origin, #[compact] id: ParaId) -> DispatchResult {
			ensure_root(origin)?;
			<Self as Registrar<T::AccountId>>::deregister_para(id)
		}

		/// Reset the number of parathreads that can pay to be scheduled in a single block.
		///
		/// - `count`: The number of parathreads.
		///
		/// Must be called from Root origin.
		fn set_thread_count(origin, count: u32) {
			ensure_root(origin)?;
			ThreadCount::put(count);
		}

		/// Register a parathread for immediate use.
		///
		/// Must be sent from a Signed origin that is able to have ParathreadDeposit reserved.
		/// `code` and `initial_head_data` are used to initialize the parathread's state.
		///
		/// Unlike `register_para`, this function does check that the maximum code size
		/// and head data size are respected, as parathread registration is an atomic
		/// action.
		fn register_parathread(origin,
			code: Vec<u8>,
			initial_head_data: Vec<u8>,
		) {
			let who = ensure_signed(origin)?;

			<T as Trait>::Currency::reserve(&who, T::ParathreadDeposit::get())?;

			let info = ParaInfo {
				scheduling: Scheduling::Dynamic,
			};

			ensure!(
				<Self as Registrar<T::AccountId>>::code_size_allowed(code.len() as _),
				Error::<T>::CodeTooLarge,
			);

			ensure!(
				<Self as Registrar<T::AccountId>>::head_data_size_allowed(
					initial_head_data.len() as _
				),
				Error::<T>::HeadDataTooLarge,
			);

			let id = <Self as Registrar<T::AccountId>>::new_id();

			let _ = <Self as Registrar<T::AccountId>>::
				register_para(id, info, code, initial_head_data);

			<Debtors<T>>::insert(id, who);

			Self::deposit_event(Event::ParathreadRegistered(id));
		}

		/// Place a bid for a parathread to be progressed in the next block.
		///
		/// This is a kind of special transaction that should be heavily prioritized in the
		/// transaction pool according to the `value`; only `ThreadCount` of them may be presented
		/// in any single block.
		fn select_parathread(origin,
			#[compact] _id: ParaId,
			_collator: CollatorId,
			_head_hash: T::Hash,
		) {
			ensure_signed(origin)?;
			// Everything else is checked for in the transaction `SignedExtension`.
		}

		/// Deregister a parathread and retrieve the deposit.
		///
		/// Must be sent from a `Parachain` origin which is currently a parathread.
		///
		/// Ensure that before calling this that any funds you want emptied from the parathread's
		/// account is moved out; after this it will be impossible to retrieve them (without
		/// governance intervention).
		fn deregister_parathread(origin) {
			let id = parachains::ensure_parachain(<T as Trait>::Origin::from(origin))?;

			let info = Paras::get(id).ok_or(Error::<T>::InvalidChainId)?;
			if let Scheduling::Dynamic = info.scheduling {} else { Err(Error::<T>::InvalidThreadId)? }

			<Self as Registrar<T::AccountId>>::deregister_para(id)?;
			Self::force_unschedule(|i| i == id);

			let debtor = <Debtors<T>>::take(id);
			let _ = <T as Trait>::Currency::unreserve(&debtor, T::ParathreadDeposit::get());

			Self::deposit_event(Event::ParathreadRegistered(id));
		}

		/// Swap a parachain with another parachain or parathread. The origin must be a `Parachain`.
		/// The swap will happen only if there is already an opposite swap pending. If there is not,
		/// the swap will be stored in the pending swaps map, ready for a later confirmatory swap.
		///
		/// The `ParaId`s remain mapped to the same head data and code so external code can rely on
		/// `ParaId` to be a long-term identifier of a notional "parachain". However, their
		/// scheduling info (i.e. whether they're a parathread or parachain), auction information
		/// and the auction deposit are switched.
		fn swap(origin, #[compact] other: ParaId) {
			let id = parachains::ensure_parachain(<T as Trait>::Origin::from(origin))?;

			if PendingSwap::get(other) == Some(id) {
				// actually do the swap.
				T::SwapAux::ensure_can_swap(id, other)?;

				// Remove intention to swap.
				PendingSwap::remove(other);
				Self::force_unschedule(|i| i == id || i == other);
				Parachains::mutate(|ids| swap_ordered_existence(ids, id, other));
				Paras::mutate(id, |i|
					Paras::mutate(other, |j|
						sp_std::mem::swap(i, j)
					)
				);

				<Debtors<T>>::mutate(id, |i|
					<Debtors<T>>::mutate(other, |j|
						sp_std::mem::swap(i, j)
					)
				);
				let _ = T::SwapAux::on_swap(id, other);
			} else {
				PendingSwap::insert(id, other);
			}
		}

		/// Block initializer. Clears SelectedThreads and constructs/replaces Active.
		fn on_initialize() {
			let next_up = SelectedThreads::mutate(|t| {
				let r = if t.len() >= T::QueueSize::get() {
					// Take the first set of parathreads in queue
					t.remove(0)
				} else {
					vec![]
				};
				while t.len() < T::QueueSize::get() {
					t.push(vec![]);
				}
				r
			});
			// mutable so that we can replace with `None` if parathread appears in new schedule.
			let mut retrying = Self::take_next_retry();
			if let Some(((para, _), _)) = retrying {
				// this isn't really ideal: better would be if there were an earlier pass that set
				// retrying to the first item in the Missed queue that isn't already scheduled, but
				// this is potentially O(m*n) in terms of missed queue size and parathread pool size.
				if next_up.iter().any(|x| x.0 == para) {
					retrying = None
				}
			}

			let mut paras = Parachains::get().into_iter()
				.map(|id| (id, None))
				.chain(next_up.into_iter()
					.map(|(para, collator)|
						(para, Some((collator, Retriable::WithRetries(0))))
					)
				).chain(retrying.into_iter()
					.map(|((para, collator), retries)|
						(para, Some((collator, Retriable::WithRetries(retries + 1))))
					)
				).collect::<Vec<_>>();
			// for Rust's timsort algorithm, sorting a concatenation of two sorted ranges is near
			// O(N).
			paras.sort_by_key(|&(ref id, _)| *id);

			Active::put(paras);
		}

		fn on_finalize() {
			// a block without this will panic, but let's not panic here.
			if let Some(proceeded_vec) = parachains::DidUpdate::get() {
				// Active is sorted and DidUpdate is a sorted subset of its elements.
				//
				// We just go through the contents of active and find any items that don't appear in
				// DidUpdate *and* which are enabled for retry.
				let mut proceeded = proceeded_vec.into_iter();
				let mut i = proceeded.next();
				for sched in Active::get().into_iter() {
					match i {
						// Scheduled parachain proceeded properly. Move onto next item.
						Some(para) if para == sched.0 => i = proceeded.next(),
						// Scheduled `sched` missed their block.
						// Queue for retry if it's allowed.
						_ => if let (i, Some((c, Retriable::WithRetries(n)))) = sched {
							Self::retry_later((i, c), n)
						},
					}
				}
			}
		}
	}
}

decl_event!{
	pub enum Event {
		/// A parathread was registered; its new ID is supplied.
		ParathreadRegistered(ParaId),

		/// The parathread of the supplied ID was de-registered.
		ParathreadDeregistered(ParaId),
	}
}

impl<T: Trait> Module<T> {
        /// Ensures that the given `ParaId` corresponds to a registered parathread, and returns a descriptor if so.
	pub fn ensure_thread_id(id: ParaId) -> Option<ParaInfo> {
		Paras::get(id).and_then(|info| if let Scheduling::Dynamic = info.scheduling {
			Some(info)
		} else {
			None
		})
	}

	fn retry_later(sched: (ParaId, CollatorId), retries: u32) {
		if retries < T::MaxRetries::get() {
			RetryQueue::mutate(|q| {
				q.resize(T::MaxRetries::get() as usize, vec![]);
				q[retries as usize].push(sched);
			});
		}
	}

	fn take_next_retry() -> Option<((ParaId, CollatorId), u32)> {
		RetryQueue::mutate(|q| {
			for (i, q) in q.iter_mut().enumerate() {
				if !q.is_empty() {
					return Some((q.remove(0), i as u32));
				}
			}
			None
		})
	}

	/// Forcibly remove the threads matching `m` from all current and future scheduling.
	fn force_unschedule(m: impl Fn(ParaId) -> bool) {
		RetryQueue::mutate(|qs| for q in qs.iter_mut() {
			q.retain(|i| !m(i.0))
		});
		SelectedThreads::mutate(|qs| for q in qs.iter_mut() {
			q.retain(|i| !m(i.0))
		});
		Active::mutate(|a| for i in a.iter_mut() {
			if m(i.0) {
				if let Some((_, ref mut r)) = i.1 {
					*r = Retriable::Never;
				}
			}
		});
	}
}

impl<T: Trait> ActiveParas for Module<T> {
	fn active_paras() -> Vec<(ParaId, Option<(CollatorId, Retriable)>)> {
		Active::get()
	}
}

/// Ensure that parathread selections happen prioritized by fees.
#[derive(Encode, Decode, Clone, Eq, PartialEq)]
pub struct LimitParathreadCommits<T: Trait + Send + Sync>(sp_std::marker::PhantomData<T>) where
	<T as system::Trait>::Call: IsSubType<Module<T>, T>;

impl<T: Trait + Send + Sync> sp_std::fmt::Debug for LimitParathreadCommits<T> where
	<T as system::Trait>::Call: IsSubType<Module<T>, T>
{
	fn fmt(&self, f: &mut sp_std::fmt::Formatter) -> sp_std::fmt::Result {
		write!(f, "LimitParathreadCommits<T>")
	}
}

/// Custom validity errors used in Polkadot while validating transactions.
#[repr(u8)]
pub enum ValidityError {
	/// Parathread ID has already been submitted for this block.
	Duplicate = 0,
	/// Parathread ID does not identify a parathread.
	InvalidId = 1,
}

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

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

	fn validate(
		&self,
		_who: &Self::AccountId,
		call: &Self::Call,
		_info: DispatchInfo,
		_len: usize,
	) -> TransactionValidity {
		let mut r = ValidTransaction::default();
		if let Some(local_call) = call.is_sub_type() {
			if let Call::select_parathread(id, collator, hash) = local_call {
				// ensure that the para ID is actually a parathread.
				let e = TransactionValidityError::from(InvalidTransaction::Custom(ValidityError::InvalidId as u8));
				<Module<T>>::ensure_thread_id(*id).ok_or(e)?;

				// ensure that we haven't already had a full complement of selected parathreads.
				let mut upcoming_selected_threads = SelectedThreads::get();
				if upcoming_selected_threads.is_empty() {
					upcoming_selected_threads.push(vec![]);
				}
				let i = upcoming_selected_threads.len() - 1;
				let selected_threads = &mut upcoming_selected_threads[i];
				let thread_count = ThreadCount::get() as usize;
				ensure!(
					selected_threads.len() < thread_count,
					InvalidTransaction::ExhaustsResources,
				);

				// ensure that this is not selecting a duplicate parathread ID
				let e = TransactionValidityError::from(InvalidTransaction::Custom(ValidityError::Duplicate as u8));
				let pos = selected_threads
					.binary_search_by(|&(ref other_id, _)| other_id.cmp(id))
					.err()
					.ok_or(e)?;

				// ensure that this is a live bid (i.e. that the thread's chain head matches)
				let e = TransactionValidityError::from(InvalidTransaction::Custom(ValidityError::InvalidId as u8));
				let head = <parachains::Module<T>>::parachain_head(id).ok_or(e)?;
				let actual = T::Hashing::hash(&head);
				ensure!(&actual == hash, InvalidTransaction::Stale);

				// updated the selected threads.
				selected_threads.insert(pos, (*id, collator.clone()));
				sp_std::mem::drop(selected_threads);
				SelectedThreads::put(upcoming_selected_threads);

				// provides the state-transition for this head-data-hash; this should cue the pool
				// to throw out competing transactions with lesser fees.
				r.provides = vec![hash.encode()];
			}
		}
		Ok(r)
	}
}

#[cfg(test)]
mod tests {
	use super::*;
	use bitvec::vec::BitVec;
	use sp_io::TestExternalities;
	use sp_core::{H256, Pair};
	use sp_runtime::{
		traits::{
			BlakeTwo256, IdentityLookup, OnInitialize, OnFinalize, Dispatchable,
			AccountIdConversion,
		}, testing::{UintAuthorityId, Header}, KeyTypeId, Perbill, curve::PiecewiseLinear,
	};
	use primitives::{
		parachain::{
			ValidatorId, Info as ParaInfo, Scheduling, LOWEST_USER_ID, AttestedCandidate,
			CandidateReceipt, HeadData, ValidityAttestation, Statement, Chain,
			CollatorPair, CandidateCommitments, GlobalValidationSchedule, LocalValidationData,
		},
		Balance, BlockNumber,
	};
	use frame_support::{
		traits::KeyOwnerProofSystem,
		impl_outer_origin, impl_outer_dispatch, assert_ok, parameter_types, assert_noop,
	};
	use keyring::Sr25519Keyring;

	use crate::parachains;
	use crate::slots;
	use crate::attestations;

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

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

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

	#[derive(Clone, Eq, PartialEq)]
	pub struct Test;
	parameter_types! {
		pub const BlockHashCount: u32 = 250;
		pub const MaximumBlockWeight: u32 = 4 * 1024 * 1024;
		pub const MaximumBlockLength: u32 = 4 * 1024 * 1024;
		pub const AvailableBlockRatio: Perbill = Perbill::from_percent(75);
	}
	impl system::Trait for Test {
		type Origin = Origin;
		type Call = Call;
		type Index = u64;
		type BlockNumber = u64;
		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 MaximumBlockLength = MaximumBlockLength;
		type AvailableBlockRatio = AvailableBlockRatio;
		type Version = ();
		type ModuleToIndex = ();
		type AccountData = balances::AccountData<u128>;
		type OnNewAccount = ();
		type OnKilledAccount = Balances;
	}

	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;
	}

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

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

	parameter_types!{
		pub const SlashDeferDuration: staking::EraIndex = 7;
		pub const AttestationPeriod: BlockNumber = 100;
		pub const MinimumPeriod: u64 = 3;
		pub const SessionsPerEra: sp_staking::SessionIndex = 6;
		pub const BondingDuration: staking::EraIndex = 28;
		pub const MaxNominatorRewardedPerValidator: u32 = 64;
	}

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

	parameter_types! {
		pub const Period: BlockNumber = 1;
		pub const Offset: BlockNumber = 0;
		pub const DisabledValidatorsThreshold: Perbill = Perbill::from_percent(17);
		pub const RewardCurve: &'static PiecewiseLinear<'static> = &REWARD_CURVE;
	}

	impl session::Trait for Test {
		type SessionManager = ();
		type Keys = UintAuthorityId;
		type ShouldEndSession = session::PeriodicSessions<Period, Offset>;
		type SessionHandler = session::TestSessionHandler;
		type Event = ();
		type ValidatorId = u64;
		type ValidatorIdOf = ();
		type DisabledValidatorsThreshold = DisabledValidatorsThreshold;
	}

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

	impl staking::Trait for Test {
		type RewardRemainder = ();
		type CurrencyToVote = ();
		type Event = ();
		type Currency = balances::Module<Test>;
		type Slash = ();
		type Reward = ();
		type SessionsPerEra = SessionsPerEra;
		type BondingDuration = BondingDuration;
		type SlashDeferDuration = SlashDeferDuration;
		type SlashCancelOrigin = system::EnsureRoot<Self::AccountId>;
		type SessionInterface = Self;
		type Time = timestamp::Module<Test>;
		type RewardCurve = RewardCurve;
		type MaxNominatorRewardedPerValidator = MaxNominatorRewardedPerValidator;
	}

	impl timestamp::Trait for Test {
		type Moment = u64;
		type OnTimestampSet = ();
		type MinimumPeriod = MinimumPeriod;
	}

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

	impl parachains::Trait for Test {
		type Origin = Origin;
		type Call = Call;
		type ParachainCurrency = balances::Module<Test>;
		type ActiveParachains = Registrar;
		type Registrar = Registrar;
		type Randomness = RandomnessCollectiveFlip;
		type MaxCodeSize = MaxCodeSize;
		type MaxHeadDataSize = MaxHeadDataSize;
		type Proof = session::historical::Proof;
		type KeyOwnerProofSystem = session::historical::Module<Test>;
		type IdentificationTuple = <Self::KeyOwnerProofSystem as KeyOwnerProofSystem<(KeyTypeId, Vec<u8>)>>::IdentificationTuple;
		type ReportOffence = ();
	}

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

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

	type Balances = balances::Module<Test>;
	type Parachains = parachains::Module<Test>;
	type System = system::Module<Test>;
	type Slots = slots::Module<Test>;
	type Registrar = Module<Test>;
	type RandomnessCollectiveFlip = randomness_collective_flip::Module<Test>;

	const AUTHORITY_KEYS: [Sr25519Keyring; 8] = [
		Sr25519Keyring::Alice,
		Sr25519Keyring::Bob,
		Sr25519Keyring::Charlie,
		Sr25519Keyring::Dave,
		Sr25519Keyring::Eve,
		Sr25519Keyring::Ferdie,
		Sr25519Keyring::One,
		Sr25519Keyring::Two,
	];

	fn new_test_ext(parachains: Vec<(ParaId, Vec<u8>, Vec<u8>)>) -> TestExternalities {
		let mut t = system::GenesisConfig::default().build_storage::<Test>().unwrap();

		let authority_keys = [
			Sr25519Keyring::Alice,
			Sr25519Keyring::Bob,
			Sr25519Keyring::Charlie,
			Sr25519Keyring::Dave,
			Sr25519Keyring::Eve,
			Sr25519Keyring::Ferdie,
			Sr25519Keyring::One,
			Sr25519Keyring::Two,
		];

		// stashes are the index.
		let session_keys: Vec<_> = authority_keys.iter().enumerate()
			.map(|(i, _k)| (i as u64, i as u64, UintAuthorityId(i as u64)))
			.collect();

		let authorities: Vec<_> = authority_keys.iter().map(|k| ValidatorId::from(k.public())).collect();

		let balances: Vec<_> = (0..authority_keys.len()).map(|i| (i as u64, 10_000_000)).collect();

		parachains::GenesisConfig {
			authorities: authorities.clone(),
		}.assimilate_storage::<Test>(&mut t).unwrap();

		GenesisConfig::<Test> {
			parachains,
			_phdata: Default::default(),
		}.assimilate_storage(&mut t).unwrap();

		session::GenesisConfig::<Test> {
			keys: session_keys,
		}.assimilate_storage(&mut t).unwrap();

		balances::GenesisConfig::<Test> {
			balances,
		}.assimilate_storage(&mut t).unwrap();

		t.into()
	}

	fn init_block() {
		println!("Initializing {}", System::block_number());
		System::on_initialize(System::block_number());
		Registrar::on_initialize(System::block_number());
		Parachains::on_initialize(System::block_number());
		Slots::on_initialize(System::block_number());
	}

	fn run_to_block(n: u64) {
		println!("Running until block {}", n);
		while System::block_number() < n {
			if System::block_number() > 1 {
				println!("Finalizing {}", System::block_number());
				if !parachains::DidUpdate::exists() {
					println!("Null heads update");
					assert_ok!(Parachains::set_heads(system::RawOrigin::None.into(), vec![]));
				}
				Slots::on_finalize(System::block_number());
				Parachains::on_finalize(System::block_number());
				Registrar::on_finalize(System::block_number());
				System::on_finalize(System::block_number());
			}
			System::set_block_number(System::block_number() + 1);
			init_block();
		}
	}

	fn schedule_thread(id: ParaId, head_data: &[u8], col: &CollatorId) {
		let tx: LimitParathreadCommits<Test> = LimitParathreadCommits(Default::default());
		let hdh = BlakeTwo256::hash(head_data);
		let inner_call = super::Call::select_parathread(id, col.clone(), hdh);
		let call = Call::Registrar(inner_call);
		let origin = 4u64;
		assert!(tx.validate(&origin, &call, Default::default(), 0).is_ok());
		assert_ok!(call.dispatch(Origin::signed(origin)));
	}

	fn user_id(i: u32) -> ParaId {
		LOWEST_USER_ID + i
	}

	fn attest(id: ParaId, collator: &CollatorPair, head_data: &[u8], block_data: &[u8]) -> AttestedCandidate {
		let pov_block_hash = BlakeTwo256::hash(block_data);
		let relay_parent = System::parent_hash();
		let candidate = CandidateReceipt {
			parachain_index: id,
			relay_parent,
			head_data: HeadData(head_data.to_vec()),
			collator: collator.public(),
			signature: pov_block_hash.using_encoded(|d| collator.sign(d)),
			pov_block_hash,
			global_validation: GlobalValidationSchedule {
				max_code_size: <Test as parachains::Trait>::MaxCodeSize::get(),
				max_head_data_size: <Test as parachains::Trait>::MaxHeadDataSize::get(),
			},
			local_validation: LocalValidationData {
				balance: Balances::free_balance(&id.into_account()),
				parent_head: HeadData(Parachains::parachain_head(&id).unwrap()),
			},
			commitments: CandidateCommitments {
				fees: 0,
				upward_messages: vec![],
				erasure_root: [1; 32].into(),
			},
		};
		let (candidate, _) = candidate.abridge();
		let candidate_hash = candidate.hash();
		let payload = (Statement::Valid(candidate_hash), System::parent_hash()).encode();
		let roster = Parachains::calculate_duty_roster().0.validator_duty;
		AttestedCandidate {
			candidate,
			validity_votes: AUTHORITY_KEYS.iter()
				.enumerate()
				.filter(|(i, _)| roster[*i] == Chain::Parachain(id))
				.map(|(_, k)| k.sign(&payload).into())
				.map(ValidityAttestation::Explicit)
				.collect(),
			validator_indices: roster.iter()
				.map(|i| i == &Chain::Parachain(id))
				.collect::<BitVec::<_, _>>(),
		}
	}

	#[test]
	fn basic_setup_works() {
		new_test_ext(vec![]).execute_with(|| {
			assert_eq!(super::Parachains::get(), vec![]);
			assert_eq!(ThreadCount::get(), 0);
			assert_eq!(Active::get(), vec![]);
			assert_eq!(NextFreeId::get(), LOWEST_USER_ID);
			assert_eq!(PendingSwap::get(&ParaId::from(0u32)), None);
			assert_eq!(Paras::get(&ParaId::from(0u32)), None);
		});
	}