模糊隨機碰撞工作量證明共識算法

廖浩德，鄒曉鳳，王 兵，肖辭源

1.西南石油大學 計算機科學學院，成都 610500

2.成都川鏈大數據研究中心，成都 610500

2008年，在發表名為《比特幣：一種點對點式的電子現金系統》論文中，首次提出了區塊鏈（blockchain）這一概念[1]。區塊鏈也稱為價值互聯網[2]，本質上是一個去中心化的分布式數據庫，是密碼學、共識算法、點對點網絡等多種技術的融合創新。區塊鏈通過共識機制，實現區塊鏈系統中節點數據一致，共識算法則是實現這一目標的核心要素。

根據應用場景不同，區塊鏈分為公有鏈、私有鏈、聯盟鏈[3]。私有鏈的寫入權限歸屬于某個組織和機構，其網絡系統中的參與節點會被嚴格限制。聯盟鏈中節點數量較為固定，分為記賬節點和其他節點。其中記賬節點由群體內部事先指定，記賬節點共同決定鏈上每個區塊的生成，其他節點可以參與交易，但不過問記賬過程。聯盟鏈的共識算法分為拜占庭容錯共識算法和非拜占庭容錯共識算法，前者的典型共識算法有實用拜占庭容錯（PBFT）[4]、HotStuffBFT[5]等；后者的典型共識算法有Paxos[6]、Raft[7]等。相對于私有鏈和聯盟鏈，公有鏈是目前應用最廣泛的區塊鏈。

公有鏈系統允許所有參與節點對其數據進行讀寫、并可以自由進出，其典型的共識機制包括工作量證明（PoW）[8]、權益證明（PoS）[9]、股份授權證明（DPoS）[10]等算法。其中，PoW算法作為較為成熟的共識技術被應用于比特幣、以太坊等公有鏈。但在實際應用中存在一些急需解決的問題，例如，高速計算機或量子計算機的出現將導致PoW所使用的加密算法難以保證其安全性[11]，對算力也難以調控。進一步提高區塊鏈的安全性，對高速計算機算力的調控等都是當前區塊鏈研究的熱點。

本文針對共識算法存在的安全性和算力難調控等問題，提出了基于模糊數學方法的新共識算法，該算法通過引進模糊傳遞閉包陣等技術，增大其解空間解決安全性問題，還采用雙重調節機制解決算力難調控問題。

1 相關背景知識介紹

1.1 PoW共識算法

區塊鏈本質上是一個分布式存儲系統，該系統主要任務是如何實現網絡中節點之間的共識。以比特幣和以太坊中的PoW為例。比特幣系統中的節點通過與或運算，尋找一個滿足特定條件的隨機數值（nonce），即可獲得本次區塊的打包權，廣播本輪需要記錄的數據，在全網節點驗證成功后再一起存儲區塊信息[12]；在以太坊系統中節點需要找到的不只是nonce值，還需計算Mix-Digest值，當找到滿足條件的nonce值后，會將計算出來的digest值賦給MixDigest，并存儲于區塊頭作為后續區塊驗證的條件，最后完成區塊信息廣播、全網驗證存儲。共識旨在防止惡意節點操作區塊鏈，從而保證數據的完整性。圖1、2分別為比特幣系統和以太坊系統中PoW共識算法工作框圖。

圖1 比特幣PoW共識算法工作框圖Fig.1 Block diagram of Bitcoin PoW consensus algorithm

根據圖1、2可知，兩個算法過程都是通過不停變化區塊頭及其附帶的隨機數作為輸入，再通過SHA-256計算，得到一個特定格式哈希值（即要求該哈希值的前p位為0）[13]。哈希值前置0的個數越多，代表區塊難度越大。其中，SHA-256加密算法主要用于完成交易數據的認證，保證交易數據的完整性以及數字簽名的驗證，保證了系統中交易數據不可篡改。SHA-256加密后得到一個前置p位為0的256位哈希值，則其解空間為2256。以不變的SHA-256算法的解空間來應對算力不斷增加的高速計算機乃至量子計算機，將無法保證PoW算法的安全性。

1.2 模糊傳遞閉包陣

在1965年，美國控制論專家Zadeh教授發表了《Fuzzy Sets》[14]一文；為模糊數學奠定了基礎。這一開創性的工作在軟、硬科學中為提高數學適用性開辟了廣闊途徑。其中本文用到的模糊傳遞閉包陣等相關知識定義如下[15]。

定義1r ij∈[0,1](i=1,2,…,m;j=1,2,…,n)，矩陣R=(r ij)m×n稱為m×n階的模糊矩陣。

定義2m=n且RT=R時，R為模糊對稱矩陣。

定義3包含R而又被任一包含R的傳遞矩陣所包含的傳遞矩陣，稱為R的傳遞閉包t(R)。計算t(R)的過程采用乘法公式：

其中“°”表示軟代數計算算子。Q表示n×n階模糊矩陣，R表示n×n階模糊矩陣，S表示兩個模糊矩陣的乘積，qik表示模糊矩陣Q的元素，r kj表示模糊矩陣R的元素，通過公式（1）得到兩個矩陣的相乘矩陣，再通過冪算法公式：

求得R的模糊傳遞閉包陣t(R)，其中：

并具有特性：

定理1求t(R)過程經過n4次的取∨和∧運算。

證明R 2=R°R?(s ij)n×n，其中1,2,…,n;j=1,2,…,n)。

（1）對于固定i,j=1,2,…,n：q ik∧r kj為n次∧運算；

（2）對于i=1,2,…,n時，則共有n2次∧運算；

（3）對于k=1,2,…,n時，共有n次取∨運算；

綜上三點可知則對于公式（1）的矩陣乘法運算可知R°R共有n×n2=n3次(∨,∧)運算。（4）通過公式（2）和（3）可知，求t(R)過程共有n次矩陣相乘運算。

綜上四點可知求t(R)模糊傳遞閉包陣有n×n3=n4次運算，證畢。

2 FRMH算法設計

隨著計算機運算速度的不斷提升，以不變的解空間應對高速計算機，理論上PoW的加密算法終將被破解。本文的新共識算法則引入了模糊傳遞閉包陣與哈希加密結合實現二次加密、再通過隨機數碰撞得到滿足條件的哈希值，來提升共識算法的安全性。本創新算法命名為模糊隨機碰撞工作量證明共識算法，又稱FRMH共識算法。

FRMH共識算法是利用種子和區塊頭哈希作為輸入、再操作隨機數獲得滿足難度且通過驗證的區塊進而完成整個算法。其中種子由上一區塊中的n、p、H構成，n為模糊傳遞閉包陣的階數、p為哈希值前置0的個數、H為上一區塊隨機數的值。FRMH共識算法主要包括：構造矩陣、運算矩陣、工作生成、工作驗證四個階段。

2.1 構造矩陣

FRMH共識算法的技術創新是首次將模糊傳遞閉包陣引入到共識算法。為了得到滿足要求的傳遞閉包陣，首要任務則是構造出一個n階模糊對稱陣。主要步驟如下：

（1）生成模糊對稱陣

由種子生成一個行列向量線性無關的n階模糊對稱陣R。

（2）求R的模糊傳遞閉包陣

通過上文中的公式（1）和（2）計算得到R的模糊傳遞閉包陣t(R)

此處求得傳遞閉包矩陣t(R)是單向不可逆過程，符合區塊鏈哈希加密正向快速、逆向困難的特點。

2.2 運算矩陣

通過S加密算法對公式（2）求得的模糊傳遞閉包陣t(R)進行加密運算，得到一個32字節長度的值f，其中：

2.3 工作生成

使用與運算矩陣階段相同的S加密算法對f和區塊頭進行加密運算，也得到一個長度為32字節的值hf，其中：

2.4 工作驗證

驗證節點是否完成工作，就是對節點的工作價值和區塊難度進行比較。由于FRMH共識算法中使用的S加密算法為SHA256加密算法，節點工作驗證則是判斷hf的256位哈希值前置0的個數是否等于種子中p值。如若不相等表示工作驗證不成功，則將工作生成階段S加密運算后生成的nonce值賦予H，開始新一輪的計算過程。驗證成功后，節點則將在其他人廣播之前廣播該區塊。

2.5 解空間

FRMH共識算法在運算過程中分為求解模糊傳遞閉包陣和哈希運算兩個過程。

（1）求傳遞閉包陣

公式（1）是冪算法求t(R)的中間過程。通過定理1可知此過程計算次數為n4，則此過程的解空間為n4。

（2）加密運算

加密運算過程采用SHA256加密算法對區塊頭和模糊傳遞閉包陣加密值進行運算，則其解空間為2256。

綜上兩個步驟計算結果，得到FRMH共識算法解空間為n4×2256。

2.6 難度調節

FRMH共識算法通過模糊傳遞閉包矩陣的階數n和哈希值前置0的個數p對區塊難度進行調節。本實驗硬件采用4核8線程的Intel Core i7-7700HQ處理器，8 GB內存的硬件平臺。通過搭建gen私鏈得到如圖3所示的算力模擬曲線。

圖3 算力測試模擬曲線Fig.3 Simulation curve of computing power test

圖中模糊矩陣的階數n和哈希值前置0的個數p是隨算力的大小自動調節，分為線性調節和幾何調節。主要分為以下幾種情況。

（1）當p＜256時

①線性調節：

②幾何調節：

（2）當p=256時

①線性調節：

②幾何調節：

其中α為難度系數，通過α=10÷(t-t0)計算（t0=上一區塊時間，t=本區塊時間）。

2.7 FRMH算法實現

（1）根據FRMH共識算法的4個階段構建出算法框架圖，如圖4所示。

圖4 FRMH算法框架Fig.4 FRMH algorithm framework

根據圖1和圖2兩個算法框圖可知，FRMH共識算法在組裝區塊頭時相對于PoW共識算法增加了變量矩陣階數n；運算過程中增加了對矩陣的計算。FRMH共識算法的難度調節是根據雙重調節機制進行的，即同時改變n（n可無窮大）、p（最多256位）值；而PoW共識算法則是根據最新2 016個區塊的出塊時間調節難度，即只改變p值。但FRMH共識算法引入的變量n，n的變化體現了對高算力調控的優勢。

圖2 以太坊PoW共識算法工作框圖Fig.2 Ethereum PoW consensus algorithm working block diagram

（2）go語言實現FRMH共識算法構造矩陣、運算矩陣、工作生成3個過程，如算法1～3所示。

算法1構造矩陣

Input：n、p、H-a byte array of 64

Output：M-ann-order matrix

InitializeN=int(n)

InitializeP=int(p)

M:=InitMatrix(N,N)

fori=1;i＜=N;i++{f

orj=i;j＜=N;j++{

if(i==j){//生成模糊矩陣主對角元素

M.Set(i,j,1)

}else{//不滿足條件重新生成模糊矩陣

xx:=GetElement(N,P,nonce,i,j)

M.Set(i,j,xx)

}

}

}

fori=1;i＜=N;i++{//生成模糊矩陣上下三角元素

forj=i+1;j＜=N;j++{

M.Set(j,i,M.Get(i,j))

}

}

count:=int（math.Log2（float64（N）））；//模糊矩陣計算

Fori=0;i＜=count+1;i++

M=FMultiply(M,M);

returnM；

算法2運算矩陣

Input：matrixString is the string converted byM

Output：32-byte cryptographic Hash ofM

matrixString：=M.ToString()//獲取矩陣字符串

f:=S（matrixString）

returnf；

算法3工作生成

Input：fhash and blockHead are 256-byte strings

Output：hfis a 256-bit Hash value

fhash:=f.ToString（）//得到矩陣的散列

hf=S（fhash+blockHead）

returnhf；

（3）針對FRMH共識算法解空間問題，當n=6時，FRMH共識算法解空間為64×2256，PoW共識算法解空間為2256，FRMH共識算法是PoW共識算法的1 296倍，大幅度提高了區塊鏈的安全性。

3 FRMH算法評估

（1）FRMH共識算法大幅度地提高了區塊鏈的安全性能

由表1可知比特幣和以太坊算法都是運用哈希加密算法，解空間為2256，其計算碰撞需要248年[16]，一般的普通電腦要破解其加密算法幾乎是不可能的，這就是區塊鏈至今未被攻破的原因。但是1臺量子計算機約相當于105臺普通電腦的算力[17]，如用量子計算機來破解哈希加密算法完全沒有問題。量子計算機的出現將使得哈希加密算法失效，現有的區塊鏈技術就失去了意義[18]。而FRMH共識算法的雙重加密算法解空間為n4×2256，大幅度提高了區塊鏈系統的安全性，且隨著n的增大，其安全性能呈幾何級數的增長。

表1 FRMH算法與主流共識算法解空間比較Table 1 FRMH algorithm and mainstream consensus algorithm solution space comparison

（2）FRMH共識算法可抵抗高算力計算機的攻擊

由表2可知，比特幣和以太坊算法都是通過p值對區塊的計算難度進行調節，且調節范圍是0～256；FRMH共識算法通過模糊矩陣的階數n和哈希值前置0的個數p實現了雙重調節，其中，p的取值范圍是0～256，但n的取值范圍卻是無限的。量子計算機運算速度再快亦是有限的，從理論上講用無限抵抗有限總是可行的。

表2 FRMH算法與主流共識算法難度調節比較Table 2 FRMH algorithm and mainstream consensus algorithm difficulty adjustment comparison

4 結束語

共識機制是區塊鏈節點數據一致性的重要保證。現有的PoW共識算法存在安全性和高算力難調控兩個缺點。本文提出的基于模糊數學方法的FRMH共識算法解決了高算力計算機乃至未來量子計算機給區塊鏈帶來的安全性問題。

FRMH共識算法融入了模糊傳遞閉包陣等技術，通過模糊傳遞閉包陣階數的變化，將解空間提升為n4×2256，大幅度提高了區塊鏈的安全性；該算法采用雙重調節機制（線性調節與幾何調節），用無限抵抗有限，實現了可抗高算力計算機，乃至未來的量子計算機的攻擊。下一步，可以對FRMH共識算法進行優化設計研究，進一步改善gen鏈上的出塊時間問題，進而加快鏈上的交易速度，并將FRMH共識算法應用于更多的公有鏈，給區塊鏈發展帶來更大的空間。