以超市收据为例，如何进行 stark 验证
其实要做的就是给定程序 A，输入 x，输出 y 和时间限制 T，能生成一个证明字符串 Π 来证明 “A (x) 在 T 个计算步骤内输出 y”，y=1 就是有效证明。
首先验证不可能重新计算一次，验证只需要抽查一部分执行轨迹，要使得抽查一部分执行轨迹就有效，就得利用纠错码功能。
还有要保障执行轨迹的数据真实有效，未被改动，这时就得利用多项式承诺，验证需要用到多项式承诺，快速验证就得用低度测试，快速幂算法，费马定律等。
有了以上就可以保障能有效的验证了，还有要实现透明性和非交互式验证，这时就得利用 Hash 函数。
总结流程#
- 把初始计算的执行轨迹（超市收据）弄下来 (encode (A,x,y,T)), 对执行轨迹进行编码，形成 T-step 的执行轨迹，通过多项式进行编码得到𝚽。把执行轨迹进行扩充，例如扩充 10 倍，选择一个更大的域，本身的执行轨迹的数据只是该域的子群（纠错码，执行轨迹视为对某个域上的多项式的赋值，并在更大的域上赋值该多项式来扩展执行轨迹）。
- 对程序 A 进行编码，通过 AIR，多项式中间描述对给定程序进行约束。
- 把上面的多项式合并成一个多项式，然后去做准备做 FRI 多项式承诺，多项式承诺保障了数据不能被修改，或者说改了基本就会被查出来。（多项式承诺的大小，生成承诺的时间的复杂度为：log (n) 对比的是 AIR 合并后的多项式）
- 验证者发送随机性𝛔₀，这使得证明者和验证者都可以将所有多项式约束 “捆绑” 到一个统一的对 A 的多项式约束。
根据证明的数据进行哈希，根据哈希生成一些随机数证明者根据执行轨迹与对 A 约束合起来的多项式 𝚵 。- 证明者将𝚵发送给验证者。验证者通过本地一致性检查确保𝚽和𝚵适当相关。
- 去做多项式承诺。一个低度测试需要计算 log (𝚵的阶数 n) 次多项式拆分，承诺的大小的复杂度也为 log (n)，承诺包括了𝚵 merkle，拆分后的𝚵 merkle，分支路径（分支路径的选择，根据此前证明中生成的数据的哈希随机选取每个样本的下标或 r 值），最底层叶子 merkle。
- 根据哈希随机抽查扩充后执行轨迹（长证明）的 n 个点（低度测试，一个点检查到错误的概率为 90%），证明通过非交互式和多项式承诺结合去验证每个点是否正确 (低度测试)。得到每个点的多项式多项式承诺，再结合状态根去生成证明。