程穗，林憲正，俞能海

（1.中國(guó)科學(xué)技術(shù)大學(xué)網(wǎng)絡(luò)空間安全學(xué)院，安徽 合肥 230001；2.中國(guó)科學(xué)院電磁空間信息重點(diǎn)實(shí)驗(yàn)室，安徽 合肥 230001）

1 引言

比特幣是一種去中心化的電子加密“貨幣”[1]。作為一個(gè)賬單系統(tǒng)，比特幣不依賴于中央機(jī)構(gòu)發(fā)行新幣和維持交易，而是依賴分布式系統(tǒng)來維護(hù)交易列表，這個(gè)交易列表即區(qū)塊鏈[2]。區(qū)塊鏈?zhǔn)峭ㄟ^密碼學(xué)方法生成的一串相關(guān)數(shù)據(jù)塊。新區(qū)塊始終鏈接到其前一個(gè)區(qū)塊。因此，區(qū)塊鏈?zhǔn)且环N協(xié)議，當(dāng)新區(qū)塊被挖掘出來時(shí)，區(qū)塊鏈的數(shù)據(jù)發(fā)生變化[3]。

在比特幣系統(tǒng)中，所有用戶都可以參與由工作量證明（PoW）協(xié)議維護(hù)的區(qū)塊鏈[4-6]。PoW協(xié)議要求有效塊的哈希值小于預(yù)定的閾值[7]。每個(gè)礦工通過調(diào)整哈希函數(shù)的輸入值（在區(qū)塊中稱為nonce）進(jìn)行有效區(qū)塊的計(jì)算[8]。獲取有效區(qū)塊后，礦工將廣播該區(qū)塊到整個(gè)網(wǎng)絡(luò)，其他礦工在驗(yàn)證該區(qū)塊的有效性后停止當(dāng)前高度的區(qū)塊挖掘[9]。

在傳統(tǒng)區(qū)塊鏈中，除了創(chuàng)世區(qū)塊外，每個(gè)區(qū)塊的區(qū)塊頭均包含其父區(qū)塊的哈希值。每個(gè)新區(qū)塊的生成方式都是通過更改隨機(jī)數(shù)，并不斷計(jì)算其區(qū)塊頭的哈希值，直到其小于當(dāng)前難度。因此，挖掘只是一個(gè)純粹的計(jì)算過程。計(jì)算速度越快，挖掘出新區(qū)塊的可能性越大。

普通的采礦設(shè)備經(jīng)歷了從PC到GPU和FPGA的多種變化，直到ASIC礦機(jī)出現(xiàn)。當(dāng)前，比特幣采礦市場(chǎng)已經(jīng)被ASIC礦機(jī)所主導(dǎo)，并且無法通過使用其他采礦設(shè)備來營(yíng)利[10]。ASIC礦機(jī)是致力于挖礦過程。但是，早期使用ASIC礦機(jī)存在一系列問題：

1)隨著網(wǎng)絡(luò)的計(jì)算能力持續(xù)迅速地提高，ASIC礦機(jī)芯片的壽命變得非常短（約6個(gè)月）；

2)投資ASIC采礦設(shè)備會(huì)增加成本（電力成本和冷卻成本）；

3)由于行業(yè)的不成熟，采礦設(shè)備的延遲交付導(dǎo)致芯片被淘汰。

盡管使用ASIC礦機(jī)進(jìn)行挖礦已經(jīng)相當(dāng)成熟，并且挖礦設(shè)備的壽命更長(zhǎng)，但挖礦業(yè)已經(jīng)從個(gè)人領(lǐng)域轉(zhuǎn)移到了大型的專業(yè)挖礦中心。因此，挖礦行業(yè)對(duì)個(gè)體礦工非常不友好。此外，整個(gè)網(wǎng)絡(luò)中的大部分計(jì)算能力集中在少數(shù)人手中，這不僅增加了資源浪費(fèi)，而且增加了51%攻擊的可能性。這與比特幣[11]最初的設(shè)計(jì)目的背道而馳。

為了打破挖礦行業(yè)中ASIC礦機(jī)的壟斷，已經(jīng)有多種方法被提出，如具有剛性內(nèi)存的函數(shù)。剛性內(nèi)存函數(shù)是一類很難并行處理的哈希函數(shù)。在此功能中，完成給定計(jì)算問題所需的時(shí)間主要取決于從內(nèi)存中讀取數(shù)據(jù)的時(shí)間，這可以減少總時(shí)間成本上的計(jì)算能力部分。因此，通過增加從內(nèi)存中讀取數(shù)據(jù)的次數(shù)，I/O所占的時(shí)間將控制新區(qū)塊挖掘的時(shí)間，從而達(dá)到抵抗ASIC礦機(jī)的目的。

現(xiàn)在已經(jīng)有與剛性內(nèi)存相關(guān)的算法被提出，如Scrypt和Primecoin[12]。這些算法可以分為兩個(gè)步驟：第一步是從一個(gè)隨機(jī)數(shù)種子生成一個(gè)偽隨機(jī)數(shù)數(shù)組，該數(shù)組存儲(chǔ)在主存儲(chǔ)器中；第二步是計(jì)算新區(qū)塊的哈希值，哈希函數(shù)的輸入是相關(guān)區(qū)塊區(qū)塊頭的串聯(lián)，這些區(qū)塊是從偽隨機(jī)數(shù)數(shù)組中隨機(jī)選擇的。

由于必須讀取幾個(gè)偽隨機(jī)數(shù)，數(shù)據(jù)讀取將影響哈希計(jì)算的時(shí)間。然而，在Scrypt函數(shù)中，每個(gè)偽隨機(jī)數(shù)都是通過前一個(gè)偽隨機(jī)數(shù)計(jì)算出來的，ASIC礦工可以通過僅存儲(chǔ)具有奇數(shù)索引[13]的偽隨機(jī)數(shù)來將主存儲(chǔ)器中使用的空間減少一半。如果哈希函數(shù)需要帶有偶數(shù)索引的偽隨機(jī)數(shù)，則可以從前一個(gè)隨機(jī)數(shù)計(jì)算出該值。因此，對(duì)于這些剛性內(nèi)存函數(shù)，計(jì)算的時(shí)間和內(nèi)存屬性是可以進(jìn)行調(diào)節(jié)的。時(shí)間和內(nèi)存的折中可以減小哈希計(jì)算中數(shù)據(jù)讀取的影響，使ASIC礦機(jī)和通用CPU之間的性能差距仍然很大。

為了解決此問題，需要一種新的哈希函數(shù)，該函數(shù)不具有時(shí)間內(nèi)存折中的功能。也就是說，如果存儲(chǔ)器的大小小于閾值，則挖礦性能將顯著下降，并且沒有有效的方法來設(shè)計(jì)一種具有時(shí)間/內(nèi)存權(quán)衡的方法。此外，希望協(xié)議中的數(shù)據(jù)讀取時(shí)間是可控的，因此，本文提出一種新的區(qū)塊鏈協(xié)議，在該協(xié)議中，每個(gè)區(qū)塊除了與其父區(qū)塊相關(guān)聯(lián)之外，還與之前的多個(gè)區(qū)塊相關(guān)聯(lián)。該協(xié)議決定了主導(dǎo)挖礦時(shí)間的是I/O，而不是計(jì)算速率。

2 基于剛性內(nèi)存的協(xié)議模型

2.1 協(xié)議模型

本節(jié)將詳細(xì)描述所提出的協(xié)議。該協(xié)議具有兩個(gè)參數(shù)（n,m），其中，n表示在區(qū)塊挖掘過程中可能被使用的區(qū)塊的數(shù)量，m表示在內(nèi)存中選擇的哈希值的數(shù)量。為了提高協(xié)議的性能，應(yīng)將這n個(gè)哈希值存儲(chǔ)在緩存或內(nèi)存中，否則處理器必須花費(fèi)大量時(shí)間在區(qū)塊挖掘過程中訪問這些值。在提出的協(xié)議中，區(qū)塊鏈中最后n個(gè)區(qū)塊的哈希值依次表示為{Ni|i=0,…,n-1}，其中N0表示最新區(qū)塊。n個(gè)哈希值中的m個(gè)（包含N0）將用于新區(qū)塊的哈希計(jì)算。給定隨機(jī)數(shù)的值，以下是選擇m個(gè)哈希值的步驟。

1)令t0=nonce和i=1，計(jì)算t=hash0(t0)。

2)令ti=Ni，計(jì)算t=hash0(ti)。如果i=m，輸出(t0,t1,…,tm)，否則i=i+1并重復(fù)步驟2)。

可以看到，hash0的共域是{0,…,n-1}，那么有 hash0(x)=x(modn)。哈希值可以通過R=hash(t0||t1,Y||…||tm,Y||N0)進(jìn)行計(jì)算。如果哈希值R滿足目標(biāo)難度，則挖掘過程結(jié)束，否則選擇新的nonce并重復(fù)該過程以找出新的m個(gè)哈希值。在實(shí)現(xiàn)中，這n個(gè)哈希值存儲(chǔ)在循環(huán)隊(duì)列中，如圖1所示，避免數(shù)據(jù)移動(dòng)。

圖1 環(huán)隊(duì)列存儲(chǔ)方式Figure 1 Circular Queue

2.2 協(xié)議分析

2.2.1 時(shí)間/內(nèi)存屬性權(quán)衡

作為內(nèi)存依賴型的PoW算法，Scrypt算法包含兩個(gè)步驟。第一步，依次生成n個(gè)偽隨機(jī)數(shù)，其中每個(gè)隨機(jī)數(shù)都是由其前一個(gè)隨機(jī)數(shù)計(jì)算而來。第二步，通過使用偽隨機(jī)順序選擇的多個(gè)偽隨機(jī)數(shù)來生成哈希值。通過在存儲(chǔ)器中存儲(chǔ)偶數(shù)位索引的個(gè)偽隨機(jī)數(shù)，可以進(jìn)行時(shí)間內(nèi)存的權(quán)衡。由于在哈希運(yùn)算中，ASIC礦機(jī)的計(jì)算速率比通用CPU快得多，ASIC礦機(jī)可以犧牲部分計(jì)算能力來減少所需的內(nèi)存。因此，這種剛性內(nèi)存算法無法達(dá)到較好的抗ASIC效果。

在本文提出的協(xié)議中，每個(gè)哈希值不能直接通過其前一個(gè)哈希值計(jì)算出來，因此該協(xié)議不具有時(shí)間/內(nèi)存權(quán)衡的屬性，這個(gè)屬性被稱為Memory-hard。因此，如果n個(gè)哈希值不能完全存儲(chǔ)在內(nèi)存中，那么應(yīng)當(dāng)存儲(chǔ)在輔助存儲(chǔ)設(shè)備（如硬盤）中。當(dāng)哈希計(jì)算過程需要使用對(duì)應(yīng)的哈希值時(shí)，處理器必須訪問硬盤讀取數(shù)據(jù)，這將減慢整個(gè)挖掘速度。

2.2.2 加載時(shí)間分析

在本文提出的協(xié)議中，對(duì)內(nèi)存是有限制的，因此當(dāng)內(nèi)存大小小于n時(shí)，區(qū)塊的挖掘速度將顯著降低。s表示存儲(chǔ)在內(nèi)存中的哈希值的數(shù)量，當(dāng)s

當(dāng)s≥n時(shí)，哈希計(jì)算所需數(shù)據(jù)的平均讀取時(shí)間為mt0。當(dāng)s＜n時(shí)，哈希計(jì)算所需數(shù)據(jù)的平均讀取時(shí)間為。通常，t1是t0的數(shù)萬倍，因此，合適的n值可以限制ASIC礦機(jī)在挖礦哈希計(jì)算過程中的優(yōu)勢(shì)。

3 安全性分析

本節(jié)將通過對(duì)區(qū)塊鏈交易進(jìn)行篡改攻擊來分析區(qū)塊鏈的安全性。在每個(gè)區(qū)塊的區(qū)塊頭，令Y表示區(qū)塊中交易的哈希值，令X表示區(qū)塊的其余部分。本文將從單個(gè)區(qū)塊的篡改攻擊和連續(xù)兩個(gè)區(qū)塊的篡改攻擊來分析協(xié)議的安全性。

（1）單個(gè)區(qū)塊篡改攻擊

首先分析對(duì)區(qū)塊鏈中一個(gè)區(qū)塊進(jìn)行篡改的難度。對(duì)于如圖2所示的傳統(tǒng)區(qū)塊鏈，區(qū)塊A是區(qū)塊B的父區(qū)塊。攻擊者篡改了區(qū)塊A中的交易，這將改變區(qū)塊A中Y的值。區(qū)塊A′表示被篡改后的區(qū)塊，Y′表示篡改后交易的哈希值。如果修改了區(qū)塊A中的交易，則區(qū)塊A′必須滿足

假設(shè)找到合適的A′Y′滿足式(1)的概率為P。

圖2 對(duì)傳統(tǒng)區(qū)塊鏈的攻擊Figure 2 Attackon traditional blockchain

對(duì)于本文提出的協(xié)議，如圖3所示，每個(gè)區(qū)塊都與其父區(qū)塊以外的m個(gè)區(qū)塊相關(guān)聯(lián)，當(dāng)區(qū)塊N0被篡改時(shí)，應(yīng)滿足

其中，每個(gè)di由2.1節(jié)中的算法計(jì)算。也就是說，對(duì)于i=0,…,m，有d1=hash0(Anonce)和di=hash0(Ndi-1)。假設(shè)找到合適的N0,Y′滿足式(2)的概率表示為q。在最壞的情況下，如果di≠0，則對(duì)于i=0,…,m，在式(1)和式(2)中更改的長(zhǎng)度是相同的。由生日攻擊[14]可知，有q=p。

圖3 新的區(qū)塊鏈結(jié)構(gòu)Figure 3 New blockchain structure

攻擊者將用于區(qū)塊A的哈希計(jì)算中使用到的區(qū)塊N0篡改為。此外，N0用于其他t個(gè)表示為G1,G2,…,Gt的區(qū)塊的哈希計(jì)算中。令Ui表示用于區(qū)塊iG哈希計(jì)算中使用的m+1個(gè)哈希值，令U0表示用于區(qū)塊A哈希計(jì)算中使用的m+1個(gè)哈希值的集合。對(duì)于i=0,…,t，hash (N0)∈Ui，有

其中，每個(gè)ui,j∈Ui，j=0,…,m。值得注意的是，對(duì)于i=0,…,t,ui,k=hash(N0,Y)∈Ui和ui′,k=hash(N0,Y′)表示替換后的哈希值。

這t+1個(gè)方程是獨(dú)立的。在最壞的情況下，只有ui,k=hash(N0)∈Ui，因此概率為qt+1=pt+1≤p。這表明，當(dāng)t≥1時(shí)，所提出的協(xié)議比傳統(tǒng)的區(qū)塊鏈協(xié)議更安全。

（2）連續(xù)兩個(gè)區(qū)塊篡改攻擊

如圖4所示，如果將區(qū)塊A篡改為A′，并且將區(qū)塊B篡改為，則在傳統(tǒng)區(qū)塊鏈協(xié)議中，當(dāng)區(qū)塊A被篡改為區(qū)塊A′時(shí)，成功的攻擊必須滿足

圖4 對(duì)新區(qū)塊鏈的相鄰篡改攻擊Figure 4 Adjacent tamper attack on new blockchain

當(dāng)區(qū)塊B被篡改為區(qū)塊B′時(shí)，成功的攻擊必須滿足

假設(shè)滿足式(5)的概率表示為p1。

在本文提出的協(xié)議中，區(qū)塊B和區(qū)塊C都與m+1個(gè)之前的區(qū)塊相關(guān)聯(lián)。對(duì)于i=0,…,m，令表示區(qū)塊B哈希計(jì)算過程中使用的m+1個(gè)哈希值組成的向量，令表示區(qū)塊C哈希計(jì)算過程中使用的m+1個(gè)哈希值組成的向量。值得注意的是，有B0=hash(A)和C0=hash(B)。那么必須滿足

如果區(qū)塊B的哈希計(jì)算過程使用了區(qū)塊A的哈希值，則將其他ta個(gè)區(qū)塊定義為GA1,GA2,…,GAta。同樣地，如果區(qū)塊C的哈希計(jì)算過程使用了區(qū)塊B的哈希值，則將其他tb個(gè)區(qū)塊定義為GB1,GB2,…,。

對(duì)于i=1,2,…,ta，令UAi表示參與區(qū)塊GAi的哈希計(jì)算的m+1個(gè)哈希值組成的向量，令UBi表示參與區(qū)塊GBi的哈希計(jì)算的m+1個(gè)哈希值組成的向量。特別地，UA0對(duì)應(yīng)區(qū)塊B哈希計(jì)算的m+1個(gè)哈希值向量，UB0對(duì)應(yīng)區(qū)塊C哈希計(jì)算的m+1個(gè)哈希值向量。對(duì)于i=0,1,…,ta，有hash(A)∈UAi。對(duì)于i=0,1,…,tb，有hash(B)∈UBi，那么可以得到

其中，當(dāng)j=0,…,m時(shí)，有。式(8)中的，并且當(dāng)i=0,…,t時(shí)，將定義為篡改后的哈希值。同樣地，必須滿足

其中，當(dāng)j=0,…,m時(shí)，有ubi,j∈UBi。式(9)中的ubi,k=hash(BY)∈UBi，并且當(dāng)i=0,…,t時(shí)，將ub′i,k=hash(BY′)定義為篡改后的哈希值。

可以看出，這ta+1和tb+1個(gè)方程都是獨(dú)立的。因此，當(dāng)ta≥0時(shí)，將區(qū)塊A篡改為區(qū)塊A′并滿足式(8)的概率為；當(dāng)t≥0時(shí)，將b區(qū)塊B篡改為區(qū)塊B′并滿足式(9)的概率為。因此，攻擊成功的概率為P=P1P2=。可以看出，P比在傳統(tǒng)的區(qū)塊鏈協(xié)議中攻擊成功的概率低。

4 協(xié)議改進(jìn)

為了提高協(xié)議實(shí)現(xiàn)的效率與穩(wěn)固該協(xié)議的剛性屬性，本節(jié)從相關(guān)聯(lián)的區(qū)塊數(shù)m的確定與新區(qū)塊計(jì)算使用的哈希函數(shù)的輸入兩方面進(jìn)行分析。

（1）相關(guān)聯(lián)的區(qū)塊數(shù)的確定

由2.1節(jié)中的協(xié)議步驟可知，本文提出的協(xié)議在新區(qū)塊的挖掘過程中，每選擇一個(gè)隨機(jī)值nonce，就需要重新從內(nèi)存中讀取m個(gè)區(qū)塊的哈希值。令x表示比特幣網(wǎng)絡(luò)中計(jì)算一個(gè)新區(qū)塊平均所需的計(jì)算次數(shù)，t2表示ASIC礦機(jī)進(jìn)行一次哈希計(jì)算所需的時(shí)間，t3表示普通CPU進(jìn)行一次哈希計(jì)算所需的時(shí)間。由2.2.2節(jié)可知，當(dāng)s≥n時(shí)，ASIC礦機(jī)進(jìn)行一輪挖礦計(jì)算所需的時(shí)間為t2+mt0，CPU礦機(jī)進(jìn)行一輪挖礦計(jì)算所需的時(shí)間為t3+mt0；當(dāng)s＜n時(shí)，ASIC礦機(jī)進(jìn)行一輪挖礦計(jì)算所需的時(shí)間為，CPU礦機(jī)進(jìn)行一輪挖礦計(jì)算所需的時(shí)間為t3+mt0。可以看出，哈希計(jì)算的時(shí)間在ASIC礦機(jī)和CPU礦機(jī)進(jìn)行一輪挖礦計(jì)算的時(shí)間中所占的比例可忽略不計(jì)。因此，為了達(dá)到抗ASIC礦機(jī)的效果，應(yīng)增大n的取值，而m的取值大小在抗ASIC方面沒有突出的作用。增大m的值僅僅增強(qiáng)了區(qū)塊鏈穩(wěn)定性，但同時(shí)導(dǎo)致節(jié)點(diǎn)在進(jìn)行區(qū)塊驗(yàn)證時(shí)面臨更大的壓力，新區(qū)塊的驗(yàn)證過程也變得更加煩瑣。因此，為了減輕驗(yàn)證節(jié)點(diǎn)的負(fù)擔(dān)，取m=1。

（2）哈希函數(shù)的輸入

在傳統(tǒng)區(qū)塊鏈的區(qū)塊挖掘過程中，新區(qū)塊僅僅與其前一個(gè)區(qū)塊相關(guān)聯(lián)，因此其哈希計(jì)算過程中，哈希函數(shù)的輸入僅包含其前一個(gè)區(qū)塊的哈希值。在本文提出的協(xié)議中，新區(qū)塊除了與其前一個(gè)區(qū)塊相關(guān)，還與m個(gè)之前的區(qū)塊相關(guān)。假設(shè)m=2，令T0表示當(dāng)前區(qū)塊，T1、T2和T3表示T0的父區(qū)塊。T1為T0的前一個(gè)區(qū)塊，T2和T3為隨機(jī)選擇的父區(qū)塊，T3的區(qū)塊高度小于T2。按照區(qū)塊的形成時(shí)間，區(qū)塊T3和T2比區(qū)塊T1更早出現(xiàn)。因此，在對(duì)區(qū)塊T0進(jìn)行哈希計(jì)算的過程中，需要用到其3個(gè)父區(qū)塊的哈希值 hash。然而，當(dāng)按照區(qū)塊高度由低到高對(duì)區(qū)塊哈希值進(jìn)行串聯(lián)作為哈希函數(shù)的輸入時(shí)，ASIC礦機(jī)可能不需要對(duì)所有n個(gè)區(qū)塊進(jìn)行存儲(chǔ)，這種情況是由某些哈希函數(shù)是線性輸入導(dǎo)致的。因此，順序串聯(lián)可能導(dǎo)致本協(xié)議不是完全剛性的，這與本文提出的完全剛性的屬性不符，對(duì)哈希函數(shù)輸入的串聯(lián)方式進(jìn)行了更改。本文將新區(qū)塊的前一個(gè)區(qū)塊的哈希值放在首位，然后按照區(qū)塊高度由低到高進(jìn)行串聯(lián)。對(duì)于T1、T2和T3，計(jì)算新區(qū)塊T0時(shí)使用的哈希函數(shù)輸入的串聯(lián)方式為hash。

5 結(jié)束語

本文提出了一種在區(qū)塊鏈上的完全剛性內(nèi)存的協(xié)議。該協(xié)議是一種無記憶功能，沒有時(shí)間/內(nèi)存折中的協(xié)議。因此，內(nèi)存中必須存儲(chǔ)區(qū)塊鏈的最后n個(gè)區(qū)塊的哈希值。然后，隨機(jī)選擇n個(gè)哈希值中的m個(gè)和最新的哈希值串聯(lián)來計(jì)算新區(qū)塊的哈希值。因此，每個(gè)區(qū)塊不僅與其父區(qū)塊相關(guān)聯(lián)，而且與n個(gè)先前的區(qū)塊中的m個(gè)相關(guān)聯(lián)。分析表明，本文提出的協(xié)議是一種完全剛性的存儲(chǔ)協(xié)議，并且證明了所提出協(xié)議的安全性優(yōu)于常規(guī)區(qū)塊鏈協(xié)議。