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

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

　　中圖分類號：F274；TP311.5 文獻標識碼：A

　　1 引言

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

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

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

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

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

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

　　3 協(xié)議設計

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

　　3.1 三方協(xié)議

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

　　3.2 n方協(xié)議設計

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

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

　　定義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是一個可交易矩陣當且僅當交易矩陣A滿足且。

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

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

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

　　.

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

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

　　3.2.2 n方協(xié)議過程

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

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

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

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

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

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

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

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

　　d) 第三列同理。

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

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

　　a) 從i=1開始遍歷所有ai1，當ai1>0時，令a=ai1，再從j=1開始遍歷所有aj1，當aj1<0時，令b=aj1。

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

　　c) 重復步驟a)和b)，當i∈[1，n]，ai1=0時，第1種貨幣交易結束。

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

　　d) 從i=1開始遍歷所有ak，當aik>0時，令a=aik，再從j=1開始遍歷所有ajk，當ajk<0時，令b=ajk。

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

　　f) 重復步驟d)和e)，當i∈[1，n]，aik=0時，第k種貨幣交易結束。

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

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

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

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

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

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

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

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

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

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

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

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

　　=

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

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

　　展開得到：

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

　　方差的最小值為：

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

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

　　4 結束語

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

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

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

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

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

　　基金項目：

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

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

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

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

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

　　參考文獻

　　[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.

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

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

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