Circle STARKs：第四部分，圆的算术化

回顾

• 在第一部分中，我们提出了使用梅森素数域进行快速模运算的动机，并详细说明了非平滑乘法群如何阻止 STARK 的实例化。
• 在第二部分中，我们描述了圆曲线和域：双陪集和标准位置陪集。我们还描述了圆曲线上的多项式，并构造了两个域上的消失多项式。
• 在第三部分中，我们描述了 Circle FFT 算法，它是一种 Cooley-Tukey 风格的算法，使我们能够在圆曲线上二元多项式的求值和系数表示之间移动。我们还定义了 Circle FFT 算法引起的基，以及圆曲线上二元多项式空间与 Circle FFT 插值多项式空间之间的维度差。

介绍

这最后一篇文章将我们之前在第一部分到第三部分中构建的所有内容 Stitch 在一起。我们的目标是展示这些成分如何组合成一个完整的 Circle STARK。

我们首先描述圆曲线上的算术化。从那里，我们介绍 Circle FRI，这是一种低阶测试，以确保多项式满足阶数约束。最后，我们将介绍 Circle STARK 的构造。

算术化

执行轨迹只是计算的记录：每一行捕捉一个步骤或一个时钟周期，每一列记录一个寄存器的演变，并且每个条目都存在于梅森素数域 $Fp$ 中。如果计算有 $N$ 个周期并且在 $w$ 个寄存器上运行，则轨迹表的大小为 $N \times w$。算术化是将此表的局部转换规则编码为在整个域上成立的多项式恒等式，以便对计算的推理简化为检查多项式的求值。

我们根据具有 $N = 2^n$ 行和 $w$ 列的轨迹表来定义我们的计算。此表中的每个单元格都是来自 $Fp$ 的元素。我们可以使用 $w$ 个列向量来定义整个轨迹：

$t_1,…,t_w \in F_p^N$

假设 $H$ 是大小为 $N = 2^n$ 的标准位置陪集。我们将使用 Circle FFT 在 轨迹域 $H$ 上插值每个轨迹列 $t_i$，以获得圆曲线上的二元多项式 $p_i$。多项式 $p_i$ 属于圆曲线上的二元多项式空间，即 $p_i \in L_N(F_p), i = 1,…,w$

证明者通过在 求值域 $D$ 上提交其求值来提交列多项式 $p_i$，该求值域 $D$ 的大小比轨迹域 $H$ 大一个因子 $2^B$，即

$|D||H| = 2^B, |D| = 2^{B+n}$

其中 $B \geq 1$。$p_i$ 在求值域 $D$ 上的求值使用 Merkle 树进行提交。

现在我们想在轨迹表上添加约束。假设我们总共添加了 $C$ 个约束。为简单起见，我们仅描述相邻行上的约束，如下所示：

$P_j(s_j, p_1,…, p_w, p_1 \circ T_G,…, p_w \circ T_G) = 0, j = 1,…,C$

这里，$p_i \circ T_G$ 表示列多项式 $p_i$ 上由生成器 $G$ 进行的平移，其中 $T_G(P) = G \cdot P$。轨迹域是 $H = Q \cdot G^n$ 的陪集，其中 $G^n$ 是大小为 $N = 2^n$ 的子群，$Q$ 是一个偏移量。每列 $p_i$ 都在轨迹域 $H$ 上进行插值，表示为：

$H = Q \cdot G^n = {Q, Q \cdot G, Q \cdot G^2,…, Q \cdot G^{2^n-1}}$

因此，$p_i \circ T_G$ 拉入轨迹的“下一行”。约束 $P_j$ 是根据列多项式 $p_i$ 和预定义的选择器多项式 $s_j$ 定义的多项式，该选择器多项式确定约束 $P_j$ 应应用在哪些行上。

注意

这些选择器多项式 $s_j$ 看起来像什么？

它们属于哪个多项式空间？

假设我们想在子域 $H_j \subset H$ 上应用约束 $P_j$。那么，对于 $H_j$ 中的点，选择器多项式 $s_j$ 应求值为某个非零值，对于 $H \setminus H_j$ 中的点，应求值为零值。描述 $s_j$ 的另一种方式是它应该在 $H_j$ 之外消失。它们定义如下： $s_j = \frac{vH}{v{H_j}}$ 其中 $vH$ 和 $v{H_j}$ 分别是 $H$ 和 $H_j$ 的消失多项式。

即使 $s_j$ 被定义为有理函数，在圆曲线上它也是一个多项式。原因是全局消失多项式 $vH$ 在较小的域 $v{H_j}$ 上消失，因此 $vH$ 可被 $v{H_j}$ 整除。因此，比率 $vH/v{H_j}$ 没有极点。有关更多详细信息，请参阅 引理 10，Circle STARKs。

我们知道 $\deg(v_H) = 2^n - 1 = N/2$ 并且 $v_H \in L_N(F_p)$（请参阅维度差，第三部分）。因此，$s_j$ 也属于多项式空间 $L_N(F_p)$。

现在，我们不是单独证明所有 $C$ 个约束，而是将它们批量处理成一个约束。验证者从 $F_p$ 的扩展域 $F$ 中选择一个随机 $\beta$。证明者计算以下内容：

$\sum_{j=1}^C \beta^{i-1} P_j(s_j, p_1,…, p_w, p_1 \circ T_G,…, p_w \circ T_G) = 0$

为了证明上述恒等式在整个轨迹域 $H$ 上的有效性，证明者计算商多项式 $q$ 如下：

$\sum_{j=1}^C \beta^{i-1} P_j(s_j, p_1,…, p_w, p_1 \circ T_G,…, p_w \circ T_G) = q \cdot v_H$

必须存在这样的商 $q$，因为如果在整个 $H$ 中满足所有约束，则左侧在 $H$ 上消失，因此可被 $v_H$ 整除。

注意

商多项式 $q$ 的阶数是多少？

它属于哪个多项式空间？

设每个 $P_j$ 的阶数最多为 $d$。多项式 $s_j, p_i,…, p_w, p_i \circ T,…, p_w \circ T$ 在空间 $L_N(Fp)$ 中，最大阶数为 $N/2$。因此，以下表达式左侧的最大阶数为 $d N/2$。 $\sum{j=1}^C \beta^{i-1} P_j(s_j, p_1,…, p_w, p_1 \circ T_G,…, p_w \circ T_G) = q \cdot v_H$ 现在 $vH$ 的阶数为 $N/2$。因此，$q$ 的阶数为 $(d-1)N/2$ 并且 $q$ 在多项式空间 $q \in L{(d-1)N}(F)$ 中。请注意，$q$ 位于扩展域 $F$ 上，因为 $\beta$ 是从 $F$ 采样的。

现在，证明者必须证明列多项式 $pi$ 的阶数 $\leq N/2$，商多项式 $q$ 的阶数 $\leq (d-1)N/2$。为了使所有多项式的阶数界限一致（即 $\leq N/2$），商多项式 $q \in L{(d-1)N}(F)$ 被拆分为多项式 $q1,…,q{d-1} \in L_N(F)$ 如下：

$q = \lambda \cdot \overline{vH} + \sum{k=1}^{d-1} \frac{\overline{vH}}{v{H_k}} \cdot q_k$

其中 $\overline{H} = \bigcup_{k=1}^{d-1} H_k$ 是大小为 $|H_k| = N$ 的双陪集的非相交并集。

注意

商多项式 $q$ 分解的直觉

商多项式 $q$ 属于空间 $L{(d-1)N}(F)$，其维度为 $(d-1)N+1$。$q$ 的分解来自多项式空间 $L{(d-1)N}(F)$ 的分解，它可以分解如下： $L_{(d-1)N}(F) = \langle \overline{vH} \rangle + L'{(d-1)N}(F)$ 其中空间 $L'_{(d-1)N}(F)$ 的维度为 $(d-1)N$。

上述分解与 维度差，第三部分 中 $L_N(F)$ 的分解非常相似。 $L_N(F) = \langle v_n \rangle + L'_N(F)$

现在我们可以进一步分解来自空间 $L'_{(d-1)N}(F)$ 的多项式，作为来自空间 $L'N(F)$ 的 $(d-1)$ 个多项式，并结合 $L'{(d-1)N}(F)$ 在 $L'_N(F)$ 上的某个基，即 $q_k$ 是来自空间 $L'_N(F)$ 的 $(d-1)$ 个多项式，而 $\frac{\overline{vH}}{v{Hk}}$ 是 $L'{(d-1)N}(F)$ 在 $L'_N(F)$ 上的基。

这给出了商多项式 $q$ 分解的直觉。有关完整的证明，请参阅 引理 12，Circle STARKs。

因此，证明者必须证明以下等式的有效性：

(1) $\sum_{j=1}^C \beta^{i-1} P_j(s_j, p_1,…, p_w, p_1 \circ T_G,…, p_w \circ T_G) = (\lambda \cdot \overline{vH} + \sum{k=1}^{d-1} \frac{\overline{vH}}{v{H_k}} \cdot q_k) \cdot v_H$

并证明多项式 $p_i, q_k$ 的阶数 $\leq N/2$。我们现在将描述 Circle FRI 来证明后者。

Circle FRI

Circle FRI 测试函数 $f \in F^D$ 在大小为 $|D| = 2^{n+B}$ 的求值域 $D$ 上与多项式空间 $L_N(F)$ 中的某个多项式 $p(x,y)$ 的接近程度。函数 $f \in F^D$ 表示为域 $D$ 上的求值向量。

这里：

• $F$ 是 $F_p$ 的字段扩展
• $B$ 是 blowup 因子 $2^B$ 的对数
• $L_N(F)$ 是圆曲线上的二元多项式空间，它可以分解如下（如 维度差，第三部分 中所述）：

$L_N(F) = L'_N(F) + \langle v_n \rangle$

注意

为什么要检查与多项式的接近程度？

证明者将函数的求值发送给验证者。但是，验证者不知道此函数是否是多项式，或者它是否满足预先指定的阶数界限。FRI 允许验证者检查证明者发送的求值是否确实“接近”某个有界阶数的多项式。在这里，验证者仅检查接近程度；也就是说，即使证明者发送的求值“足够接近”有界阶数的多项式，验证者也会接受。

Circle FRI 遵循与 Circle FFT 算法类似的 divide-and-conquer 策略。证明者递归地分解函数并使用验证者发送的随机性折叠奇数和偶数部分。这种减少会一直持续到折叠函数与多项式空间的接近程度测试足够小，验证者可以直接检查；在这种情况下，证明者直接将折叠函数发送给验证者。

下图显示了使用 2-to-1 映射链的 circle FRI 算法的域序列，其中 $r$ 折叠轮。

如上图所示，我们使用了两种不同的映射，就像在 circle FFT 算法中一样：投影映射 $\pi_x$ 和平方映射 $\pi$。该协议从大小为 $2^m$ 的标准位置陪集 $D_m$ 开始，其中 $m = B+n$，然后使用映射 $\pi_x$ 投影到 x 轴上以计算商 $Dm/J$。然后连续应用映射 $\pi$ 进行 $(r-1)$ 轮以获得具有 $2^{m-r}$ 个元素的商 $D{m-r+1}/J$。要了解有关这些映射的更多信息，请参阅 Circle FFT 的域序列，第三部分。为方便起见，我们将第 $j$ 轮的域和映射分别定义为 $S_j$ 和 $\pi_j$。

在 Circle FRI 的每个步骤中，证明者将按照上述描述对域序列上的函数进行分解和折叠。但是在折叠之前，证明者将 $f \in L_N(F)$ 分解为：

$f = g + \lambda \cdot v_n$，

其中 $g$ 来自 FFT 空间 $L'_N(F)$，$\lambda \in F$，并且 $v_n$ 是大小为 $N = 2^n$ 的标准位置陪集的消失多项式。这会将 $f$ 与 $L_N(F)$ 的接近程度声明降低为 $g$ 与 FFT 空间 $L'_N(F)$ 的接近程度声明，这通过重复折叠 $g$ 来检查。

我们从 $g = g_0 \in F^{S_0}$ 与 FFT 空间 $L(0) = L'N(F)$ 的接近程度声明开始。在每一轮 $j = 1,…,r$ 中，我们将先前 $g{j-1} \in F^{S_{j-1}}$ 与 $L(j-1)$ 的接近程度声明降低为新的 $g_j \in F^{S_j}$ 与 FFT 空间 $L(j)$ 的接近程度声明，其中

$L(j) = F[X] < N/2^j$

我们现在将详细解释完整的协议和上述简化。证明者有一个函数 $f \in F^D$，并且验证者被赋予对 $f$ 的 oracle。该协议包括一个 提交阶段 和一个 查询阶段。

提交阶段

• 分解：证明者分解 $f = g + \lambda \cdot v_n$ 并将 $\lambda$ 发送给验证者。
• 折叠：证明者持有函数 $g = g_0 \in F^{S_0}$，它想证明其与 $L(0) = L'_N(F)$ 的接近程度。
  • 对于第一轮折叠，即 $j = 1$，
  • 验证者发送一个随机挑战 $\lambda_1 \in F$。
  • 证明者使用映射 $\pi_1 = \pi_x$ 分解函数 $g_0$ 如下： $g0(X,Y) = g{0,0}(\pi1(X,Y)) + Y \cdot g{0,1}(\pi_1(X,Y))$ $g0(X,Y) = g{0,0}(X) + Y \cdot g{0,1}(X)$ 其中 $g{0,0}, g_{0,1} \in F^{S1}$ 如下： $g{0,0}(X) = \frac{g_0(X,Y) + g0(X,-Y)}{2}, g{0,1}(X) = \frac{g_0(X,Y) - g_0(X,-Y)}{2 \cdot Y}$ 正如我们在 维度差，第三部分 中所见，我们还可以分解由 Circle FFT $L'_N(F)$ 插值的多项式空间，如下所示： $L'_N(F) = F[X] < N/2 + Y \cdot F[X] < N/2$ 因此，我们已经将检查 $g_0$ 与 $L(0) = L'N(F)$ 的接近程度的任务简化为检查 $g{0,0}$ 和 $g_{0,1}$ 与 $L(1) = F[X] < N/2$ 的接近程度。但是，我们不是检查两个接近程度声明，而是使用来自验证者的随机挑战 $\lambda_1$ 将它们折叠成一个接近程度声明。 (2) $g1(X) = g{0,0}(X) + \lambda1 \cdot g{0,1}(X)$ 因此，在第一轮之后，我们已将 $g_0 \in F^{S_0}$ 与 $L(0) = L'_N(F)$ 的接近程度声明降低为 $g_1 \in F^{S_1}$ 与 $L(1) = F[X] < N/2$ 的接近程度声明。
  • 对于后续轮，即 $j = 2,…,r$，我们使用相同的过程。唯一的区别是我们在每一轮使用平方映射 $\pi$，即 $\pi_j = \pi$。对于第 $j$ 轮，
  • 验证者发送一个随机挑战 $\lambda_j \in F$。
  • 证明者分解来自前一轮的函数 $g{j-1} \in F^{S{j-1}}$ 如下： $g{j-1}(X) = g{j-1,0}(\pij(X)) + X \cdot g{j-1,1}(\pij(X))$ $g{j-1}(X) = g{j-1,0}(2X^2-1) + X \cdot g{j-1,1}(2X^2-1)$ 其中 $g{j-1,0}, g{j-1,1} \in F^{S{j-1}}$ 如下： $g{j-1,0}(2X^2-1) = \frac{g{j-1}(X) + g{j-1}(-X)}{2}, g{j-1,1}(2X^2-1) = \frac{g{j-1}(X) - g{j-1}(-X)}{2 \cdot X}$ 证明者折叠函数 $g{j-1,0}, g_{j-1,1} \in F^{S_j}$ 如下： (3) $gj(X) = g{j-1,0}(X) + \lambdaj \cdot g{j-1,1}(X)$ 因此，在第 $j$ 轮之后，我们已将 $g{j-1} \in F^{S{j-1}}$ 与 $L(j-1) = F[X] < N/2^{j-1}$ 的接近程度声明降低为 $g_j \in F^{S_j}$ 与 $L(j) = F[X] < N/2^j$ 的接近程度声明。
  • 对于每一轮，证明者向验证者发送一个 $g_j$ 的 oracle。在最后一轮中，证明者以明文形式发送 $g_r \in F^{S_r}$，验证者可以直接检查 $g_r$ 与多项式空间 $L(r)$ 的接近程度声明。

查询阶段

在查询阶段，验证者检查证明者是否使用证明者发送的 oracle 正确计算了折叠。它包括 $s \geq 1$ 轮。在每一轮中：

• 验证者采样 $(x_0, y_0) \in D$ 并将每个映射应用于元素 $(x_0, y_0)$ 以获得沿投影轨迹的每个域的元素，如下所示： $x_j = \pij(x{j-1}), \text{对于 } j \in {1,…,r}$ 然后，验证者查询 oracle，以获取 $f$ 和 $g_j$ 在上述投影轨迹的点上的值。

• 验证者检查第一轮折叠，即在 $(x_0, y_0)$ 处检查等式 (2)，如下所示。请注意，这里 $X_1 = \pi_1(x_0) = x_0$，因为 $\pi_1$ 是投影映射 $\pi_x$。 $g_1(x_0) \stackrel{?}{=} (\frac{g_0(x_0,y_0) + g_0(x_0,-y_0)}{2}) + \lambda_1 \cdot (\frac{g_0(x_0,y_0) - g_0(x_0,-y_0)}{2 \cdot y_0})$

• 验证者检查后续轮的折叠，即对于所有 $j = {2,…,r}$，检查： $g_j(xj) \stackrel{?}{=} (\frac{g{j-1}(x{j-1}) + g{j-1}(-x_{j-1})}{2}) + \lambdaj \cdot (\frac{g{j-1}(x{j-1}) - g{j-1}(-x{j-1})}{2 \cdot x{j-1}})$

如果所有上述检查对所有 $s$ 轮都通过，则验证者接受，否则拒绝。

安全性分析

在本节中，我们将对 FRI 协议的安全性进行一些直观的分析。证明者大致可以通过两种方式作弊：

• 函数 $f \in F^D$ “远离”多项式空间 $L_N(F)$，但不知何故，证明者很幸运，最终得到了“接近”$L(r)$ 的 $g_r$。接近间隙论文 分析了这种情况发生的概率可以忽略不计。也就是说，如果即使其中一个函数 $f$ “远离”多项式空间 $L_N(F)$，则 $g_r$ 函数将很可能“远离”$L(r)$。
• 现在假设 $f \in F^D$ “远离”多项式空间 $L_N(F)$，则 $g_r$ 函数将“远离”$L(r)$，但为了欺骗验证者，证明者在折叠轮中作弊并发送一些有效的 $g_r \in L(r)$。现在，验证者必须确保证明者使用证明者发送的 oracle 在每一轮中正确执行了折叠。这正是验证者在查询阶段检查的内容。从“玩具问题猜想”（ethSTARK，第 5.9 节），验证者所做的每个查询都提供 $B$（即 blowup $2^B$ 的对数）位的安全性。因此，对于 $s$ 个查询，安全性为 $s \cdot B$ 位。

Circle STARK

在本节中，我们将结合到目前为止在本系列中介绍的所有想法来构建 Circle STARK 协议。给定轨迹表作为长度为 $N = 2^n$ 的 $w$ 列，即

$t_1,…,t_w \in F_p^N$

该协议的流程如下：

1. 轨迹承诺：证明者使用 circle FFT 将每个轨迹列 $t_i$ 作为轨迹域 $H$ 上的二元多项式 $p_i$ 进行插值。然后计算求值域 $D$ 上的多项式 $p_i$，并使用 Merkle 树承诺求值向量。证明者将每个 $p_i$ 求值的 Merkle 承诺发送给验证者。

2. 算术化：验证者发送随机 $\beta$ 以批量处理所有约束。证明者计算 $q$ 并将其分解以获得 $\lambda$ 和 $q_k$ 多项式。像轨迹多项式一样，每个 $q_k$ 都在 $D$ 上提交。证明者将每个 $q_k$ 和 $\lambda$ 求值的 Merkle 承诺发送给验证者。现在证明者必须证明等式 (1) 的有效性，即

$\sum_{j=1}^C \beta^{i-1} P_j(s_j, p_1,…, p_w, p_1 \circ T_G,…, p_w \circ T_G) \stackrel{?}{=} (\lambda \cdot \overline{vH} + \sum{k=1}^{d-1} \frac{\overline{vH}}{v{H_k}} \cdot q_k) \cdot v_H$

3. 打开：上述恒等式在扩展域上圆上的域外点上进行检查。验证者采样 $\gamma \in C(F) \setminus (D \cup H)$ 并请求证明者打开 $p_i$ 和 $q_k$。证明者使用点 $\gamma$ 和 $T_G(\gamma)$ 处 $pi$ 的声明值 $v{i,0}, v_{i,1}$（对于每个 $i = 1,…,w$）以及 $\gamma$ 处 $q1,…,q{d-1}$ 的值 $v1,…,v{d-1}$ 进行响应。验证者使用这些声明的值检查恒等式。请注意，其他值（如消失多项式的求值）可以由验证者简洁地计算。

4. 低阶测试：证明者和验证者使用 Circle FRI 协议对以下商进行低阶测试。

$\frac{pi - v{i,0}}{v_\gamma}, \frac{pi - v{i,1}}{v_{T_G(\gamma)}}, \frac{q_k - vk}{v\gamma}$

其中 $v\gamma$ 和 $v{T_G(\gamma)}$ 分别是 $\gamma$ 和 $T_G(\gamma)$ 上方的消失多项式。可以使用来自验证者的随机性将所有上述接近程度测试批量处理成一个单独的接近程度测试。如果接近程度测试通过，并且声明的值满足总体恒等式，则验证者接受。

结论

这最后一篇帖子将来自算术化、商以及 Circle FRI 低阶测试的所有想法联系起来，以描述 Circle STARK 的构造。这结束了关于 Circle STARK 的四部分系列。

zkSecurity 为包括零知识证明、MPC、FHE 和共识协议在内的密码系统提供审计、研究和开发服务。

了解更多 →

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