[BCIKS20] Proximity Gaps 论文 soundness 解析

• Jade Xie [email protected]
• Yu Guo [email protected]

论文 [BCIKS20] 对 [BBHR18] 中的 FRI 协议的 soundness 进行了改进，主要分析了 batched FRI 的情况。本文将详细解析 [BCIKS20] 论文中关于 batched FRI soundness 的内容。

Introduction¶

在交互证明，分布式存储以及密码学等背景下，出现了各种协议，这些协议引出了关于一个线性编码 $V \subset \mathbb{F}_q^n$ 的 proximity 问题，其中 $\mathbb{F}_q$ 是有限域，$V$ 的最小的相对距离为 $\delta_V$ 。这些协议假设我们可以获得关于一批向量 $\textbf{u} = \{u_0, \cdots, u_l \} \subset \mathbb{F}_q^n$ 的 oracle，它们的 soundness 要求每个向量 $u_i$ 在相对 Hamming 距离上接近 $V$ 。另外，soundness 是某些向量到 code $V$ 之间的最大距离的一个函数，如果这个距离变大，那么 Verifier 拒绝的概率会降低。因此，我们想找到这样的协议，能够最小化对 $\mathbf{u}$ 中元素的 query 的数量，同时最大化能识别某个向量 $u_i$ 明显远离 $V$ 的概率。

❓ 疑问

• 如何理解下面这句话？ Furthermore, soundness deteriorates as a function of the largest distance between some vector ui and the code V . soundeness 会随着某些向量 $u_i$ 与 code $V$ 之间的最大距离的增加而降低，也就是此时 Verifier 拒绝的概率就降低了？
• 如何对 soundness 降低进行清楚地讲解呢？

由于 $V$ 的线性性，一个自然的方法([RVW13])是：在 span($\textbf{u}$)(即 $\textbf{u}$ 中各元素的线性组合) 中均匀地随机一个向量 $u'$ ，记 $u'$ 与 $V$ 之间的距离为 $\Delta(u', V)$ ，将这个距离视为 $\textbf{u}$ 中某些元素与 $V$ 之间的最大距离的一个 proxy（代理）。为了证明 soundness ，我们想要即使只有一个 $u_i$ 距离 $V$ 中的所有元素有 δ-远，那么随机选择的 $u'$ 也距离 $V$ 很远。

在下文中，用 Δ 表示相对 Hamming 距离。当 $\Delta(u, v) \le \delta$ 对某个 $v \in V$ 成立时，称为 “ $u$ 与 $V$ 的距离有 δ -近”，记作 $\Delta(u, V) \le \delta$ ；否则称为 “ $u$ 与 $V$ 的距离有 δ -远”，记作 $\Delta(u, V) > \delta$ 。

关于这个问题，一些研究结果为：

1. [AHIV17] 如果 $\delta < \delta_V /4$ ，几乎所有的 $u' \in \text{span}(\mathbf{u})$ 距离 $V$ 有 δ -远。
2. [RZ18] 将上述结果提高到 $\delta < \delta_V /3$ 。
3. [BKS18] 提高到 $\delta < 1 - \sqrt[4]{1 - \delta_V}$ 。
4. [BGKS20] 提高到 $\delta < 1 - \sqrt[3]{1 - \delta_V}$ ，但这个界对 RS 编码是 tight 的，因为当 $n = q$ 时可以达到这个界。

🤔 思考

• 为什么研究的重心都想要提高这个 δ 的上界呢？关于这个问题，目前我的想法是： δ 的上界这里是和 $\delta_V$ 有关的，对于 RS code ，$\delta_V = 1 - \rho$ ，实质也就是和码率相关，那么提高上界也就意味着降低了码率，那么就意味着更多的冗余，如果以相同的安全性，或者同样的高概率来拒绝出错的情况，此时需要的query就更少了。或者这样说，如果对于同样一个协议，query 的数量固定，δ 越大，拒绝的概率也就越大，也就提高了 soundness。
• 上面分析的第 2 点与 “Furthermore, soundness deteriorates as a function of the largest distance between some vector $u_i$ and the code V .” 似乎矛盾，这句话说的是 δ 越大，soundness 越小？这一点该如何理解呢？

目前我们关心的一个问题是：对于哪些码以及什么范围的 δ ，以下的陈述成立？

如果某个 $u^* \in \text{span}(\mathbf{u})$ 与 $V$ 有 δ -远，那么对于几乎所有的 $u' \in \text{span}(\mathbf{u})$ ，$u'$ 与 $V$ 也有 δ -远。

[BCIKS20] 论文的主要结论之一表明，当 $V$ 是一个在足够大的域上的 RS 码（域的大小与码的块长度呈多项式关系）并且 δ 小于 Johnson/Guruswami-Sudan list decoding 界时，上述陈述成立。接下来，我们称其为 proximity gap 。

Proximity Gaps¶

先给出 Proximity Gaps 的定义。

Definition 1.1 [BCIKS20, Definition 1.1] (Proximity gap). Let $P \subset \Sigma^n$ be a property and $C \subset 2^{\Sigma^n}$ be a collection of sets. Let Δ be a distance measure on $\Sigma^n$ . We say that $C$ displays a $(\delta, \epsilon)$ -proximity gap with respect to $P$ under Δ if every $S \in C$ satisfies exactly one of the following:

1. $\Pr_{s \in S} [\Delta(s, P) \le \delta] = 1$ .
2. $\Pr_{s \in S} [\Delta(s, P) \le \delta] \le \epsilon$ .

We call δ the proximity parameter and ε is the error parameter. By default, Δ denotes the relative Hamming distance measure.

对于 RS code ，如果 $V \subset \mathbb{F}^n$ 是 RS 编码 ，对应上述定义中的 $P$ ，并且 $A \subset \mathbb{F}^n$ 是一个 affine space (仿射空间) ，对应于上述定义中的 $S$ ，那么要么 $A$ 中的所有元素离 $V$ 有 δ -近，要么 $A$ 中的几乎所有元素离 $V$ 有 δ -远。换句话说，不会有这样的 affine space $A$ ，其中大概一半的元素离 $V$ 比较近，但同时另一半元素离 $V$ 比较远。

如下图所示，$A$ 是一个 affine space，这里用一条线表示，编码空间 $V$ 中的元素用黑色的点表示，以这些点为圆心，以 δ 为半径画圆。那么只有两种情况：

1. 线 $A$ 上的所有元素都落入了绿色的圆形区域内。

2. 线上只有少量的元素落入了绿色的圆形区域内。 $A$ 中的元素不可能一半在圆形区域内，一半在圆形区域外，这也是 gap 的含义，将 $A$ 中的所有元素落入的情况分成了恰好分成了两种情况，而这两种情况之间根据相对 Hamming 距离形成了一个巨大的 gap 。

在下文中，用 $\mathbb{F}_q$ 表示大小为 $q$ 的有限域，$\text{RS}[\mathbb{F}_q,\mathcal{D},k]$ 表示维数为 $k+1$ ，块长度(blocklength) 为 $n = |\mathcal{D}|$ 的 RS 编码，其码字是在 $\mathcal{D}$ 上求值(evaluated)，次数 $\le k$ 的多项式。用 ρ 表示码率， 则 $\rho = \frac{k+1}{n}$ 。δ 表示相对于 RS code 的相对 Hamming 距离，ε 表示 error 参数，也就是一个“坏事件(bad event)”发生的概率。

下面给出 RS code 的 Proximity gaps 定理。

Theorem 1.2 [BCIKS20, Theorem 1.2] (Proximity gap for RS codes). The collection $C_{\text{Affine}}$ of affine spaces in $\mathbb{F}_q^n$ displays a $(\delta, \epsilon)$ -proximity gap with respect to the RS code $V := \text{RS}[\mathbb{F}_q, \mathcal{D}, k]$ of blocklength $n$ and rate $\rho = \frac{k+1}{n}$ , for any $\delta \in (0, 1 - \sqrt{\rho})$ , and $\epsilon = \epsilon(q, n, \rho, \delta)$ defined as the following piecewise function:

• Unique decoding bound: For $\delta \in (0,\frac{1 - \rho}{2}]$ , the error parameter ε is

• List decoding bound: For $\delta \in (\frac{1 - \rho}{2}, 1 - \sqrt{\rho})$ , setting $\eta := 1 - \sqrt{\rho} - \delta$ , the error parameter ε is

🤔 Question

• δ 越大，落入圆形区域的元素可能更多，也就是 $\epsilon_{\text{J}}$ 相比 $\epsilon_{\text{U}}$ 更大一些。是这个原因吗？

Correlated agreements¶

论文中证明的主要定理是 correlated agreement ，对于在 $\mathbb{F}^{\mathcal{D}}$ 中的两个向量 $u_0, u_1 \in \mathbb{F}^{\mathcal{D}}$ ，在 $\mathbb{F}$ 中选一个随机数 $z$ ，我们关心用 $z$ 进行线性组合后的 $u_0 + zu_1$ 所形成的空间与 $V$ 之间的距离，也就是一维的 affine space $A = \{u_0 + z u_1 : z \in \mathbb{F}\}$ 。correlated agreement 结论说的是如果在 $A$ 中有足够多的元素距离 RS code 空间 $V$ 足够近（ δ - 近），那么一定存在一个非平凡的 subdomain $\mathcal{D}' \subset \mathcal{D}$ ，其大小至少是 $\mathcal{D}$ 大小的 $1 - \delta$ 倍，使得限制 $u_0, u_1$ 在 $\mathcal{D}'$ 上，有有效的 RS code $v_0, v_1$ ，满足它们分别在 $\mathcal{D}'$ 上与 $u_0, u_1$ 一致。我们就说这样的 $\mathcal{D}'$ 有 correlated agreement 性质，即 $u_0, u_1$ 和 $A$ 中的元素不仅分别与 RS 码有很大的 agreement ，而且还共享一个共同的很大的 agreement 集合。这个结果有两个参数范围，一个是 unique decoding 范围内的 proximity 参数，另一个是 list decoding 范围内的 proximity 参数。

以下给出了三种情况的 correlated agreement。结合论文中其他关于 correlated agreement 的结论，如下表所示。

下面三个定理分别对应线、低次参数曲线以及 affine spaces 的 correlated agreement 定理。

Theorem 1.4 [BSCIK20, Theorem 1.4] (Main Theorem - Correlated agreement over lines). Let $V, q, n, k$ and ρ be as defined in Theorem 1.2. For $u_0, u_1 \in \mathbb{F}_q^{\mathcal{D}}$ , if $\delta \in (0, 1 - \sqrt{\rho})$ and

where ε is as defined in Theorem 1.2, then there exist $D' \subset D$ and $v_0, v_1 \in V$ satisfying

• Density: $|D'|/|D| \ge 1 - \delta$ , and
• Agreement: $v_0$ agrees with $u_0$ and $v_1$ agrees with $u_1$ on all of $D'$ .

令 $\mathbf{u} = \{u_0, \ldots, u_l \} \subset \mathbb{F}_q^{\mathcal{D}}$ ，则次数为 $l$ 的 parameterized curve 是由 $\mathbf{u}$ 生成的如下的在 $\mathbb{F}_q^{\mathcal{D}}$ 中的向量的集合，

Theorem 1.5 [BSCIK20, Theorem 1.5] (Correlated agreement for low-degree parameterized curves). Let $V, q, n, k$ and ρ be as defined in Theorem 1.2. Let $\mathbf{u} = \{u_0, \cdots, u_l\} \subset \mathbb{F}_q^{\mathcal{D}}$ . If $\delta \in (0, 1 - \sqrt{\rho})$ and

where ε is as defined in Theorem 1.2, then there exist $\mathcal{D}' \subset \mathcal{D}$ and $v_0, \cdots, v_l \in V$ satisfying

• Density: $|\mathcal{D}'|/|\mathcal{D}| \ge 1 - \delta$ , and
• Agreement: for all $i \in \{0, \cdots, l\}$ , the functions $u_i$ and $v_i$ agree on all of $\mathcal{D}'$ .

Theorem 1.6 [BSCIK20, Theorem 1.6] (Correlated agreement over affine spaces). Let $V, q, n, k$ and ρ be as defined in Theorem 1.2. For $u_0, u_1, \cdots, u_l \in \mathbb{F}_q^{\mathcal{D}}$ let $U = u_0 + \text{span}\{u_1, \cdots, u_l\} \subset \mathbb{F}_q^{\mathcal{D}}$ be an affine subspace. If $\delta \in (0, 1 - \sqrt{\rho})$ and

where ε is as defined in Theorem 1.2, then there exist $\mathcal{D}' \subset \mathcal{D}$ and $v_0, \cdots, v_l \in V$ satisfying

• Density: $|\mathcal{D}'|/|\mathcal{D}| \ge 1 - \delta$ , and
• Agreement: for all $i \in \{0, \cdots, l\}$ , the functions $u_i$ and $v_i$ agree on all of $\mathcal{D}'$ .

Furthermore, in the unique decoding regime $\delta \in \left(0, \frac{1 - \rho}{2}\right]$ , there exists a unique maximal $\mathcal{D}'$ satisfying the above, with unique $v_i$ .

Correlated Weighted Agreement¶

如果要分析 FRI 协议的 soundness ，就需要 Theorem 1.5 的 weighted 版本。

对于一个给定的 weight 向量 $\mu : \mathcal{D} \rightarrow [0,1]$ ，$u,v$ 之间(相对的) μ -agremment 定义为

也就是在权重 μ 之下看 $u$ 与 $v$ 在 $\mathcal{D}$ 上一致的比例有多少。如果令 $\mu \equiv 1$ ，那么

一个 word $u$ 与一个线性码 $V$ 之间的 agreement 为 $u$ 与 $V$ 之间的一个码字之间的最大的 agreement ，

定义 subdomain $\mathcal{D}' \subset \mathcal{D}$ 的加权(weighted) 大小为

将上面定义中的 $\mathcal{D}'$ 定义为 $\{x \in \mathcal{D}: u(x) = v(x)\}$ ，则 agreement 满足 $\text{agree}_{\mu}(u,v) = \mu(\{x \in \mathcal{D}: u(x) = v(x)\})$ 。

最后，对于 $\mathbf{u} = \{u_0, \cdots, u_l\}$ ，其中 $u_i \in \mathbb{F}_q^{\mathcal{D}}$ 是一组 word ，μ -weighted correlated agreement 是 subdomain $\mathcal{D}' \subset \mathcal{D}$ 的最大 μ -weighted 大小，使得 $\mathbf{u}$ 在 $\mathcal{D}'$ 上的限制属于 $V|_{\mathcal{D}'}$ ，即对于每个 $i = 0, \cdots, l$ ，存在 $v_i \in V$ 使得 $u_i|_{\mathcal{D}'} = v_i|_{\mathcal{D}'}$ 。当 μ 未指定时，它被设置为常数权重函数 1 ，这恢复了在前面讨论的 correlated agreement 度量的概念。

接下来，我们假设权重函数 μ 具有某些结构，具体来说，所有权重 $\mu(x)$ 都是形式 $\mu(x) = \frac{a_x}{M}$ ，其中 $a_x$ 是变化的整数，且有共同的分母 $M$ 。对于 FRI soundness 的特殊情况（其中 $M$ 等于应用 FRI 协议的 RS 码的 blocklength），这个假设确实成立。以下是定理 1.5 的加权推广。

Theorem 7.1 [BSCIK20, Theorem 7.1] (Weighted correlated agreement over curves – Version I). Let $V, q, n, k$ and ρ be as defined in Theorem 1.2. Let $\mathbf{u} = \{u_0, \cdots, u_l\} \subset \mathbb{F}_q^{\mathcal{D}}$ . Let $\alpha \in (\sqrt{\rho}, 1)$ and let $\mu : \mathcal{D} \rightarrow [0,1]$ be a vector of weights, whose values all have denominator $M$ . Suppose

where ε is as defined in Theorem 1.2 (with $\eta = \min(\alpha - \sqrt{\rho}, \frac{\sqrt{\rho}}{20})$ ), and additionally suppose

Then there exists $\mathcal{D}' \subset \mathcal{D}$ and $v_0, \cdots, v_l \in V$ satisfying

• Density: $\mu(\mathcal{D}') \ge \alpha$ , and
• Agreement: for all $i \in \{0, \cdots, l\}$ , the functions $u_i$ and $v_i$ agree on all of $\mathcal{D}'$ .

仅适用于 Johnson 界限范围的一种更精确的形式如下。

Theorem 7.2 [BSCIK20, Theorem 7.2] (Weighted correlated agreement over curves – Version II). Let $V, q, n, k$ and ρ be as defined in Theorem 1.2. Let $\mathbf{u} = \{u_0, \cdots, u_l\} \subset \mathbb{F}_q^{\mathcal{D}}$ . Let $\mu : \mathcal{D} \rightarrow [0,1]$ be a vector of weights, whose values all have denominator $M$ . Let $m \ge 3$ and let

Let

and suppose

Then $u_0, \ldots, u_l$ have at least α correlated μ -agreement with $V$ , i.e. $\exists v_0, \cdots, v_l \in V$ such that

Theorem 7.3 [BSCIK20, Theorem 7.3] (Weighted correlated agreement over affine spaces). Let $V, q, n, k$ and ρ be as defined in Theorem 1.2. Let $\mathbf{u} = \{u_0, \cdots, u_l\} \subset \mathbb{F}_q^{\mathcal{D}}$ and let $U = u_0 + \text{span}\{u_1, \cdots, u_l\} \subset \mathbb{F}_q^{\mathcal{D}}$ be an affine subspace. Let $\alpha \in (\sqrt{\rho}, 1)$ and let $\mu : \mathcal{D} \rightarrow [0,1]$ be a vector of weights, whose values all have denominator $M$ . Suppose

where ε is as defined in Theorem 1.2 (with $\eta = \min(\alpha - \sqrt{\rho}, \frac{\sqrt{\rho}}{20})$ ), and additionally suppose

Then there exist $\mathcal{D}' \subset \mathcal{D}$ and $v_0, \cdots, v_l \in V$ satisfying

• μ-Density: $\mu(\mathcal{D}') \ge \alpha$ , and
• Agreement: for all $i \in \{0, \cdots, l\}$ , the functions $u_i$ and $v_i$ agree on all of $\mathcal{D}'$ .

同样地，对于 Theorem 7.3 也有关于 Johnson 界限的更精确的形式。

Theorem 7.4 [BSCIK20, Theorem 7.4] (Weighted correlated agreement over affine spaces – Version II). Let $V, q, n, k$ and ρ be as defined in Theorem 1.2. Let $\mathbf{u} = \{u_0, \cdots, u_l\} \subset \mathbb{F}_q^{\mathcal{D}}$ and let $U = u_0 + \text{span}\{u_1, \cdots, u_l\} \subset \mathbb{F}_q^{\mathcal{D}}$ be an affine subspace. Let $\mu : \mathcal{D} \rightarrow [0,1]$ be a vector of weights, whose values all have denominator $M$ . Let $m \ge 3$ and let

Suppose

Then $u_0, \ldots, u_l$ have at least α correlated μ -agreement with $V$ , i.e. $\exists v_0, \cdots, v_l \in V$ such that

FRI 协议¶

FRI 协议的目的是为了在 IOP 模型中，去解决 Reed-Solomon proximity testing 问题，即对于一个接收到的 word $f^{(0)}: \mathcal{D}^{(0)} \rightarrow \mathbb{F}$ ，验证它到 $V^{(0)} := \text{RS}[\mathbb{F}, \mathcal{D}^{(0)}, k^{(0)}]$ 之间的 proximity ，如果 $f^{(0)}$ 属于 $V^{(0)}$ ，就接受；如果距离 $V^{(0)}$ 有 δ 远，就拒绝。FRI 协议适用于任何 evaluation domain $\mathcal{D}^{(0)}$ 是 2-smooth 群 的陪集的情况，即对于任何的 $\mathcal{D}^{(0)}$ ，其是一个大小为 $2^s$ 的（加法或乘法）群的陪集，其中 $s$ 是一个整数。因此，为简化描述，假设群 $\mathcal{D}^{(0)}$ 是乘法的。FRI 协议有两个阶段，分别是 COMMIT 阶段与 QUERY 阶段。

在 COMMIT 阶段，经过有限次 $r$ 轮的交互，会生成一系列的函数 $f^{(1)}: \mathcal{D}^{(1)} \rightarrow \mathbb{F}, f^{(2)}: \mathcal{D}^{(2)} \rightarrow \mathbb{F}, \cdots,f^{(r)}: \mathcal{D}^{(r)} \rightarrow \mathbb{F}$ 。每一次迭代， domain 的大小 $|\mathcal{D}^{(i)}|$ 都会缩小。假设对于一个诚实的 prover， $f^{(0)}$ 是 low-degree ，那么对于每一个 $f^{(i)}$ ，它们也都会是 low-degree 的（见命题 1）。在第 $i$-轮开始时，prover 的消息 $f^{(i)}: \mathcal{D}^{(i)} \rightarrow \mathbb{F}$ 已经生成，并且 verifier 可以访问该消息的 oracle 。Verifier 现在发送一个均匀随机的 $z^{(i)} \in \mathbb{F}$ ，然后 prover 回复一个新的函数 $f^{(i+1)}: \mathcal{D}^{(i+1)} \rightarrow \mathbb{F}$ ，其中 $\mathcal{D}^{(i+1)}$ 是 $\mathcal{D}^{(i)}$ 的一个（2-smooth）strict 子群，意思是 $\mathcal{D}^{(i)}$ 不仅是 $\mathcal{D}^{(i+1)}$ 的子群，同时也是其真子集。

$\mathcal{D}^{(i+1)}$ 将 $\mathcal{D}^{(i)}$ 划分成大小为 $l^{(i)} := |\mathcal{D}^{(i)}|/|\mathcal{D}^{(i+1)}|$ 的陪集。令 $C_g^{(i)}$ 表示对应于 $g \in \mathcal{D}^{(i+1)}$ 的陪集，即

意思就是在 $\mathcal{D}^{(i)}$ 中选取那些能够通过映射 $q(x) = x^{l^{(i)}}$ 映射到 $\mathcal{D}^{(i+1)}$ 中的 $g$ 的元素，这些元素组成了集合 $C_g^{(i)}$ ，其也是陪集。

对于每个陪集 $C_g^{(i)}$ ，插值映射(interpolation map) $M_g^{(i)}$ 是一个可逆的线性映射 $M_g^{(i)}: \mathbb{F}^{C_g^{(i)}} \rightarrow \mathbb{F}^{l^{(i)}}$ ，它将 $f^{(i)}|_{C_g^{(i)}}: C_g^{(i)} \rightarrow \mathbb{F}$ （即限制 $f^{(i)}$ 在 domain $C_g^{(i)} \subset \mathcal{D}^{(i)}$ 上）映射到多项式 $P_{\mathbf{u}^{(i)}(g)}^{(i)}(Z) = \sum_{j<l^{(i)}} u_j^{(i)}(g) Z^j$ 的系数向量 $\mathbf{u}^{(i)}(g) = (u_0^{(i)}(g), \ldots, u_{l^{(i)}-1}^{(i)}(g))^{\intercal}$ （这里与论文原文表示一致，都表示列向量，不过原文没有加上转置符号），其中 $P_{\mathbf{u}^{(i)}(g)}^{(i)}(Z)$ 是插值 $f^{(i)}|_{C_g^{(i)}}$ 的多项式。换句话说，$M_g^{(i)}$ 是由 $C_g^{(i)}$ 生成的 Vandermonde 矩阵的逆，这意味着 $\left(M_g^{(i)}\right)^{-1} \cdot (u_0, \ldots, u_{l^{(i)}-1})^{\intercal}$ 是多项式 $P_{\mathbf{u}}(X) = \sum_{i<l^{(i)}} u_i X^i$ 在陪集 $C_g^{(i)}$ 上的 evaluation 。

👀 Notice 本文为保持前后一致，用 $(x_0, \ldots, x_n)$表示行向量，而 $(x_0, \ldots, x_n)^{\intercal}$ 表示列向量，也可写为： $$

$$\begin{bmatrix} > x_0\\ > x_1\\ > \vdots\\ > x_n > \end{bmatrix}$$

(23)

$$

下面详细解释下上面对插值映射的描述。根据 $C_g^{(i)}$ 的定义，知道其中的元素有 $l^{(i)}$ 个，设 $C_g^{(i)} =\{g'_1, \cdots, g'_{l^{(i)}}\}$ ，我们可以将由 $C_g^{(i)}$ 生成的 Vandermonde 矩阵写出来：

则 $M_g^{(i)} = V_{C_g^{(i)}}^{-1}$ ，是由 $C_g^{(i)}$ 生成的 Vandermonde 矩阵的逆，因此

通过上述推导看出 $\left(P_{\mathbf{u}}(g'_1), P_{\mathbf{u}}(g'_2) \cdots, P_{\mathbf{u}}(g'_{l^{(i)}}) \right)^{\intercal}$ 是多项式 $P_{\mathbf{u}}(X) = \sum_{i<l^{(i)}} u_i X^i$ 在陪集 $C_g^{(i)}$ 上的 evaluation ，因此 $\left(M_g^{(i)}\right)^{-1} \cdot (u_0, \ldots, u_{l^{(i)}-1})^{\intercal}$ 是多项式 $P_{\mathbf{u}}(X) = \sum_{i<l^{(i)}} u_i X^i$ 在陪集 $C_g^{(i)}$ 上的 evaluation 。

下面的命题使用了上述的符号，重新叙述了 [BBHR18, Section 4.1]，与 [BBHR18, Section 4.1] 不同的是，是在乘法群而不是加法群上进行的。该命题描述的就是保持 low-degree 的性质。

Claim 1 [BCIKS20, Claim 8.1]. Suppose that $f^{(i)} \in \text{RS}[\mathbb{F}, \mathcal{D}^{(i)}, k^{(i)}]$ where $k^{(i)} + 1$ is an integral power of 2 . Then, for any $z^{(i)} \in \mathbb{F}$, letting $\mathbf{z}^{(i)} = \left(\left(z^{(i)}\right)^0, \left(z^{(i)}\right)^1, \ldots, \left(z^{(i)}\right)^{l^{(i)}-1}\right)^{\intercal}$, the function $f_{f^{(i)},z^{(i)}}^{(i+1)}: \mathcal{D}^{(i+1)} \rightarrow \mathbb{F}$ defined on $g \in \mathcal{D}^{(i+1)}$ by

is a valid codeword of $V^{(i+1)} := \text{RS}[\mathbb{F}, \mathcal{D}^{(i+1)}, k^{(i+1)}]$ where $k^{(i+1)} := \frac{k^{(i)}+1}{l^{(i)}} - 1$.

根据 [BBHR18] 以及上面的记号，在 FRI 协议的 COMMIT 阶段，固定一个 $g \in \mathcal{D}^{(i+1)}$ ，下一步构造的 $f_{f^{(i)},z^{(i)}}^{(i+1)}(g) := P_{\mathbf{u}^{(i)}(g)}^{(i)}(z^{(i)})$ ，下面理解下上述构造的式子。

下面说明下命题 1 给的第二个等式，即 $\mathbf{u}^{(i)}(g) = M_g^{(i)} \cdot f^{(i)}|_{C_g^{(i)}}$ 。根据前面的分析，对于由 $C_g^{(i)}$ 生成的 Vandermonde 矩阵有

因此

由此得到了 $\left(\mathbf{u}^{(i)}(g)\right)^{\intercal} = M_g^{(i)} \cdot f^{(i)}|_{C_g^{(i)}}$ 。

Batching¶

在某些情况下，第一个 prover 的 oracle $f^{(0)}$ 是从一个仿射空间 $F \subset \mathbb{F}^{\mathcal{D}^{(0)}}$ 的函数中采样的，这个仿射空间作为我们的输入，

当使用 FRI 协议来 “batch” 多个不同的 low degree testing 问题实例时，我们就通过随机线性组合将它们全部组合在一起，即上式中的 $f_0^{(0)} + x_1 f_1^{(0)} + \cdots +x_t f_t^{(0)}$ 。在这种 batching 设置中，我们假设 prover 已经承诺了 $f_1^{(0)}, \ldots, f_t^{(0)}$ （注意在这种情况下我们设 $f_0^{(0)} = 0$），并且 batched FRI 的 verifier 从 $\mathbb{F}$ 中均匀随机地采样 $x_1, \ldots, x_t \in \mathbb{F}$， prover 答复 $f^{(0)}$ ，其应该等于 $f_0^{(0)} + \sum_{i=1}^{t} x_i \cdot f_i^{(0)}$ ，现在 FRI 协议就应用于 $f^{(0)}$ 了。相应地，batched FRI 的 QUERY 阶段也被扩展了，因此每次请求 $f^{(0)}(g)$ 的查询时，验证者同时也查询了 $f_0^{(0)}(g), \ldots, f^{(0)}_t(g)$ 并验证 $f^{(0)}(g) = f_0^{(0)}(g) + \sum_{i=1}^{t} {\color{orange}x_i} \cdot f^{(0)}_i(g)$。