关于STARKs中周期性约束的所有你想知道但无人告知的内容

正如你可能已经猜到的那样，我们正在研究所有可用的文献和代码，以成为业内的重要参与者之一。我们要感谢 Eli Ben-Sasson 和 Starkware 在该领域所做的出色工作，以及他们帮助我们学习这一切。我们还要感谢 Max Gillett 花时间与我们讨论所有这些事情。他们对我们非常好，我们希望能够继续向他们学习。

介绍

ZK-STARKs（零知识可扩展、透明、后量子知识论证）是一种密码学工具，允许一方证明计算的完整性。例如，一方可以表明他正确计算了斐波那契数列的前 1000 个元素，运行了给定的机器学习算法，或正确处理了 5000 笔以太坊交易。此外，检查结果证明比验证者天真地重新执行计算要快得多（验证时间以计算大小的对数方式缩放）。鉴于它们的特性，它们引起了许多领域的兴趣；其中，它们可以解决去中心化账本所遭受的可扩展性问题。

有很多有趣的资源可以学习 STARKs 的基础知识，例如 Starkware 的 STARK 101，Anatomy of a STARK，Ministark，以及 Starkware 关于算术化的博客（第一部分 和 第二部分）。在这篇文章中，我们将重点关注如何强制执行约束，以及如何在周期性应用时处理这些约束。很快我们将发布一个更深入的 STARKs 版本。

STARKs 的起点是算术化。我们生成程序的执行轨迹，获得一个表格，显示每个寄存器如何根据正在执行的指令演变。执行表的值通过约束（通常是低阶多项式）关联。我们将特别关注转换约束以及如何检查轨迹的值是否满足这些约束。

转换约束

转换约束规定了计算的不同状态之间的关系。假设我们有一个寄存器，其中包含斐波那契数列的元素，

$a0=a1=1$

$an+2=an+1+an$

最后一个等式给出了斐波那契数列的转换约束；其他的处理问题的边界约束，并且更容易处理它们。为了使我们的讨论更容易，假设我们对某个 $m \geq 1$ 执行了斐波那契数列的 $2^m$ 步。通过重写约束并分析每个索引，我们得到，

$a2−a1−a0=0$

$a3−a2−a1=0$

$a4−a3−a2=0$

等等。我们可以通过在合适的域上插值将轨迹元素转换为多项式。为了使事情更容易，我们选择 $n$ 次单位根，这使我们能够通过快速傅里叶变换执行插值。这些根由一个元素（一个生成器，$g$）跨越：通过取它的幂，我们得到所有的 $n$ 次单位根，${1,g,g^2,g^3,...,g^{n-1}}$。让我们称 $t(x)$ 为插值轨迹的多项式，即取以下值的多项式：

$t(1)=a0$

$t(g)=a1$

$t(g^2)=a2$

$\vdots$

$t(g^{n-1})=a_{n-1}$

我们可以将约束表示为

$t(g^2)−t(g)−t(1)=0$

$t(g^3)−t(g^2)−t(g)=0$

$t(g^4)−t(g^3)−t(g^2)=0$

以通用方式，

$t(g^2x)−t(gx)−t(x)=0$

我们可以检查约束是否被强制执行的方法是验证多项式 $p(x)=t(g^2x)−t(gx)−t(x)$ 是否可被 $(x−x_0)$ 整除，其中 $x_0$ 是我们强制执行约束的点。另一种看待此问题的方式是，结果函数

$Q(x)=\frac{p(x)}{x-x_0}$

是一个多项式。STARK IOP 没有显示 $Q(x)$ 是一个多项式，而是证明它接近一个低阶多项式。

在斐波那契数列的情况下，约束对于 $x_0 \in {1,g,g^2,...g^{n-3}}$ 有效。鉴于它可以被每个因子整除，因此可以被所有因子的乘积整除，

$ZD(x)=\prod_{0}^{n-3}(x-g^k)$

我们面临的关于这个多项式的问题是，要计算它，我们需要执行线性数量的乘法，也就是说，与因子数量一样多的乘法。幸运的是，单位根具有以下属性：

$s(x)=\prod_{i=0}^{n-1}(x-g^k)=x^n-1$

因此，我们可以通过取出缺少的因子，从 $s(x)$ 计算 $ZD(x)$ ，而不是执行线性数量的操作：

$ZD(x)=\frac{s(x)}{\prod_j(x-g^j)}=\frac{x^n-1}{(x-g^{n-1})(x-g^{n-2})}$

STARKs 的优势在于，如果一个约束重复多次，我们可以简洁地表达它。唯一的改变在于消失多项式 $ZD(x)$，它会添加因子。

约束在 $m$ 步后重复

在像斐波那契这样的情况下，约束涉及域中的几乎所有点，因此计算消失多项式 $ZD(x)$ 非常简单。但是，当仅在某些点应用约束时会发生什么？例如，在 EthStark 中，某些转换约束仅在 $m$ 步后应用。

为了确定思路，假设我们有一个形式的转换约束

$f(x,gx,...g^dx)=0$

我们的斐波那契数列符合此形式。我们现在将考虑每四步应用一次；也就是说，约束在 $x_0 \in {1,g^4,g^8,g^{12},...}$ 处强制执行

消失多项式看起来像

$ZD(x)=\prod_k(x-g^{4k})$

如果 $g$ 是 $n$ 次单位根的生成器，则 $g^4$ 是 $n/4$ 次单位根的生成器，$\omega=g^4$。因此，我们可以将前者重写为

$ZD(x)=\prod_k(x-\omega^k)$

但是由于乘积是所有 $n/4$ 次单位根的乘积，因此 $ZD(x)=x^{n/4}-1$。如果像在 EthStark 中一样，每 32 步应用一次约束，则消失多项式就是 $ZD(x)=x^{n/32}-1$。如果我们跳过一些步骤，我们需要将它们取出。例如，假设我们有两个约束

$f_1(x,gx)=0$

$f_2(x,gx)=0$。

约束 2 每四步强制执行一次，约束 1 每两步强制执行一次（但约束 2 无效的地方除外）。为了清楚起见，约束 2 在 $x_0 \in {1,g^4,g^8,g^{12},...}$ 处有效，而约束 1 在 ${g^2,g^6,g^{10},...}$ 处有效。约束 2 的消失多项式为

$ZD,2(x)=\prod(x-g^{4k})$

我们已经找到了解决方案，$ZD,2(x)=(x^{n/4}-1)$。对于约束 1，我们有

$ZD,1=\prod_{i\neq 0 \pmod{2}}(x-g^{2i})$

$i\neq 0 \pmod{2}$ 只是说乘积仅考虑 $i$ 的奇数值（因此排除 4 的倍数）的一种方式。我们可以应用与之前相同的技巧：

$ZD,1=\frac{\prod(x-g^{2i})}{\prod(x-g^{4k})}$

这可能看起来很奇怪，但我们确切地知道如何计算它们中的每一个：

$ZD,1(x)=\frac{x^{n/2}-1}{x^{n/4}-1}$

从这里，我们可以删除一些未强制执行约束的点。例如，如果它在 $x_0=6$ 处无效，

$ZD,1(x)=\frac{x^{n/2}-1}{(x^{n/4}-1)(x-g^6)}$

如果我们添加一个约束 $f_3(x,gx)$，该约束在步骤 ${32,64,92,...}$ 上强制执行，我们将有 3 个消失多项式，

$ZD,3=\frac{x^{n/32}-1}{x-1}$

$ZD,2=\frac{(x^{n/4}-1)(x-1)}{x^{n/32}-1}$

$ZD,1(x)=\frac{x^{n/2}-1}{x^{n/4}-1}$

因此，通过利用单位根的属性，我们可以强制执行周期性应用的约束。

总结

STARKs 是一种强大的工具，使我们能够证明计算的完整性。为此，STARKs 从程序的执行轨迹开始，并使用多项式插值每一列。为了查看轨迹是否有效，我们需要检查是否强制执行了计算给出的所有约束。这些约束可以与轨迹多项式组合；如果在步骤 $T$ 处保持约束，则生成的多项式 $P(x)$ 应可被 $(x-g^{T-1})$ 整除，或者等效地，存在一个多项式 $Q(x)$，使得 $P(x)=Q(x)(x-g^{T-1})$。如果多次应用约束，我们可以使用以下事实来简洁地表达它们：

• 多项式 $P(x)$ 可被 $x-x_0$ 形式的因子的乘积整除。
• 由于乘法子群的结构，我们可以轻松地移动约束。
• 乘法子群中所有元素的乘积产生 $x^n-1$，其中 $n$ 是子群的阶（元素数）。

这在性能和易于理解方面带来了优势。

最后，我们将尽快发布 STARKs 的初学者版本，敬请关注！

• 原文链接： blog.lambdaclass.com/per...
• 登链社区 AI 助手，为大家转译优秀英文文章，如有翻译不通的地方，还请包涵～