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

關(guān)鍵詞：區(qū)塊鏈；可擴(kuò)展性；支付通道網(wǎng)絡(luò)；超額抵押；路徑選擇

中圖分類號：TP399 文獻(xiàn)標(biāo)志碼：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 引言

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

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

為了縮短交易時(shí)間并提高成功率，尤其是針對大額交易，可以采用資金分割策略，將一筆大額交易分散至多條路徑上進(jìn)行，以降低單個(gè)路徑上的資金需求，從而提升交易的成功率。這種交易策略稱為多路徑支付，有助于提高大額交易的成功率，但同時(shí)也延長了交易總時(shí)間，因?yàn)樾枰却新窂缴系慕灰锥汲晒ν瓿?。若任一路徑交易失敗，整個(gè)交易都將失敗并需重新選取路徑進(jìn)行交易。在鏈下支付網(wǎng)絡(luò)中大額交易比小額交易的成功率明顯更低，大約只有45%。為確保支付通道網(wǎng)絡(luò)的經(jīng)濟(jì)可行性，研究高吞吐量的大額交易方案是必要的，這將大大減少中間節(jié)點(diǎn)鎖定資金的時(shí)間，增加中間節(jié)點(diǎn)獲得的交易轉(zhuǎn)發(fā)費(fèi)用，鼓勵(lì)更多用戶參與。交易成功的前提是路徑上所有支付通道均有足夠的資金可供交易使用。因此，高效的多路徑支付路由方案一直受到研究者的廣泛研究。

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

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

1 相關(guān)工作

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

2 系統(tǒng)模型

2.1 網(wǎng)絡(luò)模型

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

2.2 交易模型

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

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

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

?u，v∈p_i（1）

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

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

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

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

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

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 方案設(shè)計(jì)

3.1 MPST方案概述

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

總的來說，該方案首先要最大化每條路徑的交易資金，當(dāng)路徑交易金額越大，可能需要用到的交易路徑就越少，從而最大程度地節(jié)約不必要的資源浪費(fèi)。其次在保證能轉(zhuǎn)移資金相同的情況下，選擇較短的路徑進(jìn)行交易，從而相對減少了交易的等待時(shí)間，提高了交易吞吐量?？梢越?/p>

滿足：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能夠轉(zhuǎn)移的資金量；N_i表示路徑p_i的節(jié)點(diǎn)個(gè)數(shù)；k為大于1的常數(shù)；r表示交易的初始資金；fee^m_iu，v表示節(jié)點(diǎn)u轉(zhuǎn)移m_i資金至節(jié)點(diǎn)v收取的交易費(fèi)；c_u，v表示通道e_u，v的通道容量。

3.2 搜索可用路徑

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

算法1體現(xiàn)了在網(wǎng)絡(luò)中搜尋可用路徑的過程。該算法接受網(wǎng)絡(luò)拓?fù)浜椭Ц墩埱驲作為輸入，根據(jù)網(wǎng)絡(luò)拓?fù)浜椭Ц墩埱螅褂脧V度優(yōu)先算法迭代地找到從發(fā)送方到接收方的所有可用路徑。在搜尋路徑的過程中，判斷當(dāng)前路徑是否滿足信道容量和時(shí)間容忍約束可行性約束，滿足則加入路徑集合，不滿足則舍棄此路徑。如果在鏈下網(wǎng)絡(luò)中沒有可用的路徑，交易將返回空，否則返回一組可用路徑集合P={ p₁，p₂，p_i，…，p_n}，其中每個(gè)路徑p_i可以形式化為有序序列：p_i=v_s→v_i→…→v_r。其中，v_s、v_r和v_i分別表示路徑p_i上的發(fā)送方、接收方和中間節(jié)點(diǎn)。

算法1 搜尋可用路徑

輸入：網(wǎng)絡(luò)拓?fù)銰；支付請求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 // 如果沒有可用路徑跳出循環(huán)

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 // 指向后一個(gè)鏈表節(jié)點(diǎn)

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

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

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

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 構(gòu)建路徑得分

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

a） 數(shù)據(jù)正向化。

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

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

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

（6）

b）正向化矩陣標(biāo)準(zhǔn)化。

由于資金量和節(jié)點(diǎn)數(shù)是不同的度量單位，不能直接相加需要消除不同指標(biāo)量綱的影響，將其進(jìn)行標(biāo)準(zhǔn)化處理。對X中的每一項(xiàng)x_ij進(jìn)行標(biāo)準(zhǔn)化，將標(biāo)準(zhǔn)化的矩陣記為Z。

X=x₁₁₁₂x₂₁₂₂x₃₁₃₂x_n1n2標(biāo)準(zhǔn)化Z=z₁₁z₁₂z₂₁z₂₂z₃₁z₃₂z_n1z_n2

（7）

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

c）計(jì)算得分并歸一化。

經(jīng)過正向化和標(biāo)準(zhǔn)化的修正之后，對路徑構(gòu)建評分指標(biāo)。首先，找出候選路徑集P中所有路徑可轉(zhuǎn)移資金量和節(jié)點(diǎn)數(shù)的最大值和最小值，然后計(jì)算每條路徑與最大值和最小值的距離。

最大值：

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中最多的可轉(zhuǎn)移資金量；Z⁺₂表示P中最小的路徑節(jié)點(diǎn)個(gè)數(shù)；Z^－₁表示P中最少的可轉(zhuǎn)移資金量；Z^－₂表示P中最大的路徑節(jié)點(diǎn)個(gè)數(shù)。

計(jì)算p_i與 Z⁺₁，Z⁺₂的距離：

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

計(jì)算p_i與 Z^－₁，Z^－₂的距離：

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

其中：由于可轉(zhuǎn)移資金量更為重要，在構(gòu)建評分時(shí)根據(jù)優(yōu)序圖法分析了每個(gè)指標(biāo)的權(quán)重w_j，結(jié)合權(quán)重建構(gòu)路徑得分，經(jīng)過不斷調(diào)整，發(fā)現(xiàn)當(dāng)w₁=0.75，w₂=0.25時(shí)效果最優(yōu)。

d）評分構(gòu)建。

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

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

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

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

最后，根據(jù)C_i大小對所有候選路徑p_i排序，C_i越大表明評價(jià)對象越接近最優(yōu)值就越優(yōu)。

3.4 多路徑支付

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

算法2 路由選取

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

輸出：有序路徑集 P～。

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

for p in P {

c_p=TOPSIS（P，T_max） /*調(diào)用TOPSIS計(jì)算各路徑與最優(yōu)解的相似度*/

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

}

result.sort（（a，b）=gt; b［1］-a［1］） // 將結(jié)果集根據(jù) c_p進(jìn)行排序

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

add item［0］ to P～

}

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

end

4 實(shí)驗(yàn)與分析

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

funds rate=M_i/m_i=k（14）

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

4.1 評估指標(biāo)

本文主要探究了以下三個(gè)指標(biāo)與funds rate間的關(guān)系。

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

b）交易完成時(shí)間（time taken for payment，TTP）：從發(fā)送方發(fā)起交易請求到交易成功到達(dá)接收方的時(shí)間間隔。

c）通道利用率（channel utilization rate）：一輪交易中參與交易轉(zhuǎn)發(fā)的通道數(shù)量與整個(gè)網(wǎng)絡(luò)中通道數(shù)量總和的比值。

4.2 實(shí)驗(yàn)結(jié)果與結(jié)果分析

4.2.1 成功率

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

4.2.2 通道利用率

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

4.2.3 交易完成時(shí)間

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

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

5 結(jié)束語

本文提出了一種高效的多路徑支付方案MPST，以解決多路徑支付中超額抵押帶來的問題。MPST利用最大流算法和TOPSIS分析法優(yōu)化大額交易問題，有效降低了超額抵押資金。在真實(shí)的閃電網(wǎng)絡(luò)拓?fù)渲?，本文將MPST與四種經(jīng)典多路徑支付方案進(jìn)行了對比，重點(diǎn)探究了超額抵押資金與交易成功率、通道利用率和交易完成時(shí)間的關(guān)系，結(jié)果表明MPST在各項(xiàng)指標(biāo)下均表現(xiàn)出了較好的性能，減少了8%～16%的超額抵押資金。這一對比分析全面展示了MPST在優(yōu)化超額抵押多路徑支付方面的優(yōu)異性。

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

參考文獻(xiàn)：

［1］王嘉瑤， 王婷， 袁文亮， 等. 分布式賬本技術(shù)的發(fā)展歷程研究綜述 ［J］. 計(jì)算機(jī)應(yīng)用研究， 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］喻輝， 張宗洋， 劉建偉. 比特幣區(qū)塊鏈擴(kuò)容技術(shù)研究 ［J］. 計(jì)算機(jī)研究與發(fā)展， 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］潘晨， 劉志強(qiáng)， 劉振，等. 區(qū)塊鏈可擴(kuò)展性研究： 問題與方法 ［J］. 計(jì)算機(jī)研究與發(fā)展， 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］王鋒， 張強(qiáng)， 劉揚(yáng)， 等. 從擴(kuò)展性角度看區(qū)塊鏈 ［J］. 計(jì)算機(jī)應(yīng)用研究， 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］葛鐘慧， 張奕， 龍宇， 等. 一種支持高并發(fā)的多人鏈下支付方案 ［J］. 計(jì)算機(jī)學(xué)報(bào)， 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.