FRI
目标：检测多项式的阶小于 $d$。验证方如果认可是 $d$ 阶多项式，则认可证明方的保密数据正确。
FRI 协议：快速 Reed-Solomon 近似交互式预言机证明（Fast Reed-Solomon Interactive Oracle Proof of Proximity）。可基于 Fait-Shamir 计算随机数，转为非交互式协议。
整个过程不断应用折半公式和线性组合，仅需 $O(logd)$ 次，可实现对 $d$ 阶多项式 $f_0(x)$ 的阶测试，其中 $d=2^n$
以下描述是交互式的，实际应用中是非交互式的，会将每步要发送的数据进行汇总，一次性发送，发送的数据量比较大，这是 STARK 的一个缺点。验证方拿到所有数据后，一步步验证，验证过程中还会有计算，复杂度比较高。为了降低复杂度，避免使用 SHA256, SHA3, Keccak 等哈希函数，而是使用 Poseidon 等 ZK 友好型哈希函数。
第 1 步
证明：将 $d$ 阶多项式 $f_1(x)$ 的值进行 Merkle 承诺得到 Merlke 根 $root(f_1)$，对其哈希后得到随机数 $z$
$$ z=Hash(root(f_1)) $$
计算 $z$ 的函数值 $f_1(z), f_1(-z)$
发送数据为：$root(f_1), f_1(z),f_1(-z), path(f_1(z)),path(f_z(-z))$
验证：确保 $f_1(z)$ 在 Merkle 树 $root(f_1)$ 上
$$ root(f_1)=Merkle(f_1(z), path(f_1(z))) $$
同理，确保 $f_1(-z)$ 在 Merkle 树上
第 2 步
证明：多项式折半，$d$ 阶多项式 $f_1(x)$ 的偶数项为 $g(x^2)$，奇数项为 $h(x^2)$，则得到折半公式：
$$ f_1(x)=g_1(x^2)+ x \cdot h_1(x^2) $$
计算随机数 $\alpha_2$
$$ \alpha_1=Hash(z)=Hash(Hash(root(f_1))) $$
构造线阶为 $d/2$ 的性组合多项式，令 $y=x^2$
$$ f_2(y) = g_1(y) + \alpha_2 \cdot h_1(y) $$
符号修改：
$$ f_2(x)=g_1(x) + \alpha_2 \cdot h_1(x) $$
对多项式 $f_2(x)$ 的值 Merkle 承诺得到 Merkle 根 $root(f_2)$
计算随机数 $-z^2$ 处的函数值 $f_2(-z^2)$
发送数据为：$root(f_2),f_2(-z^2),path(f_2(z^2)),path(f_2(-z^2))$
因为验证方可算出 $f_2(z^2)$，所以不需要发送
验证：（Fait-Shamir）计算随机数 $z$
$$ z=Hash(root(f_1)) $$
结合第 1 步的 $f_1(z),f_1(-z)$ 和折半公式，得到
$$ \begin{align} & f_1(z)=g_1(z^2) + z \cdot h_1(z^2)\\ & f_1(-z)=g_1(z^2) - z \cdot h_1(z^2) \end{align} $$
可解出 $g_1(z^2),h_1(z^2)$
（Fait-Shamir）计算随机数 $\alpha_1$
$$ \alpha_2=Hash(z,root(f_2)) $$
从而算出 $f_2(z^2)$
$$ f_2(z^2)=g_1(z^2)+ \alpha_2 \cdot h_1(z^2) $$
验证 $f_2(z^2)$ 在 Merkle 树 $root(f_2)$ 上
$$ root(f_2)=Merkle(f_2(z^2),path(f_2(z^2))) $$
同理，验证 $f_2(z^2)$ 在 Merkle 树 $root(f_2)$ 上
第 log(d) 步
证明方发送的数据为： $root(f_{log(d)}),f_{log(d)}(-z^2),path(f_{log(d)}(z^2)),path(f_{log(d)}(-z^2))$
验证：计算出 $f_{log(d)}(z^n)$，基于多项式折半公式和线性组合，获得一个多项式
$$ f_{log(d)}(x)=g_{log(d)}(x) + \alpha_{log(d)} \cdot h_{log(d)}(x) $$
该多项式的阶为 $d / 2^{log(d)}=1$，所以为常量多项式。
验证方使用直接测试完成常量多项式阶段测试。
斐波纳契数列 Stark
证明方需要证明第 1000 个斐波纳契输出值 $Z$ 的起始为一个公开输入 $X$ 和一个保密输入 $Y$，且 $F ( X , Y ) = Z$ 。该过程等价于证明
$$ \begin{align} &F_0=X,F_1=Y\\ &F_i=F_{i-2}+F_{i-1}\\ &Z=F_{999} \end{align} $$
该计算需要 $n=1000$ 步和 $w=2$ 个寄存器，迹 $T$ 是一个 $n \cdot w = 1000 \times 2$ 的表格，可得到转换约束
$$ \begin{align} &T_{i+1,0}=T_{i,1}\\ &T_{i+1,1}=T_{i,0} + T_{i,1} \end{align} $$
第一个式子表示将本行的第 2 列赋值给下行的第 1 列，第二个式子表示本行的两列和赋值给下行的第 2 列。
边界约束：
$$ \begin{align} &T_{0,0}=X\\ &T_{999,1}=Z \end{align} $$
所有，证明方证明知道秘密值 $Y$ 满足关系 $F(X,Y)=Z$ 等价于知道迹 $T$ 满足转换约束和边界约束。
zkSTARK 中：基于秘密值 $Y$，计算出迹 $T$
Groth16 中：基于秘密 witness，计算出出向量 $\vec{s}$
迹多项式
将 $n = 0,...,999$ 当作多项式的横坐标，将寄存器 $T_{n ,0}$ 和寄存器 $T_{ n ,1}$ 中存储的迹值当作多项式的值，则构造出多项式值表达，再利用快速傅立叶变换 FFT 则可得到多项式的系数表达 $P_0(x),P_1(x)$，称为迹多项式。
约束多项式
则有如下等价转化关系：
- 多项式值表达：转换约束 $T_{i+1,1}=T_{i,0} + T_{i,1},i \in [0,1000)$
- 多项式系数表达：$P_1(i+1)=P_0(i)+P_1(i), i \in [0,1000)$
- 多项式系数表达：$P_1(i+1)-(P_0(i)+P_1(i))=0, i \in [0,1000)$
- 多项式系数表达：$Q(x)=P_1(x+1)-(P_0(x)+P_1(x))=0, i \in [0,1000)$
构造公开的目标多项式
$$ R(x)=(x-0)(x-1)...(x-999) $$
转换约束满足以下等价关系
$$ \begin{align} & T_{i+1,1}=T_{i,0}+T_{i,1} \iff C_0=\frac{Q(x)}{R(x)}=\frac{P_1(x+1)-(P_0(x)+P_1(x))}{\prod^i_{i \in [0,999)}(x-i)} \\ & T_{i+1,0}=T_{i,1} \iff C_1 = \frac{P_0(x+1)-P_1(x)}{\prod^i_{i \in [0,999)}(x-i)} \end{align} $$
边界约束满足以下等价关系
$$ \begin{align} & T_{0,0}=X \iff C_2(x) = \frac{P_0(x)-X}{x-0}\\ & T_{999,1}=Z \iff C_3(x) = \frac{P_1(x)-Z}{x-999} \end{align} $$
因此，证明方知道迹 $T$ 满足转换约束和边界约束，等价于证明方知道多项式 $P_0(x),P_1(x)$ 使得 4 个商多项式 $C_0(x),C_1(x),C_2(x),C_3(x)$ 存在，则认可证明方知道秘密值 $Y$ 满足关系 $F(X,Y)=Z$。
验证方通过 FRI 验证 4 个商多项式 $C_0(x),C_1(x),C_2(x),C_3(x)$ 是 $d$ 阶多项式，则认可证明方的保密数据正确。
zkStark
算术化
算术化：将计算问题转换为有限域 F 上的多项式代数问题。
zkSTARK 算数化包括 2 个重要方法：
首先，构建程序的代数中间表达 (Algebraic Intermediate Representation, AIR)，用 s 个多项式描述当前执行状态与下一步状态的转换约束。
其次，为降低证明者的时间复杂度和空间复杂度，将 s 个多项式线性组合为 1 个多项式，该方法称为 ALI (Algebraic Linking Interactive Oracle Proof)。
多项式承诺
算术化中会得到两种 witness：
- 整个待证明程序的执行轨迹 execution trace，对应迹多项式。轨迹可以看着一组寄存器的状态转换过程，是基于状态转换表格中的列构造出的多项式。
- 在执行过程中需要满足的约束条件 constraint，对应商多项式。约束包括两部分，边界约束和状态转换约束。
接下来对执行迹和约束条件做多项式承诺。
用 KZG 或 Dan Boneh 承诺不太好，因为通常会涉及 for 循环，如果 for 循环次数不固定，则 (PK, VK) 不固定，所以需要用递归零知识证明。
设置：STARK 使用 Merkle 树承诺，不需要额外可信设置，没有 (PK, VK)，纯哈希，因此 for 循环等约束对 AIR 没有影响。for 循环次数只影响到多项式的阶。
承诺：首先求出多项式 $\psi(x)$ 在其求值域上所有单位根处的值 $\psi(\omega^0),\psi(\omega^1),\psi(\omega^i),...$，以这些值为叶子节点，组成一棵 Merkle 树，公开的 root 为该多项式的承诺。Merkle 树要求叶子节点个数必须是 2 的幂次，所以如果叶子节点数不足的话要补齐。
打开承诺：验证者选择一些随机挑战点，证明者提供多项式在该点处的值，以及一条 Merlke 树 path。验证者验证该 path 合法性。
为协议的安全性，还需要进行扩展。
低度多项式扩展（Low-Degree Extension）
从程序的执行轨迹中，得到数个长度为 N 的轨迹多项式。出于安全性的考虑，需要在一个更大的求值域上承诺该多项式，一般需要将求值域扩大 $2^k$ 倍，扩大的倍数称为爆炸因子（blowup factor），该求值域称为 LDE 域。
利用低次多项式生成更大值域上单位根处值的方法称为低度多项式扩展。扩展后，多项式的阶不发生变化。
约束多项式线性组合
如果检查每个约束多项式的次数，代价会很大，可以将所有的约束多项式组合到一起，形成一个线性组合多项式（Composition Polynomial）。
在线性组合之前，需要注意：约束多项式的次数可能是不同的。需要先将约束多项式补齐到相同的次数，然后再线性组合。补齐方法：乘上一个随机的 $d−d_j$ 次多项式。
$$ CP(x)=\sum^3_{j=0}C_j(x)(\alpha \cdot x^{D-D_i} - \beta_j) $$
最后得到线性组合多项式 $CP(x)$，需要在 LDE 域上进行多项式承诺，因此，像之前的迹多项式那样，使用低度多项式扩展的方式进行多项式承诺。
DEEP-FRI
把迹多项式和线性组合多项式 $CP(x)$ 再做一次随机的线性组合，然后证明最终的多项式度数小于 D，就能证明所有的约束条件满足，且程序的执行过程和被承诺的 Trace 一致。
但是，从安全性角度出发，还需要做一些调整。 STARK 使用称为 Domain Extension for Eliminating Pretenders (DEEP) 的方法进行检查。从基域 $F$ 上随机选一个点 $x \in F$，然后检查各多项式的值在这个点上是否满足约束。基域是一个比 LDE 域大得多的域。
$$ DEEP(x) = \alpha_0 \frac{P_0(x)-P_0(z)}{x-z} + \alpha_1 \frac{P_1(x)-P_1(z)}{x-z} + \alpha_2 \frac{CP(x)-CP(z)}{x-z} $$
商多项式 DEEP(x) 存在，则多个多项式的随机打开点正确，则多个多项式正确，则 trace 多项式和 CP 多项式正确，则约束正确，则计算正确，则保密数据正确。
在实际应用中，CP(x) 的度一般比迹多项式要高，取决于约束条件，需要将 CP(x) 拆分为多个度小于 d 的多项式。
构造完 DEEP(x) 后，如果能够证明 DEEP(x) 是一个次数小于 d−1 的多项式，就可以证明所有的多项式在 z 点处的取值即是所预期的值，进而证明程序的执行结果正确，且所有的约束条件都满足。
FRI 低度多项式测试
FRI 通过一种称为“折叠”的方法先降低多项式的阶，再使用第一章中的折半方式进行低阶测试，可降低复杂度。
假设有 d = 1000 个点 $(x_i, f(x_i))$，构造 d/N=100 行 N=10 列矩阵。
- 将每一行的 100 个多项式值 $f(x_i)$ 组成 Merkle 树并输出 root。
- 对每一行的 100 个 $f(x_i)$ 用随机数进行线性组合，得到一个值 $f'(x_i')$
- 选择新的横坐标 $x_i$，则针对每列得到一个项数为 100 的多项式 $f'(x)$
- 重复上述步骤，直到新多项式的次数降到可接受范围内。假设重复 k 次，则只需检查最后的多项式的阶是否小于 $d / N^k$。
新多项式的定义域会发生变化：
- 原多项式的求值域上单位根分别为 $ω^0 ,ω^1 ,ω^2 ,...,ω^{n-1}$
- 新多项式其求值域是原来的 1/N，其单位根变为 $ω^0 ,ω^N ,ω^{2N} ,...,ω^{\frac{n}{N}N}$
验证者检查
检查 FRI 步骤的正确性
验证折叠关系
在新值的 Merkle 树同一层上抽取 N 个相关的折叠点，在下一层上抽取一个点，就能验证本层的 N 个点确实按正确的随机数折叠到下一层的同一个点。
- 验证折叠后的多项式的阶
检验多项式是否匹配
目标：确保多项式来源于转换约束、边界约束。
验证者可以向证明者请求 LDE 域中任意一点处的 $DEEP_{fake}(x)$ 的值，以及之前的轨迹多项式，组合多项式在该点处的值 $P_0 (x), P_1(x), CP(x)$。验证者自行计算 $DEEP_{real} (x)$，若和证明者发送的 $DEEP_{fake}(x)$ 不等，则验证不通过。
总结：验证者自己计算 k 个多项式的值，与证明方计算的值看是否相等，防止证明方承诺一个伪造的低阶多项式。
磨损因子 (Grinding Factor)：可以要求证明者在提供 STARK 证明的同时也提交一个工作量证明 (PoW)，使得重试的代价变大。
RS Code
是指 I.S.REED 和 G.SOLOMON 在 1960 年发表的《POLYNOMIAL CODES OVER CERTAIN FINITE FIELDS》 论文所提出的纠错码编码方法，因而得名 RS code。
RS code 最开始是为了解决通信中由于通信信道不可信导致的接收方来检测和更正发送方发来的原始数据的。基本思想很简单，就是通过发送方按照算法发送拉格朗日冗余。
基于不同的多项式值的集合构造出来的多项式系数表达，应该是相同的，去掉不同的。
没有评论