对FRI协议的更深入分析

在本文中，我们将回顾对 ZK 引擎中最重要的部分之一：FRI 协议（实现了交互式 oracle 邻近证明，IOPP）的密码安全性的分析的最新进展。Eli Ben-Sasson、Dan Carmon、Swastik Kopparty 和 Shubhangi Saraf，以及 Ulrich Habock (BCHKS25) 最近上传的一篇文章，重新审视了 2020 年的基础论文“Reed Solomon 代码的邻近差距”（BCIKS20），其中 RS-IOPP 的可靠性是使用相关一致性定理建立的。通过在线性代数中进行更详细和更清晰的使用，在列表解码方案下，他们获得了标准 FRI 改进的安全性能界限。在这里，我们将从概念上修改协议，并概述他们的突破是如何实现的。

熟悉的读者可以直接跳到第 4 节，而新读者则可以阅读前几节，以熟悉所涉及的符号和概念。

1. 基础 Reed-Solomon 格局

让我们从基于代码的密码学的基础知识概述开始：证明者 (P) 和验证者 (V) 之间进行交互式的信息交换 - 其中 P 想要说服 V 他已经执行了某项任务或拥有某些信息。通常，P 声称拥有的信息实际上是计算的结果，形式为低阶多项式 $f$，比如 $deg(f)<k$，其系数位于具有 $q$ 个元素的合适的有限域 $F_q$ 中。

一个完全幼稚的方法是让证明者发送他声称拥有的多项式的系数列表，或者，根据代数基本定理，发送他的多项式的 $deg(f)+1\leq k$ 个评估值的列表。很明显，这种想法效率低下，因为我们将不得不通过信道传递大量信息。

避免暴露 $f$ 的方法之一实际上是在基本域 $F_q$ 中更多的点 $D$ 上评估 $f$，其中 $n=|D|>>k$，这样现在证明者和验证者交换的是更长的评估值列表：

这种做法的效果是，任何攻击者都将面临区分对应于低阶多项式评估值的列表以及不来自此类多项式评估值的列表的挑战。

Reed-Solomon 码： 这是 Reed-Solomon 码 $RS[q,n,k]$ 的非常基本的概念：长度为 $n$ 的向量，完全由在域 $D\subset F_q$ 上以 $k$ 为界的阶的多项式的评估值组成。

作为环境向量空间 $F_q^n$ 的一个子集，Reed-Solomon 码是一个向量子空间，因为多项式的评估是一个线性运算，因此它是 线性码 的一个典型例子。这意味着码字的坐标式加法仍然是一个码字，并且码字与域元素的逐点乘法仍然是一个码字。并非所有码都是线性的。

对于在有限域 $F_q$ 上定义的块长度为 $n$ 的一般码 $C$，对于任何两个码字 $u,v\in F_q^n$，“绝对”汉明距离 $d(u,v)$ 定义为对应符号不同的位置数：

$d(u,v)=|i\in{1,\dots,n}:u_i\neq v_i|$

并且通常使用 $d$ 的分数版本，该版本考虑了块长度：

$\Delta(u,v)=\frac{d(u,v)}{n}$

这允许将 距离解释为两个码字不同的条目的分数。最后，我们回顾一下维度为 $k$ 且块长度为 $n$ 的码的速率的概念，即比率：

$\rho=\frac{k}{n}$

可以从几个方面解释这个数字，即作为 信息内容 的度量：$\rho$% 的传输符号携带消息的实际信息。 冗余 是消息中剩余的 $(1-\rho)$%，是提供纠错功能所消耗的资源（稍后会详细介绍）。较低的速率意味着较高的冗余，并且理论上具有更高的抗噪声能力，但会牺牲吞吐量。

编码理论中的一个重要概念是围绕单词 $w$ 的列表的概念：对于 $w\in F_q^n$ 和 $\delta>0$，它是集合

$List[w,C,\delta]$

它由与单词 $w$ 的距离最多为 $\delta$ 的属于码 $C$ 的码字组成。一个相关的问题是，给定 $w$，以 $\delta$ 为单位，确定列表有多少个元素。对于足够小的 $\delta$，围绕 $w$ 的列表最多包含一个元素，从这个意义上说，我们将说 $w$ 可以被“纠正”为相应的 $u\in C$；这就是代码优良性的通常信息论观点。我们将说，在这些情况下，我们处于“唯一解码方案”中。对于 Reed-Solomon 码，$\delta$ 的这个界限可以用码的速率来表示，并且该方案的特征在于

$\delta<\frac{1-\rho}{2}$

然而，在实现高效、快速的基于代码的算法时，这有时可能过于严格，我们将愿意接受一个足够接近接收到的单词 $w$ 的候选码字列表，而不是单个码字。** 在这些时候，我们将在“列表解码方案”中工作，并且 对于围绕 $w$ 的列表 $L$，列表中的元素不能太多至关重要。 对于这一点，$\delta$ 上有一个界限，通常称为 Johnson 界限，它指出列表 $L$ 中的元素数量是有多项式界的。Johnson 界限适用于任何码，并且是通过组合和几何论证获得的。

Reed-Solomon 码的 Johnson 界限： 具体来说，对于 Reed-Solomon 码，它可以根据速率给出，并且列表解码方案的特征在于

$\delta<1-\sqrt{\rho}=J$

列表大小 $L$ 的标准上限是：

$L\leq \frac{1-\delta}{(1-\delta)^2-\rho}$

有时，此列表大小表示为操作邻近参数 $\delta$ 与实际 Johnson 界限之间的距离；通常，这称为“安全间隙”$\eta$。 自然地，$\eta=J-\delta=1-\sqrt{\rho}-\delta$，然后

$\delta=(1-\sqrt{\rho})-\eta \Longrightarrow 1-\delta=\sqrt{\rho}+\eta$

这转化为

$L\leq \frac{\sqrt{\rho}+\eta}{2\eta(\sqrt{\rho}+\eta)} \approx \frac{\sqrt{\rho}}{2\eta\sqrt{\rho}}=\frac{1}{2\eta}$

FRI 文献中经常引用的依赖关系 $L=O(1/\eta)$ 只是精确判别式界限 $\frac{1-\delta}{(1-\delta)^2-\rho}$ 在邻近参数接近 Johnson 界限时的渐近行为。

2. 什么是 IOPP

回到证明者 (P) 和验证者 (V) 交换信息的问题，让我们看看如何设置该阶段。实际上，最好从明确 IOPP 实际代表什么开始：交互式 Oracle 邻近证明。我们将在本条目化的部分中对这些标题进行情景化：

• 显然，交互式 代表证明者和验证者相互交互、交换信息的概念。

• 现在是粗略的部分：在这些情况下，验证者 (V) 缺乏读取整个证明者 (P) 消息的计算资源；它仅限于打开或查找有限次数的由证明者产生的数据的一小部分。从技术上讲，验证者具有所谓的 Oracle 访问权限：P 提交一个函数 $f:D\rightarrow F$，并且 V 主要作为黑盒 oracle 访问 $f$。 V 选择一个索引 $x\in D$，并且 oracle 响应 $f(x)$。

实际上，这是通过 Merkle 树 实现的。提交是 Merkle 根。oracle 查询响应包括值 $f(x)$ 和 Merkle 身份验证路径。

• 使用 邻近证明 而不是严格的成员资格既是简洁证明中基本理论的必要性，也是实际的限制，因为 为了验证严格的成员资格（向量是否 完全 是一个码字），验证者必须读取整个输入，这需要线性时间 $\Omega(n)$。 为了摆脱这种限制，其思想不是测试单词的码成员资格，而是测试单词是否 $\delta$-接近 该码。在 FRI 协议中，可以使用仅对数数量的查询以高概率检查此属性。

让我们再次强调这些事实：

关键见解： 为了使 IOPP 协议在实践中可行，我们将成员资格 $f\in C$ 的条件放宽为邻近条件 $\Delta(f,C)<\delta$，允许正距离 $\delta>0$：这允许亚线性数量的查询（在块长度 $n$ 中是亚线性的），因为现在验证者不必读取整个消息 - 同时，出于安全原因，但我们不允许 $\delta$ 太大：如果恶意证明者 (P) 想要逃脱虚假陈述 $f$，我们希望使这些机会尽可能渺茫。出于这个原因，我们要求 $\delta$ 受有意义的常数的限制，例如 Johnson 界限。

3. FRI 如何工作

FRI 代表快速 Reed-Solomon 交互式邻近证明，是 RS-IOPP 的缩写版本。它实际上是针对 Reed-Solomon 码调整的 IOPP 协议。它基本上由两个不同的阶段组成：COMMIT 阶段和 Verify 阶段。大部分优化和证明者的工作发生在 COMMIT 阶段，而验证者的工作量发生在 Verify 阶段。我们接下来简要讨论这些阶段。

3.1 COMMIT 阶段

在此阶段，证明者想要证明他拥有 $C_0=RS[q,n,k]$ 中的码字，其中评估域 $D_0$ 是事先约定的。从概念上讲，在与验证者进行第 $i$ 轮交互后，证明者生成一个属于较小 Reed-Solomon 码 $C_i$ 的码字 $f_i$。 这导致属于适当 Reed-Solomon 码序列 $C_i=RS[q,n_i,k_i]$ 的码字序列 $f_1,f_2,\dots f_r$，这样如果 $n=n_0$ 且 $k=k_0$，则对于 $0\leq i\leq r$：

• 评估域是嵌套的：$D_{i+1}\subset D_i$，并且它们的大小均匀相关：这意味着我们具有 $ni=a\cdot n{i+1}$ 形式的关系，其中常数 $a$ 被称为 折叠常数。 通常，$a=2,4$ 或 $8$。 在本说明中，为简单起见，我们将坚持 $a=2$ 的情况。
• 代码的速率在每个步骤保持不变：$\frac{k_i}{n_i}=\rho$。

注意： FRI 协议通常针对特征 $>2$ 的域实例化，并且块大小 $n_0$ 是 2 的幂，这样 $D_0$ 确实是 $n_0$ 次单位根的集合。 此外，代码维度选择为 2 的幂。

对 COMMIT 阶段的简要描述如下：

1. 初始化： 诚实的证明者 P 提交到初始码字 $f_0$（通过 Merkle 根）。

2. 交互循环（$i=0$ 到 $r-1$）：

   • 验证者 V 发送一个随机挑战 $\alpha_i\in F$。

   • P 现在开始在新域 $D_{i+1}={x^2:x\in Di}$ 上的“较小”Reed-Solomon 码 $C{i+1}$ 中构造一个新词，它是前一个域的子集，并包含一半的点。 其背后的原理是，对于一个阶为 $deg(f_i)<k_i$ 的多项式 $f_i$，可以将其写成包含所有偶数阶的多项式和包含所有奇数阶的多项式的和。 这相当于保证存在两个多项式 $g_i$ 和 $h_i$，它们都具有阶度 $<\frac{k}{2}$，这样

     $f_i(X)=g_i(X^2)+Xh(X^2)$

     关于此分解的一个好处是，$g_i$ 和 $h_i$ 在 $x^2$ 处的评估与 $f$ 在 $x$ 和 $-x$ 处的评估线性相关：

     $g_i(x^2)=\frac{f(x)+f(-x)}{2} \text{ 和 } h(x^2)=\frac{f(x)-f(-x)}{2x}$

     因此，证明者现在能够为 $z\in D_{i+1}$ 定义一个新的 Reed-Solomon 码字

     $f_{i+1}(z)=g_i(z)+\alpha_ih_i(z)$

     属于 $C_{i+1}=RS[q,\frac{n_i}{2},\frac{k_i}{2}]$。P 计算并提交到这个新词，并将新的 Merkle 根发送给 V。

3. 终止： 当度数很小（例如，常数）时，该过程停止。P 直接发送最终值。

熟悉经典快速傅里叶变换算法的读者会发现最后几行非常熟悉。

3.2 VERIFY 阶段

我们现在准备描述协议的 VERIFY 阶段：V 验证提交的函数是否满足由挑战 $\alpha_i$ 定义的递归关系。

1. 采样： V 从初始域 $D_0$ 中采样一个随机点 $z$。

2. 一致性检查： 对于每一层 $i$：

   • V 查询 oracle 以获取 $f_i(z)$ 和 $f_i(-z)$（域 $D_i$ 中的对称点）。
   • V 查询 oracle 以获取下一个域 $D{i+1}$ 中的 $f{i+1}(z^2)$。

   • V 验证共线性方程：

     $f_{i+1}(z^2) \stackrel{?}{=} g_i(z^2)+\alpha_i\cdot h_i(z^2)$

     其中 $g_i$ 和 $h_i$ 是从 $f_i$ 的偶数和奇数系数导出的。

此描述引出了本文的中心问题：此装置有多安全？

4. FRI 安全性的改进分析，作为 IOPP 的实例化

这里是最新工作 BCHKS25 的新颖之处，它改进了 BCIKS20 中对 FRI 协议所做的安全性分析。 在题为“里德-所罗门码的邻近间隙”的基础文章中，作者证明了一个基本结果（相关一致性定理），该结果推导出了 FRI 协议的安全性。 在他们最近的论文中，对线性代数事实的详细分析被用来获得协议安全性的更严格的界限，从而使其能够在更广泛的环境中实现。 在深入研究所涉及的数学知识之前，我们需要定义 $\delta$-安全性的概念，该概念建立并微调协议的安全性。

安全性定义： 为了定义 IOPP 具有参数 $(\delta,\epsilon)$ 的安全性意味着什么，我们将简单地首先选择最简单的路径：验证者接受伪造证明 $f^\star$ 的概率应尽可能小。 就与代码的距离而言，让我们将前面的句子改写为：验证者接受距离 $\delta$ 的单词 $f^\star$ 的概率应小于 $\epsilon$。

从数学上讲，设 $C\subseteq F_q^n$ 是一个 Reed-Solomon 码。 设 $P^\star$ 是任何（可能恶意的）证明者策略，该策略输出 oracle 函数 $f^\star:D\rightarrow F$。

定义： 如果以下含义成立，则称 FRI 协议具有 邻近参数 $\delta$ 的安全性错误 $\epsilon$：

如果 $\min_{c\in C}\Delta(f^\star,c)>\delta \Longrightarrow Pr[V^{f^\star} \text{ 接受}]\leq\epsilon$

其中 $\Delta(\cdot,\cdot)$ 表示相对汉明距离。

根据 IOPP 的 $(\delta,\epsilon)$ 安全性的定义，可以定义协议的安全性级别 $\lambda$（以比特为单位）。 它与协议的安全性错误 $\epsilon$ 相关，该错误定义为验证者接受无效语句（即，距离代码 $\delta$ 的码字）的证明的概率。

$\epsilon\leq 2^{-\lambda} \Longleftrightarrow \lambda=-\log_2(\epsilon)$

现在，安全性错误的性质也可以用通俗的方式来描述：接受伪造码字可能是两种组合效应的结果

1. 不诚实的证明者很幸运地提出了一个距离代码 $\delta$ 的伪造码字 $f^\star$，并且在每个折叠步骤中都更接近代码：这通常被称为“折叠错误”或“提交错误”，因为它发生在 COMMIT 阶段，$\epsilon_{commit}$

2. 验证者很不幸，并且在伪造码字 $f^\star$ 实际上与有效码字重合的地方进行抽查：此错误通常被称为“查询错误”，$\epsilon_{query}$。

总的安全性错误由两个主要阶段的错误组成：

$\epsilon{total}\leq \epsilon{commit}+\epsilon_{query}$

特别是，提交错误具有相关性，因为它谈论了整个 FRI 装置的结构特征：我们需要知道不诚实的证明者逃脱伪造证明的机会非常小 - 就附近而言，伪造词在每个折叠步骤中都更接近代码的机会必须可以忽略不计。 这就是著名的相关一致性发挥作用的地方：它指出 每当两个词的折叠足够接近 Reed-Solomon 码时，一定是由于被折叠的词本身与有效的 Reed-Solomon 词具有非常高的一致性，也就是说，它们本身一开始就接近 Reed-Solomon 码。 这排除了“从无效词中制造有效词”的可能性。

5. 发生了什么变化？

在 BCIKS20 中提出的经典分析中，安全性错误是使用在 $r$ 轮折叠上的并集边界得出的，并且作者获得的表达式大致为：

$\epsilon{classic}\approx \frac{n^2}{q} \underbrace{}{\text{提交错误}}+(1-\delta)^l \underbrace{}_{\text{查询错误}}$

其中 $l$ 是查询的数量，$n$ 是块大小，$q$ 是该域中元素的数量。 直接的影响是，为了达到例如 $\lambda=100$ 位的安全性，需要 $\frac{n^2}{q}<2^{-100}$。 这迫使 $q\approx n^2\cdot 2^{100}$，禁止对大的 $n$ 使用小字段（如 64 位字段）。 此外，来自查询阶段的安全位数与 $l$ 线性缩放：

$\lambda_{query}\approx l\cdot \log_2(\frac{1}{1-\delta})$

在他们最近的文章中，Ben-Sasson 等人。 重温了原始证明，并改进了在线性代数论证中对 Guruswami-Sudan 解码器的应用，从而获得了对此错误的更严格，更好的边界。 改进的误差范围约为：

$\epsilon{modern}\approx \frac{n}{q} \underbrace{}{\text{提交错误 (线性)}}}+C\cdot (1-\delta)^l \underbrace{}_{\text{查询错误}}$

（其中 $C$ 是与列表大小相关的小常数，在实践中通常接近 1）。 关键改进可以直接从他们的估计中看出：从 $|S|\approx n^2$ 到 $|S|\approx n$ 的改进从根本上改变了提交阶段安全性错误 $\epsilon=|S|/q$ 中字段大小 $q$ 的要求。

• 在 BCIKS20 中： 为了获得 $\epsilon<2^{-40}$，其中 $n=2^{20}$，需要 $q\approx n^2\cdot 2^{40}=2^{80}$。 这排除了高效的 64 位字段（如 Goldilocks）。
• 在 BCHKS25 中： 对于 $|S|\approx n$，为了获得 $\epsilon<2^{-40}$，需要 $q\approx n\cdot 2^{40}=2^{60}$。 这允许使用小的，对硬件友好的字段（例如，64 位字段），同时保持严格的可证明安全性。

经典 FRI 分析中 $n^2/q$ 错误项的来源以及如何对其进行削减

本节旨在针对熟悉多项式及其在编码理论中的使用的数学读者。 一旦我们清楚某些集合的角色并与符号保持一致，就可以理解提交阶段错误边界的推导。

从概念上讲，可以通过查看证明者通过折叠两个远离代码 $\delta$ 的码字与验证者 (V) 不幸地错误选择 $\alpha\in F_q$ 并获得更接近代码的码字的情况，来解释提交阶段的绑定。 具体来说，令 $u_0,u_1:D\rightarrow F$ 是证明者提交的函数。 令 $C$ 为目标 Reed-Solomon 码。 集合 $S$ 定义为：

$S={z\in F_q:\Delta(u_0+z\cdot u_1,C)\leq\delta}$

换句话说，$S$ 包含每个域元素 $z$，使得线性组合 $u_0+zu_1$ 落在代码的邻近半径 $\delta$ 内，即使 $u_0$ 和 $u_1$ 本身远离 $C$。 在 FRI 协议级别，集合 $S$ 的大小直接决定了提交阶段的安全性错误，因为假设验证者端挑战的均匀随机选择，

提交错误的概率=$Pr_{\alpha\leftarrow F_q}[\alpha\in S]=\frac{|S|}{q}$

当然，为了确保安全性，我们必须证明与字段大小 $q$ 相比，$|S|$ 尽可能小。 在开创性的论文 BCIKS20 中，作者获得了非常重要且著名的结果，即相关一致性定理（简称 CAT），该定理涉及“坏折叠”的集合 $S$ 的大小，并且 几乎是 FRI 安全性的证明。

定理（线上的相关协议）： 令 $u_0,u_1:D\rightarrow F_q$，$m\geq 3$，并定义 $\delta_0(\rho,m)=J-\sqrt{\frac{\rho}{2m}}$。 设置 $\delta\leq\delta_0$。 如果

$$|S| > \frac{(1 + \frac{1}{2m})^7 m^7}{3\rho^{3/2}} n^2$$

那么存在两个 Reed-Solomon 码字 $v_0,v_1\in C$，它们在大小至少为 $(1-\delta)n$ 的集合中共同与 $u_0,u_1$ 重合：

$|x\in D:(u_0(x),u_1(x))=(v_0(x),v_1(x))|>(1-\delta)n$

在这一点上，读者理所当然地感到困惑，因为我们一开始就遇到了非常有趣的表达式，这些表达式奇怪地依赖于一些新的常数。 事实是，对 $S$ 的边界，其形状和定性含义是从 CA 定理的_证明方法_派生的，即使用来自编码理论的一种非常重要的工具，称为 Guruswami-Sudan 解码器。 在评论此功能强大的算法之前，让我们以对 FRI 协议更有意义的术语来研究 CAT 的声明。 通过设置 $\eta>0$，即 $\delta$ 与 Johnson 边界 $J=1-\sqrt{\rho}$ 的距离，并设置 $m=O(\sqrt{\frac{\rho}{\eta}})$，先前的定理允许我们具有 CA 的以下 工作版本：

定理（工作版本）： 令 $u_0,u_1:D\rightarrow F_q$，$\delta,\eta>0$，并假设 $\eta\leq\frac{\sqrt{\rho}}{20}$。 定义 $\delta_0(\rho,\eta)=J-\eta$，并设置 $\delta<\delta_0$。 如果

$|S|>\frac{\rho^2}{(2\eta)^7}n^2q$

那么存在两个 Reed-Solomon 码字 $v_0,v_1\in C$，它们在大小至少为 $(1-\delta)n$ 的集合中共同与 $u_0,u_1$ 重合：

$|x\in D:(u_0(x),u_1(x))=(v_0(x),v_1(x))|>(1-\delta)n$

现在，这更容易理解了。 并且现在，这实际上如何帮助我们证明 FRI 的安全性？ 该定理指出，每当坏折叠的集合“足够大”时，被折叠的词就接近 RS 代码本身。 这意味着恶意证明者没有很高的欺骗机会：他的“坏折叠集合”将具有有限的大小，因此表达式

$\frac{\rho^2}{(2\eta)^7}n^2q$

用作 $\epsilon_{commit}$ 的上限。

那么，我们如何理解为什么在这个表达式中看到二次项 $n^2$ 呢？ 让我们深入研究该结果的证明机制：Guruswami-Sudan 解码器的应用。

Guruswami-Sudan 解码器： 简而言之，Guruswami-Sudan 解码器是一种将以下内容作为输入的算法：一种以对 $(x_i,y_i)\in F^2$ 形式的单词，对于 $1\leq i\leq n$，一个“重数参数” $m$ 和一个整数 $D_X=D_X(m)$。然后在两个阶段进行：

1. 插值阶段： 该算法找到一个多项式 $Q(X,Y)\in F[X,Y]$，使得在每个 $(x_i,y_i)$ 处具有为 $m$ 的阶的零，即满足以下条件的多项式 $Q$

   $Q(x_i,y_i)=0 \text{ 并且 } \nabla_X^{m_X}\nabla_Y^{m_Y}Q(x_i,y_i)=0$

   对于所有非负整数 $m_X,m_Y$，使得 $m_X+m_Y<m$。 在这里，符号 $\nabla_X^{m_X}$ 表示“对变量 $X$ 求 $Q$ 的导数恰好 $m_X$ 次”，通过这种方式，我们指的是在 $(x_i,y_i)$ 处的 Hasse 导数。 选择 m 是为了确保这些方程形成与 Q 的系数兼容的线性方程组，从而产生一个非平凡的多项式。 这通常发生在未知数的数量超过方程的数量时。

2. 因式分解阶段： 该算法找到形式为 $R(X,Y)=Y-P(X)$ 的 $Q(X,Y)$ 的因数

   $Q$ 的消失然后意味着每个因子产生一个 $P$，内插“足够多”的输入点 $(x_i,y_i)$ 。 这种因素的数量由 $D_Y=deg_Y(Q)$（$Q$ 的总 $Y$ 阶）从上面界定。

就解码 Reed Solomon 词的列表而言，GS 解码器产生所有足够接近接收点的词。

BCIKS 中的想法是，由于 GS 解码器适用于任何字段，因此作者现在以 $F_q(Z)$ 作为基字段实例化算法，并将折叠后的词 $u_0(X)+Zu_1(X)$ 解释为该扩展设置中的 Reed Solomon 词。 通过适当地选择 $m$ 和 $D_X$，GS 解码器产生一个插值多项式

$Q(X,Y)\in F_q(Z)[X,Y]$

该多项式的系数先验地是字段 $F_q(Z)$ 的元素，这意味着系数是多项式的商：$Z$ 的有理函数。 因此，这是微调的第一个壮举：

关键观察： 通过仔细查看插值矩阵的秩并对系数矩阵的非奇异次要矩阵应用克莱默法则，可以找到插值问题的非平凡解，这样其系数实际上是 ZZ 中的多项式，并且可以跟踪它们的度数。

现在，我们可以假设 QQ 的系数只是 ZZ 中的多项式，因此我们可以考虑

$Q(X,Y,Z) \in Fq[X,Y,Z]$

正是根据该多项式的加权度数来表达 SS 的界限。 具体来说，作者证明了以下不等式成立：

• $\deg_X(Q) < D_X = (m + \frac{1}{2})\sqrt{\rho n}$
• $\deg_Y(Q) < D_X k = (m + \frac{1}{2})\sqrt{\rho}$
• $\deg_{YZ}(Q) \leq (m + \frac{1}{2})36\sqrt{\rho n}$

其中 $D_{YZ}$ 是 QQ 的 (0,1,1) 加权度。 这是在用 ZZ 中的 1 阶多项式替换 YY 之后测量 ZZ 度的。 这是要注视的一个关键量，因为它控制着 QQ 的消失。

用这种语言来说，关于“坏折叠”集合的下界的假设

$|S| > 2D_X DY^3 D{YZ}$

我们将把本文的其余部分用于理解该不等式，以及至关重要的，如何使用它。

我们将首先利用 GS 算法授予的重数插值：每当 $z \in S$ 时，我们知道存在一个系数在 Fq 中且 $\deg_X(P_z) < k$ 的多项式 $P_z(X)$，从而 $Y - P_z(X)$ 是 $Q(X,Y,z)$ 的因数。 这意味着 $Q(X,P_z(X),z) = 0$ 并且每当 QQ 因式分解为 $Q = A \cdot B$ 时，则

$A(X,P_z(X),z) = 0 \text{ 或 } B(X,P_z(X),z) = 0$ 由于$Fq$是一个域。这允许我们将注意力集中在QQ的不可约因子$\Psi \in Fq[X,Y,Z]$上；假设

$Q(X,Y,Z) = C(X,Z) \prod_i \Psi_i(X,Y,Z)$

其中每个因子$\Psi$都是不可约的，且$\deg_Y(\Psi_i) \geq 1$，为简单起见，我们还假设它们在YY变量中是可分的。现在，对于每个$z \in S$，我们必须有一些因子$\Psi_i$消失，并且由于$\deg_Y(Q) = D_Y$，所以最多有$D_Y$个这样的因子。这意味着必须有一个因子“吸收”至少$\frac{|S|}{D_Y}$个这样的点。设$\Psi$为这样的因子。

现在，下一步是找到“一个好的$x_0$”- 也就是，域DD中的一个好的起点，用来描述这样的多项式$P_z(X)$。为了做到这一点，证明了存在一个$x_0 \in Fq$，使得$\Psi(x_0,Y,Z)$在YY中再次可分。对于这样一个点，对XX的依赖性消失了，并且“好的因子”现在可以表示为

$\Psi(x0,Y,Z) = C\psi(Z) \prodj H{\psi,j}(Y,Z)$

因此，$\Psi$的消失可以转化为当在$(P_z(x_0),z)$处求值时，其因子HH之一的消失。因此，我们将对集合感兴趣

$S_{x_0,\Psi,H} = {z \in S: \Psi \text{ 在 } (X,P_z(X),z) \text{ 处消失且 } H(P_z(x_0),z) = 0}$

从概念上讲，这正是隐函数定理在有限域设置中应用的zz的集合。在代数文献中，这被称为“亨泽尔提升”的俗名。对于这些zz的值，存在一个以$Fq(Z)$为系数且以$(X - x_0)$的幂表示的幂级数形式的解$P_z(X)$。

请注意，$\Psi(x0,Y,Z)$的可分性通常是YY导数不消失。由于我们对多项式解感兴趣，因此$S{x_0,\Psi,H}$中的某些点将不起作用：这些点是级数系数的极点。因此，为了保证$P_z(x_0)$的局部存在，我们需要证明集合

$S' = S_{x_0,\Psi,H} - {z \in S: \text{ 是幂级数中出现的系数的极点}}$

“足够大”。

最大的复杂性来源来自于极点的集合 - 这是因为不能保证$\Psi$的$H_{\psi,j}$因子是首一的：这会在围绕$x_0$的形式幂级数解的系数中产生分母。处理这个问题涉及到权重理论并下降到代数函数域理论（这是一个引人入胜的主题，稍微偏离了本次回顾的目的）。

言归正传，相关协议定理中的假设

$|S| > 2D_X DY^3 D{YZ}$

使得首先找到一个重要的下界，用于导出形式幂级数解的zz：

$|S_{x_0,\Psi,H}| \geq \frac{|S|}{D_Y} > 2\frac{D_X DY^2 D{YZ}}{D_Y}$

作者还使用 Schwarz-Zippel 引理的类似物（他们附录中的引理 A.1）获得了极点数的上限，该引理在其证明中被关键地使用了三次。** 首先，获得极点集的上限，读作$DY^2 D{YZ}$

反过来，这会产生$S'$中元素数量的下限：

$|S'| > |S_{x_0,\Psi,H}| - DY^2 D{YZ} > 2D_X DY^2 D{YZ} - DY^2 D{YZ} = DY^2 D{YZ}(2D_X - 1)$

其次，这个下限正是 Schwarz-Zippel 引理要求的，以保证XX中至多kk次的多项式解；然后再次使用它来保证（与代数基本定理一起）解在ZZ中的次数至多为1，因此

$P(X,Z) = V_0(X) + ZV_1(X)$

产生承诺的 Reed-Solomon 码字$v_0$和$v_1$，这结束了BCIKS中设置的路径。

在最近的BCHKS25中，进行了两项改进：首先，在克莱姆法则级别上进行了一个更严格的线性代数论证，产生了一个具有较小$D_{YZ}$的插值多项式QQ：

$D_{YZ} \leq \frac{1}{3}(m + \frac{1}{2})^2 nk$

• 现在mm的选择必须是$m \geq 3$，并且仍然允许进行一些优化。其次，在进行与BCIKS20相同的分析时，更仔细地观察集合$S_{x_0,\Psi,H}$，即使保持使用 Schwarz-Zippel 引理用于代数函数域，也能得出SS的较小下界。发生的情况是，在原始论文中，关于此集合的下限是根据QQ的加权次数界限建立的，而该集合是根据QQ的因子定义的。

在继续之前，让我们设置：

• $D_{\Psi_i}^Y = \deg_Y(\Psi_i)$
• $D{H{i,j}}^Y \equiv D{H{\psi_i,j}}^Y = \degY(H{\psi_i,j})$
• $D_{\Psii}^Z = \deg{YZ}(\Psi_i) - \deg_Z(C_i)$ - 不包括纯ZZ因子的$\Psi_i$部分的加权（1,1）次数。

因为我们将使用这些量来限制集合$S_{x_0,\Psii,H{ij}}$的大小。现在作者证明存在一对因子$\Psii, H{ij}$，使得

1. $|S_{x_0,\Psii,H{ij}}| \geq 2\frac{DX D{\Psii}^Y D{H{ij}}^Y}{D{\Psi_i}^Z}$
2. $|S_{x_0,\Psii,H{ij}}| > D_{\Psii}^Y D{H{ij}}^Y D{\Psi_i}^Z + \delta n + 1$

同时成立；如果这些不等式对所有可能的对都不能成立，那么$S_{x_0,\Psii,H{ij}}$集合构成SS的划分这一事实意味着，通过对所有可能的因子求和，我们得到

$|S| \leq 2D_X DY^2 D{YZ} + (\delta n + 1)D_Y$

最后一个不等式是通过正式求和并在分解多项式时使用次数的可加性而获得的（这就是使上面有趣的次数表示法消失并最终弹出QQ的次数的原因）；详细信息在BCHKS25的第3节中。

这个结果说明的是，无论何时$|S| > 2D_X DY^2 D{YZ} + (\delta n + 1)D_Y$，都可以从Hensel Lifting中找到XX和ZZ中具有足够次数的多项式，从而产生相关协定结论中出现的承诺的Reed-Solomon码字。

该分析的最后一部分相当于查看使用改进的QQ加权次数界限的SS界限；通过失去$D_Y$中的线性部分，我们得到

$|S| > 2D_X DY^2 D{YZ} > 2(m + \frac{1}{2})\sqrt{nk} \cdot ((m + \frac{1}{2})nk)^2 \cdot \frac{1}{3}(m + \frac{1}{2})nk$

并且由于代码的速率定义为$\rho = \frac{k}{n}$，我们得到

$|S| > \frac{2}{3}(m + \frac{1}{2})^5 \sqrt{n} (nk)(nk)(nk) = \frac{2}{3}(m + \frac{1}{2})^5 \rho^{3/2} \cdot n$

这几乎是承诺的改进，相对于以前已知的界限

$|S| > \frac{(m + \frac{1}{2})^7}{3} \rho^{3/2} \cdot n^2$

为了最终落地，这个讨论一直在讨论什么：如果对于足够多的zz，码字$u_0(X) + zu_1(X)$与代码的距离接近$\delta$，那么一个隐函数参数会产生Reed-Solomon码字$v_0(X), v_1(X)$，它们与原始码字的距离接近$\delta$（所有这些都取决于$\delta$的选择和Reed-Solomon代码的参数）。因此，一个恶意的证明者欺骗验证者的机会确实很小，即与评估域DD的大小呈线性关系。

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