STARK 证明系统时序图

RISC Zero STARK 协议

关于 RISC Zero STARK 证明者的代码实现可以在 这里 看到。 在本文件中，我们介绍了 RISC Zero STARK 协议的概述，并在下面提供了一个顺序图和详细描述。手动构建 STARK 解释和 RISC Zero ZKP 白皮书 是本文件的很好的补充。

概述

RISC Zero 的 [收据]Receipt 基于零知识加密技术领域的几项最新进展。 该证明系统基于 STARK，实现 DEEP-ALI & FRI。 此证明系统用于为 RISC Zero 的 RISC-V 电路和 RISC Zero 的递归电路生成零知识有效性证明。 用户也可能对 [RISC Zero Groth16 电路][groth16-circuit] 感兴趣，该电路使链上验证成为可能。

在高层次上，RISC Zero STARK 协议的设计与 ethSTARK 中描述的系统非常相似，且与 Winterfell 中实现的系统相似。

设置阶段

该协议包括一个分为两部分的设置阶段；第一次设置在每个 zkVM 版本上进行一次，第二次设置为给定 RISC-V 二进制文件建立图像 ID。

第 1 部分：电路设置

该设置是透明的，并为证明者和验证者建立公共参数。 这些公共参数包括踪迹列的数量和长度、哈希函数和 Merklization 结构的选择，以及所有要执行的约束的完整枚举。

第 2 部分：程序设置

该阶段建立一个 Image ID，该 ID 透明地从 RISC-V 二进制文件和电路参数中确定。 Image ID 是通过将 RISC-V 二进制文件加载到 zkVM 内存中，然后记录整个机器状态的 Merkle 快照构造的。 该设置可以被任何有权访问二进制文件的人重复，以确认 Image ID 的正确性。

主踪迹和辅助踪迹

在设置阶段之后，证明者在 zkVM 中执行二进制文件，计算每列的低度扩展，并提交 扩展主执行踪迹。 然后，证明者计算并提交 扩展辅助执行踪迹，该踪迹依赖于验证者的随机性。

与 ethSTARK 相比，我们的协议增加了一个额外的互动回合，以支持超出基本 AIR 约束的约束。 使用可能跨越主踪迹和辅助踪迹的约束，我们按照 ethSTARK 中描述的方式继续进行 DEEP-ALI & FRI。 添加辅助执行踪迹相较于原始 STARK 协议启用了各种增强功能。 这些增强功能在 从 AIRs 到 RAPs 中有良好的描述。

我们使用这个辅助执行踪迹来支持：

1. 针对 内存验证 的排列论证<br /> 排列论证当前实现为一种大乘积累加器论证，如同 PLONK 中所示。 我们计划在下一个版本的电路中将其改为 log derivative 累加器论证。<br /> 在这里，与内存相关的操作既在原始顺序又在排列顺序中被提交到主踪迹中，并在辅助踪迹中提交大乘积累加器。
2. 范围检查的查找论证<br /> 查找论证目前使用的是 PLOOKUP 中描述的方法实现。 我们计划在下一个版本的电路中将其改为 log derivative 累加器论证。<br /> 在这里，表格和见证被提交到主踪迹中，大乘积累加器被提交到辅助踪迹中。
3. 一个大整数加速器以便于 [快速加密操作]precompiles 大整数加速器实现了通过请求主机提供非确定性建议的乘法 a 和 b 而生成的乘积 c。然后，验证者提供随机性 r，并且约束强制在将 a、b 和 c 视为多项式时，a(r) * b(r) == c(r)。<br /> 在这里，a、b 和 c 被提交到主踪迹中，而在 r 的评估值被提交到辅助踪迹中。

DEEP-ALI 和 FRI

协议的其余部分使用 DEEP-ALI & FRI 实现，如同 EthSTARK 中描述的。 我们在下面将其详细说明，并为读者指向 ZKP 白皮书 以获取该协议的更正式描述。

顺序图

sequenceDiagram
  participant P as Prover
  participant V as Verifier
  Note over P,V: Circuit Setup Phase<br/>The Prover & Verifier agree on the public<br/>parameters for the zkVM circuit.
  Note over P,V: Image ID Setup Phase<br/>Anyone with access to the binary file and the<br/>public parameters can reconstruct the Image ID.
  Note over P: Execute the binary to<br/>construct the Main Execution Trace.
  Note over P: Compute Low Degree<br/>Extension to construct the<br/>Extended Main Execution Trace.
  Note over P: Merklize Extended Main Execution Trace
  P->>V: Send Merkle Root(s) for<br/>Extended Main Execution Trace
  V->>P: Return numerous random<br/>extension field elements.<br/>These are used for a<br/>permutation argument,<br/>a lookup argument, and<br/>a big integer accelerator.
  Note over P: Compute Extended Auxiliary Execution Trace.
  Note over P: Merklize Extended Auxiliary Execution Trace.
  P->>V: Send Merkle Root for<br/>Extended Auxiliary Execution Trace
  Note over P,V: Begin DEEP-ALI Protocol
  V->>P: Return random constraint<br/>mixing parameter, alpha
  Note over P: Use powers of alpha to mix (i.e. linearly combine)<br/>Constraint Polynomials into a Mixed Constraint Polynomial.
  Note over P: Divide by the Zeroes Polynomial<br/>to construct the High Degree Validity Polynomial<br/>Degree(HDVP) = MaxConstraintDegree * TraceDegree
  Note over P: Split High Degree Validity Polynomial<br/>into a few Low Degree Validity Polynomials,<br/>Degree(LDVP) = TraceDegree
  Note over P: Merklize Low Degree Validity Polynomials.
  P->>V: Send Merkle Root<br/>for Low Degree Validity Polynomials
  V->>P: Return a random extension<br/>field element, which serves<br/>as an out-of-domain<br/>evaluation point.
  P->>V: Send "necessary evaluations"<br/>required to evaluate constraints<br/>at out-of-domain evaluation point<br/>and coefficients of DEEP polynomials
  V->>P: Return random<br/>extension field element<br/>for FRI batching
  Note over P: Use FRI batching randomness to mix<br/> the DEEP polynomials, forming the FRI polynomial.
  P->>V: Send Merkle Root<br/>for the FRI polynomial
  Note over P,V: Begin FRI protocol.
  Note over P,V: Details of FRI are omitted for brevity.

详细逐步描述

在本节中，我们详细阐述上述顺序图。 有关协议的更正式表述，请参考 ZKP 白皮书。

扩展主执行踪迹

• 证明者运行计算以生成 执行踪迹。
  • trace 被组织成 columns，这些列被分类为 control columns、data columns 和 auxiliary/accum columns。
  • control columns 处理系统初始化和关闭、执行前加载到内存的初始程序代码以及其他不依赖于程序执行的控制信号。
  • data columns 包含输入和计算数据，均为私有。这些列有两种顺序被提交：
    • 按程序执行顺序，和
    • 按注册首先和时钟周期其次的顺序重新排列。重新排列的列可以有效验证 RISC-V 内存操作。
  • auxiliary/accum columns 用于排列论证、查找论证和大整数加速电路。
  • 在计算 data columns 和 auxiliary/accum columns 之后，证明者在这些列的末尾添加一些随机 noise 以确保协议是零知识的。
• 证明者按如下方式编码 trace：
  • 证明者使用 iNTT 将每个 column 转换为多项式。我们将其称为 Trace Polynomials，表示为 $P_i(x)$。
  • 证明者在扩展域上评估 data polynomials 和 control polynomials。在这个更大域上 data polynomials 和 control polynomials 的评估值称为 扩展主执行踪迹。
  • 证明者将 扩展主执行踪迹 提交到两个独立的 Merkle 树中，并将根发送给验证者。

扩展辅助执行踪迹

• 使用当前转录作为熵源，我们选择一些随机扩展域元素，使用 SHA-2 CRNG。
• 然后，证明者使用随机性生成 auxiliary/accum columns。证明者计算辅助列的低度扩展以形成扩展辅助执行踪迹。
• 证明者将扩展辅助执行踪迹提交到 Merkle 树中，并将 Merkle 根发送给验证者。
• 使用当前转录作为熵源，我们选择一个随机的 constraint mixing parameter $\alpha$，使用 SHA-2 CRNG。

DEEP-ALI（第 1 部分）

• 证明者使用 constraint mixing parameter、Trace Polynomials 和 Rule Checking Polynomials 构造一些 Low Degree Validity Polynomials。具体如下：
  • 通过将 $k$ 个公开已知的 Rule Checking Polynomials 写为 $R_0, R1, ..., R{k-1}$，并依赖私有的 Trace Polynomials，证明者生成 $k$ 个 Constraint Polynomials，$C_j(x)$。
  • 关于这些多项式的重要一点是，对于每个 $k$ 条规则和与踪迹相关的每个输入 $z$，如果踪迹“通过测试”，则 $C_j(z)$ 将返回 0。
  • 通过使用 constraint mixing parameter $\alpha$，证明者将 Constraint Polynomials $C_j$ 组合成一个单一的 Mixed Constraint Polynomial $C$，计算 $C(x)=\alpha^0C0(x)+\ldots+\alpha^{k-1}C{k-1}(x)$。
  • 注意，如果每个 $C_j$ 在某一点 $z$ 返回 0，那么 $C$ 在 $z$ 处也将返回 0。
  • 使用一个公开已知的 Zeros Polynomial，证明者计算 High Degree Validity Polynomial，$V(x)=\frac{C(x)}{Z(x)}$。
  • Zeros Polynomial $Z(x)$ 是任何诚实构造的 $C(x)$ 的因子。 换句话说，一个诚实的证明者将构造 $V(x)$ 成为比 $C(x)$ 低档次的多项式。 我们称 $V$ 为相对于 Trace Polynomials $P_i$ 的“高档次”。
  • 证明者将 High Degree Validity Polynomial 分割成 4 个 Low Degree Validity Polynomials，$v_0(x), v_1(x), ..., v_3$。
  • 证明者评估 Low Degree Validity Polynomials，将其编码在 Merkle 树中，并将 Merkle 根发送给验证者。
  • 我们使用 Fiat-Shamir 选择一个域外评估点 $z$。

DEEP-ALI（第 2 部分）

• 验证者希望检查声称的 $C$、$Z$ 和 $V$ 之间的关系，在 DEEP 测试点 $z$。 即，验证者希望确认 $V(z)Z(z)=C(z)$。
  • 证明者发送每个 $v_i$ 在 $z$ 处的评估，这允许验证者计算 $V(z)$。
  • 计算 $C(z)$ 稍微复杂一些。由于 rule checks 可以检查跨多个 columns 和多个 clock cycles 的关系，因此评估 $C(z)$ 需要形式为 $P_i(\omega^nz)$ 的许多评估，其中 $i$ 是变化的 columns，$n$ 是 cycles。 证明者发送这些每个 $P_i$ 的 必要评估 以允许验证者评估 $C(z)$。 我们将 必要评估 $P_i(\omega^nz)$ 称为 $P_i$ 在 $z$ 处的 taps。
  • 验证者现在可以检查 $V(z)Z(z)=C(z)$。
  • 尽管这些声称的评估没有相关的 Merkle 分支，但 DEEP 技术提供了通常 Merkle 证明的替代方案。
• 证明者使用 taps 构造 DEEP 多项式：
  • 将 $P_i$ 在 $z$ 的 taps 表示为 $(x_1,P_i(x_1)),\ldots,(x_n,P_i(x_n))$，证明者构造 DEEP 多项式 $P'_i(x)=\frac{P_i(x)-\overline{P_i}(x)}{(x-x_1)\ldots(x-x_n)}$，其中 $\overline{P_i}(x)$ 是通过插值 $P_i$ 的 taps 形成的多项式。证明者计算 $P'_i$，对结果运行 iNTT，并将 $P'_i$ 的系数发送给验证者。 使用这种技术，证明者为每个 $P_i$ 和每个 $v_i$ 构造并发送一个 DEEP 多项式。
• 此时，踪迹有效性的声明已减少为每个 DEEP 多项式实际上是一个低度多项式的声明。 为了结束证明，证明者将 DEEP 多项式混合到 FRI Polynomial 中，使用 DEEP mixing parameter，并利用 FRI 协议显示 FRI Polynomial 是一个低度多项式。

FRI 协议

• 为了简洁起见，我们省略 DEEP-ALI & FRI 的细节。

感谢阅读！如果你有问题或反馈，我们希望在 Discord 或 Twitter 上听到你的意见。

原文： https://dev.risczero.com/proof-system/proof-system-sequence-diagram

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