执行轨迹

本文是STARK数学系列的第三篇，深入探讨了如何通过多项式约束的组合，从执行轨迹中构造低度多项式，并展示其在验证过程中的应用。作者介绍了误差纠正码在提高验证器查询效率中的作用，并通过简单的布尔执行轨迹和斐波那契数列示例说明了相关原理，最后讨论了多列多约束情况的处理。文章在理论和实践中都有深度和详实的分析，是理解STARKs的重要资源。

本文介绍了在zkEVM中使用plookup来创建执行轨迹的方法，以克服字节码转换为SNARK的难题。通过将操作码及其索引存储在查找表t_opcodes中，并在执行证明阶段允许prover选择任何操作码，结合程序计数器检查索引的正确性，从而实现对循环和复杂操作码（如returndatacopy和哈希函数）的支持，优化了zkEVM的性能，降低了约束开销。

这篇文章深入探讨了STARKs中的算术化方法以及其与计算完整性之间的关系，主要聚焦于AIR及其变体PAIR。文章详细分析了在STARKs中的算术中介表示、执行轨迹的定义和构建、以及多元多项式的约束形式。作者提供了丰富的数学背景支持，并通过示例和公式说明了算术化过程的具体实施方案，是一篇技术深度和结构清晰的文章。