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

回顾

• 在 Part I 中，我们介绍了用于快速模运算的 Mersenne prime fields，并详细说明了为什么非 smooth 的乘法群会阻碍 STARK 的实例化。
• 在 Part II 中，我们描述了 circle curve 以及相关的 domain：twin-coset 和 standard position cosets。我们还介绍了 circle curve 上的多项式，并在这两个 domain 上构造了 vanishing polynomials。
• 在 Part III 中，我们将 Circle FFT 算法描述为一种 Cooley–Tukey 风格的算法，它使我们能够在 circle curve 上二元多项式的 evaluation representation 和 coefficient representation 之间切换。我们还定义了由 Circle FFT 算法诱导的 basis，以及 circle curve 上二元多项式空间与 Circle FFT 所插值得到的多项式空间之间的 dimension gap。

引言

这篇收官文章将我们在 Part I–III 中构建的所有内容串联起来。我们的目标是展示这些要素如何组合成一个完整的 Circle STARK。

我们首先描述 circle curve 上的 arithmetization。接着介绍 Circle FRI，这是一种用于确保多项式满足 degree bound 的 low-degree test。最后，我们完整讲解 Circle STARK 的构造。

Arithmetization

执行 trace 本质上就是计算过程的记录：每一行对应一个 step 或一个 clock cycle，每一列记录一个 register 的演化，而每个条目都位于 Mersenne prime field $F_p$ 中。如果计算有 $N$ 个 cycle，并涉及 $w$ 个 register，那么 trace table 的大小就是 $N \times w$。Arithmetization 就是把这个表中的局部 transition rules 编码为在整个 domain 上成立的 polynomial identities，从而把对计算过程的推理归约为对多项式 evaluations 的检查。

我们用一个包含 $N=2^n$ 行和 $w$ 列的 trace table 来定义计算。这个表中的每个单元都是 $F_p$ 中的一个元素。我们可以用 $w$ 个 column vectors 来表示整个 trace：

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

假设 $H$ 是一个大小为 $N=2^n$ 的 standard position coset。我们将使用 Circle FFT 在 trace domain $H$ 上对每个 trace 列 $t_i$ 进行插值，从而得到定义在 circle curve 上的 bivariate polynomials $p_i$。这些多项式属于 circle curve 上的二元多项式空间，即 $p_i \in L_N(F_p), i=1,\dots,w$

Prover 通过对这些列多项式 $p_i$ 在一个 evaluation domain $D$ 上的 evaluations 进行承诺来提交它们，而 $D$ 的大小比 trace domain $H$ 大 $2^B$ 倍，即

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

其中 $B \ge 1$。多项式 $p_i$ 在 evaluation domain $D$ 上的 evaluations 通过 Merkle tree 进行承诺。

现在我们要在 trace table 上加入约束。假设我们总共加入了 $C$ 个约束。为简便起见，这里只描述关于相邻行的约束：

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

这里，$p_i \circ T_G$ 表示对列多项式 $p_i$ 进行由生成元 $G$ 诱导的平移，其中 $T_G(P)=G \cdot P$。trace domain 是一个 coset $H=Q \cdot G_n$，其中 $G_n$ 是一个大小为 $N=2^n$ 的子群，而 $Q$ 是一个 offset。每一列 $p_i$ 都是在 trace domain $H$ 上插值得到的，可表示为：

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

因此，$p_i \circ T_G$ 对应于 trace 的“下一行”。约束 $P_j$ 是根据列多项式 $p_i$ 和预定义的 selector polynomial $s_j$ 定义的，其中 $s_j$ 用来决定约束 $P_j$ 应该作用于哪些行。

注意

这些 selector polynomials $s_j$ 具体是什么样的？

它们属于哪个 polynomial space？

假设我们希望将约束 $P_j$ 应用于子 domain $H_j \subset H$。那么 selector polynomial $s_j$ 应该在 $H_j$ 中的点上取某个非零值，而在 $H \setminus H_j$ 中的点上取零值。换一种说法，$s_j$ 应该在 $H_j$ 之外 vanish。它们定义如下： $$ s_j=\frac{v_H}{v_{H_j}} $$ 其中 $v_H$ 和 $v_{H_j}$ 分别是 $H$ 和 $H_j$ 的 vanishing polynomials。

尽管 $s_j$ 被定义为一个 rational function，但在 circle curve 上它实际上是一个多项式。原因在于，全局 vanishing polynomial $v_H$ 在更小的 domain $H_j$ 上 vanish，因此 $v_H$ 可被 $v_{H_j}$ 整除。于是，比例 $v_H/v_{H_j}$ 不会出现 pole。更多细节请参见 Lemma 10, Circle STARKs。

我们知道 $\deg(v_H)=2^{n-1}=N/2$ 且 $v_H \in L_N(F_p)$（参见 Dimension Gap, Part III）。因此，$s_j$ 也属于多项式空间 $L_N(F_p)$。

现在，我们不再分别证明这 $C$ 个约束，而是将它们批量合并成一个。Verifier 从 $F_p$ 的 extension field $F$ 中选择一个随机的 $\beta$。Prover 计算：

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

为了证明上述恒等式在整个 trace domain $H$ 上成立，prover 计算 quotient polynomial $q$：

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

这样的 quotient $q$ 必然存在，因为如果所有约束在整个 $H$ 上都成立，那么左边在 $H$ 上 vanish，因此可被 $v_H$ 整除。

注意

quotient polynomial $q$ 的 degree 是多少？

它属于哪个 polynomial space？

设每个 $P_j$ 的 degree 至多为 $d$。多项式 $s_j,p_i,\dots,p_w,p_i \circ T,\dots,p_w \circ T$ 都属于最大 degree 为 $N/2$ 的空间 $L_N(F_p)$。因此，下面表达式左边的最大 degree 是 $dN/2$。 $$ \sum_{j=1}^C \beta^{j-1} P_j(s_j,p_1,\dots,p_w,p_1 \circ T_G,\dots,p_w \circ T_G)=q \cdot v_H $$ 而 $v_H$ 的 degree 是 $N/2$。因此，$q$ 的 degree 是 $(d-1)N/2$，且 $q$ 属于多项式空间 $q \in L_{(d-1)N}(F)$。注意，$q$ 定义在 extension field $F$ 上，因为 $\beta$ 是从 $F$ 中采样的。

现在 prover 需要证明列多项式 $p_i$ 的 degree $\le N/2$，以及 quotient polynomial $q$ 的 degree $\le (d-1)N/2$。为了让所有多项式的 degree bound 统一为 $\le N/2$，我们将 quotient polynomial $q \in L_{(d-1)N}(F)$ 分解成多项式 $q_1,\dots,q_{d-1} \in L_N(F)$，如下：

$$ q=\lambda \cdot v_{\bar{H}}+\sum_{k=1}^{d-1}\frac{v_{\bar{H}}}{v_{H_k}}\cdot q_k $$

其中 $\bar{H}=\bigcup_{k=1}^{d-1}H_k$ 是由若干个大小为 $|H_k|=N$ 的 twin-cosets 构成的不相交并集。

注意

关于 quotient polynomial $q$ 分解的直观理解

quotient polynomial $q$ 属于空间 $L_{(d-1)N}(F)$，其维度为 $(d-1)N+1$。$q$ 的分解来自于对多项式空间 $L_{(d-1)N}(F)$ 的分解，其形式如下： $$ L_{(d-1)N}(F)=\langle v_{\bar{H}} \rangle+L_{(d-1)N}'(F) $$ 其中空间 $L_{(d-1)N}'(F)$ 的维度为 $(d-1)N$。

上述分解与 Dimension Gap, Part III 中 $L_N(F)$ 的分解非常相似： $$ L_N(F)=\langle v_n \rangle+L_N'(F) $$

现在我们可以进一步将空间 $L_{(d-1)N}'(F)$ 中的多项式分解为 $(d-1)$ 个来自空间 $L_N'(F)$ 的多项式，并结合 $L_{(d-1)N}'(F)$ 相对于 $L_N'(F)$ 的某组 basis。也就是说，$q_k$ 是来自空间 $L_N'(F)$ 的这 $(d-1)$ 个多项式，而 $v_{\bar{H}}/v_{H_k}$ 则是 $L_{(d-1)N}'(F)$ 相对于 $L_N'(F)$ 的 basis。

这为 quotient polynomial $q$ 的分解提供了直观理解。完整证明请参见 Lemma 12, Circle STARKs。

因此，prover 必须证明下面这个等式成立：

$$ (1)\sum_{j=1}^C \beta^{j-1} P_j(s_j,p_1,\dots,p_w,p_1 \circ T_G,\dots,p_w \circ T_G) \stackrel{?}{=} \left(\lambda \cdot v_{\bar{H}}+\sum_{k=1}^{d-1}\frac{v_{\bar{H}}}{v_{H_k}}\cdot q_k\right) \cdot v_H $$

并证明多项式 $p_i, q_k$ 的 degree 都满足 $\le N/2$。下面我们将介绍 Circle FRI 来证明后者。

Circle FRI

Circle FRI 用于测试定义在 evaluation domain $D$ 上、大小为 $|D|=2^{n+B}$ 的函数 $f \in F^D$，是否接近多项式空间 $L_N(F)$ 中的某个多项式 $p(x,y)$。函数 $f \in F^D$ 被表示为它在 domain $D$ 上的 evaluations 向量。

这里：

• $F$ 是 $F_p$ 的一个 field extension
• $B$ 是 blowup factor $2^B$ 的对数
• $L_N(F)$ 是 circle curve 上二元多项式的空间，可按如下方式分解（如 Dimension Gap, Part III 所述）：

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

注意

为什么要检查与某个多项式的 proximity？

Prover 会向 verifier 发送某个函数的 evaluations。然而，verifier 并不知道这个函数是否真的是一个多项式，或者它是否满足预先指定的 degree bound。FRI 使 verifier 能够检查 prover 发送的这些 evaluations 是否确实“接近”某个 degree 有界的多项式。这里 verifier 检查的只是 proximity；也就是说，即使 prover 发送的 evaluations 只是“足够接近”某个 degree 有界多项式的 evaluations，verifier 也会接受。

Circle FRI 采用了与 Circle FFT 算法类似的 divide-and-conquer 策略。Prover 递归地分解函数，并利用 verifier 发送的 randomness 将 odd 和 even 两部分折叠起来。这个归约过程会持续进行，直到折叠后函数到 polynomial space 的 proximity claim 足够小，小到 verifier 可以直接检查；在这种情况下，prover 会直接将折叠后的函数发送给 verifier。

下图展示了 Circle FRI 算法在使用一条 2-to-1 映射链时，经过 $r$ 轮 folding 后得到的 domain 序列。

如上图所示，我们像在 circle FFT 算法中那样使用两种不同的映射：projection map $\pi_x$ 和 squaring map $\pi$。协议从一个大小为 $2^m$ 的 standard position coset $D_m$ 开始，其中 $m=B+n$，然后通过映射 $\pi_x$ 投影到 x-axis 上，以计算 quotient $D_m/J$。之后再应用映射 $\pi$ 进行 $(r-1)$ 轮，得到包含 $2^{m-r}$ 个元素的 quotient $D_{m-r+1}/J$。关于这些映射的更多信息，请参见 Sequence of Domains for Circle FFT, Part III。为了记号方便，我们将第 $j$ 轮的 domain 和 map 分别记为 $S_j$ 和 $\pi_j$。

在 Circle FRI 的每一步中，prover 都会按照上述 domain 序列对函数进行分解和折叠。不过在 folding 之前，prover 会先将 $f \in L_N(F)$ 分解为：

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

其中 $g$ 来自 FFT space $L_N'(F)$，$\lambda \in F$，而 $v_n$ 是大小为 $N=2^n$ 的 standard position coset 的 vanishing polynomial。这样就把 $f$ 到 $L_N(F)$ 的 proximity claim 归约为 $g$ 到 FFT space $L_N'(F)$ 的 proximity claim，而后者会通过对 $g$ 的重复 folding 来进行检查。

我们从 $g=g_0 \in F^{S_0}$ 到 FFT space $L^{(0)}=L_N'(F)$ 的 proximity claim 开始。在每一轮 $j=1,\dots,r$ 中，我们把前一轮中 $g_{j-1} \in F^{S_{j-1}}$ 到 $L^{(j-1)}$ 的 proximity claim，归约为新的 $g_j \in F^{S_j}$ 到 FFT space $L^{(j)}$ 的 proximity claim，其中

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

下面我们将详细解释完整协议以及上述归约。Prover 拥有一个函数 $f \in F^D$，而 verifier 获得了一个访问 $f$ 的 oracle。该协议由一个 commit phase 和一个 query phase 组成。

Commit Phase

• Decomposition：Prover 将 $f$ 分解为 $g+\lambda \cdot v_n$，并把 $\lambda$ 发送给 verifier。
• Folding：Prover 持有函数 $g=g_0 \in F^{S_0}$，并希望证明它接近 $L^{(0)}=L_N'(F)$。
  • 对于第一轮 folding，也就是 $j=1$，
    • Verifier 发送一个随机 challenge $\lambda_1 \in F$。
    • Prover 使用映射 $\pi_1=\pi_x$ 将函数 $g_0$ 分解如下： $$ g_0(X,Y)=g_{0,0}(\pi_1(X,Y))+Y \cdot g_{0,1}(\pi_1(X,Y)) = g_{0,0}(X)+Y \cdot g_{0,1}(X) $$ 其中 $g_{0,0},g_{0,1} \in F^{S_1}$，具体如下： $$ g_{0,0}(X)=\frac{g_0(X,Y)+g_0(X,-Y)}{2}, \quad g_{0,1}(X)=\frac{g_0(X,Y)-g_0(X,-Y)}{2 \cdot Y} $$ 正如我们在 Dimension Gap, Part III 中看到的，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)$ 的 proximity，归约为检查 $g_{0,0}$ 和 $g_{0,1}$ 到 $L^{(1)}=F[X]{<N/2}$ 的 proximity。不过，与其分别检查两个 proximity claim，不如利用 verifier 提供的随机 challenge $\lambda_1$ 将它们折叠为一个 proximity claim。 $$ (2)g_1(X)=g{0,0}(X)+\lambda_1 \cdot g_{0,1}(X) $$ 因此，经过第一轮之后，我们已经把 $g_0 \in F^{S_0}$ 到 $L^{(0)}=L_N'(F)$ 的 proximity claim，归约为 $g_1 \in F^{S_1}$ 到 $L^{(1)}=F[X]_{<N/2}$ 的 proximity claim。
  • 对于后续轮次，即 $j=2,\dots,r$，我们使用相同的过程。唯一的区别在于每一轮都使用 squaring map $\pi$，即 $\pi_j=\pi$。对于第 $j$ 轮，
    • Verifier 发送一个随机 challenge $\lambda_j \in F$。
    • Prover 将上一轮的函数 $g_{j-1} \in F^{S_{j-1}}$ 分解为： $$ g_{j-1}(X)=g_{j-1,0}(\pi_j(X))+X \cdot g_{j-1,1}(\pi_j(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}$，具体如下： $$ g_{j-1,0}(2X^2-1)=\frac{g_{j-1}(X)+g_{j-1}(-X)}{2}, \quad g_{j-1,1}(2X^2-1)=\frac{g_{j-1}(X)-g_{j-1}(-X)}{2 \cdot X} $$ Prover 按如下方式折叠函数 $g_{j-1,0},g_{j-1,1} \in F^{S_j}$： $$ (3)g_j(X)=g_{j-1,0}(X)+\lambda_j \cdot g_{j-1,1}(X) $$ 因此，在第 $j$ 轮之后，我们已经把 $g_{j-1} \in F^{S_{j-1}}$ 到 $L^{(j-1)}=F[X]{<N/2^{j-1}}$ 的 proximity claim，归约为 $g_j \in F^{S_j}$ 到 $L^{(j)}=F[X]{<N/2^j}$ 的 proximity claim。
  • 对于每一轮，prover 都会向 verifier 发送一个关于 $g_j$ 的 oracle。在最后一轮，prover 直接以明文形式发送 $g_r \in F^{S_r}$，此时 verifier 可以直接检查 $g_r$ 到多项式空间 $L^{(r)}$ 的 proximity claim。

Query Phase

在 query phase 中，verifier 使用 prover 发送的 oracles 来检查 prover 是否正确执行了 folding。它包含 $s \ge 1$ 轮。在每一轮中：

• Verifier 从 $D$ 中采样 $(x_0,y_0) \in D$，并将每个 map 作用到元素 $(x_0,y_0)$ 上，从而得到 projection trace 上每个 domain 中的一个元素，如下所示： $$ x_j=\pi_j(x_{j-1}),\text{for } j \in {1,\dots,r} $$ 然后 verifier 查询上述 projection trace 上各点处的 $f$ 和 $g_j$ 的 oracle 值。

• Verifier 按如下方式检查第一轮 folding，即在 $(x_0,y_0)$ 处检查等式 (2)。注意这里 $X_1=\pi_1(x_0)=x_0$，因为 $\pi_1$ 是 projection map $\pi_x$。 $$ g_1(x_0) \stackrel{?}{=} \left(\frac{g_0(x_0,y_0)+g_0(x_0,-y_0)}{2}\right)+\lambda_1 \cdot \left(\frac{g_0(x_0,y_0)-g_0(x_0,-y_0)}{2 \cdot y_0}\right) $$

• Verifier 检查后续 folding 轮次中的等式 (3)，即对所有 $j \in {2,\dots,r}$ 检查： $$ g_j(x_j) \stackrel{?}{=} \left(\frac{g_{j-1}(x_{j-1})+g_{j-1}(-x_{j-1})}{2}\right)+\lambda_j \cdot \left(\frac{g_{j-1}(x_{j-1})-g_{j-1}(-x_{j-1})}{2 \cdot x_{j-1}}\right) $$

如果上述所有检查在全部 $s$ 轮中都通过，则 verifier 接受；否则拒绝。

Security Analysis

在本节中，我们给出一些关于 FRI 协议安全性的直观理解。Prover 大致有两种作弊方式：

• 函数 $f \in F^D$ 与多项式空间 $L_N(F)$ 相距很“远”，但 prover 却侥幸最终得到一个与 $L^{(r)}$ 很“接近”的 $g_r$。proximity gaps 论文 分析表明，这种情况发生的概率可以忽略不计。也就是说，如果函数 $f$ 与多项式空间 $L_N(F)$ 很“远”，那么函数 $g_r$ 也会以高概率与 $L^{(r)}$ 很“远”。
• 现在假设 $f \in F^D$ 与多项式空间 $L_N(F)$ 很“远”，因此函数 $g_r$ 也会与 $L^{(r)}$ 很“远”；但为了欺骗 verifier，prover 在 folding 轮次中作弊，并发送某个有效的 $g_r \in L^{(r)}$。这时 verifier 必须确保 prover 在每一轮中都利用其发送的 oracles 正确执行了 folding。这正是 verifier 在 query phase 中检查的内容。根据 “Toy Problem Conjecture”（ethSTARK, Section 5.9），verifier 的每一次 query 都能提供 $B$（即 blowup $2^B$ 的对数）比特的安全性。因此，对于 $s$ 次 query，总安全性为 $s \cdot B$ 比特。

Circle STARKs

在本节中，我们将把本系列迄今为止介绍的所有想法结合起来，构造 Circle STARK 协议。给定长度为 $N=2^n$ 的 trace table，将其表示为 $w$ 列，即

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

协议流程如下：

1. Trace Commitment：Prover 使用 circle FFT 将每个 trace 列 $t_i$ 插值为 trace domain $H$ 上的 bivariate polynomial $p_i$。然后在 evaluation domain $D$ 上对这些多项式 $p_i$ 求值，并用 Merkle tree 对得到的 evaluation vector 进行承诺。Prover 将每个 $p_i$ 的 evaluations 对应的 Merkle commitment 发送给 verifier。

2. Arithmetization：Verifier 发送随机的 $\beta$，用于将所有约束批处理为一个。Prover 计算 $q$，并将其分解得到 $\lambda$ 和各个 $q_k$ 多项式。每个 $q_k$ 都像 trace 多项式一样在 $D$ 上进行承诺。Prover 将每个 $q_k$ 的 evaluations 对应的 Merkle commitment 以及 $\lambda$ 发送给 verifier。此时 prover 必须证明等式 (1) 成立，即

$$ \sum_{j=1}^C \beta^{j-1} P_j(s_j,p_1,\dots,p_w,p_1 \circ T_G,\dots,p_w \circ T_G) \stackrel{?}{=} \left(\lambda \cdot v_{\bar{H}}+\sum_{k=1}^{d-1}\frac{v_{\bar{H}}}{v_{H_k}}\cdot q_k\right) \cdot v_H $$

3. Opening：上述恒等式会在 extension field 上、circle 上的一个 out-of-domain point 处进行检查。Verifier 从 $C(F) \setminus (D \cup H)$ 中采样 $\gamma$，并请求 prover 打开 $p_i$ 和 $q_k$。对于每个 $i=1,\dots,w$，Prover 返回 $p_i$ 在点 $\gamma$ 和 $T_G(\gamma)$ 处的 claimed values $v_{i,0},v_{i,1}$，以及 $q_1,\dots,q_{d-1}$ 在 $\gamma$ 处的值 $v_1,\dots,v_{d-1}$。Verifier 使用这些 claimed values 检查该恒等式。注意，其他值，例如 vanishing polynomials 的 evaluations，都可以由 verifier 简洁地计算出来。

4. Low-Degree Test：Prover 和 verifier 使用 Circle FRI 协议对以下 quotient 进行 low-degree test。

$$ \frac{p_i-v_{i,0}}{v_\gamma}, \quad \frac{p_i-v_{i,1}}{v_{T_G(\gamma)}}, \quad \frac{q_k-v_k}{v_\gamma} $$

其中 $v_\gamma$ 和 $v_{T_G(\gamma)}$ 分别是点 $\gamma$ 和 $T_G(\gamma)$ 上的 vanishing polynomials。上述所有 proximity tests 都可以利用 verifier 的 randomness 批量合并为一个单独的 proximity test。如果 proximity test 通过，并且这些 claimed values 满足整体恒等式，则 verifier 接受。

结论

这篇收官文章将 arithmetization、quotienting 和 Circle FRI low-degree test 的所有思想串联起来，描述了 Circle STARK 的构造。这也为 Circle STARKs 四篇系列文章画上了句号。

zkSecurity 提供密码学系统的审计、研究和开发服务，包括零知识证明、MPC、FHE 和 consensus protocols。

了解更多 →

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