parachains.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/>.

//! Main parachains logic. For now this is just the determination of which validators do what.

use sp_std::prelude::*;
use sp_std::result;
use codec::{Decode, Encode};
use sp_runtime::{
	KeyTypeId, Perbill, RuntimeDebug,
	traits::{
		Hash as HashT, BlakeTwo256, Saturating, One, Zero, Dispatchable,
		AccountIdConversion, BadOrigin, Convert, SignedExtension, AppVerify,
		DispatchInfoOf,
	},
	transaction_validity::{TransactionValidityError, ValidTransaction, TransactionValidity},
};
use sp_staking::{
	SessionIndex,
	offence::{ReportOffence, Offence, Kind},
};
use frame_support::{
	traits::KeyOwnerProofSystem,
	dispatch::IsSubType,
	weights::{DispatchClass, Weight},
};
use primitives::v0::{
	Balance, BlockNumber,
	Id as ParaId, Chain, DutyRoster, AttestedCandidate, CompactStatement as Statement, ParachainDispatchOrigin,
	UpwardMessage, ValidatorId, ActiveParas, CollatorId, Retriable, OmittedValidationData,
	CandidateReceipt, GlobalValidationSchedule, AbridgedCandidateReceipt,
	LocalValidationData, Scheduling, ValidityAttestation, NEW_HEADS_IDENTIFIER, PARACHAIN_KEY_TYPE_ID,
	ValidatorSignature, SigningContext, HeadData, ValidationCode,
	Remark, DownwardMessage
};
use frame_support::{
	Parameter, dispatch::DispatchResult, decl_storage, decl_module, decl_error, ensure,
	traits::{Currency, Get, WithdrawReason, ExistenceRequirement, Randomness},
};
use sp_runtime::transaction_validity::InvalidTransaction;

use inherents::{ProvideInherent, InherentData, MakeFatalError, InherentIdentifier};

use system::{
	ensure_none, ensure_signed,
	offchain::{CreateSignedTransaction, SendSignedTransaction, Signer},
};
use crate::attestations::{self, IncludedBlocks};
use crate::registrar::Registrar;

// ranges for iteration of general block number don't work, so this
// is a utility to get around that.
struct BlockNumberRange<N> {
	low: N,
	high: N,
}

impl<N: Saturating + One + PartialOrd + PartialEq + Clone> Iterator for BlockNumberRange<N> {
	type Item = N;

	fn next(&mut self) -> Option<N> {
		if self.low >= self.high {
			return None
		}

		let item = self.low.clone();
		self.low = self.low.clone().saturating_add(One::one());
		Some(item)
	}
}

// wrapper trait because an associated type of `Currency<Self::AccountId,Balance=Balance>`
// doesn't work.`
pub trait ParachainCurrency<AccountId> {
	fn free_balance(para_id: ParaId) -> Balance;
	fn deduct(para_id: ParaId, amount: Balance) -> DispatchResult;
	fn transfer_in(
		source: &AccountId,
		dest: ParaId,
		amount: Balance,
		existence_requirement: ExistenceRequirement,
	) -> DispatchResult;
	fn transfer_out(
		source: ParaId,
		dest: &AccountId,
		amount: Balance,
		existence_requirement: ExistenceRequirement,
	) -> DispatchResult;
}

impl<AccountId, T: Currency<AccountId>> ParachainCurrency<AccountId> for T where
	T::Balance: From<Balance> + Into<Balance>,
	ParaId: AccountIdConversion<AccountId>,
{
	fn free_balance(para_id: ParaId) -> Balance {
		let para_account = para_id.into_account();
		T::free_balance(&para_account).into()
	}

	// TODO: this should really be the same API as `withdraw`, having NegativeImbalance as an
	//   associated type.
	fn deduct(para_id: ParaId, amount: Balance) -> DispatchResult {
		let para_account = para_id.into_account();

		// burn the fee.
		let _ = T::withdraw(
			&para_account,
			amount.into(),
			WithdrawReason::Fee.into(),
			ExistenceRequirement::KeepAlive,
		)?;

		Ok(())
	}

	fn transfer_in(
		source: &AccountId,
		dest: ParaId,
		amount: Balance,
		existence_requirement: ExistenceRequirement,
	) -> DispatchResult {
		T::transfer(source, &dest.into_account(), amount.into(), existence_requirement)
	}

	fn transfer_out(
		source: ParaId,
		dest: &AccountId,
		amount: Balance,
		existence_requirement: ExistenceRequirement,
	) -> DispatchResult {
		T::transfer(&source.into_account(), dest, amount.into(), existence_requirement)
	}
}

/// Interface to the persistent (stash) identities of the current validators.
pub struct ValidatorIdentities<T>(sp_std::marker::PhantomData<T>);

/// A structure used to report conflicting votes by validators.
///
/// It is generic over two parameters:
/// `Proof` - proof of historical ownership of a key by some validator.
/// `Hash` - a type of a hash used in the runtime.
#[derive(RuntimeDebug, Encode, Decode)]
#[derive(Clone, Eq, PartialEq)]
pub struct DoubleVoteReport<Proof> {
	/// Identity of the double-voter.
	pub identity: ValidatorId,
	/// First vote of the double-vote.
	pub first: (Statement, ValidatorSignature),
	/// Second vote of the double-vote.
	pub second: (Statement, ValidatorSignature),
	/// Proof that the validator with `identity` id was actually a validator at `parent_hash`.
	pub proof: Proof,
	/// A `SigningContext` with a session and a parent hash of the moment this offence was commited.
	pub signing_context: SigningContext,
}

impl<Proof: Parameter + GetSessionNumber> DoubleVoteReport<Proof> {
	fn verify<T: Trait<Proof = Proof>>(
		&self,
	) -> Result<(), DoubleVoteValidityError> {
		let first = self.first.clone();
		let second = self.second.clone();
		let id = self.identity.clone();

		T::KeyOwnerProofSystem::check_proof((PARACHAIN_KEY_TYPE_ID, id), self.proof.clone())
			.ok_or(DoubleVoteValidityError::InvalidProof)?;

		if self.proof.session() != self.signing_context.session_index {
			return Err(DoubleVoteValidityError::InvalidReport);
		}

		// Check signatures.
		Self::verify_vote(
			&first,
			&self.signing_context,
			&self.identity,
		)?;
		Self::verify_vote(
			&second,
			&self.signing_context,
			&self.identity,
		)?;

		match (&first.0, &second.0) {
			// If issuing a `Candidate` message on a parachain block, neither a `Valid` or
			// `Invalid` vote cannot be issued on that parachain block, as the `Candidate`
			// message is an implicit validity vote.
			(Statement::Candidate(candidate_hash), Statement::Valid(hash)) |
			(Statement::Candidate(candidate_hash), Statement::Invalid(hash)) |
			(Statement::Valid(hash), Statement::Candidate(candidate_hash)) |
			(Statement::Invalid(hash), Statement::Candidate(candidate_hash))
			if *candidate_hash == *hash => {},
			// Otherwise, it is illegal to cast both a `Valid` and
			// `Invalid` vote on a given parachain block.
			(Statement::Valid(hash_1), Statement::Invalid(hash_2)) |
			(Statement::Invalid(hash_1), Statement::Valid(hash_2))
			if *hash_1 == *hash_2 => {},
			_ => {
				return Err(DoubleVoteValidityError::NotDoubleVote);
			}
		}

		Ok(())
	}

	fn verify_vote(
		vote: &(Statement, ValidatorSignature),
		signing_context: &SigningContext,
		authority: &ValidatorId,
	) -> Result<(), DoubleVoteValidityError> {
		let payload = localized_payload(vote.0.clone(), signing_context);

		if !vote.1.verify(&payload[..], authority) {
			return Err(DoubleVoteValidityError::InvalidSignature);
		}

		Ok(())
	}
}

impl<T: session::Trait> Get<Vec<T::ValidatorId>> for ValidatorIdentities<T> {
	fn get() -> Vec<T::ValidatorId> {
		<session::Module<T>>::validators()
	}
}

/// A trait to get a session number the `MembershipProof` belongs to.
pub trait GetSessionNumber {
	fn session(&self) -> SessionIndex;
}

impl GetSessionNumber for sp_session::MembershipProof {
	fn session(&self) -> SessionIndex {
		self.session
	}
}

pub trait Trait: CreateSignedTransaction<Call<Self>> + attestations::Trait + session::historical::Trait {
	// The transaction signing authority
	type AuthorityId: system::offchain::AppCrypto<Self::Public, Self::Signature>;

	/// The outer origin type.
	type Origin: From<Origin>
		+ From<<Self as system::Trait>::Origin>
		+ Into<result::Result<Origin, <Self as Trait>::Origin>>;

	/// The outer call dispatch type.
	type Call: Parameter + Dispatchable<Origin=<Self as Trait>::Origin> + From<Call<Self>>;

	/// Some way of interacting with balances for fees and transfers.
	type ParachainCurrency: ParachainCurrency<Self::AccountId>;

	/// Polkadot in practice will always use the `BlockNumber` type.
	/// Substrate isn't good at giving us ways to bound the supertrait
	/// associated type, so we introduce this conversion.
	type BlockNumberConversion: Convert<Self::BlockNumber, BlockNumber>;

	/// Something that provides randomness in the runtime.
	type Randomness: Randomness<Self::Hash>;

	/// Means to determine what the current set of active parachains are.
	type ActiveParachains: ActiveParas;

	/// The way that we are able to register parachains.
	type Registrar: Registrar<Self::AccountId>;

	/// Maximum code size for parachains, in bytes. Note that this is not
	/// the entire storage burden of the parachain, as old code is stored for
	/// `SlashPeriod` blocks.
	type MaxCodeSize: Get<u32>;

	/// Max head data size.
	type MaxHeadDataSize: Get<u32>;
	/// The frequency at which paras can upgrade their validation function.
	/// This is an integer number of relay-chain blocks that must pass between
	/// code upgrades.
	type ValidationUpgradeFrequency: Get<Self::BlockNumber>;

	/// The delay before a validation function upgrade is applied.
	type ValidationUpgradeDelay: Get<Self::BlockNumber>;

	/// The period (in blocks) that slash reports are permitted against an
	/// included candidate.
	///
	/// After validation function upgrades, the old code is persisted on-chain
	/// for this period, to ensure that candidates validated under old functions
	/// can be re-checked.
	type SlashPeriod: Get<Self::BlockNumber>;

	/// Proof type.
	///
	/// We need this type to bind the `KeyOwnerProofSystem::Proof` to necessary bounds.
	/// As soon as https://rust-lang.github.io/rfcs/2289-associated-type-bounds.html
	/// gets in this can be simplified.
	type Proof: Parameter + GetSessionNumber;

	/// Compute and check proofs of historical key owners.
	type KeyOwnerProofSystem: KeyOwnerProofSystem<
		(KeyTypeId, ValidatorId),
		Proof = Self::Proof,
		IdentificationTuple = Self::IdentificationTuple,
	>;

	/// An identification tuple type bound to `Parameter`.
	type IdentificationTuple: Parameter;

	/// Report an offence.
	type ReportOffence: ReportOffence<
		Self::AccountId,
		Self::IdentificationTuple,
		DoubleVoteOffence<Self::IdentificationTuple>,
	>;

	/// A type that converts the opaque hash type to exact one.
	type BlockHashConversion: Convert<Self::Hash, primitives::v0::Hash>;
}

/// Origin for the parachains module.
#[derive(PartialEq, Eq, Clone, Encode, Decode)]
#[cfg_attr(feature = "std", derive(Debug))]
pub enum Origin {
	/// It comes from a parachain.
	Parachain(ParaId),
}

/// An offence that is filed if the validator has submitted a double vote.
#[derive(RuntimeDebug)]
#[cfg_attr(feature = "std", derive(Clone, PartialEq, Eq))]
pub struct DoubleVoteOffence<Offender> {
	/// The current session index in which we report a validator.
	session_index: SessionIndex,
	/// The size of the validator set in current session/era.
	validator_set_count: u32,
	/// An offender that has submitted two conflicting votes.
	offender: Offender,
}

impl<Offender: Clone> Offence<Offender> for DoubleVoteOffence<Offender> {
	const ID: Kind = *b"para:double-vote";
	type TimeSlot = SessionIndex;

	fn offenders(&self) -> Vec<Offender> {
		vec![self.offender.clone()]
	}

	fn session_index(&self) -> SessionIndex {
		self.session_index
	}

	fn validator_set_count(&self) -> u32 {
		self.validator_set_count
	}

	fn time_slot(&self) -> Self::TimeSlot {
		self.session_index
	}

	fn slash_fraction(_offenders_count: u32, _validator_set_count: u32) -> Perbill {
		// Slash 100%.
		Perbill::from_percent(100)
	}
}

/// Total number of individual messages allowed in the relay-chain -> parachain message queue.
const MAX_DOWNWARD_QUEUE_COUNT: usize = 10;
/// Total number of individual messages allowed in the parachain -> relay-chain message queue.
const MAX_QUEUE_COUNT: usize = 100;
/// Total size of messages allowed in the parachain -> relay-chain message queue before which no
/// further messages may be added to it. If it exceeds this then the queue may contain only a
/// single message.
const WATERMARK_QUEUE_SIZE: usize = 20000;

/// Metadata used to track previous parachain validation code that we keep in
/// the state.
#[derive(Default, Encode, Decode)]
#[cfg_attr(test, derive(Debug, Clone, PartialEq))]
pub struct ParaPastCodeMeta<N> {
	// Block numbers where the code was replaced. These can be used as indices
	// into the `PastCode` map along with the `ParaId` to fetch the code itself.
	upgrade_times: Vec<N>,
	// This tracks the highest pruned code-replacement, if any.
	last_pruned: Option<N>,
}

#[cfg_attr(test, derive(Debug, PartialEq))]
enum UseCodeAt<N> {
	// Use the current code.
	Current,
	// Use the code that was replaced at the given block number.
	ReplacedAt(N),
}

impl<N: Ord + Copy> ParaPastCodeMeta<N> {
	// note a replacement has occurred at a given block number.
	fn note_replacement(&mut self, at: N) {
		self.upgrade_times.insert(0, at)
	}

	// Yields the block number of the code that should be used for validating at
	// the given block number.
	//
	// a return value of `None` means that there is no code we are aware of that
	// should be used to validate at the given height.
	fn code_at(&self, at: N) -> Option<UseCodeAt<N>> {
		// The `PastCode` map stores the code which was replaced at `t`.
		let end_position = self.upgrade_times.iter().position(|&t| t < at);
		if let Some(end_position) = end_position {
			Some(if end_position != 0 {
				// `end_position` gives us the replacement time where the code used at `at`
				// was set. But that code has been replaced: `end_position - 1` yields
				// that index.
				UseCodeAt::ReplacedAt(self.upgrade_times[end_position - 1])
			} else {
				// the most recent tracked replacement is before `at`.
				// this means that the code put in place then (i.e. the current code)
				// is correct for validating at `at`.
				UseCodeAt::Current
			})
		} else {
			if self.last_pruned.as_ref().map_or(true, |&n| n < at) {
				// Our `last_pruned` is before `at`, so we still have the code!
				// but no code upgrade entries found before the `at` parameter.
				//
				// this means one of two things is true:
				// 1. there are no non-pruned upgrade logs. in this case use `Current`
				// 2. there are non-pruned upgrade logs all after `at`.
				//    in this case use the oldest upgrade log.
				Some(self.upgrade_times.last()
					.map(|n| UseCodeAt::ReplacedAt(*n))
					.unwrap_or(UseCodeAt::Current)
				)
			} else {
				// We don't have the code anymore.
				None
			}
		}
	}

	// The block at which the most recently tracked code change occurred.
	fn most_recent_change(&self) -> Option<N> {
		self.upgrade_times.first().map(|x| x.clone())
	}

	// prunes all code upgrade logs occurring at or before `max`.
	// note that code replaced at `x` is the code used to validate all blocks before
	// `x`. Thus, `max` should be outside of the slashing window when this is invoked.
	//
	// returns an iterator of block numbers at which code was replaced, where the replaced
	// code should be now pruned, in ascending order.
	fn prune_up_to(&'_ mut self, max: N) -> impl Iterator<Item=N> + '_ {
		match self.upgrade_times.iter().position(|&t| t <= max) {
			None => {
				// this is a no-op `drain` - desired because all
				// logged code upgrades occurred after `max`.
				self.upgrade_times.drain(self.upgrade_times.len()..).rev()
			}
			Some(pos) => {
				self.last_pruned = Some(self.upgrade_times[pos]);
				self.upgrade_times.drain(pos..).rev()
			}
		}
	}
}

decl_storage! {
	trait Store for Module<T: Trait> as Parachains {
		/// All authorities' keys at the moment.
		pub Authorities get(fn authorities): Vec<ValidatorId>;
		/// The active code of a currently-registered parachain.
		pub Code get(fn parachain_code): map hasher(twox_64_concat) ParaId => Option<ValidationCode>;
		/// Past code of parachains. The parachains themselves may not be registered anymore,
		/// but we also keep their code on-chain for the same amount of time as outdated code
		/// to assist with availability.
		PastCodeMeta get(fn past_code_meta): map hasher(twox_64_concat) ParaId => ParaPastCodeMeta<T::BlockNumber>;
		/// Actual past code, indicated by the parachain and the block number at which it
		/// became outdated.
		PastCode: map hasher(twox_64_concat) (ParaId, T::BlockNumber) => Option<ValidationCode>;
		/// Past code pruning, in order of priority.
		PastCodePruning get(fn past_code_pruning_tasks): Vec<(ParaId, T::BlockNumber)>;
		// The block number at which the planned code change is expected for a para.
		// The change will be applied after the first parablock for this ID included which executes
		// in the context of a relay chain block with a number >= `expected_at`.
		FutureCodeUpgrades get(fn code_upgrade_schedule): map hasher(twox_64_concat) ParaId => Option<T::BlockNumber>;
		// The actual future code of a para.
		FutureCode: map hasher(twox_64_concat) ParaId => ValidationCode;

		/// The heads of the parachains registered at present.
		pub Heads get(fn parachain_head): map hasher(twox_64_concat) ParaId => Option<HeadData>;
		/// Messages ready to be dispatched onto the relay chain. It is subject to
		/// `MAX_MESSAGE_COUNT` and `WATERMARK_MESSAGE_SIZE`.
		pub RelayDispatchQueue: map hasher(twox_64_concat) ParaId => Vec<UpwardMessage>;
		/// Size of the dispatch queues. Separated from actual data in order to avoid costly
		/// decoding when checking receipt validity. First item in tuple is the count of messages
		/// second if the total length (in bytes) of the message payloads.
		pub RelayDispatchQueueSize: map hasher(twox_64_concat) ParaId => (u32, u32);
		/// The ordered list of ParaIds that have a `RelayDispatchQueue` entry.
		NeedsDispatch: Vec<ParaId>;

		/// `Some` if the parachain heads get updated in this block, along with the parachain IDs
		/// that did update. Ordered in the same way as `registrar::Active` (i.e. by ParaId).
		///
		/// `None` if not yet updated.
		pub DidUpdate: Option<Vec<ParaId>>;

		/// Messages waiting to be delivered from the Relay chain into the parachain.
		pub DownwardMessageQueue: map hasher(twox_64_concat) ParaId => Vec<DownwardMessage<T::AccountId>>;
	}
	add_extra_genesis {
		config(authorities): Vec<ValidatorId>;
		build(|config| Module::<T>::initialize_authorities(&config.authorities))
	}
}

decl_error! {
	pub enum Error for Module<T: Trait> {
		/// Parachain heads must be updated only once in the block.
		TooManyHeadUpdates,
		/// Too many parachain candidates.
		TooManyParaCandidates,
		/// Proposed heads must be ascending order by parachain ID without duplicate.
		HeadsOutOfOrder,
		/// Candidate is for an unregistered parachain.
		UnregisteredPara,
		/// Invalid collator.
		InvalidCollator,
		/// The message queue is full. Messages will be added when there is space.
		QueueFull,
		/// The message origin is invalid.
		InvalidMessageOrigin,
		/// No validator group for parachain.
		NoValidatorGroup,
		/// Not enough validity votes for candidate.
		NotEnoughValidityVotes,
		/// The number of attestations exceeds the number of authorities.
		VotesExceedsAuthorities,
		/// Attesting validator not on this chain's validation duty.
		WrongValidatorAttesting,
		/// Invalid signature from attester.
		InvalidSignature,
		/// Extra untagged validity votes along with candidate.
		UntaggedVotes,
		/// Wrong parent head for parachain receipt.
		ParentMismatch,
		/// Head data was too large.
		HeadDataTooLarge,
		/// New validation code was too large.
		ValidationCodeTooLarge,
		/// Disallowed code upgrade.
		DisallowedCodeUpgrade,
		/// Para does not have enough balance to pay fees.
		CannotPayFees,
		/// Unexpected relay-parent for a candidate receipt.
		UnexpectedRelayParent,
		/// Downward message queue is full for the Parachain.
		DownwardMessageQueueFull,
	}
}

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

		fn on_initialize(now: T::BlockNumber) -> Weight {
			<Self as Store>::DidUpdate::kill();

			Self::do_old_code_pruning(now);

			// TODO https://github.com/paritytech/polkadot/issues/977: set correctly
			0
		}

		fn on_finalize() {
			assert!(<Self as Store>::DidUpdate::exists(), "Parachain heads must be updated once in the block");
		}

		/// Provide candidate receipts for parachains, in ascending order by id.
		#[weight = (1_000_000_000, DispatchClass::Mandatory)]
		pub fn set_heads(origin, heads: Vec<AttestedCandidate>) -> DispatchResult {
			ensure_none(origin)?;
			ensure!(!<DidUpdate>::exists(), Error::<T>::TooManyHeadUpdates);

			let active_parachains = Self::active_parachains();

			let parachain_count = active_parachains.len();
			ensure!(heads.len() <= parachain_count, Error::<T>::TooManyParaCandidates);

			let mut proceeded = Vec::with_capacity(heads.len());

			let schedule = Self::global_validation_schedule();

			if !active_parachains.is_empty() {
				// perform integrity checks before writing to storage.
				{
					let mut last_id = None;

					let mut iter = active_parachains.iter();
					for head in &heads {
						let id = head.parachain_index();
						// proposed heads must be ascending order by parachain ID without duplicate.
						ensure!(
							last_id.as_ref().map_or(true, |x| x < &id),
							Error::<T>::HeadsOutOfOrder
						);

						// must be unknown since active parachains are always sorted.
						let (_, maybe_required_collator) = iter.find(|para| para.0 == id)
							.ok_or(Error::<T>::UnregisteredPara)?;

						if let Some((required_collator, _)) = maybe_required_collator {
							ensure!(required_collator == &head.candidate.collator, Error::<T>::InvalidCollator);
						}

						Self::check_upward_messages(
							id,
							&head.candidate.commitments.upward_messages,
							MAX_QUEUE_COUNT,
							WATERMARK_QUEUE_SIZE,
						)?;

						Self::remove_processed_downward_messages(
							id,
							head.candidate.commitments.processed_downward_messages as usize,
						);

						let id = head.parachain_index();
						proceeded.push(id);
						last_id = Some(id);
					}
				}

				let para_blocks = Self::check_candidates(
					&schedule,
					&heads,
					&active_parachains,
				)?;

				<attestations::Module<T>>::note_included(&heads, para_blocks);

				Self::update_routing(
					&heads,
				);

				// note: we dispatch new messages _after_ the call to `check_candidates`
				// which deducts any fees. if that were not the case, an upward message
				// could be dispatched and spend money that invalidated a candidate.
				Self::dispatch_upward_messages(
					MAX_QUEUE_COUNT,
					WATERMARK_QUEUE_SIZE,
					Self::dispatch_message,
				);
			}

			DidUpdate::put(proceeded);

			Ok(())
		}

		/// Provide a proof that some validator has commited a double-vote.
		///
		/// The weight is 0; in order to avoid DoS a `SignedExtension` validation
		/// is implemented.
		#[weight = 0]
		pub fn report_double_vote(
			origin,
			report: DoubleVoteReport<
				<T::KeyOwnerProofSystem as KeyOwnerProofSystem<(KeyTypeId, ValidatorId)>>::Proof,
			>,
		) -> DispatchResult {
			let reporter = ensure_signed(origin)?;

			let validators = <session::Module<T>>::validators();
			let validator_set_count = validators.len() as u32;

			let session_index = report.proof.session();
			let DoubleVoteReport { identity, proof, .. } = report;

			// We have already checked this proof in `SignedExtension`, but we need
			// this here to get the full identification of the offender.
			let offender = T::KeyOwnerProofSystem::check_proof(
					(PARACHAIN_KEY_TYPE_ID, identity),
					proof,
				).ok_or("Invalid/outdated key ownership proof.")?;

			let offence = DoubleVoteOffence {
				session_index,
				validator_set_count,
				offender,
			};

			// Checks if this is actually a double vote are
			// implemented in `ValidateDoubleVoteReports::validete`.
			T::ReportOffence::report_offence(vec![reporter], offence)
				.map_err(|_| "Failed to report offence")?;

			Ok(())
		}

		/// Transfer some tokens into a parachain and leave a message in the downward queue for it.
		#[weight = 100_000]
		pub fn transfer_to_parachain(
			origin,
			to: ParaId,
			amount: Balance,
			remark: Remark,
		) {
			let who = ensure_signed(origin)?;
			let downward_queue_count = DownwardMessageQueue::<T>::decode_len(to).unwrap_or(0);
			ensure!(downward_queue_count < MAX_DOWNWARD_QUEUE_COUNT, Error::<T>::DownwardMessageQueueFull);
			T::ParachainCurrency::transfer_in(&who, to, amount, ExistenceRequirement::AllowDeath)?;
			DownwardMessageQueue::<T>::append(to, DownwardMessage::TransferInto(who, amount, remark));
		}

		/// Send a XCMP message to the given parachain.
		///
		/// The origin must be another parachain.
		#[weight = 100_000]
		pub fn send_xcmp_message(
			origin,
			to: ParaId,
			msg: Vec<u8>,
		) {
			ensure_parachain(<T as Trait>::Origin::from(origin))?;
			let downward_queue_count = DownwardMessageQueue::<T>::decode_len(to).unwrap_or(0);
			ensure!(downward_queue_count < MAX_DOWNWARD_QUEUE_COUNT, Error::<T>::DownwardMessageQueueFull);
			DownwardMessageQueue::<T>::append(to, DownwardMessage::XCMPMessage(msg));
		}
	}
}

fn majority_of(list_len: usize) -> usize {
	list_len / 2 + list_len % 2
}

fn localized_payload(
	statement: Statement,
	signing_context: &SigningContext,
) -> Vec<u8> {
	let mut encoded = statement.encode();
	signing_context.using_encoded(|s| encoded.extend(s));
	encoded
}

/// Iterator that returns groups of validators that are assigned to the same chain.
///
/// Assumes that the inner validators are sorted by chain id.
struct GroupedDutyIter<'a> {
	next_idx: usize,
	inner: &'a [(usize, ParaId)],
}

impl<'a> GroupedDutyIter<'a> {
	fn new(inner: &'a [(usize, ParaId)]) -> Self {
		GroupedDutyIter { next_idx: 0, inner }
	}

	fn group_for(&mut self, wanted_id: ParaId) -> Option<&'a [(usize, ParaId)]> {
		while let Some((id, keys)) = self.next() {
			if wanted_id == id {
				return Some(keys)
			}
		}

		None
	}
}

impl<'a> Iterator for GroupedDutyIter<'a> {
	type Item = (ParaId, &'a [(usize, ParaId)]);

	fn next(&mut self) -> Option<Self::Item> {
		if self.next_idx == self.inner.len() { return None }
		let start_idx = self.next_idx;
		self.next_idx += 1;
		let start_id = self.inner[start_idx].1;

		while self.inner.get(self.next_idx).map_or(false, |&(_, ref id)| id == &start_id) {
			self.next_idx += 1;
		}

		Some((start_id, &self.inner[start_idx..self.next_idx]))
	}
}

/// Convert a duty roster, which is originally a Vec<Chain>, where each
/// item corresponds to the same position in the session keys, into
/// a list containing (index, parachain duty) where indices are into the session keys.
/// This list is sorted ascending by parachain duty, just like the
/// parachain candidates are.
fn make_sorted_duties(duty: &[Chain]) -> Vec<(usize, ParaId)> {
	let mut sorted_duties = Vec::with_capacity(duty.len());
	for (val_idx, duty) in duty.iter().enumerate() {
		let id = match duty {
			Chain::Relay => continue,
			Chain::Parachain(id) => id,
		};

		let idx = sorted_duties.binary_search_by_key(&id, |&(_, ref id)| id)
			.unwrap_or_else(|idx| idx);

		sorted_duties.insert(idx, (val_idx, *id));
	}

	sorted_duties
}

impl<T: Trait> Module<T> {
	/// Initialize the state of a new parachain/parathread.
	pub fn initialize_para(
		id: ParaId,
		code: ValidationCode,
		initial_head_data: HeadData,
	) {
		<Code>::insert(id, code);
		<Heads>::insert(id, initial_head_data);
	}

	/// Cleanup all storage related to a para. Some pieces of data may remain
	/// available in the on-chain state.
	pub fn cleanup_para(
		id: ParaId,
	) {
		let code = <Code>::take(id);
		<Heads>::remove(id);

		// clean up from all code-upgrade maps.
		// we don't clean up the meta or planned-code maps as that's handled
		// by the pruning process.
		if let Some(_planned_future_at) = <Self as Store>::FutureCodeUpgrades::take(&id) {
			<Self as Store>::FutureCode::remove(&id);
		}

		if let Some(code) = code {
			Self::note_past_code(id, <system::Module<T>>::block_number(), code);
		}
	}

	// note replacement of the code of para with given `id`, which occured in the
	// context of the given relay-chain block number. provide the replaced code.
	//
	// `at` for para-triggered replacement is the block number of the relay-chain
	// block in whose context the parablock was executed
	// (i.e. number of `relay_parent` in the receipt)
	fn note_past_code(id: ParaId, at: T::BlockNumber, old_code: ValidationCode) {
		<Self as Store>::PastCodeMeta::mutate(&id, |past_meta| {
			past_meta.note_replacement(at);
		});

		<Self as Store>::PastCode::insert(&(id, at), old_code);

		// Schedule pruning for this past-code to be removed as soon as it
		// exits the slashing window.
		<Self as Store>::PastCodePruning::mutate(|pruning| {
			let insert_idx = pruning.binary_search_by_key(&at, |&(_, b)| b)
				.unwrap_or_else(|idx| idx);
			pruning.insert(insert_idx, (id, at));
		})
	}

	// does old code pruning.
	fn do_old_code_pruning(now: T::BlockNumber) {
		let slash_period = T::SlashPeriod::get();
		if now <= slash_period { return }

		// The height of any changes we no longer should keep around.
		let pruning_height = now - (slash_period + One::one());

		<Self as Store>::PastCodePruning::mutate(|pruning_tasks: &mut Vec<(_, T::BlockNumber)>| {
			let pruning_tasks_to_do = {
				// find all past code that has just exited the pruning window.
				let up_to_idx = pruning_tasks.iter()
					.take_while(|&(_, at)| at <= &pruning_height)
					.count();
				pruning_tasks.drain(..up_to_idx)
			};

			for (para_id, _) in pruning_tasks_to_do {
				let full_deactivate = <Self as Store>::PastCodeMeta::mutate(&para_id, |meta| {
					for pruned_repl_at in meta.prune_up_to(pruning_height) {
						<Self as Store>::PastCode::remove(&(para_id, pruned_repl_at));
					}

					meta.most_recent_change().is_none() && Self::parachain_head(&para_id).is_none()
				});

				// This parachain has been removed and now the vestigial code
				// has been removed from the state. clean up meta as well.
				if full_deactivate {
					<Self as Store>::PastCodeMeta::remove(&para_id);
				}
			}
		});
	}

	// Performs a code upgrade of a parachain.
	fn do_code_upgrade(id: ParaId, at: T::BlockNumber, new_code: &ValidationCode) {
		let old_code = Self::parachain_code(&id).unwrap_or_default();
		Code::insert(&id, new_code);

		Self::note_past_code(id, at, old_code);
	}

	/// Get a `SigningContext` with a current `SessionIndex` and parent hash.
	pub fn signing_context() -> SigningContext {
		let session_index = <session::Module<T>>::current_index();
		let parent_hash = <system::Module<T>>::parent_hash();

		SigningContext {
			session_index,
			parent_hash: T::BlockHashConversion::convert(parent_hash),
		}
	}

	/// Submit a double vote report.
	pub fn submit_double_vote_report(
		report: DoubleVoteReport<T::Proof>,
	) -> Option<()> {
		Signer::<T, T::AuthorityId>::all_accounts()
			.send_signed_transaction(
				move |_account| {
					Call::report_double_vote(report.clone())
				}
			)
			.iter()
			.find_map(|(_, res)| res.ok().map(|_| ()))
	}

	/// Dispatch some messages from a parachain.
	fn dispatch_message(
		id: ParaId,
		origin: ParachainDispatchOrigin,
		data: &[u8],
	) {
		if let Ok(message_call) = <T as Trait>::Call::decode(&mut &data[..]) {
			let origin: <T as Trait>::Origin = match origin {
				ParachainDispatchOrigin::Signed =>
					<T as Trait>::Origin::from(<T as system::Trait>::Origin::from(system::RawOrigin::Signed(id.into_account()))),
				ParachainDispatchOrigin::Parachain =>
					Origin::Parachain(id).into(),
				ParachainDispatchOrigin::Root =>
					<T as Trait>::Origin::from(<T as system::Trait>::Origin::from(system::RawOrigin::Root)),
			};
			let _ok = message_call.dispatch(origin).is_ok();
			// Not much to do with the result as it is. It's up to the parachain to ensure that the
			// message makes sense.
		}
	}

	/// Ensure all is well with the upward messages.
	fn check_upward_messages(
		id: ParaId,
		upward_messages: &[UpwardMessage],
		max_queue_count: usize,
		watermark_queue_size: usize,
	) -> DispatchResult {
		// Either there are no more messages to add...
		if !upward_messages.is_empty() {
			let (count, size) = <RelayDispatchQueueSize>::get(id);
			ensure!(
				// ...or we are appending one message onto an empty queue...
				upward_messages.len() + count as usize == 1
				// ...or...
				|| (
				// ...the total messages in the queue ends up being no greater than the
				// limit...
					upward_messages.len() + count as usize <= max_queue_count
				&&
					// ...and the total size of the payloads in the queue ends up being no
					// greater than the limit.
					upward_messages.iter()
						.fold(size as usize, |a, x| a + x.data.len())
					<= watermark_queue_size
				),
				Error::<T>::QueueFull
			);
			if !id.is_system() {
				for m in upward_messages.iter() {
					ensure!(m.origin != ParachainDispatchOrigin::Root, Error::<T>::InvalidMessageOrigin);
				}
			}
		}
		Ok(())
	}

	/// Remove processed downward messages from the `DownwardMessageQueue`.
	fn remove_processed_downward_messages(id: ParaId, processed: usize) {