深入探索STARK世界中的DEEP FRI：通过一个具体的例子学习你的日常月亮数学

介绍

在 LambdaClass，我们正在构建 Lambdaworks，一个用于开发零知识应用的库。一个重要的证明系统是 STARKs (Scalable, transparent arguments of knowledge，可扩展的，透明的知识论证)。STARKs 是一个强大的工具，允许我们证明给定计算的完整性。有关 STARKs 的概述，你可以查看我们 之前的帖子 或 Starkware 提供的优秀教程，例如 STARK-101 （对于 rust 版本，你可以关注 此链接）以及关于 算术化 I 和 II 的帖子，还有 STARK 解剖。

在这篇文章中，我们将做一个 STARKs 的纸笔示例，以便我们可以按照生成和验证证明所需的所有步骤进行操作（但我们将跳过哈希部分）。一个需要指出的重要方面是，在这种情况下，我们对我们所做事情的安全性不感兴趣（但在现实生活中，这应该非常重要）。让我们跳到问题中......

问题陈述

假设我们想要计算一个由以下关系给出的序列：

$a_0 = 3$

$a_{n+1} = a_n^2$

该序列给出前一个数的平方，从值 3 开始。我们将使用素数 17（费马素数，$2^4 + 1$）作为模数，并且我们将理解所有模 17 完成的运算。 17 的优点在于它包含一个具有 16 个元素的乘法群，这对于 STARKs 很有用（通常，我们希望 $p-1$ 为 $2^m \times q$，其中 $m$ 应该足够大，而 $q$ 是奇素数）。序列的前四个元素是：

$a_0 = 3$

$a_1 = a_0^2 = 9$

$a_2 = a_1^2 = 9^2 = 81 \equiv 13 \pmod{17}$

$a_3 = a_2^2 = 13^2 = 169 \equiv 16 \pmod{17}$

第一步是将这些值解释为多项式在合适域上的求值。我们正在使用 $p = 17$，其乘法群有 16 个元素：{1,2,3,4,…,15,16}。我们将选择以下子群 $D_t = {1, 13, 16, 4}$，这恰恰是由 $13$ 模 $17$ 的所有幂形成的群：

$13^0 = 1$

$13^1 = 13$

$13^2 = 169 \equiv 16 \pmod{17}$

$13^3 \equiv 4 \pmod{17}$

$13^4 \equiv 1 \pmod{17}$

从现在开始，我们将省略 $\pmod{17}$，这是从上下文中理解的。我们看到 $13$ 的幂每 4 个重复一次，这是元素在乘法群中的阶。使用这个并且将插值迹的多项式称为 $t(x)$，我们有：

$t(1) = 3$

$t(13) = 9$

$t(16) = 13$

$t(4) = 16$

插值

我们可以使用拉格朗日插值来找到多项式（对于更大的问题，最好使用快速傅里叶变换）：

$t(x) = L_1(x)t(1) + L_2(x)t(13) + L_3(x)t(16) + L_4(x)t(4)$

拉格朗日多项式 $L_1(x)$ 由下式给出

$L_1(x) = \frac{(x-13)(x-16)(x-4)}{(1-13)(1-16)(1-4)}$

进行运算，我们得到

$L_1(x)t(1) = 5(x^3 + x^2 + x + 1)$

其他的多项式是

$L_2(x)t(13) = 8x^3 + 2x^2 + 9x + 15$

$L_3(x)t(16) = x^3 + 16x^2 + x + 16$

$L_4(x)t(4) = 16x^3 + 13x^2 + x + 4$

因此，迹插值多项式为

$t(x) = 13x^3 + 2x^2 + 16x + 6$

如果我们计算多项式在 $D_t$ 处的值，你可以检查我们是否获得了与迹执行表中的相同值。

提交到迹多项式

我们必须提交到迹插值多项式。为此，我们通过选择与原始域不同的更大的域来执行低次扩展。如果我们选择 $h = 9$ 及其幂，我们将得到一个具有 8 个元素的循环子群，${h^0, h^1, h^2, \dots, h^7}$。该群包含来自 $D_t$ 的元素，因此我们通过引入陪集的元素 $w$ 并形成以下域将其移动到另一个域，

$D_0 = {wh^0, wh^1, wh^2, \dots, wh^7}$

我们可以选择 $w = 3$，因此域变为

$D_0 = {3, 10, 5, 11, 14, 7, 12, 6}$

要提交，我们在 $D_0$ 中的所有值上计算 $t(x)$ 并形成一个 Merkle 树，其叶子是这些值。

输入约束

我们现在需要关注计算给出的迹元素上的约束。在这个问题中，我们有两个约束：

1. 边界条件。这适用于第一行，其中 $t(1) = 3$。
2. 过渡约束。这些由多元多项式 $P(x, y) = y - x^2$ 给出，其中如果 $x = an$，则 $y = a{n+1}$。

此时我们需要做的是将迹多项式与这些约束组合以在整个迹上强制执行它们。

边界约束

第一个约束是

$p_1(x) = t(x) - 3$

为了确保它在第一步中被强制执行，多项式 $p_1(x)$ 必须可被 $x-1$ 整除（多项式的一个属性是 $p(a) = b$ 当且仅当 $r(x) = p(x) - b$ 可被 $x-a$ 整除）。

我们有

$p_1(x) = 13x^3 + 2x^2 + 16x + 3$

如果我们分解这个多项式，我们得到

$p_1(x) = 13(x-1)(x^2 + 9x + 5)$

它有因子 $(x-1)$。如果我们除，我们得到

$C_1(x) = 13(x^2 + 9x + 5)$

你可以检查，如果我们想要 $t(x) - a$ 可以被 $x-1$ 整除，则必然 $a = 3$。

过渡验证约束

为了评估第二个约束，我们需要能够选择迹的一个元素和下一个元素。我们可以通过注意 $D_t$ 的元素由 $g = 13$ 生成来做到这一点，因此如果我们选择 $x = x_0$，则 $y = gx_0$ 是下一个。所以，$y = t(gx) = t(13x)$ 并且

$t(gx) = x^3 + 15x^2 + 4x + 6$

我们现在将这些多项式替换为过渡验证多项式 $P(x, y)$，以获得 $p_2(x)$

$p_2(x) = P(t(x), t(gx)) = x^6 + 16x^5 + 5x^4 + 2x^3 + 7x^2 + 16x + 4$

你可以检查，如果我们选择 $x \in {1, 13, 16}$，则多项式计算结果为 $0$。这是预期的，因为元素 $an$ 和 $a{n+1}$ 通过公式 $a_{n+1} = a_n^2$ 连接。 $4$ 的情况不再如此，因为没有下一个元素。与之前一样，如果约束有效，则 $p_2(x)$ 应可被 $Z_2(x)$ 整除，后者是在约束被强制执行的域上的消失多项式。在我们的例子中，

$Z_2(x) = (x-1)(x-13)(x-16)$

我们也可以将其写成

$Z_2 = \frac{x^4 - 1}{x - 4}$

在这里我们只是删除了约束未被强制执行的元素。我们验证了对于 $x \in {1, 13, 16}$，$p_2(x) = 0$，因此 $p_2(x)$ 具有因子 $(x-1)(x-13)(x-16)$。其完整分解为

$p_2(x) = (x-1)(x-13)(x-16)(x^3 + 12x^2 + 9x + 16)$

因此，

$C_2(x) = \frac{p_2(x)}{Z_2(x)} = x^3 + 12x^2 + 9x + 16$

（约束）组合多项式

我们现在处于构建组合多项式的条件

$H(x) = C_1(x)(\alpha_1 x^{D-D_1} + \beta_1) + C_2(x)(\alpha_2 x^{D-D_2} + \beta_2)$

其中 $\alpha_k$ 和 $\beta_k$ 是验证者提供的值。添加项 $x^{D-D_k}$ 是为了使线性组合中的所有多项式都具有相同的次数。我们希望总次数为 $2$ 的幂，因此 $D = 4$。

假设验证者将以下内容作为随机系数采样：$\alpha_1 = 1$、$\beta_1 = 3$、$\alpha_2 = 2$、$\beta_2 = 4$。 然后，

$C_1(x)(1x^{4-2} + 3) = 13x^4 + 15x^3 + 2x^2 + 11x + 8$

$C_2(x)(2x^{4-3} + 4) = 2x^4 + 11x^3 + 15x^2 + 13$

然后，

$H(x) = 15x^4 + 9x^3 + 11x + 4$

将多项式分成奇数项和偶数项，

$H_1(x^2) = 15x^4 + 4$

$H_2(x^2) = 9x^2 + 11$

以便

$H(x) = H_1(x^2) + xH_2(x^2)$

我们可以通过在 $D_0$ 上计算并形成 Merkle 树来提交到多项式 $H(x)$ 或其部分 $H_1(x)$ 和 $H_2(x)$。

在原始域之外采样

验证者现在选择一个随机点 $z$，该点位于迹插值和评估域之外。在我们的示例中，这些点之外的点是 {2,8,9,15}。假设验证者选择 $z = 8$。 然后，

$H(8) = 10$

每个部分都是

$H_1(8^2) = 6$

$H_2(8^2) = 9$

我们需要检查组合多项式和迹元素是否相关。为了能够以数值方式评估约束，我们需要 $t(z)$ 和 $t(gz)$ (记住，$g$ 是迹插值域的生成器)，因为我们必须计算 $P(x, y)$。 必要的值是：

$t(8) = 16$

$t(13 \times 8) = t(2) = 14$

为什么验证者需要这个？

验证者现在可以检查迹和组合多项式是否相关：

1. $p_1(8) = t(8) - 3 = 13$
2. $Z_1(8) = 8 - 1 = 7$
3. $C_1(8) = p_1(8) / Z_1(8) = 13 \times 7^{-1} = 14$
4. $C_1(8)(1 \times 8^2 + 3) = 3$
5. $p_2(8) = t(2) - t(8)^2 = 13$
6. $Z_2(8) = 8$
7. $C_2(8) = p_2(8) / Z_2(8) = 13 \times 8^{-1} = 8$
8. $C_2(8)(2 \times 8 + 4) = 7$
9. $H(8) = C_1(8) + C_2(8) = 3 + 7 = 10$

我们看到 $H_1(z^2)$ 和 $H_2(z^2)$ 的计算结果与来自迹元素的 $H(z)$ 的计算结果相匹配。

确保证明者不作弊

验证者如何检查我们传递的值确实是 $z$ 和 $gz$ 处的迹和组合多项式计算结果？我们可以使用相同的技巧：如果多项式 $y(x)$ 在 $x = a$ 中计算为 $b$，则 $y(x) - b$ 可被 $x - a$ 整除。 我们形成 DEEP 组合多项式，

$P_0(x) = \gamma_1 \frac{t(x) - t(z)}{x - z} + \gamma_2 \frac{t(x) - t(gz)}{x - gz} + \gamma_3 \frac{H_1(x^2) - H_1(z^2)}{x - z^2} + \gamma_4 \frac{H_2(x^2) - H_2(z^2)}{x - z^2}$

让我们计算每一项

$\frac{t(x) - t(8)}{x - 8} = 13(x+13)(x+3) = 13(x^2 + 16x + 5)$

$\frac{t(x) - t(2)}{x - 2} = 13(x+8)(x+2) = 13(x^2 + 10x + 16)$

$\frac{H_1(x^2) - H_1(8^2)}{x - 8^2} = 15(x+15)(x+8)(x+2)$

$\frac{H_2(x^2) - H_1(8^2)}{x - 8^2} = 9(x+8)$

每一项都是一个多项式，因此线性组合也是一个多项式。通过应用 FRI 协议，我们必须向验证者证明这接近于一个低次多项式。多项式是（使用 $\gamma_i = 1$），

$P_0(x) = 15x^3 + 15x + 1$

我们可以使用 $D_0$ 并形成 Merkle 树来提交到这个多项式，

分为奇数项和偶数项，

$xP_{0,odd}(x) = 15x^3 + 15x$

$P_{0,even}(x) = 1$

验证者采样 $\beta_0 = 4$。 然后，

$P_1(y=x^2) = 9y + 10$

该域由 $y = x^2$ 形式的点给出，因此 $D_1 = {9, 15, 8, 2}$。 Merkle 树的叶子是

我们重复这个过程，

$yP_{0,odd}(y) = 9y$

$P_{0,even}(y) = 10$

验证者采样 $\beta_1 = 3$

$P_2(z=y^2) = 3$.

我们以一个常数多项式结束。第二个域是 $D_2 = {13, 4}$

检查 FRI 层

为了生成证明，验证者从 $D_0$ 中选择一个元素。 我们必须将重构组合多项式和 FRI 步骤的评估所需的所有元素发送给他。 假设他选择 $x = 10$，这对应于等于 11 的索引。为了评估所有内容，我们必须传递 $x$ 和 $-x$ 处每个层的评估，以及在 $x$ 和 $gx$ 处评估的迹多项式。

从 $P_0(x)$ 我们传递值 $P_0(x=10) = 4$ 和 $P_0(x=7) = 15$，以及它们的身份验证路径。

从 $P_1(x)$ 我们传递值 $P_1(x=15) = 9$ 和 $P_1(x=2) = 11$ 以及它们的身份验证路径。

从 $P_2(x)$，我们只需要 $3$ 的常数值。

检查 FRI 的正确性需要验证每个值是否与其 Merkle 树和共线性测试相对应，

$P_{i+1}(x^2) = \frac{P_i(x) + P_i(-x)}{2} + \beta_i \frac{P_i(x) - P_i(-x)}{2x}$

让我们检查从每层的跳跃：

$P_1(15) = 16 = \frac{P_0(10) + P_0(7)}{2} + 4 \frac{P_0(10) - P_0(7)}{2 \times 10}$

我们可以看到

$\frac{P_0(10) + P_0(7)}{2} = 1$

和

$4 \frac{P_0(10) - P_0(7)}{2 \times 10} = 8$

让我们跳到下一层，

$P_2(y^2) = \frac{P_1(y) + P_1(-y)}{2} + \beta_1 \frac{P_1(y) - P_1(-y)}{2y}$

替换这些值，

$P_2(y^2) = 3$

和

$\frac{P_1(15) + P_1(2)}{2} = 10$

$3 \frac{P_1(15) - P_1(2)}{2 \times 15} = 10$

但是

$10 + 10 = 3 = P_2(4)$

完成检查。 你可以尝试选择其他指数并验证证明。

唯一剩下的检查表明迹和组合多项式是相关的。 我们将其作为一个挑战留给读者（答案将很快出现）

总结

这篇文章介绍了使用 STARKs 进行计算完整性的纸笔示例。 我们选择了一个序列，其中每个元素都是前一个元素的平方，从 3 开始。我们陈述了问题，将计算解释为在合适的域上评估多项式，并执行了拉格朗日插值。 之后，我们强制执行执行迹上的约束并获得了组合多项式。 为了提高稳健性，我们强制证明者在域之外的点 $z$ 处进行评估，并表明迹和组合多项式是相关的。 然后，我们创建了一个有理函数，以确保证明者没有作弊并发送了正确的值。 如果证明者是诚实的，那么结果函数就是一个多项式，我们通过使用 FRI 表明它接近于一个低次多项式。 如果你想尝试更复杂的例子，请关注 Lambdaworks 的更新。

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