精通閃電網路

到目前為止，我們已經研究了幾種作為閃電網路一部分的技術，並且看到了它們作為 BOLT 標準一部分的確切規範。你可能會驚訝地發現路徑尋找不是 BOLT 的一部分！

這是因為路徑尋找不是需要不同實現之間任何形式的協調或互操作性的活動。正如我們所見，路徑由發送者選擇。即使路由細節在 BOLT 中有詳細規定，路徑發現和選擇完全留給發送者。因此，每個節點實現可以選擇不同的策略/演算法來尋找路徑。事實上，不同的節點/客戶端和錢包實現甚至可以競爭，並將其路徑尋找演算法作為差異化的亮點。

要選擇最佳路徑，我們必須首先定義「最佳」是什麼意思。可能有許多不同的標準，例如：

所有這些標準在某種程度上都是可取的，選擇在多個維度上都有利的路徑不是一件容易的事。像這樣的最佳化問題可能太複雜而無法解決「最佳」解決方案，但通常可以解決最優解的某種近似值，這是好消息，因為否則路徑尋找將是一個棘手的問題。

閃電網路中的路徑尋找屬於數學中 圖論 的一般類別，以及電腦科學中 圖遍歷 的更具體類別。

像閃電網路這樣的網路可以表示為一種稱為 圖 的數學結構，其中 節點 通過 邊（相當於支付通道）相互連接。閃電網路形成一個 有向圖，因為節點是 不對稱 連接的，因為通道餘額在兩個通道合作夥伴之間分配，付款流動性在每個方向上都不同。在其邊上具有數值容量約束的有向圖稱為 流網路，這是一種用於優化運輸和其他類似網路的數學結構。當解決方案需要在最小化成本的同時實現特定流量時，可以使用流網路作為框架，這被稱為最小成本流問題（MCFP）。

為了更好地理解將聰從 A 點傳輸到 B 點的問題，我們需要更好地定義三個重要術語：容量、餘額和流動性。我們使用這些術語來描述支付通道路由付款的能力。

在連接 A←→B 的支付通道中：

網路（通過八卦公告）唯一知道的值是通道的總容量。該容量的某些未知部分作為每個合作夥伴的餘額分配。該餘額的某些子集可用於朝一個方向通過通道發送：

如果我們知道每個通道的確切通道餘額，我們可以使用在良好的電腦科學課程中教授的任何標準路徑尋找演算法來計算一條或多條付款路徑。但我們不知道通道餘額；我們只知道總通道容量，這是由節點在通道公告中宣傳的。為了使付款成功，通道的發送側必須有足夠的餘額。如果我們不知道容量如何在通道合作夥伴之間分配，我們就不知道我們嘗試發送付款的方向上是否有足夠的餘額。

餘額不在通道更新中宣告有兩個原因：隱私和可擴展性。首先，宣告餘額會降低閃電網路的隱私性，因為它將允許通過對餘額變化的統計分析來監視付款。其次，如果節點（全域地）在每次付款時宣告餘額，閃電網路的擴展性將與向所有參與者廣播的鏈上比特幣交易一樣糟糕。因此，餘額不被宣告。為了在餘額不確定的情況下解決路徑尋找問題，我們需要創新的路徑尋找策略。這些策略必須與使用的路由演算法密切相關，即基於源的洋蔥路由，其中發送者有責任通過網路找到一條路徑。

不確定性問題可以用數學方式描述為 流動性範圍，根據已知資訊指示流動性的下限和上限。由於我們知道通道的容量，並且我們知道通道儲備餘額（每端允許的最小餘額），流動性可以定義為：

我們的通道流動性不確定性範圍是最小和最大可能流動性之間的範圍。這對網路來說是未知的，除了兩個通道合作夥伴。然而，正如我們將看到的，我們可以使用從付款嘗試返回的失敗 HTLC 來更新我們的流動性估計並減少不確定性。例如，如果我們收到一個 HTLC 失敗代碼，告訴我們一個通道無法完成一個小於我們對最大流動性估計的 HTLC，這意味著最大流動性可以更新為失敗 HTLC 的金額。簡單來說，如果我們認為流動性可以處理 N 聰的 HTLC，而我們發現它無法傳遞 M 聰（其中 M 更小），那麼我們可以將我們的估計更新為 M–1 作為上限。我們試圖找到天花板並撞上了它，所以它比我們想像的要低！

通過圖找到路徑是現代電腦可以相當高效地解決的問題。如果邊的權重都相等，開發人員主要選擇廣度優先搜尋。在邊的權重不相等的情況下，使用基於 Dijkstra 演算法的演算法，例如 A*（讀作「A-star」）。在我們的情況下，邊的權重可以代表路由費用。只有容量大於要發送金額的邊才會被包含在搜尋中。在這種基本形式中，閃電網路中的路徑尋找非常簡單直接。

然而，通道流動性對發送者來說是未知的。這將我們簡單的理論電腦科學問題變成了一個相當複雜的現實問題。我們現在必須在只有部分知識的情況下解決路徑尋找問題。例如，我們懷疑哪些邊可能能夠轉發付款，因為它們的容量看起來足夠大。但我們無法確定，除非我們嘗試一下或直接詢問通道所有者。即使我們能夠直接詢問通道所有者，在我們詢問其他人、計算路徑、構建洋蔥並發送它的時候，他們的餘額可能已經改變。我們不僅資訊有限，而且我們擁有的資訊是高度動態的，可能在任何時候在我們不知情的情況下改變。

閃電節點中實現的路徑尋找機制是首先創建一個候選路徑列表，通過某種函數進行過濾和排序。然後，節點或錢包將在試錯迴圈中探測路徑（通過嘗試傳遞付款），直到找到成功傳遞付款的路徑。

雖然盲目探測不是最優的，留有很大的改進空間，但應該注意到，即使是這種簡單的策略對於較小的付款和連接良好的節點也出奇地有效。

大多數閃電節點和錢包實現通過對候選路徑列表進行排序/加權來改進這種方法。一些實現按成本（費用）或成本和容量的某種組合對候選路徑進行排序。

正如你從 通道圖 中看到的，Selena 不知道任何通道的餘額。她的初始通道圖包含最高程度的不確定性。

但是等等：Selena 確實知道 一些 通道餘額！她知道她自己的節點與其他節點連接的通道的餘額。雖然這看起來不多，但它實際上是構建路徑的非常重要的資訊——Selena 知道她自己通道的實際流動性。讓我們更新通道圖以顯示這些資訊。我們將使用「?」符號來表示未知餘額，如 帶有已知和未知餘額的通道圖 所示。

雖然「?」符號看起來很不祥，但缺乏確定性與完全無知不同。我們可以 量化 不確定性，並通過用我們嘗試的成功/失敗 HTLC 更新圖來 減少 它。

不確定性可以被量化，因為我們知道最大和最小可能的流動性，並且可以計算更小（更精確）範圍的機率。

一旦我們嘗試發送 HTLC，我們就可以了解更多關於通道餘額的資訊：如果我們成功，那麼餘額 至少 足以傳輸特定金額。同時，如果我們收到「臨時通道失敗」錯誤，最可能的原因是特定金額的流動性不足。

為了量化通道流動性的不確定性，我們可以應用機率論。付款傳遞機率的基本模型將導致一些相當明顯但重要的結論：

雖然這些可能很明顯，但它們有重要的影響，特別是對於多部分付款的使用（見 多部分付款）。數學並不難理解。

讓我們使用機率論來看看我們如何得出這些結論。

首先，讓我們假設容量為 c 的通道在一側有一個未知值在 (0, c) 範圍內的流動性，即「0 到 c 之間的範圍」。例如，如果容量是 5，那麼流動性將在 (0, 5) 範圍內。現在，從這裡我們看到如果我們想發送 5 聰，我們成功的機會只有 1/6（16.66%），因為我們只有在流動性恰好是 5 時才會成功。

更簡單地說，如果流動性的可能值是 0、1、2、3、4 和 5，這六個可能值中只有一個足以發送我們的付款。繼續這個例子，如果我們的付款金額是 3，那麼如果流動性是 3、4 或 5，我們就會成功。所以我們成功的機會是 3/6（50%）。用數學表示，單個通道的成功機率函數是：

其中 a 是金額，c 是容量。

從方程式中我們看到，如果金額接近 0，機率接近 1，而如果金額超過容量，機率為零。

換句話說：「較小的付款成功傳遞的機會更大」或「較大容量的通道為我們提供特定金額的更好傳遞機會」以及「你無法在容量不足的通道上發送付款」。

現在讓我們考慮通過由多個通道組成的路徑成功的機率。假設我們的第一個通道有 50% 的成功機會（P = 0.5）。然後如果我們的第二個通道有 50% 的成功機會（P = 0.5），直覺上我們的整體機會是 25%（P = 0.25）。

我們可以將此表示為一個方程式，將付款成功的機率計算為路徑中每個通道機率的乘積：

其中 P_i 是通過一條路徑或通道成功的機率，P_payment 是通過所有路徑/通道成功付款的整體機率。

從方程式中我們看到，由於通過單個通道成功的機率總是小於或等於 1，通過多個通道的機率將 呈指數下降。

換句話說，「你使用的通道（跳數）越多，成功的機會越低。」

接下來，我們的發送者將根據從中間節點收到的 channel_update 訊息向圖添加資訊。提醒一下，channel_update 包含關於通道和通道合作夥伴之一期望的豐富資訊。

在 通道圖費用和其他通道指標 中，我們看到 Selena 如何根據來自 A、B、X 和 Y 的 channel_update 訊息更新通道圖。請注意，通道 ID 和通道方向（包含在 channel_flags 中）告訴 Selena 這個更新指的是哪個通道和哪個方向。每個通道合作夥伴八卦一條或多條 channel_update 訊息來宣告他們的費用期望和關於通道的其他資訊。例如，在左上角我們看到 Alice 為通道 A—​B 和方向 A 到 B 發送的 channel_update。通過這個更新，Alice 告訴網路她將收取多少費用來通過該特定通道將 HTLC 路由到 Bob。Bob 可能會為相反方向宣告一個通道更新（未在此圖中顯示），具有完全不同的費用期望。任何節點都可以隨時發送新的 channel_update 來更改費用或時間鎖期望。

費用和時間鎖資訊非常重要，不僅作為路徑選擇指標。正如我們在 洋蔥路由 中看到的，發送者需要在每一跳添加費用和時間鎖（cltv_expiry_delta）來製作洋蔥。計算費用的過程是從接收者到發送者 向後 沿著路徑進行的，因為每個中間跳期望傳入的 HTLC 具有比他們將發送給下一跳的傳出 HTLC 更高的金額和到期時間鎖。因此，例如，如果 Bob 想要 1,000 聰的費用和 30 個區塊的到期時間鎖增量來向 Rashid 發送付款，那麼該金額和到期增量必須添加到 來自 Alice 的 HTLC 中。

同樣重要的是要注意，通道必須具有不僅足夠付款金額而且足夠所有後續跳的累計費用的流動性。即使 Selena 到 Xavier 的通道（S→X）有足夠的流動性用於 1M 聰的付款，一旦我們考慮費用，它 就沒有 足夠的流動性了。我們需要知道費用，因為只有具有 付款和所有費用 足夠流動性的路徑才會被考慮。

Selena 嘗試第一條路徑（S→A→B→R）。她構建洋蔥並發送它，但收到 Bob 節點的失敗代碼。Bob 報告了 temporary channel failure，並帶有 channel_update 識別通道 B→R 為無法傳遞的通道。這次嘗試如 路徑 #1 嘗試失敗 所示。

現在 Selena 嘗試第四條候選路徑（S→A→B→X→Y→R）。這是一條更長的路徑，將產生更多費用，但它現在是傳遞付款的最佳選擇。

幸運的是，Selena 從 Alice 收到 update_fulfill_htlc 訊息，表示付款成功，如 路徑 #4 嘗試成功 所示。

MPP 不是用戶會選擇的東西，而是一種節點路徑尋找和付款傳遞策略。相同的基本步驟被實現：創建圖、選擇路徑和試錯迴圈。區別在於，在路徑選擇期間，我們還必須考慮如何拆分付款以優化傳遞。

在我們的例子中，我們可以看到使用 MPP 可以對我們的路徑尋找問題進行一些直接的改進。首先，我們可以利用 S→X 通道，它已知流動性不足以傳輸 1M 聰加上費用。通過在該通道上發送較小的部分，我們可以使用以前不可用的路徑。其次，我們有 B→R 通道的未知流動性，它不足以傳輸 1M 金額，但可能足以傳輸較小的金額。

多部分付款導致付款傳遞的試錯迴圈有所修改。因為我們在每次嘗試中嘗試多條路徑，我們有四種可能的結果：

在第二種情況下，一些部分失敗並返回錯誤，一些部分成功，我們現在可以 重複 試錯迴圈，但 只針對剩餘金額。

例如，假設 Selena 有一個更大的通道圖，有數百條可能的路徑到達 Rashid。她的路徑尋找演算法可能找到一個由 26 個不同大小的部分組成的最佳付款拆分。在第一輪嘗試發送所有 26 個部分後，其中 3 個部分失敗並返回錯誤。

如果這 3 個部分包含，比如說 155k 聰，那麼 Selena 將重新開始路徑尋找工作，只針對 155k 聰。下一輪可以找到完全不同的路徑（針對 155k 的剩餘金額進行優化），並將 155k 金額拆分成完全不同的拆分！

此外，Selena 的節點將使用從第一輪的成功和錯誤中收集的資訊來更新通道圖，以找到第二輪的最優路徑和拆分。

假設 Selena 的節點計算出發送 155k 剩餘金額的最佳方式是 6 個部分，拆分為 80k、42k、15k、11k、6.5k 和 500 聰。在下一輪中，Selena 只收到一個錯誤，表示 11k 聰部分失敗了。Selena 再次根據收集的資訊更新通道圖，並再次運行路徑尋找以發送 11k 剩餘金額。這一次，她成功了，分別用 6k 和 5k 聰的 2 個部分。

這個使用 MPP 發送付款的多回合範例如 使用 MPP 在多回合中發送付款 所示。

最後，Selena 的節點使用 3 回合的路徑尋找將 1M 聰分成 30 個部分發送。