羅玉琴,關(guān)沛冬,田海博

(1.中山大學(xué) 計(jì)算機(jī)學(xué)院,廣東 廣州 510000;2.廣東省信息安全技術(shù)重點(diǎn)實(shí)驗(yàn)室,廣東 廣州 510000)

1 引 言

共識機(jī)制是區(qū)塊鏈的核心。隨著區(qū)塊鏈技術(shù)越來越受到關(guān)注,眾多的研究也在致力于開發(fā)更實(shí)用和更有效率的區(qū)塊鏈共識機(jī)制[1]。目前,區(qū)塊鏈中常用的共識機(jī)制有工作量證明(Proof Of Work,POW)、權(quán)益證明(Proof Of Stake,POS)、BFT(Byzantine Fault Tolerance)算法等。

工作量證明是早期的共識機(jī)制,在比特幣、門羅幣、萊特幣等民間數(shù)字貨幣系統(tǒng)中使用。參與方通過算力競爭來獲得記賬權(quán)。在正常情況下,系統(tǒng)中只能有單個(gè)參與方獲得記賬權(quán)。當(dāng)不誠實(shí)的參與方算力小于50%時(shí),參與方具有一致賬本的概率較高[2]。工作量證明機(jī)制的缺點(diǎn)是較為消耗資源。

權(quán)益證明共識機(jī)制最早用在Peercoin中,它依賴參與方持有幣的數(shù)量和時(shí)間。參與方的資產(chǎn)越多,持有時(shí)間越長,越可能獲得記賬權(quán)。文獻(xiàn)[3]中提出了可證明安全的POS協(xié)議Ouroboros。該協(xié)議采用了有界延遲網(wǎng)絡(luò),誠實(shí)節(jié)點(diǎn)發(fā)送的消息在已知的延時(shí)內(nèi)可以被其他誠實(shí)節(jié)點(diǎn)收到。協(xié)議中的時(shí)間劃分為時(shí)槽,每個(gè)時(shí)槽有一個(gè)領(lǐng)導(dǎo)節(jié)點(diǎn)負(fù)責(zé)生成區(qū)塊。Praos協(xié)議[4]針對Ouroboros領(lǐng)導(dǎo)節(jié)點(diǎn)存在拒絕服務(wù)攻擊的問題,采用了可驗(yàn)證隨機(jī)函數(shù)(Verifiable Random Function,VRF)來選擇領(lǐng)導(dǎo)節(jié)點(diǎn),并證明了共識的安全性。文獻(xiàn)[5]中提出的Algorand協(xié)議也采用了可驗(yàn)證隨機(jī)函數(shù)選舉領(lǐng)導(dǎo)節(jié)點(diǎn),針對異步網(wǎng)絡(luò),需要至少3輪消息驗(yàn)證和m輪拜占庭共識算法(Byzantine Agreement,BA)。權(quán)益證明共識機(jī)制中產(chǎn)生新的區(qū)塊幾乎不消耗資源,這帶來了許多新的安全威脅,其中之一為長程攻擊(Long Range Attack)[6-7],攻擊者通過獲取某個(gè)曾經(jīng)擔(dān)任領(lǐng)導(dǎo)者的節(jié)點(diǎn)私鑰,接入某個(gè)舊帳本,并偽造新賬本?？沈?yàn)證隨機(jī)函數(shù)可能導(dǎo)致權(quán)益較少的領(lǐng)導(dǎo)者被選中,增加了長程攻擊的風(fēng)險(xiǎn)。

BFT算法希望在系統(tǒng)存在拜占庭行為參與方的情況下,仍能就某一提議達(dá)成一致[8]。實(shí)際的BFT(Practical BFT,PBFT)算法[9]是第一個(gè)較為實(shí)用的BFT類算法,用在聯(lián)盟鏈Fabric 1.0中。為了提升效率,HoneyBadgerBFT算法[10]結(jié)合可靠廣播協(xié)議和二值異步拜占庭共識算法(Binary BA,BBA),實(shí)現(xiàn)了異步網(wǎng)絡(luò)的共識。Dumbo算法[11-12]進(jìn)一步提出了可證明的可靠廣播協(xié)議和多值異步拜占庭共識協(xié)議[13],提升了共識效率。

上述共識算法需要單個(gè)記賬節(jié)點(diǎn)或者領(lǐng)導(dǎo)節(jié)點(diǎn)提出建議,其他節(jié)點(diǎn)驗(yàn)證記賬不能容忍多個(gè)記賬節(jié)點(diǎn)的情況,同時(shí)沒有考慮共識對象間內(nèi)在的關(guān)系。設(shè)共識對象為交易,每個(gè)記賬節(jié)點(diǎn)通過在交易中包含舊交易的信息,可以形成交易間的引用關(guān)系。以該引用關(guān)系為邊,以交易為頂點(diǎn),可以構(gòu)成不同記賬節(jié)點(diǎn)所發(fā)出交易的有向無環(huán)圖(Directed Acyclic Graph,DAG),進(jìn)而利用有向無環(huán)圖的拓?fù)浣Y(jié)構(gòu)輔助達(dá)成關(guān)于交易的共識。因此,基于有向無環(huán)圖的共識機(jī)制具有容忍多節(jié)點(diǎn)并行記賬的能力,受到了極大的關(guān)注。

目前,有向無環(huán)圖的共識機(jī)制與工作量證明結(jié)合在一起,通過共識對象的直接和間接工作量來完成共識。文獻(xiàn)[14-15]要求創(chuàng)建交易時(shí)進(jìn)行工作量證明,從而形成每個(gè)交易的權(quán)重,進(jìn)而可以根據(jù)引用關(guān)系來計(jì)算某個(gè)交易的累積權(quán)重,以期達(dá)到該交易是否入鏈的共識。文獻(xiàn)[16]中提出了GHOST共識機(jī)制,給出通過找到最大權(quán)重子樹來確定主鏈的協(xié)議。以太坊早期采用該共識機(jī)制來解決其因挖礦難度低造成的出塊碰撞問題。文獻(xiàn)[17]中提出了Conflux共識,增加了引用邊,使得主鏈以外的合法交易也可以參與排序。文獻(xiàn)[18]中提出的Byteball共識引入了見證人機(jī)制,主鏈確認(rèn)算法依賴于見證人的信譽(yù)。基于有向無環(huán)圖和工作量證明的共識機(jī)制,新的區(qū)塊產(chǎn)生時(shí)消耗的資源很少,這一點(diǎn)帶來了新的安全威脅[15,18]。其中一種威脅為分裂攻擊,攻擊者通過發(fā)送交易,使得有向無環(huán)圖分裂為不相交的子圖,破壞共識記賬。

文獻(xiàn)[19]是首個(gè)基于有向無環(huán)圖和工作量證明的共識機(jī)制。該共識機(jī)制利用了有向無環(huán)圖允許多個(gè)記賬節(jié)點(diǎn)的特點(diǎn),由基于權(quán)益證明的領(lǐng)導(dǎo)者節(jié)點(diǎn)集合共同記賬。攻擊者此時(shí)進(jìn)行長程攻擊,需要獲取領(lǐng)導(dǎo)者集合中不少于1/3的節(jié)點(diǎn)私鑰,提高了攻擊代價(jià)。同時(shí),不多于1/3的攻擊者即便在領(lǐng)導(dǎo)者節(jié)點(diǎn)集合中,也很難破壞共識記賬過程,可以抵御分裂攻擊等行為。然而,該文只是就已有的雙花等多種攻擊進(jìn)行了分析,并沒有進(jìn)行嚴(yán)格的安全性證明,同時(shí)其關(guān)鍵的委員會(huì)協(xié)議和交易確認(rèn)算法也采用的是描述性語言,存在歧義性理解。因此,筆者給出委員會(huì)協(xié)議和交易確認(rèn)算法的正式描述,并給出詳細(xì)的安全性證明,提出了一個(gè)完整的可證明安全的權(quán)益有向無環(huán)圖共識機(jī)制。最后,基于該共識機(jī)制實(shí)現(xiàn)了一個(gè)簡單的區(qū)塊鏈系統(tǒng),測試了共識機(jī)制的性能。

2 基礎(chǔ)知識

權(quán)益有向無環(huán)圖共識機(jī)制涉及的一些基本概念包括有界延遲網(wǎng)絡(luò)、參與方及交易[19]。

2.1 有界延遲網(wǎng)絡(luò)

在有界延遲網(wǎng)絡(luò)中,如果誠實(shí)節(jié)點(diǎn)發(fā)送交易,則其他誠實(shí)節(jié)點(diǎn)一定會(huì)在Δ時(shí)間內(nèi)接收到交易。Δ是交易的最大容忍時(shí)延。有界延遲網(wǎng)絡(luò)是一個(gè)常用的同步網(wǎng)絡(luò)模型,例如PBFT[9]、Praos[4]等協(xié)議都采用了該模型。

比時(shí)延Δ大的一個(gè)時(shí)間單位是時(shí)槽,通常一個(gè)時(shí)槽定義為3倍時(shí)延。e個(gè)時(shí)槽在一起形成的一段連續(xù)時(shí)間稱為一個(gè)世代,世代從0開始計(jì)數(shù)。

2.2 參與方及交易

參與方區(qū)分為客戶端節(jié)點(diǎn)和鏈節(jié)點(diǎn)。鏈節(jié)點(diǎn)按照其工作任務(wù)分為活躍鏈節(jié)點(diǎn)、候選鏈節(jié)點(diǎn)和靜默鏈節(jié)點(diǎn)。

客戶端節(jié)點(diǎn)主要生成常規(guī)凈交易(Normal Net Transaction,NNT) 。常規(guī)凈交易用于改變鏈中賬戶的狀態(tài),例如賬戶的權(quán)益值。常規(guī)凈交易的字段包括時(shí)間戳T、計(jì)數(shù)器值c、參數(shù)消息m和前述內(nèi)容的簽名σ。

活躍鏈節(jié)點(diǎn)主要接收常規(guī)凈交易和生成鏈交易(Chain Transaction,CT)。生成鏈交易用于形成有向無環(huán)圖,輔助記賬。生成鏈交易的字段包括時(shí)間戳T、計(jì)數(shù)器值c、管理消息或常規(guī)凈交易哈希值、引用生成鏈交易的個(gè)數(shù)及引用生成鏈交易的哈希值、穩(wěn)定狀態(tài)根R和前述內(nèi)容的簽名σ。其中穩(wěn)定狀態(tài)根是S個(gè)時(shí)槽前活躍鏈節(jié)點(diǎn)狀態(tài)數(shù)據(jù)庫的默克爾根,S為系統(tǒng)參數(shù),通常為2。狀態(tài)數(shù)據(jù)庫存儲(chǔ)所有節(jié)點(diǎn)賬戶的狀態(tài)。賬戶的狀態(tài)包含權(quán)益值、計(jì)數(shù)器值等內(nèi)容。

候選鏈節(jié)點(diǎn)主要產(chǎn)生管理凈交易(Management Net Transaction,MNT)。管理凈交易用于委員會(huì)協(xié)議。管理凈交易的字段包括時(shí)間戳T、世代編號r、穩(wěn)定狀態(tài)根R和前述內(nèi)容的簽名σ。靜默鏈節(jié)點(diǎn)不產(chǎn)生任何交易,可以偵聽和驗(yàn)證交易或同步它們的交易數(shù)據(jù)庫。鏈節(jié)點(diǎn)的交易數(shù)據(jù)庫存儲(chǔ)生成鏈交易、管理凈交易和常規(guī)凈交易這3類交易。另外還有交易池,存儲(chǔ)沒有被確認(rèn)的常規(guī)凈交易和暫時(shí)無法驗(yàn)證的生成鏈交易。

3 權(quán)益有向無環(huán)圖共識

權(quán)益有向無環(huán)圖共識主要包含委員會(huì)協(xié)議和常規(guī)凈交易確認(rèn)算法。其中委員會(huì)協(xié)議迭代地生成每個(gè)世代的活躍鏈節(jié)點(diǎn)。常規(guī)凈交易確認(rèn)算法則由該世代的活躍鏈節(jié)點(diǎn)對常規(guī)凈交易進(jìn)行有向無環(huán)圖輔助下的投票記賬。

3.1 委員會(huì)協(xié)議

委員會(huì)協(xié)議通過當(dāng)前世代的委員會(huì)選舉出下一世代的委員會(huì)。委員會(huì)成員即成為下一世代的活躍鏈節(jié)點(diǎn)。協(xié)議主要從自主注冊的節(jié)點(diǎn)中,以當(dāng)前世代開始時(shí)槽的穩(wěn)定狀態(tài)根所確定的這些節(jié)點(diǎn)的權(quán)益值為依據(jù),選擇權(quán)益值較大的節(jié)點(diǎn)作為委員會(huì)成員。第0世代的委員會(huì)成員由初始鏈交易定義,稱為{N0,…,Nl-1}。簡單起見,設(shè)3|l且這l個(gè)節(jié)點(diǎn)一直在線。初始鏈交易是每個(gè)節(jié)點(diǎn)都知曉的一個(gè)配置性交易。其他世代的委員會(huì)成員由委員會(huì)協(xié)議確定。為了成為委員會(huì)成員,鏈節(jié)點(diǎn)需要通過常規(guī)凈交易盡可能地增大自己的權(quán)益值,以增加成為委員會(huì)成員的概率。

委員會(huì)協(xié)議如協(xié)議1所示。

協(xié)議1委員會(huì)協(xié)議。

在第r世代,對于鏈節(jié)點(diǎn)pi:

① 初始化:權(quán)益降序表Si、哈希表HCi、有序確認(rèn)表Confirmedi置空;

② 在當(dāng)前世代的倒數(shù)第2個(gè)時(shí)槽結(jié)束前:

③ 若pi是候選鏈節(jié)點(diǎn),廣播MNTi=r‖Ri‖Ti‖σi;

④ 當(dāng)收到候選鏈節(jié)點(diǎn)pj發(fā)出的MNTj后,執(zhí)行fr(MNTj),若返回值非空,則解析返回值為(pkj,stakej);

⑤ 將(pkj,stakej)插入到表Si中;

⑥ 在最后一個(gè)時(shí)槽開始時(shí):

⑦ 對Si中的每對二元組計(jì)算哈希值hc,并初始化每個(gè)哈希值的投票數(shù)Vhc=1,(hc,Vhc)寫入哈希表HCi;

⑧ 若pi是活躍鏈節(jié)點(diǎn),則:

⑨ 設(shè)置管理消息Mi為HCi中所有的哈希值,生成并廣播交易CTMNTi=Ti‖ci‖Mi‖引用數(shù)據(jù)‖Ri‖σi,更新ci=ci+1;

⑩ 在最后一個(gè)時(shí)槽開始后的2Δ時(shí)延內(nèi):

協(xié)議1分為以下幾個(gè)階段:

(1) ②～③行:自主注冊。希望成為下一世代活躍鏈節(jié)點(diǎn)的候選節(jié)點(diǎn)在當(dāng)前世代發(fā)送管理凈交易。

(2) ④行:主動(dòng)退位。鏈節(jié)點(diǎn)接收管理凈交易。若該管理凈交易各個(gè)字段合規(guī)性檢查通過,則函數(shù)fr恢復(fù)發(fā)送該管理凈交易的節(jié)點(diǎn)公鑰pk,檢查管理凈交易的數(shù)字簽名,簽名驗(yàn)證通過則繼續(xù)檢查恢復(fù)的公鑰是不是當(dāng)前任意活躍鏈節(jié)點(diǎn)的公鑰,檢查通過則繼續(xù)從狀態(tài)數(shù)據(jù)庫中找到該世代開始時(shí)槽的穩(wěn)定狀態(tài)所確定的該節(jié)點(diǎn)的權(quán)益值stake,返回二元組(pk,stake);任意檢查不通過,則停止處理該交易,返回空值。其中函數(shù)fr恢復(fù)公鑰的實(shí)現(xiàn)方法較多,例如簽名σ中附帶公鑰或者采用橢圓曲線數(shù)字簽名算法(Elliptic Curve Digital Signature Algorithm,ECDSA)的公鑰恢復(fù)算法。

(3) ⑤行:權(quán)益優(yōu)先。權(quán)益降序表Si初始為空,在一次委員會(huì)執(zhí)行周期內(nèi),該表按照權(quán)益由大到小的順序插入二元組(pk,stake),當(dāng)權(quán)益值相同時(shí),公鑰較小的節(jié)點(diǎn)優(yōu)先排序。

委員會(huì)協(xié)議設(shè)計(jì)上具有自主注冊、權(quán)益優(yōu)先和主動(dòng)退位的特點(diǎn)。任何一個(gè)靜默鏈節(jié)點(diǎn)都可以在一個(gè)新世代開始時(shí)使它自己成為一個(gè)候選鏈節(jié)點(diǎn)。對于一個(gè)誠實(shí)的節(jié)點(diǎn),自主注冊是為了體現(xiàn)鏈節(jié)點(diǎn)想要成為一個(gè)活躍鏈節(jié)點(diǎn)的主動(dòng)性,這可以盡量避免選到睡眠中的節(jié)點(diǎn)。權(quán)益優(yōu)先是盡可能讓高權(quán)益節(jié)點(diǎn)來完成共識,以避免權(quán)益證明共識機(jī)制固有的長程攻擊等問題。主動(dòng)退位則是為了盡可能地增加共識節(jié)點(diǎn)的動(dòng)態(tài)性,以減輕權(quán)益證明中“富者越富”的問題。

委員會(huì)協(xié)議在每個(gè)世代結(jié)束時(shí)明確了下一世代的委員會(huì)成員。攻擊者根據(jù)委員會(huì)成員的公鑰可以確定委員會(huì)成員的交易,進(jìn)一步嘗試分析委員會(huì)成員的IP地址,進(jìn)而發(fā)動(dòng)拒絕服務(wù)攻擊。然而,與單一記賬節(jié)點(diǎn)相比,委員會(huì)成員中有l(wèi)個(gè)記賬節(jié)點(diǎn),這事實(shí)上增加了拒絕服務(wù)攻擊的代價(jià)。另外,即便采用可驗(yàn)證隨機(jī)函數(shù)等方式匿名選出一個(gè)隨機(jī)的委員會(huì),在有向無環(huán)圖模式下,當(dāng)這些成員提供共識服務(wù)時(shí),同樣給了攻擊者拒絕服務(wù)攻擊的機(jī)會(huì),并且增加了長程攻擊的風(fēng)險(xiǎn)。

為了更清晰地展示委員會(huì)協(xié)議,給出一個(gè)世代內(nèi)的委員會(huì)協(xié)議工作流程圖,如圖1所示。假設(shè)有m個(gè)鏈節(jié)點(diǎn),k個(gè)候選鏈節(jié)點(diǎn)和l個(gè)委員會(huì)節(jié)點(diǎn)。每個(gè)候選鏈節(jié)點(diǎn)將自己的公鑰和權(quán)益封裝在管理凈交易中,于該世代倒數(shù)第2個(gè)時(shí)槽結(jié)束前完成廣播;所有鏈節(jié)點(diǎn)接收到MNTi后,根據(jù)收到的MNTi更新本地權(quán)益降序表;在最后1個(gè)時(shí)槽開始時(shí),所有鏈節(jié)點(diǎn)在本地構(gòu)建哈希表,其中委員會(huì)節(jié)點(diǎn)將哈希表封裝在生成鏈交易中廣播出去;所有鏈節(jié)點(diǎn)收到CTMNTi后,在最后1個(gè)時(shí)槽開始后2Δ時(shí)延內(nèi)完成本地哈希表的更新,即更新每個(gè)候選鏈節(jié)點(diǎn)的投票數(shù);在最后1個(gè)時(shí)槽結(jié)束前Δ時(shí)延內(nèi),鏈節(jié)點(diǎn)檢查本地哈希表中的投票數(shù),根據(jù)協(xié)議來確定下一世代委員會(huì)。委員會(huì)協(xié)議只需要2次廣播:一次是候選鏈節(jié)點(diǎn)廣播的管理凈交易消息;另一次是當(dāng)前委員會(huì)成員廣播的CTMNT消息。與其他共識協(xié)議相比,通信代價(jià)較低。另外,委員會(huì)協(xié)議在一個(gè)世代內(nèi)只執(zhí)行一次,對整個(gè)共識機(jī)制的效率影響較小。

圖1 一個(gè)世代內(nèi)的委員會(huì)協(xié)議工作流程圖

3.2 常規(guī)凈交易確認(rèn)算法

當(dāng)前世代的委員會(huì)成員接收常規(guī)凈交易,生成并發(fā)送生成鏈交易,從而擴(kuò)展有向無環(huán)圖,確認(rèn)交易。其中常規(guī)凈交易由客戶端節(jié)點(diǎn)生成。常規(guī)凈交易中的計(jì)數(shù)器用于防止重放攻擊,每生成一個(gè)常規(guī)凈交易該計(jì)數(shù)器值都加1。

常規(guī)凈交易確認(rèn)算法由鏈節(jié)點(diǎn)執(zhí)行,如算法1所示。

算法1常規(guī)凈交易確認(rèn)算法。

在第r世代,對于鏈節(jié)點(diǎn)pi:

① NNTPooli為常規(guī)凈交易池,NNTDBi為常規(guī)凈交易數(shù)據(jù)庫,CTPooli為生成鏈交易池,CTDBi為生成鏈交易數(shù)據(jù)庫;

② 當(dāng)接收到常規(guī)凈交易時(shí):

③ 檢查常規(guī)凈交易的有效性,若有效則:

④ 計(jì)算h=Hash(NNT),增加常規(guī)凈交易和表(h,{})到NNTPooli;

⑤ 如果pi是當(dāng)前委員會(huì)成員:

⑥ 以概率Pe生成CTNNTi=Ti‖ci‖h‖引用數(shù)據(jù)‖Ri‖σi;

⑦ 更新ci=ci+1,CTNNTi存入CTDBi,廣播CTNNTi;

⑧ 當(dāng)收到節(jié)點(diǎn)pj廣播的CTNNTj時(shí):

⑨ 檢查CTNNTj的有效性,若有效則:

算法1包含以下幾個(gè)階段:

(1) ①～④行:接收常規(guī)凈交易。鏈節(jié)點(diǎn)驗(yàn)證常規(guī)凈交易中的數(shù)字簽名、生成時(shí)間和計(jì)數(shù)器值。驗(yàn)證常規(guī)凈交易的生成時(shí)間的有效性指節(jié)點(diǎn)接收時(shí)間和交易時(shí)間戳的差值絕對值不大于Δ;驗(yàn)證計(jì)數(shù)器值的有效性是指在收到交易后,要求交易中計(jì)數(shù)器值大于當(dāng)前節(jié)點(diǎn)狀態(tài)數(shù)據(jù)庫中的對應(yīng)計(jì)數(shù)器值。

如果驗(yàn)證通過,則交易有效,首先更新發(fā)送該常規(guī)凈交易的客戶端賬戶中計(jì)數(shù)器的值,然后計(jì)算這個(gè)常規(guī)凈交易的哈希值h,為該常規(guī)凈交易構(gòu)建一個(gè)空的哈希確認(rèn)表,將常規(guī)凈交易和確認(rèn)表存入常規(guī)凈交易池中。

(2) ⑤～⑦行:生成并發(fā)送生成鏈交易。對于委員會(huì)成員,接收常規(guī)凈交易后會(huì)以概率Pe生成CTNNT,封裝該常規(guī)凈交易的哈希值。其中,引用數(shù)據(jù)構(gòu)造如下:

首先需要確認(rèn)引用數(shù)量,一般該數(shù)量大于等于2,這里假設(shè)為2。然后從生成鏈交易數(shù)據(jù)庫的未被引用生成鏈交易中,按照均勻分布隨機(jī)選取兩個(gè)生成鏈交易,計(jì)算其哈希值并作為引用數(shù)據(jù)。如果所有生成鏈交易都已經(jīng)被引用,就選取生成鏈交易數(shù)據(jù)庫中新近存儲(chǔ)的任意兩個(gè)生成鏈交易,計(jì)算其哈希值并作為引用數(shù)據(jù)。

封裝完成后,將生成鏈交易存儲(chǔ)在生成鏈交易數(shù)據(jù)庫中,并廣播給其他鏈節(jié)點(diǎn)。

(1) 優(yōu)先按照常規(guī)凈交易的創(chuàng)建時(shí)間排序,創(chuàng)建時(shí)間更早的常規(guī)凈交易排在前面。

(2) 如果兩個(gè)常規(guī)凈交易有同樣的創(chuàng)建者,那么它們應(yīng)有不同的創(chuàng)建時(shí)間,且有更小的創(chuàng)建時(shí)間的常規(guī)凈交易應(yīng)有更小的計(jì)數(shù)器值。如果違反了該規(guī)則,觸發(fā)懲罰機(jī)制,即兩個(gè)常規(guī)凈交易都被丟棄,且該創(chuàng)建者的權(quán)益或令牌被共享給該世代中的活躍鏈節(jié)點(diǎn)。

(3) 如果兩個(gè)有相同創(chuàng)建時(shí)間的常規(guī)凈交易被不同的創(chuàng)建者創(chuàng)建,則應(yīng)計(jì)算兩個(gè)哈希值。哈希函數(shù)的輸入是當(dāng)前世代數(shù)、常規(guī)凈交易發(fā)送者的公鑰和當(dāng)前世代委員會(huì)成員的公鑰。計(jì)算后,哈希值小的常規(guī)凈交易排在前面。

排序的第1個(gè)規(guī)則鼓勵(lì)客戶端節(jié)點(diǎn)使用盡可能早的創(chuàng)建時(shí)間來創(chuàng)建交易。但是客戶端節(jié)點(diǎn)的交易是需要委員會(huì)成員確認(rèn)的,因此,委員會(huì)成員會(huì)約束客戶端節(jié)點(diǎn)創(chuàng)建交易的時(shí)間,使得客戶端節(jié)點(diǎn)創(chuàng)建交易的時(shí)間在一個(gè)合理的范圍內(nèi)。排序的第2個(gè)規(guī)則主要是針對客戶端節(jié)點(diǎn)的雙花攻擊進(jìn)行的約束,該規(guī)則意味著常規(guī)凈交易的接收方可以通過發(fā)送方計(jì)數(shù)器值的連續(xù)性來確認(rèn)發(fā)送方?jīng)]有雙花。排序的第3個(gè)規(guī)則是通過引入環(huán)境參數(shù)來打破排序僵局,屬于常用方法。

為了更清晰地展示常規(guī)凈交易確認(rèn)算法,給出該算法的主要工作流程,如圖2所示。

圖2 常規(guī)凈交易確認(rèn)算法工作流程圖

設(shè)某客戶端向鏈接點(diǎn)廣播了一個(gè)NNT。鏈節(jié)點(diǎn)收到NNT后,檢查NNT的有效性,有效則加入本地常規(guī)凈交易池中,并在常規(guī)凈交易池中構(gòu)建新的哈希確認(rèn)列表,其中,委員會(huì)節(jié)點(diǎn)將常規(guī)凈交易封裝在生成鏈交易中廣播出去;所有鏈節(jié)點(diǎn)收到CTNNTi后,檢查其有效性,有效則將其加入本地生成鏈交易數(shù)據(jù)庫中,并更新常規(guī)凈交易池中的哈希確認(rèn)列表,包括NNT的哈希確認(rèn)數(shù)的更新、以CTNNTi為根節(jié)點(diǎn)的子樹中的樹節(jié)點(diǎn)包含的NNT的哈希確認(rèn)數(shù)的更新等。

4 安全性分析

4.1 安全模型

權(quán)益有向無環(huán)圖共識機(jī)制包含鏈節(jié)點(diǎn)和客戶端節(jié)點(diǎn)。鏈節(jié)點(diǎn)又分為活躍鏈節(jié)點(diǎn)、候選鏈節(jié)點(diǎn)和靜默鏈節(jié)點(diǎn)。鏈節(jié)點(diǎn)和客戶端節(jié)點(diǎn)都在一個(gè)點(diǎn)到點(diǎn)網(wǎng)絡(luò)中,誠實(shí)的鏈節(jié)點(diǎn)會(huì)轉(zhuǎn)發(fā)其他鏈節(jié)點(diǎn)或者客戶端節(jié)點(diǎn)的消息?？蛻舳斯?jié)點(diǎn)發(fā)送的消息為常規(guī)凈交易,鏈節(jié)點(diǎn)發(fā)送的消息為生成鏈交易。鏈節(jié)點(diǎn)將確認(rèn)的常規(guī)凈交易存入常規(guī)凈交易數(shù)據(jù)庫。

攻擊者既可以是鏈節(jié)點(diǎn)又可以是客戶端節(jié)點(diǎn),這些節(jié)點(diǎn)稱為拜占庭節(jié)點(diǎn)。拜占庭節(jié)點(diǎn)可以有任意行為,例如發(fā)起合謀攻擊、延遲轉(zhuǎn)發(fā)消息、不轉(zhuǎn)發(fā)消息或者單播某個(gè)消息。拜占庭節(jié)點(diǎn)的這些行為囊括了網(wǎng)絡(luò)故障或者誠實(shí)節(jié)點(diǎn)故障等意外情況。因此,如果誠實(shí)節(jié)點(diǎn)發(fā)送交易,根據(jù)有界延遲網(wǎng)絡(luò)假設(shè),其他誠實(shí)節(jié)點(diǎn)會(huì)在交易最大容忍時(shí)延Δ內(nèi)接收到交易。

假設(shè)在每個(gè)世代中,候選鏈節(jié)點(diǎn)中拜占庭節(jié)點(diǎn)的占比小于1/3,且按照權(quán)益排序時(shí),分布均勻。假設(shè)第0世代的委員會(huì)成員一直在線,是誠實(shí)節(jié)點(diǎn),則可以在必要時(shí)加入委員會(huì)。

考慮共識機(jī)制的如下安全屬性:

(1)一致性

如果某個(gè)誠實(shí)鏈節(jié)點(diǎn)將某個(gè)常規(guī)凈交易存入了常規(guī)凈交易數(shù)據(jù)庫,那么其他誠實(shí)鏈節(jié)點(diǎn)也會(huì)將該常規(guī)凈交易存入其常規(guī)凈交易數(shù)據(jù)庫。

(2)可結(jié)束性

如果某個(gè)誠實(shí)的鏈節(jié)點(diǎn)收到了某個(gè)常規(guī)凈交易,則該鏈節(jié)點(diǎn)要么停止處理該常規(guī)凈交易,要么將其存入常規(guī)凈交易數(shù)據(jù)庫。

4.2 安全性證明

為了證明常規(guī)凈交易確認(rèn)算法的一致性和可結(jié)束性,首先需要明確委員會(huì)協(xié)議的安全屬性。由于委員會(huì)協(xié)議僅僅有2次廣播,并不能確保每個(gè)鏈節(jié)點(diǎn)都有一致的委員會(huì)視圖。然而,委員會(huì)協(xié)議可以確保每個(gè)鏈節(jié)點(diǎn)關(guān)于誠實(shí)節(jié)點(diǎn)有一致的視圖,并且委員會(huì)協(xié)議是可以連續(xù)更迭的。

定理1委員會(huì)協(xié)議可以在兩個(gè)時(shí)槽內(nèi)結(jié)束,每一世代可以確認(rèn)下一世代的委員會(huì)成員,且委員會(huì)成員中不少于2l/3個(gè)成員是誠實(shí)且一致的。

證明 采用數(shù)學(xué)歸納法證明。

(1)第0世代的委員會(huì)成員為初始鏈交易定義的l個(gè)鏈節(jié)點(diǎn)。根據(jù)假設(shè),這些鏈節(jié)點(diǎn)是誠實(shí)節(jié)點(diǎn)。

(2)第r世代確定第r+1世代的委員會(huì)時(shí)(r≥0),第r世代委員會(huì)成員中有不少于2l/3個(gè)成員是誠實(shí)的。假設(shè)候選節(jié)點(diǎn)中有x′個(gè)惡意節(jié)點(diǎn),x個(gè)誠實(shí)節(jié)點(diǎn),則根據(jù)拜占庭節(jié)點(diǎn)占比假設(shè)有x′≤(x′+x)/3。根據(jù)協(xié)議1的第②～③行,x個(gè)誠實(shí)的候選節(jié)點(diǎn)廣播管理凈交易。根據(jù)有界延遲網(wǎng)絡(luò)假設(shè),當(dāng)前委員會(huì)成員中不少于2l/3個(gè)成員在倒數(shù)第2個(gè)時(shí)槽的第1個(gè)Δ時(shí)延內(nèi)會(huì)收到x個(gè)誠實(shí)節(jié)點(diǎn)發(fā)出的所有管理凈交易。

收到管理凈交易的誠實(shí)委員會(huì)成員根據(jù)協(xié)議1的第④～⑤行對收到的管理凈交易進(jìn)行處理,根據(jù)協(xié)議1的第⑥～⑨行,在最后一個(gè)時(shí)槽開始時(shí)產(chǎn)生并廣播CTMNT。根據(jù)有界延遲網(wǎng)絡(luò)假設(shè),誠實(shí)鏈節(jié)點(diǎn)在最后一個(gè)時(shí)槽開始后不超過2Δ的時(shí)間內(nèi)可以收到不少于2l/3個(gè)委員會(huì)成員發(fā)出的所有CTMNT。

在委員會(huì)成員中有不少于2l/3個(gè)成員是一致的這個(gè)前提下,可以證明常規(guī)凈交易確認(rèn)算法可以確保單個(gè)常規(guī)凈交易在誠實(shí)鏈節(jié)點(diǎn)中經(jīng)過一段時(shí)間后總是可以得到確認(rèn)的。

證明 首先分析在有向無環(huán)圖中,引用數(shù)至少為2時(shí),單個(gè)生成鏈交易被引用的情況。

設(shè)客戶端節(jié)點(diǎn)每Δ時(shí)間產(chǎn)生λ個(gè)常規(guī)凈交易。根據(jù)算法1的第⑥行,委員會(huì)節(jié)點(diǎn)會(huì)以概率Pe生成包含常規(guī)凈交易哈希值的生成鏈交易,則單個(gè)委員會(huì)成員每Δ時(shí)間產(chǎn)生約Peλ個(gè)生成鏈交易。設(shè)全體誠實(shí)委員會(huì)成員每Δ時(shí)間產(chǎn)生λ1個(gè)生成鏈交易,由定理1可知誠實(shí)委員會(huì)成員數(shù)量不少于2l/3個(gè),所以λ1≥2lPeλ/3。

設(shè)每Δ時(shí)間,單個(gè)委員會(huì)成員向其生成鏈交易數(shù)據(jù)庫存入λ2個(gè)生成鏈交易,顯然有λ2≤λ1。

根據(jù)算法1第⑥行的描述,每產(chǎn)生一個(gè)生成鏈交易,其引用數(shù)至少為2,則Δ時(shí)間內(nèi)產(chǎn)生Peλ個(gè)生成鏈交易需引用至少2Peλ個(gè)生成鏈交易。

因?yàn)樯涉溄灰滓靡?guī)則是按照均勻分布隨機(jī)選取的,所以每Δ時(shí)間存入生成鏈交易數(shù)據(jù)庫的單個(gè)生成鏈交易被直接引用的概率至少是2Peλ/λ2。為了讓單個(gè)生成鏈交易的直接引用概率趨于1,需要有x≈λ2/(2Peλ)個(gè)委員會(huì)成員。因λ1≥2lPeλ/3,且λ2≤λ1,故可得x≤l/3。

因?yàn)槲瘑T會(huì)成員中不少于2l/3個(gè)成員是誠實(shí)的,所以單個(gè)生成鏈交易在Δ時(shí)間內(nèi)直接被引用次數(shù)至少是2次。單個(gè)生成鏈交易經(jīng)過y個(gè)Δ時(shí)間后,被直接和間接引用的次數(shù)至少是2+…+2y=2y+1-2。

下面考慮單個(gè)世代內(nèi),某個(gè)常規(guī)凈交易從被接收到被確認(rèn)的時(shí)延。當(dāng)該常規(guī)凈交易被一個(gè)誠實(shí)鏈節(jié)點(diǎn)確認(rèn)時(shí),根據(jù)算法1的行,該常規(guī)凈交易一定在該誠實(shí)節(jié)點(diǎn)的常規(guī)凈交易池中,即該誠實(shí)節(jié)點(diǎn)接收了該常規(guī)凈交易。根據(jù)有界延遲網(wǎng)絡(luò)假設(shè),其他誠實(shí)節(jié)點(diǎn)在Δ時(shí)間內(nèi)也接收了該常規(guī)凈交易。根據(jù)算法1的第⑥行,有2lPe/3個(gè)誠實(shí)節(jié)點(diǎn)生成了包含該常規(guī)凈交易的不同生成鏈交易。因此,對于某個(gè)常規(guī)凈交易,在接收后至多經(jīng)過1個(gè)Δ時(shí)間會(huì)在有向無環(huán)圖中出現(xiàn)包含該常規(guī)凈交易的生成鏈交易。經(jīng)過y個(gè)Δ時(shí)間,該常規(guī)凈交易被直接和間接確認(rèn)的次數(shù)至少為2lPe(2y+1-1)/3,其中包含生成鏈交易對該常規(guī)凈交易的一次引用。

依次類推,可知在原世代結(jié)束前yΔ時(shí)延內(nèi)的常規(guī)凈交易,在新世代根據(jù)常規(guī)凈交易確認(rèn)算法能夠以概率1被確認(rèn),最大延遲不變。

最后,分析當(dāng)一個(gè)誠實(shí)鏈節(jié)點(diǎn)確認(rèn)某個(gè)常規(guī)凈交易后,其他誠實(shí)鏈節(jié)點(diǎn)的行為。

推論常規(guī)凈交易確認(rèn)算法具有一致性和可結(jié)束性。

5 區(qū)塊鏈系統(tǒng)及性能

圖3所示為基于權(quán)益有向無環(huán)圖共識機(jī)制,實(shí)現(xiàn)了一個(gè)區(qū)塊鏈系統(tǒng)。為了測試筆者提出的共識機(jī)制性能,在4臺(tái)主機(jī)配置了20臺(tái)虛擬機(jī),每臺(tái)虛擬機(jī)配置6 GB內(nèi)存,4個(gè)處理器,均運(yùn)行Ubuntu 18.04系統(tǒng)。主機(jī)之間的網(wǎng)絡(luò)為百兆局域網(wǎng),網(wǎng)絡(luò)通信采用了HoneyBadger BFT協(xié)議開源代碼中Python版本的異步通信模塊。為了確保數(shù)據(jù)的準(zhǔn)確性,給出的數(shù)據(jù)為多次測量的平均值。根據(jù)測試目標(biāo)的不同,測試次數(shù)有所不同,每個(gè)測試目標(biāo)的測試次數(shù)在10～20次之間。

圖3 區(qū)塊鏈系統(tǒng)

客戶端節(jié)點(diǎn)功能單一,僅發(fā)送常規(guī)凈交易。用Python自帶的len()函數(shù),計(jì)算得到每個(gè)常規(guī)凈交易的長度約360字節(jié),其中包括時(shí)間戳32字節(jié)、計(jì)數(shù)器28字節(jié)、ECDSA簽名97字節(jié)和參數(shù)消息59字節(jié)。根據(jù)測試,單個(gè)TCP連接下,客戶端節(jié)點(diǎn)每秒鐘可以發(fā)送約400個(gè)常規(guī)凈交易。

鏈節(jié)點(diǎn)部署了委員會(huì)協(xié)議和常規(guī)凈交易確認(rèn)算法,完成委員會(huì)更迭和常規(guī)凈交易的確認(rèn)。設(shè)置委員會(huì)成員數(shù)量l∈{4,8,12,16},其他參數(shù)包括Pe=0.5,Δ=0.5 s,一個(gè)時(shí)槽為3 s,一個(gè)世代為1 min,算法1的第行中的時(shí)間閾值為0.8 s。此時(shí)可計(jì)算得到生成鏈交易的長度約670字節(jié),包括時(shí)間戳32字節(jié)、計(jì)數(shù)器28字節(jié)、常規(guī)凈交易哈希值113字節(jié)、引用數(shù)量28個(gè)字節(jié)、引用2個(gè)生成鏈交易哈希值226字節(jié)、穩(wěn)定狀態(tài)根113字節(jié)、ECDSA簽名97字節(jié)。

從表1可以看到,在委員會(huì)協(xié)議中,候選鏈節(jié)點(diǎn)運(yùn)行1.429 ms,活躍鏈節(jié)點(diǎn)運(yùn)行2.006 ms,其他鏈節(jié)點(diǎn)運(yùn)行0.024 ms。各部分運(yùn)行時(shí)間在預(yù)期的Δ延時(shí)內(nèi),符合節(jié)4.1安全模型中的最大容忍時(shí)延的假設(shè),且整個(gè)委員會(huì)協(xié)議的運(yùn)行時(shí)間在2個(gè)時(shí)槽內(nèi)完成,符合定理1。

表1 委員會(huì)協(xié)議運(yùn)行時(shí)間

表2 常規(guī)凈交易確認(rèn)算法運(yùn)行時(shí)間

在委員會(huì)成員數(shù)量分別為4、8、12、16,拜占庭節(jié)點(diǎn)數(shù)分別為1至4時(shí),測試了文中的共識機(jī)制確認(rèn)單個(gè)客戶端交易的時(shí)延和系統(tǒng)的吞吐量。類似HoneyBadger BFT協(xié)議,交易時(shí)延是常規(guī)凈交易自發(fā)出到該交易進(jìn)入常規(guī)凈交易數(shù)據(jù)庫的用時(shí),系統(tǒng)吞吐量為常規(guī)凈交易數(shù)據(jù)庫中每秒增加的交易數(shù)。

作為對比實(shí)驗(yàn),在相同局域網(wǎng)、相同節(jié)點(diǎn)下運(yùn)行HoneyBadger BFT協(xié)議,測試HoneyBadger BFT協(xié)議處理與單個(gè)常規(guī)凈交易相同大小的交易的時(shí)延。由于HoneyBadger BFT協(xié)議在處理交易時(shí),并沒有對交易簽名,為公平起見,在HoneyBadger BFT協(xié)議中加入了交易簽名和驗(yàn)證簽名的過程,同樣采用ECDSA簽名。

如表3所示,在處理單個(gè)常規(guī)凈交易時(shí),隨著局域網(wǎng)內(nèi)節(jié)點(diǎn)數(shù)量增加,節(jié)點(diǎn)的平均交易處理時(shí)延逐漸增加,但依然保持毫秒級時(shí)延,明顯低于HoneyBadger BFT協(xié)議的單個(gè)交易處理時(shí)延。

表3 不同情況下的單個(gè)交易處理時(shí)延 ms

注意到定理2給出的是常規(guī)凈交易被確認(rèn)的最大時(shí)延,可見該實(shí)驗(yàn)結(jié)果符合定理2。在實(shí)驗(yàn)過程中,采用Wireshark軟件監(jiān)測網(wǎng)絡(luò),測得局域網(wǎng)內(nèi)的交易傳播時(shí)延在0.04 ms左右,遠(yuǎn)低于Δ=0.5 s,符合安全模型中最大容忍時(shí)延的假設(shè)。

在測試系統(tǒng)吞吐量時(shí),采用了類似HoneyBadger BFT協(xié)議的批量處理方法。增加了常規(guī)凈交易載荷的規(guī)模來進(jìn)行批量處理。交易批量為常規(guī)凈交易載荷的規(guī)模除以每個(gè)客戶端交易的大小。測試結(jié)果如圖4所示:首先隨著交易批量增大,系統(tǒng)吞吐量不斷增大;然后當(dāng)局域網(wǎng)內(nèi)通信量趨于飽和時(shí),系統(tǒng)吞吐量有所下降;最后隨著部署節(jié)點(diǎn)的增多,局域網(wǎng)內(nèi)通信量增加,系統(tǒng)的吞吐量下降。當(dāng)部署16個(gè)活躍鏈節(jié)點(diǎn),交易批量為106時(shí),本系統(tǒng)的交易吞吐量約17 000 tx/s;在相同配置下,HoneyBadger BFT協(xié)議的交易吞吐量為2 600 tx/s。

圖4 不同節(jié)點(diǎn)部署情況下的交易吞吐量

分析HoneyBadger BFT協(xié)議的共識過程,可知其完成一次共識在RBC階段就需3次廣播,在BA階段也至少需要3次廣播,而筆者提出的共識機(jī)制中的共識過程僅需兩輪廣播。因此,本系統(tǒng)在共識過程中,交易通信量會(huì)明顯小于HoneyBadger BFT協(xié)議,使得本系統(tǒng)的單個(gè)交易處理時(shí)延遠(yuǎn)小于HoneyBadger BFT協(xié)議時(shí)延,吞吐量也會(huì)高于HoneyBadger BFT協(xié)議的交易吞吐量。

6 結(jié)束語

以上完整地呈現(xiàn)了一個(gè)可證明安全的權(quán)益有向無環(huán)圖共識機(jī)制,詳細(xì)給出了委員會(huì)協(xié)議和常規(guī)凈交易確認(rèn)算法,證明了協(xié)議和算法的安全性,并基于該共識機(jī)制實(shí)現(xiàn)了一個(gè)區(qū)塊鏈系統(tǒng),給出了基本的性能測試數(shù)據(jù)。測試結(jié)果符合預(yù)期。