[發(fā)明專利]一種基于FPGA的poseidon哈希算法的優(yōu)化方法

有效

• 申請(qǐng)?zhí)枺?/td>: 202210410309.2
• 申請(qǐng)日: 2022-04-19
• 公開（公告）號(hào): CN114745099B
• 公開（公告）日: 2023-04-04
• 發(fā)明（設(shè)計(jì)）人: 王偉
• 申請(qǐng)（專利權(quán)）人: 麥田云網(wǎng)（杭州）信息技術(shù)有限公司
• 主分類號(hào): H04L9/06
• 分類號(hào): H04L9/06;H04L9/32
• 代理公司: 成都慕川專利代理事務(wù)所(普通合伙) 51278
• 代理人: 馮琬茹

本發(fā)明公開了一種基于FPGA的poseidon哈希算法的優(yōu)化方法，所述方法包括如下步驟：在FPGA內(nèi)對(duì)poseidon算法參數(shù)及流程優(yōu)化和底層蒙哥馬利模乘優(yōu)化兩方面進(jìn)行優(yōu)化；其中在poseidon哈希算法參數(shù)及流程優(yōu)化中通過常量計(jì)算、矩陣計(jì)算、常量及矩陣選擇和算法流程優(yōu)化；在底層蒙哥馬利模乘優(yōu)化中將蒙哥馬利算法輸入值由標(biāo)準(zhǔn)值轉(zhuǎn)化為蒙哥馬利形式，并通過將模乘、冪模運(yùn)算中計(jì)算開銷大的除法運(yùn)算轉(zhuǎn)化為計(jì)算開銷小的移位和乘法，提高計(jì)算效率。基于FPGA實(shí)現(xiàn)了poseidon哈希算法，并對(duì)參數(shù)、算法流程等進(jìn)行了優(yōu)化，提高了算法效率，在硬件設(shè)備的支持下，可應(yīng)用于零知識(shí)證明、區(qū)塊鏈、分布式存儲(chǔ)計(jì)算等場(chǎng)景；基于FPGA實(shí)現(xiàn)了底層蒙哥馬利算法，并進(jìn)行了優(yōu)化，提高了大整數(shù)運(yùn)算效率。

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

本發(fā)明涉及一種哈希算法的優(yōu)化，具體涉及一種基于FPGA的poseidon哈希算法的優(yōu)化方法。

背景技術(shù)

用于密碼學(xué)的hash函數(shù)有嚴(yán)格的要求，單向性：從數(shù)據(jù)求散列值很容易，但不能倒推，或者倒推十分困難，理論上不可行。無(wú)相關(guān)性：要求在輸入有一點(diǎn)點(diǎn)改變的情況下，要產(chǎn)生完全不同的輸出，這樣，從散列值完全不能看出數(shù)據(jù)之間的相關(guān)性。唯一性：不能通過不同的數(shù)據(jù)產(chǎn)生相同的hash值，這里說的不能是基本上不能人為實(shí)現(xiàn)，也就是說概率極小，此特性也可以成為碰撞安全性。在分布式存儲(chǔ)領(lǐng)域中，要把大容量GB級(jí)的數(shù)據(jù)打散加密，這時(shí)要用到PoseidonHash算法。

Poseidon哈希可將若干個(gè)GF(p)中的元素映射為單個(gè)GF(p)中的元素，形如其中t為輸入個(gè)數(shù)，p為有限域的階數(shù)。由于零知識(shí)證明如ZKsnark、zkstark、bulletproof等使用了大量pedersen哈希、sha256等哈希算法以保證完整性，然而在證明及驗(yàn)證時(shí)效率較低，而poseidon哈希則基于傳統(tǒng)哈希設(shè)計(jì)方法(類SPN結(jié)構(gòu))，是有限域上較為高效的哈希算法，且支持零知識(shí)證明中使用的多數(shù)曲線(BN、BLS、Ed25519)。

Poseidon哈希可用于以下場(chǎng)景：零知識(shí)證明中的承諾函數(shù)，在該類協(xié)議中，秘密值通常通過承諾函數(shù)加密并生成零知識(shí)證明；將多個(gè)有限域中元素映射為一個(gè)元素或變長(zhǎng)哈希；用于merkle樹中葉子節(jié)點(diǎn)的存在性證明，如證明某個(gè)節(jié)點(diǎn)屬于某一個(gè)樹。

發(fā)明內(nèi)容

本發(fā)明所要解決的技術(shù)問題是目前在PFGA上進(jìn)行Poseidon哈希算法的運(yùn)算工作量巨大，現(xiàn)有的硬件水平無(wú)法跟上大規(guī)模的數(shù)據(jù)量運(yùn)算，需要優(yōu)化運(yùn)算方式，使得現(xiàn)有的PFGA能過處理，本申請(qǐng)文件目的在于提供一種基于FPGA的poseidon哈希算法的優(yōu)化方法，上述問題。

本發(fā)明通過下述技術(shù)方案實(shí)現(xiàn)：

一種基于FPGA的poseidon哈希算法的優(yōu)化方法，所述方法包括如下步驟：在FPGA內(nèi)對(duì)poseidon算法參數(shù)及流程優(yōu)化和底層蒙哥馬利模乘優(yōu)化兩方面進(jìn)行優(yōu)化；其中在poseidon哈希算法參數(shù)及流程優(yōu)化中通過常量計(jì)算、矩陣計(jì)算、常量及矩陣選擇和算法流程優(yōu)化；在底層蒙哥馬利模乘優(yōu)化中將蒙哥馬利算法輸入值由標(biāo)準(zhǔn)值轉(zhuǎn)化為蒙哥馬利形式，并通過將模乘、冪模運(yùn)算中計(jì)算開銷大的除法運(yùn)算轉(zhuǎn)化為計(jì)算開銷小的移位和乘法，提高計(jì)算效率。

目前Poseidon哈希主要由若干輪輪函數(shù)組成，輪函數(shù)主要包括三個(gè)部分：

1.AddRoundConstants，記為ARC()，即與常量相加；

2.SubWords，記為S-Box()或SB()，包含一個(gè)非線性變換；

3.MixLayer，記為M()，混淆函數(shù)，一般為一個(gè)常量MDS矩陣的乘積。

輪函數(shù)有兩種：Full?S-Box和Partial?S-Box，F(xiàn)ull?S-Box輪函數(shù)中每一輪各輸入均需計(jì)算S-Box值，即需要計(jì)算ARC()→SB()→M()完整過程，而Partial?S-Box每一輪只需計(jì)算一個(gè)輸入值的S-Box。

Poseidon哈希算法流程為：