張?jiān)娡? 秦波，鄭海彬

（1. 中國(guó)人民大學(xué)信息學(xué)院，北京100872；2. 北京航空航天大學(xué)電子信息工程學(xué)院，北京 100191；3. 信息保障技術(shù)重點(diǎn)實(shí)驗(yàn)室，北京 100072）

1 引言

自2008年中本聰發(fā)明比特幣[1]至今，已有近10年時(shí)間。在這10年間，源自于比特幣的底層技術(shù)，區(qū)塊鏈技術(shù)逐步成長(zhǎng)為一項(xiàng)獨(dú)立、擴(kuò)展性強(qiáng)、應(yīng)用范圍廣的新型互聯(lián)網(wǎng)技術(shù)。隨著公有鏈、私有鏈、聯(lián)盟鏈[2]的發(fā)展，區(qū)塊鏈研究呈現(xiàn)百花齊放的態(tài)勢(shì)，各大機(jī)構(gòu)公司紛紛涉足，希望找到適合于自身的區(qū)塊鏈發(fā)展路徑。區(qū)塊鏈技術(shù)有四大技術(shù)特點(diǎn)，分別是去中心化、不可篡改、可追溯和不可偽造。

與此同時(shí)，因脫離區(qū)塊鏈1.0技術(shù)的區(qū)塊鏈2.0智能合約[3]廣泛的應(yīng)用性，全球范圍內(nèi)的新型區(qū)塊鏈項(xiàng)目如雨后春筍，數(shù)量與日俱增。根據(jù)Coinmarket Cap（數(shù)字貨幣數(shù)據(jù)分析網(wǎng)站）的數(shù)據(jù)顯示，現(xiàn)有流通數(shù)字貨幣已有2071種，總市值高達(dá)1467億美元，相當(dāng)于一個(gè)中等國(guó)家的GDP總量。隨著區(qū)塊鏈項(xiàng)目的增多，區(qū)塊鏈的互通性問(wèn)題成為搭建區(qū)塊鏈價(jià)值網(wǎng)絡(luò)的核心問(wèn)題。

2 區(qū)塊鏈的跨鏈需求及技術(shù)難點(diǎn)

區(qū)塊鏈?zhǔn)且环N分布式的總賬，一種區(qū)塊鏈?zhǔn)且粋€(gè)獨(dú)立的賬本，兩種區(qū)塊鏈?zhǔn)莾蓚€(gè)相互獨(dú)立的賬本。對(duì)于某個(gè)特定的用戶而言，如何把一種區(qū)塊鏈上的價(jià)值轉(zhuǎn)移到另一種區(qū)塊鏈上，就要涉及到兩個(gè)獨(dú)立賬本之間的價(jià)值流通，也就是我們所說(shuō)的跨鏈問(wèn)題。如果鏈與鏈之間無(wú)法實(shí)現(xiàn)互通互聯(lián)，那么區(qū)塊鏈網(wǎng)絡(luò)恐成一個(gè)個(gè)價(jià)值孤島?？珂溂夹g(shù)是鏈接區(qū)塊鏈的橋梁和紐帶，如果說(shuō)各個(gè)幣種是區(qū)塊鏈生態(tài)的血液，那么跨鏈技術(shù)就是區(qū)塊鏈生態(tài)的血管。

現(xiàn)有的跨鏈技術(shù)主要有四類(lèi)：公證人機(jī)制、側(cè)鏈/中繼、哈希鎖定以及分布式私鑰控制。公證人機(jī)制例如Ripple[4]的Interledger協(xié)議。著名的側(cè)鏈BTC Relay[5]是一種基于以太坊的智能合約，將比特幣和以太坊以一種安全去中心化的方式連接起來(lái)。Wanchain[6]和Fusion[7]是兩種目前較為流行的分布式私鑰控制跨鏈方案，雖然在一定程度上實(shí)現(xiàn)了多鏈間價(jià)值轉(zhuǎn)移，但因基于智能合約，能夠?qū)崿F(xiàn)的交易類(lèi)型還非常有限。

2013年5月，Tier Nolan提出了原子交換的思路[8]，實(shí)現(xiàn)跨鏈交易的原子性。Tier Nolan的技術(shù)方案經(jīng)過(guò)改進(jìn)升級(jí)后被稱為哈希鎖定，并成為跨鏈的一種主要技術(shù)手段。除了Bitshares、Stellar、Loopring等去中心化交易所，關(guān)于討論多方交易行為的論文還有[9]最早探討假設(shè)中介的物物交換協(xié)議[10]；分析數(shù)字貨幣網(wǎng)絡(luò)鏈下交易方式與效率[11]；不可分割商品交易探索[12]；分析多方交易存在的流動(dòng)性風(fēng)險(xiǎn)[13]；具有懲罰效應(yīng)和安全現(xiàn)金分配的分?jǐn)偠喾接?jì)算的有效協(xié)議[14,15；]嘗試在比特幣線下搭建雙重微支付渠道解決多方交易問(wèn)題[16]；提出了一種針對(duì)多方電子支付訂單撮合的新算法。在利用圖論理論闡述交易協(xié)議問(wèn)題方面，IOTA[17]和Byteball[18]利用有向無(wú)環(huán)圖，提高了系統(tǒng)交易效率，Maurice Herlihy提出用強(qiáng)有向連通圖證明了雙方HTLC的原子性[19]。

3 協(xié)議設(shè)計(jì)

從三方的跨鏈協(xié)議說(shuō)起，首先用一個(gè)簡(jiǎn)單的故事描述這種交易需求：有三個(gè)交易方，即Alice、Bob、Cindy。Alice想用蘭博基尼換取15萬(wàn)元的人民幣；Bob想用比特幣換取蘭博基尼；Cindy想用15萬(wàn)元的人民幣換取比特幣，如圖1所示。

圖1 三方原子交換協(xié)議

3.1 三方協(xié)議

下面假設(shè)Alice、Bob、Cindy的強(qiáng)有向連通圖(V,E)已經(jīng)通過(guò)系統(tǒng)自動(dòng)匹配的方式建立完畢，系統(tǒng)生成三個(gè)參數(shù)：第一個(gè)是V 中點(diǎn)的個(gè)數(shù)3；第二個(gè)是2*3*Δ記為T(mén)ime Lock時(shí)間鎖定值；第三個(gè)是Alice、Bob、Cindy三者中的一個(gè)隨機(jī)參與方。具體協(xié)議是雙方原子交換協(xié)議的一種平凡擴(kuò)展，具體詳見(jiàn)[19]。協(xié)議中設(shè)立一種激活函數(shù)，是協(xié)議的每一個(gè)參與方交易需要觸發(fā)的條件。經(jīng)過(guò)六步操作，假設(shè)每一步操作至多Δ時(shí)間，且整個(gè)協(xié)議在6Δ內(nèi)完成。當(dāng)計(jì)時(shí)結(jié)束后，確認(rèn)三個(gè)激活函數(shù)都激活完畢。若計(jì)時(shí)結(jié)束后，其中一個(gè)激活函數(shù)未激活完畢，則協(xié)議不會(huì)發(fā)送交易單，此時(shí)交易失敗。

3.2 n方協(xié)議設(shè)計(jì)

3.2.1 n方協(xié)議的數(shù)學(xué)建模

為了將n方協(xié)議的過(guò)程表達(dá)清楚，首先運(yùn)用矩陣與圖論的數(shù)學(xué)方法對(duì)n個(gè)交易方m種數(shù)字貨幣的交易問(wèn)題進(jìn)行建模。

定義1：矩陣A={A1, A2,..., An}T 為交易矩陣，第i 個(gè)交易方的資產(chǎn)交換需求被描述為Ai=(ai1, ai2,..., aij,...,aim)。其中aij∈Z，表示第i個(gè)交易方對(duì)與第j種數(shù)字貨幣的需求情況。例如ai1=2，表示第i個(gè)交易方想要買(mǎi)入2個(gè)第一種數(shù)字貨幣，如果ai1=-2，則表示第i個(gè)交易方想要賣(mài)出2個(gè)第一種數(shù)字貨幣。

例如3 個(gè)交易方三種數(shù)字貨幣的交易矩陣A如下：

定理1：交易矩陣A是一個(gè)可交易矩陣當(dāng)且僅當(dāng)交易矩陣A滿足

根據(jù)定義1，可以將交易矩陣A 交易的過(guò)程，被描述為矩陣A 的每一列變?yōu)榱阆蛄康倪^(guò)程。這有助于后續(xù)對(duì)“邊著色”算法進(jìn)行優(yōu)化時(shí)從矩陣變換的角度優(yōu)化問(wèn)題。

定義2：圖G 是一個(gè)有序二元組(V,E)，其中V 為 頂 集(V e r t i c e s S e t)，E 為 邊 集(E d g e s s e t)，將交易方定義為頂，雙方的交易表示為邊，E 邊集按照交易數(shù)字貨幣的種類(lèi)劃分為E={E1, E2,..., Em}T。定義交易矩陣中aij為正的值為圖的該頂點(diǎn)的入度，aij為負(fù)的值為圖的該頂點(diǎn)的出度。

定義3：矩陣V為價(jià)格期望矩陣V，例如三個(gè)交易方3種數(shù)字貨幣的價(jià)格期望矩陣如下：

其中Vi是第i 個(gè)交易方的價(jià)格期望向量Vi=(vi1, vi2,..., vij, vim)T, vi1為第i個(gè)交易方對(duì)于第一種數(shù)字貨幣的價(jià)格期望，該期望是一種比例數(shù)。例如，假設(shè)交易平臺(tái)的平臺(tái)幣與美元等值，即一個(gè)交易平臺(tái)的平臺(tái)幣可以換取1美元，那么對(duì)于比特幣，其價(jià)格期望為對(duì)應(yīng)交易方對(duì)于比特幣兌換美元的價(jià)格期望。某交易方的比特幣的價(jià)格期望可以填寫(xiě)為4503.72。

若交易平臺(tái)沒(méi)有平臺(tái)幣，則可以假設(shè)第一種數(shù)字貨幣為基準(zhǔn)，比如以比特幣為第一種數(shù)字貨幣且為基準(zhǔn)，第二種數(shù)字貨幣為以太坊，則某交易方對(duì)于第一種數(shù)字貨幣比特幣的價(jià)格期望為1，第二種數(shù)字貨幣以太坊的價(jià)格期望為0.033，表示該交易方愿意用0.033個(gè)比特幣換取一個(gè)以太坊。

3.2.2 n方協(xié)議過(guò)程

將三方協(xié)議擴(kuò)展至n 方時(shí)，首先要考慮的是，n個(gè)交易方的需求如何匹配的問(wèn)題。若想要n個(gè)交易方之間能夠在保證每個(gè)人都不虧錢(qián)的情況下進(jìn)行資產(chǎn)交易完成各自的需求，矩陣A需要滿足下面兩個(gè)條件：

假設(shè)上述兩個(gè)條件在我們的交易環(huán)境中能夠被滿足，那么如何執(zhí)行協(xié)議能夠?qū)崿F(xiàn)所有交易方的交易需求。先考慮一種簡(jiǎn)單情況：有甲、乙、丙、丁四個(gè)交易方，A、B、C 三種數(shù)字貨幣，每個(gè)交易方的需求如表1所示。

從加總列和加總行可以得知，該矩陣滿足交易的兩個(gè)前提條件，即該交易環(huán)境能實(shí)現(xiàn)所有交易方的交易需求。然后進(jìn)行協(xié)議算法。

a) 從表的第一列開(kāi)始，選擇第一列從上往下的第一個(gè)正數(shù)a11為起點(diǎn)，第一列從當(dāng)前正數(shù)往下的第一個(gè)負(fù)數(shù)a31為終點(diǎn)，箭頭的權(quán)重為2，表示甲將2個(gè)A給乙。因?yàn)?-4=-2，所以a11的值變?yōu)?，同時(shí)a31的值變?yōu)?2。

b) 變換表格，繼續(xù)從第一列從上往下進(jìn)行選擇，選擇第一個(gè)正數(shù)a41為起點(diǎn)，第一個(gè)負(fù)數(shù)a11為終點(diǎn)，表示丁將2個(gè)A給丙。此時(shí)，a41的值變?yōu)?，a31的值也變?yōu)?。

c) 經(jīng)過(guò)前兩步，第一列的所有值都變?yōu)?，結(jié)束對(duì)第一列的計(jì)算，第二列按照第一列的算法進(jìn)行計(jì)算，直至第二列都變?yōu)?。

d) 第三列同理。

以交易者為圖的頂點(diǎn)，交易為邊，用不同的顏色表示不同的貨幣品種對(duì)圖進(jìn)行著色，按照步驟進(jìn)行“邊著色圖”如圖2所示。

表1 4方數(shù)字貨幣需求

圖2 4方原子交換協(xié)議

上面是問(wèn)題2在4個(gè)交易方3種貨幣下的算法舉例，下面說(shuō)明n個(gè)人m種貨幣時(shí)的算法步驟：

a) 從i=1開(kāi)始遍歷所有ai1，當(dāng)ai1＞0時(shí)，令a=ai1，再?gòu)膉=1開(kāi)始遍歷所有aj1，當(dāng)aj1＜0時(shí)，令b=aj1。

b) 若|a|≤|b|，則ai1=0，aj1=|a|-|b|；若|a|＞|b|，則ai1=|a|-|b|，ai1=0。

c) 重復(fù)步驟a)和b)，當(dāng)i[1,n],ai1=0時(shí)，第1種貨幣交易結(jié)束。

下面用同樣的方法處理其它m-1種貨幣，下面敘述第k種貨幣的情形：

d) 從i=1開(kāi)始遍歷所有ak，當(dāng)aik＞0時(shí)，令a=aik，再?gòu)膉=1開(kāi)始遍歷所有ajk，當(dāng)ajk＜0時(shí)，令b=ajk。

e) 若|a|≤|b|，則aik=0，ajk=|a|-|b|；若|a|＞|b|，則aik=|a|-|b|,ajk=0。

f) 重復(fù)步驟d)和e)，當(dāng)i[1,n],aik=0時(shí)，第k種貨幣交易結(jié)束。

當(dāng)i [1,n],k∈[1,m],aik=0時(shí),則所有貨幣的交易完成。

關(guān)于自動(dòng)撮合交易的算法需要依據(jù)圖的搜索策略。平面圖的搜索策略包括廣度優(yōu)先搜索、深度優(yōu)先搜索和啟發(fā)式搜索三種。Dijkstra算法是一種特殊的廣度優(yōu)先搜索，也是最經(jīng)典的一種最短路徑搜索算法，但基于我們的問(wèn)題，要保持行向量和為零的條件下進(jìn)行搜索與上面三種搜索方法都不盡相同，更優(yōu)化的路徑還需要等待我們繼續(xù)深入研究才能得到。

3.2.3 n方協(xié)議的價(jià)格磋商機(jī)制

“邊著色”算法解決了當(dāng)不同貨幣等值的情況下，交易的匹配問(wèn)題，但真實(shí)的情況往往是非等值的情況，例如按照目前市場(chǎng)價(jià)格，1個(gè)比特幣大約可以換取30個(gè)以太坊。本文提出一種關(guān)于n方協(xié)議的價(jià)格磋商機(jī)制，用于解決在不同貨幣不等值的情況下交易的匹配問(wèn)題。

設(shè)m 種貨幣之間的價(jià)值比為：(v1, v2,..., vm)，例如比特幣與以太坊的價(jià)值比可表示為（30,1），即：

此時(shí)，問(wèn)題1中，交易的可執(zhí)行條件中的第一個(gè)條件，變成了：

即第i個(gè)交易方買(mǎi)入與賣(mài)出的資產(chǎn)等價(jià)，既不能虧錢(qián)也不能獲利。現(xiàn)實(shí)情況是，并沒(méi)有放之天下皆準(zhǔn)的定價(jià)規(guī)則，所以對(duì)于(v1, v2,..., vm)一千個(gè)交易方中就有一千種答案，交易所需要對(duì)一千個(gè)交易方的答案進(jìn)行均衡，在保證公平的前提下完成交易。在我們的場(chǎng)景中，對(duì)于每個(gè)交易方的價(jià)格期望，對(duì)應(yīng)交易矩陣，產(chǎn)生了下面的價(jià)格期望矩陣V，例如：

其中，Vi是第i 個(gè)交易方的價(jià)格期望向量Vi=(vi1, vi2,..., vij,..., vim)T,m仍然表示交易的貨幣種類(lèi)數(shù)量。接下來(lái)，需要處理的問(wèn)題是，n個(gè)交易方m種貨幣，交易矩陣A與價(jià)格期望矩陣V已知，且滿足的條件下，如何對(duì)n個(gè)交易方進(jìn)行交易匹配，在保證公平的前提下完成交易。

這里，還需要提出一些隱含的假設(shè)，確保協(xié)議的有效性，也便于為后續(xù)的探索理清思路。

a) 假設(shè)進(jìn)行交易的交易方填寫(xiě)的交易矩陣A和價(jià)格期望矩陣V都是自己真實(shí)想要交易的情況。

b) 我們假設(shè)存在一種平臺(tái)幣，使得每個(gè)交易方對(duì)于各個(gè)幣種的價(jià)格都能有一定的衡量尺度，例如將第一列的貨幣設(shè)為平臺(tái)幣，則每個(gè)交易方的價(jià)格期望向量中的第一項(xiàng)變?yōu)?，即

為了在公平的狀況下實(shí)現(xiàn)交易，那么平臺(tái)必須通過(guò)對(duì)每個(gè)交易方的價(jià)格期望矩陣進(jìn)行折衷，取得一個(gè)使所有人的損失最小的價(jià)格進(jìn)行交易。設(shè)這個(gè)價(jià)格為P=(p1, p2,..., pj,..., pm)T.則每個(gè)交易方的損失可以被表示為下面的問(wèn)題轉(zhuǎn)化為，如何取P使得最小.化簡(jiǎn)Δ：

令σ定義為n個(gè)交易m種貨幣交易狀態(tài)下的方差，則：

展開(kāi)得到：

上式是關(guān)于p1到pn的多元二次函數(shù)，因?yàn)樗远魏瘮?shù)開(kāi)口向上，函數(shù)有最小值，可以求得，方差取最小值時(shí)，p1到pn的值為：

方差的最小值為：

至此，首先提出所有交易方損失的總和與選取的P值無(wú)關(guān)，其次證明了當(dāng)P取(1)值時(shí)，所有交易方損失的方差最小，也就是交易達(dá)到了公平原則。

此時(shí)，n方協(xié)議“邊著色”算法按照每種不同貨幣進(jìn)行交易，所以每種幣的價(jià)值并不影響我們的算法，算法可以如期進(jìn)行。n方協(xié)議的意義在于：不需要第三方交易所，而可以在去中心化的交易所為n個(gè)人m種貨幣交易進(jìn)行需求匹配，且保證交易的公平性與原子性。

4 結(jié)束語(yǔ)

本文提出了一種基于哈希鎖定的多方跨鏈協(xié)議，用于解決多方跨鏈資產(chǎn)轉(zhuǎn)移的清結(jié)算問(wèn)題。

首先，通過(guò)對(duì)雙方原子交換協(xié)議進(jìn)行擴(kuò)展，提出了三方至n方的原子交換過(guò)程。

其次，本文對(duì)n方交易進(jìn)行建模，定義了交易矩陣和價(jià)格期望矩陣，解決了n方協(xié)議的價(jià)格磋商問(wèn)題，證明了總損失只與交易矩陣和價(jià)格期望矩陣有關(guān)，與平臺(tái)提供的最終交易價(jià)格無(wú)關(guān)。為了保證交易的公平性，本文求出了總損失最小時(shí)的最優(yōu)交易價(jià)格。

最后，基于最優(yōu)交易價(jià)格，本文提出了一種自動(dòng)撮合交易算法，可以在多方多鏈情況下匹配交易，實(shí)現(xiàn)無(wú)需第三方的交易協(xié)議。本文的創(chuàng)新點(diǎn)在于用數(shù)學(xué)建模的方法將n方交易的復(fù)雜問(wèn)題模型化，并提出了最優(yōu)交易價(jià)格，在保證公平的前提下，實(shí)現(xiàn)了交易所的去中心化。

比特幣誕生10年，人們一直在追逐卻從未真正超越比特幣。它理論的完美性，源于它對(duì)于人性的挖掘。數(shù)據(jù)層、網(wǎng)絡(luò)層、共識(shí)層、激勵(lì)層、合約層層層相扣，缺一不可。中國(guó)數(shù)字貨幣研究所所長(zhǎng)姚前教授，曾在一篇名為《去中心化資產(chǎn)交易：一種新的金融市場(chǎng)模式》的文章中指出，隨著技術(shù)的發(fā)展深入，業(yè)界希望對(duì)現(xiàn)行模式作出變革，即真正發(fā)揮區(qū)塊鏈技術(shù)的特點(diǎn)實(shí)現(xiàn)去中心化資產(chǎn)交易。