Polkadot｜茶溪岸啤（XCMP），再来一杯！

导读：上一篇文章Polkadot 茶溪岸啤（XCMP），干杯！主要介绍了XCMP一些基本内容，还有XCMP消息路由方式。

「总体而言，XCMP主要分为2部分：XCMP消息的分发、XCMP消息的存取」，本文主要就是介绍XCMP消息的存取。

XCMP消息的存取

当接收链接收到消息后，接下去要进行的流程是：处理消息，然后将消息及相关证明放进新块构建好后交给验证人，并最终确认出块。这个流程是比较复杂的，涉及到的新数据结构也很多。

先来看看一些接下去要用到名词的解释：

Para X

表示平行链X或者平行线程X。

因为平行链要接入Polkadot需要购买一个专用插槽Slot，Slot数量少且贵，所以更精益的方式是使用平行线程。平行线程接入Polkadot不需要专门购买一个Slot，而是按块付费。平行线程与平行链在开发上基本上一样，而且也能使用Polkadot的各种功能。

平行链

当我们说平行链的时候，其实是指由平行链收集人节点构成的区块链网络。如果提到了验证人，一般会专门指出这是验证人节点。

好，接下去我们借助一张看起来有点复杂、但其实比较清晰的图来讲解XCMP消息的存取。

上图是我们自己总结的XCMP消息存取的全景图，基本上概括了XCMP消息存取的全部内容。

图中描述了Para B要给Para A发送消息 m2020。虽然Para还可能表示平行线程，但接下去以平行链为例（平行线程也是类似的）来解释这张图，阐述XCMP的消息存取流程。

在平行链B要向平行链A发送XCMP消息前，首先要开一个链B通向链A的通道（Channel），然后接下去的流程是：

1. 平行链B发出消息 m2020（放至出口队列），并在新出的块 （假设为#3号块） 中包含了此消息。

2. 平行链B作为发送链，会维护对每个接收链的一条MQHC（Message Queue Hash Chain），可以看成是一种链表（如图中，平行链B到A、C、D、E都建立了通道并发送过跨链消息，所以平行链B有4条MQHC）。

1. MQHC链的每个元素对应于一条跨链消息，元素的结构是一个三元组（parent_hash、message_hash、block_number）。parent_hash是该元素的父元素的哈希，message_hash跨链消息的哈希，block_number是父元素消息发出时的中继链区块号（可以当做全局时间来用）。
2. 平行链B的所有MQHC（这里是4条）的链表头元素会作为Merkle树的叶节点从而构成一棵树，树根是Message Root，简称MR。MR具有非常牛逼的作用。如果你有了MR，再加上到某个MQHC元素的Merkle路径，就能验证MQHC上的元素，再加上发送链的消息队列里的消息原文，你就能验证所有已经发送、但没有被处理的所有消息。
3. MR会存储到平行链B的区块头里（这里刚好是#3号块的区块头）。#3号块的区块头除了有MR，还有bitfield、watermark这两个也是和XCMP相关的数据。
4. bitfield是一个位域数组，每一位的含义是发送链对该位表示的接收链在本块中是否发送了跨链消息。假设bitfield 的1-4位表示链B对链A、C、D、E的跨链消息发送情况，则区块头里的bitfield =1111说明这个区块包含了对这四条链的跨链消息。
5. watermark可以理解为跨链消息的序号，不过这个序号不是一维的，而是二维的， watermark的结构为（block_number，para_id），block_number中继链的区块号，para_id是平行链的id。两个watermark组成的区间就可以确定一个消息集合，比如，若w1=(100,A)，w2=(300,A)，则区间[w1,w2) 表示在中继链#100号区块到#300号区块这段时间里，链B对para_id=A的这条链发送的所有消息。

3. 当平行链B将消息m2020包含进区块并最终被验证人验证确认后，其区块头会存储到中继链的区块中（如本例中B的#3号区块头）。这样一来，中继链就拿到了链B的#3号块的MR，bitfield、watermark三个关键数据结构。根据这三个数据结构，中继链就会做一些有趣的事情。

4. 中继链上有一个数据结构叫做CST（Channel State Table），中继链于是会使用该新提交的平行链区块头里的MR去更新自己的CST里相应的一行。

1. CST的作用是跟踪某条发送链对某条接收链所发送的消息的状态，从而提供某个通道的MQHC的链表头的证明（proof）。
2. CST作为一张表，其行标是发送链的ID，列标是接收链的ID，每个表项其实可以表示一个通道，表项的结构是一个二元组（sender_mr，block_number），易知通过表项的block_number +列对应的para_id可以得出watermark。sender_mr表示该通道的最新mr，block_number为该表项上次更新时的中继链区块号。
3. CST其实是按行来进行存储的，一行中会有很多表项；因为是同一行所以这些表项的发送链都相同；而因为发送链都相同，同行的表项里的最新MR也都相同。因此当新的平行链区块头到来时，CST是按行进行更新的。
4. CST其实除了一张表外，还有第二部分是映射（para_id => row_root）。row_root是CST的行里的表项构成的Merkle树的树根。这样，某一行只要有一个表项变化了，其row_root就会变化。
5. row_root会作为叶子继续构出一棵Merkle树，其根为XCMP_Root，其会关联至中继链的状态根（State Root）。

5. 当平行链A开始构建新PoV区块时，将会需要其所有消息的proof。

1. 链A需向中继链获取：以A为发送链的MR的light client proof，以A为接收链的所有通道的watermark的light client proof，而且这些proof需要同时构建，这样这些proof都能基于中继链的同一个State Root；light client proof是通过Merkle proof转化而成的。
2. 因为中继链状态根（State Root）路径到CST的表项其实要分2部分，先从State Root到row_root，再从row_root到表项。所以从State Root到表项里的MR的整个Merkle proof被称为「Nested Proof」。
3. 某个通道的最新消息根MR可以通过中继链能够获取，MR的作用在前面提到过，MR 、MQHC链表头的Merkle root、MQHC、对应消息的原文这四样东西能验证这个通道目前未被处理的消息。这样，本次构建区块就会把目前还没有处理的消息都处理下。
4. 因此，链A还需要所有消息的从MR到MQHC元素的merkle root，以及消息的原文。
5. 这样，包含消息哈希的MQHC元素——消息根MR ——MR构成的CST表项—— CST的row_root ——State Root，就能整合成一个总的proof，从中继链状态根State Root到跨链消息的哈希。
6. 最后PoV区块里需要包含内容有：所有的消息原文，及其对应的MQHC元素，及其整个的proof。

另外还有一些细节：

1）平行链的状态里不光要存储MQHC的链表头的Merkle proof，还要存储MQHC所有元素的Merkle proof（它们也曾当过链表头）。

2）如果确认消息被执行，则MQHC里的链表可以丢弃已经执行过的消息的对应元素（但不一定要求立即丢弃，因为可以多存一会起到冗余的作用）。

对上面第5点——平行链PoV区块的构造，Polkadot官网上有一个简例。

以上面这张图中的链B为例。链B给链A发送了跨链消息，且通过Channel State Table可知，链A上一次处理链B发过来的消息的时间是中继链块号位rc_1的时候，上一次的watermark1为（rc_1, A），而当前的watermark2为（rc_6, A）。

假设链A要出新块，其要把[watermark1,watermark2) 之间的跨链消息都进行处理。链A出块需要的数据有（以下的1、2、3就是构成整个的proof）：

1) 中继链State Root到CST row_root的Merkle proof（红色部分）；

2) CST row_root到 (MR，block_number) 构成的表项的Merkle proof（蓝色部分）；

3) MR到MQHC链表头的Merkle proof（橙色部分）；

4) 所有消息对应MQHC的元素（图中左下方绿色矩形）；

5) 所有消息的原文（图中左下方绿色信封）；

最后当平行链构造完PoV区块后，验证人会对其进行验证，验证通过则完成出块，然后区块头会上到中继链，中继链更新状态，而发送链通过查询中继链也能知道自己发出的消息最终被处理完成了。

总结

本次Polkadot XCMP的干货文章到此就结束了。这杯茶（X）溪（C）岸（M）啤（P）的味道如何？

XCMP的内容，尤其是本篇中讲到的XCMP消息存取部分，还是比较复杂的，用到了很多新创造的概念，比如消息哈希链表（MQHC），以及各种类型的Merkle树（消息树、CST Item构成的树、CST Row构成树、状态树等等）。确实很难一次性看懂，建议大家多看几遍（划重点：可以仔细看看我们画的那张XCMP消息存取的图）。

之所以设计得这么复杂，是为了XCMP的设计目标：快速、有序、可验证、无遗漏。

XCMP的设计主要分为XCMP消息分发和XCMP消息存取，现在我们回顾下，Polkadot是否实现了其设计目标：

消息分发：通过平行链直接直接发消息，而不中继链达到了快速√。

消息存取：通过watermark及其相关机制达到有序√、无遗漏√的目的；通过MQHC、各种Merkle树及Proof做到了可验证√。

综上，Polkadota XCMP的设计大致是完成其目标的。但也因为XCMP设计比较复杂，目前还在实现中，未来可能会有一些变动，让我们共同关注。