摘要：區(qū)塊鏈技術(shù)是當(dāng)前熱門的互聯(lián)網(wǎng)技術(shù)之一，因其去中心化、可追溯、不可篡改和不可偽造等優(yōu)良特性，被廣為熟知與應(yīng)用。當(dāng)前，在區(qū)塊鏈技術(shù)面臨的諸多挑戰(zhàn)中，區(qū)塊鏈之間的互通性問題因為鏈的特異性強、種類繁多而日益凸顯?？珂溂夹g(shù)是解決這一問題的關(guān)鍵所在。論文提出了一種基于哈希鎖定的多方跨鏈協(xié)議，用于解決多方跨鏈資產(chǎn)轉(zhuǎn)移的清結(jié)算問題。文中的“邊著色”自動撮合交易算法，可以在多方多鏈情況下快速匹配交易，實現(xiàn)交易所的去中心化，解決現(xiàn)有交易所因中心化而產(chǎn)生的信任問題。論文還提出了一種價格磋商機制，在保證公平性的前提下求出了多方交易多種貨幣時的最優(yōu)價格

　　關(guān)鍵詞：區(qū)塊鏈；跨鏈技術(shù)；哈希鎖定；原子交換協(xié)議

　　中圖分類號：F274；TP311.5 文獻(xiàn)標(biāo)識碼：A

　　1 引言

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

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

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

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

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

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

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

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

　　3.1 三方協(xié)議

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

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

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

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

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

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

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

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

　　定義2：圖G是一個有序二元組(V，E)，其中V為頂集(Vertices Set)，E為邊集(Edges set)，將交易方定義為頂，雙方的交易表示為邊，E邊集按照交易數(shù)字貨幣的種類劃分為E={E1， E2，...， Em}T。定義交易矩陣中aij為正的值為圖的該頂點的入度，aij為負(fù)的值為圖的該頂點的出度。

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

　　.

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

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

　　3.2.2 n方協(xié)議過程

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

　　a) ，即每個交易方買入與賣出的資產(chǎn)等價，如果將交易方看作圖中的頂點，則本條件需要使每個頂點的入度和等于出度和。

　　b) ，即每種貨幣的買入與賣出相同，才能保證市場是均衡的，交易可實現(xiàn)。

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

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

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

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

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

　　d) 第三列同理。

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

　　上面是問題2在4個交易方3種貨幣下的算法舉例，下面說明n個人m種貨幣時的算法步驟：

　　a) 從i=1開始遍歷所有ai1，當(dāng)ai1>0時，令a=ai1，再從j=1開始遍歷所有aj1，當(dāng)aj1<0時，令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時，第1種貨幣交易結(jié)束。

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

　　d) 從i=1開始遍歷所有ak，當(dāng)aik>0時，令a=aik，再從j=1開始遍歷所有ajk，當(dāng)ajk<0時，令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時，第k種貨幣交易結(jié)束。

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

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

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

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

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

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

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

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

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

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

　　b) 我們假設(shè)存在一種平臺幣，使得每個交易方對于各個幣種的價格都能有一定的衡量尺度，例如將第一列的貨幣設(shè)為平臺幣，則每個交易方的價格期望向量中的第一項變?yōu)?，即vi1=1，i∈[1，n]。

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

　　=

　　因為，故與P值無關(guān)，故價格的選取只與每個交易方想要交易的數(shù)量和價格期望有關(guān)。為了保證公平性，還需要考慮的因素是所有交易方的方差。方差體現(xiàn)交易方交易損失的均衡情況，方差越大，表示交易方損失之間的差別越大，方差越小，表示交易方損失較為均衡。下面，先定義方差的公式：

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

　　展開得到：

　　上式是關(guān)于p1到pn的多元二次函數(shù)，因為，所以二次函數(shù)開口向上，函數(shù)有最小值，可以求得，方差取最小值時，p1到pn的值為：

　　方差的最小值為：

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

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

　　4 結(jié)束語

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

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

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

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

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

　　基金項目：

　　1.科技部國家重點研發(fā)計劃（項目編號：2017YFB1400700）；

　　2.國家自然科學(xué)基金面上項目（項目編號：61772538和61672083）；

　　3.國家自然科學(xué)基金重點項目（項目編號：91646203和61532021）；

　　4.信息保障技術(shù)重點實驗室開放基金項目（項目編號：61421120305162112006）；

　　5.十三五國家密碼發(fā)展基金密碼理論課題（項目編號：MMJJ20170106）。

　　參考文獻(xiàn)

　　[1] Nakamoto Satoshi. Bitcoin： A Peer-To-Peer Electronic Cash System. 2009.

　　[2] Vitalik Buterin. On Public and Private Blockchains. 2015.

　　[3] Vitalik Buterin. A Next-Generation Smart Contract and Decentralized Application Platform. https：//github.com/ethereum/wiki/wiki/White-Paper. 2014.

　　[4] David Schwartz， Noah Youngs， Arthur Britto. The Ripple Protocol Consensus Algorithm. 2014.

　　[5] BTC Relay. https：//github.com/Ethereum/btcrelay. 2018.

　　[6] Jack Lu， Boris Yang， Zane Liang， Ying Zhang， el al. WanChain. https：//www.chainwhy.com/upload/default/20180615/3dd1f9350b626b6b5371906f2acdaa78.pdf. 2017.

　　[7] Fusion Foundation. An Inclusive Cryptofinance Platform Based on Blockchain. https：//www.chainwhy.com/upload/default/20180619/299dd7eb20e20760b4e53dd5b6c05a6e.pdf. 2017.

　　[8] Tier Nolan. Alt Chains and Atomic Transfers. 2013.

　　[9] Matt Franklin， Gene Tsudik. Secure Group Barter： Multi-Party Fair Exchange with Semi-Trusted Neutral Parties. 1998.

　　[10] Rami Khalil， Arthur Gervais. Revive： Rebalancing Off-Blockchain Payment Networks. In Proceedings of the 2017 ACM SIGSAC Conference on Computer and Communications Security， CCS ’17. 2017.

　　[11] Lloyd Shapley， Herbert Scarf. On Cores and Indivisibility. Journal of Mathematical Economics.

　　[12] Adam Back， Matt Corallo， Luke Dashjr， Mark Friedenbach， et al. Enabling Blockchain Innovations with Pegged Sidechains. 2014.

　　[13] Iddo Bentov， Ranjit Kumaresan， Andrew Miller. Instantaneous Decentralized Poker. https： //arxiv.org/abs/1701.06726. 2017.

　　[14] Christian Decker， Roger Wattenhofer. A Fast and Scalable Payment Network with Bitcoin Duplex Micropayment Channels. Springer International Publishing. 2015.

　　[15] Matthew Green， Ian Miers. Bolt： Anonymous Payment Channels for Decentralized Currencies. Cryptology ePrint Archive： Report 2016/701. 2016.

　　[16] Randy M. Kaplan. An Improved Algorithm for Multi-Way Trading for Exchange and Barter. Electronic Commerce Research and Applications. 2011.

　　[17] Serguei Popov. The Tangle. http：//www.descryptions.com/Iota.pdf. 2018.

　　[18] Anton Churyumov. Byteball： A Decentralized System for Storage and Transfer of Value. 2016.

　　[19] Maurice Herlihy. Atomic Cross-Chain Swaps. arXiv preprint arXiv：1801.09515. 2018.

　?。?. 中國人民大學(xué)信息學(xué)院，北京100872；2. 北京航空航天大學(xué)電子信息工程學(xué)院，北京 100191；3. 信息保障技術(shù)重點實驗室，北京 100072）

　　張詩童1， 秦波1，鄭海彬2，3

關(guān)注讀覽天下微信， 100萬篇深度好文， 等你來看……