基于博弈論抗共謀攻擊的全局隨機(jī)化共識(shí)算法

張寶，田有亮，高勝

基于博弈論抗共謀攻擊的全局隨機(jī)化共識(shí)算法

張寶1,2，田有亮1,2，高勝3

（1. 貴州大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院，貴州 貴陽 550025；2. 貴州省公共大數(shù)據(jù)重點(diǎn)實(shí)驗(yàn)室，貴州 貴陽 550025；3. 中央財(cái)經(jīng)大學(xué)信息學(xué)院，北京 100081）

隨著區(qū)塊鏈技術(shù)的不斷發(fā)展，作為區(qū)塊鏈技術(shù)基石的共識(shí)技術(shù)受到更多關(guān)注，共識(shí)技術(shù)的發(fā)展越發(fā)迅速，但依舊存在相關(guān)難題。容錯(cuò)類共識(shí)算法作為區(qū)塊鏈共識(shí)技術(shù)的代表性之一，依然存在諸多難題待研究，針對(duì)容錯(cuò)類共識(shí)算法中節(jié)點(diǎn)隨機(jī)性和節(jié)點(diǎn)共謀攻擊問題進(jìn)行了研究，提出基于博弈論抗共謀攻擊的全局隨機(jī)化共識(shí)算法，通過實(shí)現(xiàn)節(jié)點(diǎn)的隨機(jī)化和解決相關(guān)安全問題提高區(qū)塊鏈網(wǎng)絡(luò)的安全性和吞吐量。在選擇參與容錯(cuò)類共識(shí)算法的節(jié)點(diǎn)過程中，利用映射函數(shù)和加權(quán)隨機(jī)函數(shù)實(shí)現(xiàn)發(fā)起者和驗(yàn)證者節(jié)點(diǎn)的全局隨機(jī)化，從而保證發(fā)起者和驗(yàn)證者節(jié)點(diǎn)的身份匿名，提高區(qū)塊鏈網(wǎng)絡(luò)的安全性。利用信譽(yù)更新模型實(shí)現(xiàn)信譽(yù)動(dòng)態(tài)更新的同時(shí)利用博弈論分析容錯(cuò)類共識(shí)算法的安全問題，構(gòu)造更加正確和高效的算法模型以提高算法的吞吐量并分析發(fā)現(xiàn)這類算法中存在超過1/3節(jié)點(diǎn)的共謀攻擊問題，利用精煉貝葉斯博弈構(gòu)造共謀合約，分析求得共謀者之間的納什均衡點(diǎn)，從而解決超過1/3節(jié)點(diǎn)的共謀攻擊問題。通過安全性分析和實(shí)驗(yàn)表明，基于博弈論抗共謀攻擊的全局隨機(jī)化共識(shí)算法相對(duì)工作量證明（PoW，proof of work）、權(quán)益證明（PoS，proof of stake）和實(shí)用拜占庭容錯(cuò)（PBFT，practical Byzantine fault tolerance）共識(shí)算法不僅提高吞吐量、降低計(jì)算資源消耗，而且該算法抵抗分布式拒絕服務(wù)（DDoS，distributed denial of service）、Eclipse attacks和超過1/3節(jié)點(diǎn)共謀攻擊。

共識(shí)算法；全局隨機(jī)化；博弈論；共謀攻擊

0 引言

隨著區(qū)塊鏈技術(shù)的發(fā)展，對(duì)數(shù)據(jù)上鏈速度的要求越來越高，用高效且安全的共識(shí)協(xié)議來保證數(shù)據(jù)上鏈成為區(qū)塊鏈系統(tǒng)的關(guān)鍵問題。在該背景下，如何解決基于工作量證明（PoW，proof of work）[1]和基于權(quán)益證明（PoS，proof of stake）的共識(shí)協(xié)議[2]中高資源浪費(fèi)、低效率上鏈[3]、權(quán)益過大、富者越富、易分叉、易雙花[4]等問題是重點(diǎn)。近年來，代理權(quán)益證明（DPoS，delegated proof of stake）[5]被認(rèn)為是解決資源浪費(fèi)、權(quán)益過大和低效率等問題的有效技術(shù)。該技術(shù)是一種基于投票選舉的共識(shí)算法，只需要少部分的節(jié)點(diǎn)就能達(dá)成共識(shí)實(shí)現(xiàn)交易數(shù)據(jù)快速上鏈?；诎菡纪ト蒎e(cuò)協(xié)議的Tendermint[6]和True Decentralization[7]協(xié)議的出現(xiàn)不僅保證了1/3節(jié)點(diǎn)的容錯(cuò)，而且只需要少部分節(jié)點(diǎn)對(duì)交易進(jìn)行驗(yàn)證就可以達(dá)成最后的共識(shí)。

文獻(xiàn)[8]提出了一種將PoW和PoS相結(jié)合的共識(shí)協(xié)議，該協(xié)議提供了更高的安全性和效率。文獻(xiàn)[9]研究了交互式的PoS共識(shí)算法，將通信引入塊，減少交互，提高效率和安全性，但該協(xié)議依然沒有解決PoS存在的權(quán)益過大、易分叉和易雙花問題。文獻(xiàn)[10]利用Kgmedoids聚類算法根據(jù)參與區(qū)塊鏈共識(shí)的大規(guī)模網(wǎng)絡(luò)節(jié)點(diǎn)的特征進(jìn)行聚類與層次劃分，再將改進(jìn)的多中心化實(shí)用拜占庭容錯(cuò)算法應(yīng)用于這種聚類后的分層模型。文獻(xiàn)[11]研究了新的共識(shí)算法固定驗(yàn)證器，但它依賴于極端信任的假設(shè)。文獻(xiàn)[12]提出了一個(gè)無發(fā)起者、完全異步的拜占庭容錯(cuò)共識(shí)協(xié)議。文獻(xiàn)[13]提出了一個(gè)委托隨機(jī)拜占庭容錯(cuò)共識(shí)協(xié)議。文獻(xiàn)[14]利用博弈論和智能合約解決了委托計(jì)算中不誠實(shí)雙方的共謀問題。文獻(xiàn)[15]提出了休眠共識(shí)（SC，sleepy consensus）機(jī)制，該機(jī)制只要在線誠實(shí)節(jié)點(diǎn)超過故障節(jié)點(diǎn)就可以保證安全性。文獻(xiàn)[16]基于發(fā)起者的拜占庭容錯(cuò)復(fù)制協(xié)議提出了HB-BFT（honey badger of BFT）。文獻(xiàn)[17]基于拜占庭提出了一種新的共識(shí)機(jī)制Proteus，無論網(wǎng)絡(luò)中出現(xiàn)多少次故障，Proteus都能保證穩(wěn)定的性能。

基于拜占庭容錯(cuò)的這類共識(shí)算法中，當(dāng)提議者提出新塊后，發(fā)起者接收到提議者指令后開始選擇驗(yàn)證者，當(dāng)驗(yàn)證者確定后由驗(yàn)證者投票達(dá)成最終的共識(shí)。共識(shí)的過程中實(shí)現(xiàn)參與節(jié)點(diǎn)的隨機(jī)化是保證共識(shí)算法安全性的關(guān)鍵難題。而本文提出的基于博弈論抗共謀攻擊的全局隨機(jī)化共識(shí)算法（GRCACAGT，global randomized consensus algorithm resist collusion attack based on game theory）可以解決節(jié)點(diǎn)的全局隨機(jī)化問題以及這類算法中存在的共謀攻擊，主要貢獻(xiàn)如下。

1) 提出GRCACAGT，利用映射函數(shù)和加權(quán)隨機(jī)函數(shù)實(shí)現(xiàn)共識(shí)算法中發(fā)起者節(jié)點(diǎn)的隨機(jī)化。

2) 分析容錯(cuò)類共識(shí)算法發(fā)現(xiàn)1/3節(jié)點(diǎn)共謀攻擊問題，并利用智能合約和貝葉斯博弈構(gòu)造共謀合約解決了該問題。

3) 安全性分析和實(shí)驗(yàn)表明，GRCACAGT不僅抗分布式拒絕服務(wù)（DDoS，distributed denial of service）、1/3節(jié)點(diǎn)共謀等攻擊，而且相比其他的共識(shí)算法，吞吐量和效率方面都有優(yōu)勢(shì)。

1 本文算法

本文基于True Decentralization[7]提出GRCACAGT，GRCACAGT與True Decentralization邏輯很像但構(gòu)造不同。第一，確定所需要的驗(yàn)證者人數(shù)方法不同。GRCACAGT是根據(jù)提議者的動(dòng)態(tài)信譽(yù)值確定驗(yàn)證者人數(shù)，而True Decentralization是根據(jù)提議者的不誠實(shí)概率來確定驗(yàn)證者人數(shù)。第二，確定發(fā)起者的方法不同。True Decentralization在起始?jí)K創(chuàng)建時(shí)就確定了發(fā)起者。而GRCACAGT每輪共識(shí)都需要選擇新的發(fā)起者，因?yàn)門rue Decentralization中選擇發(fā)起者的方法存在發(fā)起者節(jié)點(diǎn)身份暴露的安全問題。分析發(fā)現(xiàn)，當(dāng)所有驗(yàn)證節(jié)點(diǎn)身份全部暴露時(shí)，節(jié)點(diǎn)池中剩下的節(jié)點(diǎn)就是發(fā)起者節(jié)點(diǎn)，此時(shí)發(fā)起者的身份也會(huì)暴露。第三，發(fā)起者選擇驗(yàn)證者的方法不同。True Decentralization是將節(jié)點(diǎn)池平均分為4個(gè)小的節(jié)點(diǎn)池，每個(gè)發(fā)起者對(duì)應(yīng)一個(gè)小節(jié)點(diǎn)池，從對(duì)應(yīng)的節(jié)點(diǎn)池中選擇驗(yàn)證者。這樣風(fēng)險(xiǎn)較大，因?yàn)樵赥rue Decentralization中雖然每次參與驗(yàn)證節(jié)點(diǎn)的身份在節(jié)點(diǎn)完成驗(yàn)證之后才會(huì)暴露，但經(jīng)過多輪驗(yàn)證后，每個(gè)節(jié)點(diǎn)池中節(jié)點(diǎn)的身份都會(huì)暴露，此時(shí)通過節(jié)點(diǎn)出現(xiàn)的次數(shù)能確定哪些節(jié)點(diǎn)被選擇的概率最大，所以少數(shù)的節(jié)點(diǎn)就能實(shí)現(xiàn)攻擊。而GRCACAGT利用抽樣不放回和加權(quán)隨機(jī)的方法，相對(duì)True Decentralization不僅能增加4倍的安全性而且節(jié)點(diǎn)不會(huì)被重復(fù)選擇。

在GRCACAGT中，每輪共識(shí)開始后首先隨機(jī)選出發(fā)起者，并根據(jù)提議者的信譽(yù)大小確定驗(yàn)證者人數(shù)；然后根據(jù)更新后的信譽(yù)值加權(quán)隨機(jī)選擇驗(yàn)證者，該過程是利用抽樣不放回的方法實(shí)現(xiàn)的，這樣能夠保證節(jié)點(diǎn)不被重復(fù)選擇；最后利用博弈論分析GRCACAGT發(fā)現(xiàn)在驗(yàn)證上鏈階段存在節(jié)點(diǎn)之間的共謀安全問題。本文將這種共謀定義為1/3節(jié)點(diǎn)共謀攻擊，并提出共謀合約解決了該安全問題。圖1為GRCACAGT模型。

1) 提議者：創(chuàng)建新區(qū)塊并向全網(wǎng)廣播這個(gè)塊。

2) 發(fā)起者：新區(qū)塊廣播后確定所需要的驗(yàn)證者。

3) 驗(yàn)證者：對(duì)新提出的區(qū)塊進(jìn)行投票達(dá)成共識(shí)。

4) 其余節(jié)點(diǎn)：礦池中沒有參與共識(shí)的節(jié)點(diǎn)。

1.1 發(fā)起者的選擇

該階段博弈在提議者（Alice）和發(fā)起者（Bob）間進(jìn)行，通過博弈結(jié)果確定發(fā)起者人數(shù)。發(fā)起者有兩個(gè)策略，即最小驗(yàn)證者（MV）和更多的驗(yàn)證者（AMV），AMV的大小是根據(jù)博弈結(jié)果確定的。Alice和Bob存在兩種狀況（誠實(shí)或不誠實(shí)），Alice不同的狀況下有兩種類型（作弊或不作弊）。

把4個(gè)發(fā)起者之間博弈看作一對(duì)一的獨(dú)立博弈。由于Bob不知道Alice的類型，且提議者行動(dòng)在先，發(fā)起者行動(dòng)在后，兩者的行動(dòng)具有非同時(shí)性，所以該博弈是精煉貝葉斯納什均衡（PBNE），發(fā)起者和提議者的博弈樹如圖2所示。

圖1 GRCACAGT模型

Figure 1 GRCACAGT model

圖2 發(fā)起者和提議者的博弈樹

Figure 2 Game tree of initiators and proposers

表1為系統(tǒng)中提議者和發(fā)起者間博弈的參數(shù)說明。圖3表示提議者（Alice）為不誠實(shí)節(jié)點(diǎn)的收益矩陣，第一個(gè)收益是Alice，第二個(gè)是Bob。圖4表示提議者（Alice）為誠實(shí)節(jié)點(diǎn)的收益矩陣。

純策略：假設(shè)玩家Alice知道玩家Bob的信譽(yù)值為，那么Alice確定他的策略之后，對(duì)于玩家Bob選擇AMV的預(yù)期收益為

同理，玩家Bob選擇MV的預(yù)期收益為

表1 參數(shù)說明

Figure 3 The utility matrix when the proposer (Alice) is the dishonest nodes

圖4 提議者(Alice)為誠實(shí)節(jié)點(diǎn)的收益矩陣

Figure 4 The utility matrix when the proposer (Alice) is the honesty nodes

通過化簡(jiǎn)之后得到

這時(shí)對(duì)于玩家Bob來說，最好的選擇是AMV。如果玩家Bob選擇了AMV，那么作弊對(duì)于玩家為不誠實(shí)節(jié)點(diǎn)就不再是最好的決策，這時(shí)他會(huì)選擇不作弊，所以((不誠實(shí)節(jié)點(diǎn)且作弊, 誠實(shí)節(jié)點(diǎn)不作弊)，選擇AMV,)不是一個(gè)貝葉斯納什均衡點(diǎn)。

這時(shí)玩家Bob最好的選擇是MV，((不誠實(shí)節(jié)點(diǎn)且作弊, 誠實(shí)節(jié)點(diǎn)不作弊)，選擇MV,)是一個(gè)純策略的精煉貝葉斯納什均衡。

混合策略：在式(4)成立時(shí)，不存在納什均衡，所以存在PBNE的混合策略，假設(shè)玩家(Alice)作弊的概率為，玩家Bob選擇AMV的概率為，則玩家Bob選擇AMV的預(yù)期收益為

玩家Bob選擇MV的預(yù)期收益為

同理，當(dāng)Alice不誠實(shí)時(shí)，可預(yù)期收益函數(shù)為

玩家不作弊的收益為

PBNE的混合策略為

這里，*是一個(gè)發(fā)起者選擇AMV的概率。

PBNE混合戰(zhàn)略的策略為

1.2 驗(yàn)證者的選擇

1.3 節(jié)點(diǎn)的信譽(yù)更新

利用層次自組網(wǎng)中基于節(jié)點(diǎn)角色的新信譽(yù)模型實(shí)現(xiàn)動(dòng)態(tài)更新[18]，可以通過將節(jié)點(diǎn)自身的經(jīng)驗(yàn)與其行為和其在路由過程中的合作有效性相結(jié)合來評(píng)估信譽(yù)，通過信譽(yù)值確定節(jié)點(diǎn)的安全情況來選擇具有較高價(jià)值的節(jié)點(diǎn), 以確保通信可靠。因?yàn)椴煌?jié)點(diǎn)之間可能存在一定的關(guān)系，可以根據(jù)節(jié)點(diǎn)的作用將信譽(yù)分為提議者發(fā)起者之間的信譽(yù)（PLR）、發(fā)起者驗(yàn)證者之間的信譽(yù)（LVR）、提議者驗(yàn)證者之間的信譽(yù)（PVR），根據(jù)各個(gè)信譽(yù)之間的關(guān)系制定的信譽(yù)更新模型如圖5所示。

圖5 信譽(yù)更新模型

Figure 5 Credibility updating model

在一輪的驗(yàn)證過程中，節(jié)點(diǎn)池中節(jié)點(diǎn)分為提議者、發(fā)起者、驗(yàn)證者和其他，每一個(gè)節(jié)點(diǎn)都有自己的任務(wù)，任務(wù)結(jié)束后每個(gè)節(jié)點(diǎn)的信譽(yù)會(huì)有所變動(dòng)，通過影響信譽(yù)值元素的大小變化而更新對(duì)應(yīng)節(jié)點(diǎn)的信譽(yù)值。隨著PLR、LVR和PVR大小的變化實(shí)現(xiàn)節(jié)點(diǎn)信譽(yù)的更新。提議者提出假的交易塊信譽(yù)就會(huì)被降低，區(qū)塊通過驗(yàn)證則信譽(yù)增大。對(duì)于發(fā)起者，只有在積極參與驗(yàn)證的情況下信譽(yù)才會(huì)有所增加。對(duì)于驗(yàn)證者也是如此。

2 GRCACAGT共謀攻擊

2.1 1/3節(jié)點(diǎn)共謀攻擊

GRCACAGT在達(dá)成共識(shí)部分分為身份驗(yàn)證和投票達(dá)成兩個(gè)階段。首先將驗(yàn)證者人數(shù)平均分為兩部分，一部分作為發(fā)起者身份驗(yàn)證階段的驗(yàn)證，身份驗(yàn)證成功后另一部分驗(yàn)證者再進(jìn)行投票達(dá)成共識(shí)。所以，只有身份驗(yàn)證和投票達(dá)成階段結(jié)果正確共識(shí)結(jié)果才可信。通過博弈論分析發(fā)現(xiàn)這個(gè)過程中存在嚴(yán)重的安全問題。分析發(fā)現(xiàn)通過多次共識(shí)后，節(jié)點(diǎn)被選擇的概率就會(huì)被暴露，概率大的節(jié)點(diǎn)會(huì)選擇共謀，當(dāng)共謀節(jié)點(diǎn)數(shù)量大于整體的1/3，整個(gè)區(qū)塊鏈系統(tǒng)就會(huì)面臨嚴(yán)重的安全問題。本文將這種共謀攻擊稱為1/3節(jié)點(diǎn)共謀攻擊，并構(gòu)建共謀合約解決了該安全問題。

對(duì)于該共謀攻擊問題，本文首先分析了實(shí)現(xiàn)攻擊的共謀節(jié)點(diǎn)數(shù)量及對(duì)應(yīng)的概率，主要分為兩個(gè)部分（最大數(shù)量的共謀節(jié)點(diǎn)，最小數(shù)量的共謀節(jié)點(diǎn)），然后利用智能合約設(shè)立共謀合約，再通過博弈論分析不同選擇的效用函數(shù)證明該共謀合約的正確性。

攻擊者人數(shù)越多，攻擊成功的概率越大，攻擊者的期望值越高，因此共謀人數(shù)通常遠(yuǎn)高于節(jié)點(diǎn)池中的1/3節(jié)點(diǎn)。

若共謀者要實(shí)現(xiàn)發(fā)起者身份驗(yàn)證結(jié)果不可信，則所有共謀節(jié)點(diǎn)都要在該階段選擇驗(yàn)證者時(shí)被選中，該概率為

通過以上分析可知在1/3節(jié)點(diǎn)共謀攻擊中，當(dāng)一些節(jié)點(diǎn)之間達(dá)成共謀之后, 該協(xié)議被攻擊的概率是一個(gè)不能忽視的大小，因此解決1/3節(jié)點(diǎn)共謀攻擊問題對(duì)該類算法的安全性具有重要意義。

2.2 共謀合約

2.2.1 建立合約

當(dāng)?shù)V池中的節(jié)點(diǎn)被選為發(fā)起者或驗(yàn)證者節(jié)點(diǎn)后，每個(gè)節(jié)點(diǎn)都上傳一筆保證金，保證節(jié)點(diǎn)的誠實(shí)行為。若節(jié)點(diǎn)行為誠實(shí)，完成共識(shí)后將會(huì)退回，但發(fā)現(xiàn)節(jié)點(diǎn)行為不誠實(shí)時(shí)將會(huì)被扣除，在共識(shí)階段，理性的礦工為了使自己的利益最大化會(huì)尋求共謀，對(duì)于這個(gè)共謀問題，本文利用構(gòu)建共謀合約來解決。合約規(guī)定，當(dāng)節(jié)點(diǎn)發(fā)起共謀后，接收到共謀消息的節(jié)點(diǎn)可以選擇同意或舉報(bào)，當(dāng)節(jié)點(diǎn)選擇舉報(bào)策略后，發(fā)起共謀節(jié)點(diǎn)保證金將被扣除，而舉報(bào)者獲得共謀節(jié)點(diǎn)的保證金作為舉報(bào)獎(jiǎng)金，并且兩者信譽(yù)值將會(huì)更新，合約如下。

實(shí)現(xiàn)共謀攻擊需要礦池中多個(gè)節(jié)點(diǎn)共謀，礦池中每個(gè)節(jié)點(diǎn)之間的共謀相互獨(dú)立，假設(shè)每次的共謀節(jié)點(diǎn)為c1和c2，節(jié)點(diǎn)c1和c2之間共謀，共謀合約參數(shù)如表2所示。

1) c1, c2輸入時(shí)，系統(tǒng)自動(dòng)執(zhí)行()函數(shù)。

2) 節(jié)點(diǎn)加入?yún)^(qū)塊鏈時(shí)支付保證金到系統(tǒng)，執(zhí)行()函數(shù)確定是否要被扣除。

3) 舉報(bào)共謀，假設(shè)c1給c2發(fā)起共謀，然后其中一方舉報(bào)另一方。分為兩種情況：c1給c2發(fā)起共謀，c2同意之后，c1反過來舉報(bào)c2獲得c2的保證金；c1給c2發(fā)起共謀，c2假裝答應(yīng)，等c1簽字確認(rèn)共謀后，c2舉報(bào)c1獲得c1保證金。

4) 將共謀者信譽(yù)值歸零，舉報(bào)者信譽(yù)增加。

表2 合約參數(shù)

2.2.2 合約分析

通過合約的建立可以得到節(jié)點(diǎn)c1和c2共謀雙方的博弈樹，如圖6所示。假設(shè)c1發(fā)起共謀，c2同意的概率為1，c1舉報(bào)c2的概率為2，因?yàn)樵谠摴仓\合約中作為c1不知道當(dāng)它發(fā)起共謀時(shí)c2是否會(huì)同意共謀，但是可以根據(jù)共謀攻擊獲得的利潤(rùn)、獲得的舉報(bào)獎(jiǎng)金以及它的信譽(yù)值等這些信息判斷c2同意共謀的概率1。同樣的c2會(huì)根據(jù)舉報(bào)獎(jiǎng)金、攻擊成功獲得的利益以及c1的一個(gè)信譽(yù)值確定被c1舉報(bào)的概率2。利用不完全信息動(dòng)態(tài)博弈分析該博弈，確定最后的精煉貝葉斯納什均衡解。

圖6 共謀雙方的博弈樹

Figure 6 Conspiracy the game tree of both parties

本文利用精煉貝葉斯納什均衡的方法求均衡解，要達(dá)到最優(yōu)必須每步最優(yōu)。如圖6所示。先分析c2同意共謀是否最優(yōu)，對(duì)于c2來說，當(dāng)它選擇了同意，那么希望c1不舉報(bào)它，最終達(dá)成共謀成功獲得額外收益。如果2較大，那c2相對(duì)于同意的策略不是最優(yōu)，即相對(duì)于c1來說選擇不舉報(bào)是c2選擇同意的目的，即

化簡(jiǎn)之后為

由

則有

因此，c1會(huì)大概率舉報(bào)c2，而對(duì)于c2來說，同意共謀就不再是當(dāng)前最優(yōu)策略，因此c2會(huì)舉報(bào)c1，而這時(shí)對(duì)于c1來說，發(fā)起共謀也不是最優(yōu)策略。

每個(gè)節(jié)點(diǎn)最終都是為了自己的利益最大化，當(dāng)一個(gè)節(jié)點(diǎn)發(fā)起共謀時(shí)，根據(jù)博弈樹中的線路必定最后會(huì)被另一方舉報(bào)，這時(shí)雙方就會(huì)形成囚徒困境。它的效用函數(shù)為

圖7 c1發(fā)起共謀后c2同意的效用函數(shù)

Figure 7 The utility function c2 agrees to after c1 initiates a conspiracy

圖8 c1發(fā)起共謀后c2不同意的效用函數(shù)

Figure 8 The utility function that c2 disagrees with after c1 initiates a conspiracy

圖9 c1和c2不共謀的效用函數(shù)

Figure 9 c1 and c2 are not collusive utility functions

3 安全性分析

3.1 抗DDoS和Eclipse attacks攻擊

在GRCACAGT共識(shí)算法中，礦池中節(jié)點(diǎn)分為提議者、發(fā)起者、驗(yàn)證者和其他，其中發(fā)起者和驗(yàn)證者身份的匿名保證了共識(shí)算法的安全性，如果發(fā)起者和驗(yàn)證者身份暴露，則很可能發(fā)生DDoS攻擊和Eclipse attacks攻擊[19]，這兩種攻擊都需要事先知道驗(yàn)證發(fā)起者和驗(yàn)證者，提出的共識(shí)協(xié)議中，用智能合約和加權(quán)隨機(jī)函數(shù)實(shí)現(xiàn)發(fā)起者和驗(yàn)證者的隨機(jī)化，并保證節(jié)點(diǎn)之間的身份匿名，從而防止DDoS攻擊和Eclipse attacks攻擊。

3.2 抗1/3節(jié)點(diǎn)共謀攻擊

利用博弈論分析容錯(cuò)類的共識(shí)算法中得到，該類共識(shí)算法每輪投票都需要保證正確節(jié)點(diǎn)多于錯(cuò)誤節(jié)點(diǎn)的3倍，當(dāng)大于1/3節(jié)點(diǎn)發(fā)生共謀則最終達(dá)成的共識(shí)結(jié)果不可信。對(duì)于該問題，在GRCACAGT共識(shí)算法中利用智能合約和博弈論方法設(shè)計(jì)了共謀合約，當(dāng)有節(jié)點(diǎn)發(fā)起共謀時(shí)，理性地接收節(jié)點(diǎn)最終會(huì)選擇舉報(bào)共謀而獲得收益，而對(duì)于共謀發(fā)起者來說這種策略是對(duì)其損失最大的策略，因此對(duì)于礦池中理性的礦工節(jié)點(diǎn)不會(huì)選擇發(fā)起共謀，從而防止了1/3節(jié)點(diǎn)共謀攻擊。

3.3 信譽(yù)動(dòng)態(tài)更新增強(qiáng)共識(shí)算法的正確性

一個(gè)人的信譽(yù)是變化的，并且一個(gè)人的不誠實(shí)概率等于信譽(yù)的對(duì)立。因此，本文利用構(gòu)建的信譽(yù)模型對(duì)節(jié)點(diǎn)信譽(yù)進(jìn)行更新，利用提議者的信譽(yù)值代替提議者的不誠實(shí)概率能夠使本文的共識(shí)算法更加高效，同時(shí)驗(yàn)證者的數(shù)量更加準(zhǔn)確，提高共識(shí)算法正確性。

4 實(shí)驗(yàn)分析

容錯(cuò)類共識(shí)算法中共謀攻擊的概率是不可以忽略的。本文對(duì)基于拜占庭容錯(cuò)的共識(shí)算法進(jìn)行7次共識(shí)實(shí)驗(yàn)，分別進(jìn)行20次、50次、80次、110次、140次、170次、200次共識(shí)過程。

在假設(shè)所有節(jié)點(diǎn)被選擇的概率相等下得到最后1/3節(jié)點(diǎn)共謀攻擊成功的次數(shù)和每次共謀成功的概率為0.436 4，如圖10所示。

圖10 1/3節(jié)點(diǎn)共謀攻擊情況分析

Figure 10 Analysis of conspiracy attack of 1/3 nodes

實(shí)際情況是，節(jié)點(diǎn)為了更大概率地實(shí)現(xiàn)攻擊會(huì)選擇概率大的節(jié)點(diǎn)進(jìn)行共謀，因此實(shí)現(xiàn)共謀攻擊的概率大于0.436 4。本文通過建立共謀合約制止節(jié)點(diǎn)之間的這種共謀。

發(fā)起者開銷為

驗(yàn)證者確認(rèn)的時(shí)間開銷為

投票者確認(rèn)階段時(shí)間開銷

總的時(shí)間開銷為

通過對(duì)比PoW、PoS、True Decentralization和GRCACAGT性能指標(biāo)（如表3所示），發(fā)現(xiàn)GRCACAGT相對(duì)PoW和PoS在TPS、時(shí)延、交易確認(rèn)時(shí)間、交易不可更改時(shí)間、資源消耗方面具有優(yōu)勢(shì)，相對(duì)True Decentralization具有更高的安全性。

表3 PoW, PoS, True Decentralization, GRCACAGT性能指標(biāo)

吞吐量是衡量系統(tǒng)單位時(shí)間內(nèi)處理交易的能力。本文使用每秒交易數(shù)（TPS，transaction per second）來表示吞吐量，比較了True Decentralization和GRCACAGT兩種共識(shí)機(jī)制的吞吐量，區(qū)塊鏈網(wǎng)絡(luò)中吞吐量指單位時(shí)間內(nèi)交易從產(chǎn)生到被確認(rèn)并寫入?yún)^(qū)塊鏈中的交易總數(shù)，計(jì)算如下：

圖11 True Decentralization和GRCACAGT吞吐量比較

Figure 11 Comparison of throughput with True Decentralization and GRCACAGT

運(yùn)行兩個(gè)共識(shí)協(xié)議30次后對(duì)比兩者的運(yùn)行時(shí)間，True Decentralization和GRCACAGT一輪驗(yàn)證時(shí)間對(duì)比如圖12所示。

圖12 True Decentralization和GRCACAGT運(yùn)行時(shí)間對(duì)比

Figure 12 Run time comparison of True Decentralization and GRCACAGT

通過圖12能夠清楚地知道，GRCACAGT 在時(shí)間上相比True Decentralization更有優(yōu)勢(shì)。

5 結(jié)束語

本文利用博弈論、映射函數(shù)和加權(quán)隨機(jī)函數(shù)，提出了GRCACAGT。GRCACAGT主要解決容錯(cuò)類算法中節(jié)點(diǎn)的全局隨機(jī)化問題，并利用博弈論分析發(fā)現(xiàn)這類算法中存在共謀攻擊，然后構(gòu)建共謀合約解決這類共謀攻擊從而實(shí)現(xiàn)該類算法的高安全性。安全性分析表明，GRCACAGT抗DDoS、Eclipse attacks、不誠實(shí)節(jié)點(diǎn)賄賂和與1/3節(jié)點(diǎn)共謀等攻擊。實(shí)驗(yàn)分析對(duì)比了GRCACAGT和相似的一些共識(shí)算法的吐量、交易完成時(shí)間、時(shí)間開銷等性能。實(shí)驗(yàn)結(jié)果表明，GRCACAGT在安全性和效率性方面得到了很大的提高。本文在選擇驗(yàn)證節(jié)點(diǎn)時(shí)通過不放回抽樣的方法避免節(jié)點(diǎn)被重復(fù)選中，但是該方法使協(xié)議的效率變低。并且，在信譽(yù)的動(dòng)態(tài)更新模型中，本文沒有具體設(shè)置模型的參數(shù)，對(duì)于影響信譽(yù)大小的元素沒有具體構(gòu)造出來。因此，高效地實(shí)現(xiàn)節(jié)點(diǎn)不被重復(fù)選擇和信譽(yù)更新模型具體的構(gòu)建是下一步工作的方向。

[1] TILBORGH C A, JAJIDIA S. Encyclopedia of cryptography and security[M]. US：Springer, 2011.

[2] GANESH C, ORLANDI C, TSCHUDI D. Proof-of-stake protocols for privacy-aware blockchains[C]//Advances in Cryptology – EUROCRYPT 2019, 2019

[3] KIAYIAS A, RUSSELL A, DAVID B, et al. Ouroboros: a provably secure proof-of-stake blockchain protocol[C]//Advances in Cryptology – CRYPTO 2017.

[4] KERBER T, KIAYIAS A, KOHLWEISS M, et al. Ouroboros crypsinous: privacy-preserving proof-of-stake[C]//Proceedings of 2019 IEEE Symposium on Security and Privacy. 2019: 157-174.

[5] FAN X X, CHAI Q. Roll-DPoS: a randomized delegated proof of stake scheme for scalable blockchain-based Internet of things systems[C]//Proceedings of the 15th EAI International Conference on Mobile and Ubiquitous Systems: Computing, Networking and Services. 2018.

[6] BUCHMAN E, KWON J, MILOSEVIC Z. The latest gossip on BFT consensus[EB].

[7] ALZAHRANI N, BULUSU N. Towards true decentralization: a blockchain consensus protocol based on game theory and randomness[C]//Decision and Game Theory for Security, 2018.

[8] BENTOV I, LEE C, MIZRAHI A, et al. Proof of activity[J]. ACM SIGMETRICS Performance Evaluation Review, 2014, 42(3): 34-37.

[9] CHEPURNOY A. Interactive proof-of-stake[EB].

[10] SABZMAKAN A, MIRTAHERI S L. An improved distributed access control model in cloud computing by blockchain[C]//Proceedings of 2021 26th International Computer Conference, Computer Society of Iran (CSICC). 2016: 1-4.

[11] GILAD Y, HEMO R, MICALI S, et al. Algorand: scaling Byzantine agreements for cryptocurrencies[C]//Proceedings of the 26th Symposium on Operating Systems Principles. 2017.

[12] OMAR M, CHALLAL Y, BOUABDALLAH A. Reliable and fully distributed trust model for mobile ad hoc networks[J]. Computers & Security, 2009, 28(3/4): 199-214.

[13] ZHAN Y, WANG B C, LU R X, et al. DRBFT: Delegated randomization Byzantine fault tolerance consensus protocol for blockchains[J]. Information Sciences, 2021, 559: 8-21.

[14] DONG C Y, WANG Y L, ALDWEESH A, et al. Betrayal, distrust, and rationality: smart counter-collusion contracts for verifiable cloud computing[EB].

[15] CHEN H, LAINE K, PLAYER R. Simple encrypted arithmetic library - SEAL v2.1[M]. Berlin:Springer, 2016.

[16] ANDERW M, YU X, KUYLE C,et alThe Honey badger of BFT Protocols[R]. 2016.

[17] JALALZAI M, BUSCH C, JII G R. Proteus: a scalable bft consesus protocol for blockchains[C]//CORR .2019.

[18] LESSMANN S, BAESENS B, SEOW H V, et al. Benchmarking state-of-the-art classification algorithms for credit scoring: an update of research[J]. European Journal of Operational Research, 2015, 247(1): 124-136.

[19] 王纘, 田有亮, 岳朝躍, 等. 基于門限密碼方案的共識(shí)機(jī)制[J]. 計(jì)算機(jī)研究與發(fā)展, 2019, 56(12): 2671-2683.

WANG Z, TIAN Y L, YUE C Y, et al. Consensus mechanism based on threshold cryptography scheme[J]. Journal of Computer Research and Development, 2019, 56(12): 2671-2683.

[20] YU Y L, CHEN T S. An efficient threshold group signature scheme[J]. Applied Mathematics and Computation, 2005, 167(1): 362-371.

Global randomized consensus algorithm resist collusion attack based on game theory

ZHANG Bao1,2, TIAN Youliang1,2, GAO Sheng3

1. Computer Science and Technology Institute, Guizhou University, Guiyang 550025, China 2. Guizhou Provincial Key Laboratory of Public Big Data, Guiyang 550025, China 3. Information Institute CentralUniversityofFinanceandEconomics, Beijing 100081, China

As the cornerstone of blockchain technology, consensus technology has received more attention with the continuous development of blockchain technology. The development of consensus technology has become more and more rapid, but there are still related problems. Nowadays, fault-tolerant consensus algorithms, as one of the representative blockchain consensus technologies, still have many problems to be studied. The problem of node randomness and node collusion attacks in fault-tolerant consensus algorithms had been studied, and a game-theoretic-based anti-corruption algorithm was proposed. The global randomization consensus algorithm of collusion attack improved the security and throughput of the blockchain network by realizing the randomization of nodes and solving related security problems. In the process of selecting nodes participating in the fault-tolerant consensus algorithm, the global randomization of the initiator and verifier nodes was realized by using the mapping function and the weighted random function, thereby ensuring the identity anonymity of the initiator and verifier nodes and improving the blockchain network security accordingly. The reputation update model was used to realize the dynamic update of the reputation, and the game theory was used to analyze the security problems of the fault-tolerant consensus algorithm. A more correct and efficient algorithm model was constructed to improve the throughput of the algorithm and analyze the problem of collusion attack of more than one third of the nodes in this kind of algorithm, the refined Bayesian game was used to construct a collusion contract and analyze the collusion The Nash equilibrium point between the two nodes was adopted to solve the collusion attack problem of more than one third of the nodes. The security analysis and experiments show that the global randomization consensus algorithm based on the game theory anti-collusion attack is better than PoW、PoS and PBFT. The consensus algorithm is not only effective to improve throughput and reduce computing resource consumption, but also resistant to DDoS, Eclipse attacks and collusion attacks by more than one third of nodes.

consensus algorithm, global randomization, game theory, conspiracy attack

The National Natural Science Foundation of China (61662009, 61772008), Science and Technology Major Support Program of Guizhou Province (20183001), Key Program of the National Natural Science Union Foundation of China (U1836205), Science and Technology Program of Guizhou Province ([2019]1098), Project of High-level Innovative Talents of Guizhou Province ([2020]6008), Science and Technology Program of Guiyang ([2021]1-5)

張寶, 田有亮, 高勝. 基于博弈論抗共謀攻擊的全局隨機(jī)化共識(shí)算法[J]. 網(wǎng)絡(luò)與信息安全學(xué)報(bào), 2022, 8(4):98-109.

TP393

A

10.11959/j.issn.2096?109x.2022048

張寶（1995?），男，貴州畢節(jié)人，貴州大學(xué)碩士生，主要研究方向?yàn)槊艽a學(xué)、區(qū)塊鏈網(wǎng)絡(luò)和共識(shí)算法。

田有亮（1982?），男，貴州盤州人，博士，貴州大學(xué)教授、博士生導(dǎo)師，主要研究方向?yàn)樗惴ú┺恼?、密碼學(xué)與安全協(xié)議、大數(shù)據(jù)安全與隱私保護(hù)、區(qū)塊鏈與電子貨幣等。

高勝（1987?），男，湖北黃岡人，博士，中央財(cái)經(jīng)大學(xué)副教授，主要研究方向?yàn)閿?shù)據(jù)安全與隱私保護(hù)、區(qū)塊鏈技術(shù)及應(yīng)用。

2021?11?22；

2022?03?01

田有亮，youliangtian@163.com

國家自然科學(xué)基金（61662009，61772008）；貴州省科技重大專項(xiàng)計(jì)劃（20183001）；國家自然科學(xué)基金聯(lián)合基金重點(diǎn)支持項(xiàng)目（U1836205）；貴州省科技計(jì)劃項(xiàng)目（[2019]1098）；貴州省高層次創(chuàng)新型人才項(xiàng)目（[2020]6008）；貴陽市科技計(jì)劃項(xiàng)目（[2021]1-5）

ZHANG B, TIAN Y L, GAO S. Global randomized consensus algorithm resist collusion attack based on game theory[J]. Chinese Journal of Network and Information Security, 2022, 8(4): 98-109.