Polkadot XCMP MMD — Minimal POC

Forum background: XCMP Design Discussion (Polkadot).

XCMP MMD - Design Document

Overview

XCMP MMD (Merkle Mountain Range based cross-chain messaging) is a proof-of-concept for trustless cross-chain message delivery between parachains. It uses a three-tier cryptographic proof system that leverages the relay chain’s BEEFY finality gadget and Merkle structures.

Problem Statement

HRMP (Horizontal Relay-routed Message Passing) stores message payloads on the relay chain, which is expensive in terms of storage and execution costs.

XCMP MMD replaces that with:

How MMD XCMP Replaces HRMP

HRMP approach:

MMD XCMP approach:

POC Semantics

This minimal POC has the following characteristics:

Design Rationale

This POC uses a single global append-only XcmpOutboxMmr that commits all outbound messages across all destinations. This differs from the forum sketch which proposed one XcmpMessageMMR per channel plus an XcmpChannelTree over those roots.

Benefits of the single global MMR approach:

Architecture

┌─────────────────────────────────────────────────────────────────┐
│                         Relay Chain                              │
│  ┌──────────────┐         ┌─────────────────┐                  │
│  │  BEEFY MMR   │────────▶│ ParaHeadsRoot   │                  │
│  │  (pallet-mmr)│         │ (Merkle tree)   │                  │
│  └──────────────┘         └─────────────────┘                  │
│         │                          │                             │
│         │ Proof 1                  │ Proof 2                    │
│         ▼                          ▼                             │
└─────────────────────────────────────────────────────────────────┘
          │                          │
          │                          │
┌─────────▼──────────┐      ┌───────▼────────────┐
│  Source Para 1000  │      │  Dest Para 2000    │
│                    │      │                     │
│  ┌──────────────┐  │      │  ┌──────────────┐  │
│  │ Outbox MMR   │  │      │  │ Inbox Pallet │  │
│  │ (messages)   │  │      │  │ (verifier)   │  │
│  └──────────────┘  │      │  └──────────────┘  │
│         │          │      │                     │
│         │ Proof 3  │      │                     │
│         ▼          │      │                     │
│  ┌──────────────┐  │      │                     │
│  │ xmmd digest  │  │      │                     │
│  │ in header    │  │      │                     │
│  └──────────────┘  │      │                     │
└────────────────────┘      └─────────────────────┘
         │                           ▲
         │                           │
         └───────────────────────────┘
                  Relayer
           (off-chain proof builder)

Three-Tier Proof System

The system uses three nested proofs to establish a chain of trust from the destination parachain back to the source parachain’s committed messages.

Tier 1: Relay MMR Proof

Purpose: Prove that a relay chain block containing the source parachain’s header is finalized by BEEFY.

How it works:

  1. The relay chain maintains a Merkle Mountain Range (MMR) of all blocks via pallet-mmr
  2. BEEFY validators sign MMR roots, providing finality guarantees
  3. Each BEEFY MMR leaf contains a ParaHeadsRoot in its leaf_extra field
  4. The relayer fetches an MMR proof for a specific relay block (the “MMR leaf block”)
  5. The destination parachain verifies this proof against the relay MMR root cached in LatestRelayMmr

Destination Anchor (LatestRelayMmr) Mechanism:

In practice the destination is not guaranteed to author a block at every relay height (e.g. a coretime on-demand parachain). The inbox therefore cannot assume it can verify against an arbitrary historical relay context; it can only verify against relay information it has actually cached at execution time.

The mechanism is:

Data structure:

Security: Relies on BEEFY finality - if 2/3+ validators signed the MMR root, the relay block is finalized. Cached roots are read from the relay state proof, ensuring trustless verification.

Tier 2: Para-heads Merkle Proof

Purpose: Prove that the source parachain’s header is included in the ParaHeadsRoot from Tier 1.

How it works:

  1. The relay chain builds a binary Merkle tree of all parachain headers each block
  2. Leaves are SCALE((para_id: u32, head_bytes: Vec<u8>)) sorted by para_id
  3. The tree root is stored in the BEEFY MMR leaf as ParaHeadsRoot
  4. The relayer reconstructs the Merkle proof by fetching all para heads from relay state
  5. The destination parachain verifies the source header is in the tree

Data structure:

Security: If the header is in the ParaHeadsRoot, and the ParaHeadsRoot is in the finalized BEEFY MMR, then the header is finalized.

Tier 3: Outbox MMR Proof

Purpose: Prove that a specific message is committed in the source parachain’s outbox MMR.

How it works:

  1. The source parachain maintains an MMR of all outbound messages via pallet-xcmp-mmd-outbox
  2. Each message is hashed and appended to the MMR as a leaf
  3. The MMR root is deposited in the block header as a DigestItem::Other(b"xmmd" ++ SCALE(XcmpMmdDigest)) digest
  4. The relayer calls a runtime API to generate a proof for a specific message
  5. The destination parachain extracts the MMR root from the verified source header (Tier 2) and verifies the message proof

Data structure:

Security: If the message is in the outbox MMR, and the MMR root is in the finalized source header, then the message was committed by the source parachain.

BEEFY and Relay Chain Dependencies

BEEFY MMR Implementation

The relay chain’s pallet_beefy_mmr is configured with:

This defines the exact proof format and hashing that the inbox verifier must match.

Relay MMR Root Access

The destination parachain obtains the relay MMR root trustlessly via:

  1. Trust anchor: ValidationData.relay_parent_storage_root (already verified in set_validation_data)
  2. Storage key: pallet_mmr::RootHash at twox_128("Mmr") ++ twox_128("RootHash")
  3. Collator integration: Runtime implements KeyToIncludeInRelayProof to include this key in the inherent relay proof
  4. Verification: Inbox pallet reads the value from RelayChainStateProof (no extra proof in extrinsic)

Important: The storage key must match the relay runtime’s pallet name (e.g., “Mmr” on Westend).

Data Availability

On-chain commitment: Only payload_hash = Keccak256(payload) is committed to the outbox MMR.

POC payload availability (current code): The outbox pallet emits the full payload bytes in an event (XcmpMmdOutbox::MessageCommitted) and does not store them in state. The outbox runtime API returns the proof (and committed_at), while relayers fetch the payload bytes from events. This keeps the end-to-end flow working without relying on legacy HRMP storage.

Cryptographic binding: The hash commitment is on-chain. In this PoC, payload bytes are emitted in an on-chain event (not stored in state), and are retrieved off-chain via RPC/indexing; long-term availability depends on node history/archival rather than on-chain storage.

Message Flow

1. Message Commitment (Source Parachain)

User submits XCM
    ↓
XcmpQueue enqueues message
    ↓
XcmpMmdOutbox wraps XcmpQueue
    ↓
On block finalization:
  - Hash message payload
  - Create OutboxLeaf { dest, payload_hash }
  - Append to outbox MMR
  - Deposit xmmd digest in header

2. Proof Construction (Off-chain Relayer)

Monitor source finalized headers
    ↓
Poll outbox leaf count (`XcmpMmdOutboxApi::mmr_leaf_count`)
    ↓
For each new leaf index:
  - Call `XcmpMmdOutboxApi::generate_outbox_proof`
    - gets `(leaf, proof, mmr_size, committed_at)`
    ↓
Find relay block containing source header
  - Scan relay chain for matching para head
    ↓
Read destination anchor from storage
  - Read destination `LatestRelayMmr` (single `(relay_parent, mmr_root)`)
    ↓
Build Tier 1 proof (relay MMR)
  - Ensure anchor is high enough (roughly \(A \ge B+1\) for inclusion at relay block \(B\))
  - Call mmr_generateProof RPC (anchored at cached block)
  - Extract ParaHeadsRoot from BEEFY leaf
    ↓
Build Tier 2 proof (para-heads Merkle)
  - Fetch all para heads from relay state
  - Reconstruct Merkle proof
    ↓
Assemble MessageWithProof
  - Set relay_ancestry_proof to None
    ↓
Sign and submit to destination

3. Verification (Destination Parachain)

Receive submit_xcmp_mmd(MessageWithProof)
    ↓
Read LatestRelayMmr (cached relay parent + MMR root)
    ↓
Verify Tier 1 (relay MMR proof)
  - Verify against **cached** relay MMR root from `LatestRelayMmr`
  - Extract ParaHeadsRoot from BEEFY leaf
    ↓
Verify Tier 2 (para-heads Merkle proof)
  - Verify source header is in ParaHeadsRoot
    ↓
Extract outbox MMR root from source header digest
    ↓
Verify Tier 3 (outbox MMR proof)
  - Verify message leaf is in outbox MMR
    ↓
Verify payload hash matches
    ↓
Check message not already seen (replay protection)
    ↓
Dispatch message to XcmpQueue

Components

Outbox Pallet (Source Parachain)

Role: Commit outbound messages to an MMR and publish the root in block headers.

Key features:

Storage:

Inbox Pallet (Destination Parachain)

Role: Verify three-tier proofs and dispatch verified messages.

Key features:

Storage:

Relayer (Off-chain)

Role: Monitor source parachains and construct proofs for destination parachains.

Key features:

Architecture:

Technical Specifications

Hard Bounds

The POC enforces the following limits:

These bounds ensure:

Data Structures

OutboxLeaf:

struct OutboxLeaf {
    dest: u32,              // Destination para ID
    payload_hash: H256,     // Keccak256(payload)
}

XcmpMmdDigest:

struct XcmpMmdDigest {
    version: u8,
    root: H256,             // Outbox MMR root
}
// Deposited as: DigestItem::Other(b"xmmd" ++ SCALE(digest))

MessageWithProof:

struct MessageWithProof {
    source: ParaId,
    dest: ParaId,
    mmr_leaf_index: u64,
    relay_mmr_leaf_index: u64,
    payload: Vec<u8>,
    
    // Tier 1: Relay MMR proof
    relay_mmr_proof: Vec<H256>,
    relay_mmr_leaf: Vec<u8>,        // BEEFY MMR leaf
    relay_mmr_size: u64,
    relay_ancestry_proof: Option<AncestryProof<H256>>,
    
    // Tier 2: Para-heads Merkle proof
    para_heads_proof: Vec<H256>,
    source_head: Vec<u8>,           // Source header bytes
    para_head_index: u32,
    para_heads_count: u32,
    
    // Tier 3: Outbox MMR proof
    outbox_leaf: OutboxLeaf,
    outbox_mmr_proof: Vec<H256>,
    outbox_mmr_size: u64,
}

Hashing and Encoding

Verification Guards

The inbox pallet enforces:

Security Properties

Trustlessness

The destination parachain does not trust:

Replay Protection

Messages are identified by (source_para_id, mmr_leaf_index). Once processed, the inbox pallet rejects duplicate submissions.

Finality

Messages are only delivered after:

  1. Source parachain block is finalized (included in relay chain)
  2. Relay chain block is finalized (BEEFY signatures)
  3. Proofs are verified on destination

Censorship Resistance

Anyone can run a relayer. If one relayer fails or censors messages, others can submit the same proof.

Performance Characteristics

Latency

Typical message delivery time: 30-45 seconds

Breakdown:

Proof Size

Approximate sizes:

Scalability

Bottlenecks:

Optimizations:

Comparison to Alternatives

vs. Validator-based XCMP

Advantages:

Disadvantages:

vs. Light Client Bridges

Advantages:

Disadvantages:

Future Improvements

  1. Batch multiple messages in one proof
  2. WebSocket subscriptions instead of polling
  3. Persistent relayer state (database)
  4. Retry logic and error handling
  5. Economic incentives for relayers (fee mechanism)
  6. Proof compression (aggregate signatures, state proof compression)
  7. Parallel proof construction (multiple relayers)

References