算术化

许多零知识证明系统都使用算术化的方法，将计算类问题简化成涉及有限域F上的多项式的代数问题。zk-STARK对计算完整性（ Computational Integrity， CI）声明，“输出结果α是程序C根据输入x经过T步执行所得”，进行证明的第一步是算术化。

zk-STARK算术化的方法包括2个重要方法，首先，构建程序C的代数中间表达(Algebraic Intermediate Representation, AIR)，用s个多项式描述当前执行状态与下一步状态的转化约束；其次，为降低证明者的时间复杂度和空间复杂度，将上述多项式进行链接合并形成1个多项式，该方法称为ALI（Algebraic Linking Interactive Oracle Proof）。 详细说明如下。

AIR

对计算完整性进一步深入理解下，实际上需要通过AIR将这一约束表达出来，即从输入x到输出α的程序执行过程中的中间计算状态转换，中间计算状态则是一堆寄存器数值。因此，给出AIR的定义，是一个低度多项式的集合

$P=\{P_1(\overrightarrow{X},\overrightarrow{Y}),...,P_s(\overrightarrow{X},\overrightarrow{Y})\}$

1. 低度多项式的系数在域 $F$内
2. $\overrightarrow{X}=(X_1,...,X_w)$ 代表当前计算状态
3. $\overrightarrow{Y}=(X_1,...,X_w)$ 代表下一步计算状态
4. $w$ 是证明系统所中某一个计算状态的变量数量
5. $P_i$ 代表转换关系的多项式
6. 有一对解$(\overrightarrow{x},\overrightarrow{y})$使得转换关系成立，当且仅当 $(\overrightarrow{x},\overrightarrow{y})$是$P$的共同的解，即 $P_1(\overrightarrow{x},\overrightarrow{y})=...=P_s(\overrightarrow{x},\overrightarrow{y})=0$
7. AIR的多项式的度是 所有$P_i$中的最大值
8. s 是所有约束的数量

通过上述定义，可以看出，AIR将程序C执行过程中寄存器数值前后变化关系转化成了约束多项式，以便验证者能信任输入x到输出y的完整过程，而不是随便得出的结果或者是伪造的输出结果。

那么，上述的计算状态具体包括什么，如何组织，请查看执行轨迹

ALI协议

由于多项式的插值计算及验证计算需要耗费大量的计算资源，因此，ALI协议将s个多项式约束化简为单一约束，例如，可以使用随机线性组合。

实际上，采用ALI协议后，具有更好的可靠性(soundness)。如果对证明过程感兴趣，可以参考 Eli Ben Sasson 的文章Scalable, transparent, and post-quantum secure computational integrity附录D