基于剛性內存的區塊鏈協議改進

程穗，林憲正，俞能海

（1.中國科學技術大學網絡空間安全學院，安徽 合肥 230001；2.中國科學院電磁空間信息重點實驗室，安徽 合肥 230001）

1 引言

比特幣是一種去中心化的電子加密“貨幣”[1]。作為一個賬單系統，比特幣不依賴于中央機構發行新幣和維持交易，而是依賴分布式系統來維護交易列表，這個交易列表即區塊鏈[2]。區塊鏈是通過密碼學方法生成的一串相關數據塊。新區塊始終鏈接到其前一個區塊。因此，區塊鏈是一種協議，當新區塊被挖掘出來時，區塊鏈的數據發生變化[3]。

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

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

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

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

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

3)由于行業的不成熟，采礦設備的延遲交付導致芯片被淘汰。

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

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

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

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

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

2 基于剛性內存的協議模型

2.1 協議模型

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

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

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

可以看到，hash0的共域是{0,…,n-1}，那么有 hash0(x)=x(modn)。哈希值可以通過R=hash(t0||t1,Y||…||tm,Y||N0)進行計算。如果哈希值R滿足目標難度，則挖掘過程結束，否則選擇新的nonce并重復該過程以找出新的m個哈希值。在實現中，這n個哈希值存儲在循環隊列中，如圖1所示，避免數據移動。

圖1 環隊列存儲方式Figure 1 Circular Queue

2.2 協議分析

2.2.1 時間/內存屬性權衡

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

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

2.2.2 加載時間分析

在本文提出的協議中，對內存是有限制的，因此當內存大小小于n時，區塊的挖掘速度將顯著降低。s表示存儲在內存中的哈希值的數量，當s

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

3 安全性分析

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

（1）單個區塊篡改攻擊

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

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

圖2 對傳統區塊鏈的攻擊Figure 2 Attackon traditional blockchain

對于本文提出的協議，如圖3所示，每個區塊都與其父區塊以外的m個區塊相關聯，當區塊N0被篡改時，應滿足

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

圖3 新的區塊鏈結構Figure 3 New blockchain structure

攻擊者將用于區塊A的哈希計算中使用到的區塊N0篡改為。此外，N0用于其他t個表示為G1,G2,…,Gt的區塊的哈希計算中。令Ui表示用于區塊iG哈希計算中使用的m+1個哈希值，令U0表示用于區塊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。這表明，當t≥1時，所提出的協議比傳統的區塊鏈協議更安全。

（2）連續兩個區塊篡改攻擊

如圖4所示，如果將區塊A篡改為A′，并且將區塊B篡改為，則在傳統區塊鏈協議中，當區塊A被篡改為區塊A′時，成功的攻擊必須滿足

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

當區塊B被篡改為區塊B′時，成功的攻擊必須滿足

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

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

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

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

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

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

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

4 協議改進

為了提高協議實現的效率與穩固該協議的剛性屬性，本節從相關聯的區塊數m的確定與新區塊計算使用的哈希函數的輸入兩方面進行分析。

（1）相關聯的區塊數的確定

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

（2）哈希函數的輸入

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

5 結束語

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