XCMP: Cross Chain Message Passing

[gavofyork]

A tracking issue for the progress towards XCMP implementation across all associated repos.

The workload may be broken down into:

• Runtime logic (parachain side)
  • Proof-of-post inherents.
  • Verification of proof-of-post, including message-queue chain, ingress buffering, watermarks.
  • Partial proof caching (low-priority, optimisation).
  • Ingress message processing: splitting, buffering and dispatching.
  • Egress post API, aggregation, storage and cleanup.
  • Egress message queue chain building.
• Runtime logic (relay-chain side)
  • Channels API: connect/accept creation, closure, fees, parachain-freebies.
  • Channel state table: updates from attestations, Merkle root builder.
  • Watermarks (should be (BlockNumber, ParaId) so that it can move by a single sender in a single block).
• Client logic (parachain side)
  • Proof-of-post generation (CST item -> MQC head, MQC head -> MQC item).
  • Networking service to provide proofs as required.
  • Integration of relay-chain proof generation and remote parachain proof generation into inherent.
  • Transport of message preimage blobs.
• Client logic (relay-chain side)
  • Proof-generation (Relay State root -> CSTR root, CSTR root -> CST item).

Message Queue Chain

A simple hash chain which tracks the messages (specifically their hashes) that are sent between one specific source ParaId to one specific destination ParaId. Its blocks are the triple:

• parent_hash: Hash: the hash of the encoded parent triple or the null/default hash in the cash of no parent.
• message_hash: Hash: the hash of the message sent.
• number: BlockNumber: the block number when the parent's message was sent.

The chain as a whole is not stored as blocks in this format anywhere: rather it is constructed on-demand for use in proofs. The head of the chain for each channel is stored on the Relay chain in the Channel State Table.

The tail of this chain is stored on-chain as (BlockNumber, Hash), which gives the hash of the most recent discarded item of the chain together with the block number at which the message contained in it was sent. This allows the head to be generated on-demand without needing the full history of the chain. The head is formed from that tail together with the active items in the outgoing queue.

By knowing some item in the MQC, it is possible to succinctly verify a proof that, up until that item, either some message or messages were sent following a particular block number, or that no further message was sent after a particular block.

Channel State Table

The CST is a construct that exists within the Relay-chain's state and tracks the latest sender message queue roots. Its items are ChannelStates, which contain two fields:

• sender_message_queue_merkle_root: Hash: The Merkle root of the trie containing all current MQC heads across the channels that it sends in.
• block_number: BlockNumber: the Relay-chain block number at the time that this item was last updated.

The CST items are stored in rows, where all items share the same sender. They are paired with the target's ParaId into a storage map. A second storage item contains a Merkle root of each row.

map ChannelStateTable ParaId => Vec<(ParaId, ChannelState)>;
map ChannelStateTableRoots ParaId => Hash;

The Merkle root is computed whenever the row changes and the trie nodes are not retained in any way. It exists only for providing a proof of MQC head of a particular channel given knowledge of a storage root of the Relay-chain.

Proof-of-post inherents

Inherent extrinsics passed in to the parachain runtime that provide full proofs that a particular message was sent from a para to us at a previous block number. The proof is based on only the current relay state root, which should be known by the destination parachain runtime. A watermark, stored locally, retains the pair (BlockNumber, ParaId) which is the last processed message. Senders are iterated in lexical ordering, thus older blocks are first processed and in the case of two messages from the same block, lower ParaId senders are processed first. The watermark must be change to a strictly higher value every block (though it may only be the ParaId component which changes).

The proof contains five parts; some may be omitted in the case that they are cached from previous blocks in the parachain's state:

• A proof taking the relay chain state root (which should be known to us already) to derive a storage item holding the Merkle root of all items in a single row (same sender) of the Channel State Table (CST).
• A proof deriving the contents of a specific item (i.e. a specific sender/target) in the CST from the CST root.
• A proof deriving the Message Queue Chain's head-triple from the the CST item.
• A proof deriving the historical MQC's item-triple from the MQC head-triple.
• The original message, which is a preimage to the hash contained in the MQC item-triple.