邻近间隙：发生了什么以及它如何影响我们的SNARKs

如果你最近一直在关注 ZK 领域，你可能已经听说过最近出现的一系列否定邻近间隙猜想的结果。这个猜想被用于设置基于哈希的 SNARKs 的参数。因此，许多评论员迅速称其为对 SNARKs 的巨大打击。所以最大的问题是：它到底有多糟糕？

在这篇文章中，我想为你提供一些关于发生了什么的视觉直觉，并解释这些结果如何影响当前部署的 SNARKs。我将尝试这样做，而无需通过使我们所有协议成为可能的奇妙数学之旅。如果你有兴趣学习这些数学知识，请告诉我们！一篇“邻近间隙 201”的文章永远不会被排除。

在撰写本文时，一周内发布了 6 篇与 Reed-Solomon 码和邻近间隙相关的论文：

1. Diamond 和 Gruen, 关于随机词距离的分布，( ePrint).

2. Crites 和 Stewart, 关于 Reed-Solomon 邻近间隙猜想 ( ePrint).

3. Bordage, Chiesa, Guan 和 Manzur, 所有多项式生成器都保持着相互关联一致性的距离 ( ePrint).

4. Goyal 和 Guruswami, 子空间设计码和（随机）Reed-Solomon 码的最佳邻近间隙 ( ePrint).

5. Ben-Sasson, Carmon, Haböck, Kopparty 和 Saraf, 关于 Reed-Solomon 码的邻近间隙 ( ePrint).

6. Chatterjee, Harsha 和 Kumar, Reed-Solomon 码的确定性列表解码 ( ECCC).

我将只关注否定该猜想的论文。即上面的第 1、2 和 5 篇论文。为了简洁起见，我将使用作者的首字母来指代它们：分别是 DG、CS 和 BGHKS。

本文中使用的视觉效果和一些解释基于 Angus Gruen 在 ethproofs call #6 中展示的幻灯片。你还可以使用 Mahdi Sedaghat (Soundness Labs) 构建的 这个可爱的互动工具 来调整图表的参数 。

在我们开始之前

为了理解发生了什么，让我们首先解释一下在所有新论文出现之前的现状是什么。

在很高的层面上，SNARKs 利用纠错码来引入冗余，并允许验证者在不读取证明者输入的全部内容的情况下检查属性。为了确保编码正确完成，SNARKs 还使用邻近测试。

SNARK 的效率和安全性取决于代码和邻近测试的参数。虽然有很多参数可以调整，但我们将重点关注：

• 代码的速率 ρ。这是衡量代码引入多少冗余的指标。准确地说，它是冗余量的倒数：ρ=1/2 意味着消息的编码是消息的 2 倍大，ρ=1/4 意味着 4 倍的膨胀，等等...我们的 SNARKs 通常要求分母是 2 的幂，因此我们将重点关注 ρ 在 0 和 1/2 之间的值。
• 邻近测试的邻近参数 δ。这是一个介于 0 和 1-ρ 之间的值，是测试认为“远离”代码的阈值。对于熟悉相对汉明距离概念的读者：调整邻近测试，使得所有距离大于 δ 的输入都以高概率被拒绝。

为这些参数选择值需要在几个权衡之间取得平衡。速率 ρ 设置了一个纯粹的性能权衡：证明者时间与证明大小和验证者时间。另一方面，邻近参数 δ 调整了性能与安全性的权衡。δ 的值越大，证明者时间、验证者时间和证明大小就越好！这是非常理想的。但是，数学的现状还不足以将 δ 设置为任意大。

下图显示了 ρ 和 δ 的所有可能选择，并定义了多个区域：

• 黑色区域表示无效参数。正如我们上面所说，δ 必须小于 1-ρ。
• 绿色和蓝色区域表示我们对其安全性有数学证明的参数集。两个区域中的参数都保证邻近测试的输入要么与代码 δ 接近，要么将以高概率被拒绝。此外，绿色区域中的参数保证测试的输入接近唯一码字。
• 白色区域中的参数具有未知行为。我们没有证据表明它们会产生安全的邻近测试。在此区域中运行代表一种权衡：我们通过使用更大的 δ 值来提高性能，但是我们失去了协议安全性的数学保证。

因此，未解决的问题是：“白色区域内会发生什么？”。到目前为止，许多项目都采用了假设白色区域中的参数是安全的这种方法。这种假设（大致）就是邻近间隙猜想所陈述的内容。

新结果

新结果部分解决了这个问题，并将其与其他数学问题联系起来。我们将分别介绍这两个方面。

理解白色区域

第一个结果以 DG、CS 和 BCHKS 的不同形式出现，即白色区域中的某些参数选择不安全。你可以在下面的图像中看到这一点，我在其中绘制了与之前相同的图表，但还绘制了在 DG 中公式化的新红色区域的近似值。

稍后我们将看到这如何影响我们的 SNARKs。在此之前，让我们讨论一下对白色区域的其余部分所做的进展。

将邻近间隙与其他未解决的问题联系起来

尽管这些论文没有解释整个白色区域的性质，但它们让我们了解了这项任务的难度。CS 和 BCHKS 都表明，确定白色区域的安全状态与称为“list-decoding”问题一样困难。

粗略地说，这个问题可以表述如下：“如果我通过噪声信道发送编码消息，我们可以容忍多少错误，同时仍然能够在另一端恢复小消息列表？”。这里的小意味着列表大小是消息长度的多项式函数。这是一个未解决的问题。

最著名的列表解码算法与图表的蓝色区域完全对应。对于列表解码也存在一个理论上的上限，我们在图表上叠加了这个上限（参见下面的黄线）：

让我强调关于这条新黄线的两个重要事实。首先，也是最重要的是，它代表了安全参数集的新的上限。其次，我们的图表显示它与上一节中的红色区域相交。这不能被视为视觉证据；绘制的红色区域只是 DG 结果的近似值。实际上，我不确定黄线和红线如何相互作用，尤其是因为这两条线都依赖于超出 ρ 和 δ 的参数。

对我们 SNARKs 的影响

对我们 SNARKs 的主要影响是我们不能将参数设置为高于黄线或在红色区域内。纠正此问题需要使用较小的 δ 值，并相应地调整邻近测试的其他参数（对于熟悉邻近测试的人，我指的是查询的数量）。正如我们所看到的，这意味着证明者时间、验证者时间和证明大小将变得更大。

增加多少取决于选择的新参数：

• 如果我们想绝对安全并在经过验证的安全区域（即，不是白色区域）中运行，则证明大小将加倍。验证者时间也将大致加倍。但是，证明者时间将几乎不受影响！这是因为证明者的计算主要由与 ρ-1 成正比的工作决定，而不是 δ。
• 如果我们想继续在未知的白色区域中运行，那么移动到最接近的可能参数将导致证明大小和验证者时间增加高达 2-3%。与前一种情况一样，证明者时间将几乎不受影响。

结论

最后，我将为你提供一些关键要点：

1. 基于哈希的 SNARKs 可以在两种参数方案中运行：经过验证的安全性或猜想的安全性。前者肯定安全，但性能较差。

2. 一些猜想的参数被证明是不安全的。

3. 仍然存在大面积的未知参数。

4. 调整我们的 SNARKs 从先前猜想的安全性变为经过验证的安全性，会使证明大小和验证者时间增加 2 倍。证明者几乎不受影响。

5. 调整我们的 SNARKs 从先前猜想的安全性变为新猜想的安全性，会使证明大小和验证者时间增加 2-3%。证明者几乎不受影响。

zkSecurity 为密码系统提供审计、研究和开发服务，包括零知识证明、MPC、FHE 和共识协议。

了解更多 →

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