Circle STARKs 介绍

介绍

可扩展的、透明的知识论证（STARKs）由于其在可验证计算和区块链可扩展性方面的应用而受到了广泛关注。我们可以使用 STARKs 生成一个简短的字符串，证明计算的完整性，并且验证者可以非常快速地验证它。生成 STARK 证明的步骤包括：

1. 将计算表示为多项式约束/方程组。这可以是代数中间表示（AIR）或 Plonkish 算术化。在本文的剩余部分，我们将使用 AIR。
2. 获取程序的执行轨迹。
3. 将执行轨迹的每一列解释为单变量多项式在某个平滑域 $D$ 上的求值结果（此步骤称为插值）。
4. 在更大且不相交的域 $D_0$ 上评估轨迹多项式，并使用这些评估结果构建一个 Merkle 树。
5. 对轨迹多项式强制执行约束。
6. 为了确保满足这些约束，将步骤 5 中的每个多项式除以约束成立集合上的消失多项式。如果除法的结果是一个多项式，则表示满足了约束。
7. 如果有很多多项式，从验证者那里获取随机值以执行线性组合；如果结果是一个多项式，则高概率地约束成立。
8. 在 $D_0$ 上评估结果函数，并从这些评估结果构建一个 Merkle 树。
9. 为了表明这些评估结果属于一个至多为 $n$ 阶的多项式（而不是更高阶或有理函数），应用 FRI 协议。

STARKs 的效率取决于在平滑域上工作，在那里我们可以使用基数-2 Cooley-Tukey 快速傅里叶变换（FFT）来执行快速插值和求值。如果 $p-1 = 2^mc$，其中 $m$ 足够大，且 $c$ 是一个奇数，我们就说这个域是平滑的。 具有此属性的域的示例包括 STARK-252、$2^{64} - 2^{32} + 1$（有时称为 Mini-Goldilocks 或 oxfoi 素数）、 $2^{31} - 2^{27} + 1$（Baby Bear）。

STARKs 的主要优点之一是，我们可以在“小域”上工作（它们的大小小于密码安全性所需的大小），从而减少了表示执行轨迹/虚拟机中的变量所需的开销。然后，我们可以从一个扩展域中采样随机性，以实现密码安全性。Binius 展示了如何使用二进制域以零开销表示变量。

在本文中，我们将解释 Circle STARKs，如何使用圆群来访问非常快的模算术，以及为什么我们需要某些属性才能在圆群上执行 STARKs。为此，我们需要开发经典 STARKs 的圆形类似物：二元多项式、平滑域、圆代码、消失多项式、FFT 和 FRI。虽然许多东西看起来与它们的经典类似物非常接近，但出现了一些微妙之处和特殊的限制或点，我们应该小心。如果你想看看这些原语是如何实现的，可以查看 Starkware 的 prover Stwo、Polygon 的 Plonky3 和 Vitalik 的 python 实现。如果你需要回顾一下经典 STARKs，请参阅 post 1 和 post 2。

梅森素数

梅森素数的形式为 $2^p - 1$，其中 $p$ 是素数（对于每个素数 $p$， $2^p - 1$ 并不总是素数）。它们具有很好的归约公式（因为 $2^p \equiv 1 \pmod{2^p - 1}$），并且可以进行非常快的模算术运算（这反过来对 STARKs 的性能至关重要）。一些梅森素数是：

• $2^2 - 1 = 3$
• $2^3 - 1 = 7$
• $2^5 - 1 = 31$
• $2^7 - 1 = 127$
• $2^{31} - 1 = 2147483647$
• $2^{61} - 1$
• $2^{127} - 1$

在 STARKs 中使用梅森素数的问题是 $p - 1 = 2c$，其中 $c$ 是奇数，这意味着它们不平滑。这样，我们就无法使用 FFT 有效地执行插值。解决这个问题的方法是让插值域位于梅森素数的二次扩展中，如 此处 所述。但是，这种方法不太适合约束评估（商计算），从而限制了 zkvms 中经常遇到的轨迹的性能。

可以通过切换到由梅森素数给出的域上的圆曲线 $x^2 + y^2 = 1$ 来避免这些缺点。圆，配备了从域上的旋转群继承的操作，是一个循环群。此外，元素的数量等于 $q + 1$。对于梅森素数，这意味着 $q + 1 = 2^p$。

梅森素数也满足 $q \equiv 3 \pmod{4}$，这意味着 $x^2 + 1$ 在 $q$ 上是不可约的。我们将让 $i$ 满足 $i^2 = -1$，并使用 $F_q$ 的扩展 $F$。为了与论文的表示法保持一致，$F(i)$ 是基域 $F$ 的二次扩展。

多项式

我们将 $F[x]_d$ 表示阶数至多为 $d$ 的单变量多项式，并将 $F[x,y]_d$ 表示阶数至多为 $d$ 的二元多项式。例如，$x + 2x^5 + x^{34}$ 在 $Fq[x]{36}$ 中，但 $x^{56} + 1$ 不在。类似地，$1 + xy^2 + x^{34} + y^{35} + x^{12}y^{12}$ 在 $Fq[x,y]{64}$ 中，但 $x^{32}y^{34} + x^{12} + 25$ 不在。

在 circle STARKs 中，我们将处理模 $x^2 + y^2 - 1$ 的二元多项式。由于 $y^2 = x^2 - 1$，我们总是可以将多项式 $F[x,y]_d$ 表示为

$f(x,y) = f_0(x) + yf_1(x)$

我们称之为多项式的规范表示。例如，假设我们有以下多项式

$p(x,y) = x + 4y^3 + 5x^2y^5 + xy^6$

我们可以替换 $y^2 = x^2 - 1$ 得到

$p(x,y) = x + 4y(x^2 - 1) + 5x^2y(x^2 - 1)^2 + x(x^2 - 1)^3$

由此，我们得到

$f_0(x) = x + x(x^2 - 1)^3$

$f_1(x) = 4(x^2 - 1) + 5x^2(x^2 - 1)^2$

这种分解对于计算 circle FFT 和 FRI 非常有用。$f_0(x)$ 和 $f_1(x)$ 的一个优点是它们都是单变量的，这将为后续步骤带来额外的简单性和性能（我们唯一需要注意的是 $x$ 的平方映射的结构。代替 $x \rightarrow x^2$，我们有 $x \rightarrow 2x^2 - 1$）。

圆群

圆上的点是满足方程 $x_0^2 + y_0^2 = 1$ 的点对 $(x_0, y_0)$（坐标在域 $F$ 中）。我们可以通过考虑以下运算来引入群结构，

$(x_0, y_0) \cdot (x_1, y_1) = (x_0x_1 - y_0y_1, x_0y_1 + x_1y_0)$

如果我们固定 $P = (P_x, P_y)$，我们可以定义由 $P$ 旋转，$T_P(x, y) = (x_0P_x - y_0P_y, x_0P_y + P_xy0)$。当我们需要评估转移约束时，此操作非常重要。例如，如果我们想检查我们是否正在计算斐波那契数列，我们需要证明 $a{n+2} = a_{n+1} + a_n$。 如果我们有轨迹多项式 $t(x)$，我们可以通过乘以 $\omega$（插值域的生成元），得到 $x$ 的下一个元素，并使斐波那契约束为 $t(\omega^2x) = t(\omega x) + t(x)$。 如果我们选择 $P$ 作为（圆）插值域的生成元，我们可以使用相同的想法来编写这些约束。

逆可以很容易地计算出来：如果 $P = (x, y)$，则 $-P = (x, -y)$。

一个重要的映射是平方映射，$\pi(x, y) = (x^2 - y^2, 2xy) = (2x^2 - 1, 2xy)$。我们可以看到，第一个分量仅取决于 $x$。当作用于子群或特殊陪集（称为孪生位置陪集）时，平方映射会产生一个二对一的归约。圆群上的运算在 Stwo 中实现。

要了解有关圆上的域或陪集类型的更多信息，请参阅 Plonky3 的实现。

圆代码

圆代码是通过在 $F_q$ 上的圆群的一个合适的子集 $D$ 上评估多项式 $f(x, y)$ 获得的。可以证明，它与 Reed-Solomon 码存在一一对应关系（基本上，圆代码就是 Reed-Solomon 码）。

消失多项式

在经典 STARKs 中，我们需要计算集合上的消失多项式，然后生成商。我们需要找到这些消失多项式在 circle STARKs 中的样子。有趣的结果是，消失多项式将是单变量的，$v(x)$。 阶数为 $n$ 的消失多项式可以在 $\log(n)$ 个运算中有效地计算出来：一次平方、一次加倍和一次减一。消失多项式是：

$v_1(x) = x$

$v_2(x) = 2x^2 - 1$

$v_3(x) = 2(x^2 - 1)^2 - 1$

$v_4(x) = 2((x^2 - 1)^2 - 1)^2 - 1$

$v_5(x) = 2(((x^2 - 1)^2 - 1)^2 - 1)^2 - 1$

你可以查看如何在 Stwo 中评估消失多项式。

与经典 STARKs 的情况一样，如果 $v_H(x)$ 和 $v_J(x)$ 是集合 $H$ 和 $J$ 上的消失多项式，则商 $v_H(x) / v_J(x)$ 是 $H \setminus J$ 上的消失多项式。 这样，我们可以有效地计算应用于 $H \setminus J$ 的约束。

Circle FFT

逆 FFT 接受一个评估向量，并生成多项式在某个基上的坐标。FFT 接受基上的坐标，并生成一组评估。我们习惯于使用单项式基 $1, x, x^2, x^3, \dots x^n$，但还有其他可用选项。在 circle FFT 的情况下，基看起来更复杂，但请记住，我们想要的只是将值编码为多项式，然后在更大的域上评估它们。对于涉及 $n$ 个元素的 FFT，令 $j_0j_1j2\dots j{n-1}$ 是 $0 \le k \le n-1$ 的二进制分解，即 $k = j_0 + 2j_1 + 4j2 + \dots 2^{n-1}j{n-1}$。第 $k$ 个基多项式由下式给出：

$b_k(x, y) = y^{j_0}v_1(x)^{j_1}v_2(x)^{j2}\dots v{n-1}(x)^{j_{n-1}}$

为了澄清表达式，这里我们有第一个基多项式，

$b_0(x) = 1$

$b_1(x) = y$

$b_2(x) = v_1(x) = x$

$b_3(x) = yv_1(x) = xy$

$b_4(x) = v_2(x) = 2x^2 - 1$

$b_5(x) = yv_2(x) = y(2x^2 - 1)$

$b_6(x) = v_1(x)v_2(x) = x(2x^2 - 1)$

如果我们需要在 $\beta n$ 个点上评估一个 $n$ 阶多项式，$\beta \ge 2$，我们可以毫无问题地对多项式进行零填充。

在 FFT 的第一步中，我们使用多项式的规范表示的拆分，$p(x, y) = f_0(x) + yf_1(x)$。 以下步骤处理单变量多项式 $f_j(x)$，我们可以在其中应用偶奇分解，同时考虑到平方映射遵循圆运算。换句话说，

$f_{j,e}(2x^2 - 1) = (f_j(x) + f_j(-x)) / 2$

$f_{j,o}(2x^2 - 1) = (f_j(x) - f_j(-x)) / 2x$

我们可以继续分解所有内容，直到我们可以直接求解 FFT，使用 蝴蝶。

第一步的旋转因子与第二步使用的旋转因子不同。

circle STARKs 中的其他变化

当我们对轨迹多项式施加约束并计算商时，我们得到组合多项式。它的阶数取决于约束的最大阶数，我们可能需要将其分成几个块。在单变量的情况下，我们可以按如下方式进行分解：

$p(x) = p_0(x) + x^{n+1}p_1(x) + x^{2n+2}p_2(x)$

每个 $p_k(x)$ 的阶数最多为 $n$。在 circle STARKs 中，分解为函数 $q_1, q_2, \dots q_d$ 和参数 $\lambda$，使得

$p = \lambda v_H(x) + \sum_k v_H qk / v{H_k}$

其中 $H_k$ 是大小为 $n$ 的不相交孪生陪集，它们的并集产生 $H$。 由于论文中讨论的维度差距，需要额外的参数 $\lambda$。

Circle FRI 在经典 FRI 方面面临一些修改。 首先，我们需要将我们将应用 FRI 的函数分解为 $f = g + \lambda v_n(x)$。 这种分解对于确保函数空间在每个折叠步骤中减半，并在协议结束时达到常数函数空间至关重要。折叠遵循与我们在 circle FFT 中遇到的类似的程序；在第一次折叠后，我们必须处理单变量函数和平方映射 $x \rightarrow 2x^2 - 1$。

总结

Circle STARKs 通过利用梅森素数（具有已知的最快有限域算术）已经显示出 惊人的性能。它们能够通过移动到圆群来绕过在梅森素数上定义的域的非平滑结构，但密切遵循其经典的 STARKs 类比（尽管有一些细微之处）。 幸运的是，大多数这些细微之处都对开发人员隐藏了，并且 circle STARKs 以及有效的查找（例如那些基于 LogUp 和 GKR 的查找）可以帮助提高通用 zkvms 的性能。

我们采访了正在开发 Iroh 的团队，Iroh 是一个即开即用的 Rust 点对点库。

介绍 互动证明是证明者 PP 和验证者 VV 之间的协议，其中证明者试图使验证者确信声明的有效性。 通过利用随机性和交互性，验证者可以比通过做所有事情更有效地检查状态。

TL;DR: 这篇文章讨论了 Pod，一种新的共识概念，通过消除副本间通信，实现了单次往返（约 200 毫秒）的最佳延迟。 我们认为这篇论文和 pod 网络的工作是开创性的，我们希望其他人分享我们对他们工作的兴奋和热情，

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