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仍然是需求量最大的，最複雜的元件，並且有望保留下來。
鏈間資訊傳遞:出口佇列（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)的任何字首。
執行時有關平行鏈的所有資訊均來自
該候選源是透過驗證平行鏈候選區塊生成的，幷包含在中繼鏈區塊中。候選人有很多領域。以下是一些相關的內容：
出口根（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佇列路由的簡單八卦協議：基於發出訊息的中繼鏈區塊的陣列（Topics）
本章描述了用於傳播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）傳播頻寬。
5. 用類似於概率性小額支付的方式激勵分銷。
6. 平行鏈驗證人節點將保留出口（egress）佇列，直到確認已包含訊息為止。當兩個平行鏈網路沒有相同的完整節點並且訊息不透過閒聊到達時，這是一個回滾。接收方平行鏈的平行鏈驗證人節點將注意到丟失的訊息，並向傳送鏈的平行鏈驗證人節點詢問訊息。一旦他們收到了該請求，就會在接收者的平行鏈網路中傳播。
區塊鏈到業務邏輯具有的所有資訊均採用CandidateReceipts的形式。區塊簽署者可以從區塊中的每個平行鏈提交最多一個CandidateReceipt（實際上，只有那些由多個驗證者證明的鏈才可實現，儘管此假設在此不相關）。
原作者：潛行之堯PolkaBase
原文連結：https://mp.weixin.qq.com/s/hQhVkn6MJ2jFOQkzOMHIfw
