基于DAG的聯(lián)盟鏈共識機(jī)制研究與分析

宋東翔，馬伽洛倫，王怡然，朱福林通信作者）

1.德宏師范高等專科學(xué)校，云南德宏，678400；2.德宏職業(yè)學(xué)院，云南德宏，678400； 3.德宏州衛(wèi)生健康委員會(huì)計(jì)劃生育協(xié)會(huì)，云南德宏，678400

0 引言

有向無環(huán)圖DAG（directed acyclic graph）采用了有向無環(huán)圖的存儲結(jié)構(gòu)，是一種新的區(qū)塊鏈存儲結(jié)構(gòu)[1]。但其仍然面臨著許多問題，例如是否能夠像鏈?zhǔn)絽^(qū)塊鏈存儲那樣可以使分布式存儲的信息保持一致、是否會(huì)產(chǎn)生拜占庭將軍問題、雙花問題要怎么處理等[2]。近年來，已經(jīng)有很多學(xué)術(shù)論文和科技公司針對這些問題做了大量的研究。拜占庭將軍問題（byzantine failures）是由萊斯利·蘭伯特提出的點(diǎn)對點(diǎn)通信中的基本問題[3]，而一個(gè)可能呈現(xiàn)任意行為的節(jié)點(diǎn)被稱為拜占庭。任意行為意味著“所有能想象到的事情”，比如根本不發(fā)送任何消息、向不同的鄰居發(fā)送不同且錯(cuò)誤的消息以及謊報(bào)自己的輸入值。雙花問題簡單來說就是消費(fèi)兩次，例如：在A商店買了一瓶水，在B商店買了一包瓜子，兩個(gè)商店幾乎同時(shí)消費(fèi)；假設(shè)商店都不等待確認(rèn)，如果A或B商店支付結(jié)束后其中一家沒有收到貨幣，這樣就實(shí)現(xiàn)了一次雙花。對于這些問題，IOTA團(tuán)隊(duì)提出使用PoW權(quán)重比較進(jìn)行共識的解決方案[4]；Byteball和TrustNote則提出選取公證人共識節(jié)點(diǎn)進(jìn)行共識，由公證共識節(jié)點(diǎn)提交公證單元來完成MC定序，判斷查找出無效單元，避免雙花攻擊。本文主要基于DAG的區(qū)塊鏈拜占庭共識和雙花問題進(jìn)行研究，對IOTA-PoW權(quán)重、Byteball公證人節(jié)點(diǎn)和TrustNote公證人節(jié)點(diǎn)的共識方法進(jìn)行比較[5-6]。

1 DAG的技術(shù)

如圖1所示，G單元為創(chuàng)世單元，無序號單元為未引用單元（或無字單元），單元14被藍(lán)色單元15引用，稱為直接引用。由藍(lán)色單元15順著圖的方向到達(dá)創(chuàng)世單元G的主鏈MC（main chain），對所有單元進(jìn)行的排序稱為主鏈索引MCI（main chain index）[7]。單元9被MC上的單元10和不在MC上的黃色單元11所引用，由于單元10在MC上面，單元10的MCI為10；黃色單元11不在MC上，但是黃色單元11被MC的單元11直接引用，所以黃色單元11分配的MCI為11。同理，黃色單元15被MC上的單元15引用，稱為間接引用，黃色單元的MCI為15。如果一個(gè)DAG序列受到雙花攻擊，有可能出現(xiàn)兩種情況。①兩個(gè)相同數(shù)據(jù)輸出的單元被有序引用，即一個(gè)單元（直接或間接）中包括另一個(gè)單元；如圖1所示，在先提交了藍(lán)色單元14之后，后來的藍(lán)色單元15如果提交相同的輸出，此時(shí)通過判斷父單元的數(shù)據(jù)發(fā)現(xiàn)雙花，則利用DAG的共識安全地拒絕后面的藍(lán)色單元15。②建立單元之間的總序后，他們隱藏在足夠深的新單元里；如圖1所示，黃色的單元11和單元15都不屬于同一序列，他們之間是無序關(guān)系，此時(shí)系統(tǒng)無法分辨出哪個(gè)單元的信息有效，只能先接收，再通過后續(xù)主鏈單元間接引用共識數(shù)據(jù)。

2 方法研究

2.1 IOTA

IOTA提出了自己的系統(tǒng)結(jié)構(gòu)Tangle（纏結(jié)），基于有向無環(huán)圖結(jié)構(gòu)（DAG）不是一種連續(xù)的鏈?zhǔn)郊軜?gòu)，不能夠定期添加區(qū)塊[8]。如圖2所示，每個(gè)表示交易的小方塊右下角的數(shù)字被稱為權(quán)重，這個(gè)權(quán)重t是和PoW所付出的計(jì)算量相關(guān)的。假如有2筆交易，通過PoW（proof of work）算出來的二進(jìn)制值分別為x和y，x的開頭是2個(gè)0，y的開頭是4個(gè)0，得到y(tǒng)所需要的計(jì)算量一定是大于x的，所以交易y的權(quán)重會(huì)比交易x的權(quán)重大。在IOTA里，權(quán)重的取值范圍是3n，所以權(quán)重t的取值只可能是如1、3、9、27之類的數(shù)。方塊里左上角的數(shù)字被稱為累積權(quán)重，等于這個(gè)交易自己的權(quán)重加上所有直接或間接指向它的交易的權(quán)重總和。比如交易F，直接或間接指向F的有A、B、C、E，所以F的累計(jì)權(quán)重為1+3+1+1+3=9。IOTA解決雙花問題的方法是：節(jié)點(diǎn)會(huì)計(jì)算每個(gè)交易的權(quán)重值，選擇權(quán)重高的交易來進(jìn)行驗(yàn)證，有助于增加自己的交易被后來交易驗(yàn)證的可能性。如果這筆交易非法綁定，后來的交易則不會(huì)選擇這筆交易來驗(yàn)證。交易數(shù)量越來越多，這筆沒有被驗(yàn)證的交易就會(huì)被網(wǎng)絡(luò)拋棄。如圖2所示，通過協(xié)議選擇累計(jì)權(quán)重高的單元F去計(jì)算權(quán)重值，需要計(jì)算的權(quán)重值為3，F(xiàn)單元的累計(jì)權(quán)重為9，后來通過驗(yàn)證F成功產(chǎn)生的單元Q是在F之后，完成驗(yàn)證。

2.2 Byteball

Byteball解決雙花問題，是通過觀察網(wǎng)絡(luò)的一些參與者，他們可能是非匿名長期參與社區(qū)并且擁有良好信譽(yù)的，或許是主動(dòng)維護(hù)網(wǎng)絡(luò)健康發(fā)展的，這些參與者統(tǒng)稱為證人[9]，證人會(huì)在一個(gè)周期內(nèi)循環(huán)發(fā)布公證單元參與系統(tǒng)的共識。如果需要驗(yàn)證公證單元的真實(shí)性，回溯DAG鏈中的MC，統(tǒng)計(jì)成為公證單元的個(gè)數(shù)（對于重復(fù)的公證單元不會(huì)被重復(fù)計(jì)數(shù)）。如圖3所示，把P作為證人發(fā)布的公證單元，選擇一個(gè)MC上的交易單元W，在MC上向創(chuàng)世單元G做回溯，統(tǒng)計(jì)成為公證單元的數(shù)量為5個(gè)，分別是單元9、單元7、單元6、單元4和單元1。回溯時(shí)遇到公證單元?jiǎng)t停止前進(jìn)，計(jì)算從創(chuàng)世單元到停止單元的長度，這個(gè)長度被稱為停止單元的級別。例如在回溯到公證單元7和公證單元6時(shí)，看見公證單元，停止回溯，通過計(jì)算，選擇的最大停止單元級別為7，同時(shí)該公證單元的父母單元被選擇為最佳父母單元。如果同時(shí)存在一些較大見證級別的競爭者參與競爭，則會(huì)選擇其中最低級別的父母單元。如果一個(gè)攻擊者自己秘密建立一個(gè)屬于自己的單元長鏈（影子鏈），其中還包含了雙花，如圖3所示，在圖中紅色圈內(nèi)顯示為灰色的單元鏈就是影子鏈。影子鏈最終合并到了DAG序列中，這時(shí)最佳父母選擇算法會(huì)在合并點(diǎn)處把影子鏈驅(qū)動(dòng)到MC的最佳父母單元，由于影子鏈中的單元被最佳父母單元15直接和間接引用，所以他們的MCI只能為15，但這些單元數(shù)據(jù)都不在MC上，所以這段影子鏈的單元數(shù)據(jù)都被視為無效。

2.3 TrustNote

TrusNote團(tuán)隊(duì)提出了TrustME-PoW的共識算法，使用PoW的工作量證明共識機(jī)制選取公證人[10]。TrustME-PoW中提出了超級節(jié)點(diǎn)的概念，只有超級節(jié)點(diǎn)才具有爭奪成為公證人的資格。要成為超級節(jié)點(diǎn)，需要滿足以下的條件：①具有良好的網(wǎng)絡(luò)帶寬資源、存儲空間和運(yùn)算能力，有獨(dú)立公網(wǎng)IP的最好；②需要在共識周期內(nèi)有足夠的TrusNote虛擬貨幣作為激勵(lì)機(jī)制的獎(jiǎng)勵(lì)；③在之前的共識中，提交的所有公證單元都被全網(wǎng)認(rèn)證為有效。該算法每輪共識都會(huì)選擇參與競選的少量超級節(jié)點(diǎn)成為公證節(jié)點(diǎn)，并確定公證節(jié)點(diǎn)的優(yōu)先級。每一輪TrustMEPoW共識算法的執(zhí)行周期是五分鐘，每次共識完成都會(huì)選出不超過二十個(gè)超級節(jié)點(diǎn)作為公證節(jié)點(diǎn)，被選擇的公證節(jié)點(diǎn)有權(quán)利發(fā)送公證單元并且以此獲得虛擬貨幣作為公證獎(jiǎng)勵(lì)。該算法解決雙花問題的方法是嘗試在DAG圖上找到一條以創(chuàng)世單元為起點(diǎn)的MC，并給位于MC上的單元分配索引，創(chuàng)世單元的索引為0，創(chuàng)世單元的子單元索引為1，以此類推。然后，對于不在MC上的單元，定義其索引等于引用此單元的第一個(gè)MC單元的索引。最終，DAG序列上的每筆交易都擁有了一個(gè)索引。如果兩筆交易嘗試使用同一筆輸出，只需要比較MCI的大小，小的有效，大的無效，由此解決雙花問題。例如DAG中存在兩筆雙花交易，首先通過MC為單元定序MCI，當(dāng)確定了它們的MCI，其中一筆雙花的MCI是11，而另一筆雙花的MCI是15；通過比較兩筆交易的MCI，判斷具有較小MCI的交易11有效，大的MCI交易15無效。

3 綜合分析

通過模擬實(shí)驗(yàn)測試，對以下四個(gè)性能指標(biāo)進(jìn)行分析。①時(shí)延：表示改進(jìn)的共識算法在執(zhí)行過程中所花的時(shí)間，該時(shí)間的減少會(huì)減少用戶的等待時(shí)間，改善用戶對應(yīng)用的體驗(yàn)。②成本：是指對于全網(wǎng)系統(tǒng)的經(jīng)濟(jì)投入，如果參與全網(wǎng)的共識節(jié)點(diǎn)的經(jīng)濟(jì)投入太大，則不利于小型聯(lián)盟鏈的建立和發(fā)展。③功耗：主要指的是在共識算法的執(zhí)行過程中，對于CPU的利用率，PoW的共識算法對于CPU的利用率非常高。④容錯(cuò)性：是指在系統(tǒng)參與共識的節(jié)點(diǎn)中，可以容忍出現(xiàn)錯(cuò)誤共識節(jié)點(diǎn)的數(shù)量；容錯(cuò)性可以保證在遭受修改共識節(jié)點(diǎn)信息等攻擊時(shí)，系統(tǒng)仍然可以良好地運(yùn)行。如表1所示，IOTA的優(yōu)點(diǎn)是采用了工作量證明，將系統(tǒng)容錯(cuò)率提升為50%。PoW算法設(shè)置的難題比區(qū)塊鏈簡單，解題時(shí)間在5～20分鐘之內(nèi)；缺點(diǎn)是每一次交易都需要節(jié)點(diǎn)去提供算力，PoW的原理就是要耗費(fèi)發(fā)起者一定量的計(jì)算資源，并且使用PoW共識的時(shí)延較高。Byteball使用選取12名公證人的共識機(jī)制，比PoW功耗低、時(shí)延高，但是這12名公證人是人為設(shè)定的，系統(tǒng)的容錯(cuò)率較低。TrusNote同樣使用PoW共識，但系統(tǒng)使用超級節(jié)點(diǎn)，通過虛擬貨幣的激勵(lì)機(jī)制保證系統(tǒng)中的超級節(jié)點(diǎn)都努力維護(hù)系統(tǒng)的穩(wěn)定運(yùn)行，使系統(tǒng)的功耗低、時(shí)延低。

表1 性能比較

4 結(jié)語

本文綜合分析了IOTA的工作量證明共識、Byteball的選取公證人機(jī)制和TrusNote的TrustME-PoW共識算法三種基于DAG數(shù)據(jù)結(jié)構(gòu)的共識方法。這三種方法都能夠應(yīng)對拜占庭容錯(cuò)和雙花攻擊問題，但通過性能分析，三種方法都不適用于當(dāng)前聯(lián)盟鏈的應(yīng)用場景。本文綜合三種方法，基于TrustME-PoW共識算法提出了改進(jìn)思想：①取消超級節(jié)點(diǎn)的設(shè)定，降低聯(lián)盟鏈中節(jié)點(diǎn)配置所產(chǎn)生的經(jīng)濟(jì)成本；②取消PoW工作量證明的提供算力的算法，降低對節(jié)點(diǎn)的資源消耗；③刪除使用虛擬代幣作為獎(jiǎng)勵(lì)的激勵(lì)機(jī)制，采用信用積分機(jī)制來作為系統(tǒng)共識的憑據(jù)。希望在日后的研究中，能夠根據(jù)思路完成改進(jìn)。