Partnered With:

Gavin Wood shares the Polkadot cross-chain messaging scheme

Read this article in 26 Minutes

The cross-chain messaging scheme defines how messages can be passed between parallel chains in the absence of trust assumptions other than the security of Shared relay chains.

Text title: Polkadot's cross-chain messaging scheme (XCMP)
Source: PolkaWorld
作者：Fatemeh Shirazi、Logan Saether、Alistair Stewart、Rob Habermier、Gavin Wood

In recent months, the Web3 foundation research team has been working on a textual overview of cross-chain messaging (XCMP) capabilities. It is a key component of Polkadot, the Web3 foundation's flagship project. We are glad to share our work with you!

The cross-chain messaging (XCMP) scheme is a subset of the Polkadot protocol. It defines how messages can be passed between parallel chains without the assumption of trust other than the security of Shared relay chains. This article describes the parallel chain messaging protocol and relies heavily on Polkadot's unique relay chain architecture and design.

The agreement includes:

· in terms of consensus: message queuing and sorting mechanism.

· combined with other parts of the relay chain, especially GRANDPA's finalization mechanism: data availability.

· used in conjunction with parallel chain validation: message input and output.

In addition, this article reviews ideas for delivery, how to achieve a consistent history, and how to prevent DoS attacks. Finally, we reviewed XCMP in conjunction with SPREE and concluded by summarizing the features that XCMP implements.

Message semantics and network details, such as peer discovery, are not covered in this article.

introduce

One of the key features of Polkadot version 1.0 is to allow parallel chains that were originally isolated to send messages to each other in a secure and untrusted manner.

For this purpose, we define message in much the same way we define transaction. Both refer to data from outside the receiving chain, and both imply and require the chain to respond to the data in accordance with its internal logic. Given the latency level of the actual system, the chain cannot reject or confuse the data. In the context of bitcoin, for example, this property means that flawed or malicious miners in bitcoin cannot redistribute funds, so it is the basis of a good cryptographic economy consensus system.

The key difference between transaction and message is that a transaction contains a signature that certifies the source of the data (and thus the authority of the instruction). In the case of message, the source is only demonstrated by Polkadot's anti-byzantine cryptographic economy validation infrastructure, which is largely the same way messages are passed between eethernet contracts.

example

Before XCMP of each component will be discussed in detail, let's take an example, explain how to make A smart parallel chain is shown in figure 1 (A) of the contract on the outbound messages financial (DeFi) connected to A distributed parallel chain is shown in figure 1 (B) in the inbound queue, so that people (collator) collected from DeFi parallel chain into the next candidate block.

At block 300 of the relay chain, the smart contract parallel chain initiates a message to the endpoint of "32", which is the parallel chain ID of the DeFi parallel chain. Messages are first contained in the outbound or outbound queue of the smart contract parallel chain.

All nodes in the parallel chain of smart contracts will begin to gossip messages across the network (see the "passing" section below). If some of the nodes in the smart contract chain are also full nodes of the DeFi chain, and these nodes act as the glue between the two gossip networks by forwarding messages. If there are no network Shared nodes to traverse, the fallback mechanism is invoked (see the fallback section below).

Once the message reaches the collectors of the parallel DeFi chain, they receive it (and any other messages it receives) and enter it into the inbound or inbound queue for processing in its next candidate block.

Figure 1: shows the collector and full node corresponding to two parallel chains A and B. There are two nodes that are full nodes of parallel chain A network and parallel chain B network.

Collectors on the DeFi parallel chain will generate candidate blocks for the relay chain block 301. This candidate block will require proof that the message it executes from A's block is the correct message. The relay chain block 300 contains the parallel chain block header of the block in A, that is, A small amount of data including the message root hash that can be used to authenticate the message.

This candidate block will include the relay chain light client proof that this message root is in the relay chain and will be combined with the message sent by the sending chain.

The parallel chain verifier of the DeFi parallel chain will be able to use these proofs to verify the integrity of the proposed candidate block from the DeFi parallel chain. The original message of the smart contract chain is then contained in the DeFi parallel chain, with no additional nodes providing security and relying on Shared security from Polkadot.

Queue and sort messages

Each block in a parallel chain in Polkadot may generate an empty list of messages to send to other blocks. These lists are called egress queues. Once the message is sent, it enters the entry queue of the parallel chain. Parallel chains must process the entry list sequentially.

A collector or verifier attempts to collect messages for an exit queue of a parallel chain, calling the entry of the parallel chain and searching the propagation pool for related messages, waiting for messages that have not yet been gossiped about.

The message

Assume that each parallel chain has a full-node connection network. We assume that each complete node knows a subset of the other complete nodes in the system, which we call adjacent nodes. Note that we have no assumptions about the topology or diameter of these networks.

The simplest way to send a message is to use the gossip protocol. Recall that peers often communicate with each other about what they think of their current vacation. For more efficient delivery, unsent messages are delivered only to adjacent nodes with the same view.

If there are common nodes between the two networks, messages are propagated from one parallel chain network to another.

Figure 2: shows the messaging process done by gossip. Let's assume that this message is sent by the pink collator, which produces the latest parallel chain block.

Roll back the pass

However, if the receiver's parallel chain verifier realizes that the message is not being gossiped in the receiving parallel chain, they will request the message from the parallel chain verifier sending the parallel chain. Once they receive this information, they gossip about it in a network of receiving parallel links.

Figure 3: shows rollback passing when sending and receiving parallel chains do not share any full nodes.

The rollback delivery mechanism is shown in figure 3. We assume that parallel chain A wants to send messages to parallel chain C, which has no full nodes Shared with A. Once parallel chain C's parallel chain validators notice that the message has not yet arrived, they make a request to the sending parallel chain validator, who is responsible for saving the exit message from their parallel chain. Once the response to the request arrives, the verifier of parallel chain C will gossip in parallel chain C.

Obtain consistent historical records

One of the key features we hope to obtain from XCMP is the specification of parallel chain blocks, that is, those parallel chain blocks that we finally agree it has occurred. This means that in the current parallel-chain block, only messages that are sent from the parallel-chain block work, and these parallel-chain blocks themselves are both canonical and predated the current parallel-chain block.

Relay chains define the history of all parallel chains. For example, a block header from a parallel chain B in a relay chain block 301 can be said to act on all messages up to block 300. If applied to all messages prior to block 300, then applied to messages sent by blocks of parallel chain A, and only applied if A parallel chain block header appears in block 300 of the relay chain or earlier.

This means that the relay chain needs to play a role in validating messages. However, since we cannot place large amounts of data in these parallel chain block headers, the relay chain itself should not have the payload of the message. Instead, we effectively maintain a consistent history by using nested Merkle trees. The parallel chain block header corresponding to the sent message will contain a message root hash, the root of the Merkle tree. In turn, the Merkle tree leaf is the block head of the message hash chain from one parallel chain to another.

This means that there is a hash sequence containing each message hash that validates all sent messages from one parallel chain to another. This allows the collector to construct a proof of many hashes that they work on messages, and only on messages that they should work on, by first showing that the message roots are in the relay chain and then proving that these are messages from the root hash.

For more information on this topic, see:
https://research.web3.foundation/en/latest/polkadot/XCMP.html

Input and output validation

Recall that Polkadot consists of a trunk chain and multiple (tentatively up to 100) parallel chains.

The parallel chain block header contains the message root of the outgoing message. In order to generate parallel chain blocks on a parallel chain based on a particular relay chain block the collector needs to see which parallel chain heads are built between the relay chain block and the relay chain that includes the last parallel chain block header of the parallel chain. For these messages, parallel chains need to act on the corresponding message data.

Figure 4: shows the parallel chain blocks built for the three parallel chains A, B, and C in round 0, 1, and 2, and the messages sent in each of these parallel chains.

The chain state transition validation function (STVF) USES the validation function to verify that the input message is executed. The validation function, which is part of WebAssembly, checks that the state transitions of the parallel chains are actually valid. It associates the new state of the parallel chain and a set of output messages with the summary of the previous state of the parallel chain, the parallel chain block data, and a set of input messages that are accurately routed from other parallel chains or from the relay chain.

Figure 4 shows an example of the parallel chain blocks and messages generated between the three parallel chains A, B, and C for rounds 0, 1, and 2. Suppose parallel chain B does not produce any parallel chain blocks in round 0, and parallel chain C does not produce any parallel chain blocks in round 1. Parallel chain block B1 generated in round 1 needs to take message m1 as the input message and reply to parallel chain A by sending message m3 in round 1. The parallel chain block C1 generated in round 2 needs to get the messages m2 and m4 in its unprocessed entry queue.

Message availability

Once the messages are included in the exit queue, they are saved by the full nodes of the collector and the sending parallel chain. When the header of the sending parallel chain block is included in the relay chain, the parallel chain verifier will also retain the message. The collector and full node receiving the parallel chain also need to know the payload of the message sent between the parallel chains. All other entities that need to know that the message exists can only store hashes that can be used to validate the message.

To ensure availability, we require all verifiers to hold erasure-coded pieces that can recover any parallel-linked message. These erasure code fragments are generated and distributed by the parallel chain verifier that sends the parallel chain. One-third of the erasure code fragments were sufficient to recover all messages. Final confirmation requires that voters (verifiers) receive these erasure code snippets or they will be punished for voting. Therefore, two thirds of the erasure code segments must be available for final validation. From this we can ensure that the final message is also available.

DoS attack prevention

Note that the purpose of XCMP is not to specify a standard format for messages. However, there is a limit to the total size of messages sent by each parallel chain to another parallel chain. In addition, the gossip protocol USES boundary passing to avoid larger messages.

For parallel threads that do not often put blocks in the relay chain, unprocessed message queues can grow substantially. To limit this, sending parallel chains maintains an exit queue with a size limit for this chain. It can delete old messages only when it knows they have been received. The receiving chain publishes a watermark indicating how many blocks it has processed in the block of the parallel chain. The sending chain can use this watermark to streamline its exit queue.

In addition, we plan to make the receiving parallel chain able to prevent another parallel chain from sending a message (this capability is not yet implemented). Parallel threads can also disable XCMP functions to avoid processing large Numbers of messages.

XCMP and SPREE

SPREE (Shared Protected Runtime Execution Enclaves) are logical fragments similar to the Runtime module, but they are located on a trunk chain and can be selected for functionality by parallel chains.

These pieces of logic are WebAssembly code blocks that are uploaded to Polkadot through a governance mechanism or parallel chain. Once these pieces of logic are uploaded to Polkadot, all other parallel chains can decide to join the logic. The SPREE module will retain its own storage independent of the parallel chain, but can be invoked through an interface with the parallel chain. Parallel chains send messages synchronously to the SPREE module. For more information about SPREE, see its wiki article:

https://wiki.polkadot.network/docs/en/learn-spree。

These pieces of logic can address an XCMP message to a SPREE module, and guarantee that when you perform an operation on that message, it will use the same code from that SPREE module as any other parallel chain. SPREE modules are important to the overall XCMP architecture because they provide assurance of a specific interpretation of the code executed on a parallel chain of targets. While XCMP guarantees the delivery of the message, it does not guarantee the execution of the code that receives the parallel chain to interpret the message. Code updates to the SPREE module are synchronized with parallel chains. In addition to the security benefits, this means that you can change the message format without coordinating updates across multiple parallel chains.

In summary, although XCMP does the trusting of messaging, SPREE is a trusted interpretation of the message and a key part of the usefulness of XCMP. XCMP messages sent to the SPREE module give developers and users who schedule messages a clear idea of what to do with them.

XCMP attribute summary

XCMP scheme can implement the following properties:

De-trustworthiness: since the same set of validators ensure the security of one parallel chain with another while ensuring correct message delivery, the trust required for XCMP is no more than that required for a single blockchain.

Consistency: we provide absolute assurance that the message received is exactly the same as the message sent, even if there is any chain reconfiguration.

Validity: Polkadot ensures that messages are not lost and remain available. This is done by distributing erasure code snippets that can be used to reconstruct the message.

Maintain correct sequence: through input/output validation, it is ensured that the correct order of the output messages of the parallel chain blocks is maintained.

Efficiency: this protocol avoids too much bandwidth and allows messages to arrive as quickly as possible.

For more information about the Web3 foundation, visit web3.foundation.

To a deep understanding of the functions and features of Polkadot, please see our Wiki (https://wiki.polkadot.network/), we are constantly update and perfect it.

The original:https://medium.com/web3foundation/polkadots-messaging-scheme-b1ec560908b7

Translation: PolkaWorld

Source:weixin.qq.com