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。
但這甚至是不可能的。
