多因素反向拍賣的跨鏈支付路由方案

張 謙 曹 晟,2 張小松,2

1(電子科技大學計算機科學與工程學院 成都 611731) 2(電子科技大學(深圳)高等研究院 廣東深圳 518110)

自比特幣誕生以來，區塊鏈技術憑借其新穎的數據結構及去中心化、透明度和可審計性等重要特性，逐漸在金融、供應鏈管理、醫療保健和能源電力等應用領域顯示出重要潛力[1].

由于比特幣、以太坊等公鏈平臺為保障交易的安全性，嚴格限制鏈上出塊速度，導致其交易吞吐量低[2].其現有應用大都局限在同一區塊鏈網絡覆蓋下的存證、審計等低頻交易場景.為滿足實時支付等場景的高頻交易需求，研究人員開展了對于區塊鏈擴容技術的研究.相比于主要從共識算法、區塊擴容等方面進行研究的鏈上擴容技術，鏈下擴容技術一般不修改區塊鏈底層數據或網絡結構，通過將耗時的鏈上數據操作轉移至鏈下，將交易的有效性驗證放在鏈上進行，在滿足小額高頻、復雜計算等交易處理需求的同時支持了區塊鏈之間的跨鏈操作.

作為鏈下擴容技術的重要手段，支付通道[3]以其鏈下支付的快速、低成本等特點得到了廣泛應用.利用哈希時間鎖定合約(Hash time lock contract, HTLC)技術[4]，通過在交易發生頻繁的2個參與者之間建立共享的鏈下虛擬通道，控制交易資金的鎖定與釋放，將交易從鏈上轉移到鏈下的虛擬通道進行，待交易結束后將交易添加至區塊鏈中，從而提高了區塊鏈節點間的交易效率.由于支付通道的建立需要一定成本，對于不直接共享通道的各方，需要通過沿現有支付通道組成的圖中的一個或多個節點組成多跳路徑，由中繼節點的轉發來促成區塊鏈內或區塊鏈間交易.在多跳跨鏈交易中，對于每筆待處理的付款交易，交易中繼節點在付款完成之前需要提供資金抵押[5].交易過程中，尋找合適節點構成支付路徑的過程稱為路由.典型的支付通道網絡有閃電網絡[6]、雷電網絡[7]、InterLedger[8]等.

當前針對支付通道網絡路由方法的研究主要聚焦在2個方面:1)提高所選擇路徑的隱私與安全性，避免由于各種攻擊造成交易的失敗，文獻[9-12]分別提出基于秘密共享、大蒜路由等具備隱私保護的路由方案，加強路由選擇中節點通信內容與節點身份信息的隱私性；2)優化改進路由選擇與調度算法，以提高交易處理效率，文獻[13-17]分別提出了基于信標節點的靜態路由方案、基于圖嵌入的貪心路由方案、基于流量算法的Flash動態路由方案和基于資金偏度的混合路由方案等.

以上方法缺乏交易手續費對于交易路由選擇影響的分析與手段.跨鏈路由路徑越長，中繼服務的中繼節點跳數越多，用戶向中繼節點支付的手續費就越高.在小額支付的場景中，潛在的高額節點手續費對于跨鏈支付發起者來說是不可忽視的[5].文獻[18]中，Zhang等人提出了一種基于服務拍賣的中繼節點選擇方案，可以降低交易手續費.如果支付通道中存在低信譽的中繼節點，其掉線或拒絕服務等行為可能會引起跨鏈交易的失敗.此外，拍賣過程容易受到某些隱私攻擊[19].例如，隨著交易次數的增多，惡意節點可以通過長期監測網絡中的交易結果，發起推理攻擊[20].通過嘗試不同的詢價/出價組合，推理歷史獲勝節點報價，以預測路由拍賣的相應結果，控制路由選擇過程，進而干擾或破壞跨鏈交易.

為了避免惡意節點被選中參與跨鏈交易，并保護中繼節點的報價不被監測，本文將中繼節點的路由選擇抽象成交易服務提供者拍賣過程，提出了一種基于熵權法的多因素反向拍賣(multi-factor reverse auction, MFRA)的路由方案，綜合評估候選中繼節點的歷史信譽、路徑距離、手續費報價等因素，以選擇最優的中繼節點參與跨鏈交易.本文提出了多因素反向Vickrey拍賣模型，建立節點的等價報價函數，用于將候選中繼節點的其他非價格屬性因素轉換為價格屬性.MFRA方案引入以2為基數的指數型差分隱私機制，以保障中繼節點的報價不被泄露.

本文的主要貢獻包括4個方面:

1)提出了基于多因素反向Vickrey拍賣的路由機制MFRA，為跨鏈支付提供了節點手續費報價、節點信譽、路徑距離的多重因素綜合下的路由中繼節點選擇方案.

2)引入反向Vickrey拍賣的思想，根據獲勝節點的非價格屬性值，建立候選節點的等價競標函數.MFRA促進了候選節點的誠實投標，減少了交易發起者支付的跨鏈手續費.

3)在獲勝候選節點最終手續費的確定過程中，引入了以2為基數的指數機制差分隱私，保障候選中繼節點的報價隱私.

4)設計基于MFRA的支付通道網絡跨鏈交易方案，并進行了安全性分析和性能評估，表明MFRA路由方案可有效用于跨鏈支付.

1 相關工作

Fig.1 Payment channel networks based on HTLC

保障多跳支付路徑的安全、快速參與節點的隱私是支付通道網絡的研究熱點.SilentWhispers[9]使用地標路由算法選擇網絡中連接性最高的節點來生成總交易路徑，并為節點自身信息提供隱私保護.文獻[10]提出了一種基于本地知識的隱私保護路由算法SpeedyMurmurs，可在完全分布式的環境中保護節點隱私，并在有效性和效率方面優于SilentWhispers.文獻[11]在支付通道交易過程中引入大蒜路由，保障發送方/接收方的個人信息隱私.文獻[12]設計了一種名為Boomerang的多路徑路由方案，可以建立冗余通道以消除參與者不執行交易協議的風險.文獻[21]研究了隱私和實用性之間的權衡，以實現最短路徑路由機制的噪聲信道平衡.

在提高交易吞吐量方面，文獻[13]利用信標節點，提出了Flare靜態路由方案.節點只需要維護了信標節點的本地路由表，通過將它們的路徑組合到信標，發送者和接收者可以獲得交易的完整路徑.文獻[14]利用基于圖嵌入的貪心路由算法，實現分布式環境中節點之間的路徑查找.文獻[15]將基于圖嵌入的貪心路由算法從雙人通道網絡進一步推廣至多人通道網絡中.文獻[16]提出了Flash動態路由方案，根據交易金額將交易分為大象支付和老鼠支付.然后，使用修改后的最大流量算法進行大象支付來尋找資金充足的路徑，而老鼠支付則直接通過存儲在路由表中的路徑發送.文獻[17]使用基于資金偏度的路徑選擇方案，利用靜態和動態路由來減少資金偏度，提高交易成功概率并降低延遲.

相比于上述路由方法分別重點關注路由安全與路由效率，低估了交易費用、反映節點歷史行為的節點信譽等關鍵因素.文獻[18]提出基于拍賣的路由選擇方案，以最小化手續費開銷為目的，但容易受到推理攻擊泄露節點報價隱私.文獻[22]提出了一種綜合度量路徑距離、手續費價格的路由選擇方案AMPS，但缺乏對于候選中繼節點手續費報價這一動態可調整的因素進行隱私保護.作為共同的缺陷，文獻[18,22]提出的2個方案中的惡意節點可以通過掌握的節點報價信息，調整個人節點手續費報價，控制路由選擇結果進而控制或破壞跨鏈交易.

2 預備知識

2.1 基于HTLC的支付通道網絡

基于HTLC的支付通道包括建立通道的兩方所需支付的金額等要素，通過HTLC合約來控制參與雙方抵押資金的鎖定與釋放，每個支付通道可以執行通道建立、交易執行以及通道關閉等3種操作，實現節點間的鏈下資金轉移交易.

HTLC的核心是時間鎖和哈希鎖，利用時間鎖限制了交易約定時間，迫使交易雙方在規定期限內完成轉賬支付的接受與確認；利用哈希鎖給交易雙方提供交易接受與確認機制.只有在時間鎖的規定時間內，完成哈希鎖Hash(R)=H的驗證，交易才算成功，否則交易參與雙方可以收回各自鎖定的抵押資金.其中，R是交易接受者生成的隨機哈希原像值，H為R的哈希值，在交易開始前將哈希值H發送至交易發起者.哈希鎖和時間鎖的結合保障跨鏈交易的原子性，避免參與節點因欺詐或交易失敗造成抵押資金損失.

基于HTLC的支付通道網絡如圖1所示，由m+1段支付通道組成，通過m個中繼節點的交易中轉實現資金的轉移.在支付過程中，隨著交易跳數的增加以及延遲波動時間的累計，各段通道中合約設置的截止日期自后向前依次遞增，即t1>t2>…>tm+1，以滿足多跳交易可在限制時間內完成.

2.2 反向拍賣

反向Vickrey拍賣模型[23]是反向定價機制和Vickrey拍賣模型的結合.反向定價機制指的是通過服務提供者(中繼節點)的出價投標來確定任務的服務價格(中繼手續費)，通常由出價較低的服務提供者中標.為了防止投標人在實際場景中夸大真實成本和惡意低價競爭，在定價過程中廣泛引入了Vickrey拍賣機制[24]，也稱為次高價密封拍賣，可以確保每個投標人真實出價.在競拍過程中，每個參與者都在不知道別人的出價的情況下秘密出價.在投標結束時，所有當前的報價都被計算在內，出價最高的人獲勝，但只支付第二高的出價.投標人沒有理由錯報其報價，因為他/她不知道對手的報價，并且他/她的報價不能影響最終價格.

由于反向定價機制和Vickrey拍賣模式的結合，在密封規則和次低交易規則下，反向Vickrey拍賣可以保證中繼節點手續費出價的真實性，保證跨鏈交易請求者和中繼節點都獲得更高的回報.

2.3 差分隱私

Dwork等人提出了差分隱私[25]的概念，用于保護統計數據集的隱私.差分隱私確保觀察者查詢的結果不應該透露個人信息.當前基于差分隱私的隱私保護方案大多基于指數機制與拉普拉斯機制2種基礎模型.區別于拉普拉斯機制只能針對數值型數據進行隱私保護，McSherry等人[26]提出的指數機制適用于非數值型數據，例如選舉、投票、拍賣等實體對象.

在拍賣等場景中，對于所有可能的輸出集合O，指數機制的目的是使輸出結果滿足某種概率分布的隨機性.可用性函數u(D，o)用來衡量每一個輸出項的價值，其中D為輸入的數據集，o為可能的輸出集合O中的項.可用性函數u返回一個實數來表示o的價值，返回的u值越高，表示該項的價值越大，其被輸出的概率也越大.

差分隱私在實際場景下易受到一些基于浮點的攻擊，攻擊者利用浮點算術舍入和截斷特性破壞差分隱私效果，使得隱私數據無法得到保護.Christina Ilvento將以e為基數切換到以2為基數，從而使差分隱私過程中能夠執行以2為基數的精確運算.

定義2.基數為2的指數機制[27].設隨機算法M輸入為數據集D，輸出為實體對象集合O中的某一對象o，u(D,o)為可用性函數，Δu為可用性函數u的敏感度.以2為基數的指數機制根據如下概率從對象集合O中選取一個元素：

Pr(o)

(1)

3 多因素反向拍賣的跨鏈支付路由方案

3.1 問題分析

假設在發起者Alice發起的跨鏈交易過程中，需要沿著由m個提供交易中繼服務的中繼節點組成的支付通道鏈路path={Alice→C1→C2→…→Cj→…→Cm→Bob}完成跨賬本的轉移.在通道中，對于通道path中的任意一跳交易中繼服務節點，都有一個由n個候選節點組成的集合cdj={cdj1,cdj2,…,cdjn}，可以滿足第j跳節點的路由要求，例如資金儲備和網絡連通.每j跳中選出的候選節點cdji作為提供中繼跨鏈交易的中繼節點Cj參與支付通道path的交易轉移.

將中繼節點的選擇過程抽象為服務提供者的選擇過程，提出了一種基于多因素反向拍賣的跨鏈支付路由方案MFRA，以從候選節點中選擇中繼節點.

在節點選擇過程中，基于反向拍賣的思想，將節點選擇看作一次“路由服務拍賣”，各候選節點提交各自報價，然后收集各節點記錄在區塊鏈中的節點位置、歷史信譽因素.通過建立的基于熵權法的多因素節點質量評價函數計算各節點綜合得分，其中函數涵蓋中間手續費報價、節點間路徑距離、節點歷史信譽等3個因素.選擇總分最高的候選節點作為第j跳中繼節點.

在計算支付給第j跳中繼節點的最終手續費的過程中，本文構造了候選節點的等價報價函數，以中標節點的非價格屬性值為標準屬性值，將其他候選節點的多因素質量評分轉換為標準屬性值下的等價物，計算并收集各節點非價格屬性標準值下的等效報價，組成等效池.在各候選節點的等效報價池中剔除最低價格.以一定的差分隱私預算ε和可用性函數u(D，o)，對當前的等效報價池BO進行以2為基數的差分隱私，生成等效價格池BO的概率分布.在生成等效價格的指數概率分布后，使用隨機機制選擇一個臨時價格，進一步檢查所有約束條件，例如所選價格應滿足非負效用、正收益等.如果所選價格滿足所有要求，該臨時價格最終被確定并視為第j跳中繼節點應得的最終手續費.

在第j跳節點的路由選擇中，令υji為候選節點cdji的出價，γji為候選節點cdji想要獲得的報酬，min(υ-Cj)是除Cj之外的所有投標人的最低出價.那么中繼節點Cj的收益ηji表示為

(2)

如果υji>γji，則投標人獲得負收益；如果υji<γji，當υji

根據上面的分析，在中繼節點投標報價與選擇過程中，直接給出自己的實際價格是每個候選中繼節點的最優策略.綜合節點信譽、路徑距離等公開因素后，選擇每一跳得分最高的候選節點為獲勝者.除去最低報價的等效報價池作為第j跳節點的最終應得手續費的基礎價格集合，從中隨機選擇得到一個滿足非負效益等約束的vj作為實際支付給第j跳中繼節點的最終交易手續費.在報價確定過程中，每個候選中繼節點的出價組成報價池，MFRA路由方案中的差分隱私策略，能夠從報價池中隨機地選擇一個報價，這種隨機性確保沒有對手可以知道候選中繼節點對交易服務價值的原始報價.因此，以2為基數的指數型差分隱私機制為參與候選節點提供了隱私保證.

然后通過m個提供跨鏈交易服務的中繼節點組成的支付通道path，Alice需要支付的總交易手續費用Ptotal表示為

(3)

其中υj為第j個中繼節點的出價.

3.2 基于多因素反向拍賣的路由選擇方案

在支付通道path的第j跳節點的選擇過程中，有n個候選節點滿足第j跳節點的要求.在n個候選節點選擇第j跳中繼節點時應考慮多個評估因子.本文主要考慮3個因素：候選節點的歷史信譽、節點間路徑距離及節點的中間手續費報價.其中，節點間路徑距離和歷史信譽記錄在區塊鏈上，所有節點都可以看到；節點出價由各候選節點提交.第j跳的候選節點集合cdj={cdj1,cdj2,…,cdjn}中的任意一個節點有3個因子xik,k∈{0,1,2}，其中xik代表第i個候選節點的第k個因子的實際值.本文中k=0時表示為報價因素，k=1時表示為路徑距離因素，k=2時表示為節點信譽因素.

MFRA路由方案的中繼節點選擇如圖2所示，包括5個步驟.

Fig.2 Relay node selection of MFRA routing scheme

步驟1.交易發起者Alice或上一跳節點Cj-1檢測其鄰居節點之間的連接，提取節點所在公鏈中記錄的每個鄰居節點的數據信息，更新節點路由信息表RT.數據信息包括節點坐標、節點歷史信譽、賬戶金額等.根據更新后的路由表RT，上一跳節點Cj-1通過多播路由表RT向鄰居節點發送跨鏈交易請求.第j-1跳節點Cj-1建立智能合約SCj，負責候選節點cdji的選擇并監控與目標節點Bob的跨區塊鏈交易.該請求包含交易金額coin、目標區塊鏈B和響應期限t.

步驟2.滿足Alice要求的節點響應Alice的請求，將服務費υji提交給智能合約SC.收集整理來自每個相鄰候選節點cdji的中間服務費投標，計算每個候選節點到目標節點的路徑距離.智能合約SC根據候選節點出價、路徑距離和歷史信譽生成候選信息表Candi.

步驟3.根據候選節點信息表Candi中的信息，智能合約SC計算每個候選節點的質量評分，根據總分Score[i]從高到低對候選節點表Candi進行排序，并選擇得分最高的候選節點cdji作為跨鏈交易的中繼節點Cj，提供交易中繼服務.

在步驟3中，本文引入熵值法確定路徑距離、交易手續費報價和節點歷史信譽等因素的權重，并建立路由節點質量評分函數.MFRA路由方案避免了現有支付通道跨鏈研究僅依靠最短路由距離或最小手續費來選擇跨鏈交易路由節點.步驟3的詳細過程有4點：

① 通過分析路徑距離、交易手續費報價和節點歷史信譽同跨鏈路由整體開銷的正負相關關系確定積極因子和消極因子，利用候選節點各指標的參數值建立指標集合；

② 使用臨界值法對因子分別進行歸一化，得到每個因子的歸一化形式，每個因子的無量綱形式為

(4)

(5)

其中，xik是第i個候選節點的第k個因子的實際值，max(xk)是第k個因子的最大值,min(xk)是第k個因子的最小值.

③ 建立跨鏈路由節點打分的線性加權和公式，得到各指標的信息熵，通過熵權法確定線性加權和公式中的各個權重系數，并列出系數集合.

第k個因子的信息熵形式為

(6)

第k個因子的權重wk表示為

(7)

④ 根據因子的權重wk計算出每個候選節點的綜合得分.將所有候選節點的節點質量得分Score[i]從高到低重新排序，選擇得分最高的候選節點cdji作為獲勝中繼節點Cj參與跨鏈交易的中繼服務.

(8)

針對步驟1～3，設計具體算法1.

算法1.獲勝候選節點的確定.

輸入：需要交易的金額coin、報價響應截止時間t、當前所在區塊鏈Ledgerj-1、下一跳區塊鏈Ledgerj；

輸出：第j跳的中繼節點Cj.

/*第1階段：收集節點報價*/

① Initialize:Bidding={0,…,0},CandiID={0,…,0};

② sendtask(coin,t,Ledgerj-1,LedgerjtoSC;

/*智能合約向Ledgerj-1網絡廣播需求*/

③ whiledatetime.now()intdo

④getResponse(υji,cdji);

⑤Bidding[i]=υji;

⑥CandiID[i]=cdji;

⑦ end while

⑧ Stop Bidding Process

/*第2階段：計算各候選節點綜合得分*/

⑨ SetRT=getRoutingTablefromLedgerj；

Table 1 Comparison and Analysis of Routing Schemes

Table 2 Comparison of Transaction Latency of Multi-hop Cross-blockchain

⑩ forCandiIDinBidderIDdo

/*計算熵值*/

/*計算各因素權重*/

/*計算各候選節點的得分*/

/*返回得分最高節點，即為第j跳中繼節點*/

算法2.第j跳中繼節點的手續費.

輸出：最終支付給第j跳中繼節點的手續費υj.

②EB=[];

③ foriinScore[]do

⑤EB.add(feesi);/*計算各候選節點等效報價，組成等效報價池*/

⑥ end for

⑦EB.remove(min(EB));

/*去除最低價格*/

⑧ Δu=1/Score[].length();

/*設置隱私敏感度*/

⑨ foriinEB

⑩u(D,i)=max(EB)-EB.i;

/*設置可用性函數*/

/*生成概率分布集*/

在步驟4中，本文引入了反向Vickrey拍賣，以避免候選節點的不誠實投標.通常反向Vickrey拍賣只考慮價格指標，沒有考慮路徑距離和節點歷史信譽等多個指標.本文以獲勝節點的非價格屬性值為標準，將其他候選節點的價格轉換為標準屬性值的等價價格，從而用于將節點質量中的非價格屬性因素轉化為價格屬性.根據Vickrey支付功能的特點，剔除最低等效價格，利用以2為基數的指數型差分隱私計算出最終支付給第j跳中繼節點的手續費.具體來說：

① 根據步驟3中選中的中繼節點Cj的非價格因素的值，計算非價格因素評分標準和V；

(9)

② 根據非價格評分標準總和V計算每個節點的等價出價feesi，

(10)

③SC將所有選中節點的等價出價從低到高排序，生成不包括最低出價min(fees)的等效報價池BO；

④SC秘密向上一條節點Cj-1臨時獲取隱私參數ε和可用性函數u，對等效報價池BO進行以2為基數的差分隱私，生成等效價格池BO的概率分布.

Pr(o)

(11)

⑤ 在生成等效價格的指數概率分布后，SC使用隨機機制選擇一個臨時價格temp(fees)，進一步檢查所有約束條件，例如所選價格應滿足非負效用、正收益等.驗證臨時價格temp(fees)是否大于獲勝節點的價格.如果滿足，SC宣布獲勝節點Cj和中間價格υj，其中υj=temp(fees).

定理1.MFRA滿足ε-差分隱私.

(12)

根據文獻[26-27]中的差分隱私證明，如果輸入集合BO值改變了一個元素，式(12)滿足ε-差分隱私，那么輸出變化不超過exp(ε).可以表示為

Pr[output(BO)=x]≤exp(ε)×

Pr[output(BO′)=x].

(13)

根據上述分析可以得出結論，步驟4中對等效報價池設計的以2為基數的指數差分機制滿足ε-差分隱私.

步驟5.獲勝的中繼節點Cj與上一跳中繼節點Cj-1或跨鏈交易發起者Alice建立連接.Cj-1或Alice授權中繼節點Cj幫助她完成跨區塊鏈交易并預先提交等于手續費υj的保證金.跨區塊鏈交易完成后，則υj將自動支付給Cj.

3.3 基于MFRA的跨鏈支付

基于HTLC的支付通道網絡實現跨鏈支付，一般通過在跨鏈支付發起方與接收方之間建立一條跨區塊鏈網絡的單跳或多跳支付通道path={Alice→C1→C2→…→Cj→…→Cm→Bob}，從而完成Alice與Bob間跨鏈交易.其中，Cj←j∈{1,2,…,m}表示通道中任意中繼節點Cj在區塊鏈網絡Ledgerj-1與Ledgerj中擁有賬戶，以支持跨鏈支付中的資金交換.交易發起者首先通過路由方案，通知各候選中繼節點交易接收者所在區塊鏈網絡、交易金額等信息，并選出各中繼節點參與跨鏈交易中繼任務，構建跨鏈支付通道.各參與節點分別通過哈希時間鎖，沿著通道中交易轉移順序先后在Ledgerj鎖定支付給Cj或Bob的資金，其中j∈{1,2,…,m}，并在Bob身份驗證后，倒序依次獲取Cj-1或Alice鎖定在網絡Ledgerj-1中的交易資金，實現Alice與Bob間跨鏈交易.

為了解決上述的跨鏈方案中，選擇路由節點的因素單一而造成跨鏈支付發起者可能承擔高昂交易手續費的問題，本文提出了基于MFRA路由方法的跨鏈支付方案，使得只有貨幣A的交易發起者Alice能夠與只接受貨幣B的接受者Bob進行交易結算.通過引入面向跨鏈中繼服務的反向拍賣機制，在保障跨鏈交易順利進行的同時，很大程度上降低了多跳支付通道累計的中間手續費開銷.并引入以2為基數的指數差分隱私機制，避免了在線支付過程中中繼節點的報價隱私泄露，提高了路由過程的抗推理攻擊能力.基于上述跨鏈路由方案，整體跨鏈支付過程具體步驟為：

步驟1.交易發起者Alice向接受者Bob的區塊鏈網絡節點秘密發送支付請求，以確定本次交易的金額、交易時限以及哈希證明.

步驟2.使用智能合約SC.Alice發送一個準備數據包，包含Bob的帳戶地址、交易金額、共享密鑰的哈希值和到期時間.SC遵循3.2節中的步驟執行算法1與算法2，選擇C1作為第一個提供跨鏈交易中繼服務的節點.中繼節點C1的服務手續費由SC鎖定，待交易完成后智能合約自動將獎勵支付給中繼節點C1.

步驟3.Cj檢查Alice帳戶中的金額是否足以支付交易費用.如果足夠，Cj將減少Alice賬戶中的余額，否則交易被拒絕.Cj在許可下構建和使用智能合約SC.

步驟4.與步驟2類似，智能合約SC使用算法1與算法2，Cj的本地路由表確定下一跳和過期時間，根據匯率改變包量，將包發送到下一跳.對于每個Cj，執行步驟3～步驟4.

步驟5.當數據包到達Bob節點時，Bob首先檢查數據包的有效性，如超時、金額等.如果有效，則將具有共享秘密數據包的履行數據包發送到Cm，這可以看作是一個開具收據的過程；否則，交易被拒絕.

步驟6.Cj收到Cj+1發送的共享秘密后，利用哈希計算檢查秘密是否正確.如果正確，則在到期前將秘密發送到Cj-1，此時，為Cj+1托管的轉賬被執行；否則，Cj將拒絕發送給Cj-1.每個Cj都執行步驟6，直到消息傳遞給Alice.當檢測到Alice的確認時，所有中繼節點的獎勵自動由智能合約SC支付.

至此，僅持有貨幣A的交易發起者Alice已成功向僅接受貨幣B的交易接受者Bob完成了多跳支付通道下的跨鏈支付.

4 安全性分析

本節詳細分析引入拍賣機制的MFRA路由方案可能面臨的安全威脅.

4.1 誠實報價

在介紹了拍賣機制的路由選擇過程之后，可能會出現2個誠實報價相關的問題.

問題1.在中繼節點的選擇中，候選節點是否可以提交虛假價格在交易結束后獲得更高的費用，即拍賣機制是否滿足激勵相容(incentive-compatibility, IC)[28]約束.

IC定義為:參與者如實申報自己的估值所獲得的利潤不低于虛報自己的估值所獲得的利潤.在拍賣理論中，IC通常被稱為“真實性”，這使得每個投標人更傾向于提交真實的報價.

根據本文中對3.1節的方程(2)的分析，在反向Vickrey拍賣機制下，如實提交自己的估價作為報價是所有投標人的最優策略.由于每個投標人都是自我的和理性的，他們會保持其投標的真實性，即υi=γi.因此，MFRA路由方案滿足激勵相容性.

問題2.如何避免理性的低信譽投標人以不誠實的低價中標后不提供相應的跨鏈服務.

為了避免這種情況影響拍賣過程，設計了押金機制和信譽機制.投標時，每個投標人提交一定的保證金，這可能高于節點的投標.如果投標人中標但未履行義務，則該節點的這種惡意行為會導致其提交的押金被扣除，該節點的信譽評分被降低.當信譽分數下降到一個定義的值(如0)時，該節點被判斷為惡意節點并拒絕參與拍賣.將交易發起者Alice的損失lossj定義為惡意節點的利潤，表示為：

(14)

其中，a=1表示中繼節點Cj發生了惡意行為；a=0表示中繼節點Cj被選中后確實誠實地提供了相應的跨鏈服務；min(υ-Cj)是交易發起者Alice需要花費的跨鏈手續費用；dj是中繼節點Cj提交的押金，其中dj?min(υ-Cj).

假設惡意投標者是自私和理性的.由于dj?min(υ-Cj)，當中繼節點Cj選擇作惡時，押金將扣除，其收益lossj=(min(υ-Cj)-dj)為負數，遠小于0.因此，放棄作惡是其最優策略.如果惡意投標者是非理性的，且a=1時，則中繼節點Cj的信用Crj=Crj-h，其中h是一個大于0的常數.當Crj-num(a=1)×h為小于0時，中繼節點Cj將失去投標資格，其中num(a=1)表示出現惡意行為的次數.可改變h的取值調節單次惡意行為對信譽減小的影響程度，并且由于dj?min(υ-Cj)，在這個過程中惡意節點的行為不會對交易發起者節點造成損失.

4.2 報價隱私

在4.1節的惡意報價分析中，假設候選節點總是自私與理性的，無法通過非誠實報價獲取更多自身利益.對于以破壞跨鏈交易為目的的惡意攻擊者來說，他們通常不在乎資金的損失.在跨鏈路由選擇過程中，攻擊者可以通過監測到的拍賣公布結果，推斷獲勝候選節點的初始服務報價，并利用獲取的歷史獲勝報價信息，實現對于下一筆跨鏈交易到來時中繼節點服務拍賣的選擇結果預測，通過惡意調低自身報價取得中繼交易的資格，從而控制跨鏈交易的中間路由，進而達成破壞跨鏈交易的目的，也被稱為推理攻擊[20].

在本文提出的MFRA路由方法中，首先使用熵權法的候選節點最終評分分別計算各節點的等效報價，并組成等效報價池BO；然后采用基于基數2的指數機制，對等效報價池BO進行差分隱私，生成等效價格集BO的概率分布.為了進行報價的隱私分析，在3.2節中，定理1已經證明MFRA方案確定的節點手續費報價能夠滿足差分隱私定義1、定義2的隱私界限.在基于拍賣理論的中繼節點跨鏈路由服務選擇過程中，本文提出的MFRA路由方案滿足了ε-差分隱私的理論含義，能夠維護參與節點投標隱私的有效機制，并具備基于基數2的指數機制抗浮點攻擊的能力.

4.3 原像安全

根據交易流程，中繼節點只有在接收方確認后回復確認，才能從資金接收方操作獲得條件原像，即資金發送方和資金接受方在發起交易前確定的密鑰.在獲得條件原像后該中繼節點向上一跳中繼節點繼續發送帶有條件原像的數據包后才能得到來自上一節點的轉賬.那么中繼節點就有可能去嘗試破解條件原像，因為一旦破解成功，中繼節點不用付出任何代價就可以獲得來自上一節點的資金.攻擊方法有2種:1)通過條件去逆推條件原像;2)通過監聽資金收發雙方的網絡通信獲得條件原像.

針對逆推條件原像的攻擊方法，當前條件原像使用SHA-256算法和AES-256算法生成.SHA-256暫無明顯有效的破解方法；在不知道加密密鑰的情況下，AES-256加密算法也幾乎無法破解；整個交易過程具有時間限制.在這樣三重條件下，要在短時間內通過條件逆推出條件原像幾乎是不可能的，所以條件原像的安全性可以得到保證.

針對通過網絡監聽獲取條件原像的攻擊方法，有2種方案可以保障其通信中密鑰的安全性：

1)交易雙方在正式開啟交易之前會通過HTTPS使用Diffie-Hellman密鑰交換算法生成共享密鑰(即條件原像)，然后通過HTTPS傳輸交易必要數據，包括共享密鑰以及接收方的賬戶地址.HTTPS通過數字證書、對稱加密算法以及非對稱加密算法來保證數據傳輸過程中的安全性，而Diffie-Hellman進一步保障了共享密鑰的安全性.

2)中繼節點嘗試通過監聽資金收發雙方的網絡通信獲得條件原像，需要知道自己將要參與的交易中的資金收發雙方的信息.但是，在交易雙方正式開啟交易之前，是不知道自己將作為哪兩個交易雙方的中繼節點，也就是中繼節點在交易開啟之前是找不到監聽目標的，所以中繼節點想要通過監聽資金收發雙方的網絡通信以獲得條件原像的方法行不通.故條件原像的安全性可以得到保證.

5 仿真實驗

實驗在Ubuntu 18.04操作系統上進行，主機CPU為Intel Core i7 8700，主頻為3.2 GHz.在本實驗中，主要考慮3個因素：節點價格、路徑距離和歷史信譽.候選中繼節點提交的價格投標以及與前一跳節點之間的路徑距離為消極因子；候選節點的歷史信譽是一個積極因子.

5.1 候選節點的綜合評分比較

為了比較本文提出的MFRA路由方法和單因素路由方案的質量評分差異，分別對4種方案的中繼節點選擇過程進行了仿真實驗.

Fig.3 Synthesis scores of the four schemes

設置了若干組候選連接節點，為各候選節點的3個因素隨機生成對應屬性值，計算所有候選節點基于熵權法的綜合得分.隨著一跳節點的路由選擇中候選節點數量的增加，4種方案選出的中繼節點的得分變化，包括僅考慮節點報價的方法、僅考路徑距離的方法、僅考慮節點信譽的方法和MFRA方案，如圖3所示.基于MFRA路由方案選擇的候選節點質量評分始終處于最高級別.由于其他3種方案僅考慮中繼節點選擇過程的單一因素，因此選擇的候選節點通常在其他2個因素上更容易有較差表現.例如，出價最低的節點可能距離上一跳節點較遠或歷史信譽較差.隨著候選節點數量的增加，其他3種方案的候選節點逐漸在2到3之間波動，而MFRA路由方案選擇的候選節點的分數在逐漸增加.這是因為隨著節點數量的增加，單個競標因子選擇的節點在其他2個因素中的性能趨于平均，而MFRA路由方案選擇的節點在綜合得分方面越來越優越.

5.2 中繼節點最終手續費開銷對比

本節分別對5種方案的中繼節點選擇過程進行了仿真實驗，以比較本文提出的MFRA路由方案、未考慮差分隱私的MFRA方案(記為“MFRA-1”方案)與單因素路由方案在中繼節點手續費上花銷的差異.

首先，在5.1節實驗的基礎上，模擬計算了3種僅考慮單因素的路由方案，第4種方案是僅使用多因素評價以及反向Vickrey拍賣的路由方案但不進行報價差分隱私.對比這4種方案的單跳中繼節點中繼手續費用開銷結果，實驗結果如圖4所示.隨著候選節點數量的增加，只考慮節點報價的方案和不考慮隱私保護的MFRA-1方案都逐漸減少，基于路徑距離或節點聲譽的路由方案的最終交易價格始終在4.0和6.0之間波動.當可選的候選節點較少時，MFRA-1路由方案的結果顯示出比其他3個單因素選擇方案更高的交易價格，因為MFRA-1路由方案引入的Vickrey拍賣機制，為避免節點不誠實的投標，需要剔除直接計算后得出的最低價格.該機制的引入使得在候選節點過少時成本增加；在5～7個候選節點加入拍賣過程后，最終交易手續費開銷迅速回落，低于僅考慮路徑距離或節點信譽的單因素選擇方案.雖然MFRA-1路由方案在手續費方面始終高于最低中標方案，但仍然有效降低了節點的中間服務手續費，平衡了各種因素，避免只考慮價格因素而忽略節點信譽、路徑距離造成的跨鏈交易延遲高、風險大甚至交易失敗等結果.

Fig.4 One-hop intermediate fees without regard to bidding privacy

在以上方案的基礎上，我們使用MFRA路由方案并對最終應付的中間手續費進行以2為基數的指數差分隱私，其中，本次實驗中將隱私參數設置為ε={1,0.25,0.0625}，并將其同未考慮報價隱私的多因素路由方案MFRA-1與僅考慮信譽的方案對比.實驗結果如圖5所示.隨著候選節點數量的增加，僅基于中間服務費拍賣的方案和MFRA路由方案都逐漸減少，以隱私參數ε=1的方案與未使用差分隱私的方案在最終手續費的計算結果上產生了一定波動，總體上保持一致.隨著隱私參數ε的減小，最終手續費的結果不斷偏離未考慮報價隱私的多因素路由選擇方案.以上實驗結果表明，在最終手續費計算中引入以2為基數的指數型差分隱私機制，實現了對候選節點報價的隱私保護，可以有效避免惡意節點通過歷史公布的手續費結果發起對候選中繼節點初始報價的推理攻擊.

Fig.5 One-hop intermediate fees considering bidding privacy

Fig.6 Multi-hop intermediate fees comparison

本節還比較了考慮差分隱私的多因素路由選擇方案、未考慮差分隱私的多因素路由選擇方案與設置多個跳中繼節點Cj時隨機選擇節點的方案之間手續費的變化.其中，本實驗中MFRA路由選擇機制中的隱私參數設置為ε=1.實驗結果如圖6所示.隨著支付通道中所需的中繼節點跳數的增加，MFRA路由方案無論是否考慮差分隱私都減少了中間手續費，且以隱私參數ε=1的方案與未使用差分隱私的方案在最終手續費的計算結果上總體保持一致.

此外，本文分別從交易手續費、路徑距離、節點歷史信譽、路由選擇中心化、隱私保護等角度分別對比了SilentWhispers[9]，Flare[13]，基于服務拍賣的路由選擇方案[18]，AMPS[22]等代表性路由方案，如表1所示.SilentWhispers和Flare方案均將路徑最短作為最優路徑的選擇標準，低估了交易費用、反映節點歷史行為的節點信譽等關鍵動態變化因素，均難以避免出現交易沿著一條固定路徑傳播，導致路由選擇中心化問題.文獻[18]僅考慮跨鏈交易手續費，在一定程度上降低手續費開銷，但易使交易信息沿著較遠、較差支付路徑進行中轉，造成跨鏈支付延遲完成甚至導致支付失敗.AMPS盡管在路由選擇時可同時引入中間手續費與路徑距離因素，進行多目標的動態路由選擇，也能夠一定程度上緩解了路由選擇中心化，但與文獻[18]所提出的方案一樣，均未考慮歷史行為不端的低信譽節點惡意違約，延遲甚至拒絕履行交易路由服務，破壞交易.此外，也都未考慮引入節點手續費報價機制后的報價隱私問題.

5.3 MFRA路由方案的時延分析

基于MFRA路由方案，本文采用InterLeger Protocol跨鏈協議(ILP)在本地環境實現跨鏈支付方案，創建InterLedger結算引擎的框架是開源的[29].ILP現在由W3C的InterLedger支付社區組共同開發和維護，采用基于HTLC的泛化協議(Hashed Time-Lock Agreements, HTLAs)，實現了完整的資金鎖定與交易確認機制.接下來分別對MFRA的通信時延與跨鏈交易的時延進行分析.

1)MFRA通信時延分析.為了清楚地展示MFRA跨鏈支付方案中基于拍賣機制的節點選擇方案對跨鏈延遲的影響，在基于ILP協議搭建的本地網絡環境下測試了拍賣機制額外引起的通信延遲.從圖7可以看到，隨著參與中繼節點服務拍賣的候選節點數量的增加，執行反向拍賣所需的時間不斷增加；但是當有100個節點參與時，整個拍賣機制造成的通信延遲仍然只有70 ms.基于多因素反向Vickrey拍賣的時間復雜度為O(logn).因此，引入的反向Vickrey拍賣機制在降低中間手續費的同時，不會影響跨鏈支付的時間.

Fig.7 Communication latency for reverse Vickrey auction

Fig.8 Transaction latency of cross-blockchain payment

2)MFRA交易時延分析.為了綜合評估基于MFRA路由方案的跨鏈方案，在搭建本地測試網絡上，測試MFRA跨鏈支付方案在不同交易金額與不同跳數通道下的跨鏈交易時延.

首先，測試了單跳中繼節點下，6種不同的貨幣組合的交易時延，其中每個組合包含3類節點，分別是交易發起者節點、交易的中繼節點和交易接收者節點.交易發起者賬戶中只有貨幣x，而接收者只接受貨幣y，中繼節點同時擁有2種貨幣，可為跨鏈交易提供中繼服務，滿足中繼節點要求的有30個候選者節點.圖8展示了不同交易金額下的交易延遲，當從交易發起者到接收者的支付環節建立后，整個交易將直接支付.此設置使中繼節點的單筆付款的托管金額非常大，這意味著更高的風險.

在InterLedger優化版本ILPv4的生態系統中，傳輸層使用了STREAM協議.STREAM協議的一個功能是將整個交易分成幾個小的交易包，然后完成支付，從而降低了中繼節點的風險.但是這樣的設置也意味著較大的交易會被分割成更多的小交易，增加了網絡通信的負擔和交易延遲.如圖8所示，當支付金額僅為10 USD時，交易延遲在0.048～0.184 s之間；當支付金額為100 USD時，交易延遲達到2.1～6.9 s.顯然，這種延遲通常是可以接受的.因此，基于MFRA路由的跨鏈支付方案可適用于支付通道網絡下的小額跨鏈支付場景，例如在線醫療咨詢.

其次，探討了在多個中繼節點組成的多跳支付通道中，基于MFRA路由方案的跨鏈交易時延.在圖8所示的實驗中，每種貨幣組合只需要經過一個中繼節點的單跳通道.將交易金額設置為30 USD，結果如表2所示.前3行包含3種貨幣并需要2個中繼節點，最后一行包含4種貨幣并需要3個中繼節點.延遲仍然保持在秒級，滿足實際應用需求.

6 結 論

目前支付通道網絡的路由研究大多關注節點間路徑距離等因素對交易處理效率的提升，忽視可能出現的高昂交易手續費對于小額支付場景中跨鏈交易發起者路由選擇偏好的影響.本文以節點手續費報價、路徑距離和代表交易成功率的節點歷史信譽，定義了跨鏈中繼節點服務質量評價函數，提出了一種基于熵權法的多因素反向Vickrey拍賣路由選擇方案MFRA來優化支付通道網絡中繼節點選擇，綜合評估候選中繼節點的質量來選擇獲勝節點.本文提出的MFRA多因素反向拍賣路由方案通過建立候選節點的等效報價函數，將候選節點的非價格屬性因素轉化為價格屬性，解決了在多屬性拍賣中無Vickrey拍賣讓節點誠實出價的問題.在最終手續費金額的確定過程中，MFRA路由方案引入了以2為基數的指數型差分隱私，避免最終路由過程與成交價被惡意節點推測.安全分析和量化實驗證明，MFRA路由方法可以優化中繼節點的選擇，有效保障交易參與節點的報價隱私，實現了支付通道網絡跨鏈路由過程的低花費與隱私性.

作者貢獻聲明：張謙負責完成實驗并撰寫論文;曹晟提出了算法思路和實驗方案;張小松提出指導意見并修改論文.