Crate pallet_mmr

Merkle Mountain Range

Overview

Details on Merkle Mountain Ranges (MMRs) can be found here: https://github.com/mimblewimble/grin/blob/master/doc/mmr.md

The MMR pallet constructs an MMR from leaf data obtained on every block from LeafDataProvider. MMR nodes are stored both in:

• on-chain storage - hashes only; not full leaf content;
• off-chain storage - via Indexing API we push full leaf content (and all internal nodes as well) to the Off-chain DB, so that the data is available for Off-chain workers. Hashing used for MMR is configurable independently from the rest of the runtime (i.e. not using frame_system::Hashing) so something compatible with external chains can be used (like Keccak256 for Ethereum compatibility).

Depending on the usage context (off-chain vs on-chain) the pallet is able to:

• verify MMR leaf proofs (on-chain)
• generate leaf proofs (off-chain)

See [primitives::Compact] documentation for how you can optimize proof size for leafs that are composed from multiple elements.

What for?

Primary use case for this pallet is to generate MMR root hashes, that can latter on be used by BEEFY protocol (see https://github.com/paritytech/grandpa-bridge-gadget). MMR root hashes along with BEEFY will make it possible to build Super Light Clients (SLC) of Substrate-based chains. The SLC will be able to follow finality and can be shown proofs of more details that happened on the source chain. In that case the chain which contains the pallet generates the Root Hashes and Proofs, which are then presented to another chain acting as a light client which can verify them.

Secondary use case is to archive historical data, but still be able to retrieve them on-demand if needed. For instance if parent block hashes are stored in the MMR it’s possible at any point in time to provide an MMR proof about some past block hash, while this data can be safely pruned from on-chain storage.

NOTE This pallet is experimental and not proven to work in production.

Re-exports

• pub use sp_mmr_primitives as primitives;
• pub use pallet::*;

Modules

• pallet
  The pallet module in each FRAME pallet hosts the most important items needed to construct this pallet.

Structs

• DefaultBlockHashProvider
  Default implementation of BlockHashProvider using frame_system.
• NodesUtils
  MMR nodes & size -related utilities.
• ParentNumberAndHash
  The most common use case for MMRs is to store historical block hashes, so that any point in time in the future we can receive a proof about some past blocks without using excessive on-chain storage.

Enums

• Error
  Merkle Mountain Range operation error.

Traits

• BenchmarkHelper
  This trait decoples dependencies on pallets needed for benchmarking.
• BlockHashProvider
  Block hash provider for a given block number.
• LeafDataProvider
  A provider of the MMR’s leaf data.
• WeightInfo

Functions

• verify_ancestry_proof
  Stateless ancestry proof verification.
• verify_leaves_proof
  Stateless MMR proof verification for batch of leaves.

Type Aliases

• LeafIndex
  A type to describe leaf position in the MMR.
• NodeIndex
  A type to describe node position in the MMR (node index).