Rescue-Prime hash STARK 代码解析

1. 引言

前序博客有：

• STARK入门知识
• STARKs and STARK VM: Proofs of Computational Integrity
• STARK中的FRI代码解析
• Rescue-Prime hash STARK

相关代码见：

• https://github.com/aszepieniec/stark-anatomy/blob/master/code（Python）

以Rescue-Prime hash STARK为例。 Rescue-Prime STARK 针对的场景为：

• public info： h , H h,H h,H
• private info： x x x
• 待证明relation： h = H ( x ) h=H(x) h=H(x)

其中 H ( ∗ ) H(*) H(∗) 为Rescue-Prime hash函数。

Rescue-Prime hash运算中涉及：

• trace：witness信息，Rescue-Prime hash算法中每一轮的输入输出；
• boundary constraints：公开信息，Rescue-Prime hash函数算法中第一轮的补0，以及最后的hash结果；
• transition constraints（又称为AIR constraints）：公开信息，Rescue-Prime hash算法中每一轮的函数运算。

2. Rescue-Prime hash函数

根据Alan Szepieniec等人2020年论文《Rescue-Prime: a Standard Specification (SoK)》可知，Rescue-Prime哈希函数主要参数有 ( p , m , c p , s ) (p,m,c_p,s) (p,m,cp​,s)：

• p p p：定义了素数域 F p \mathbb{F}_p Fp​， p p p为素数且具有a binary expansion of at least 32 bits。
• m m m：定义了哈希函数的state width。状态由 m > 1 m>1 m>1个field elements确定。
• c p c_p cp​：为arithmetic sponge的capacity。 r p = m − c p r_p=m-c_p rp​=m−cp​ r p r_p rp​：为该arithmetic sponge的rate，决定了Recue-XLIX permutation之间absorb的field elements数量。
• 80 ≤ s ≤ 512 80\leq s\leq 512 80≤s≤512：为 target security level，以bits为单位。

此外，还有如下参数：

• α 和 α − 1 \alpha和\alpha^{-1} α和α−1：为S-boxes的幂乘系数。对于所有的 x ∈ F p x\in\mathbb{F}_p x∈Fp​，有 ( x α ) α − 1 = x (x^{\alpha})^{\alpha^{-1}}=x (xα)α−1=x成立。
• M ∈ F p m × m M\in\mathbb{F}_p^{m\times m} M∈Fpm×m​：为 m × m m\times m m×m MDS矩阵。
• N ∈ N N\in\mathbb{N} N∈N为round数，一个单一的Rescue-XLIX permutation中包含了 N N N个simpler base permutation迭代，这种simpler base permutation称为a round。
• 2 m N 2mN 2mN个field elements { C i } i = 0 2 m N − 1 \{C_i\}_{i=0}^{2mN-1} {Ci​}i=02mN−1​：round constants。

2.1 sponge函数

Rescue-Prime hash函数本质是将任意长的field elements序列 映射为 r p r_p rp​个field elements： f R ′ : F p ∗ → F p r p f_{R'}:\mathbb{F}_p^*\rightarrow \mathbb{F}_p^{r_p} fR′​:Fp∗​→Fprp​​ 其在sponge构造中使用了Rescue-XLIX permutation。最终sponge函数会将任意长的序列 映射为 任意长的field elements序列： f R ′ − s p o n g e : F p ∗ → F ⋆ f_{R'-sponge}:\mathbb{F}_p^*\rightarrow \mathbb{F}^\star fR′−sponge​:Fp∗​→F⋆ 然后对该sponge函数裁剪，仅获取其前 r p r_p rp​个elements作为结果。

在sponge函数的evaluation过程中，包含了：

• 1）a permutation f R X L I X : F p m → F p m f_{R^{XLIX}}:\mathbb{F}_p^m\rightarrow \mathbb{F}_p^m fRXLIX​:Fpm​→Fpm​
• 2）具有 m m m个field elements的register，称为state。state的初始状态为全零序列 0 ∈ F p m \mathbf{0}\in\mathbb{F}_p^m 0∈Fpm​。
• 3）two phases：absorbing phase以及squeezing phase。

  • 3.1）absorbing阶段：会重复以下流程，直到所有的input elements都吸收完毕：

    • 3.1.1）将input序列中的next r p r_p rp​个elements 与 state的前 r p r_p rp​个elements相加；
    • 3.1.2）以与 r p r_p rp​个input elements相加后的state为输入，运用permutation f R X L I X f_{R^{XLIX}} fRXLIX​，获得新的state。

  • 3.2）squeezing阶段：state的前 r p r_p rp​个elements即为输出。理论上，可对state递归调用 f R X L I X f_{R^{XLIX}} fRXLIX​获得任意长的output elements序列，不过本文限制为output elements数量最多为 r p r_p rp​个。

以input elements长度为 2 ∗ r p 2*r_p 2∗rp​为例，相应的absorbing阶段具有2次迭代，示意为： 填充Padding：当inputs为任意长度时，sponge函数需要进行填充操作——在inputs之后附加一个 1 ∈ F p 1\in\mathbb{F}_p 1∈Fp​以及一堆 0 ∈ F p 0\in\mathbb{F}_p 0∈Fp​，使得填充后的inputs长度为 r p r_p rp​的整数倍。 相应的SageMath算法示例为：

2.2 Rescue-XLIX Permutation

Rescue-XLIX Permutation f R X L I X f_{R^{XLIX}} fRXLIX​中包含了 N N N次Rescue-XLIX round函数迭代，单个round中包含了以下6步：

• 1）S-box layer：对state中的每个元素进行power map ( ⋅ ) α (\cdot)^{\alpha} (⋅)α。
• 2）Linear layer：将MDS矩阵 与 state进行 矩阵向量乘法运算。
• 3）Constants injection：从round constants { C i } i = 0 2 m N − 1 \{C_i\}_{i=0}^{2mN-1} {Ci​}i=02mN−1​中取next m m m constants，将其与state中的 m m m个元素分别相加。（state中共有 m m m个元素。）
• 4）Inverse S-box layer：对state中的每个元素进行inverse power map ( ⋅ ) α − 1 (\cdot)^{\alpha^{-1}} (⋅)α−1。
• 5）Linear layer：将MDS矩阵 与 state进行 矩阵向量乘法运算。
• 6）Constants injection：从round constants { C i } i = 0 2 m N − 1 \{C_i\}_{i=0}^{2mN-1} {Ci​}i=02mN−1​中取next m m m constants，将其与state中的 m m m个元素分别相加。（state中共有 m m m个元素。）

以 m = 3 m=3 m=3为例，Rescue-XLIX permutation中第 i i i轮示意为： 相应的SageMath代码示例为：

2.3 MDS矩阵选择

令 g g g为 F p \mathbb{F}_p Fp​的smallest primitive element，通常取 g = 2 g=2 g=2，基于此找到order为 p − 1 p-1 p−1的最小 g g g。详细的生成算法参见SageMath代码：

2.4 round constants { C i } i = 0 2 m N − 1 \{C_i\}_{i=0}^{2mN-1} {Ci​}i=02mN−1​选择

round constants { C i } i = 0 2 m N − 1 \{C_i\}_{i=0}^{2mN-1} {Ci​}i=02mN−1​选择，见SageMath算法：

2.5 计算 α \alpha α和 α − 1 \alpha^{-1} α−1

α \alpha α为the smallest integer that is coprime with p − 1 p-1 p−1， α − 1 \alpha^{-1} α−1为其multiplicative inverse in the ring Z / < p − 1 > \mathbb{Z}/ Z/。 当 gcd ⁡ ( p − 1 , 3 ) = 1 \gcd(p-1,3)=1 gcd(p−1,3)=1时，有 α = 3 , α − 1 = 2 p − 1 3 \alpha=3,\alpha^{-1}=\frac{2p-1}{3} α=3,α−1=32p−1​。 详细的SageMath算法为：

2.6 计算round数

当 ∣ p ∣ ≥ 32 |p|\geq 32 ∣p∣≥32且 80 ≤ s ≤ 512 80\leq s\leq 512 80≤s≤512时，Gr¨obner basis攻击效率最高，要基于该攻击来选择round数。 详细SageMath算法见：

2.7 Rescue-Prime哈希算法

Rescue-Prime哈希SageMath算法见：

3. Rescue-Prime hash STARK证明

以https://github.com/aszepieniec/stark-anatomy/blob/master/code/rescue_prime.py中的Rescue-Prime哈希函数实现为例，其设置input length固定为1， r b = 1 , m = 1 , c p = 1 , N = 27 , p = 407 ∗ ( 1 < < 119 ) + 1 r_b=1,m=1,c_p=1,N=27,p=407 * (1