Winter FRI

本crate包含Winterfell STARK证明/验证器使用的FRI证明者和验证器的实现。

FRI代表快速Reed-Solomon交互式近似证明，用于STARK协议中的低度测试。具体来说，给定对某个函数在域D上的评估集的承诺，验证者可以通过对承诺进行少量查询来确信该函数是度至多d的多项式。

证明者

FRI证明由两个步骤的FRI证明者生成

1. 首先，通过build_layers()函数执行协议的提交阶段。在此阶段，通过应用尊重度的投影，多项式的度数被反复降低，直到多项式评估的域的大小低于max_remainder_size参数。在执行降低的过程中，证明者将一系列层承诺写入ProverChannel。这些承诺应在证明验证过程中被记录并发送给验证者。
2. 然后，通过build_proof()函数执行协议的查询阶段。该函数的输出是FriProof结构体实例。当FRI作为STARK协议的一部分执行时，FRI证明将被包含到STARK证明中。

验证者

FRI证明由以下方式的FriVerifier验证

1. 首先，需要将FRI证明转换为VerifierChannel。本crate提供了一个默认的验证器通道实现，但当FRI证明验证作为更大STARK协议的一部分执行时，STARK验证器处理此转换。
2. 然后，应该实例化一个 FriVerifier（通过 new() 函数）。这将执行 FRI 协议的提交阶段，从验证者的角度 - 即，验证者将读取通道中的 FRI 层承诺，并生成用于层折叠所需的随机值。
3. 最后，应该通过 verify() 函数执行 FRI 协议的查询阶段。请注意，第一层 FRI 的查询值直接提供给 verify() 函数。其余层的值，验证者将从指定的验证者通道中读取。

协议参数

该包支持执行具有动态可配置参数的 FRI 协议，包括

• 基本 STARK 场
• 扩展场
• 域膨胀因子
• 哈希函数（用于 Merkle 树承诺）
• 折叠因子（用于每个 FRI 层的度数减少）
• 最后一个 FRI 层的最大大小

包功能

此包可以编译以下功能

• std - 默认启用，并依赖于 Rust 标准库。
• concurrent - 意味着 std 并启用多线程证明生成。
• no_std - 不依赖于 Rust 标准库，并启用编译到 WebAssembly。

要使用 no_std 编译，通过 --no-default-features 标志禁用默认功能。

并发执行

当此包编译时启用 concurrent 功能，FriProver 将使用多个线程构建 FRI 层。线程数可以通过 RAYON_NUM_THREADS 环境变量进行配置，通常默认为机器上的逻辑核心数。

参考资料

• StarkWare 关于 低度测试 的博客文章
• 快速 Reed-Solomon 交互式 Oracle 证明接近性
• DEEP-FRI：跳出盒子采样提高正确性
• Swastik Kooparty 关于 DEEP-FRI 的演讲

许可证

本项目采用 MIT 许可证。