STIR：使用更少查询的 Reed-Solomon 邻近度测试

原文：https://gfenzi.io/papers/stir/

作者：Giacomo Fenzi

译者：Kurt Pan

这篇博文简要介绍新工作：“STIR：使用更少查询的 Reed-Solomon 邻近度测试”。该工作与 Gal Arnon 、 Alessandro Chiesa 和 Eylon Yogev 合作完成，完整版 可在 ePrint 上获取 。代码也可在 WizardOfMenlo/stir 获取。这里还有一些可能有用的幻灯片、zkSummit11 演讲的录像 ，以及在 zkPodcast 上的一集。

• https://eprint.iacr.org/2024/390
• https://github.com/WizardOfMenlo/stir
• https://gfenzi.io/presentations/stir.pdf
• https://youtu.be/OLklJjp8KB4?si=-Brr6YLj6YCoQvh9
• https://open.spotify.com/episode/1CRYtmzNHIFNZ0yceS3aO4?si=721b999fff674618

用 表示域 上码率为  Reed-Solomon (RS) 码[^1] 。测试与 码的邻近度的问题为, 给定预言访问 , 确定下面哪个是成立的：

• ，即 是一个 码字。
• ，即 距任何 码字 远（以Hamming距离表示)。

在这项工作中，我们考虑 RS 码的交互式预言邻近证明（IOPP)，即证明者和验证者之间的交互协议，旨在测试与证明者发送的预言消息中的 RS 码的邻近性。

FRI 协议 [BBHR18、BCIKS20、BGKS20] [^2][^3][^4] 就是其中一种 IOPP，它是许多基于 SNARK 的实际系统的基础，这些系统提供了最先进的技术，可对区块链上价值数十亿美元的交易提供保护。

STIR 🥣

我们提出了 STIR（Shift To Improve Rate)，这是一种对 RS 码的具体高效的 IOPP，达到了已知对此问题的任何具体高效 IOPP 中最好的查询复杂性。

在编译成论证后，STIR 在 (i) 证明大小 (ii) 验证者时间 (iii) 验证者哈希方面均优于 FRI。

以 和 为例:

• STIR 证明大小为 160 KiB，而 FRI 为 306 KiB (好 1.8 倍)。
• STIR 验证者执行 2600 次哈希，FRI 为 5600 次,  (好 2.13 倍)。
• STIR 验证者运行时间为 3.8 毫秒, FRI为 3.9 毫秒 (好 1.03 倍)。

概述

STIR 背后的核心直觉是，降低码率会使邻近测试变得更容易。直观上，码率越低，编码中的冗余就越多, 于是验证者可以在其测试中利用更多的结构。

令 ， ， 为两个 码, 并令 为其码率。

一次STIR 迭代执行 次查询, 同时达到两个目标:

1. 将 与 的邻近度测试归约到一个新（虚拟）函数 与 的邻近度测试。
2. 放大距离。粗略地说，如果 是 -远离 的, 那么 就是 -远离[^5] 的（除了大致为 的概率，我们将此称为"不良事件")。

现在测试与 的邻近度更容易了。首先, 多项式的次数减少了 倍。其次, 请注意 , 因此如果 则 , 因此码率更小了。

想象一下现在应用 次 STIR 迭代。令 为每轮测试的函数、重复参数和求值域。以及令 和 。在这些迭代结束时，(诚实的) 证明者将发送次数为 的多项式 。然后验证者在 的 个点处检查 。

分析一下这个协议的可靠性。首先, 对每次迭代中发生不良事件的概率给出上界。在第一轮, 这个概率是 。在之后的几轮中, 由于距离被放大, 现在的概率是:

如果这些不良事件都没有发生, 则多项式 一定与 相距 , 因此最终检查将至少以概率 检测到这一点 。

该协议的整体可靠性误差为:

使得上述和式中的每一项 , 从而 导向设置 以及

码率的减小意味着 值的减少（除了第一次迭代)。这就是使得 STIR 高效的地方。

例如，在 FRI 中，每次迭代之间的码率是保持不变的，因此每一轮（除了第一轮）将查询其相应的预言至少 次。事实上, 由于 FRI 进行关联查询, 因此每一轮的查询次数将与第一轮相同, 至少为 。大致而言, FRI协议的查询总次数为:

而STIR只需进行：

技术

一次STIR 迭代大致由两个步骤组合组成:

折叠

与 FRI 中一样，折叠是将多项式的次数从 降低到 的过程，方法是将其拆分为 个 次多项式，再对他们进行随机组合。我们主要依赖折叠的两个性质：

1. 折叠保持距离（除掉最多 的概率，假设有一个大域，则该概率非常小)。
2. 折叠是局部的。给定对的预言访问 , 计算折叠后求值域中某个点的折叠 的值是高效的（包括在 个位置查询 ）。

商化

函数 与函数 的商，是 的函数，定义为：

其中 是 在上进行插值后的多项式。我们依赖于商的两个性质：

1. 如果所有接近 的低次多项式与 都不一致, 则商与 码距离很远。
2. 商是局部的。给定对的预言访问  计算某个点的商的值是高效的（包括在单个位置查询 。

STIR 迭代

我们在高层次上描述 STIR 的迭代。令 。

1. 折叠随机性：验证者采样并发送 。
2. 折叠：证明者发送 ，即 对 在 上的折叠的求值。（注意折叠是一个函数 , 其中 ，而这里 是大小为 的求值域。)
3. 求值域外采样：验证者采样并发送 。
4. 求值域外回复：证明者发送 。
5. 移动查询: 验证者对 进行采样并查询 以计算这些点处 的折叠值（使用本地映射）。将这些值表示为 。
6. 新预言：验证者将 设置为函数 。要测试的新函数 是 与 的商。 

大致来说，可靠性分析如下：

1. 折叠步保留了距离（除了很小的概率)。
2. 求值域外采样保证了在 的 距离内至多有一个具有 的码字 (除了很小的概率)。

现在, 如果没有这样的码字, 那么 将远离 码 , 因为它是一个商且 。反之，如果存在这样的码字, 则通过第一点 可以与求值域的至多 部分 上的折叠一致 (因为折叠保持了距离)。如果任何采样点 位于不一致部分, 则再次地商将 远离RS码。因此, 除了 的概率, 这种情况将会发生。

基准测试

我们用 Rust 实现了 STIR 和 FRI ，并比较了它们的性能。代码可以在 WizardOfMenlo/stir 找到。下面展示了 时的基准测试结果（FRI是红色, STIR是蓝色）

• https://github.com/WizardOfMenlo/stir 

对于所有测试参数, STIR的证明大小和验证者哈希复杂度都比FRI更好。验证者的整体运行时间也比 FRI 更快, 尤其对于大次数来说。以 和 为例:

• STIR 证明大小为 160 KiB，而 FRI 为 306 KiB (好 1.8 倍)。
• STIR 验证者执行 2600 次哈希，FRI 为 5600 次,  (好 2.13 倍)。
• STIR 验证者运行时间为 3.8 毫秒, FRI为 3.9 毫秒 (好 1.03 倍)。

如需更详细的比较, 请参阅论文第 6 节。

实践考量

我们考虑 STIR 的证明者开销。实践中, FRI 在大量批处理的环境中运行, 即不是测试单个多项式与 RS 码的邻近性，而是测试多项式列表 的随机线性组合。主要的证明者开销是对多项式承诺的开销，其中涉及执行 次FFT 来计算 在 上的求值，然后对这些求值进行承诺。这个开销在FRI 和 STIR 中都有，并且尤其是在批量场景中，会占据主导地位。邻近测试的其余部分 (STIR 比 FRI 慢) 与承诺多项式的数量无关。因此，从 FRI 改为 STIR ，对证明者运行时间的影响几乎可以忽略不计。

此外，STIR 在查询复杂性方面的改进实现了新的参数权衡，与 FRI 相比，可以实现更好的证明者时间、证明大小和验证者哈希复杂度。例如, [ethSTARK] [^6] 将使用 和 的FRI。在我们的实验中, FRI 的证明者运行时间为 11 秒, 产生大小为 KiB的证明, 可以通过执行 次哈希来验证。而使用 和 运行 STIR 会得到一个在 10 秒内运行的证明者，证明大小为 KiB，以及执行 次哈希的验证者。更一般地, 在批量场景中, 我们预计 FRI 和 STIR 的主要开销与 成正比。如果证明大小、验证器哈希的改进允许设置更大的码率（例如 2 倍)，那么 STIR 证明者的主要开销也会减少同样的倍数。