Web3研究系列：XCMP跨链传输协议

目录

· 链间消息传递

· ICMP队列路由的简单八卦协议

    在新的树状结构（leaves）B上

    节点(peer)k的新链区块头声明

    来自模组t的k在队列(Queue) 消息m上

    对等层节点(peer)k在〖allowed〗_k (m)上的定义

    时效性（Periodically）

· XCMP Routing概述

· 未来提升

XCMP 跨链消息传递

在波卡网络中我们需要提交信息给一些实体（entities），首先就让我们来简明扼要地梳理一下这些实体的类型：（1）用户，（2）收集人，（3）验证人

1. 用户 - 创建交易并将信息提供至平行链或中继链

2. 收集人 - 隶属于特定的平行链。他们负责把平行链的交易数据整理打包成区块生成有效凭证，并将其作为下一个区块的组成部分提交给位于平行链上的验证人。之后与有效性相关的两个环节是波卡网络的基本规则的一部分，但如何进行具体的整理操作是由平行链自主选择完成的。

3. 验证人 - 隶属于中继链且遵守波卡网络的规则。验证人不同的子集会被分配至不同的平行链以验证这些链，由此我们把这些子集称为“平行链的验证人”。他们同样也会整理交易信息提交并给中继链。

接下来，我们需要了解几个在这些实体间的子协议，每一个子协议都服务于执行交易的相应抽象部分：

1. 交易提交（Transaction submission）

在相关实体接入可用的情况下，用户需要找到该相关实体以提交交易。

2. 平行链的收集 （Parachain collation）

平行链的收集人将交易信息收集打包到区块中，区块内的数据来自于每个平行链自行选择的波卡网络范围之外的外部链。

3. 平行链区块认证（Parachain block attestation）

收集人还会生成其他证明数据，并将其提交给平行链的验证人。这样做的最终目的是让平行链的验证人有效地检查每个平行链区块是否满足其链上的验证功能。为了生成证明数据，收集人还需要中继链上早期由平行链验证人发送回的数据。

4. 中继链协议（Relay-chain protocols）

平行链验证人会证明已发送的任何平行链区块的有效性，并将这些证明分发给其他验证人以达成共识。然后，所有验证人将已证明的区块和中继链上的交易信息整理打包为中继链区块，并最终确定区块。

5. 链间消息传递（Inter-chain messaging）

在中继链区块最终确定并将这个事实提交回平行链之后，平行链会检查这些区块是否包含来自其他平行链的新信息，如果有，则进行纠正并做出反应。

6. 平行链的信息一体化

（Parachain synchronisation）

当收集人首次连接或长时间断开连接后，再次恢复连接后它必须重新进行检索并验证平行链的最新状态，验证内容包括临时提交的交易信息以及有关中继链最新状态的信息。

7. 中继链的信息一体化

验证人首次连接或长时间断开连接后，再次恢复连接后它必须重新进行检索并验证平行链的最新状态，如临时提交的交易信息。

在上述的描述中，我们已经抽象地解释了有关的细节，并试图保证其有效性即便这些细节发生了变化。写程序时我们发现，在波卡网络层需要提供服务中，子协议（3-5）和7仍然是需求量最大的，最复杂的组件，并且有望保留下来。

XCMP

链间信息传递: 出口队列（Egress Queue）数据获取

Polkadot中的每个平行链块都会生成一个可能为空的消息列表发送至其他每个区块。这些    被称为“出口队列（egress queues）”。E_(x,y)^B用来表示在区块B中从x链到y链的出口队列（egress queues）。R(E_(x,y)^B) 这是Merkle Patricia trie[]的哈希根，根由为信息数据中的E_(x,y)^B绘制树状图而得到。

传递到链被挂起的尚未处理的消息应该在该链的下一个区块中进行处理。如果一段时间内链上未生成新的区块，消息可能会开始堆积。

平行链p上的收集人节点和完整节点已执行了该平行链上的所有区块，并应了解所有B区块和x链中的E_(p,y)^B

平行链p上的区块出口（egress）在区块B上的的接入点集合为：

区块的入口（ingress）集合根为

平行链p上区块B的总积累入口（ingress）可由递归函数来定义：

这是一个包含了由区块B开始到每个平行链再到p链内的每个区块上所有入口（ingress）

平行链都必须运行在 〖ingress〗_(parent(B),p)之后运行 〖Ingress〗_(B,P)，同时任何来自〖Ingress〗_(B,P)的数据和指令都必须被运行。

每条平行链都有有中继链生成的一个水印值p，该值反映了最近运行的入口（ingress）操作。最初设置为Genesis，为了将包含所有未处理消息的结构定义为一个平行链，我们引入了待处理入口（ingress），它由递归函数定义。

这些待处理根R(P_INGRESS (B,P))也可以被近似计算成R(T_INGRESS (B,P)).一个平行链的候选链允许在中继链区块B顶部构建P_INGRESS (B,P)的任何前缀。

运行时有关平行链的所有信息均来自 

CandidateReceipts

该候选源是通过验证平行链候选区块生成的，并包含在中继链区块中。候选人有很多领域。以下是一些相关的内容：

出口根（egress roots）：

Vec<(ParaId, Hash)>

当中继链块B包含在平行链p中时，与唯一平行链y配对的每个哈希值为R(E_(p,y)^B)

当接收数据是针对平行链p时，会生成一个新的

watermark p

的值。运行时将其收到的来自最近的平行链的候选链的值视为当前值。在包含候选者的任何区块B的原始值必须至少与之前watermark p的值一样高。

（rob：不允许空列表里非空的待处理出口（egress））

验证人和收集人都试图在区块B上收集出块队列信息，或验证人仅调用〖Ingress〗_(B,P)并在传播池中搜索相关消息，以等待尚未被放出的消息。收集人在P上的目标是在中继链parent B上进行构建，以此尽可能地获取P_INGRESS (B,P)的前缀。

最简单的方法就是用。消息从一个平行链网络被流言（gossip）到另一个平行链网络。如果这两个网络之间有共同的节点在散播消息，则消息将导致正在接收消息的平行链接收到其消息。然而，如果靶平行链的验证人意识到消息没有在平行链的接收器上被传播，他们会从发送消息的平行链的验证人节点处重新请求消息，之后他们会自行在平行链上的接收器进行传播。

R(P_INGRESS (B,P))在每个区块B和平行链p在运行时都可用。

平行链p和区块B的可用性是由于p和B是该块的待处理入口（ingress roots）的入口（ingress）列表而每个列表与根首先要与路由的区块编号配对。从入口（ingress）列表中省略R(∅)，并省略空列表并按区块号升序排序。其中所有区块号均小于num(B)，并引用同一链中的区块。

在RUST语言中的伪码（pseudo-code） (TODO:转录到 LaTeX)

fn ingress(B, p) -> Vec<(BlockNumber, Vec<(ParaId, Hash)>)>

对于给定的B和p的未出口队列（egress queues）数据在运行时依旧可用，这与入口（ingress）列表w.r.t.对空列表的排序和省略遵循相同的约束。这里的 ParaId是接收链，而在入口（ingress）函数中，它是发出的链。

fn egress(B, p) -> Vec<(BlockNumber, Vec<(ParaId, Hash)>)>

我们来假设树状结构端点（leaves）区块是中继链中最新的平行链区块。

我们对节点做出以下假设：

1，树状结构端点的区块状态（block-state of leaves）可用，但不能保证旧区块的状态

2，可以预期，平行链上的收集人和完整节点会保留在平行链上已执行的所有出块。

3，验证人不需要保持任何的出块。同时要注意信息可以从验证人保存的擦除编码片段中恢复

假设我们建立在承认流言传播协议（gossip protocol）系统的基础上，同龄人可以互相交流他们认为最好的树状结构端点（leaves）

ICMP队列路由的简单八卦协议：基于发出消息的中继链区块的数组（Topics）

本章描述了用于传播ICMP消息队列的有限制的流言传播协议（gossip protocol）（请参阅概述以了解定义）。

fn ingress(B, p) -> Vec<(BlockNumber, Vec<(ParaId, Hash)>)>

和

fn egress(B, p) -> Vec<(BlockNumber, Vec<(ParaId, Hash)>)>

由于在区块B上ingress已被调用，我们可以轻易将 

BlockNumber -> BlockHash

进行转换

消息从非路由状态开始以路由状态结束

我们提议定义一个流言（gossip）传播系统

有关此模块的的消息格式为

struct Queue { root: Hash, messages: Vec<Message>, }

我们将本地信息保留为：

1.〖leaves〗_k是我们DAG区块树状结构端点（leaves）哈希函数最好的列表需要执行代码

MAX_CHAIN_HEADS

2.〖leaves〗_k，对于每一个对等点k最好最新列表需执行代码MAX_CHAIN_HEADSDAG区块的哈希值（基于它们发送给我们的内容）

3. leafTopics(l)→{queueTopic(h)}表示对于所有树状结构（leaves）上的树状节点l上的平行链上未展开的根h

4. expectedQueues(t)→H 表示所有调用模组对应哈希根的推导过程，所有条目中的t∈∪l_(∈leaves)leafTopics(l)

在新的树状结构（leaves）B上

1.升级树状结构（leaves），树状模组（leafTopics），以及预期队列（尚未进行基准测试，但保守估算会有100ms的运行时间）

2. 发送同层新的树状结构（leaves）

3. 如果平行链p的收集人在线执行代码egress(B,p). 对于任何已知的尚未传播的消息队列根，我们会将相应的Queue 消息放入传播池中。

节点(peer)k的新链区块头声明

1. 升级树状结构（leaves）〖leaves〗_k

2. 符合∀H∈leaves ∩ 〖leaves〗_k要求的，broadcastTopic(k,t)中的每个t都映射在leafTopics(H)上

来自模组t的k在队列(Queue) 消息m上

我们定义函数

good(m)

作为本地局部的置信标准(local acceptance criterion)。

该消息的哈希根

root

在函数 expectedQueues(t)上有定义，给定消息的实根等于root

如果函数good(m) 证明k是正向的，便将m放在传播池中，否则，证明m是不可用的，这对同步培育（peer-set cultivation）来说很有用。

对等层节点(peer)k在〖allowed〗_k (m)上的定义，以及在模组t上的Queue 消息m 

如果消息k在我们发送消息完成之前就已经发送该消息给我们，消息k就应当被拒绝。反之，如果出现以下情况 

∃l∈leaves∩〖leaves〗_k| t∈leafTopics(l)∃l∈leaves∩〖leaves〗_k | t∈leafTopics(l)，则允许消息k， 并禁止其他方式。

时效性（Periodically）

除了expectedQueues 我们需要标记所有模组作为过期失效模组，并在传播池（propagation pool）中清除他们。实际上，这样的操作每隔几秒钟就会执行一次。以此防止我们的传播池无限期增长。

仅将未路由的消息（unrouted messages）传播给对当前模组有相同观点的对等层节点(peer)的决定可能会引起争议，但是我们提出的一些先决条件可以很好地证明这一点。

首先，我们不希望节点必须处理无数个消息，这说明在queueTopic(H)中的H对于节点来说是未知的，因为有无数个这样的H。其次，节点不必进行大量工作来决定是否将消息传播到特定对等方。假设leaves∩〖leaves〗_k=∅，但一些〖leaves〗_k的条目是leaves的源代码

（ancestors）。我们必须在O(n)上运行每一个 l∈〖leaves〗_k来证明。然后，我们必须弄清楚给定的消息是否在前一个块上取消路由。我们天真地认为，如果一条消息在同一条链中的某个较后的区块上仍然被取消路由，而不是在较早的链中建立路由，虽然不太可能但是链的状态可能会在钓鱼人节点处回滚。

由于假定链状态不可从先前的区块中获得，因此我们没有好的方法来确定是否实际将出口（egress）发送给该先前的区块的节点(peer)。在未来的改进部分中，我们将讨论通过扩展到固定数量的源代码（ancestors）来放宽这一限制。

尽管如此，只有向已经同步到同一链节点(peer)传播才是合理的，假设如下（一些经验的但合理的，但也有可能被高估）：

1.新的有效块平均间隔至少5秒发布一次（我们的目标实际上是10-15秒）

2. 区块在流言（gossip）传播结构的 “有用”部分内的传播时间在2秒以内。

3. 流言（gossip）传播结构中的相邻主体有小于等于500ms的延迟

4. 在同步到DAG头部之前有意义地传播消息可能是不值得的

如果我们假设直到块完全传播后才会广播更新树状结构（leaves）节点（实际上显然不是这种情况），那么在更新leaves之后直到下一个区块到来会有一段500毫秒的延迟向流言（gossip）系统 Queues并发送完整的2.5个跃点(hops)。

实际取值几乎可以肯定会更好。好消息是，并非所有的出块都必须在一个阻塞时间内进行传播-随着时间的流逝，参与者越来越有可能获得较早的消息。这是一个让所有参与者看到所有消息的方案。几乎可以肯定的是，它不会扩展到超出少数初始链的范围，而是在功能上充当一个启动协议。

XCMP Routing概述

要根据设置将消息从一个平行链（发送平行链）发送到另一个平行链（接收平行链），将执行以下步骤。

当发送平行链的完整节点也属于接收平行链域的一部分时，消息就足够了

中继链完整节点在发送和接收并行链的域中，只需对消息进行流言（gossip）传播就可以了

接收平行链的平行链验证人没有发现消息被传播，然后它直接从发送平行链的平行链验证器（发送实时的PV）请求消息。发送平行链的PV负责保持消息可用。发送平行链的平行链验证人直接将消息发送给接收平行链的PoV，最后接收平行链的PV对接收平行链网络中的消息进行流言（gossip）传播。

未来提升

1. 上面的部分描述了为什么将出口队列（egress queues）传播到任意远的节点层（peer layer）是一个坏主意，但是一旦我们同步并遵循正常的出块，我们就可以合理地跟踪所有树状结构（leaves）的最终源代码（ancestors）α。对于α最初合理的取值应与亲代保持一致取1。这可能会让我们获得所需收益的90%，原因很简单，这仅仅是因为当需要树状集相交时会出现“卡顿”的现象，并且两个对等节点在发送更多消息之前需要互相更新有关新子项的信息。

2. 扩展E_(x,y)^B的定义可以允许链间相互审查。例如，平行链y可以在区块B通知中继链不要路由来自x的消息（然后通知它在区块B'重新开始路由）。对于任一在B和B’之间的区块，当不考虑 CandidateReceipt上b的x我们会有运行时间运行E_(x,y)^b=∅ 。实际上，由于运行时仅处理哈希根散列，因此它实际上只是从候选收据中忽略R（E_(x,y)^b）并将其设置为R（∅）

3. 扩展以支持并非所有人都能看到所有内容的更智能的拓扑。也许有两种主题数组（Topics），基于（B，（B，〖chain〗_from））的主题数组（Topics）和基于（B，〖chain〗_to）的模组将提高该模组的可用性。

4. 使用某种智能设置对帐（例如

https://github.com/sipa/minisketch）来最小化流言（gossip）传播带宽。

5. 用类似于概率性小额支付的方式激励分销。

6. 平行链验证人节点将保留出口（egress）队列，直到确认已包含消息为止。当两个平行链网络没有相同的完整节点并且消息不通过闲聊到达时，这是一个回滚。接收方平行链的平行链验证人节点将注意到丢失的消息，并向发送链的平行链验证人节点询问消息。一旦他们收到了该请求，就会在接收者的平行链网络中传播。

区块链到业务逻辑具有的所有信息均采用CandidateReceipts的形式。区块签署者可以从区块中的每个平行链提交最多一个CandidateReceipt（实际上，只有那些由多个验证者证明的链才可实现，尽管此假设在此不相关）。

编译 / 潜行之尧

原文 / Research at W3F

往期回顾

Polkadot Newbee

Polkadot Pro

关注公众号，发送1进入社群

点个“在看”继续支持