lib.rs

// Copyright 2019-2021 Parity Technologies (UK) Ltd.
// This file is part of Parity Bridges Common.

// Parity Bridges Common 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.

// Parity Bridges Common 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 Parity Bridges Common.  If not, see <http://www.gnu.org/licenses/>.

//! Runtime module that allows sending and receiving messages using lane concept:
//!
//! 1) the message is sent using `send_message()` call;
//! 2) every outbound message is assigned nonce;
//! 3) the messages are stored in the storage;
//! 4) external component (relay) delivers messages to bridged chain;
//! 5) messages are processed in order (ordered by assigned nonce);
//! 6) relay may send proof-of-delivery back to this chain.
//!
//! Once message is sent, its progress can be tracked by looking at module events.
//! The assigned nonce is reported using `MessageAccepted` event. When message is
//! delivered to the the bridged chain, it is reported using `MessagesDelivered` event.
//!
//! **IMPORTANT NOTE**: after generating weights (custom `WeighInfo` implementation) for
//! your runtime (where this module is plugged to), please add test for these weights.
//! The test should call the `ensure_weights_are_correct` function from this module.
//! If this test fails with your weights, then either weights are computed incorrectly,
//! or some benchmarks assumptions are broken for your runtime.

#![cfg_attr(not(feature = "std"), no_std)]
// Generated by `decl_event!`
#![allow(clippy::unused_unit)]

pub use inbound_lane::StoredInboundLaneData;
pub use outbound_lane::StoredMessageData;
pub use weights::WeightInfo;
pub use weights_ext::{
	ensure_able_to_receive_confirmation, ensure_able_to_receive_message,
	ensure_weights_are_correct, WeightInfoExt, EXPECTED_DEFAULT_MESSAGE_LENGTH,
};

use crate::{
	inbound_lane::{InboundLane, InboundLaneStorage, ReceivalResult},
	outbound_lane::{OutboundLane, OutboundLaneStorage, ReceivalConfirmationResult},
};

use bp_messages::{
	source_chain::{
		LaneMessageVerifier, MessageDeliveryAndDispatchPayment, OnDeliveryConfirmed,
		OnMessageAccepted, RelayersRewards, SendMessageArtifacts, TargetHeaderChain,
	},
	target_chain::{
		DispatchMessage, MessageDispatch, ProvedLaneMessages, ProvedMessages, SourceHeaderChain,
	},
	total_unrewarded_messages, DeliveredMessages, InboundLaneData, InboundMessageDetails, LaneId,
	MessageData, MessageKey, MessageNonce, MessagePayload, MessagesOperatingMode, OutboundLaneData,
	OutboundMessageDetails, Parameter as MessagesParameter, UnrewardedRelayer,
	UnrewardedRelayersState,
};
use bp_runtime::{BasicOperatingMode, ChainId, OwnedBridgeModule, Size};
use codec::{Decode, Encode, MaxEncodedLen};
use frame_support::{
	ensure, fail,
	traits::Get,
	weights::{Pays, PostDispatchInfo},
};
use num_traits::{SaturatingAdd, Zero};
use sp_std::{
	cell::RefCell, cmp::PartialOrd, collections::vec_deque::VecDeque, marker::PhantomData,
	ops::RangeInclusive, prelude::*,
};

mod inbound_lane;
mod outbound_lane;
mod weights_ext;

pub mod weights;

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

#[cfg(test)]
mod mock;

pub use pallet::*;

/// The target that will be used when publishing logs related to this pallet.
pub const LOG_TARGET: &str = "runtime::bridge-messages";

#[frame_support::pallet]
pub mod pallet {
	use super::*;
	use frame_support::pallet_prelude::*;
	use frame_system::pallet_prelude::*;

	#[pallet::config]
	pub trait Config<I: 'static = ()>: frame_system::Config {
		// General types

		/// The overarching event type.
		type Event: From<Event<Self, I>> + IsType<<Self as frame_system::Config>::Event>;
		/// Benchmarks results from runtime we're plugged into.
		type WeightInfo: WeightInfoExt;

		/// Gets the chain id value from the instance.
		#[pallet::constant]
		type BridgedChainId: Get<ChainId>;
		/// Pallet parameter that is opaque to the pallet itself, but may be used by the runtime
		/// for integrating the pallet.
		///
		/// All pallet parameters may only be updated either by the root, or by the pallet owner.
		type Parameter: MessagesParameter;

		/// Maximal number of messages that may be pruned during maintenance. Maintenance occurs
		/// whenever new message is sent. The reason is that if you want to use lane, you should
		/// be ready to pay for its maintenance.
		type MaxMessagesToPruneAtOnce: Get<MessageNonce>;
		/// Maximal number of unrewarded relayer entries at inbound lane. Unrewarded means that the
		/// relayer has delivered messages, but either confirmations haven't been delivered back to
		/// the source chain, or we haven't received reward confirmations yet.
		///
		/// This constant limits maximal number of entries in the `InboundLaneData::relayers`. Keep
		/// in mind that the same relayer account may take several (non-consecutive) entries in this
		/// set.
		type MaxUnrewardedRelayerEntriesAtInboundLane: Get<MessageNonce>;
		/// Maximal number of unconfirmed messages at inbound lane. Unconfirmed means that the
		/// message has been delivered, but either confirmations haven't been delivered back to the
		/// source chain, or we haven't received reward confirmations for these messages yet.
		///
		/// This constant limits difference between last message from last entry of the
		/// `InboundLaneData::relayers` and first message at the first entry.
		///
		/// There is no point of making this parameter lesser than
		/// MaxUnrewardedRelayerEntriesAtInboundLane, because then maximal number of relayer entries
		/// will be limited by maximal number of messages.
		///
		/// This value also represents maximal number of messages in single delivery transaction.
		/// Transaction that is declaring more messages than this value, will be rejected. Even if
		/// these messages are from different lanes.
		type MaxUnconfirmedMessagesAtInboundLane: Get<MessageNonce>;

		/// Maximal size of the outbound payload.
		#[pallet::constant]
		type MaximalOutboundPayloadSize: Get<u32>;
		/// Payload type of outbound messages. This payload is dispatched on the bridged chain.
		type OutboundPayload: Parameter + Size;
		/// Message fee type of outbound messages. This fee is paid on this chain.
		type OutboundMessageFee: Default
			+ From<u64>
			+ PartialOrd
			+ Parameter
			+ SaturatingAdd
			+ Zero
			+ Copy
			+ MaxEncodedLen;

		/// Payload type of inbound messages. This payload is dispatched on this chain.
		type InboundPayload: Decode;
		/// Message fee type of inbound messages. This fee is paid on the bridged chain.
		type InboundMessageFee: Decode + Zero;
		/// Identifier of relayer that deliver messages to this chain. Relayer reward is paid on the
		/// bridged chain.
		type InboundRelayer: Parameter + MaxEncodedLen;

		// Types that are used by outbound_lane (on source chain).

		/// Target header chain.
		type TargetHeaderChain: TargetHeaderChain<Self::OutboundPayload, Self::AccountId>;
		/// Message payload verifier.
		type LaneMessageVerifier: LaneMessageVerifier<
			Self::Origin,
			Self::AccountId,
			Self::OutboundPayload,
			Self::OutboundMessageFee,
		>;
		/// Message delivery payment.
		type MessageDeliveryAndDispatchPayment: MessageDeliveryAndDispatchPayment<
			Self::Origin,
			Self::AccountId,
			Self::OutboundMessageFee,
		>;
		/// Handler for accepted messages.
		type OnMessageAccepted: OnMessageAccepted;
		/// Handler for delivered messages.
		type OnDeliveryConfirmed: OnDeliveryConfirmed;

		// Types that are used by inbound_lane (on target chain).

		/// Source header chain, as it is represented on target chain.
		type SourceHeaderChain: SourceHeaderChain<Self::InboundMessageFee>;
		/// Message dispatch.
		type MessageDispatch: MessageDispatch<
			Self::AccountId,
			Self::InboundMessageFee,
			DispatchPayload = Self::InboundPayload,
		>;
	}

	/// Shortcut to messages proof type for Config.
	type MessagesProofOf<T, I> = <<T as Config<I>>::SourceHeaderChain as SourceHeaderChain<
		<T as Config<I>>::InboundMessageFee,
	>>::MessagesProof;
	/// Shortcut to messages delivery proof type for Config.
	type MessagesDeliveryProofOf<T, I> =
		<<T as Config<I>>::TargetHeaderChain as TargetHeaderChain<
			<T as Config<I>>::OutboundPayload,
			<T as frame_system::Config>::AccountId,
		>>::MessagesDeliveryProof;

	#[pallet::pallet]
	#[pallet::generate_store(pub(super) trait Store)]
	pub struct Pallet<T, I = ()>(PhantomData<(T, I)>);

	impl<T: Config<I>, I: 'static> OwnedBridgeModule<T> for Pallet<T, I> {
		const LOG_TARGET: &'static str = LOG_TARGET;
		type OwnerStorage = PalletOwner<T, I>;
		type OperatingMode = MessagesOperatingMode;
		type OperatingModeStorage = PalletOperatingMode<T, I>;
	}

	#[pallet::call]
	impl<T: Config<I>, I: 'static> Pallet<T, I> {
		/// Change `PalletOwner`.
		///
		/// May only be called either by root, or by `PalletOwner`.
		#[pallet::weight((T::DbWeight::get().reads_writes(1, 1), DispatchClass::Operational))]
		pub fn set_owner(origin: OriginFor<T>, new_owner: Option<T::AccountId>) -> DispatchResult {
			<Self as OwnedBridgeModule<_>>::set_owner(origin, new_owner)
		}

		/// Halt or resume all/some pallet operations.
		///
		/// May only be called either by root, or by `PalletOwner`.
		#[pallet::weight((T::DbWeight::get().reads_writes(1, 1), DispatchClass::Operational))]
		pub fn set_operating_mode(
			origin: OriginFor<T>,
			operating_mode: MessagesOperatingMode,
		) -> DispatchResult {
			<Self as OwnedBridgeModule<_>>::set_operating_mode(origin, operating_mode)
		}

		/// Update pallet parameter.
		///
		/// May only be called either by root, or by `PalletOwner`.
		///
		/// The weight is: single read for permissions check + 2 writes for parameter value and
		/// event.
		#[pallet::weight((T::DbWeight::get().reads_writes(1, 2), DispatchClass::Operational))]
		pub fn update_pallet_parameter(
			origin: OriginFor<T>,
			parameter: T::Parameter,
		) -> DispatchResult {
			Self::ensure_owner_or_root(origin)?;
			parameter.save();
			Self::deposit_event(Event::ParameterUpdated { parameter });
			Ok(())
		}

		/// Send message over lane.
		#[pallet::weight(T::WeightInfo::send_message_weight(payload, T::DbWeight::get()))]
		pub fn send_message(
			origin: OriginFor<T>,
			lane_id: LaneId,
			payload: T::OutboundPayload,
			delivery_and_dispatch_fee: T::OutboundMessageFee,
		) -> DispatchResultWithPostInfo {
			crate::send_message::<T, I>(origin, lane_id, payload, delivery_and_dispatch_fee).map(
				|sent_message| PostDispatchInfo {
					actual_weight: Some(sent_message.weight),
					pays_fee: Pays::Yes,
				},
			)
		}

		/// Pay additional fee for the message.
		#[pallet::weight(T::WeightInfo::maximal_increase_message_fee())]
		pub fn increase_message_fee(
			origin: OriginFor<T>,
			lane_id: LaneId,
			nonce: MessageNonce,
			additional_fee: T::OutboundMessageFee,
		) -> DispatchResultWithPostInfo {
			Self::ensure_not_halted().map_err(Error::<T, I>::BridgeModule)?;
			// if someone tries to pay for already-delivered message, we're rejecting this intention
			// (otherwise this additional fee will be locked forever in relayers fund)
			//
			// if someone tries to pay for not-yet-sent message, we're rejecting this intention, or
			// we're risking to have mess in the storage
			let lane = outbound_lane::<T, I>(lane_id);
			ensure!(
				nonce > lane.data().latest_received_nonce,
				Error::<T, I>::MessageIsAlreadyDelivered
			);
			ensure!(
				nonce <= lane.data().latest_generated_nonce,
				Error::<T, I>::MessageIsNotYetSent
			);

			// withdraw additional fee from submitter
			T::MessageDeliveryAndDispatchPayment::pay_delivery_and_dispatch_fee(
				&origin,
				&additional_fee,
			)
			.map_err(|err| {
				log::trace!(
					target: LOG_TARGET,
					"Submitter can't pay additional fee {:?} for the message {:?}/{:?}: {:?}",
					additional_fee,
					lane_id,
					nonce,
					err,
				);

				Error::<T, I>::FailedToWithdrawMessageFee
			})?;

			// and finally update fee in the storage
			let message_key = MessageKey { lane_id, nonce };
			let message_size = OutboundMessages::<T, I>::mutate(message_key, |message_data| {
				// saturating_add is fine here - overflow here means that someone controls all
				// chain funds, which shouldn't ever happen + `pay_delivery_and_dispatch_fee`
				// above will fail before we reach here
				let message_data = message_data.as_mut().expect(
					"the message is sent and not yet delivered; so it is in the storage; qed",
				);
				message_data.fee = message_data.fee.saturating_add(&additional_fee);
				message_data.payload.len()
			});

			// compute actual dispatch weight that depends on the stored message size
			let actual_weight = sp_std::cmp::min(
				T::WeightInfo::maximal_increase_message_fee(),
				T::WeightInfo::increase_message_fee(message_size as _),
			);

			Ok(PostDispatchInfo { actual_weight: Some(actual_weight), pays_fee: Pays::Yes })
		}

		/// Receive messages proof from bridged chain.
		///
		/// The weight of the call assumes that the transaction always brings outbound lane
		/// state update. Because of that, the submitter (relayer) has no benefit of not including
		/// this data in the transaction, so reward confirmations lags should be minimal.
		#[pallet::weight(T::WeightInfo::receive_messages_proof_weight(proof, *messages_count, *dispatch_weight))]
		pub fn receive_messages_proof(
			origin: OriginFor<T>,
			relayer_id_at_bridged_chain: T::InboundRelayer,
			proof: MessagesProofOf<T, I>,
			messages_count: u32,
			dispatch_weight: Weight,
		) -> DispatchResultWithPostInfo {
			Self::ensure_not_halted().map_err(Error::<T, I>::BridgeModule)?;
			let relayer_id_at_this_chain = ensure_signed(origin)?;

			// reject transactions that are declaring too many messages
			ensure!(
				MessageNonce::from(messages_count) <= T::MaxUnconfirmedMessagesAtInboundLane::get(),
				Error::<T, I>::TooManyMessagesInTheProof
			);

			// why do we need to know the weight of this (`receive_messages_proof`) call? Because
			// we may want to return some funds for not-dispatching (or partially dispatching) some
			// messages to the call origin (relayer). And this is done by returning actual weight
			// from the call. But we only know dispatch weight of every messages. So to refund
			// relayer because we have not dispatched Message, we need to:
			//
			// ActualWeight = DeclaredWeight - Message.DispatchWeight
			//
			// The DeclaredWeight is exactly what's computed here. Unfortunately it is impossible
			// to get pre-computed value (and it has been already computed by the executive).
			let declared_weight = T::WeightInfo::receive_messages_proof_weight(
				&proof,
				messages_count,
				dispatch_weight,
			);
			let mut actual_weight = declared_weight;

			// verify messages proof && convert proof into messages
			let messages = verify_and_decode_messages_proof::<
				T::SourceHeaderChain,
				T::InboundMessageFee,
				T::InboundPayload,
			>(proof, messages_count)
			.map_err(|err| {
				log::trace!(target: LOG_TARGET, "Rejecting invalid messages proof: {:?}", err,);

				Error::<T, I>::InvalidMessagesProof
			})?;

			// dispatch messages and (optionally) update lane(s) state(s)
			let mut total_messages = 0;
			let mut valid_messages = 0;
			let mut dispatch_weight_left = dispatch_weight;
			for (lane_id, lane_data) in messages {
				let mut lane = inbound_lane::<T, I>(lane_id);

				if let Some(lane_state) = lane_data.lane_state {
					let updated_latest_confirmed_nonce = lane.receive_state_update(lane_state);
					if let Some(updated_latest_confirmed_nonce) = updated_latest_confirmed_nonce {
						log::trace!(
							target: LOG_TARGET,
							"Received lane {:?} state update: latest_confirmed_nonce={}",
							lane_id,
							updated_latest_confirmed_nonce,
						);
					}
				}

				for mut message in lane_data.messages {
					debug_assert_eq!(message.key.lane_id, lane_id);

					// ensure that relayer has declared enough weight for dispatching next message
					// on this lane. We can't dispatch lane messages out-of-order, so if declared
					// weight is not enough, let's move to next lane
					let dispatch_weight = T::MessageDispatch::dispatch_weight(&mut message);
					if dispatch_weight > dispatch_weight_left {
						log::trace!(
							target: LOG_TARGET,
							"Cannot dispatch any more messages on lane {:?}. Weight: declared={}, left={}",
							lane_id,
							dispatch_weight,
							dispatch_weight_left,
						);
						break
					}
					total_messages += 1;

					let receival_result = lane.receive_message::<T::MessageDispatch, T::AccountId>(
						&relayer_id_at_bridged_chain,
						&relayer_id_at_this_chain,
						message.key.nonce,
						message.data,
					);

					// note that we're returning unspent weight to relayer even if message has been
					// rejected by the lane. This allows relayers to submit spam transactions with
					// e.g. the same set of already delivered messages over and over again, without
					// losing funds for messages dispatch. But keep in mind that relayer pays base
					// delivery transaction cost anyway. And base cost covers everything except
					// dispatch, so we have a balance here.
					let (unspent_weight, refund_pay_dispatch_fee) = match receival_result {
						ReceivalResult::Dispatched(dispatch_result) => {
							valid_messages += 1;
							(
								dispatch_result.unspent_weight,
								!dispatch_result.dispatch_fee_paid_during_dispatch,
							)
						},
						ReceivalResult::InvalidNonce |
						ReceivalResult::TooManyUnrewardedRelayers |
						ReceivalResult::TooManyUnconfirmedMessages => (dispatch_weight, true),
					};

					let unspent_weight = sp_std::cmp::min(unspent_weight, dispatch_weight);
					dispatch_weight_left -= dispatch_weight - unspent_weight;
					actual_weight = actual_weight.saturating_sub(unspent_weight).saturating_sub(
						// delivery call weight formula assumes that the fee is paid at
						// this (target) chain. If the message is prepaid at the source
						// chain, let's refund relayer with this extra cost.
						if refund_pay_dispatch_fee {
							T::WeightInfo::pay_inbound_dispatch_fee_overhead()
						} else {
							0
						},
					);
				}
			}

			log::trace!(
				target: LOG_TARGET,
				"Received messages: total={}, valid={}. Weight used: {}/{}",
				total_messages,
				valid_messages,
				actual_weight,
				declared_weight,
			);

			Ok(PostDispatchInfo { actual_weight: Some(actual_weight), pays_fee: Pays::Yes })
		}

		/// Receive messages delivery proof from bridged chain.
		#[pallet::weight(T::WeightInfo::receive_messages_delivery_proof_weight(
			proof,
			relayers_state,
			T::DbWeight::get(),
		))]
		pub fn receive_messages_delivery_proof(
			origin: OriginFor<T>,
			proof: MessagesDeliveryProofOf<T, I>,
			relayers_state: UnrewardedRelayersState,
		) -> DispatchResultWithPostInfo {
			Self::ensure_not_halted().map_err(Error::<T, I>::BridgeModule)?;

			// why do we need to know the weight of this (`receive_messages_delivery_proof`) call?
			// Because we may want to return some funds for messages that are not processed by the
			// delivery callback, or if their actual processing weight is less than accounted by
			// weight formula. So to refund relayer, we need to:
			//
			// ActualWeight = DeclaredWeight - UnspentCallbackWeight
			//
			// The DeclaredWeight is exactly what's computed here. Unfortunately it is impossible
			// to get pre-computed value (and it has been already computed by the executive).
			let single_message_callback_overhead =
				T::WeightInfo::single_message_callback_overhead(T::DbWeight::get());
			let declared_weight = T::WeightInfo::receive_messages_delivery_proof_weight(
				&proof,
				&relayers_state,
				T::DbWeight::get(),
			);
			let mut actual_weight = declared_weight;

			let confirmation_relayer = ensure_signed(origin)?;
			let (lane_id, lane_data) = T::TargetHeaderChain::verify_messages_delivery_proof(proof)
				.map_err(|err| {
					log::trace!(
						target: LOG_TARGET,
						"Rejecting invalid messages delivery proof: {:?}",
						err,
					);

					Error::<T, I>::InvalidMessagesDeliveryProof
				})?;

			// verify that the relayer has declared correct `lane_data::relayers` state
			// (we only care about total number of entries and messages, because this affects call
			// weight)
			ensure!(
				total_unrewarded_messages(&lane_data.relayers).unwrap_or(MessageNonce::MAX) ==
					relayers_state.total_messages &&
					lane_data.relayers.len() as MessageNonce ==
						relayers_state.unrewarded_relayer_entries,
				Error::<T, I>::InvalidUnrewardedRelayersState
			);
			// the `last_delivered_nonce` field may also be used by the signed extension. Even
			// though providing wrong value isn't critical, let's also check it here.
			ensure!(
				lane_data.last_delivered_nonce() == relayers_state.last_delivered_nonce,
				Error::<T, I>::InvalidUnrewardedRelayersState
			);

			// mark messages as delivered
			let mut lane = outbound_lane::<T, I>(lane_id);
			let last_delivered_nonce = lane_data.last_delivered_nonce();
			let confirmed_messages = match lane.confirm_delivery(
				relayers_state.total_messages,
				last_delivered_nonce,
				&lane_data.relayers,
			) {
				ReceivalConfirmationResult::ConfirmedMessages(confirmed_messages) =>
					Some(confirmed_messages),
				ReceivalConfirmationResult::NoNewConfirmations => None,
				ReceivalConfirmationResult::TryingToConfirmMoreMessagesThanExpected(
					to_confirm_messages_count,
				) => {
					log::trace!(
						target: LOG_TARGET,
						"Messages delivery proof contains too many messages to confirm: {} vs declared {}",
						to_confirm_messages_count,
						relayers_state.total_messages,
					);

					fail!(Error::<T, I>::TryingToConfirmMoreMessagesThanExpected);
				},
				error => {
					log::trace!(
						target: LOG_TARGET,
						"Messages delivery proof contains invalid unrewarded relayers vec: {:?}",
						error,
					);

					fail!(Error::<T, I>::InvalidUnrewardedRelayers);
				},
			};

			if let Some(confirmed_messages) = confirmed_messages {
				// handle messages delivery confirmation
				let preliminary_callback_overhead =
					relayers_state.total_messages.saturating_mul(single_message_callback_overhead);
				let actual_callback_weight =
					T::OnDeliveryConfirmed::on_messages_delivered(&lane_id, &confirmed_messages);
				match preliminary_callback_overhead.checked_sub(actual_callback_weight) {
					Some(difference) if difference == 0 => (),
					Some(difference) => {
						log::trace!(
							target: LOG_TARGET,
							"T::OnDeliveryConfirmed callback has spent less weight than expected. Refunding: \
							{} - {} = {}",
							preliminary_callback_overhead,
							actual_callback_weight,
							difference,
						);
						actual_weight = actual_weight.saturating_sub(difference);
					},
					None => {
						debug_assert!(
							false,
							"T::OnDeliveryConfirmed callback consumed too much weight."
						);
						log::error!(
							target: LOG_TARGET,
							"T::OnDeliveryConfirmed callback has spent more weight that it is allowed to: \
							{} vs {}",
							preliminary_callback_overhead,
							actual_callback_weight,
						);
					},
				}

				// emit 'delivered' event
				let received_range = confirmed_messages.begin..=confirmed_messages.end;
				Self::deposit_event(Event::MessagesDelivered {
					lane_id,
					messages: confirmed_messages,
				});

				// if some new messages have been confirmed, reward relayers
				<T as Config<I>>::MessageDeliveryAndDispatchPayment::pay_relayers_rewards(
					lane_id,
					lane_data.relayers,
					&confirmation_relayer,
					&received_range,
				);
			}

			log::trace!(
				target: LOG_TARGET,
				"Received messages delivery proof up to (and including) {} at lane {:?}",
				last_delivered_nonce,
				lane_id,
			);

			Ok(PostDispatchInfo { actual_weight: Some(actual_weight), pays_fee: Pays::Yes })
		}
	}

	#[pallet::event]
	#[pallet::generate_deposit(pub(super) fn deposit_event)]
	pub enum Event<T: Config<I>, I: 'static = ()> {
		/// Pallet parameter has been updated.
		ParameterUpdated { parameter: T::Parameter },
		/// Message has been accepted and is waiting to be delivered.
		MessageAccepted { lane_id: LaneId, nonce: MessageNonce },
		/// Messages in the inclusive range have been delivered to the bridged chain.
		MessagesDelivered { lane_id: LaneId, messages: DeliveredMessages },
	}

	#[pallet::error]
	pub enum Error<T, I = ()> {
		/// Pallet is not in Normal operating mode.
		NotOperatingNormally,
		/// The message is too large to be sent over the bridge.
		MessageIsTooLarge,
		/// Message has been treated as invalid by chain verifier.
		MessageRejectedByChainVerifier,
		/// Message has been treated as invalid by lane verifier.
		MessageRejectedByLaneVerifier,
		/// Submitter has failed to pay fee for delivering and dispatching messages.
		FailedToWithdrawMessageFee,
		/// The transaction brings too many messages.
		TooManyMessagesInTheProof,
		/// Invalid messages has been submitted.
		InvalidMessagesProof,
		/// Invalid messages delivery proof has been submitted.
		InvalidMessagesDeliveryProof,
		/// The bridged chain has invalid `UnrewardedRelayers` in its storage (fatal for the lane).
		InvalidUnrewardedRelayers,
		/// The relayer has declared invalid unrewarded relayers state in the
		/// `receive_messages_delivery_proof` call.
		InvalidUnrewardedRelayersState,
		/// The message someone is trying to work with (i.e. increase fee) is already-delivered.
		MessageIsAlreadyDelivered,
		/// The message someone is trying to work with (i.e. increase fee) is not yet sent.
		MessageIsNotYetSent,
		/// The number of actually confirmed messages is going to be larger than the number of
		/// messages in the proof. This may mean that this or bridged chain storage is corrupted.
		TryingToConfirmMoreMessagesThanExpected,
		/// Error generated by the `OwnedBridgeModule` trait.
		BridgeModule(bp_runtime::OwnedBridgeModuleError),
	}

	/// Optional pallet owner.
	///
	/// Pallet owner has a right to halt all pallet operations and then resume it. If it is
	/// `None`, then there are no direct ways to halt/resume pallet operations, but other
	/// runtime methods may still be used to do that (i.e. democracy::referendum to update halt
	/// flag directly or call the `halt_operations`).
	#[pallet::storage]
	#[pallet::getter(fn module_owner)]
	pub type PalletOwner<T: Config<I>, I: 'static = ()> = StorageValue<_, T::AccountId>;

	/// The current operating mode of the pallet.
	///
	/// Depending on the mode either all, some, or no transactions will be allowed.
	#[pallet::storage]
	#[pallet::getter(fn operating_mode)]
	pub type PalletOperatingMode<T: Config<I>, I: 'static = ()> =
		StorageValue<_, MessagesOperatingMode, ValueQuery>;

	/// Map of lane id => inbound lane data.
	#[pallet::storage]
	pub type InboundLanes<T: Config<I>, I: 'static = ()> =
		StorageMap<_, Blake2_128Concat, LaneId, StoredInboundLaneData<T, I>, ValueQuery>;

	/// Map of lane id => outbound lane data.
	#[pallet::storage]
	pub type OutboundLanes<T: Config<I>, I: 'static = ()> =
		StorageMap<_, Blake2_128Concat, LaneId, OutboundLaneData, ValueQuery>;

	/// All queued outbound messages.
	#[pallet::storage]
	pub type OutboundMessages<T: Config<I>, I: 'static = ()> =
		StorageMap<_, Blake2_128Concat, MessageKey, StoredMessageData<T, I>>;

	#[pallet::genesis_config]
	pub struct GenesisConfig<T: Config<I>, I: 'static = ()> {
		/// Initial pallet operating mode.
		pub operating_mode: MessagesOperatingMode,
		/// Initial pallet owner.
		pub owner: Option<T::AccountId>,
		/// Dummy marker.
		pub phantom: sp_std::marker::PhantomData<I>,
	}

	#[cfg(feature = "std")]
	impl<T: Config<I>, I: 'static> Default for GenesisConfig<T, I> {
		fn default() -> Self {
			Self {
				operating_mode: Default::default(),
				owner: Default::default(),
				phantom: Default::default(),
			}
		}
	}

	#[pallet::genesis_build]
	impl<T: Config<I>, I: 'static> GenesisBuild<T, I> for GenesisConfig<T, I> {
		fn build(&self) {
			PalletOperatingMode::<T, I>::put(&self.operating_mode);
			if let Some(ref owner) = self.owner {
				PalletOwner::<T, I>::put(owner);
			}
		}
	}

	impl<T: Config<I>, I: 'static> Pallet<T, I> {
		/// Get stored data of the outbound message with given nonce.
		pub fn outbound_message_data(
			lane: LaneId,
			nonce: MessageNonce,
		) -> Option<MessageData<T::OutboundMessageFee>> {
			OutboundMessages::<T, I>::get(MessageKey { lane_id: lane, nonce }).map(Into::into)
		}

		/// Prepare data, related to given inbound message.
		pub fn inbound_message_data(
			lane: LaneId,
			payload: MessagePayload,
			outbound_details: OutboundMessageDetails<T::InboundMessageFee>,
		) -> InboundMessageDetails {
			let mut dispatch_message = DispatchMessage {
				key: MessageKey { lane_id: lane, nonce: outbound_details.nonce },
				data: MessageData { payload, fee: outbound_details.delivery_and_dispatch_fee }
					.into(),
			};
			InboundMessageDetails {
				dispatch_weight: T::MessageDispatch::dispatch_weight(&mut dispatch_message),
			}
		}
	}
}

impl<T, I>
	bp_messages::source_chain::MessagesBridge<
		T::Origin,
		T::AccountId,
		T::OutboundMessageFee,
		T::OutboundPayload,
	> for Pallet<T, I>
where
	T: Config<I>,
	I: 'static,
{
	type Error = sp_runtime::DispatchErrorWithPostInfo<PostDispatchInfo>;

	fn send_message(
		sender: T::Origin,
		lane: LaneId,
		message: T::OutboundPayload,
		delivery_and_dispatch_fee: T::OutboundMessageFee,
	) -> Result<SendMessageArtifacts, Self::Error> {
		crate::send_message::<T, I>(sender, lane, message, delivery_and_dispatch_fee)
	}
}

/// Function that actually sends message.
fn send_message<T: Config<I>, I: 'static>(
	submitter: T::Origin,
	lane_id: LaneId,
	payload: T::OutboundPayload,
	delivery_and_dispatch_fee: T::OutboundMessageFee,
) -> sp_std::result::Result<
	SendMessageArtifacts,
	sp_runtime::DispatchErrorWithPostInfo<PostDispatchInfo>,
> {
	ensure_normal_operating_mode::<T, I>()?;

	// the most lightweigh check is the message size check
	ensure!(
		payload.size() <= T::MaximalOutboundPayloadSize::get(),
		Error::<T, I>::MessageIsTooLarge,
	);

	// initially, actual (post-dispatch) weight is equal to pre-dispatch weight
	let mut actual_weight = T::WeightInfo::send_message_weight(&payload, T::DbWeight::get());

	// let's first check if message can be delivered to target chain
	T::TargetHeaderChain::verify_message(&payload).map_err(|err| {
		log::trace!(
			target: LOG_TARGET,
			"Message to lane {:?} is rejected by target chain: {:?}",
			lane_id,
			err,
		);

		Error::<T, I>::MessageRejectedByChainVerifier
	})?;

	// now let's enforce any additional lane rules
	let mut lane = outbound_lane::<T, I>(lane_id);
	T::LaneMessageVerifier::verify_message(
		&submitter,
		&delivery_and_dispatch_fee,
		&lane_id,
		&lane.data(),
		&payload,
	)
	.map_err(|err| {
		log::trace!(
			target: LOG_TARGET,
			"Message to lane {:?} is rejected by lane verifier: {:?}",
			lane_id,
			err,
		);

		Error::<T, I>::MessageRejectedByLaneVerifier
	})?;

	// let's withdraw delivery and dispatch fee from submitter
	T::MessageDeliveryAndDispatchPayment::pay_delivery_and_dispatch_fee(
		&submitter,
		&delivery_and_dispatch_fee,
	)
	.map_err(|err| {
		log::trace!(
			target: LOG_TARGET,
			"Message to lane {:?} is rejected because submitter is unable to pay fee {:?}: {:?}",
			lane_id,
			delivery_and_dispatch_fee,
			err,
		);

		Error::<T, I>::FailedToWithdrawMessageFee
	})?;

	// finally, save message in outbound storage and emit event
	let encoded_payload = payload.encode();
	let encoded_payload_len = encoded_payload.len();
	let nonce =
		lane.send_message(MessageData { payload: encoded_payload, fee: delivery_and_dispatch_fee });
	// Guaranteed to be called outside only when the message is accepted.
	// We assume that the maximum weight call back used is `single_message_callback_overhead`, so do
	// not perform complex db operation in callback. If you want to, put these magic logic in
	// outside pallet and control the weight there.
	let single_message_callback_overhead =
		T::WeightInfo::single_message_callback_overhead(T::DbWeight::get());
	let actual_callback_weight = T::OnMessageAccepted::on_messages_accepted(&lane_id, &nonce);
	match single_message_callback_overhead.checked_sub(actual_callback_weight) {
		Some(difference) if difference == 0 => (),
		Some(difference) => {
			log::trace!(
				target: LOG_TARGET,
				"T::OnMessageAccepted callback has spent less weight than expected. Refunding: \
				{} - {} = {}",
				single_message_callback_overhead,
				actual_callback_weight,
				difference,
			);
			actual_weight = actual_weight.saturating_sub(difference);
		},
		None => {
			debug_assert!(false, "T::OnMessageAccepted callback consumed too much weight.");
			log::error!(
				target: LOG_TARGET,
				"T::OnMessageAccepted callback has spent more weight that it is allowed to: \
				{} vs {}",
				single_message_callback_overhead,
				actual_callback_weight,
			);
		},
	}

	// message sender pays for pruning at most `MaxMessagesToPruneAtOnce` messages
	// the cost of pruning every message is roughly single db write
	// => lets refund sender if less than `MaxMessagesToPruneAtOnce` messages pruned
	let max_messages_to_prune = T::MaxMessagesToPruneAtOnce::get();
	let pruned_messages = lane.prune_messages(max_messages_to_prune);
	if let Some(extra_messages) = max_messages_to_prune.checked_sub(pruned_messages) {
		actual_weight = actual_weight.saturating_sub(T::DbWeight::get().writes(extra_messages));
	}

	log::trace!(
		target: LOG_TARGET,
		"Accepted message {} to lane {:?}. Message size: {:?}",
		nonce,
		lane_id,
		encoded_payload_len,
	);

	Pallet::<T, I>::deposit_event(Event::MessageAccepted { lane_id, nonce });

	Ok(SendMessageArtifacts { nonce, weight: actual_weight })
}

/// Calculate the relayers rewards
pub fn calc_relayers_rewards<T, I>(
	lane_id: LaneId,
	messages_relayers: VecDeque<UnrewardedRelayer<T::AccountId>>,
	received_range: &RangeInclusive<MessageNonce>,
) -> RelayersRewards<T::AccountId, T::OutboundMessageFee>
where
	T: frame_system::Config + crate::Config<I>,
	I: 'static,
{
	// remember to reward relayers that have delivered messages
	// this loop is bounded by `T::MaxUnrewardedRelayerEntriesAtInboundLane` on the bridged chain
	let mut relayers_rewards: RelayersRewards<_, T::OutboundMessageFee> = RelayersRewards::new();
	for entry in messages_relayers {
		let nonce_begin = sp_std::cmp::max(entry.messages.begin, *received_range.start());
		let nonce_end = sp_std::cmp::min(entry.messages.end, *received_range.end());

		// loop won't proceed if current entry is ahead of received range (begin > end).
		// this loop is bound by `T::MaxUnconfirmedMessagesAtInboundLane` on the bridged chain
		let mut relayer_reward = relayers_rewards.entry(entry.relayer).or_default();
		for nonce in nonce_begin..=nonce_end {
			let key = MessageKey { lane_id, nonce };
			let message_data = OutboundMessages::<T, I>::get(key)
				.expect("message was just confirmed; we never prune unconfirmed messages; qed");
			relayer_reward.reward = relayer_reward.reward.saturating_add(&message_data.fee);
			relayer_reward.messages += 1;
		}
	}
	relayers_rewards
}

/// Ensure that the pallet is in normal operational mode.
fn ensure_normal_operating_mode<T: Config<I>, I: 'static>() -> Result<(), Error<T, I>> {
	if PalletOperatingMode::<T, I>::get() ==
		MessagesOperatingMode::Basic(BasicOperatingMode::Normal)
	{
		return Ok(())
	}

	Err(Error::<T, I>::NotOperatingNormally)
}

/// Creates new inbound lane object, backed by runtime storage.
fn inbound_lane<T: Config<I>, I: 'static>(
	lane_id: LaneId,
) -> InboundLane<RuntimeInboundLaneStorage<T, I>> {
	InboundLane::new(inbound_lane_storage::<T, I>(lane_id))
}

/// Creates new runtime inbound lane storage.
fn inbound_lane_storage<T: Config<I>, I: 'static>(
	lane_id: LaneId,
) -> RuntimeInboundLaneStorage<T, I> {
	RuntimeInboundLaneStorage {
		lane_id,
		cached_data: RefCell::new(None),
		_phantom: Default::default(),
	}
}

/// Creates new outbound lane object, backed by runtime storage.
fn outbound_lane<T: Config<I>, I: 'static>(
	lane_id: LaneId,
) -> OutboundLane<RuntimeOutboundLaneStorage<T, I>> {
	OutboundLane::new(RuntimeOutboundLaneStorage { lane_id, _phantom: Default::default() })
}

/// Runtime inbound lane storage.
struct RuntimeInboundLaneStorage<T: Config<I>, I: 'static = ()> {
	lane_id: LaneId,
	cached_data: RefCell<Option<InboundLaneData<T::InboundRelayer>>>,