Polkadot’s Messaging Scheme (XCMP)

One of the key features of Polkadot “version 1.0” is to let its otherwise isolated parachains send messages between each other with guarantees and in a secure and trust-free manner. A message refers to data coming from outside of the receiving chain, and implies and requires that the chain acts on the data following the chain’s internal logic. Allowing for some level of delay typical for real-world systems, the chain cannot reject or confound the implications of the data. The key difference between a transaction and a message is that a transaction contains a signature to prove the provenance of the data (and thus the authority of the instructions), whereas with a message the provenance is proven merely by virtue of Polkadot’s internal Byzantine-resistant cryptoeconomic validation infrastructure, in much the same way as Ethereum’s inter-contract message passing. Let's take a look how Polkadot works and enables its messaging system.

What is Polkadot?

Polkadot is a next-generation blockchain protocol that unites an entire network of purpose-built blockchains, allowing them to operate seamlessly together at scale. Because Polkadot allows any type of data to be sent between any type of blockchain, it unlocks a wide range of real-world use cases. By bringing together the best features from multiple specialized blockchains, Polkadot paves the way for new decentralized marketplaces to emerge, offering fairer ways to access services through a variety of apps and providers.

Being a global network of blockchains and the foundation for a new, peer-to-peer Internet Polkadot makes it easier than ever to create and connect decentralized applications, services, and institutions. Polkadot is a network with a burgeoning ecosystem which always keeps pace with the most hi-tech technology in the evergrowing blockchain world.

How it works?

Polkadot utilises a central chain called the relay chain which communicates with multiple heterogeneous and independent sharded chains called parachains (portmanteau of parallel chains). The relay chain is responsible for providing shared security for all parachains, as well as trust-free interchain transactability between parachains. These chains connect also connect with external networks via bridges. In other words, the issues that Polkadot aims to address are those discussed above: interoperability, scalablility, and weaker security due to splitting the security power.

• Relay Chain is the heart of Polkadot, responsible for the network’s security, consensus and cross-chain interoperability.
• Parachains are sovereign blockchains that can have their own tokens and optimize their functionality for specific use cases. To connect to the Relay Chain, parachains can pay as they go or lease a slot for continuous connectivity.
• Bridges are special blockchains that allow Polkadot shards to connect to and communicate with external networks like Ethereum and Bitcoin

The security goal of Polkadot is to be Byzantine fault tolerant when the participants are rational and with the properties NPoS gives, the stakeholders elect a set of validators that has a more than 2/3 fraction of honest members.

Nominated Proof-of-Stake (NPoS)

The used consensus mechanism is called Nominated Proof-of-Stake (NPoS), which is very similar to Delegated Proof-of-Stake, of which we've already discussed. However, NPoS allows for an unlimited number of DOT holders (Polkadot token) to participate as nominators, who help maintain high levels of security by putting more value at stake. As such, NPoS is not only much more efficient than proof-of-work (PoW), but also considerably more secure than conventional forms of PoS such as DPoS.

A new set of validators is elected at the beginning of every era – a period during roughly one day - to serve for that era, according to the nominators’ preferences. More precisely, any DOT holder may choose to become a validator candidate or a nominator. Each candidate indicates the amount of stake he is willing to stake and his desired commission fee for operational costs. In turn, each nominator locks some stake and publishes a list with any number of candidates that she trusts. Then a public protocol, discussed below, takes these lists as input and elects the candidates with the most backing to serve as validators for the next era. Nominators share the rewards, or eventual slashings, with the validators they nominated on a per-staked-dot basis; Nominators are thus economically incentivised to act as watchdogs for the system, and they will base their preferences on parameters such as validators’ staking levels, commission fees, past performance, and security practices.

Nodes

Nodes which run Polkadot network assume different roles and functions that we introduce next.

• Validators: A validator is the highest in charge and helps seal new blocks on the Polkadot network. The validators role is contingent upon a sufficiently high bond being deposited and a validator must run a relay-chain client implementation with high availability and bandwidth. At each block the node must be ready to accept the role of ratifying a new block on some parachain, and may be required to double check a few more. This process involves receiving, validating and republishing candidate blocks. The parachain assignment is random and changes frequently. Since the validator cannot reasonably be expected to maintain a fully-synchronised database of all parachains, the task of devising a suggested new parachain block will be delegated to a third-party, known as a collator. Once all new parachain blocks have been properly ratified by their appointed validator subgroups, validators must then ratify the relay-chain block itself. This involves updating the state of the transaction queues (essentially moving data from a parachains output queue to another parachains input queue), processing the transactions of the ratified relay-chain transaction set and ratifying the final block, including the final parachain changes. A validator provably not fulfilling their role will be slashed i.e. part or all of their bond will be taken. In some sense, validators are similar to the mining pools of current PoW blockchains.
• Nominators: A nominator is a stake-holding party who contributes to the security bond of a validator. They have no additional role except to place risk capital and as such to signal that they trust a particular validator (or set thereof) to act responsibly in their maintenance of the network. They receive a pro-rata increase or reduction in their deposit according to the bonds growth to which they contribute. Together with collators, next, nominators are in some sense similar to the miners of the present-day PoW networks.
• Collators: Transaction collators (collators for short) are parties who assist validators in producing valid parachain blocks. They maintain a full-node for a particular parachain; meaning that they retain all necessary information to be able to author new blocks and execute transactions in much the same way as block producers do on current blockchains. Under normal circumstances, they will collate and execute transactions to create an unsealed block, and provide it, together with a proof of validity, to one or more validators presently responsible for proposing a parachain block.
• Fishermen: Unlike the other two active parties, fishermen are not directly related to the block-authoring process. Rather they are independent bounty hunters motivated by a large one-off reward. Precisely due to the existence of fishermen, the expected events of misbehaviour to seldom happen, and when they do only due to the bonded party being careless with secret key security, rather than through malicious intent. The name comes from the expected frequency of reward, the minimal requirements to take part and the eventual reward size. Fishermen get their reward through a timely proof that at least one bonded party acted illegally. This will be especially valuable for detecting the ratification of invalid parachain blocks.

Block Production

In outline, a collator produces a parachain block, sends it to the parachain validators, who sign its header as valid, and the header with enough signatures is placed on the relay chain. At this point, the parachain block is as canonical as the relay chain block its header appeared in. So when this relay chain block is finalised, so is the parachain block.

Because the parachain validators switch parachains frequently, they are stateless clients of the parachain. Thus there is a distinguishment between the parachain block B, which is normally enough for full nodes of the parachain such as collators to update the parachain state, and the Proof of Validity(PoV) block B_PoV , which a validator who does not have the parachain state can verify.

Any validator should be able to verify B_PoV given the relay chain state using the parachain’s state transition validation function (STVF), the Web assembly code for which is stored on the relay chain in a similar way to the relay chain’s runtime. The STVF takes as an input the PoV block, the header of the last parachain block from this parachain and a small amount of data from the relay chain state.

The STVF outputs the validity of the block, the header of this block and its outgoing messages. The PoV block contains any outgoing messages and the parachain block B. The parachain validators should gossip the parachain block to the parachain network, as a back up to the collator itself doing so.

The PoV block will be the parachain block, its outgoing messages, its header and light client proof witnesses. These witnesses are Merkle proofs that give all elements of the input and output state that are used or modified by the state transition from the input and output state roots.

VMP (Vertical Message Passing)

Polkadot implements two for acting on messages between its constituent parachains

• VMP (Vertical Message Passing)
• XCMP (Cross-Chain Message Passing)

There are two kinds of vertical message-passing transport protocols:

• UMP (Upward Message Passing): allows parachains to send messages to their relay chain.
• DMP (Downward Message Passing): allows the relay chain to pass messages down to one of their parachains.

Messages that are passed via DMP may originate from a parachain. In which case, first UMP is used to communicate the message to the Relay Chain and DMP is used to move it down to another parachain.

Cross-Chain Message Passing (XCMP)

XCMP allows the parachains to exchange messages with other parachains on the same Relay Chain. Cross-chain transactions are resolved using a simple queuing mechanism based around a Merkle tree to ensure fidelity. It is the task of the Relay Chain validators to move transactions on the output queue of one parachain into the input queue of the destination parachain. However, only the associated metadata is stored as a hash in the Relay Chain storage.

XCMP is the protocol that parachains use to send messages to each other. It aims to guarantee four things:

• that messages arrive quickly;
• that messages from one parachain arrive to another in order;
• that arriving messages were indeed sent in the finalised history of the sending chain;
• that recipients will receive messages fairly across senders, helping guarantee that senders never wait indefinitely for their messages to be seen.

There are two parts to XCMP.

• Metadata about outgoing messages for a parachain block are included on the relay chain and later this metadata is used to authenticate messages by the receiving parachain.
• The message bodies corresponding to this metadata need to be actually distributed from the senders to the recipients, together with a proof that the message body is actually associated with the relevant metadata.

The way relay chain blocks include headers of parachain blocks gives a synchronous notion of time for parachain blocks, just by relay chain block numbers. Additionally it allows to authenticate messages as being sent in the history given by the relay chain i.e. it is impossible that one parachain sends a message, then reorgs, so that that message was not sent, but has been received. This holds even though the system may not have reached finality over whether the message was sent, because any relay chain provides a consistent history.

Because parachains are required to act on every message eventually, non-delivery of a single message can potentially stop a parachain from being able to build blocks, therefore requiring enough redundancy for the message delivery system.

Any validators, who validate the PoV block, should keep any outgoing messages from that block available for a day or so and all full nodes of the sending parachain also store the outgoing messages until they know they have been acted on.

To achieve consistency, when a source parachain S sends messages in a parachain block B to a destination parachain D, then an authentication will be needed of these using the relay chain state, which is updated based on the parachain header P_H corresponding to the parachain block B that was included in the relay chain. There is a limit of the amount of data in headers like P_H, in the relay chain state and also to limit what the relay chain needs to do for authentication when processing such parachain headers.

To this end, the parachain header P_H contains a message root M of outgoing messages, as well as a bitfield indicating which other parachains were sent messages in this block. The message root M is the root of a Merkle tree of the head hash Hp of a hash chain for each parachain p that this block sends messages to. The hash chain with head HD has the hash of all messages sent to S from D, not just in block B but ever sent from S to D in any block up to block B. This allows many messages from S to D to be verified at once from M. However the messages themselves are passed, they should also be sent with the Merkle proof that allows nodes of the receiving parachain to authenticate that they were sent by a B whose header P_H was in a particular relay chain block.

Parachains receive incoming messages in order. Internally parachains may defer or reorder acting on messages according to their own logic. However they must receive messages in the order determined by the consistent history given by the relay chain. A parachain D always receives messages sent by parachain blocks whose header was in earlier relay chain blocks first. When several such source parachains have a header in the relay chain block, the messages from these parachains are received in some predetermined order of parachains - sequentially in order of increasing parachain id.

A parachain D receives all messages sent by one parachain S in one parachain block or none of them. A parachain header P_H0 of D contains a watermark, which consists of a block number of a relay chain block R and a parachain id of a source parachain S. This indicates that D has recieved all messages sent by all chains before relay chain block R, and has acted on messages sent in block R from parachains up to and including S in the ordering. The watermark must advance by at least one sending parachain in each of Ds parachain blocks, which means that the watermark’s relay chain block number advances or it stays the same and we only advance the parachain.

To produce a parachain block on parachain D which builds on a particular relay chain block R, a collator would need to look at which parachain headers were built reorganisation of the chain between the relay chain block that the last parachain block of this chain built on. In addition, it needs the corresponding message data for each of those that indicated that they sent messages to D. Thus it can construct a PoV block so that the STVF can validate that all such messages were acted on. Since a parachain must accept all messages that are sent to it, a method is implemented for parachains to make it illegal for another parachain to send it any messages that can be used in the case of spam occurring. When the parachain header of a parachain block that sends a message is included in a relay chain block, then any nodes connected to both the source and destination parachain networks should forward messages, together with their proofs, from sender to receiver. The relay chain should at least act as a back up: the receiving parachain validators of D are connected to D’s parachain network and if they do not receive messages on it, then they can ask for them from the parachain validators of the sending chain S at the time the message was sent.

The Anatomy of an XCMP Interaction

A smart contract that exists on parachain A will route a message to parachain B in which another smart contract is called that makes a transfer of some assets within that chain.Charlie executes the smart contract on parachain A, which initiates a new cross-chain message for the destination of a smart contract on parachain B.

The collator node of parachain A will place this new cross-chain message into its outbound messages queue, along with a destination and a timestamp. The collator node of parachain B routinely pings all other collator nodes asking for new messages (filtering by the destination field). When the collator of parachain B makes its next ping, it will see this new message on parachain A and add it into its own inbound queue for processing into the next block.

Validators for parachain A will also read the outbound queue and know the message. Validators for parachain B will do the same. This is so that they will be able to verify the message transmission happened.

When the collator of parachain B is building the next block in its chain, it will process the new message in its inbound queue as well as any other messages it may have found/received. During processing, the message will execute the smart contract on parachain B and complete the asset transfer as intended. The collator now hands this block to the validator, which itself will verify that this message was processed. If the message was processed and all other aspects of the block are valid, the validator will include this block for parachain B into the Relay Chain.

Overview

Finally, check out our animated video below that explores how XCMP works: