BLAKE2b算法優化及OpenCL實現

杜飛飛,張德學,王佃濤,郭曉超

1(山東科技大學 電子信息工程學院,山東 青島 266590)2(中國科學院 計算技術研究所,北京 100190)3(中國科學院大學,北京 100190)

1 引 言

Equihash算法是主流數字貨幣zcash采用的一種工作量證明算法[1,2],它由 Alex Biryukov 和 Dmitry Khovratovich 聯合發明,其理論依據是一個著名的計算機科學及密碼學問題—廣義生日悖論.Equihash算法具有去中心化的優勢,但同時存在運算量大的問題.Equihash算法計算過程中需要一種產生固定長度值的哈希算法—BLAKE2b算法[3],BLAKE2b算法相比同類的哈希算法,速度更快,具有可并行實現的設計結構.針對可并行實現的結構,現有兩大主流硬件實現方法:G/2結構和1G結構[4,5].兩種結構可根據硬件的特點進行調整.大多數學者采用Xilinx的Virtex實現BLAKE系列算法,文獻[6-9]對各個版本實現BLAKE2b算法的頻率與吞吐率進行分析.硬件實現BLAKE系列算法的研究已有很多年,2010年,文獻[6,7]提出了BLAKE-256作為SHA-3候選算法在Aumasson 1G并行結構基礎上增加寄存器,構成流水線結構,提升吞吐率,在Altera Stratix III FPGA芯片上運行頻率為46.97MHz,但未將整體算法在硬件上實現;同年,Karri等人提出BLAKE-128利用G/2結構以及移位寄存器的ASIC實現[8],頻率和吞吐率分別為67.5MHz,281.61Mbps,但與Xilinx Virtex-4 FPGA實現相比,性能并未提升;2014年,Nuray等人[9]在Virtex-6 FPGA上利用G/2并行結構的流水線實現BLAKE-512,其頻率為329 MHz,吞吐率250Mbits/s,其頻率雖然有較大提升,但吞吐率有所下降.

相比于傳統的人工設計編寫RTL代碼實現BLAKE2b算法,本文采用Intel最新的FPGA SDK for OpenCL技術,針對此技術特點對BLAKE2b算法進行優化,省略SIGMA操作,減少CPU和與內存之間交互訪問時間;利用loop展開技術以及pipeline,減少數據依賴.面向FPGA實現優化后的OpenCL代碼,將OpenCL代碼直接編譯為硬件配置文件,并在Terasic DE5-Net FPGA開發板上實現.

2 BLAKE2b算法簡介及應用于 Equihash算法中的優化

BLAKE2b應用于Equihash算法如圖1所示,區塊頭數據和一個隨機數nonce以及輸入參數i作為BLAKE2b參數,計算生成220個200位的哈希數據,利用廣義生日算法對哈希數據進行異或碰撞求解.若通過驗證條件,則求解成功,否則重新開始計算.BLAKE2b單次計算可以生成512位哈希數據,可分為2組200位數據,Equihash共需219次BLAKE2b運算,運算量較大.

2.1 BLAKE2b算法簡介

BLAKE2b可處理0～2128間任意字節長度的數據,按128 字節分組,不足128字節時補零填充,運算后可產生1～64 字節長度的哈希數據,具體參見BLAKE2b算法文獻[3],本文僅對改進部分做必要說明.

1) G(a,b,c,d)函數定義如式(1),8個G函數操作,執行12輪,如式(3).

(1)

其中mσr為SIGMA表(10×16 個常量)中的值,r(1

p=σr mod10(2i)q=σr mod10(2i+1)

(2)

其中σr mod10是SIGMA表中的第rmod10行,σr mod10(2i)為該行第2i個值.

G0=(V0,V4,V8,V12);G1=(V1,V5,V9,V13);G2=(V2,V6,V10,V14);G3=(V3,V7,V11,V15);G4=(V0,V5,V10,V15);G5=(V1,V6,V11,V12);G6=(V2,V7,V8,V13);G7=(V3,V4,V9,V14);

(3)

其中V0,…,V14,V15為存儲G函數計算過程的存儲變量,即將每次計算的結果都存儲到這16個中間變量,用于每一輪的計算.

2) 最終輸出值,可參考文獻[3]中附錄A.1

(4)

2.2 BLAKE2b應用于Equihash算法中的優化

Equihash算法中,用BLAKE2b處理長度為144 字節的數據塊,并在服務器端給定的隨機數基礎上,按序列生成220組200位哈希數據.BLAKE2b處理的數據具體格式如圖2所示,108字節的區塊頭數據,32字節的隨機數nonce,4字節的用戶輸入值i.

圖2 輸入數據格式Fig.2 Format of input data

將32 字節的nonce值分成20+12字節兩部分,先計算108+20=128字節輸入數據,這部分只需計算一次;依次取i為0～220-1.

nonce是任意32字節隨機數,可進一步優化,限定其低12字節全為0,將12字節0值與4字節i組合,同時補齊112字節的0值,構成下一組128 字節的數據,以8字節為單位劃分為16個信息塊mσr,即是m0=0,m1=i,其余m2～m15均為0.如圖3所示:

圖3 優化后數據組合Fig.3 Optimized data combination

本文將mσr(2i)、mσr(2i+1)作為G函數的新增輸入參數,分別賦值給x、y,G函數重新定義為mix(a,b,c,d,x,y)函數,公式如下:

a=a+b+x;d=(d^a)>>32;c=c+d;b=(b^c)>>24;a=a+b+y;d=(d^a)>>16;c=c+d;b=(b^c)>>63;

(5)

采用mix函數實現G運算后,每一輪中的8個G操作需要展開調用mσr,按調用順序給定不同的mσ(2i)和mσ(2i+1)作為x、y參數值,此時可將mσr提前計算,并編碼到源程序中.例如在第一輪、第二輪計算中8個mix函數定義如下:

//round1

mix(V0,V4,V8,V12,0,m1);mix(V1,V5,V9,V13,0,0);

mix(V2,V6,V10,V14,0,0);mix(V3,V7,V11,V15,0,0);

mix(V0,V5,V10,V15,0,0);mix(V1,V6,V11,V12,0,0);

mix(V2,V7,V8,V13,0,0);mix(V3,V4,V9,V14,0,0);

//round2

mix(V0,V4,V8,V12,0,0);mix(V1,V5,V9,V13,0,0);

mix(V2,V6,V10,V14,0,0);mix(V3,V7,V11,V15,0,0);

mix(V0,V5,V10,V15,m1,0);mix(V1,V6,V11,V12,0,0);

mix(V2,V7,V8,V13,0,0);mix(V3,V4,V9,V14,0,0);

相比于式(1)(2)(3)調用SIGMA置換操作,當采用上述nonce低12字節全取0優化時,m0、m2～m15均為0,可直接用0作為參數調用mix函數,編譯器可以生成優化代碼.采用本優化方法,可優化掉SIGMA置換操作,BLAKE2b計算一次減少12×2次CPU對內存的訪問,減少運行時間.

3 Intel FPGA SDK for OpenCL技術特點及BLAKE2b優化實現

3.1 Intel FPGA SDK for OpenCL技術特點

在FPGA上實現OpenCL代碼時,FPGA一般只含1個或少數幾個計算單元,但可采用流水線技術提高吞吐率.當數據有依賴時,FPGA可利用流水線技術隱藏等待周期.

利用loop 展開及pipeline技術,結合算法特點,將循環部分無數據依賴部分展開為流水線結構或者并行計算結構,提升計算效率.

不同于直接利用RTL代碼實現定制硬件結構,采用將OpenCL技術綜合為硬件的技術,訪存的頻率高低會影響FPGA計算效率,均衡全局內存和局部內存的訪問效率,才能達到更好的吞吐量.CPU對global memory 訪問次數越少,則運行性能更好.

3.2 BLAKE2b優化實現

如圖4所示,本文將BLAKE2b算法部分編寫成內核代碼,同時編寫了主機端代碼.主機端程序主要包括A、B、C、D、E五部分;內核部分主要包括常量定義和內核函數定義.內核函數外部聲明8個IV常量,內核函數包括讀取IV值、12輪mix函數、Hash值存儲三部分,各部分作用如下:

圖4 優化后BLAKE2b的OpenCL實現Fig.4 OpenCL implementation of optimized BLAKE2b

1) 讀取IV值:由于IV定義為內核函數外部local memory常數,減少CPU的外部訪存時間.

2) 12輪mix函數:Equihash算法中需要220組200位哈希值,各組數據是無依賴的,因而可以并行計算,根據開發板資源,本文將“#pragma unroll N”中N設置為16,Intel離線編譯器會自動將無依賴數據進行展開實現.

3) Hash值存儲:將hash定義為global memory動態指針數組,存儲哈希值.

本文修改了BLAKE2b算法區塊頭及、nonce數據以及輸入數據i的組合方式,略去SIGMA置換部分,減少了221次SIGMA置換,即減少了CPU對global memory訪問時間.BLAKE2b算法每輪間有數據依賴,12輪需串行計算,同一輪中的8 個G運算,前后4個之間無數據依賴,可并行計算.明確BLAKE2b算法中的數據依賴關系后,可以通過在OpenCL代碼中手工展開每輪前后4個G運算,指導離線編譯器生成如圖5所示的流水線結構.系統在每一輪構建2級流水線,分別并行計算前后4個G運算,12輪共24級,流水計算i～i+23組數據.

圖5 流水線結構Fig.5 Structrue of pipeline

4 實驗結果

本文采用友晶公司的DE5-Net以及Intel 系列的CPU實現了優化前和優化后BLAKE2b算法,分別計算了220組哈希值,共輸出1G bits哈希數據.Intel i5/i7 CPU有睿頻技術,表1中時鐘頻率是測試時CPU-Z軟件顯示的實際頻率.所測試代碼沒有利用多線程技術,測試結果是單核運行結果.最終測試結果如表1所示.

表1 測試結果
Table 1 Results

測試平臺優化前優化后時鐘頻率(MHz)時間(s)吞吐率(Gbits/s)時鐘頻率(MHz)時間(s)吞吐率(Gbits/s)Inteli5-3210MCPU28931680.0060289613.160.0760Inteli7-8750HCPU3993114.920.006940927.0610.1416IntelXeonE5-2670C2CPU349055.3750.018126001.880.5319DE5-Net///226.30.03231.47

BLAKE2b算法優化前,進行一次BLAKE2b計算需要進行12×2輪的SIGMA表常量的置換,因Equihash算法需要219次BLAKE2b算法的計算,因此需要訪問219×12×2次SIGMA常量表,優化前BLAKE2b算法在Intel系列CPU實現,其中Intel Xeon E5-2670 C2 CPU運行時間最短,為55.375秒;在Intel i5處理器上運行時間最長為168秒.優化BLAKE2b算法后,本文將SIGMA置換表略去,重組輸入數據,略去SIGMA置換表中數據,預計算mσr值,寫入mix函數參數中,減少了219×12×2次對常量內存的訪問,優化后的算法在Intel系列CPU上運行,運行時間均有不同程度的減少.將優化后的BLAKE2b是我OpenCL代碼面向硬件編譯時,針對DE5-Net開發板以及BLAKE2b特點,每一輪8G函數展開為兩級流水線結構,即由8個時間單位縮短為2個,提升了75%的計算效率.DE5-Net運行時間最短,為0.032秒,吞吐率為31.47 Gbits/s.

分析以上測試結果,采用略去SIGMA置換,減少了本地訪存操作,利用流水線結構,縮短了運行時間;在優化掉SIGMA操作后,既不改變輸出數據,又滿足Equihash算法需求.

5 結 語

Equihash算法中需要用BLAKE2b算法生成220組200 位哈希值,計算效率很重要.可以通過優化輸入數據模式,利用構造出的大量零值數據和預編碼,省略SIGMA計算操作.在面向FPGA實現時,利用循環展開以及流水線等技術,實現計算過程并行化,提高了吞吐率,實驗結果表明,優化后BLAKE2b算法運行時間大大縮短,在DE5-Net FPGA板卡上吞吐率可達E5-2670 C2 CPU的59倍,可提高Equihash算法求解速度.