程穗，林憲正，俞能海

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

1 引言

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

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

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

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

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

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

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

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

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

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

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

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

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

2.1 協(xié)議模型

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

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

2)令ti=Ni，計算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)進行計算。如果哈希值R滿足目標(biāo)難度，則挖掘過程結(jié)束，否則選擇新的nonce并重復(fù)該過程以找出新的m個哈希值。在實現(xiàn)中，這n個哈希值存儲在循環(huán)隊列中，如圖1所示，避免數(shù)據(jù)移動。

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

2.2 協(xié)議分析

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

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

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

2.2.2 加載時間分析

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

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

3 安全性分析

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

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

首先分析對區(qū)塊鏈中一個區(qū)塊進行篡改的難度。對于如圖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 對傳統(tǒng)區(qū)塊鏈的攻擊Figure 2 Attackon traditional blockchain

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

4 協(xié)議改進

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

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

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

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

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

5 結(jié)束語

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