作者：Alex Myers
來源：https://btctranscripts.com/bitcoinplusplus/2022/2022-06-07-alex-myers-minisketch-lightning-gossip
本文為作者在 Bitcoin++ 2022 大會上的演講的轉寫稿，轉錄者為 Michael Folkson 。演講的幻燈片在此：https://endothermic.dev/presentations/magical-minisketch
Minisketch 庫：https://github.com/sipa/minisketch
Rusty Russell 論在閃電網絡 gossip 中使用 Minisketch：https://gnusha.org/url/https://lists.linuxfoundation.org/pipermail/lightning-dev/2018-December/001741.html
Bitcoin Core PR 審核俱樂部關於 Minisketch 的三次討論：
引言
我在閃電網絡的開發上完全是個新手，剛剛才加入 Core Lightning 團隊。我準備討論 Minisketch 以及我從 gossip 網絡中學到的東西。
話題
我會先聊聊 gossip 協議在閃電網絡中的作用。大家都熟悉閃電網絡，至少有點研究對不對？我不會花太多時間在閃電網絡的工作原理這些背景知識上。但我要解釋 gossip 是如何交織到閃電網絡的運行中的。然後，我也會概要介紹 Minisketch 的工作原理，講解一個案例，然後介紹我們可以如何利用它來優化閃電網絡的 gossip 。
Gossip 的作用
我想，通過案例來介紹 gossip 在閃電網絡中的作用會比較有趣。所以我們從一筆簡單的閃電網絡交易開始。
發送一筆閃電支付
從普通用戶的角度看，所謂的 “閃電支付” 可能就是先打開手機上的錢包 app，然後把攝像頭對準一個 QR 碼或者一段可以掃描的文字（發票）。然後，app 就會給你交易附言和備註，你驗證數額大致正確之後，就點擊 “發送”。只要你不是運氣很差，只需片刻，手機屏幕上就會出現綠色的勾，表明支付發送成功。
但在場的都是狂熱愛好者，所以我認為可以再深入一些 —— 手機屏幕背後，到底在發生什麼事》
閃電支付 - 進階
在 Core Lightning 客戶端中，有很多命令行命令，可以用來獲得更多信息。
lightning-cli listpays <BOLT 11>輸入這個命令之後，我們可以看到它實際上的經過。支付完成了，就會出現原像（preimage），有點像我們在閃電網絡上支付得到的收據。有趣的是，我們可以看出，這筆支付被打散成了 12 筆更小的部分。這 12 條支付路徑都是為了完成這筆支付而計算出來的。
lightning-cli listpaystatus <BOLT 11>我們再看仔細些。可以看出，客戶端不止嘗試了 12 條路徑，實際上它嘗試了 53 次。這就是 “多路徑支付”。一部分路徑因為超時而失敗了。在支付成功之前，我們獲得了一些故障信息。這個 CLI 命令會打印出這些數據。但實際上，我們可以斷定在每一次失敗的嘗試中，已經執行的跳躍（轉發）的次數；而且我們得到了文本編碼的字符串（0x1007...）。如果我們將這些字符串傳入另一個工具（devtools/decodemsg），我們就可以解碼它們。這是 BOLT4 的一部分，該規範指明 1007 意味著我們遇上的是 temporary_channel_failure（通道臨時故障）。
這裡還有一種 “錯失通道更新故障”（0x1000 new channel update enclosed），意味著我們錯過了該節點宣告的支付轉發要求變更。這個中間節點並不知道我們是誰，也不知道支付的最終目的地在哪裡，因為所有消息都是洋蔥路由的。於是它說：“不管你是誰，我覺得，你應該找錯人了。你手上的一些信息已經過時了，我認為你需要看看這個”。在這個案例中，我們可以看到，我們獲得了關於這條通道要收取的手續費、其 cltv_expiry_delta 數值、我們要給超時時間加入多少區塊數量的信息。重要的是這個：channel_flags=1。它看起來不起眼，但如果你仔細看看協議規範，你會發現，它表明該通道已經被禁用了。顯然，在我們計算轉發路徑的時候，我們還沒有這些信息；它就是這條路徑走不通的原因。
閃電支付 - 總結
在這個基礎案例中，我們學到了什麼？即使在這樣簡單的情形中，為了讓這筆支付成功，我們總共利用了 70 條不同通道。關於其中一部分通道，我們的信息已經陳舊了，但我們可以檢索一些新的 gossip 消息、更新我們的路由圖譜 —— 這個圖譜就像是關於網絡形貌的地圖。使用新的信息，我們可以重新計算我們的路徑，從而最終讓支付成功。
Gossip 的作用
回到一開始我們提出的問題：廣義來說，gossip 在閃電網絡中的作用是什麼？就跟生活中的八卦一樣（譯者注：gossip 的字面意思就是 “閒言碎語”）。Gossip 是你分享的關於自己並不直接溝通的對等節點的二手信息。在閃電網絡中，多種多樣的節點互相連接。我們可能直接連接了幾個節點，但是，比如說，我們位於左下角，我們就需要收集不在這個區域的其它節點的信息。這是通過叫做 node_announcement 的 gossip 消息做到的。
這是通過叫做 node_announcement（節點宣告）的 gossip 消息做到的。node_announcement 信息中給出了一個節點的公鑰，以及觸達它的網絡地址（以備你想跟它建立直接連接）。比如說 IP 地址、洋蔥地址或是 web socket，所有你能想象到的方式，都可以包含在節點宣告信息中。
我們想要知道的下一個事情是，通道都在哪裡。於是我們有 channel_announcement（通道宣告）消息。它的作用是表明節點 A 與節點 B 之間存在一條通道、在區塊鏈上有一筆交易為該通道注資。它會列出 “短通道 ID”，就是你要搜索這條通道以及檢查區塊鏈上的哪個 UTXO 為它注資所需的信息。這部分信息對隱私並不好，但在防止拒絕服務式攻擊（DoS）上很有用 —— 發送消息的人需要證明自己有一個開設通道的 UTXO。
現在，我們已經瞭解了網絡的基本拓撲，可以找出穿過它的路徑。但如果有更多信息，那就更好了。於是我們有 channel_update（通道條件更新）信息。這種消息包含的就是比如手續費、該通道願意轉發的 HTLC 的最大數額、是否已被禁用等信息，就像我們在上面的案例中看到的那樣。這都是我們在計算路徑時幫助我們剔除不合用路徑的信息。
現在，我們就有了構造路徑所需的一切信息了。但是，為什麼我的演講題目是 “Lightning Gossip Network” 呢？我們剛剛討論的不是閃電網絡嗎？簡單的回答是，這兩個概念並不完全等同。區別在於，我們看到的這些節點之間的連接，是閃電網絡中的（支付）通道。但在參與 gossip 時，我們只會跟一部分節點通信。具體的數量取決於實現，我記得 Core Lightning 會使用 5 個對等節點，在你連接到的節點中，你會跟 3 個到 5 個節點 gossip。你的 gossip 對象不需要是你的對等節點。你可以跟任何節點 gossip。它甚至不必是一個節點，只要是一個能夠理解協議的及其，可以提供你還不知道的信息，就可以了。只要能收集到關於網絡狀態的新信息，來回通信是受歡迎的。最重要的細節是，gossip 協議是以洪泛傳播（flood propagation）模式運作的。比如你連接到了 5 個 gossip 對等節點，在你從其中一個 gossip 節點那裡收到信息只會，你就會廣播給另外 4 個節點。這在信息傳播的起步階段是非常高效的，因為你會快速將信息傳遞給你所有的夥伴。但在信息傳出幾跳之後，它的效率就開始下降 —— 你開始在多個對等節點處收到一模一樣的數據，這就是效率下降的表現。
Gossip 統計數據
這裡是閃電網絡狀態的基本統計數據。當前，整個閃電網絡有 8 萬條通道和 1.7 萬公開節點。回到前面的洪泛傳播模式，如果我們在一個最小規模的團體（三個相互連接的 gossip 對等節點）裡面，那就意味著，為了讓消息傳遍整個網絡，我們需要至少 14 跳。而且 gossip 傳播有內在的蘇旭限制。實際上，你會批量處理自己收到的所有 gossip 消息，然後等待 60 ~ 90 秒。Core Lightning 使用 60 秒的數值，但我記得 LND 好像是使用 90 秒的循環。你會定期廣播所有你收到的新 gossip 消息給你所有 gossip 對等節點。14 跳，每一跳之間間隔 60 ~ 90 秒，這是一個不短的時間。在實踐中，我們發現，網絡中 95% 的節點會在 13 分鐘內收到新消息。你可能需要等待 20 分鐘，才能指望每個人都能看到新信息 —— 至少是一個有用的經驗法則。
什麼是 “Minisketch”？
換個擋，我們現在要介紹 “Minisketch” 了。我會盡我最大努力。
Minisketch 是一種集合調解（set reconciliation）協議。什麼是 “集合調解” 呢？我們有兩個數據集合，你可以從這個韋恩圖（Venn）看出它們在很大程度上是重合的。在這種情況下，我們倆的數據都是有效的，而我們希望確保我們都能得到一部分新數據，讓這兩個集合都得到更新。這時候我們在意的是兩個集合之間的 “對稱差（symmetric difference）”。這就是 Minisketch 幫助我們的地方。如果你跟幾個月前的我一樣，那麼你可能會認為這是一個很難解決的問題，嘗試調和這兩個集合會付出不小的開銷。你可能會發送超出嚴格必要的信息，因為你不知道對等節點缺少什麼。但就像我一樣，你可能是錯的。Minisketch 有一些非常棒的特性。
背景
Minisketch 實際上來自一個叫做 “BCH 糾錯碼” 的糾錯碼家族。它使用一種映射（map），就像 Berlekamp-Massey 算法一樣。我準備將一個非常簡單、非常抽象的例子。
BCH 例子
設想我們有兩組數據，分別包含元素 (1, 2, 3) 和 (1, 2, 3, 4)。
如果我們想要調解這兩個集合，一種很棒的技巧是確保兩者都擁有所有的數據。我們分別計算出這兩個集合中所有元素的和，那麼一個是 6，另一個是 10 。如果我們在左邊這個集合中，我們想要跟右邊這個集合同步，於是我們說：“這是我這個集合內元素的和，是 6 。我們取兩個集合的差值，就是 10 - 6 = 4，這就是我這邊缺失的元素啦”。這當然很棒，而且基本上只是在做減法。但是，這隻對相差一個元素的情形有效。只要相差不止一個元素，那就行不通了。但這時候，我們又有另一種技巧。
假設我們想要編碼兩個差值，我們可以將所有元素的簡單和放在數組中 ——— 這就是我們的數組，數組的第一個元素是集合中所有元素的簡單和，第二個元素則是集合內所有元素的平方和。這都是基本的數學。這個數組就是我們要傳遞給其他人的東西。現在要調和兩個差值，是原來的兩倍。我們可以把這兩個差值放在一起：“第一個差值是元素簡單和的差值，第二個是元素平方和的差值”。回想我們學過的代數知識：這裡有兩個等式，有兩個未知數。那就是可以求解！
隨著差值的數量增加（階數也增加），它會逐步變成非常難解的問題。這就是用到 Berlekamp-Massey 算法的地方，它是非常高效的解法。
構造一個大草圖
對任意規模的集合，我們都可以應用這種方法。階數可以一直上升到 n 。顯然，階數越大，求解所需的時間越長。你必須編碼每一個條目，直到上升到獲得 n 階。但它確實有用，我們可以求出兩個集合之間的差異，不管涉及到的元素數量有多少。
Minisketch
Minisketch 庫：https://github.com/sipa/minisketch
這是一個 C++ 庫，由 Pieter Wuille 開發。它實現了 PinSketch 算法。它可以在各種架構和硬件上運行。它使用一些表，以優化求解根值的過程、節約時間。Pieter 還得出了一個純粹的 Python 實現，這本身就讓人驚訝。它只需要 500 行代碼，就可以運行各種足以塞爆我的腦袋的計算。而且代碼非常好讀，推薦你自己到 GitHub 頁面看看。
使用 Minisketch
但是，假設你像我一樣，只是個工程師。該如何在實踐中使用這種有趣的數學呢？就像這樣：
首先，我們初始化一個草圖（sketch），為此，我們需要知道我們想要編碼的數據的寬度。在這裡我們討論的是 64 比特寬。我們先填入數據的寬度，然後填入容量。容量就是我們希望能夠在兩個集合之間調解的差異元素的數量。如果我們認為兩個集合之間可能會相差 5 個元素，那麼我們可以選擇數值 8，也就是確保我們稍微超過。但我們也不想超出太多。然後，我們就把我們的集合數據輸進去，計算出綜合值。這個過程就像我們在 “構造一個大草圖” 一節說的。然後，我們將結果序列化，並從 Alice 傳輸到 Bob。
Bob 會經歷一個完全相同的流程。他建構自己的草圖，然後合併兩個草圖。這是非常有趣的，他需要選擇相同的數據寬度，但容量可以有所不同。數學原理使得你可以隨時截斷這個數組，從而兩者相等、你可以合併這兩個草圖。容量是稍微寬鬆的（並不等於差異元素的數量），但依然可以很好地解決。然後你使用 Berlekamp-Massey 算法，解出的結果就是這兩個集合之間相差的元素。
黑箱特性
這套數學在使用的時候有那些屬性？它支持從 2 比特寬到 64 比特寬的數據。真正酷的東西是，草圖在序列化之後的體積，也就是要在節點間傳輸的數據的體積，就是草圖的容量（也就是你想要求解的差異元素的數量）乘以數據寬度。如果你所選擇的草圖容量恰到好處，那麼你可以從數據中獲得 100% 的效率（被傳輸的數量體積恰好等於你抽取出來的缺失元素的體積）。
草圖序列化體積 = 草圖容量 * 數據寬度它讓我大吃一驚。不過還有一些別的事情要提醒。隨著你增加草圖的容量，調解的時間會（線性）上升。取決於你真正想要求解的差異元素的數量，調解時間會平方級上升。所以我們都希望約束差異元素的數量。你也不想在瞭解集合的差異有多大的時候就被沖垮。
侷限性
還有些記住幾個基本事項。在初始化草圖的時候，你不能編碼零個元素。別的數字都可以，就是不能為零。另一件事情是，確保每個草圖中的元素的數量、兩個集合件的差異不是非常大（不會超出草圖的容量），也是有用的。一般來說這不會是個問題，但假如你在一個草圖中有 50 個元素，而在另一個草圖中有 100 個元素，但你的草圖容量僅僅是 10 。那就無法求解了，因為容量根本不夠。不過，好的事情是，如果無法求解，它會給你一個警告，它會說“ 我找不出任何能夠滿足這個等式的多項式”。大部分時候都能做到這個效果。
Erlay
以下是關於我們將來如何使用這項技術的背景。比特幣網絡也面臨跟閃電 gossip 網絡極為相似的問題 —— 洪泛式的交易傳播無法很好地拓展。如果你聽過 Erlay 協議的話，你可能知道，那就是 Minisketch 的開發目標。Erlay 使用 Minisketch 來編碼交易池中的每一筆交易。然後你就可以跟比特幣網絡中的對等節點分享草圖。交易 ID 是 32 字節寬，但在 Minisketch 中我們只有 8 字節的數據寬度。所以我們需要將交易 ID 壓縮成一個體積更小的指紋，從而知道我們找出的差異元素代表著哪一筆交易。有一個哈希函數可以做到這件事。
節點還會協調 inventory 集合。這是另一個會讓事情複雜少許的因素。假設我們有一整個交易池，一種辦法是將每一筆交易都編碼進一個草圖、所有對等節點都要做這件事，然後都要求解、看看彼此的交易池有什麼差異。但這跟 Erlay 的工作原理不一致。Erlay 做的事情是，節點跟蹤與自己溝通的每一個對等節點，然後節點表示 “自我們上一次通信以來，已經過去 15 秒啦，我把我想要告訴你、但還沒告訴你的事情列了個清單（inventory）。這是我希望告訴你的 5 件事。”與此同時，你的對等節點 Bob 也做完全相同的事情，但也許他收集了 7 件事。Erlay 不會要求編碼交易池中的交易（可能有幾千筆交易），而只會要求編碼這 5 筆交易和 7 筆交易。我們調和兩者，也許會發現它們之間只有 3 個差異。一旦調解完成，這些 inventory 集合就會清空，然後兩個對等節點進入下一個輪次：記錄接下來 15 秒內發生的新鮮事。
閃電網絡 Gossip vs. 比特幣交易轉發
比特幣網絡在交易轉發上面臨的問題跟閃電網絡 Gossip 是極為相似的，但也有少許不同。其一，任何時候，你想要用短哈希函數來產生 64 比特的指紋，都要擔心碰撞問題。有些人可能會利用這一點，反覆嘗試，找出會產生相同指紋的交易 ID（本身是一個哈希值）。這就成了一個拒絕服務攻擊界面。這的確讓人心生顧慮。此外，是對隱私交易的時序分析（timing analysis）。在 gossip 中，不需要隱藏什麼，因為所有信息都天然是公開的。此外，我們有一種小技巧，從而可以不使用哈希函數。我們不僅有一種數據類型，我們想轉發的消息有 3 種類型。
在 Gossip 中應用
這些消息有 channel_update、node_announcement 和 channel_announcement 三種類型。channel_announcement 包含了關於手續費、通道使用狀態（激活或禁用）、可支持的最大 HTLC 數額等等信息。這可能構成了 gossip 網絡流量的 97%，這是很大的鼻涕，所以我們想要更加高效。前面的兩種消息（channel_update、node_announcement）只有兩個星期的有效期，所以它們會被反覆廣播。
挑戰
我們的挑戰是，我們要編碼所有 3 種消息類型。我們只能使用 8 個字節，但我們有個工具，是 “短通道 ID（SCID）”。這是將一條通道與區塊鏈上的注資交易關聯起來的信息。區塊鏈上的每一筆交易都是獨一無二的。這就是我們可以使用的很棒的捷徑。在 node_announcement 中不包含任何關聯到該節點的通道，所以它難以使用短通道 ID。理想情況下，我們會引用節點 ID，也就是節點的公鑰。但是公鑰也有 32 字節寬，所以我們不得不哈希它，或者做別的什麼處理。
編碼方案
實際上，在編碼這些信息時，我們可以使用這些數據：區塊高度、交易索引、輸出索引，這是短通道 ID。我們可以通過表明 “該節點的最老通道”、指出該節點在通道哪一邊，來引用一條節點宣告消息。這樣我們就有了一種方法來連貫地定位我們討論的是哪個節點。這通常來說就是 8 個字節的數據，而且我們就要嘗試把它塞進 8 個字節裡面。我們所做的不過是削去我們並不需要的少量比特。如果一個區塊只包含 32000 筆交易，那這可能就夠用了。如果你要給一條閃電通道注資，注資交易不太可能會有 1000 個輸出。我們已經節約了一些字節，因此，有空間留給別的信息，比如消息的類型，以及該節點在通道的哪一邊。這就是我們用恰好 64 個比特來定位我們要傳播的是哪種 gossip 消息的方法。最後，我們還有時間戳。對於那些定期發送的消息，我們需要知道哪一條更新，哪一條更舊。有一些比特能夠區分它們會帶來幫助。
集合調解的好處
這有什麼吸引人的呢？簡短的回答是：我們可以節約至少 60% 的 gossip 帶寬。完成這些工作之後，我們就可以跟更多對等節點溝通。跟更多節點溝通是非常好的事情，因為這能提高 gossip 傳播的可靠性。尤其是，節點宣告消息在過去飽經磨難，因為對另外兩種消息，有一些簡單的啟發法可以分辨你是否錯過了它們。對通道更新消息，我們已經在開頭的案例中看到了，在最壞情況下，我們的支付路徑會失敗，而報錯的包裹就會帶來更新，我們可以得到反饋。但節點宣告消息呢，它告訴了你該節點的 IP 地址。如果該節點的 IP 地址改變了，而你沒有看到，那你可能再也無法連接到它。這是非常糟糕的，而且有望能從增強的可靠性中獲得真實的好處。
下一步呢？
我還有幾個懸而未決的問題。其中一個問題是，我們可以維護全局草圖，也可以採用對應不同對等節點的 inventory 集合。這兩種方案都有各自的論據。
還有一件事是，我們在接收 gossip 消息時也有速率限制。如果我們對 gossip 消息的速率限制非常嚴格可以極大地減少我們的草圖容量。對於選擇性使用這種集合調解功能的實現來說，如果人們能夠對以什麼時間尺度來限制速率達成一致，那就太好了。我傾向於使用區塊高度。我正在努力說服大家。如果我能將每一條 gossip 消息都跟當前的區塊高度關聯起來；比如說，每一個區塊收取一條 gossip 消息，或者每 100 個區塊收取一條，等等。這是非常容易驗證的，因為你已經在運行全節點了。
最後，從長遠來看，我們真的希望在 gossip 中擺脫短通道 ID，因為它確實會洩露隱私。你肯定不想公開你所有的未花費交易輸出。現在我們還完全沒有準備好，然而一旦開始這樣做，就會走向對應不同對等節點的 inventory 集合方案。這可能已經指明瞭我們當前應該選擇什麼。
結論
Gossip 消息讓我們能夠構建對整個閃電網絡的視圖並找出路徑。Minisketch 真的很酷，大家都應該去看看。希望我們能夠利用它來提高閃電網絡 gossip 消息的可靠性。
（完）
