基于哈希鎖定的多方跨鏈協議研究

張詩童, 秦波，鄭海彬

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

1 引言

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

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

2 區塊鏈的跨鏈需求及技術難點

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

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

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

3 協議設計

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

圖1 三方原子交換協議

3.1 三方協議

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

3.2 n方協議設計

3.2.1 n方協議的數學建模

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

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

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

定理1：交易矩陣A是一個可交易矩陣當且僅當交易矩陣A滿足

根據定義1，可以將交易矩陣A 交易的過程，被描述為矩陣A 的每一列變為零向量的過程。這有助于后續對“邊著色”算法進行優化時從矩陣變換的角度優化問題。

定義2：圖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 邊集按照交易數字貨幣的種類劃分為E={E1, E2,..., Em}T。定義交易矩陣中aij為正的值為圖的該頂點的入度，aij為負的值為圖的該頂點的出度。

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

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

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

3.2.2 n方協議過程

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

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

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

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

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

c) 經過前兩步，第一列的所有值都變為0，結束對第一列的計算，第二列按照第一列的算法進行計算，直至第二列都變為0。

d) 第三列同理。

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

表1 4方數字貨幣需求

圖2 4方原子交換協議

上面是問題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時,則所有貨幣的交易完成。

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

3.2.3 n方協議的價格磋商機制

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

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

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

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

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

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

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

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

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

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

展開得到：

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

方差的最小值為：

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

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

4 結束語

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

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

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

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

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