Abstract

如SNARK、STARK、Bulletproof等证明系统的许多应用场景中，通常需要证明某个哈希函数的原像的知识，此类证明通常开销很大，Zcash加密货币中，币的所有权的零知识证明会涉及到SHA256的计算，该过程会引入巨大的计算开销

本文的主要目标是提出了一个模块化框架和一个密码学Hash函数，称为Poseidon，该Hash函数在$GF(p)$上工作，且对于消息中的每个比特而言，需要的约束数量为Pedersen Hash的1/8

本文的构造不仅可以表示为电路，还可以使用特制的多项式，以在不同的证明系统提升性能，本文的方案在Bulletproofs中以不到一秒钟的时间内使用Merkle树完成了1 out of a billion的成员证明

1 Introduction

计算完整性证明系统多用于在短时间内以零知识的方式进行证明，现阶段出现了许多此类协议，要求一方证明某个秘密值是由某个初始种子衍生而来，或者某个元素是一个大的集合的成员。基于累加器的解决方案$[CL02,CKS09]$和代数Schnorr证明非常复杂，很容易出错，同时此类方案需要可信的设置，在证明部分语言中受到限制，效率也比较差

另一种方法是使用加密哈希函数来表示秘密的派生过程，并通过在正确选择的Merkle树中解释承诺来证明集合成员资格，此类基于哈希的协议需要计算完整性证明系统，该系统也适用于任意算术电路。但是为了确保协议有效，必须在合理的时间内生成和验证证明，因此要求采用的Hash函数的开销要尽可能的小

本文的目标是设计一系列的Hash函数，在R1CS中式最优的，同时在AET矩阵中也有不错的表现，同时函数还可以支持不同有限域

因此本文提出了一个$GF(p)$上的Hash函数族，称为Poseidon，该函数族的中间置换称为$POSIDEN^\pi$，其设计策略基于HADES$[GLR+20]$，该策略本质上是基于具有$t$个单元的SPN结构，结构中包含仅作用域部分状态的partial round（partial round中只使用一个S盒，其他round中使用所有的$t$个S盒，这么做的目的是减少开销）

本文的Hash函数为容量（capacity）保留了若干个S盒的元素（比特数量为安全参数的2倍），其余S盒元素用于速率（rate），函数中置换的宽度取决于实际应用（对长消息进行Hash时为1280比特，若用于Merkle Tree的话宽度会更灵活）

基于R1CS和AET的POSEIDON约束数量如表1所示（以安全级别划分），其中BLS表示BLS12-381曲线，BN表示BN254曲线，Ed表示Ristretto群

2 The POSEIDON Hash Function

按照惯例，先介绍一下本文的一些符号表示，POSIDON Hash将域上的串映射到域上的另一个串

  • $\mathbb F_p$：表示素数域，$p$为一长度为$n$比特的素数
  • $\mathbb F^*_p \rarr \mathbb F^o_p$：其中$o$表示输出长度（通常$o=1$）

此外，记$N=n\cdot t$

2.1 Sponge Construction for $POSEIDON^\pi$

海绵结构于由$[BDP08]$提出，其是一种建立在内部置换上的结构，可用于实现加密、认证、散列等各种密码学原语

海绵结构通常由两个参数定义：速率（rate）和容量（capacity），分别记为$r,c$，速率决定了海绵结构的吞吐量，而容量则和结构的安全性息息相关（举个例子，如果将内部置换的宽度固定为$N$比特时，需要权衡速率和容量之间的关系，以同时确保安全性和吞吐量）

一个简单的海绵结构如图1所示

不难看出，海绵结构利用四个$r$比特的消息$m_1,m_2,m_3,m_4$来计算，并得到两个$r$比特的Hash值$h_1,h_2$

海绵结构的安全性一定程度上受到其其内部的$N$比特置换性质的影响，若将该置换视为随机选择的置换，则在至多$2^{c/2}$次调用中，海绵结构与随机预言机之间是无差别的，因此一个基于海绵结构的Hash函数，若其容量为$c$，则其可以提供$2^{c/2}$比特的抗碰撞性和（第二）抗原像性

本文采用$POSEIDON^\pi$来实例化海绵结构，给定大小为$N$的置换和期望的安全级别$s$，$POSEIDON^\pi$每次可以对$r=H-2s$比特进行置换，之后需要选择$POSEIDON^\pi$的内部置换轮数来确保置换在$2^M$次请求中的安全性（$M$表示期望的安全级别），因此本文令容量为$2M$，并以POSEIDON-M表示方案可提供$M$比特的抗碰撞性和抗原像攻击

对于$POSEIDON^\pi$的海绵结构而言，本文提供了POSEIDON的多个不同实例以适用于不同的场景

2.2 The HADES Design Strategy for Hashing

在密码学中，置换通常会包含一个轮函数，且该轮函数会重复调用多次，其目的是确保置换的输出和随机置换几乎一致，通常置换过程会采用同一个轮函数，这样可以确保破坏输入的对称性和输入的某些结构特性

在HADES中，考虑同一构造的不同轮函数，也即考虑将全S盒层的轮函数与partial S盒层的轮函数混用，因为全S盒在ZKP和部分应用中的开销很大，但是其可以提供很强的抗统计分析性质，partial层的开销相对较小，但是partial的轮函数可以提供与全S盒的轮函数相同的抗代数攻击性质

HADES的设计策略如下：初始时包含$R_f$轮，此时状态会作用于所有的S盒，$R_f$轮后再进行$R_P$轮，但是每轮仅包含一个S盒，其余状态未作用S盒的状态通过一个非线性层（也即以一个恒等函数来代替缺失的S盒），最后再进行一次$R_f$轮的全S盒，具体的结构图如下所示

而POSEIDON的每个轮函数由下列三个部分组成

  • $ARC$：轮常数加，记为$ARC(\cdot )$
  • $SB$：S盒，记为$S(\cdot )$
  • $M$：混合层，为一个线性层，该层中状态会与一个$t\times t$的MDS矩阵相乘，记为$M(\cdot )$

三个组成部分以$ARC\rarr SB\rarr M$的方式一次执行，共执行$R$轮

ARC和M在每一轮中相同，但是SB在每一轮中不一定相同，和前面提到的一样，最初的$R_f$轮和最末的$R_f$轮使用所有的S盒，而中间的$R_P$轮每轮只使用1个S盒和$t-1$个恒等函数

HADES的设计思路具体可以看$[GRL+20]$

尽管可以用全S盒的轮来代替中间的partial轮，从而提高方案的安全性，但是本文的目的是优化Hash函数的计算开销，因此需要用partial轮来代替全S盒轮，但是这么做必然会损失一定程度的安全性

2.3 The Permutation Family $POSEIDON^\pi$

由于本文的方案主要在大的素域上使用，因此要求$POSEIDON^\pi$的输入字$t\geq 2$​

$POSEIDON^\pi$的构造组件如下

  • S盒：本文的方案主要关注两个S盒

$\alpha$幂-S盒：定义为$S(x)=x^\alpha$，其中$\alpha$为满足$gcd(\alpha,p-1)=1$的最小正整数，对应的置换记为$x^\alpha -POSEIDON^\pi$，当$\alpha=5$时，置换适用于BLS12-381和BN254两条曲线

逆S盒：定义为$S(x)=x^{-1},S(0)=0$，对应的置换记为$x^{-1}-POSEIDON^\pi$

  • 线性层：这一层需要用到一个$t\times t$的MDS矩阵（Maximum Distance Separable matrix），其中$2t+1\leq p$，MDS的构造和安全性分析可以看原文及其附录B

3 Applications

POSEIDON可用于各类ZKP友好的Hash中，比如下面这几类

  • POSEIDON可用于协议中的承诺部分，效率比Pedersen承诺更高，且适用于签名
  • 对多元素对象进行Hash
  • 用POSEIDON Hash构建Merkle Tree
  • 在集成加密方案（Intergrated Enc Scheme）中进行可验证加密

部分协议中已经采用了POSEIDON Hash，比如Filecoin中用于构建Merkel Tree证明，Dusk Network中用于构建类似于Zcash的安全交易协议等等

4 Concrete Instantiations of $POSEIDON^\pi$

诸如Groth16，Bulletproof等ZKP协议都用到了椭圆曲线配对，这些协议主要采用BLS12-381，BN254，Ed25519三条曲线

4.1 Main Instances

本部分给出了基于素域的$POSEIDON^\pi$置换，非素域情况可以看原文的附录

本文的$POSEIDON^\pi$置换中，S盒选择$\alpha=5$，安全参数为80和128时对应的容量为255比特，本文考虑$t=3,t=5$两种宽度，分别对应于2-1和4-1压缩函数

安全参数对应的轮数如表2所示（附录给出了其他情况的轮数）

4.2 Domain Separation for POSEIDON

由于部分协议中明确要求采用若干个不同的Hahs函数，因此本文提出域分离概念，若需要不同长度的输入，则采用填充的方式来区分不同的输入，比如下列几种常见的情况

  • Merkle Tree（满二叉树的情况）：，$arity=32$，此时容量为$2^{32}-1$，无填充
  • Merkle Tree（完全二叉树的情况）：容量与叶节点的比特掩码已一致，无填充
  • 变长输入：容量为$2^{64}+(o-1)$，其中$o$表示输出长度，填充1个1和若干个0
  • 定长输入：记输入长度为$length$，此类情况下容量为$length\cdot 2^{64}+(o-1)$，需要填充若干0
  • 加密：容量为$2^{32}$，填充若干个0
  • 其他可能的情况：填充取决于具体的应用场景

5 Cryptanalysis Summary of POSEIDON

安全性分析，没看，留个坑

6 POSEIDON in Zero-Knowledge Proof Sys-tems

Poseidon Hash的设计初衷就是想将其用于ZKP系统，希望尽可能地缩短证明大小，证明与验证的时间开销

这一部分主要是Poseidon Hash适用于不同SNARK方案之间的效率对比，具体可以看原文

6.1 State of the Art

首先来看一些经典的ZKP方案

记$P$为有限域$\mathbb F$上电路对应的多项式，输入输出分别表示为$I,O$，也即有$P(I)=O$

与ZKP相关的概念之一是计算完整性问题：对于输出$O_0$，需要证明其为输入$I_0$经过电路计算的结果，也即证明$P(I_0)=O_0$，现代CPU上执行的有限步骤的程序均可转换为此类电路$[BCTV14]$，且可以在几乎不引入额外开销的情况下实现证明的零知识性

基于PCP构建的系列方案表明：对于任何程序$P$，均有可能构建计算完整性的证明，该证明可以在$|P|$的亚线性阶内完成验证，但是这只是个理论结果，对于效率很低的算法，这个结果仍然不可达

最近有一些Prover开销为$|P|$的多项式阶的方案，但这些方案需要可信设置，此时Prover的开销可以达到$|P|$的线性阶，且Verifier的验证开销为恒定值，此类系统也被称为SNARK，经典的方案比如Pinocchio、Groth16、Sonic、Plonk、Marlin等等

后续有一些无需可信设置的方案，比如Bulletproof、STARK和RedShift，但是这些方案目前仍存在不同方面的缺陷

6.2 SNARKs with $POSEIDON^\pi$

许多SNARK都是基于配对构建的，因此会需要用到配对友好的曲线来构造方案

$POSEIDON^\pi$可以用于构造此类电路，且电路中的门很少，但是需要由参数$p$确定，不过需要确保$x^\alpha$在$GF(p)$中是可逆的（需要确保$p\mod \alpha \neq 1)$

6.3 Bulletproof

Bulletproof无需可信设置，且证明大小为程序的对数阶，但是Bulletproof的验证开销与程序大小呈线性关系

‍## References

$[1]$ Lorenzo Grassi, Dmitry Khovratovich, Christian Rechberger, Arnab Roy, Markus Schofnegger:Poseidon: A New Hash Function for Zero-Knowledge Proof Systems. USENIX Security Symposium 2021: 519-535