Polkadot跨链消息传递(XCMP)方案

Polkadot 的跨链消息传递（Cross-chain Message Passing，XCMP）方案是 Polkadot 协议的一个子集，它主要用来定义除共享中继链安全之外，在没其他信任假设的情况下，消息如何得以在平行链之间传递。主要内容包括：消息队列机制，消息可用性，消息输入和输出等

简而言之，XCMP 方案利用基于 Merkle 树的简单队列机制确保跨链交易的正确性，并由中继链上的验证人负责把平行链出口队列中的交易转移到目标链的入口队列中。

（翻译：波卡技术大使 Lester）

XCMP - 中继链轻客户端设计

在本文档中，我们描述了如何为 XCMP 存储和检索消息。本文不涉及 ICMP 网络，而是重点在于链上的数据，以便可以通过平行链和平行线程确定已接收哪些消息。

动机

平行链和平行线程可能有多种发送消息的原因。仅举几个例子：可能需要代币转移，共享/转移智能合约或通过平行链向另一个提供服务。XCMP 应全部涵盖这些。

问题

问题在于，平行链收集人需要知道他们从发送平行链收到的消息。特别是，他们需要知道尚未采取行动的消息。为了做到这一点，并避免过多的并行链间通信，中继链需要能够验证消息以及平行链所作用消息的信息。

但是，将这些消息的所有哈希值保留在中继链上是个很大数据量，并且可能在许多地方需要查找该数据。

此外，平行链对消息起作用的时间可能很长，这期间可能已经重新分配了平行链验证人，或者根本不再是验证人。

后一个问题对于平行线程尤其如此，因为平行线程之间可能存在较长的间隙。

目标

XCMP 应适应以下情况：

（1）所有验证人应能够尽可能长的时间内验证 PoV，至少是在平行区块产生的第二天。为此，验证人需要检查是否对正确的传入消息采取了措施。

（2）应该使用最少的中继链状态存储。每个区块的中继链处理和状态访问也需要是可行的。

（3）接收平行链或平行线程的全节点需要知道从它作用于消息的最后一个中继链区块以来，是否有来自任何平行链的新消息。

（4）如果特定的发送平行链向接收平行链发送了一条消息，然后该发送平行链产生了不向该接收方发送任何消息的区块，则接收平行链的收集人不需要来自全节点或发送平行链的平行链验证人的任何数据。特别是，这意味着当接收者需要对来自发送者的新消息采取行动时，仅存在链间通信。

假设

接收平行链按照中继链区块的顺序作用于消息，其中中继链区块包括引发该消息的平行链区块的区块头。如果多个发送平行链已在同一中继链区块中发送了接收平行链消息，则接收平行链将作用的消息顺序是根据规则，例如递增的平行链ID或基于中继链区块号的确定性混洗。合理地假设一条平行链至少可以作用于单个平行区块中另一个平行链发送的所有消息。因此，我们总是可以假设，一旦接收方的平行链对中继链中的一个平行链起作用，它就会对与该平行链相关的所有消息起作用。因此，存在定义明确的*watermark=(relay chain block number, paraid)*，即“水印”为中继链区块号和平行链ID组成的元祖，该“水印”表明接收平行链已对其最后一个平行链区块执行消息。

平行链区块的水印应位于进入中继链区块的平行链区块头中，最后一个水印需要以与平行链关联的中继链状态存储。

通过构建区块，每个平行链都可以与其他平行链通信。但是，由于可能存在大量的平行线程，因此，每次要生成区块时，平行链收集人必须查询的区块数量有限。因此，对于从平行线程发送的消息，中继链必须存储的数据量应该有一个限制。

平行链收集人在许多区块查询中继链，或者中继链的所有全节点查询中继链中的许多区块。为了限制这一点，我们将平行线程可以与之通信的链数限制为100，并将其称为通道。这意味着一条平行链可以与所有其他平行链（最多100条）通信，并且还具有通向已知数量的平行线程（可能超过100条）的通道。通道列表存储在中继链状态中。通道两端的两个平行链都需要同意建立这样的通道，并且在开放时，都需要将另一个作为其通道之一。

注意，这里我们假设通道是单向的，但是它们可以实现为双向的。

一个平行链可以发送给另一个的未接收消息的数量也需要受到限制。

解决方案概述

我们希望有一个压缩的数据结构，但还要确保接收到的平行链仍然可以找到发送给它们的消息。接下来，我们描述如何构造这样的数据结构。

数据结构：Merkle 树和位域

我们想要构建一个数据结构，该结构允许在中继链区块和中继链状态上包含少量的数据，但可以验证 PoV 块中所有接收到的消息。

消息队列链：为了在中继链上保留最少的消息数据量，将消息链接在仅存储链头的消息队列链中。这也确保了消息的有序性，其接收者按照此顺序对其执行操作。

我们定义消息队列哈希链如下。我们有一个

$$H(Head_{HC}) : Head_{HC} = H (m) || b || H(previous Head_{HC}))$$

其中 $m$ 是一条消息，$H()$ 是一个哈希函数，$b$ 是我们最后发送消息的中继链区块号，不是 $m$ ，而是前一条消息。

有关更多详细信息，请参见?此处（github.com/paritytech/p）。

每个平行链区块都有一个元组，该元组由平行链区块消息根（即sender_message_queue_merkle_root）和一个位字段组成，它们存储在中继链块的平行链区块头中。

消息根是 Merkle 树的根，该树可用于从接收对象中查找 $Head_{HC}$。该位域的每个通道都有一个位，表明该平行链区块向其发送消息的接收平行链。消息根和位字段将在发送平行链区块头中，并将用于更新中继链状态。

当接收方平行链正在构建 PoV 区块时，它会包含来自有此平行链通道的平行链的最新消息根。使用消息根，接收平行链需要证明它已获取了从最后一个“水印”到当前“水印”的所有消息。这可以通过以下方式完成：将消息根和 Merkle 证明提供给发送平行链消息队列的头部，并将哈希链显示回最后一个“水印”之后的最早消息。它包含所有当前消息的哈希，这些哈希可用于验证所有接收到的消息是否正确。此外，显示的消息哈希链还可用于验证我们所处理的消息之前的最后一条消息的区块数是否低于最后一条“水印”。

创建一个 PoV 区块：收集人需要做两件事才能产生一个平行链区块。首先，收集人需要获取所有消息和相应的 Merkle 证明。其次，要生成 PoV 块，需要能够在中继链中查询具有相应区块号的最新消息根，以获取每个通道中收到的最后一条消息。

为了验证 PoV 区块，平行链验证人需要至少一天后才能找到这些消息根。如果这些仍在链上，则可能具有较大的中继链存储需求。中继链的轻量级客户端成为钓鱼人也很好，这样能够验证中继链区块。因此，对于这些消息根，我们将使用中继链轻客户端状态证明。

也就是说，对于每个通道，在 PoV 区块中将有一个哈希链，从中继链状态根开始，该哈希链由3部分组成：- 消息根的中继链轻客户端证明；- 哈希链头的 Merkle 证明；- 哈希链扩展回前一个区块号在前一个水印之前的区块。平行链需要在该通道中作用的所有消息的哈希值。

关于中继链出口数据的实现细节

通道状态表（Channel State Table，CST）是一种结构，存在于中继链的状态内，并跟踪最新的发送方消息队列根。CST 项按行存储，其中所有项共享同一发件人。它们与目标的平行链ID配对成一个存储映射。第二个存储项包含每行的 Merkle 根。

有关更多详细信息，请参见?此处（github.com/paritytech/p）。

当中继链处理包括消息根和位字段的平行链区块头时，中继链节点将更新 CST 中的一行，该行与发送平行链和该行的 Merkle 根相对应。该行包含每个平行链的最新消息根目录和区块号，每个平行链具有此平行区块所属链中的一个通道。

该行可能很大，但是可以在一个区块写入一次存储更新。

原则上，如果我们将此设计与位域一起使用，那么我们可以拥有大量的传出通道，但以这种单次写入操作需要更多数据为代价。特别是，将允许平行链连接到100多个平行线程。

可选地，平行链可以具有由所有进入通道的入口队列，它是由平行链ID，最后一个消息根和区块号组成的三元组(paraid, last message root, block number)?。中继链可以更新每个区块，这样一来，一条链可以拥有10,000个通道，而不必在中继链上查找10,000个区块。

哪些数据，存储在哪里？

中继链区块中的parachain-header/candidate_receipt：消息根和引用接收平行链的位字段。由于通道的数量有限，对于平行线程，该位字段可能是128位，但对于平行链，则可能需要可变大小。它还需要中继链区块号和平行链ID形成的“水印”以表明接收平行链已作用于哪个消息，以及中继链状态根，加上相应的区块号，其中 PoV 区块中的所有中继轻客户端证明均是基于该区块号。

发送平行链的状态：发送平行链状态将存储中继链上接收平行链所收到的最后一个“水印”。它不只是存储了链的区块头，还为链中所有链接的每个消息根存储了 Merkle 证明。链接是一个三元组，它包括消息的哈希，前一个区块号和前一个链接的哈希。

哈希链的大小决定了通道的容量。可以在接收证据（通过中继链轻客户端证明）上删除接收链水印已更新的旧消息。

发送平行链验证人集合：他们保留已验证的平行链区块上已发送的消息，完整的 Merkle 树和最新的哈希链的区块头。该数据存储一天。

链上的中继链状态：即上一节中描述的CST。

XCMP_CST 这是平行链 A，B，C，D，E 通道状态表的示例，在这些参数中共有 9 个通道。

中继链状态可以通过存储 XCMP_root 来帮助验证 XCMP 消息，该 XCMP_root 是包含所有通道水印，即由（中继链区块编号，平行链ID）组成的 Trie 根。在此示例中，平行链 A 最后作用于中继链区块 rc_1 中的消息，平行链 B 最后作用于中继链区块 rc_2 中的消息，依此类推。底部的信封图标对应于通道的消息队列链中的实际消息内容。仅这些链的头部用于构造发送消息的根。

生成 PoV 区块

PoV 区块需要包括嵌套的 Merkle 证明和哈希链扩展，该扩展从轻客户端状态根开始，并在每个需要执行的传入消息处结束。Merkle 证明将有很多共同的部分，并且可以通过共享共同的部分进行优化（未来的工作）。

考虑一个收集人 $C_A$，它想为平行链 $A$ 生成一个 PoV 区块。我们假设平行链 $B$ 具有到平行链 $A$ 的通道，即可以向平行链 $A$ 发送消息，平行链 $A$ 具有到平行链 $D$ 的通道。请注意，如果通道是单向的，则平行链 $A$ 无法将消息发送到平行链 $B$，平行链 $D$ 不能将消息发送到平行链 $A$ 。

收集人 $C_A$ 需要中继链中的某个全节点构造的一个轻客户端证明，证明消息根是所有对平行链 $A$ 开放通道的，例如平行链 $B$ 。请注意，收集人 $C_A$ 和全节点可能在同一台计算机上运行。

同时收集人 $C_A$ 需要轻客户端证明，证明平行链 $A$ 具有访问其它平行链“水印”的权限，例如平行链 $D$ 。所有这些轻客户端证明都应同时从中继链状态构建，这意味着它们都从相同的中继链状态根开始。此中继链状态根和相应的区块号将在平行链区头中（candidate_receipt）。

可选：对于平行链，如果要使用它们的入口队列，我们将为中继链更新每个区块的所有传入通道维护一个列表，由(平行链ID，最后一个消息根，区块号)组成的三元组。因此，中继链轻客户端证明仅是此列表和 Merkle 证明。

如果平行线程和平行链之间没有特殊区别，则整个节点需要查看 CST 中多达 100 行（或者对于平行链则更多）的出口数据，对于发送平行链有其通道的通道，例如平行链 $B$ 的所有通道。对于这些通道中的每一个，都需要一个 Merkle 证明，该证明从中继链状态根开始，并在接收平行链的(消息根，区块号)处结束，比如平行链 $A$ 。也就是说，对于每个通道，都有一个嵌套的 Merkle 证明，其中第一个 Merkle 证明指的是完整的 CST 行，而第二个 Merkle 证明（嵌套 Merkle 树），指的是与接收平行链，例如平行链 $A$ 相对应的条目。

在中继链轻客户端证明中包括了100多个所有这些通道的 Merkle 证明。

在全节点提供给收集人 $C_A$ 所有轻客户端证明之后， $C_A$ 拥有所有最新消息的区块号和消息根。因此，它可以验证平行链 $A$ 是否已经正确接收到任何指定消息的内容（有效负载）。

如果平行链 $A$ 没有对某条消息进行处理，例如来自平行链 $B$ 的消息，则 $C_A$ 需要该消息及其消息根中的证明。$C_A$ 可能已经具有此消息并提供证明，但如果 $C_A$ 没有，则需要向已连接到平行链 $B$ 的任何全节点询问该消息，或向消息对应区块号的平行链 $A$ 或平行链 $B$ 的验证人询问消息。如果来自平行链 $B$ 的消息来自它的验证人，则这可能意味着询问不同时间是平行链 $B$ 的许多验证人，因为平行链验证人是根据区块号轮循的。请注意，平行链 $B$ 的全节点知道所有这些消息，因此应首先询问它。

除了来自 $B$ 的最新消息外， $C_A$ 还应收到将最新消息链接到消息根的证据，以及前一条消息的区块号，因此它知道是否还需要请求较早的消息。

当 $C_A$ 同时具有：- 来自消息根的所有消息证明，- 来自一个中继链状态根的所有消息根证明时，上述嵌套的 Merkle 证明，它可以将它们组合起来以获取来自中继链状态的所有消息的证明，然后将这些证明以及所有起作用的消息放入 PoV 区块中。

例如，如果平行链 $A$ 自上一个“水印”以来已从平行链 $B$ 接收到许多消息，则 PoV 块应包括：

一个 Merkle 证明，从平行链区块头中的中继链状态根（或candidate_receipt）到 CST 中平行链 $B$ 的 CST 行哈希。

一个消息根和区块号的 Merkle 证明，对应于从 CST 行哈希到中继链状态根的区块高度处，从平行链 $B$ 到平行链 $A$ 的最后一条消息。

一个 Merkle 证明，消息根从平行链 $B$ 到平行链 $A$ 的消息哈希链头。

通道哈希链三元组，平行链 $B$ 到平行链 $A$ ，再到在平行链 $A$ 上一个“水印”之前的区块号

从平行链 $B$ 到平行链 $A$ 的消息，平行链 $A$ 上一个水印到其新“水印”的消息，其哈希与哈希链中哈希相对应。

注意，如果中继链状态的根是正确的，并且区块号比新的“水印”更安全，则此证明表明这些正是平行链 $B$ 应该由平行链 $A$ 进行的消息。

平行链全节点用来更新状态的平行链区块，可能包含有关接受到的消息，“水印”更新等未经验证的断言。

XCMP_POV 在此示例中，平行链 $A$ 需要显示它对平行链 $B$ 发送给平行链 $A$ 的最后两个消息起作用，即这是新消息。为了证明这一点，收集人 $C_A$ 在 PoV 区块中包含以下证明。1）从中继链状态根到平行链 $B$ 的 CST 行哈希的 Merkle 证明（图中的红色节点）。2）消息根的Merkle证明（图中的蓝色节点）和区块号，在中继链状态根的区块高度（rc_1）处从平行链 $B$ 到平行链 $A$ 的最后一个消息所对应的区块号。3）从平行链 $B$ 到平行链 $A$ 的消息哈希链头部的 Merkle 证明（图中的橙色节点）。4）从平行链 $A$ 的先前水印到其平行链 $B$ 到平行链 $A$ 的哈希链三元组以及从平行链 $B$ 到平行链 $A$ 消息新“水印”（图中为绿色的节点+信封）。

验证 PoV 区块

根据上述方案，任何知道这三个数据的都可以验证 PoV 块：

PoV 区块本身。

状态转换验证功能（state-transition-validation-funtion，STVF）。

平行链区块头。

这使得不是平行链和中继链客户端的“钓鱼人”能够验证 PoV 区块。

但是，如果我们不能信任 STVF，则该方案会有一个缺点（一旦有了 SPREE，我们将在下面进行讨论，这将不再是问题）。存在恶意 STVF 时的缺点是中继链不验证哈希链更新，它们处于平行链的状态。如果 STVF 更改了此平行链状态，则可能需要发送方接收带有哈希的消息，而该哈希从未发送过任何消息，因此最终使接收方停滞。

在 SPREE 之前，我们应该要求平行链验证人独立于 STVF 验证来验证哈希链更新。平行链验证人将需要检查（1）新消息的 Merkle 证明和来自中继链根的哈希链头，以及（2）最后一个消息根的 Merkle 证明（当前在中继链中）。检查（1）和（2）满足新哈希链区块头中的前一个哈希和区块号确实对应于前一个哈希链区块头。

未能正确做到这一点也是对平行链验证人进行 slashing 的一个条件。但是，如果很快实现了SPREE，则优先级较低，因为我们最终可能会跳过它。

SPREE 集成

SPREE 是一种使模块具有状态和执行沙箱的方法，该模块从 wasm 执行的其余部分开始。我们希望一条链（可以是平行链，也可以是中继链）上的 SPREE 模块将消息发送到另一条链上的同一 SPREE 模块，并且对于任何一条链的 STVF 都不可能干扰该消息。

由于我们的解决方案要求消息具有链状状态，因此显而易见的方法是使消息处理代码和状态本身由 SPREE 模块处理。我们将拥有一个中央 SPREE 模块，如果所有平行链都想完全参与 XCMP ，则需要它们。

消息处理 SPREE 模块将在执行 STVF 时首先被调用，并在将控制权移交给 STVF 的其余部分之前将进入的消息路由到其他 SPREE 模块和 STVF 的大部分。

我们认为接收模块不应对收到的消息采取行动，而应仅将传入消息添加到缓冲区中并等待 STVF 安排它们有时间对其采取行动。

这是多大的数据？

发送平行链的出口数据有 Merkle 根和用于接收平行链的区块号。Merkle 根是 32 字节的哈希，区块号为4字节。

我们可能有多达一百万个通道，这意味着 36 MB 链上数据，如果我们包括 Merkle 树以及每个出口表的数据和 Merkle 根，则为 72 MB。在最坏的情况下，其中一半将在一个区块中进行更新。

我们需要对该数据量进行两次哈希运算以计算其 Merkle 根。Blake2b 速度很快，请参阅?blake2.net/，并且在1秒钟内，它可以在现代处理器上哈希超过100 MB 的数据。因此，我们将考虑 36 MB 和 360 ms。

但这甚至是不可能的。

—-

编译者/作者：超节点区块链SSS

玩币族申明：玩币族作为开放的资讯翻译/分享平台，所提供的所有资讯仅代表作者个人观点，与玩币族平台立场无关，且不构成任何投资理财建议。文章版权归原作者所有。