目錄

鏈間消息傳遞

ICMP隊列路由的簡單八卦協議

在新的樹狀結構（leaves）B上

節點(peer)k的新鏈區塊頭聲明

• 來自模組t的k在隊列(Queue) 消息m上

• 時效性（Periodically）

在波卡網絡中我們需要提交信息給一些實體（entities），首先就讓我們來簡明扼要地梳理一下這些實體的類型：（1）用戶，（2）收集人，（3）驗證人

每條平行鏈都有有中繼鏈生成的一個水印值p，該值反映了最近運行的入口（ingress）操作。最初設置為Genesis，為了將包含所有未處理消息的結構定義為一個平行鏈，我們引入了待處理入口（ingress），它由遞歸函數定義。

運行時有關平行鏈的所有信息均來自

出口根（egress roots）：

該候選源是通過驗證平行鏈候選區塊生成的，並包含在中繼鏈區塊中。候選人有很多領域。以下是一些相關的內容：

出口根（egress roots）：

當中繼鏈塊B包含在平行鏈p中時，與唯一平行鏈y配對的每個哈希值為R(E_(p,y)^B)

當接收數據是針對平行鏈p時，會生成一個新的

的值。運行時將其收到的來自最近的平行鏈的候選鏈的值視為當前值。在包含候選者的任何區塊B的原始值必須至少與之前watermark p的值一樣高。

R(P_INGRESS (B,（rob：不允許空列表裡非空的待處理出口（egress））

驗證人和收集人都試圖在區塊B上收集出塊隊列信息，或驗證人僅調用〖Ingress〗_(B,P)並在傳播池中搜索相關消息，以等待尚未被放出的消息。收集人在P上的目標是在中繼鏈parent B上進行構建，以此盡可能地獲取P_INGRESS (B,P)的前綴。

最簡單的方法就是用。消息從一個平行鍊網絡被流言（gossip）到另一個平行鍊網絡。如果這兩個網絡之間有共同的節點在散播消息，則消息將導致正在接收消息的平行鏈接收到其消息。然而，如果靶平行鏈的驗證人意識到消息沒有在平行鏈的接收器上被傳播，他們會從發送消息的平行鏈的驗證人節點處重新請求消息，之後他們會自行在平行鏈上的接收器進行傳播。

P))在每個區塊B和平行鏈p在運行時都可用。

平行鏈p和區塊B的可用性是由於p和B是該塊的待處理入口（ingress roots）的入口（ingress）列表而每個列表與根首先要與路由的區塊編號配對。從入口（ingress）列表中省略R(∅)，並省略空列表並按區塊號升序排序。其中所有區塊號均小於num(B)，並引用同一鏈中的區塊。

在RUST語言中的偽碼（pseudo-code） (TODO:轉錄到LaTeX)

對於給定的B和p的未出口隊列（egress queues）數據在運行時依舊可用，這與入口（ingress）列表wrt對空列表的排序和省略遵循相同的約束。這裡的ParaId是接收鏈，而在入口（ingress）函數中，它是發出的鏈。

我們來假設樹狀結構端點（leaves）區塊是中繼鏈中最新的平行鏈區塊。

我們對節點做出以下假設：

1，樹狀結構端點的區塊狀態（block-state of 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秒以內。

二級標題

二級標題

XCMP Routing概述

二級標題

XCMP Routing概述

接收平行鏈的平行鏈驗證人沒有發現消息被傳播，然後它直接從發送平行鏈的平行鏈驗證器（發送實時的PV）請求消息。發送平行鏈的PV負責保持消息可用。發送平行鏈的平行鏈驗證人直接將消息發送給接收平行鏈的PoV，最後接收平行鏈的PV對接收平行鍊網絡中的消息進行流言（gossip）傳播。

二級標題

二級標題

二級標題

未來提升

1. 上面的部分描述了為什麼將出口隊列（egress queues）傳播到任意遠的節點層（peer layer）是一個壞主意，但是一旦我們同步並遵循正常的出塊，我們就可以合理地跟踪所有樹狀結構（leaves）的最終源代碼（ancestors）α。對於α最初合理的取值應與親代保持一致取1。這可能會讓我們獲得所需收益的90%，原因很簡單，這僅僅是因為當需要樹狀集相交時會出現“卡頓”的現象，並且兩個對等節點在發送更多消息之前需要互相更新有關新子項的信息。https://github.com/sipa/minisketch2. 擴展E_(x,y)^B的定義可以允許鏈間相互審查。例如，平行鏈y可以在區塊B通知中繼鏈不要路由來自x的消息（然後通知它在區塊B'重新開始路由）。對於任一在B和B'之間的區塊，當不考慮CandidateReceipt上b的x我們會有運行時間運行E_(x,y)^b=∅ 。實際上，由於運行時僅處理哈希根散列，因此它實際上只是從候選收據中忽略R（E_(x,y)^b）並將其設置為R（∅）