(19)国家知识产权局 (12)发明 专利申请 (10)申请公布号 (43)申请公布日 (21)申请 号 202210410309.2 (22)申请日 2022.04.19 (71)申请人 麦田云网 （杭州） 信息技 术有限公司 地址 310000 浙江省杭州市余杭区仓前街 道鼎创财富中心 2幢1704室 (72)发明人 王伟　 (74)专利代理 机构 成都慕川专利代理事务所 (普通合伙) 51278 专利代理师 冯琬茹 (51)Int.Cl. H04L 9/06(2006.01) H04L 9/32(2006.01) (54)发明名称 一种基于FPGA的poseidon哈希算法的优化 方法 (57)摘要 本发明公开了一种基于FPGA的poseidon哈 希算法的优化方法， 所述方法包括如下步骤： 在 FPGA内对poseidon算法参数及流程优化和底层 蒙哥马利模乘优化两方面进行优化； 其中在 poseidon哈希算法参数及流程优化中通过常量 计算、 矩阵计算、 常量及矩阵选择和算法流程优 化； 在底层蒙哥马利模乘优化中将蒙哥马利算法 输入值由标准值转化为蒙哥马利形式， 并通过将 模乘、 幂模运算中计算开销大的除法运算转化为 计算开销小的移位和乘法， 提高计算效率。 基于 FPGA实现了poseidon哈希算法， 并对参数、 算法 流程等进行了优化， 提高了算法效率， 在硬件设 备的支持下， 可应用于零知识 证明、 区块链、 分布 式存储计算等场景； 基于 FPGA实现了底层蒙哥马 利算法， 并进行了优化， 提高了大整数运 算效率。 权利要求书1页 说明书7页 附图13页 CN 114745099 A 2022.07.12 CN 114745099 A 1.一种基于FPGA的poseidon哈希算法的优化方法， 其特征在于， 所述方法包括如下步 骤： 在FPGA内对poseidon算法参数及流程优化和底层蒙哥马利模乘优化两方面进行优化； 其中在poseidon哈希算法参数及流程优化中通过常量计算、 矩阵计算、 常量及矩阵选择和 算法流程优化； 在底层蒙哥马利模乘优化中将蒙哥马利算法输入值由标准值转化为蒙哥马利形式， 并 通过将模乘、 幂模运算中计算开销大 的除法运算转化为计算开销小的移位和乘法， 提高计 算效率。 2.根据权利 要求1所述的一种基于FPGA的poseidon哈希算法的优化方法， 其特征在于， 所述步骤中的常量计算采用的SPN结构中， 由于交换线性变换阶段和常量计算 都是线性的， 通过交换计算 顺序， 进行等 价转换。 3.根据权利 要求1所述的一种基于FPGA的poseidon哈希算法的优化方法， 其特征在于， 所述步骤中的矩阵计算中的交换线性变换阶段， 计算与MDS矩阵的乘积时， 使用多线程及并 行计算， 提高矩阵运 算效率。 4.根据权利 要求1所述的一种基于FPGA的poseidon哈希算法的优化方法， 其特征在于， 所述步骤中的算法流程优化时， 将poseidon哈希算法的输入定为11个256b it大整数， 输出 定为1个25 6bit大整数， 进行实现和优化， 算法流 程如下： S1： 将11个输入值扩充为12个25 6bit大整数； S2： 在12个输入值加前12个常量； S3： 进行4轮Full  S‑Box， 每轮Full  S‑Box包含12个指数运算， 12个加法运算， 以及矩阵 乘积， 返回12个大整数； S4： 进行57轮Partial  S‑Box， 每轮Partial  S‑Box包含1个指数运算， 1个加法运算， 以 及稀疏矩阵乘法， 返回12个大整数； S5： 进行3轮Full  S‑Box， 每轮Full  S‑Box包含12个指数运算， 12个加法运算， 以及矩阵 乘积， 返回12个大整数； S6： 进行最后一轮Ful l S‑Box， 包含12个指数运 算， 以及矩阵乘积， 返回12个大整数； S7： 输出第二个元 素， 为256bit大整数。 5.根据权利 要求1所述的一种基于FPGA的poseidon哈希算法的优化方法， 其特征在于， 所述步骤中的蒙哥马利算法包括模乘、 约减和幂模运算， 其采用的蒙哥马利算法输入值转 化为蒙哥马利形式后表 示为X＝xRmodN， 其中x为标准值， X为蒙哥马利表 示法， R为蒙哥马利 参数， mod为 求余函数。权　利　要　求　书 1/1 页 2 CN 114745099 A 2一种基于FPGA的pose idon哈希算法的优化方 法 技术领域 [0001]本发明涉及一种哈希算法的优化， 具体涉及一种基于FPGA的poseidon哈希算法的 优化方法。 背景技术 [0002]用于密码学的hash函数有严格的要求， 单向性： 从数据求散列值很容易， 但不能倒 推， 或者倒推十 分困难， 理论上不可行。 无相关性： 要求在输入有一点点改变的情况下， 要产 生完全不同的输出， 这样， 从散列值完全不能看出数据之间的相关性。 唯一性： 不能通过不 同的数据产生相同的hash值， 这里说的不能是基本上不能人为 实现， 也就是说概率极小， 此 特性也可以成为碰撞安全性。 在分布式存储领域中， 要把大容量GB 级的数据打散加密， 这时 要用到Poseido nHash算法。 [0003]Poseidon哈希可将若干个GF(p)中的元素映射为单个GF(p)中的元素， 形如 其中t为输入个数， p为有限域的阶数。 由于零知识证明如ZKsnark、 zkstark、 bulletproof等使用了大量pedersen哈希、 sha2 56等哈希算法以保证完整性， 然而在证明及 验证时效率较低， 而poseidon哈希则基于传统哈希设计方法(类SPN结构)， 是有限域上较为 高效的哈希算法， 且支持零知识证明 中使用的多数曲线(BN、 BLS、 Ed25 519)。 [0004]Poseidon哈希 可用于以下场景： 零知识证明中的承诺函数， 在该类协议中， 秘密值 通常通过承诺函数加密并生成零知识证明； 将多个有限域中元素映射为一个元素或变长哈 希； 用于merk le树中叶子节点的存在性证明， 如证明某个节点属于某一个树。 发明内容 [0005]本发明所要解决的技术问题是目前在PFGA上进行Poseidon哈希算法的运算工作 量巨大， 现有的硬件水平无法跟上大规模的数据量运算， 需要优化运算方式， 使得现有的 PFGA能过处理， 本申请文件目的在于提供一种 基于FPGA的poseidon哈希算法的优化方法， 上述问题。 [0006]本发明通过 下述技术方案实现： [0007]一种基于FPGA的poseidon哈希算法的优化方法， 所述方法包括如下步骤： 在FPGA 内对poseidon算法参数及流程优化和底层蒙哥马利模乘优化两方面进行优化； 其中在 poseidon哈希算法参数及流程优化中通过常量计算、 矩阵计算、 常量及矩阵选择和算法流 程优化； 在底层蒙哥马利模乘优化中将蒙哥马利算法输入值由标准值转化为蒙哥马利形 式， 并通过将模乘、 幂模运算中计算开销大的除法运算转化为计算开销小的移 位和乘法， 提 高计算效率。 [0008]目前Poseido n哈希主要由若干轮 轮函数组成， 轮函数主 要包括三个部分： [0009]1.AddRoundCo nstants， 记为ARC()， 即与常量相加； [0010]2.SubWords， 记为S ‑Box()或SB()， 包 含一个非线性变换； [0011]3.MixLayer， 记为M()， 混淆函数， 一般为 一个常量MD S矩阵的乘积。说　明　书 1/7 页 3 CN 114745099 A 3