mod.rs

// Copyright (C) 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/>.

//! The paras pallet acts as the main registry of paras.
//!
//! # Tracking State of Paras
//!
//! The most important responsibility of this module is to track which parachains
//! are active and what their current state is. The current state of a para consists of the current
//! head data and the current validation code (AKA Parachain Validation Function (PVF)).
//!
//! A para is not considered live until it is registered and activated in this pallet.
//!
//! The set of parachains cannot change except at session boundaries. This is primarily to ensure
//! that the number and meaning of bits required for the availability bitfields does not change
//! except at session boundaries.
//!
//! # Validation Code Upgrades
//!
//! When a para signals the validation code upgrade it will be processed by this module. This can
//! be in turn split into more fine grained items:
//!
//! - Part of the acceptance criteria checks if the para can indeed signal an upgrade,
//!
//! - When the candidate is enacted, this module schedules code upgrade, storing the prospective
//!   validation code.
//!
//! - Actually assign the prospective validation code to be the current one after all conditions are
//!   fulfilled.
//!
//! The conditions that must be met before the para can use the new validation code are:
//!
//! 1. The validation code should have been "soaked" in the storage for a given number of blocks.
//! That    is, the validation code should have been stored in on-chain storage for some time, so
//! that in    case of a revert with a non-extreme height difference, that validation code can still
//! be    found on-chain.
//!
//! 2. The validation code was vetted by the validators and declared as non-malicious in a processes
//!    known as PVF pre-checking.
//!
//! # Validation Code Management
//!
//! Potentially, one validation code can be used by several different paras. For example, during
//! initial stages of deployment several paras can use the same "shell" validation code, or
//! there can be shards of the same para that use the same validation code.
//!
//! In case a validation code ceases to have any users it must be pruned from the on-chain storage.
//!
//! # Para Lifecycle Management
//!
//! A para can be in one of the two stable states: it is either a lease holding parachain or an
//! on-demand parachain.
//!
//! However, in order to get into one of those two states, it must first be onboarded. Onboarding
//! can be only enacted at session boundaries. Onboarding must take at least one full session.
//! Moreover, a brand new validation code should go through the PVF pre-checking process.
//!
//! Once the para is in one of the two stable states, it can switch to the other stable state or to
//! initiate offboarding process. The result of offboarding is removal of all data related to that
//! para.
//!
//! # PVF Pre-checking
//!
//! As was mentioned above, a brand new validation code should go through a process of approval. As
//! part of this process, validators from the active set will take the validation code and check if
//! it is malicious. Once they did that and have their judgement, either accept or reject, they
//! issue a statement in a form of an unsigned extrinsic. This extrinsic is processed by this
//! pallet. Once supermajority is gained for accept, then the process that initiated the check is
//! resumed (as mentioned before this can be either upgrading of validation code or onboarding). If
//! getting a supermajority becomes impossible (>1/3 of validators have already voted against), then
//! we reject.
//!
//! Below is a state diagram that depicts states of a single PVF pre-checking vote.
//!
//! ```text
//!                                            ┌──────────┐
//!                        supermajority       │          │
//!                    ┌────────for───────────▶│ accepted │
//!        vote────┐   │                       │          │
//!         │      │   │                       └──────────┘
//!         │      │   │
//!         │  ┌───────┐
//!         │  │       │
//!         └─▶│ init  │──── >1/3 against      ┌──────────┐
//!            │       │           │           │          │
//!            └───────┘           └──────────▶│ rejected │
//!             ▲  │                           │          │
//!             │  │ session                   └──────────┘
//!             │  └──change
//!             │     │
//!             │     ▼
//!             ┌─────┐
//! start──────▶│reset│
//!             └─────┘
//! ```

use crate::{
	configuration,
	inclusion::{QueueFootprinter, UmpQueueId},
	initializer::SessionChangeNotification,
	shared,
};
use bitvec::{order::Lsb0 as BitOrderLsb0, vec::BitVec};
use frame_support::{pallet_prelude::*, traits::EstimateNextSessionRotation, DefaultNoBound};
use frame_system::pallet_prelude::*;
use parity_scale_codec::{Decode, Encode};
use primitives::{
	ConsensusLog, HeadData, Id as ParaId, PvfCheckStatement, SessionIndex, UpgradeGoAhead,
	UpgradeRestriction, ValidationCode, ValidationCodeHash, ValidatorSignature, MIN_CODE_SIZE,
};
use scale_info::{Type, TypeInfo};
use sp_core::RuntimeDebug;
use sp_runtime::{
	traits::{AppVerify, One, Saturating},
	DispatchResult, SaturatedConversion,
};
use sp_std::{cmp, collections::btree_set::BTreeSet, mem, prelude::*};

use serde::{Deserialize, Serialize};

pub use crate::Origin as ParachainOrigin;

#[cfg(feature = "runtime-benchmarks")]
pub(crate) mod benchmarking;

#[cfg(test)]
pub(crate) mod tests;

pub use pallet::*;

const LOG_TARGET: &str = "runtime::paras";

// the two key times necessary to track for every code replacement.
#[derive(Default, Encode, Decode, TypeInfo)]
#[cfg_attr(test, derive(Debug, Clone, PartialEq))]
pub struct ReplacementTimes<N> {
	/// The relay-chain block number that the code upgrade was expected to be activated.
	/// This is when the code change occurs from the para's perspective - after the
	/// first parablock included with a relay-parent with number >= this value.
	expected_at: N,
	/// The relay-chain block number at which the parablock activating the code upgrade was
	/// actually included. This means considered included and available, so this is the time at
	/// which that parablock enters the acceptance period in this fork of the relay-chain.
	activated_at: N,
}

/// Metadata used to track previous parachain validation code that we keep in
/// the state.
#[derive(Default, Encode, Decode, TypeInfo)]
#[cfg_attr(test, derive(Debug, Clone, PartialEq))]
pub struct ParaPastCodeMeta<N> {
	/// Block numbers where the code was expected to be replaced and where the code
	/// was actually replaced, respectively. The first is used to do accurate look-ups
	/// of historic code in historic contexts, whereas the second is used to do
	/// pruning on an accurate timeframe. These can be used as indices
	/// into the `PastCodeHash` map along with the `ParaId` to fetch the code itself.
	upgrade_times: Vec<ReplacementTimes<N>>,
	/// Tracks the highest pruned code-replacement, if any. This is the `activated_at` value,
	/// not the `expected_at` value.
	last_pruned: Option<N>,
}

/// The possible states of a para, to take into account delayed lifecycle changes.
///
/// If the para is in a "transition state", it is expected that the parachain is
/// queued in the `ActionsQueue` to transition it into a stable state. Its lifecycle
/// state will be used to determine the state transition to apply to the para.
#[derive(PartialEq, Eq, Clone, Encode, Decode, RuntimeDebug, TypeInfo)]
pub enum ParaLifecycle {
	/// Para is new and is onboarding as an on-demand or lease holding Parachain.
	Onboarding,
	/// Para is a Parathread (on-demand parachain).
	Parathread,
	/// Para is a lease holding Parachain.
	Parachain,
	/// Para is a Parathread (on-demand parachain) which is upgrading to a lease holding Parachain.
	UpgradingParathread,
	/// Para is a lease holding Parachain which is downgrading to an on-demand parachain.
	DowngradingParachain,
	/// Parathread (on-demand parachain) is queued to be offboarded.
	OffboardingParathread,
	/// Parachain is queued to be offboarded.
	OffboardingParachain,
}

impl ParaLifecycle {
	/// Returns true if parachain is currently onboarding. To learn if the
	/// parachain is onboarding as a lease holding or on-demand parachain, look at the
	/// `UpcomingGenesis` storage item.
	pub fn is_onboarding(&self) -> bool {
		matches!(self, ParaLifecycle::Onboarding)
	}

	/// Returns true if para is in a stable state, i.e. it is currently
	/// a lease holding or on-demand parachain, and not in any transition state.
	pub fn is_stable(&self) -> bool {
		matches!(self, ParaLifecycle::Parathread | ParaLifecycle::Parachain)
	}

	/// Returns true if para is currently treated as a parachain.
	/// This also includes transitioning states, so you may want to combine
	/// this check with `is_stable` if you specifically want `Paralifecycle::Parachain`.
	pub fn is_parachain(&self) -> bool {
		matches!(
			self,
			ParaLifecycle::Parachain |
				ParaLifecycle::DowngradingParachain |
				ParaLifecycle::OffboardingParachain
		)
	}

	/// Returns true if para is currently treated as a parathread (on-demand parachain).
	/// This also includes transitioning states, so you may want to combine
	/// this check with `is_stable` if you specifically want `Paralifecycle::Parathread`.
	pub fn is_parathread(&self) -> bool {
		matches!(
			self,
			ParaLifecycle::Parathread |
				ParaLifecycle::UpgradingParathread |
				ParaLifecycle::OffboardingParathread
		)
	}

	/// Returns true if para is currently offboarding.
	pub fn is_offboarding(&self) -> bool {
		matches!(self, ParaLifecycle::OffboardingParathread | ParaLifecycle::OffboardingParachain)
	}

	/// Returns true if para is in any transitionary state.
	pub fn is_transitioning(&self) -> bool {
		!Self::is_stable(self)
	}
}

impl<N: Ord + Copy + PartialEq> ParaPastCodeMeta<N> {
	// note a replacement has occurred at a given block number.
	pub(crate) fn note_replacement(&mut self, expected_at: N, activated_at: N) {
		self.upgrade_times.push(ReplacementTimes { expected_at, activated_at })
	}

	/// Returns `true` if the upgrade logs list is empty.
	fn is_empty(&self) -> bool {
		self.upgrade_times.is_empty()
	}

	// The block at which the most recently tracked code change occurred, from the perspective
	// of the para.
	#[cfg(test)]
	fn most_recent_change(&self) -> Option<N> {
		self.upgrade_times.last().map(|x| x.expected_at)
	}

	// 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.
	//
	// Since we don't want to prune anything inside the acceptance period, and the parablock only
	// enters the acceptance period after being included, we prune based on the activation height of
	// the code change, not the expected height of the code change.
	//
	// 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> + '_ {
		let to_prune = self.upgrade_times.iter().take_while(|t| t.activated_at <= max).count();
		let drained = if to_prune == 0 {
			// no-op prune.
			self.upgrade_times.drain(self.upgrade_times.len()..)
		} else {
			// if we are actually pruning something, update the `last_pruned` member.
			self.last_pruned = Some(self.upgrade_times[to_prune - 1].activated_at);
			self.upgrade_times.drain(..to_prune)
		};

		drained.map(|times| times.expected_at)
	}
}

/// Arguments for initializing a para.
#[derive(PartialEq, Eq, Clone, Encode, Decode, RuntimeDebug, TypeInfo, Serialize, Deserialize)]
pub struct ParaGenesisArgs {
	/// The initial head data to use.
	pub genesis_head: HeadData,
	/// The initial validation code to use.
	pub validation_code: ValidationCode,
	/// Lease holding or on-demand parachain.
	#[serde(rename = "parachain")]
	pub para_kind: ParaKind,
}

/// Distinguishes between lease holding Parachain and Parathread (on-demand parachain)
#[derive(PartialEq, Eq, Clone, RuntimeDebug)]
pub enum ParaKind {
	Parathread,
	Parachain,
}

impl Serialize for ParaKind {
	fn serialize<S>(&self, serializer: S) -> Result<S::Ok, S::Error>
	where
		S: serde::Serializer,
	{
		match self {
			ParaKind::Parachain => serializer.serialize_bool(true),
			ParaKind::Parathread => serializer.serialize_bool(false),
		}
	}
}

impl<'de> Deserialize<'de> for ParaKind {
	fn deserialize<D>(deserializer: D) -> Result<Self, D::Error>
	where
		D: serde::Deserializer<'de>,
	{
		match serde::de::Deserialize::deserialize(deserializer) {
			Ok(true) => Ok(ParaKind::Parachain),
			Ok(false) => Ok(ParaKind::Parathread),
			_ => Err(serde::de::Error::custom("invalid ParaKind serde representation")),
		}
	}
}

// Manual encoding, decoding, and TypeInfo as the parakind field in ParaGenesisArgs used to be a
// bool
impl Encode for ParaKind {
	fn size_hint(&self) -> usize {
		true.size_hint()
	}

	fn using_encoded<R, F: FnOnce(&[u8]) -> R>(&self, f: F) -> R {
		match self {
			ParaKind::Parachain => true.using_encoded(f),
			ParaKind::Parathread => false.using_encoded(f),
		}
	}
}

impl Decode for ParaKind {
	fn decode<I: parity_scale_codec::Input>(
		input: &mut I,
	) -> Result<Self, parity_scale_codec::Error> {
		match bool::decode(input) {
			Ok(true) => Ok(ParaKind::Parachain),
			Ok(false) => Ok(ParaKind::Parathread),
			_ => Err("Invalid ParaKind representation".into()),
		}
	}
}

impl TypeInfo for ParaKind {
	type Identity = bool;
	fn type_info() -> Type {
		bool::type_info()
	}
}

/// This enum describes a reason why a particular PVF pre-checking vote was initiated. When the
/// PVF vote in question is concluded, this enum indicates what changes should be performed.
#[derive(Debug, Encode, Decode, TypeInfo)]
pub(crate) enum PvfCheckCause<BlockNumber> {
	/// PVF vote was initiated by the initial onboarding process of the given para.
	Onboarding(ParaId),
	/// PVF vote was initiated by signalling of an upgrade by the given para.
	Upgrade {
		/// The ID of the parachain that initiated or is waiting for the conclusion of
		/// pre-checking.
		id: ParaId,
		/// The relay-chain block number of **inclusion** of candidate that that initiated the
		/// upgrade.
		///
		/// It's important to count upgrade enactment delay from the inclusion of this candidate
		/// instead of its relay parent -- in order to keep PVF available in case of chain
		/// reversions.
		///
		/// See https://github.com/paritytech/polkadot/issues/4601 for detailed explanation.
		included_at: BlockNumber,
		/// Whether or not the upgrade should be enacted directly.
		///
		/// If set to `Yes` it means that no `GoAheadSignal` will be set and the parachain code
		/// will also be overwritten directly.
		upgrade_strategy: UpgradeStrategy,
	},
}

/// The strategy on how to handle a validation code upgrade.
///
/// When scheduling a parachain code upgrade the upgrade first is checked by all validators. The
/// validators ensure that the new validation code can be compiled and instantiated. After the
/// majority of the validators have reported their checking result the upgrade is either scheduled
/// or aborted. This strategy then comes into play around the relay chain block this upgrade was
/// scheduled in.
#[derive(Debug, Copy, Clone, PartialEq, TypeInfo, Decode, Encode)]
pub enum UpgradeStrategy {
	/// Set the `GoAhead` signal to inform the parachain that it is time to upgrade.
	///
	/// The upgrade will then be applied after the first parachain block was enacted that must have
	/// observed the `GoAhead` signal.
	SetGoAheadSignal,
	/// Apply the upgrade directly at the expected relay chain block.
	///
	/// This doesn't wait for the parachain to make any kind of progress.
	ApplyAtExpectedBlock,
}

impl<BlockNumber> PvfCheckCause<BlockNumber> {
	/// Returns the ID of the para that initiated or subscribed to the pre-checking vote.
	fn para_id(&self) -> ParaId {
		match *self {
			PvfCheckCause::Onboarding(id) => id,
			PvfCheckCause::Upgrade { id, .. } => id,
		}
	}
}

/// Specifies what was the outcome of a PVF pre-checking vote.
#[derive(Copy, Clone, Encode, Decode, RuntimeDebug, TypeInfo)]
enum PvfCheckOutcome {
	Accepted,
	Rejected,
}

/// This struct describes the current state of an in-progress PVF pre-checking vote.
#[derive(Encode, Decode, TypeInfo)]
pub(crate) struct PvfCheckActiveVoteState<BlockNumber> {
	// The two following vectors have their length equal to the number of validators in the active
	// set. They start with all zeroes. A 1 is set at an index when the validator at the that index
	// makes a vote. Once a 1 is set for either of the vectors, that validator cannot vote anymore.
	// Since the active validator set changes each session, the bit vectors are reinitialized as
	// well: zeroed and resized so that each validator gets its own bit.
	votes_accept: BitVec<u8, BitOrderLsb0>,
	votes_reject: BitVec<u8, BitOrderLsb0>,

	/// The number of session changes this PVF vote has observed. Therefore, this number is
	/// increased at each session boundary. When created, it is initialized with 0.
	age: SessionIndex,
	/// The block number at which this PVF vote was created.
	created_at: BlockNumber,
	/// A list of causes for this PVF pre-checking. Has at least one.
	causes: Vec<PvfCheckCause<BlockNumber>>,
}

impl<BlockNumber> PvfCheckActiveVoteState<BlockNumber> {
	/// Returns a new instance of vote state, started at the specified block `now`, with the
	/// number of validators in the current session `n_validators` and the originating `cause`.
	fn new(now: BlockNumber, n_validators: usize, cause: PvfCheckCause<BlockNumber>) -> Self {
		let mut causes = Vec::with_capacity(1);
		causes.push(cause);
		Self {
			created_at: now,
			votes_accept: bitvec::bitvec![u8, BitOrderLsb0; 0; n_validators],
			votes_reject: bitvec::bitvec![u8, BitOrderLsb0; 0; n_validators],
			age: 0,
			causes,
		}
	}

	/// Resets all votes and resizes the votes vectors corresponding to the number of validators
	/// in the new session.
	fn reinitialize_ballots(&mut self, n_validators: usize) {
		let clear_and_resize = |v: &mut BitVec<_, _>| {
			v.clear();
			v.resize(n_validators, false);
		};
		clear_and_resize(&mut self.votes_accept);
		clear_and_resize(&mut self.votes_reject);
	}

	/// Returns `Some(true)` if the validator at the given index has already cast their vote within
	/// the ongoing session. Returns `None` in case the index is out of bounds.
	fn has_vote(&self, validator_index: usize) -> Option<bool> {
		let accept_vote = self.votes_accept.get(validator_index)?;
		let reject_vote = self.votes_reject.get(validator_index)?;
		Some(*accept_vote || *reject_vote)
	}

	/// Returns `None` if the quorum is not reached, or the direction of the decision.
	fn quorum(&self, n_validators: usize) -> Option<PvfCheckOutcome> {
		let accept_threshold = primitives::supermajority_threshold(n_validators);
		// At this threshold, a supermajority is no longer possible, so we reject.
		let reject_threshold = n_validators - accept_threshold;

		if self.votes_accept.count_ones() >= accept_threshold {
			Some(PvfCheckOutcome::Accepted)
		} else if self.votes_reject.count_ones() > reject_threshold {
			Some(PvfCheckOutcome::Rejected)
		} else {
			None
		}
	}

	#[cfg(test)]
	pub(crate) fn causes(&self) -> &[PvfCheckCause<BlockNumber>] {
		self.causes.as_slice()
	}
}

/// Runtime hook for when a parachain head is updated.
pub trait OnNewHead {
	/// Called when a parachain head is updated.
	/// Returns the weight consumed by this function.
	fn on_new_head(id: ParaId, head: &HeadData) -> Weight;
}

#[impl_trait_for_tuples::impl_for_tuples(30)]
impl OnNewHead for Tuple {
	fn on_new_head(id: ParaId, head: &HeadData) -> Weight {
		let mut weight: Weight = Default::default();
		for_tuples!( #( weight.saturating_accrue(Tuple::on_new_head(id, head)); )* );
		weight
	}
}

/// Assign coretime to some parachain.
///
/// This assigns coretime to a parachain without using the coretime chain. Thus, this should only be
/// used for testing purposes.
pub trait AssignCoretime {
	/// ONLY USE FOR TESTING OR GENESIS.
	fn assign_coretime(id: ParaId) -> DispatchResult;
}

impl AssignCoretime for () {
	fn assign_coretime(_: ParaId) -> DispatchResult {
		Ok(())
	}
}

pub trait WeightInfo {
	fn force_set_current_code(c: u32) -> Weight;
	fn force_set_current_head(s: u32) -> Weight;
	fn force_set_most_recent_context() -> Weight;
	fn force_schedule_code_upgrade(c: u32) -> Weight;
	fn force_note_new_head(s: u32) -> Weight;
	fn force_queue_action() -> Weight;
	fn add_trusted_validation_code(c: u32) -> Weight;
	fn poke_unused_validation_code() -> Weight;

	fn include_pvf_check_statement_finalize_upgrade_accept() -> Weight;
	fn include_pvf_check_statement_finalize_upgrade_reject() -> Weight;
	fn include_pvf_check_statement_finalize_onboarding_accept() -> Weight;
	fn include_pvf_check_statement_finalize_onboarding_reject() -> Weight;
	fn include_pvf_check_statement() -> Weight;
}

pub struct TestWeightInfo;
impl WeightInfo for TestWeightInfo {
	fn force_set_current_code(_c: u32) -> Weight {
		Weight::MAX
	}
	fn force_set_current_head(_s: u32) -> Weight {
		Weight::MAX
	}
	fn force_set_most_recent_context() -> Weight {
		Weight::MAX
	}
	fn force_schedule_code_upgrade(_c: u32) -> Weight {
		Weight::MAX
	}
	fn force_note_new_head(_s: u32) -> Weight {
		Weight::MAX
	}
	fn force_queue_action() -> Weight {
		Weight::MAX
	}
	fn add_trusted_validation_code(_c: u32) -> Weight {
		// Called during integration tests for para initialization.
		Weight::zero()
	}
	fn poke_unused_validation_code() -> Weight {
		Weight::MAX
	}
	fn include_pvf_check_statement_finalize_upgrade_accept() -> Weight {
		Weight::MAX
	}
	fn include_pvf_check_statement_finalize_upgrade_reject() -> Weight {
		Weight::MAX
	}
	fn include_pvf_check_statement_finalize_onboarding_accept() -> Weight {
		Weight::MAX
	}
	fn include_pvf_check_statement_finalize_onboarding_reject() -> Weight {
		Weight::MAX
	}
	fn include_pvf_check_statement() -> Weight {
		// This special value is to distinguish from the finalizing variants above in tests.
		Weight::MAX - Weight::from_parts(1, 1)
	}
}

#[frame_support::pallet]
pub mod pallet {
	use super::*;
	use sp_runtime::transaction_validity::{
		InvalidTransaction, TransactionPriority, TransactionSource, TransactionValidity,
		ValidTransaction,
	};

	#[pallet::pallet]
	#[pallet::without_storage_info]
	pub struct Pallet<T>(_);

	#[pallet::config]
	pub trait Config:
		frame_system::Config
		+ configuration::Config
		+ shared::Config
		+ frame_system::offchain::SendTransactionTypes<Call<Self>>
	{
		type RuntimeEvent: From<Event> + IsType<<Self as frame_system::Config>::RuntimeEvent>;

		#[pallet::constant]
		type UnsignedPriority: Get<TransactionPriority>;

		type NextSessionRotation: EstimateNextSessionRotation<BlockNumberFor<Self>>;

		/// Retrieve how many UMP messages are enqueued for this para-chain.
		///
		/// This is used to judge whether or not a para-chain can offboard. Per default this should
		/// be set to the `ParaInclusion` pallet.
		type QueueFootprinter: QueueFootprinter<Origin = UmpQueueId>;

		/// Runtime hook for when a parachain head is updated.
		type OnNewHead: OnNewHead;

		/// Weight information for extrinsics in this pallet.
		type WeightInfo: WeightInfo;

		/// Runtime hook for assigning coretime for a given parachain.
		///
		/// This is only used at genesis or by root.
		///
		/// TODO: Remove once coretime is the standard across all chains.
		type AssignCoretime: AssignCoretime;
	}

	#[pallet::event]
	#[pallet::generate_deposit(pub(super) fn deposit_event)]
	pub enum Event {
		/// Current code has been updated for a Para. `para_id`
		CurrentCodeUpdated(ParaId),
		/// Current head has been updated for a Para. `para_id`
		CurrentHeadUpdated(ParaId),
		/// A code upgrade has been scheduled for a Para. `para_id`
		CodeUpgradeScheduled(ParaId),
		/// A new head has been noted for a Para. `para_id`
		NewHeadNoted(ParaId),
		/// A para has been queued to execute pending actions. `para_id`
		ActionQueued(ParaId, SessionIndex),
		/// The given para either initiated or subscribed to a PVF check for the given validation
		/// code. `code_hash` `para_id`
		PvfCheckStarted(ValidationCodeHash, ParaId),
		/// The given validation code was accepted by the PVF pre-checking vote.
		/// `code_hash` `para_id`
		PvfCheckAccepted(ValidationCodeHash, ParaId),
		/// The given validation code was rejected by the PVF pre-checking vote.
		/// `code_hash` `para_id`
		PvfCheckRejected(ValidationCodeHash, ParaId),
	}

	#[pallet::error]
	pub enum Error<T> {
		/// Para is not registered in our system.
		NotRegistered,
		/// Para cannot be onboarded because it is already tracked by our system.
		CannotOnboard,
		/// Para cannot be offboarded at this time.
		CannotOffboard,
		/// Para cannot be upgraded to a lease holding parachain.
		CannotUpgrade,
		/// Para cannot be downgraded to an on-demand parachain.
		CannotDowngrade,
		/// The statement for PVF pre-checking is stale.
		PvfCheckStatementStale,
		/// The statement for PVF pre-checking is for a future session.
		PvfCheckStatementFuture,
		/// Claimed validator index is out of bounds.
		PvfCheckValidatorIndexOutOfBounds,
		/// The signature for the PVF pre-checking is invalid.
		PvfCheckInvalidSignature,
		/// The given validator already has cast a vote.
		PvfCheckDoubleVote,
		/// The given PVF does not exist at the moment of process a vote.
		PvfCheckSubjectInvalid,
		/// Parachain cannot currently schedule a code upgrade.
		CannotUpgradeCode,
		/// Invalid validation code size.
		InvalidCode,
	}

	/// All currently active PVF pre-checking votes.
	///
	/// Invariant:
	/// - There are no PVF pre-checking votes that exists in list but not in the set and vice versa.
	#[pallet::storage]
	pub(super) type PvfActiveVoteMap<T: Config> = StorageMap<
		_,
		Twox64Concat,
		ValidationCodeHash,
		PvfCheckActiveVoteState<BlockNumberFor<T>>,
		OptionQuery,
	>;

	/// The list of all currently active PVF votes. Auxiliary to `PvfActiveVoteMap`.
	#[pallet::storage]
	pub(super) type PvfActiveVoteList<T: Config> =
		StorageValue<_, Vec<ValidationCodeHash>, ValueQuery>;

	/// All lease holding parachains. Ordered ascending by `ParaId`. On demand parachains are not
	/// included.
	///
	/// Consider using the [`ParachainsCache`] type of modifying.
	#[pallet::storage]
	pub type Parachains<T: Config> = StorageValue<_, Vec<ParaId>, ValueQuery>;

	/// The current lifecycle of a all known Para IDs.
	#[pallet::storage]
	pub(super) type ParaLifecycles<T: Config> = StorageMap<_, Twox64Concat, ParaId, ParaLifecycle>;

	/// The head-data of every registered para.
	#[pallet::storage]
	pub type Heads<T: Config> = StorageMap<_, Twox64Concat, ParaId, HeadData>;

	/// The context (relay-chain block number) of the most recent parachain head.
	#[pallet::storage]
	pub type MostRecentContext<T: Config> = StorageMap<_, Twox64Concat, ParaId, BlockNumberFor<T>>;

	/// The validation code hash of every live para.
	///
	/// Corresponding code can be retrieved with [`CodeByHash`].
	#[pallet::storage]
	pub type CurrentCodeHash<T: Config> = StorageMap<_, Twox64Concat, ParaId, ValidationCodeHash>;

	/// Actual past code hash, indicated by the para id as well as the block number at which it
	/// became outdated.
	///
	/// Corresponding code can be retrieved with [`CodeByHash`].
	#[pallet::storage]
	pub(super) type PastCodeHash<T: Config> =
		StorageMap<_, Twox64Concat, (ParaId, BlockNumberFor<T>), ValidationCodeHash>;

	/// 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 keep it available for approval checkers.
	#[pallet::storage]
	pub type PastCodeMeta<T: Config> =
		StorageMap<_, Twox64Concat, ParaId, ParaPastCodeMeta<BlockNumberFor<T>>, ValueQuery>;

	/// Which paras have past code that needs pruning and the relay-chain block at which the code
	/// was replaced. Note that this is the actual height of the included block, not the expected
	/// height at which the code upgrade would be applied, although they may be equal.
	/// This is to ensure the entire acceptance period is covered, not an offset acceptance period
	/// starting from the time at which the parachain perceives a code upgrade as having occurred.
	/// Multiple entries for a single para are permitted. Ordered ascending by block number.
	#[pallet::storage]
	pub(super) type PastCodePruning<T: Config> =
		StorageValue<_, Vec<(ParaId, BlockNumberFor<T>)>, ValueQuery>;

	/// The block number at which the planned code change is expected for a parachain.
	///
	/// 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`.
	#[pallet::storage]
	pub type FutureCodeUpgrades<T: Config> = StorageMap<_, Twox64Concat, ParaId, BlockNumberFor<T>>;

	/// The list of upcoming future code upgrades.
	///
	/// Each item is a pair of the parachain and the expected block at which the upgrade should be
	/// applied. The upgrade will be applied at the given relay chain block. In contrast to
	/// [`FutureCodeUpgrades`] this code upgrade will be applied regardless the parachain making any
	/// progress or not.
	///
	/// Ordered ascending by block number.
	#[pallet::storage]
	pub(super) type FutureCodeUpgradesAt<T: Config> =
		StorageValue<_, Vec<(ParaId, BlockNumberFor<T>)>, ValueQuery>;

	/// The actual future code hash of a para.
	///
	/// Corresponding code can be retrieved with [`CodeByHash`].
	#[pallet::storage]
	pub type FutureCodeHash<T: Config> = StorageMap<_, Twox64Concat, ParaId, ValidationCodeHash>;

	/// This is used by the relay-chain to communicate to a parachain a go-ahead with in the upgrade
	/// procedure.
	///
	/// This value is absent when there are no upgrades scheduled or during the time the relay chain
	/// performs the checks. It is set at the first relay-chain block when the corresponding
	/// parachain can switch its upgrade function. As soon as the parachain's block is included, the
	/// value gets reset to `None`.
	///
	/// NOTE that this field is used by parachains via merkle storage proofs, therefore changing
	/// the format will require migration of parachains.
	#[pallet::storage]
	pub(super) type UpgradeGoAheadSignal<T: Config> =
		StorageMap<_, Twox64Concat, ParaId, UpgradeGoAhead>;

	/// This is used by the relay-chain to communicate that there are restrictions for performing
	/// an upgrade for this parachain.
	///
	/// This may be a because the parachain waits for the upgrade cooldown to expire. Another
	/// potential use case is when we want to perform some maintenance (such as storage migration)
	/// we could restrict upgrades to make the process simpler.
	///
	/// NOTE that this field is used by parachains via merkle storage proofs, therefore changing
	/// the format will require migration of parachains.
	#[pallet::storage]
	pub type UpgradeRestrictionSignal<T: Config> =
		StorageMap<_, Twox64Concat, ParaId, UpgradeRestriction>;

	/// The list of parachains that are awaiting for their upgrade restriction to cooldown.
	///
	/// Ordered ascending by block number.
	#[pallet::storage]
	pub(super) type UpgradeCooldowns<T: Config> =
		StorageValue<_, Vec<(ParaId, BlockNumberFor<T>)>, ValueQuery>;

	/// The list of upcoming code upgrades.
	///
	/// Each item is a pair of which para performs a code upgrade and at which relay-chain block it
	/// is expected at.
	///
	/// Ordered ascending by block number.
	#[pallet::storage]
	pub(super) type UpcomingUpgrades<T: Config> =
		StorageValue<_, Vec<(ParaId, BlockNumberFor<T>)>, ValueQuery>;

	/// The actions to perform during the start of a specific session index.
	#[pallet::storage]
	pub type ActionsQueue<T: Config> =
		StorageMap<_, Twox64Concat, SessionIndex, Vec<ParaId>, ValueQuery>;

	/// Upcoming paras instantiation arguments.
	///
	/// NOTE that after PVF pre-checking is enabled the para genesis arg will have it's code set
	/// to empty. Instead, the code will be saved into the storage right away via `CodeByHash`.
	#[pallet::storage]
	pub(super) type UpcomingParasGenesis<T: Config> =
		StorageMap<_, Twox64Concat, ParaId, ParaGenesisArgs>;

	/// The number of reference on the validation code in [`CodeByHash`] storage.
	#[pallet::storage]
	pub(super) type CodeByHashRefs<T: Config> =
		StorageMap<_, Identity, ValidationCodeHash, u32, ValueQuery>;

	/// Validation code stored by its hash.
	///
	/// This storage is consistent with [`FutureCodeHash`], [`CurrentCodeHash`] and
	/// [`PastCodeHash`].
	#[pallet::storage]
	pub type CodeByHash<T: Config> = StorageMap<_, Identity, ValidationCodeHash, ValidationCode>;

	#[pallet::genesis_config]
	#[derive(DefaultNoBound)]
	pub struct GenesisConfig<T: Config> {
		#[serde(skip)]
		pub _config: sp_std::marker::PhantomData<T>,
		pub paras: Vec<(ParaId, ParaGenesisArgs)>,
	}

	#[pallet::genesis_build]
	impl<T: Config> BuildGenesisConfig for GenesisConfig<T> {
		fn build(&self) {
			let mut parachains = ParachainsCache::new();
			for (id, genesis_args) in &self.paras {
				if genesis_args.validation_code.0.is_empty() {
					panic!("empty validation code is not allowed in genesis");
				}
				Pallet::<T>::initialize_para_now(&mut parachains, *id, genesis_args);
				T::AssignCoretime::assign_coretime(*id)
					.expect("Assigning coretime works at genesis; qed");
			}
			// parachains are flushed on drop
		}
	}

	#[pallet::call]
	impl<T: Config> Pallet<T> {
		/// Set the storage for the parachain validation code immediately.
		#[pallet::call_index(0)]
		#[pallet::weight(<T as Config>::WeightInfo::force_set_current_code(new_code.0.len() as u32))]
		pub fn force_set_current_code(
			origin: OriginFor<T>,
			para: ParaId,
			new_code: ValidationCode,
		) -> DispatchResult {
			ensure_root(origin)?;
			let new_code_hash = new_code.hash();
			Self::increase_code_ref(&new_code_hash, &new_code);
			Self::set_current_code(para, new_code_hash, frame_system::Pallet::<T>::block_number());
			Self::deposit_event(Event::CurrentCodeUpdated(para));
			Ok(())
		}

		/// Set the storage for the current parachain head data immediately.
		#[pallet::call_index(1)]
		#[pallet::weight(<T as Config>::WeightInfo::force_set_current_head(new_head.0.len() as u32))]
		pub fn force_set_current_head(
			origin: OriginFor<T>,
			para: ParaId,
			new_head: HeadData,
		) -> DispatchResult {
			ensure_root(origin)?;
			Self::set_current_head(para, new_head);
			Ok(())
		}

		/// Schedule an upgrade as if it was scheduled in the given relay parent block.
		#[pallet::call_index(2)]
		#[pallet::weight(<T as Config>::WeightInfo::force_schedule_code_upgrade(new_code.0.len() as u32))]
		pub fn force_schedule_code_upgrade(
			origin: OriginFor<T>,
			para: ParaId,
			new_code: ValidationCode,
			relay_parent_number: BlockNumberFor<T>,
		) -> DispatchResult {
			ensure_root(origin)?;
			let config = configuration::ActiveConfig::<T>::get();
			Self::schedule_code_upgrade(
				para,
				new_code,
				relay_parent_number,
				&config,
				UpgradeStrategy::ApplyAtExpectedBlock,
			);
			Self::deposit_event(Event::CodeUpgradeScheduled(para));
			Ok(())
		}

		/// Note a new block head for para within the context of the current block.
		#[pallet::call_index(3)]
		#[pallet::weight(<T as Config>::WeightInfo::force_note_new_head(new_head.0.len() as u32))]
		pub fn force_note_new_head(
			origin: OriginFor<T>,
			para: ParaId,
			new_head: HeadData,
		) -> DispatchResult {
			ensure_root(origin)?;
			let now = frame_system::Pallet::<T>::block_number();
			Self::note_new_head(para, new_head, now);
			Self::deposit_event(Event::NewHeadNoted(para));
			Ok(())
		}

		/// Put a parachain directly into the next session's action queue.
		/// We can't queue it any sooner than this without going into the
		/// initializer...
		#[pallet::call_index(4)]
		#[pallet::weight(<T as Config>::WeightInfo::force_queue_action())]
		pub fn force_queue_action(origin: OriginFor<T>, para: ParaId) -> DispatchResult {
			ensure_root(origin)?;
			let next_session = shared::CurrentSessionIndex::<T>::get().saturating_add(One::one());
			ActionsQueue::<T>::mutate(next_session, |v| {
				if let Err(i) = v.binary_search(&para) {
					v.insert(i, para);
				}
			});
			Self::deposit_event(Event::ActionQueued(para, next_session));
			Ok(())
		}

		/// Adds the validation code to the storage.
		///
		/// The code will not be added if it is already present. Additionally, if PVF pre-checking
		/// is running for that code, it will be instantly accepted.
		///
		/// Otherwise, the code will be added into the storage. Note that the code will be added
		/// into storage with reference count 0. This is to account the fact that there are no users
		/// for this code yet. The caller will have to make sure that this code eventually gets
		/// used by some parachain or removed from the storage to avoid storage leaks. For the
		/// latter prefer to use the `poke_unused_validation_code` dispatchable to raw storage
		/// manipulation.
		///
		/// This function is mainly meant to be used for upgrading parachains that do not follow
		/// the go-ahead signal while the PVF pre-checking feature is enabled.
		#[pallet::call_index(5)]
		#[pallet::weight(<T as Config>::WeightInfo::add_trusted_validation_code(validation_code.0.len() as u32))]
		pub fn add_trusted_validation_code(
			origin: OriginFor<T>,
			validation_code: ValidationCode,
		) -> DispatchResult {
			ensure_root(origin)?;
			let code_hash = validation_code.hash();

			if let Some(vote) = PvfActiveVoteMap::<T>::get(&code_hash) {
				// Remove the existing vote.
				PvfActiveVoteMap::<T>::remove(&code_hash);
				PvfActiveVoteList::<T>::mutate(|l| {
					if let Ok(i) = l.binary_search(&code_hash) {