Abstract
零知识证明系统被广泛用作不同协议的构建块，例如那些支持区块链的协议，零知识证明系统中的一个核心元素是底层PRF，通常建模为哈希函数，该函数需要在素数阶的有限域上有效，这样的散列函数是新开发的面向算术（Arithmetization-Oriented，AO）的设计范式的一部分
本文提出了两个新的AO哈希函数，XHash8和XHash12，它们是基于改进RPO中的瓶颈而设计的
根据本文的实验，XHash8的性能比RPO快约2.75倍，XHash12的性能比RTO快约2倍，同时继承了Marvelous设计策略的安全性和稳健性
1 Introduction
ZK-STARK$[BSBHR18]$是一个ZK证明系统，它是一个可扩展的证明系统，主要用于Layer 2项目，如Polygon和Starknet
Rescue的设计是AO原语领域的一个重大改进，引入了非过程计算，虽然Rescue在STARK内部具有竞争力，但当在CPU或FPGA等更标准的平台上执行时，其仍然具有改进的空间（包括后续的Rescue-Prime和RPO）
在STARK内部进行评估时，RPO提供了与Rescue Prime相同的性能，但在标准CPU上的速度约快40%，这一改进的大部分是通过找到一个特别有效的MDS矩阵实现的，但没有改变总体设计或引入新的操作
本文主要设计在CPU和STARK运行时间之间进行平衡的AO哈希函数，首先从分析RPO中剩余的瓶颈开始，并通过引入一种新的操作来提高效率：在扩展域上进行乘法运算
在传统对称密钥算法（如AES$[DR02a]$）的设计中，扩展域上的乘法非常常见，在AO密码的背景下，这种方法被沿用到Vision$[AAB+20]$和Chaghri$[AMT22]$以及现在已经失效的Starkad$[GKK+19]$
基于上述工作，本文将相同的技术应用于素数阶域，以降低成本同时实现扩散和代数复杂性，在扩域上计算乘法比较高效，也可以更高的扩散所需要的特性，从而提高设计效率
本文的主要贡献为XHash12和XHash8两个Hash算法
2 Preliminaries
- $p$：素数，本文采用的素数$p=2^{64}-2^{32}+1$
- $\mathbb F_p$：素域
- $S=(S[0],\dots,S[n-1])$：大小为$n$的向量
- $M[i][j]$：$n\times m$矩阵的第$i$行第$j$列的元素
- $\boxplus$：有限域上加法
2.1 Rescue-Prime Optimized
Rescue-Prime优化Hash本质是一个海绵函数，通过$\mathbb F^{12}_p$上的置换进行实例化（类似于Poseidon Hash和MiMC），其置换包含7轮，每一轮包含下列四个组件
- $\pi_0:x\mapsto x^7$
- $\pi_1:x\mapsto x^{1/7}$
- $M$：MDS矩阵
- $\boxplus_c$：有限域常数加法
这里记状态向量$s\in \mathbb F^{12}_p$，基于这个向量定义两种类型的步骤
- $F$：此类步骤中首先将$\pi_0$作用域所有状态元素（目的是提供非线性性质），然后将状态向量与MDS矩阵相乘，将局部元素扩散到整个状态（实现扩散性质），然后再向每个元素中加上一个轮常数，避免不同轮之间的自对称性
- $B$：和步骤$F$过程类似，区别在于这一类步骤用的是$\pi_1$
基于上述两类步骤，类Rescue函数的典型步骤轮为$(F)(B)$交替，比如下面这样
$$ (F)(B)(F)(B)(F)(B)(F)(B)(F)(B)(F)(B)(F)(B) $$
3 XHash8 and XHash12 — Design Rationale
设计策略中两个主要的部件是S盒和线性层，前者提供非线性映射，后者通常是由MDS矩阵实现，目的是提供扩散性质
S盒、MDS矩阵乘法与密钥注入（Key Injection）相互作用，得到了具有高阶盒高密度的复杂多项式表示，但是开销也很大
为了降低此类开销，本文建议在扩域上使用幂映射，在扩域中的乘法通过混合基域元素来提供扩散，以及通过非线性的方式来提供混淆
但是这里还有一个自然的问题：是否存在进一步提高效率的可能，注意到$\pi_0$和加常数的操作的开销几乎可以忽略不计，且矩阵$M$也经过了特殊的优化，因此效率的主要瓶颈在于$\pi_1$
实际CPU执行时$\pi_1$需要大约70次乘法运算，而每个$B$步中都需要12次调用$\pi_1$，7次$B$步总共需要$70*12*7=5880$次乘法，开销极大
因此为了优化效率，就需要考虑这两和S盒的作用，这里看一下$[AAB+20]$的研究
这两个S盒的区别在于他们的阶，设计S盒时应当确保$\pi_0$在正向时（加密时）具有高阶，而反向时（解密时具有低阶），而$\pi_1$的思路则相反，也即正向低阶，反向高阶
这么设计主要是出于三个目的考虑
- 无论敌手试图在哪个方向实施攻击，都可以确保方案的阶数较高
- 加解密的开销基本一致
- 可以有效评估每个S盒的低阶表示
这里需要注意的是，$[AAB+20]$给出的时通用原语构造思路，不仅可以用于设计Hash，还可以用于设计STARK
不过上面的第二点要求与本文无关，因为Hash只是正向的，确保正向的高效即可，无需高效的反向，因此这里直接不考虑第二点
类似的，也可以对第一点要求做出一点妥协，尽管防御攻击需要确保两个方向的阶都很高，但是也不需要确保这两个方向的阶一致
注意到反向的阶来自于$F$轮，无需进行优化，而本文考虑$B$轮是否提供了太多的安全性以导致其性能下降
$[AAB+20]$注意到两次$B$轮之后阶已经可以达到最大，假设修改后的$B$轮可以在4轮就达到最大阶，则Rescue中的最小轮数可以设置为10，Rescue-Prime中设置为8轮，RPO中设置为7轮，从而在不影响安全性的前提下确保效率
此外，注意到$\mathbb F^{12}_p$上计算Hash的时候，对于多项式阶数不高的情况下，主要的攻击手段是插值攻击，如果编码密文的单变量多项式为稠密的，且具有最高阶，则可以抵抗插值攻击
根据前面的设计思路，多项式定理盒MDS矩阵、幂映射确保了多项式的密度，因此重点就来到了确保最大阶，这里令$x^{1/7}$如下
$$ x^{1/7}=x^{(2p-1)/7}=x^{10540996611094048183} $$
此时可以在$\pi_1$的单次调用中就可以达到接近最大阶，这里本文非正式的认为这是一种过度杀伤（overkill），且只要在合理的轮数内达到最大阶，则仍然可以确保每一步的低阶S盒仍然足以抵抗插值攻击
简单来说就是找到一个幂映射$\beta$，使得$7<\beta<\frac{p-1}{7}$，但是根据定义，此类S盒无论是在STARK内部直接计算还是折叠计算都是 效率很低的，不难看出高效的幂映射其实很难找
不过可以使用相同的幂映射，但是将其作用于更少的元素来提高效率，但是此类方法只有使用了幂映射的元素才会具有安全性
4 Specification
这里用第三种类型的S盒来补充上述两类S盒，称为$\pi_2$
$\pi_2$与$\pi_0$类似，将域元素升高至7次幂，但是$\pi_2$是在$\mathbb F_{p^3}$域上计算（而非$\mathbb F_p$）
这里引入了新的S盒之后，本文定义XHash8和XHash12，后者使用作用于所有状态元素的S盒$\pi_1$的完全层，而前者为了确保效率，仅在部分层（Partial Layer）作用$\pi_1$
4.1 XHash12: With Full $x^{1/7}$ Layer
XHash12的完全层需要作用S盒$\pi_1$，并包含下列几个步骤
- 初始化步骤$(I)$：执行常量加法盒MDS矩阵运算
- $B$：执行标准的$B$轮，将$\pi_1$作用于所有状态元素，然后执行常数注入
- $P3$：将12个状态元素切分为四个$\mathbb F_{p^3}$上的向量，也即$(s_0,\dots,s_{11})\mapsto (S_{0,1,2},\dots,S_{9,10,11})$，然后将$\pi_2$作用于$(S_{0,1,2},\dots,S_{9,10,11})$，得到$(S^7_{0,1,2},\dots,S^7_{9,10,11})$，之后将这四个向量拆分回12个元素，并将其与MDS矩阵相乘，然后执行常数注入
上述步骤的执行顺序如下，流程如图1所示
$$ (I)(F)(B)(P3)(F)(B)(P3)(F)(B)(P3) $$
4.2 XHash8: With Partial $x^{1/7}$ Layer
XHash8相对于XHash12更激进，区别在于其在部分层采用$\pi_1$
XHash8的计算步骤与XHash12基本一致，区别在于$B$轮，XHash8会执行$B'$轮（执行修改的$B$轮），将$\pi_1$作用于12个元素的其中8个（除了$s_1,s_4,s_7,s_{10}$），然后执行常数注入
XHash8通过在以元素$(s_0,\dots,s7)$作为外部部分和$(s_9,\dots,s_{11})$作为内部部分的海绵结构中使用该排列来获得提供128位安全性的散列函数
流程图如下图所示
5 Security and Performance
安全性分析和效率可以看原文
References
$[1]$ XHash8 and XHash12: Efficient STARK-friendly Hash Functions (iacr.org)