通过 12 节课理解 STARK 构建过程

手动构建 STARK

当 RISC Zero zkVM 执行时，会生成一个 收据，允许第三方验证执行的有效性。 该收据包含一个 zk-STARK，以 密封（seal） 的形式存在。 在收据上的 zk-STARK 是 RISC Zero 技术的核心。

RISC Zero STARK 的构建是高度技术性的，依赖于零知识密码学领域的几项最近进展。 具体来说，构建 RISC Zero 的 zk-STARK 使用 DEEP-ALI 协议和批量 FRI 协议（经过随机预处理步骤）。

在这 12 个简短的课程中，我们将通过一个简化的数字示例，逐步走过 RISC Zero 的 STARK 构建过程。

• Google Sheet 版本
• PDF 版本 (PDF)
• Python 版本

如果你理解这 12 课内容，你将能够扎实掌握 zk-STARK 的机制（我们可能也会非常想要 招聘你）。

证明系统序列图 更一般性地描述了该过程；我们建议在本文档与序列图之间来回查看。

课程 1：执行的 Trace

当任何代码在 RISC Zero 虚拟机中执行时，该执行的每一步都记录在一个 Execution Trace 中。

我们展示一个简化的示例，计算 4 步 Fibonacci 数列模 97，使用两个用户指定的输入。

在这个例子中，我们的Trace包括 6 个 列。

• 前三列是每个时钟周期内寄存器内部状态的记录，从初始化到结束。我们称这些为 数据列。
• 接下来的三列是 控制列，我们用来标记初始化和终止点。

在完整的 RISC Zero 协议中，数据列保存 RISC-V 处理器的状态，包括 ISA 寄存器、程序计数器，以及各种微架构细节，如指令解码数据、ALU 寄存器等，而 控制列 则处理系统初始化和关闭，使用程序内存映像设置页表，以及其他不依赖于程序执行的控制信号。

完整实现还具有 累加器列，允许进行 RISC-V 内存仿真。在这个简化示例中，累加器列并不是必需的。

课程 2：验证计算的规则检查

在这里，我们引入一些规则检查单元以演示执行的有效性。 在这个示例中，我们展示六条特定于生成 Fibonacci 数字的规则。

每个规则检查以多项式形式写在数据列上，例如 $a + b - c$ 只有在 $a + b = c$ 时才等于 $0$。 在我们的示例中，$a$、$b$ 和 $c$ 可能是数据列中的项，用于强制执行 Fibonacci 数列规则，即 $F(i) + F(i+1) = F(i + 2)$。

每个规则与来自控制列的选择器结合，以决定何时应用规则。 例如，我们应该检查一步的输出是否等于下一步的输入，除了考虑第一行，那里没有先前步骤，而必须等于用户输入。 这种组合是通过乘法进行的，例如 $(s)(a + b - c)$ 确保要么 $a + b = c$，要么 $s = 0$。

每个规则检查列可以表示为多输入、单输出多项式，其中输入是Trace中的某些条目组合；我们称这些为 规则检查多项式。 所有这些多项式位于有限域上，本示例中它是模 97 的整数。

在完整的 RISC-V 实现中，规则构成了正确执行 RISC-V 指令的含义（即检查程序计数器在每条指令后是否递增）。 我们检查成千上万条规则以验证执行Trace。

课程 3：填充Trace

在将每列编码为多项式之前，我们在执行Trace末尾附加随机填充，这增加了隐藏用户数据所需的熵，从而允许执行零知识协议。

这随机噪声由主机系统的密码安全伪随机数生成器生成。 我们将控制列设置为这随机噪声行的 0，以关闭我们的规则检查。

课程 4：构建Trace多项式

本课程解释如何进行 Reed-Solomon 编码。 RS 编码是一种纠错编码；它允许在加密消息中有效地增加冗余。

让我们先移除 规则检查列，把注意力转向将我们的Trace数据编码为多项式。 在这些课程中，所有算术运算发生在 $\mathbb{F}_{97}$ 中。

从此以后的课假设你对有限域有一定的了解。如果有限域对你来说是陌生的，别担心！ 这份 有限域入门 的内容刚好足够理解 RISC Zero 对有限域的使用。

$\mathbb{F}{97}$ 中的每个元素都可以写成 5 的幂。换句话说，$\mathbb{F}{97}$ 中的元素为 $0, 5^0, 5^1, \ldots,$ 和 $5^{95}$。 我们用 $\mathcal{D}(5^{12})$ 表示 $5^{12}$ 的幂的集合，用 $\mathcal{D}(5^{3})$ 表示 $5^{3}$ 的幂的集合。 每个集合在 $\mathbb{F}_{97}$ 中都是“均匀分布”的，这促进了 数论变换 的使用。

简而言之，对 Trace列 运行 iNTT 会给出 Trace多项式 的系数。

上述表格展示了 Python 代码及相关的输入/输出数组；输入数组对应于 Trace列，输出数组对应于 Trace多项式 的系数。 关于 Trace多项式 的关键特性是：

• 它们的最大次数为 $7$（列的长度减去 $1$），并且
• Trace多项式 在 $\mathcal{D}(5^{12})$ 上的评估与填充的执行Trace中的数据完全匹配。

在更大的集合 $\mathcal{D}(5^{3})$ 上评估 Trace多项式 会得到一个 Reed-Solomon 编码的 Trace块。

我们说这个 块 是 列 的 次数 4 扩展，并且 Reed-Solomon 编码的 速率 为 $\frac{1}{4}$。 Reed-Solomon 编码 通过放大无效Trace中的任何错误来提高协议的健壮性。

课程 5：Trace数据的 ZK 承诺

下一步是证明者将 Trace多项式 承诺到 Merkle 树中。 为了使 RS 扩展能够与零知识良好配合，我们必须避免在 "Trace域 "和 "承诺域 "之间的评估域重叠。

证明者在 $\mathcal{D}(5^3)$ 的 偏移量 下评估每个 Trace多项式。

我们选择一个偏移量为 5，并在 $x = 5, 5^4, 5^7, ..., 5^{94}$ 上评估每个 Trace多项式。

注意，由于 偏移，数据列 1、2 和 3 中的黄色和蓝色单元格不再与 输入 和 断言输出 匹配。 事实上，这种评估域的偏移“伪装”了所有的 Trace数据。

我们只公开有关 伪装Trace 的信息，而我们附加的随机填充足以防止攻击者推断出伪装Trace与实际Trace之间的任何关联。

课程 6：约束多项式

本课程简要描述 RISC Zero 中如何完成 算术化。 约束是逻辑检查的“算术化”版本。

现在我们已将 Trace列 编码为 Trace多项式，让我们重新回到原始的 Reed-Solomon 域中并将 规则检查单元 加回。

当然，我们不应预期这些 规则检查 在 冗余行 中评估为 0，因为它们与 Trace 数据无直接关联。

方便的是，通过将这些 规则检查 以我们的 Trace多项式 的形式编写，我们可以将多输入的规则检查多项式转换为单输入多项式，我们称之为 约束多项式。

注意，每个 约束多项式 将在与实际Trace数据相关的输入值处评估为 0。

课程 7：混合约束多项式

我们可以通过将一组约束压缩成一项来减少计算负担。 为此，我们添加一列新的列，使得 混合 我们的 约束多项式 成为一个单一的 混合约束多项式。

在证明者为 控制多项式 和 数据多项式 （以及完整实现中的 累加器多项式）提交 Merkle 根后，这些 Merkle 根被用作熵来随机生成一个 约束混合参数 $\alpha_1$。

令 $c_i$ 表示约束多项式，我们写：

$C(x) = \alpha_1^0 * c_0(x) + \alpha_1^1 c_1(x) + ... + \alpha_1^5 c_5(x)$

注意，如果每个 $c_i$ 在某些输入 $x$ 下评估为 0，那么 $C$ 在该输入下也会评估为 0。

在这个示例中，混合约束多项式 的次数等于 Trace多项式 的次数，因为涉及的 规则检查 特别简单。 在更复杂的示例中，将我们的 规则检查多项式 与我们的 Trace多项式 组合会产生 高次约束多项式。 在这种情况下，我们将在第 9 课结束时添加一个额外步骤，将我们的 高次有效多项式 拆分为几个 低次有效多项式。

课程 8：RISC Zero STARK 的核心

证明者通过将前一课的混合约束多项式 除以公共已知的 零点多项式 来构建 有效性多项式。

$V(x) = C(x) / Z(x)$

如果我们将约束用Trace多项式表示，结果将在零点多项式的每个根处消失。 在我们的示例中，零点多项式 为

$Z(x) = (x-1)(x-47)(x-75)(x-33)(x-96)(x-50)(x-22)(x-64)$，其中 8 项是 $\mathcal{D}(5^{12})$ 的元素。

通常，当我们将两个低次多项式相除时，我们并不期望得到另一个低次多项式。 但对于诚实的证明者来说，很容易看出 $V(x)$ 的次数会低于 $C(x)$，因为 $Z(x)$ 的根与 $C(x)$ 的根完全对齐。

证明者在 $5, 5^4, \ldots, 5^{94}$ 上评估 $V(x)$，并将这些值提交给一个 有效性 Merkle 树，根添加到密封中。

这些多项式的构建是 RISC Zero 证明Trace有效性的核心概念。 确认原始执行Trace有效性所需的所有信息可通过以下关于这些多项式的断言进行描述：

(i) 对所有 $x$ 有 $V(x) = C(x) / Z(x)$

(ii) 有效性多项式 和每个 Trace多项式 的次数都小于或等于 7。

FRI 协议 是我们用于证明 (ii) 的技术。这些细节在这个简化示例中省略。

在原始 STARK 协议中，验证者在多个测试点测试 (i)；协议的健壮性取决于测试的数量。 DEEP-ALI 技术使我们得以通过一次测试实现高程度的健壮性。 DEEP 的细节将在下一课中描述。

课程 9：DEEP 技术

DEEP 技术是通过从比承诺域更大的域采样来提高与单个查询相关的安全级别的一种手段。

在这里，我们使用 Trace多项式 和 有效性多项式 组合构建 DEEP 多项式。

DEEP 多项式 允许验证者在原始 Merkle 树承诺之外测试 $V(x) = C(x) / Z(x)$，这实质上提高了验证者测试的健壮性。

如果没有 DEEP 技术，证明者将声称Trace多项式 $d_1, d_2, d_3, c_1, c_2, c_3$，以及有效性多项式 $V$ 都是低次多项式。 使用 DEEP 技术，证明者主张相反，$d'_1, d'_2, d'_3, c'_1, c'_2, c'_3$ 和 $V'$ 是低次多项式。

在 Trace多项式 和 有效性多项式 的承诺到位后，验证者使用密封的熵随机选择一个 DEEP 测试点，$z$。 在这个例子中，我们使用 $z=93$。

验证者希望能够计算 混合约束多项式，$C(93)$。 证明者发送 $V(93)$ 及 Trace多项式 的必要评估，以允许验证者计算 $C(93)$。

在这个例子中，必要评估 是 $d_1(93), d_2(93), d_3(93), c_1(93), c_2(93), c_3(93), d_2(93\cdot5^{-12}), d_3(93\cdot 5^{-12})$，如图所示。 注意 $5^{-12}$ 是向后一个计算步骤的指针；通过向前和向后指向，tap 允许检查横跨多个时钟周期的规则。

这 8 个点，加上公开的规则检查函数，允许验证者手动计算 $C(93)$，从而计算 $V(93)$。

证明者还构建 DEEP 多项式，对每个多项式进行插值，并将每个 DEEP 多项式的系数发送给验证者。 DEEP 多项式 被定义为：

$d'_1(x) = \frac{d_1(x) - d_1(93)}{x - 93}$ $d'_2(x) = \frac{d_2(x) - \overline{d_2}(x)}{(x-93)(x-6)}$ 其中 $\overline{d_2}(x)$ 是通过插值得到的 $(6, d_2(6))$ 和 $(93, d_2(93))$。

$d'_3(x) = \frac{d_3(x) - \overline{d_3}(x)}{(x-93)(x-6)}$ 其中 $\overline{d_3}(x)$ 是通过插值得到的 $(6, d_3(6))$ 和 $(93, d_3(93))$。

$c'_1(x) = \frac{c_1(x) - c_1(93)}{x - 93}$

$c'_2(x) = \frac{c_2(x) - c_2(93)}{x - 93}$

$c'_3(x) = \frac{c_3(x) - c_3(93)}{x - 93}$

$V'(x) = \frac{V(x) - V(93)}{x - 93}$，其中证明者通过运行 iNTT(ValidityColumn) 首先计算 V(93)，然后在 $z=93$ 上评估得到的 有效性多项式。

课程 10：为 FRI 混合

在通过 DEEP 多项式 检查 Trace多项式、有效性多项式 和 零点多项式 之间的关系后，证明者唯一需做的就是展示 DEEP 多项式 是低次的。

FRI 协议 提供了一种机制，允许验证者确认多项式的低次数，与验证者所需的计算相对较少。 为了将低次性的声明降低到 FRI 的一个应用，证明者将 DEEP 多项式 混合为单个 FRI 多项式，使用 DEEP 混合参数 $\alpha_2$。

令 $c'_1, c'_2, c'_3, d'_1, d'_2, d'_3$ 和 $V'$ 为 DEEP 多项式，我们混合这些 DEEP 多项式 来构造 FRI 多项式，$f_0(x) = \alpha_2 ^0 c'_1(x) + \alpha_2 ^1 c'_2(x) + ... + \alpha_2 ^6 V'(x)$

为了完成论证，证明者构造了一个 FRI 证明，证明 $f_0(x)$ 是一个低次多项式。 通过此过程，证明者构造了一个零知识的计算完整性的论证。 由于简洁的理由，我们省略了 FRI 的细节，但我们可以通过对 $f_0$ 的评估运行 iNTT 来检查我们的工作：

iNTT([53,69,63,30,46,13,60,50,38,3,95,23,75,39,62,19,62,58,41,67,89,41,50,24,95,90,72,20,82,33,0,16],prime=97)

返回

[19, 56, 34, 48, 43, 37, 10, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]

将此数组写成多项式的系数，我们可以看到 FRI 多项式列中的值实际上对应于以下低次多项式：

$f_0(x)=19+56x+34x^2+48x^3+43x^4+37x^5+10x^6$。

课程 11：FRI 协议（承诺阶段）

给定向量承诺，FRI 协议证明承诺对应于低次多项式的评估。 在本示例中，我们使用 FRI 来证明 “FRI 多项式” 的承诺（来自上一课）最多具有 7 次项。 FRI 由两个阶段组成；本课程展示“承诺阶段”，下一课展示“查询阶段”。

这里的 "FRI 扩展因子" 为 4，因为 FRI 多项式的承诺有 32 个条目，且一个 7 次多项式有 8 个系数。 这个展开因子是之前选择的 Reed-Solomon 扩展的 “速率” 选择的结果。 一个 FRI 扩展因子为 4 对应于一个速率为 1/4 的 RS 码。

FRI 由承诺阶段和查询阶段组成。承诺阶段由 $r$ 回合组成。 在每个回合，证明者将先前的承诺“折叠”成一个更小的承诺（既在承诺大小方面又在多项式度数方面）。

在这里，我们显示三个回合，使用的折叠因子为 2：在每个回合中，证明者承诺一个长度是先前承诺一半的向量。

FRI 承诺阶段的第一轮

证明者刚刚为 $f_0(x) = 19 + 56x + 34x^2 + 48x^3 + 43x^4 + 37x^5 + 10x^6 + 0x^7$ 提交了一个 32 叶子的 Merkle 树。

将 $f_0$ 按偶数和奇数项进行分类，得到两个系数数量减半的多项式，其中 $f0(x)=f{0,even}(x^2) + xf_{0,odd}(x^2)$。

具体地，$f{0,even}(x) = 19 + 34x + 43x^2 + 10x^3$ 和 $f{0,odd}(x) = 56 + 48x + 37x^2 + 0x^3$。

现在，证明者将这两个更小的多项式混合在一起，使用验证者提供的随机数 $r_1$。 具体而言，第一轮的承诺为 $f1 = f{0,even} + r1f{0,odd}$。

假设 $r_1=12$，我们有：

$$ f1(x)=f{0,even}(x) + r1f{0,odd}(x) $$

$$ = (19 + 34x + 43x^2 + 10x^3) + 12(56 + 48x + 37x^2 + 0x^3) $$

归约至模 97，得到： $f_1(x) = 12 + 28x + 2x^2 + 10x^3$。 证明者为 $f_1(x)$ 提交了 16 叶子的 Merkle 树，完成第一轮。 前一个承诺的叶子是由 $28$ 的幂索引的，而此承诺的叶子则用 $28^2$ 的幂索引。

FRI 承诺阶段的第二轮

我们重复之前的步骤，将 $f_1$ 分为偶数部分和奇数部分，其中

$$ f1(x)=f{1,even}(x^2) + xf_{1,odd}(x^2) $$

我们找到 $f{1,even}(x) = 12+2x$ 和 $f{1,odd}(x) = 28+10x$。

同样，证明者使用来自验证者的随机数混合这些。

假设 $r_2=32$，我们得到：

$$ f2(x)=f{1,even}(x) + r2f{1,odd}(x) $$

$$ = (12+2x) + 32(28+10x) $$

归约至模 97，得到： $f_2(x)=35+31x$。

同样，证明者承诺了一个 Merkle 树以获取 $f_2$，其叶子的数量为前一轮的一半。 这一次，叶子由 $28^4$ 的幂索引。

FRI 承诺阶段的第三轮

同样地，我们将 $f2$ 分为偶数部分和奇数部分，然后进行混合。 此时，$f{2,even}=31$ 和 $f_{2,odd}=35$。 使用随机值 $r_3=64$，我们得到：

$$ f3(x)=f{2,even}+r2f{2,odd} $$

$$ = 31 + 64\cdot35=79 $$

证明者向验证者发送关于 $f_3$ 的评估，使用 $28^8$ 的幂进行索引，无需 Merklization；验证者可以自行检查 $f_3$ 的评价是否对应于常数多项式。

这完成了 FRI 协议的承诺阶段。在 3 轮折叠中，我们将一个拥有 8 个系数的多项式缩减为一个具有 1 个系数的多项式（即，一个常数多项式）。

在 RISC Zero 协议中，FRI 的最终轮发生在多项式被缩减到 255 次时。 证明者发送 1024 个评估向量，验证者插值以确认这些评估对应于低次多项式。

课程 12：FRI 协议（查询阶段）

当承诺阶段完成后，验证者进行若干 查询。 在本课程中，我们展示一个单个查询的机制。

查询作为随机挑战，测试证明者承诺的合法性。 放松说，使用 4 的扩展因子，一个单一查询将检测出作弊证明者的概率为 $\frac{3}{4}$。 换句话说，一个单一查询提供 $2$ 位的安全性。 RISC Zero zkVM 使用 50 个查询以及 4 的扩展因子，相当于 ~100 位的安全性。

请注意，上述段落是对整个安全分析的重大简化。 有关更彻底的安全分析，请参见我们的 密码学安全模型 页面和我们的 安全计算器。

证明者已在 $28$ 的幂上承诺了 $f_0$，在 $28^2$ 的幂上承诺了 $f_1$，在 $28^4$ 的幂上承诺了 $f_2$，以及在 $28^8$ 的幂上承诺了 $f_3$。

单个查询的评估

对于单个查询，证明者提供来自 $f_0, f_1$ 和 $f_2$ 的 2 个评估。 具体而言，如果验证者查询为 $g$，证明者提供的评估为：

• $f_0(g)$ 和 $f_0(-g)$
• $f_1(g^2)$ 和 $f_1(-g^2)$
• $f_2(g^4)$ 和 $f_2(-g^4)$

验证者检查每个评估的 Merkle 分支，并检查来自一轮到下一轮的评估是否一致。 这包括检查 $f_2$ 的评估与 $f_3(g^8)$ 的评估是否一致。

检查评估是否一致

验证者可以通过检查以下公式确认 $f{i-1}$ 和 $f{i}$ 的评估是否一致：

$$ f_{i}(x^2) = \frac{ri+x}{2x}f{i-1}(x) + \frac{ri-x}{2(-x)}f{i-1}(-x) $$

为简化阐述，我们将讨论限制在检查 $f_0$ 和 $f_1$ 的评估一致性。

繁重的代数

我们将展示

$$ f1(x^2) = f{0,even}(x^2) + r1 \cdot f{0,odd}(x^2) $$

意味着

$$ f_{1}(x^2) = \frac{r1+x}{2x}f{0}(x) + \frac{r1-x}{2(-x)}f{0}(-x)。 $$

我们将使用以下事实：

$$ f_{0,even}(x^2) = \frac{f_0(x)+f_0(-x)}{2} $$

$$ f_{0,odd}(x^2) = \frac{f_0(x)-f_0(-x)}{2x} $$

根据构造，我们有

$$ f1(x^2) = f{0,even}(x^2) + r1 \cdot f{0,odd}(x^2) $$

使用 $f{0,even}$ 和 $f{0,odd}$ 的表达式，我们可以仅使用 $f_0(x)$、$f_0(-x)$ 和 $r_1$ 重新写 $f_1(x^2)$：

$$ f_1(x^2) = \frac{f_0(x)+f_0(-x)}{2} + r_1 \cdot \frac{f_0(x)-f_0(-x)}{2x}. $$

现在我们可以找到共同的分母并重新排列项：

$$ f_1(x^2) = \frac{xf_0(x)+xf_0(-x)}{2x} + \frac{r_1 f_0(x) - r_1 f_0(-x)}{2x} $$

$$ = \frac{x+r_1}{2x}f_0(x)+\frac{x-r_1}{2x}f_0(-x) $$

$$ = \frac{x+r_1}{2x}f_0(x) + \frac{r_1-x}{2(-x)}f_0(-x) $$

这完成了声明。

关键在于 FRI 折叠过程可以_局部_检查：验证者可以只使用前一轮的两个评估检验声称的评估 $fi(x^2)$：$f{i-1}(x)$ 和 $f_{i-1}(-x)$。

感谢阅读！

哇！恭喜你，感谢你坚持读到这里！

有疑问、反馈或修正？可以在 Twitter 和 Discord 找到我们。

原文：https://dev.risczero.com/proof-system/stark-by-hand

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