多因素反向拍卖的跨链支付路由方案

张 谦 曹 晟,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路由方法可以优化中继节点的选择，有效保障交易参与节点的报价隐私，实现了支付通道网络跨链路由过程的低花费与隐私性.

作者贡献声明：张谦负责完成实验并撰写论文;曹晟提出了算法思路和实验方案;张小松提出指导意见并修改论文.