fn block_hash(block_number: BlockNumberFor<T>) -> T::Hash {

		frame_system::Pallet::<T>::block_hash(block_number)

	}

#[frame_support::pallet]

pub mod pallet {

	use super::*;

	use frame_support::pallet_prelude::*;

	pub struct Pallet<T, I = ()>(PhantomData<(T, I)>);

	/// This pallet's configuration trait

	#[pallet::config]

	pub trait Config<I: 'static = ()>: frame_system::Config {

		/// Prefix for elements stored in the Off-chain DB via Indexing API.

		///

		/// Each node of the MMR is inserted both on-chain and off-chain via Indexing API.

		/// The former does not store full leaf content, just its compact version (hash),

		/// and some of the inner mmr nodes might be pruned from on-chain storage.

		/// The latter will contain all the entries in their full form.

		///

		/// Each node is stored in the Off-chain DB under key derived from the

		/// [`Self::INDEXING_PREFIX`] and its in-tree index (MMR position).

		const INDEXING_PREFIX: &'static [u8];

		/// A hasher type for MMR.

		///

		/// To construct trie nodes that result in merging (bagging) two peaks, depending on the

		/// node kind we take either:

		/// - The node (hash) itself if it's an inner node.

		/// - The hash of SCALE-encoding of the leaf data if it's a leaf node.

		///

		/// Then we create a tuple of these two hashes, SCALE-encode it (concatenate) and

		/// hash, to obtain a new MMR inner node - the new peak.

		type Hashing: traits::Hash;

		/// Data stored in the leaf nodes.

		///

		/// The [LeafData](primitives::LeafDataProvider) is responsible for returning the entire

		/// leaf data that will be inserted to the MMR.

		/// [LeafDataProvider](primitives::LeafDataProvider)s can be composed into tuples to put

		/// multiple elements into the tree. In such a case it might be worth using

		/// [primitives::Compact] to make MMR proof for one element of the tuple leaner.

		///

		/// Note that the leaf at each block MUST be unique. You may want to include a block hash or

		/// block number as an easiest way to ensure that.

		/// Also note that the leaf added by each block is expected to only reference data coming

		/// from ancestor blocks (leaves are saved offchain using `(pos, parent_hash)` key to be

		/// fork-resistant, as such conflicts could only happen on 1-block deep forks, which means

		/// two forks with identical line of ancestors compete to write the same offchain key, but

		/// that's fine as long as leaves only contain data coming from ancestors - conflicting

		/// writes are identical).

		type LeafData: primitives::LeafDataProvider;

		/// A hook to act on the new MMR root.

		///

		/// For some applications it might be beneficial to make the MMR root available externally

		/// apart from having it in the storage. For instance you might output it in the header

		/// digest (see [`frame_system::Pallet::deposit_log`]) to make it available for Light

		/// Clients. Hook complexity should be `O(1)`.

		type OnNewRoot: primitives::OnNewRoot<HashOf<Self, I>>;

		/// Block hash provider for a given block number.

		type BlockHashProvider: BlockHashProvider<

			BlockNumberFor<Self>,

			<Self as frame_system::Config>::Hash,

		>;

		/// Weights for this pallet.

		type WeightInfo: WeightInfo;

	}

	/// Latest MMR Root hash.

	pub type RootHash<T: Config<I>, I: 'static = ()> = StorageValue<_, HashOf<T, I>, ValueQuery>;

	/// Current size of the MMR (number of leaves).

	#[pallet::getter(fn mmr_leaves)]

	pub type NumberOfLeaves<T, I = ()> = StorageValue<_, LeafIndex, ValueQuery>;

	/// Hashes of the nodes in the MMR.

	///

	/// Note this collection only contains MMR peaks, the inner nodes (and leaves)

	/// are pruned and only stored in the Offchain DB.

	#[pallet::getter(fn mmr_peak)]

	pub type Nodes<T: Config<I>, I: 'static = ()> =

		StorageMap<_, Identity, NodeIndex, HashOf<T, I>, OptionQuery>;

	impl<T: Config<I>, I: 'static> Hooks<BlockNumberFor<T>> for Pallet<T, I> {

			use primitives::LeafDataProvider;

				log::error!(target: "runtime::mmr", "MMR push failed");

				return T::WeightInfo::on_initialize(peaks_before)

			// Update the size, `mmr.finalize()` should also never fail.

				Err(e) => {

					log::error!(target: "runtime::mmr", "MMR finalize failed: {:?}", e);

					return T::WeightInfo::on_initialize(peaks_before)

				},

			};

	}

}

pub fn verify_leaves_proof<H, L>(

	root: H::Output,

	leaves: Vec<mmr::Node<H, L>>,

	proof: primitives::LeafProof<H::Output>,

) -> Result<(), primitives::Error>

where

	H: traits::Hash,

	L: primitives::FullLeaf,

{

	let is_valid = mmr::verify_leaves_proof::<H, L>(root, leaves, proof)?;

	if is_valid {

		Ok(())

		Err(primitives::Error::Verify.log_debug(("The proof is incorrect.", root)))

}

pub fn verify_ancestry_proof<H, L>(

	root: H::Output,

	ancestry_proof: primitives::AncestryProof<H::Output>,

) -> Result<H::Output, Error>

where

	H: traits::Hash,

	L: primitives::FullLeaf,

{

	mmr::verify_ancestry_proof::<H, L>(root, ancestry_proof)

		.map_err(|_| Error::Verify.log_debug(("The ancestry proof is incorrect.", root)))

}

	fn node_canon_offchain_key(pos: NodeIndex) -> Vec<u8> {

		NodesUtils::node_canon_offchain_key(&T::INDEXING_PREFIX, pos)

	}

	fn leaf_index_to_parent_block_num(leaf_index: LeafIndex) -> BlockNumberFor<T> {

		// leaves are zero-indexed and were added one per block since pallet activation,

		// while block numbers are one-indexed, so block number that added `leaf_idx` is:

		// `block_num = block_num_when_pallet_activated + leaf_idx + 1`

		// `block_num = (current_block_num - leaves_count) + leaf_idx + 1`

		// `parent_block_num = current_block_num - leaves_count + leaf_idx`.

		<frame_system::Pallet<T>>::block_number()

			.saturating_sub(Self::mmr_leaves().saturated_into())

			.saturating_add(leaf_index.saturated_into())

	}

	fn block_num_to_leaf_index(block_num: BlockNumberFor<T>) -> Result<LeafIndex, Error>

	where

		T: frame_system::Config,

	{

		let first_mmr_block = utils::first_mmr_block_num::<HeaderFor<T>>(

			<frame_system::Pallet<T>>::block_number(),

			NumberOfLeaves::<T, I>::get(),

		)?;

		utils::block_num_to_leaf_index::<HeaderFor<T>>(block_num, first_mmr_block)

	}

	pub fn block_num_to_leaf_count(block_num: BlockNumberFor<T>) -> Result<LeafIndex, Error>

	where

		T: frame_system::Config,

	{

		let leaf_index = Self::block_num_to_leaf_index(block_num)?;

		Ok(leaf_index.saturating_add(1))

	}

	pub fn generate_proof(

		block_numbers: Vec<BlockNumberFor<T>>,

		best_known_block_number: Option<BlockNumberFor<T>>,

	) -> Result<(Vec<LeafOf<T, I>>, primitives::LeafProof<HashOf<T, I>>), primitives::Error> {

		// check whether best_known_block_number provided, else use current best block

		let best_known_block_number =

			best_known_block_number.unwrap_or_else(|| <frame_system::Pallet<T>>::block_number());

		let leaf_count = Self::block_num_to_leaf_count(best_known_block_number)?;

		let leaf_indices = block_numbers

			.iter()

			.map(|block_num| -> Result<LeafIndex, primitives::Error> {

				Self::block_num_to_leaf_index(*block_num)

			})

			.collect::<Result<Vec<LeafIndex>, _>>()?;

		let mmr: ModuleMmr<mmr::storage::OffchainStorage, T, I> = mmr::Mmr::new(leaf_count);

		mmr.generate_proof(leaf_indices)

	}

	pub fn verify_leaves(

		leaves: Vec<LeafOf<T, I>>,

		proof: primitives::LeafProof<HashOf<T, I>>,

	) -> Result<(), primitives::Error> {

		if proof.leaf_count > NumberOfLeaves::<T, I>::get() ||

			proof.leaf_count == 0 ||

			proof.items.len().saturating_add(leaves.len()) as u64 > proof.leaf_count

			return Err(primitives::Error::Verify

				.log_debug("The proof has incorrect number of leaves or proof items."))

		}

		let mmr: ModuleMmr<mmr::storage::OffchainStorage, T, I> = mmr::Mmr::new(proof.leaf_count);

		let is_valid = mmr.verify_leaves_proof(leaves, proof)?;

		if is_valid {

			Ok(())

			Err(primitives::Error::Verify.log_debug("The proof is incorrect."))

	}

	pub fn generate_ancestry_proof(

		prev_block_number: BlockNumberFor<T>,

		best_known_block_number: Option<BlockNumberFor<T>>,

	) -> Result<primitives::AncestryProof<HashOf<T, I>>, Error> {

		// check whether best_known_block_number provided, else use current best block

		let best_known_block_number =

			best_known_block_number.unwrap_or_else(|| <frame_system::Pallet<T>>::block_number());

		let leaf_count = Self::block_num_to_leaf_count(best_known_block_number)?;

		let prev_leaf_count = Self::block_num_to_leaf_count(prev_block_number)?;

		let mmr: ModuleMmr<mmr::storage::OffchainStorage, T, I> = mmr::Mmr::new(leaf_count);

		mmr.generate_ancestry_proof(prev_leaf_count)

	}

	pub fn verify_ancestry_proof(

		root: HashOf<T, I>,

		ancestry_proof: primitives::AncestryProof<HashOf<T, I>>,

	) -> Result<HashOf<T, I>, Error> {

		verify_ancestry_proof::<HashingOf<T, I>, LeafOf<T, I>>(root, ancestry_proof)

	}

	pub fn mmr_root() -> HashOf<T, I> {

		RootHash::<T, I>::get()

	}