Web3研究：XCMP跨链传输协议

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

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

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

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

时效性（Periodically）

• XCMP Routing概述

• 未来提升

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

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

出口根（egress roots）：

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

当接收数据是针对平行链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)

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

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

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

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

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

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

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

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

和

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

进行转换

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

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

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

我们将本地信息保留为：

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

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上

我们定义函数

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

该消息的哈希根

在函数 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）传播带宽。