改進的超額抵押高吞吐量多路徑支付方案

摘 要：在鏈下支付中，多路徑支付較單路徑支付在成功率和交易時延上存在顯著差異。盡管Spear方案通過超額抵押顯著提升了多路徑支付的性能，但過多的抵押資金鎖定可能對網絡資金流動性造成重大影響。為解決這一問題，提出了一種改進的超額抵押高吞吐量多路徑支付方案，通過最大流算法和逼近理想解排序法優化大額支付的路徑選擇和資金分配問題。實驗結果顯示，相較于其他四種經典多路徑支付方案，本方案在相同性能下減少了8%～16%的超額抵押資金，有效降低了抵押資金需求，增強了網絡資金流動性。

關鍵詞：區塊鏈；可擴展性；支付通道網絡；超額抵押；路徑選擇

中圖分類號：TP399 文獻標志碼：A 文章編號：1001-3695（2024）11-005-3239-06

doi：10.19734/j.issn.1001-3695.2024.02.0059

Improved over-collateralized high-throughput multi-path payments scheme

Liu Ya^1?， Liu Xuelin¹， Zhao Fengyu²， Qu Bo³

（1.School of Optical-Electrical amp; Computer Engineering， University of Shanghai for Science amp; Technology， Shanghai 200093， China; 2. Dept. of Information amp; Intelligence Engineering， Shanghai Publishing amp; Printing College， Shanghai 200093， China; 3. Guangdong University of Science amp; Technology， Dongguan Guangdong 523083， China）

Abstract：In off-chain payments， multi-path payments show a significant gap in both success rates and transaction latency compared to single-path payments. Although the Spear scheme significantly enhanced the performance of multi-path payments through over-collateralization， excessive locking of collateral funds may have a significant impact on network liquidity. To address this issue， this paper proposed an improved over-collateralized high-throughput multi-path payment scheme， optimizing path selection and fund allocation for large payments using maximum flow algorithm and technique for order preference by similarity to ideal solution. Experimental results show that compared to four other classic multi-path payment schemes， the proposed scheme reduces over-collateralized funds by 8%～16% under similar performance， effectively reducing collateral fund requirements and enhancing network liquidity.

Key words：blockchain; scalability; payment channel network; over-collateralization; path selection

0 引言

隨著互聯網和數字化技術的快速發展，商業活動和數據處理需求正逐漸轉向高速高效的數字化解決方案。在這種背景下，加密貨幣作為一種替代支付手段，受到了廣泛關注。區塊鏈^［1］ 作為加密貨幣的基礎支撐技術，能夠確保交易的匿名性和安全性，解決了無須依賴任何中央信任機構，開放網絡環境下的信任問題。但其高額的礦工費和緩慢的區塊確認時間使其存在很大局限性，阻礙了其廣泛應用。以比特幣^［2］ 為例，其每秒的處理能力僅限于七筆交易，一項交易的平均確認時間至少需要10 min。為了防止雙重支付，用戶至少需要等待六個連續區塊后才能確認，這與能夠每秒處理數萬筆交易的在線支付系統形成鮮明反差。此外，區塊的數據容量進一步制約了交易通過率和單位時間的交易總量，且交易雙方還必須為礦工支付一筆不菲的交易處理費用^［3］ 。針對區塊鏈的擴展性問題，研究者提出了側鏈、分片與鏈下支付網絡等解決方案，文獻［4～6］對區塊鏈中現有的可擴展性問題進行了研究和總結。

鏈下支付由于其高效性而受到廣泛關注，被認為是最有前景的擴展性解決方案。鏈下支付通過支付通道實現，這些通道建立在區塊鏈之外，無須修改區塊鏈底層的共識協議。交易雙方開啟通道并存儲資金以進行多次交易，每筆交易無須上傳主鏈，只有在通道建立、關閉或交易發生爭議時才需要上鏈處理。通道中的雙方在不犧牲安全性的情況下在鏈下進行快速、低成本的小額交易，減輕了區塊鏈網絡的負擔。相互連接的支付通道形成了支付通道網絡（payment channel network，PCN），沒有直接通道的用戶可以使用已有的通道進行多跳交易。這種多跳交易一般通過多簽名合約，如哈希時間鎖合約（hashed time lock contract，HTLC）完成。常見的PCN有比特幣的閃電網絡^［7］ 和以太坊的雷電網絡^［8］ 。閃電網絡是當前最受歡迎且應用廣泛的鏈下支付網絡，也是本文研究的重點。根據The Block Research的數據^［9］，截至2023年6月，閃電網絡的容量已達5 490 BTC（1.28億美元），較2022年增長了63%。2021年9月，薩爾瓦多成為第一個采用比特幣作為法定貨幣的國家，推動了比特幣在全球的應用。Twitter等公司也紛紛采用閃電網絡，促進了比特幣支付的普及。2023年，Lightspark公司推出了比特幣閃電網絡平臺，致力于推動企業加入這一網絡。閃電網絡自2018年建立以來一直呈現強勁增長態勢^［10］，逐漸融入人們的日常生活。然而隨著閃電網絡的迅速發展，網絡負載急劇增加，網絡交易吞吐量嚴重降低。其隱私保護措施是造成這一問題的主要原因。在支付通道網絡中，通道的資金總量是公開的，但為了保護用戶隱私，各用戶在通道中的資金是私有的，僅通道中的雙方知曉。由于發送方無法知曉中間節點的資金狀況，交易可能因中間節點資金不足而失敗，導致交易回滾并需重新選擇路徑進行交易。最近的一項研究表明，在閃電網絡中成功發送5美元付款的機會約為50%^［11］。因此，進一步提高PCN中的交易成功率是非常必要的。

為了縮短交易時間并提高成功率，尤其是針對大額交易，可以采用資金分割策略，將一筆大額交易分散至多條路徑上進行，以降低單個路徑上的資金需求，從而提升交易的成功率。這種交易策略稱為多路徑支付，有助于提高大額交易的成功率，但同時也延長了交易總時間，因為需要等待所有路徑上的交易都成功完成。若任一路徑交易失敗，整個交易都將失敗并需重新選取路徑進行交易。在鏈下支付網絡中大額交易比小額交易的成功率明顯更低，大約只有45%。為確保支付通道網絡的經濟可行性，研究高吞吐量的大額交易方案是必要的，這將大大減少中間節點鎖定資金的時間，增加中間節點獲得的交易轉發費用，鼓勵更多用戶參與。交易成功的前提是路徑上所有支付通道均有足夠的資金可供交易使用。因此，高效的多路徑支付路由方案一直受到研究者的廣泛研究。

Boomerang^［12］和Spear^［13］等方案利用超額抵押思想（交易時使用遠遠高出交易雙方原始交易資金的交易資金來進行交易）顯著提高了鏈下支付網絡的性能，但它們均存在路徑選擇隨意、資金分配不合理的問題，導致需鎖定更多資金、使用更多備用路徑進行交易。為解決此類問題，需要尋求更加高效的資金、路徑利用方式。最大流算法^［14］可確定路徑最大容量，從而減少備用路徑以及超額資金的使用，提高支付效率。逼近理想解排序法（tecknique for order preference by similarity to ideal solution，TOPSIS）是一種常用的多目標決策分析方法，其根據原始數據和數學模型評估候選對象，綜合考慮多個評估因素，避免主觀偏見的影響，使決策更加客觀和科學，是一種有效的決策支持工具。綜合來看，TOPSIS法可以科學、客觀評估候選路徑，優化路徑選擇，從而實現更加快速、高效的交易，提升網絡交易性能，是解決鏈下支付網絡現存路徑選取問題的科學方案。

針對上述問題，本文提出了一種高效的鏈下多路徑支付方案MPST（multi-path payment scheme based on TOPSIS），旨在解決超額抵押多路徑支付中的路徑選擇和大額支付分割問題，提升多路徑支付的效率。MPST適用于PCN中多路徑支付的各種應用場景，包括但不限于前述提及的使用案例。MPST使用最大流算法找出每條候選路徑可轉移的最大資金量，并根據路徑可轉移的最大資金量和節點數，采用TOPSIS法評估路徑得分，隨后基于得分對路徑進行排序，自動選擇得分最高的可行路徑集。在交易中為每條路徑分配最佳支付金額，充分利用資金以降低超額抵押、減少備選路徑。其次，研究了超額抵押資金和原始交易資金的最佳平衡點，研究發現，在使用冗余路徑進行交易時，當交易總金額達到原始交易金額的1.4～1.6倍時（不同的多路徑支付方案存在差異），可達到較高的成功率和較低的交易完成時間，此時再增加冗余路徑對交易的影響微乎其微，反而會浪費節點資源。最后，將MPST和四種經典多路徑支付方案進行對比，結果表明通過適度增加冗余路徑，在成功率、交易延遲和通道利用率方面達到與其他方案相同的性能甚至更優的情況下MPST將超額抵押資金下降了8%～16%，對于大額支付來說，這種效果是顯著的。這表明MPST有效降低了資金抵押需求，實現了資金利用更佳，顯著提升了網絡的資金流動性。

1 相關工作

當前，越來越多的學者提出了各種改進的鏈下支付通道網絡路由方案，這些方案旨在優化鏈下支付通道網絡的吞吐量，并降低交易延遲或減少交易費用。2016年Prihodko等人^［15］提出了第一個分布式路由方案Flare協議，該方案使用地標路由，其中只有一些節點存儲整個網絡的路由表，其余節點只知道如何到達其中一個地標節點，用戶將付款發送到網關節點，網關節點處理其余的事務。然而Flare使用靜態路由方法，不考慮動態信道容量，且該方案的吞吐量相對較低。為了進一步減少路徑查找中的通信開銷，2017年Malavolta等人^［16］提出了SilentWhispers，該方案以地標為中心進行路由，周期性地執行廣度優先搜索以找到從地標到發送方和接收方之間的最短距離。為了繼續完善路由效率、保護支付隱私，2018年Roos等人^［17］提出了基于嵌入式的路由方案SpeedyMurmurs，旨在縮短平均路徑長度，并在支付成功率、穩定性等方面作出了改善，但該方案仍沒有考慮通道余額的動態平衡。2019年Wang等人^［18］根據網絡中加密貨幣交易重尾分布和高重復性的特征，提出了一種新的動態路由解決方案Flash，將支付分成了大象支付和老鼠支付來進行不同處理，降低了路由探測開銷，但該方案的成功率仍有待提升。為了優化交易費用，同年Zhang等人^［19］提出了CheaPay算法，該算法在時間和可行性約束的條件下，以最小化交易費用為目標對支付通道路由協議進行優化，該方案大幅降低了交易費用，但該方案僅考慮交易費用最小，未考慮路由中的其他情況，局限性較大。考慮到鏈下支付網絡的通道平衡，2020年Sivaraman等人^［20］提出了一種高吞吐量的路由算法Spider將分組交換路由技術應用于PCN，將支付分成微支付，該方案還采用擁塞控制和best-effort模型，通過選擇特定的路徑來重新平衡通道以此提高支付吞吐量，但是動態平衡并不是萬能的，會帶來較大的平衡開銷。為了提高多路徑支付的性能，2020年Bagaria等人^［12］ 提出了Boomerang，這是第一種使用超額抵押資金來解決多路徑支付中延遲和吞吐量問題的多路徑支付方式，其很大程度解決了多路徑支付中的延遲和吞吐量等問題，超額抵押的主要挑戰是保護發送方的資金安全，Boomerang使用密鑰共享使發送方能夠在接收方透支時收回付款，保證了發送方資金安全，但是其合約等待時間為HTLC合約的兩倍，并且每條路徑交易的資金需要交易雙方提前商定且是均衡的，這對交易雙方造成了極大的限制。針對PCN高并發場景，2021年葛鐘慧等人^［21］提出了一種支持高并發的多人鏈下支付方案，該方案在原有多人通道框架內改進了通道內狀態更新機制，將通道狀態依據支付串行更新變為并行更新，并引入支付有效期來減輕網絡時延與高并發支付場景對支付有效性的影響，從而實現通道內支付處理效率的提升和對鏈下高并發支付場景的支持，但該方案引入了監督節點，增強了網絡的中心性。2021年Rahimpour等人^［13］進一步改進Boomerang提出了Spear，該方案通過對HTLC增加了一個發送方密鑰就可以做到超額抵押支付并保護發送方資金安全，Spear具有更低的延遲，合約的最大鎖定時間是Boomerang的一半，計算量相對Boomerang也有很大的改善，并且Spear中交易資金可以是任意的，也不需要交易雙方提前商定，這為支付提供了更大的靈活性，但該方案的抵押資金仍然較多，需要進一步改善。2022年Qian等人^［22］ 提出了支持支付證明的多路徑支付方案，并達到了較高的路由效率，但該方案未對其他性能指標作出說明。為解決鏈下網絡中現存的路由問題并提升，2023年Liu等人^［23］ 提出了一種基于權值計算的均衡路由選擇方案BRBW。綜合考慮通道容量、手續費、路徑長度等因素，給用戶提供了更多路由選擇，但該方案多路徑交易的成功率仍有待提升。

2 系統模型

2.1 網絡模型

本文將閃電網絡建模為有向圖G=（V，E），其中V是網絡中的節點集，E是網絡中的通道集。每個節點v_i∈V表示網絡中的用戶，e_u，v∈E表示網絡中的支付通道。對于任意通道e_u，v，設b_u，v表示節點u的通道余額，b_v，u表示節點v的通道余額，c_u，v表示通道e_u，v的通道容量，因此有c_u，v=b_u，v+b_v，u，其中c_u，v是公開信息，而b_u，v是節點u的私有信息，b_v，u是節點v的私有信息。為了簡單起見，邊集合E在任何時候都是非負的。fee^m_u，v表示節點u通過通道e_u，v轉發m資金的交易到v收取的手續費。 ξ_u，v表示節點u等待節點v提供合約原像的最大可容忍時間。

2.2 交易模型

鏈下支付通道網絡的交易模型主要描述了在鏈下支付網絡中進行交易的基本過程和規則。用戶的交易需求可以描述成一個三元組 R=（s，r，m），其中s和r分別表示交易的發送方與接收方，m表示此次交易的金額。在支付通道網絡中，交易請求R需要通過一組網絡中的可用路徑 p_i=v_s→v_i→…→v_r完成，其中p_i∈P。在支付通道網絡中一個交易請求能否轉發成功，應取決于以下約束條件：

a）通道容量約束：在支付通道網絡中，每個支付通道可以被視為一個有向邊，其容量代表該通道可以處理的最大支付額度。假設有一個支付通道e_u，v，其容量為c_u，v，通過該通道進行的兩個有向支付流f_u，v和f_v，u之和必須滿足通道容量約束，如下所示。

∑f_u，v+∑f_v，u≤c_u，v

?u，v∈p_i（1）

b）可行性約束：假設有一筆支付m，在使用路徑p_i進行交易時需要確保該路徑上所有的通道都有足夠的容量來處理該支付，即需要滿足以下條件：

∑fee^m_u，v+m≤c_u，v，?u，v∈p_i（2）

c）時間容忍約束：每一筆交易都需要考慮支付的時間限制。ξ_u，v表示節點u等待節點v提供合約原像的最大可容忍時間，Δ_u，v表示節點u收到節點v釋放合約密鑰間隔時間。那么對于每一筆支付都應該滿足

Δ_u，v≤ξ_u，v，?u，v∈p_i（3）

d）支付模型：假設路徑p_i轉移的資金為m_i，若此筆交易成功那么對于該路徑上所有的支付通道余額將發生以下變化：

b_u，v=b_u，v－（m_i+∑fee^m_iu，v），?u，v∈p_ib_v，u =b_v，u+（m_i+∑fee^m_iu，v）（4）

3 方案設計

3.1 MPST方案概述

本節重點介紹了MPST方案的工作原理。在MPST方案中，當發送方發起交易請求時，MPST首先使用廣度優先算法尋找發送方到接收方的可用路徑，并通過最大流算法計算出路徑的最大可轉移資金量，這一過程不斷迭代，直至發送方和接收方之間無可用路徑為止，然后返回路徑集和路徑相關信息。MPST綜合考量每條路徑的可轉移最大資金量和節點數，使用TOPSIS法評估路徑得分。最后，基于路徑得分對這些路徑進行降序排序，在交易時自動選擇得分最高的路徑集，并為每條支付路徑分配最佳交易金額，最大化資金利用，在保證高成功率和低交易延遲的情況下，降低超額抵押資金的使用。圖1詳細展示了MPST方案的基本框架，為讀者提供對該方案的直觀理解。

總的來說，該方案首先要最大化每條路徑的交易資金，當路徑交易金額越大，可能需要用到的交易路徑就越少，從而最大程度地節約不必要的資源浪費。其次在保證能轉移資金相同的情況下，選擇較短的路徑進行交易，從而相對減少了交易的等待時間，提高了交易吞吐量。可以建模為

滿足：max

∑p_i∈Pα_im_i

min

∑p_i∈Pα_iN_i

∑p_i∈Pm_i=kr

∑p_i∈Pα_im_i+α_ifee^m_iu，v≤α_ic_u，v

?u，v∈p_i（5）

其中：α_i為0或1表示該條路徑是否被選取；m_i表示路徑p_i能夠轉移的資金量；N_i表示路徑p_i的節點個數；k為大于1的常數；r表示交易的初始資金；fee^m_iu，v表示節點u轉移m_i資金至節點v收取的交易費；c_u，v表示通道e_u，v的通道容量。

3.2 搜索可用路徑

通道容量是多路徑支付方案的一個關鍵指標，因此當用戶發起交易請求時，如果多條路徑共享一個支付通道，僅僅依賴最短路徑可能會導致資源利用率嚴重不足。以圖2為例，假設節點A是發送方，節點D是接收方，其余節點為它們的中間節點，使用兩條路徑來進行交易。從節點A到D的兩條最短路徑p₁=A→B→C→D和p₂=A→E→C→D都包含了節點C到D的支付通道。這兩條路徑可以提供9個單位的總容量，但如果選擇其他互不相交的路徑，例如p₁=A→B→C→D和p₃=A→E→F→D，那么交易總資金量可以達到15。因此，為了更高效地利用通道容量，本研究在路徑選擇時采用了Spider中不相交路徑的策略。這種策略能夠在保證交易成功的同時最大化利用支付通道的容量，從而提高鏈下支付網絡的整體效率。

算法1體現了在網絡中搜尋可用路徑的過程。該算法接受網絡拓撲和支付請求R作為輸入，根據網絡拓撲和支付請求，使用廣度優先算法迭代地找到從發送方到接收方的所有可用路徑。在搜尋路徑的過程中，判斷當前路徑是否滿足信道容量和時間容忍約束可行性約束，滿足則加入路徑集合，不滿足則舍棄此路徑。如果在鏈下網絡中沒有可用的路徑，交易將返回空，否則返回一組可用路徑集合P={ p₁，p₂，p_i，…，p_n}，其中每個路徑p_i可以形式化為有序序列：p_i=v_s→v_i→…→v_r。其中，v_s、v_r和v_i分別表示路徑p_i上的發送方、接收方和中間節點。

算法1 搜尋可用路徑

輸入：網絡拓撲G；支付請求R=（s，r，m）。

輸出：候選路徑集P；通道容量C； 最大交易流集T_max。

P =1，t=0 // 初始化路徑集P、交易流t

C_{i， j} =∞，C～_{i， j}=∞ // 初始化通道i， j的容量矩陣與剩余容量矩陣

for {

p=Breadth-First-Search（G，C～_{i， j}，s，r） // 迭代搜索s到r的路徑

if p==0 then // 如果沒有可用路徑跳出循環

break

C_min=findMin（p） // 找到路徑p的瓶頸容量

t=t+C_min // 路徑p能交易的最大資金流

add t to T_max // 將t添加T_max

u=s

while u≠r do

v=p［u］ →next // 指向后一個鏈表節點

if C_{i， j}［u，v］=∞ then // 初次設置通道容量

C_{i， j}［u，v］=C［u，v］ C～_{i， j}［u，v］=C［u，v］

if C_{i， j}［v，u］=∞ then // 初次設置通道容量

C_{i， j}［v，u］=C［u，v］ C～_{i， j}［v，u］=C［u，v］

Cr_{i， j}［u，v］=Cr_{i， j}［u，v］－C_min

Cr_{i， j}［v，u］=Cr_{i， j}［v，u］+C_min

if tgt;0 amp;amp; ∑fee^t_u，v+t≤C_u，v：

add p to P // 添加路徑p到可用路徑集合P

}

return P，C_{i， j}，T_max

end

3.3 構建路徑得分

為了最大限度地減少由于路由選擇導致的節點資源浪費，降低節點間的不公平性，并在滿足約束條件的前提下選擇最優的交易路徑，本文提出了一種高效支付方案以解決路徑選擇和支付分割問題。具體而言，通過每條路徑的可轉移資金量和節點個數，本文采用了TOPSIS分析法來對所有候選路徑進行了深入分析，構建每條路徑的得分。路徑分析的步驟如下：

a） 數據正向化。

設收集到的路徑相關的所有數據記為X，其中的元素記為x_ij，對于本文中的兩個指標，路徑可轉移資金量x_i1越大越好，而路徑節點個數x_i2則是越小越好。為了簡化分析，首先需要對所有節點個數相關數據進行正向化處理：_i2=1/x_i2， 將其轉為效益型指標。

X=x₁₁x₁₂x₂₁x₂₂x₃₁x₃₂x_n1x_n2

正向化X=x₁₁₁₂x₂₁₂₂x₃₁₃₂x_n1n2

（6）

b）正向化矩陣標準化。

由于資金量和節點數是不同的度量單位，不能直接相加需要消除不同指標量綱的影響，將其進行標準化處理。對X中的每一項x_ij進行標準化，將標準化的矩陣記為Z。

X=x₁₁₁₂x₂₁₂₂x₃₁₃₂x_n1n2標準化Z=z₁₁z₁₂z₂₁z₂₂z₃₁z₃₂z_n1z_n2

（7）

其中：z_ij= x_ij∑ni=1x²_ij。

c）計算得分并歸一化。

經過正向化和標準化的修正之后，對路徑構建評分指標。首先，找出候選路徑集P中所有路徑可轉移資金量和節點數的最大值和最小值，然后計算每條路徑與最大值和最小值的距離。

最大值：

Z⁺=（max{z₁₁，…，z_n1}，max{z₁₂，…，z_n2}）=（ Z⁺₁，Z⁺₂）（8）

最小值：

Z^－=（min{z₁₁，…，z_n1}，min{z₁₂，…，z_n2}）=（ Z^－₁，Z^－₂）（9）

其中：Z⁺₁ 表示P中最多的可轉移資金量；Z⁺₂表示P中最小的路徑節點個數；Z^－₁表示P中最少的可轉移資金量；Z^－₂表示P中最大的路徑節點個數。

計算p_i與 Z⁺₁，Z⁺₂的距離：

D⁺_i=∑2j=1w_j（Z⁺_j－Z_ij）²（10）

計算p_i與 Z^－₁，Z^－₂的距離：

D^－_i=∑2j=1w_j（Z^－_j－Z_ij）²（11）

其中：由于可轉移資金量更為重要，在構建評分時根據優序圖法分析了每個指標的權重w_j，結合權重建構路徑得分，經過不斷調整，發現當w₁=0.75，w₂=0.25時效果最優。

d）評分構建。

由上述步驟，得到了所有候選路徑p_i與最優值的相對接近度，從而構建出所有路徑的得分。

C_i=D^－_iD⁺_i+D^－_i（12）

得到所有候選路徑p_i的得分集合：

C={C₁，C₂，…，C_n}（13）

最后，根據C_i大小對所有候選路徑p_i排序，C_i越大表明評價對象越接近最優值就越優。

3.4 多路徑支付

MPST使用超額抵押資金來進行交易，為了保證發送方資金安全，本文利用Spear中的方案實現了多路徑的轉發。發送方發起支付請求R（s，r，m），在得到支付請求R后，調用算法1來搜尋發送方s到接收方r的所有可用路徑P，并計算出每條候選路徑p_i的可轉移最大資金量m_imax，然后調用算法2構建出所有候選路徑得分，并返回有序路徑集P～，在交易時根據路徑集P～依次選擇路徑進行交易，路徑p_i將轉移m_imax的資金，發送方可使用多余路徑來快速完成交易。只要接收方收到了原始交易資金，交易完成，其余路徑的交易均被取消。

算法2 路由選取

輸入：可用路徑集合P；最大交易流集合T_max。

輸出：有序路徑集 P～。

initialize result， P～ // 初始化映射集合result和結果集P～

for p in P {

c_p=TOPSIS（P，T_max） /*調用TOPSIS計算各路徑與最優解的相似度*/

result.put（{p，c_p}） // 將各路徑相似度添加結果集

}

result.sort（（a，b）=gt; b［1］-a［1］） // 將結果集根據 c_p進行排序

for item in result { // 將路徑p有序地放到 P～

add item［0］ to P～

}

return P～ // 返回有序路徑集

end

4 實驗與分析

本文使用Cloth^［24］ 模擬器來進行實驗，該模擬器完全實現了閃電網絡所有功能，確保了實驗結果的可靠性。根據需求，本文對其進行了功能擴展，實驗數據來自該模擬器提供的真實的閃電網絡數據：2020年12月17日閃電網絡節點和通道的快照，當時網絡中有6 006個活躍節點和30 457個活躍通道。因此，模擬的節點和通道（連同它們的屬性：通道容量、基本和比例費用、最小HTLC策略和時間鎖策略）正是閃電網絡在該日期的節點和通道。然后對每個通道生成了一個均勻分布于0～1的隨機數，該隨機數對應于該通道的一個節點所擁有的通道容量的比例。由于網絡中的余額是保密的，為了保證隱私，未公開余額信息。考慮到鏈下網絡應該支持高支付吞吐量，平均支付率被設置為每秒100筆支付，總支付數設置為5 000。鑒于本文主要解決大額支付問題，因此選取了交易金額在10²～10⁵聰的交易來進行實驗。本節主要通過帶有超額抵押資金的Shortest、CheaPay、Flash和BRBW這四種經典多路徑支付方案探究了資金率（funds rate）和成功率、交易完成時間以及通道利用率之間的關系，并將其與MPST進行了對比。

funds rate=M_i/m_i=k（14）

其中：M_i表示第i筆交易的交易總資金；m_i表示第i筆交易的原始交易資金。

4.1 評估指標

本文主要探究了以下三個指標與funds rate間的關系。

a）成功率（success rate）：一輪支付中從發送方成功到達接收方交易的數量和總交易數量的比值。

b）交易完成時間（time taken for payment，TTP）：從發送方發起交易請求到交易成功到達接收方的時間間隔。

c）通道利用率（channel utilization rate）：一輪交易中參與交易轉發的通道數量與整個網絡中通道數量總和的比值。

4.2 實驗結果與結果分析

4.2.1 成功率

本節觀察了網絡中隨著funds rate變化，平均成功率的變化。如圖3所示，其中，CheaPay在選擇路線時追求交易費最少，Shortest在選擇路線時追求最短路徑，這限制了它們選擇路線的能力，導致其較低的成功率，而Flash和BRBW針對大額支付時有一定優化策略，因此有較高的成功率。隨著超額抵押資金的增長，這四個方案中交易的平均成功率也在不斷提高，成功率最高可達98%左右，這表明超額抵押資金對成功率具有正向影響。Shortest在funds rate=1.6左右時成功率趨于穩定，CheaPay在funds rate=1.57左右時成功率趨于穩定，Flash、BRBW均在funds rate=1.48左右時成功率趨于穩定，這表明此時增加超額抵押資金并不會對成功率產生影響，甚至可能對網絡產生負面影響。通過這一結果，用戶在使用超額抵押進行交易時，可根據實際需求來設置超額抵押的抵押資金量。而本文方案MPST在funds rate=1.4左右時成功率已經達到與他們相同的效果且趨于穩定，這表明MPST有效降低了超額抵押資金，在鎖定更少資金的情況下就可以達到較高的成功率，鎖定較少的資金意味著網絡有更高的資金流動性，減少了資金的閑置時間，降低了資金的機會成本，將會大大提高網絡吞吐量。

4.2.2 通道利用率

本節探究了網絡中平均通道利用率和funds rate的關系。對于鏈下支付通道網絡來說，網絡的通道利用率非常重要，通道利用率的高低對于支付通道網絡的有效運行至關重要。高通道利用率可以提高網絡的效率和吞吐量，同時也有助于降低交易的延遲時間。此外，高通道利用率還可以增加網絡的流動性，促進資金的快速流動，從而提高整個網絡的健壯性和可靠性。因此，維持良好的通道利用率對于支付通道網絡的穩定運行和用戶體驗至關重要。如圖4所示，隨著funds rate的增長，以下方案的通道利用率整體呈現上升趨勢。這是由于增加冗余路徑可以提高交易速度，更多的路徑意味著更多的選擇余地，從而有助于避免網絡擁堵和提高交易的成功率，使網絡中的資金流動更加靈活，有助于優化整個網絡的資源利用效率。而本文方案MPST的通道利用率在整個過程中明顯優于其他方案，在最好情況下MPST的通道利用率相對于其他方案提高了6%～9%，這主要由于MPST有效降低了超額抵押，釋放了更多可流動資金，減少了資金的閑置時間，從而帶來更高的交易效率和更快的資金流動，大大增強了網絡吞吐量，提高整個網絡的處理能力，使資金流動更加均衡和高效。需要說明的是，通道利用率并不總是隨著超額抵押資金的增多而上升，考慮極端情況下，當用戶使用遠遠超于原始交易資金的超額資金進行交易時，此時通道利用率將會明顯地急速下降。

4.2.3 交易完成時間

本節探究了網絡中平均交易完成時間和funds rate的關系。在鏈下支付網絡中，交易完成時間的重要性體現在其對交易確認速度、資金流動性和用戶體驗的影響。較短的交易完成時間可以提高交易的確認速度，降低資金的閑置時間，并改善用戶體驗。此外，快速的交易完成時間還有助于提高網絡的吞吐量和效率，從而增強整個支付網絡的性能和競爭力。如圖5所示，隨著冗余路徑的增長，交易完成時間持續縮短直至達到飽和。這是由于通過使用超額抵押，交易可以選擇更多的路徑來完成，從而降低了單一路徑擁堵的風險，提高了交易的成功率和速度。冗余路徑還可以提供備用選項，當某條路徑出現問題時，交易可以快速切換到其他路徑，減少了交易失敗的可能性，進而縮短了交易完成時間。因此，使用超額抵押有助于降低交易完成時間。

此外，由于Shortest算法致力于找尋一條最短的交易路徑完成支付，在剛開始時其交易完成時間最低。然而，由于其總是使用最短路徑，一些通道的資源被消耗殆盡，導致不得不重試失敗的交易，從而使其后面的交易時間下降緩慢。相比之下，MPST算法在初始時交易完成時間較高，但隨著冗余路徑的增長，其交易完成時間快速下降，最終達到最低。這是由于MPST通過最大化每條路徑的轉移資金量，提高每條路徑的利用率，降低了超額抵押資金，加快了網絡中資金的流動，并且有效減少了多余路徑的使用，進一步縮短了交易完成時間。

5 結束語

本文提出了一種高效的多路徑支付方案MPST，以解決多路徑支付中超額抵押帶來的問題。MPST利用最大流算法和TOPSIS分析法優化大額交易問題，有效降低了超額抵押資金。在真實的閃電網絡拓撲中，本文將MPST與四種經典多路徑支付方案進行了對比，重點探究了超額抵押資金與交易成功率、通道利用率和交易完成時間的關系，結果表明MPST在各項指標下均表現出了較好的性能，減少了8%～16%的超額抵押資金。這一對比分析全面展示了MPST在優化超額抵押多路徑支付方面的優異性。

然而，MPST未考慮網絡通道余額的動態性，可能導致其在選取路徑以及為路徑分配交易資金的時候無法及時適應網絡變化，從而影響支付通道的有效利用和交易成功率。此外，未考慮支付通道的動態變化也可能導致其無法充分利用新的高效支付通道，從而影響網絡的吞吐量和交易效率。因此，考慮支付通道的動態變化將是本方案未來工作中需要重點解決的問題之一。

參考文獻：

［1］王嘉瑤， 王婷， 袁文亮， 等. 分布式賬本技術的發展歷程研究綜述 ［J］. 計算機應用研究， 2023， 40（3）： 641-648. （Wang Jiayao， Wang Ting， Yuan Wenliang， et al. Review on development history of distributed ledger technology ［J］. Application Research of Computers， 2023， 40（3）： 641-648.）

［2］Nakamoto S. Bitcoin： a peer-to-peer electronic cash system ［R/OL］. （2008）. https：//bit-coin.org/bitcoin.pdf.

［3］Bitcoin historical feechart ［EB/OL］. （2011-04-14）. https：//bitinfocharts.com/compariso/bitcoin-median_transaction_fee.html.

［4］喻輝， 張宗洋， 劉建偉. 比特幣區塊鏈擴容技術研究 ［J］. 計算機研究與發展， 2017， 54（10）： 2390-2403. （Yu Hui， Zhang Zongyang， Liu Jianwei. Research on scaling technology of bitcoin blockchain ［J］. Journal of Computer Research and Development， 2017， 54（10）： 2390-2403.）

［5］潘晨， 劉志強， 劉振，等. 區塊鏈可擴展性研究： 問題與方法 ［J］. 計算機研究與發展， 2018， 55（10）： 2099-2110. （Pan Chen. Liu Zhiqiang， Liu Zhen， et al. Research on scalability of blockchain technology： problems and methods ［J］. Journal of Computer Research and Development， 2018， 55（10）： 2099-2110.）

［6］王鋒， 張強， 劉揚， 等. 從擴展性角度看區塊鏈 ［J］. 計算機應用研究， 2023， 40（10）： 2896-2907. （Wang Feng， Zhang Qiang， Liu Yang， et al. Research progress of blockchain from perspective of scalability ［J］. Application Research of Computers， 2023， 40（10）： 2896-2907.）

［7］Poon J， Dryja T. The bitcoin lightning network： scalable off-chain lightning network ［EB/OL］. （2016-01-14）. https：//lightning. network/lightn-ing-network-paper. pdf.

［8］The Raiden network ［EB/OL］. （2019）. https：//radien. network/.

［9］The Block. Co. Lightning network reaches all-time high in bitcoin capacity ［EB/OL］. （2023-02-06）. https：//www. theblock. co/post/208817/li-htning-network-reaches-all-time-high-in-bitcoin-capacity.

［10］Medium. Lightning network 2018 to 2023 and beyond ［EB/OL］. （2023-05-02）. https：//medium. com/coinmonks/lightning-network-2018-to-2023-and-beyond-9ea9359ada77.

［11］Sompolinsky Y， Zohar A. Secure high-rate transaction processing in bitcoin ［C］//Proc of the 19th International Conference on Financial Cryptography and Data Security. Berlin：Springer， 2015： 507-527.

［12］Bagaria V， Neu J， Tse D. Boomerang： redundancy improves latency and throughput in payment-channel networks ［C］ //Proc of the 24th International Conference on Financial Cryptography and Data Security. Cham： Springer， 2020： 304-324.

［13］Rahimpour S， Khabbazian M. Spear： fast multi-path payment with redundancy ［C］ //Proc of the 3rd ACM Conference on Advances in Financial Technologies. New York： ACM Press， 2021： 183-191.

［14］Cormen T H， Leiserson C E. Introduction to Algorithms ［M］. Boston： MIT Press， 2019： 176-190.

［15］Prihodko P， Zhigulin S， Sahno M， et al. Flare： an approach to routing in lightning network ［EB/OL］. （2016-07-07）. https：//bitfury. com/content/do-wnloads/whitepaper_flare_an_approach_to_routing_in_lightning_network_7_7_2016. pdf.

［16］Malavolta G， Moreno-Sanchez P， Kate A， et al. SilentWhispers： enforcing security and privacy in decentralized credit networks ［C］ //Proc of Network and Distributed System Security Symposium. 2017： 1054-1071.

［17］Roos S， Moreno-Sanchez P， Kate A， et al. Settling payments fast and private： efficient decentralized routing for path-based transactions ［C］ //Proc of Network and Distributed System Security Symposium. 2018： 1-10.

［18］Wang Peng， Xu Hong， Jin Xin， et al. Flash： efficient dynamic routing for off-chain networks ［C］ //Proc of the 15th International Conference on Emerging Networking Experiments and Technologies. New York： ACM Press， 2019： 370-381.

［19］Zhang Yuhui， Yang Dejun， Xue Guoliang. CheaPay： an optimal algorithm for fee minimization in blockchain-based payment channel networks ［C］ //Proc of IEEE International Conference on Communications. Piscataway， NJ： IEEE Press， 2019： 1-6.

［20］Sivaraman V， Venkatakrishnan S B， Ruan K， et al. High throughput cryptocurrency routing in payment channel networks ［C］ //Proc of the 17th USENIX Symposium on Networked Systems Design and Implementation. 2020： 777-796.

［21］葛鐘慧， 張奕， 龍宇， 等. 一種支持高并發的多人鏈下支付方案 ［J］. 計算機學報， 2021， 44（1）： 132-146. （Ge Zhonghui， Zhang Yi， Long Yu， et al. A high-concurrency multi-party off-chain payment scheme ［J］. Chinese Journal of Computers， 2021， 44（1）： 132-146.）

［22］Qian Hangguan， You Lin. A multipath payment scheme supporting proof of payment ［J］. Wireless Communications and Mobile Computing， 2022， 2022（1）： 1-7.

［23］Liu Ya， Wu Yuanhang， Zhao Fengyu， et al. Balanced off-chain payment channel network routing strategy based on weight calculation ［J］. The Computer Journal， 2024，67（3）：907-922

［24］Conoscenti M， Vetrò A， De Martin J. Cloth： a lightning network si-mulator ［J］. Software X， 2021， 15： 100717.