[發(fā)明專利]一種實(shí)現(xiàn)Equihash算法的芯片及方法

在審

• 申請?zhí)枺?/td>: 202111279378.6
• 申請日: 2021-11-01
• 公開（公告）號: CN113704362A
• 公開（公告）日: 2021-11-26
• 發(fā)明（設(shè)計(jì)）人: 劉明;汪福全
• 申請（專利權(quán)）人: 中科聲龍科技發(fā)展（北京）有限公司
• 主分類號: G06F16/27
• 分類號: G06F16/27;G06F16/22;G06F5/16
• 代理公司: 北京安信方達(dá)知識產(chǎn)權(quán)代理有限公司 11262
• 代理人: 栗若木

一種實(shí)現(xiàn)Equihash算法的芯片及方法；所述芯片包括：pingpong結(jié)構(gòu)數(shù)據(jù)存儲器，包括ping存儲器和pong存儲器；處理模塊，用于在對每個(gè)nonce進(jìn)行處理的過程中，交替使用第一存儲器和第二存儲器存儲本輪生成的中間數(shù)據(jù)和中間序號，和/或，使用上一輪存儲所使用的存儲器讀取上一輪生成的中間數(shù)據(jù)和中間序號，并順序?qū)懭胱x取的中間序號；第一存儲器為ping存儲器，第二存儲器為pong存儲器；或第一存儲器為pong存儲器，第二存儲器為ping存儲器；本申請實(shí)施例可以使得Equihash算法按照流水線方式實(shí)現(xiàn)，提高了Equihash算法的處理效率。

技術(shù)領(lǐng)域

本文涉及加密算法與芯片設(shè)計(jì)領(lǐng)域，尤其涉及一種實(shí)現(xiàn)Equihash算法的芯片及方法。

背景技術(shù)

區(qū)塊鏈作為一個(gè)共享數(shù)據(jù)庫，存儲于其中的數(shù)據(jù)或信息，具有“不可偽造”、“全程留痕”、“可以追溯”、“公開透明”、“集體維護(hù)”等特征。基于這些特征，區(qū)塊鏈技術(shù)奠定了堅(jiān)實(shí)的“信任”基礎(chǔ)，創(chuàng)造了可靠的“合作”機(jī)制，具有廣闊的運(yùn)用前景。Equihash算法是由盧森堡大學(xué)的安全、可靠性和信任跨學(xué)科中心（SnT）開發(fā)的一種以內(nèi)存為導(dǎo)向的應(yīng)用于區(qū)塊鏈中的工作證明算法，其理論依據(jù)是一個(gè)著名的計(jì)算法科學(xué)及密碼學(xué)問題：廣義生日悖論問題；Equihash算法的實(shí)現(xiàn)過程是先構(gòu)造輸入條件，即區(qū)塊鏈中當(dāng)前最后一個(gè)區(qū)塊的區(qū)塊頭和各項(xiàng)參數(shù)，然后將輸入條件轉(zhuǎn)化成廣義生日悖論問題的一般形式，解析該問題并對獲得的解進(jìn)行難度判斷，同時(shí)滿足算法條件和難度條件則判定求解成功，完成工作證明，生成新的區(qū)塊；否則調(diào)整參數(shù)重新運(yùn)算。

Equihash(n，k)算法具有其鮮明特點(diǎn)：它一方面是記憶性的，另一方面很容易驗(yàn)證。廣義生日悖論就是在N個(gè)n比特的數(shù)據(jù)樣本中找到2^k個(gè)碰撞的數(shù)據(jù)樣本，數(shù)據(jù)樣本數(shù)目N＝2^n/(k+1)+1，數(shù)據(jù)樣本X_{1 ..N}由區(qū)塊頭block header和nonce產(chǎn)生；其中nonce是一個(gè)只被使用一次的任意或非重復(fù)的隨機(jī)數(shù)值。

在一個(gè)示例中，block header包括4個(gè)字節(jié)的區(qū)塊版本號nVersion，它指示遵從哪個(gè)區(qū)塊驗(yàn)證規(guī)則；32字節(jié)的hashPrevBlock，它表示前一區(qū)塊的區(qū)塊頭block header；32字節(jié)的 hashMerkleRoot，該字段允許調(diào)整，通過對包含進(jìn)區(qū)塊的交易進(jìn)行增刪，或改變順序，或者修改Coinbase交易的輸入字段而產(chǎn)生變化；32字節(jié)的hashReserved，這是保留字段；4個(gè)字節(jié)的nTime，一般取機(jī)器開始哈希header時(shí)候的Unix時(shí)間戳；4個(gè)字節(jié)的nBits，它由全網(wǎng)算力決定，每產(chǎn)生一個(gè)新塊都調(diào)整一次難度；32個(gè)字節(jié)的nNonce，提供2²⁵⁶種可能取值，通過改變nNonce來改變block header以最終產(chǎn)生一個(gè)小于或等于目標(biāo)target的哈希。所以hashMerkleRoot和nNonce是發(fā)揮自由度的兩個(gè)字段。

一個(gè)有效的Equihash解應(yīng)該滿足下列條件： A：廣義生日悖論條件即2^k個(gè)樣本異或結(jié)果為0；B：對于第r輪(0rk)2^k個(gè)數(shù)據(jù)樣本按字典順序排列后每2^r個(gè)樣本數(shù)據(jù)異或后有rn/(k +1)個(gè)導(dǎo)0(leading zeros)。

為了找到有效的Equihash解，一般采用Wagner算法：在產(chǎn)生N個(gè)X_i后，對X_i進(jìn)行排序，找到所有第一個(gè)n/(k+1)比特碰撞的X_i、X_j，然后保存他們之間的異或結(jié)果X_ij；接著對所有X_ij排序，找到下一個(gè)n/(k+1)碰撞的X_ij、X_mn；重復(fù)上述過程共k-1輪，直到只有2n/(k+1)比特沒有碰撞。最后一步，找到最后2n/(k+1)比特碰撞的結(jié)果X，即最終Equihash的解。