[FRI] 如何理解论文 [BBHR18] Fast Reed-Solomon Interactive Oracle Proofs of Proximity 中关于映射的描述？

[wenjin1997]

在论文中 [BBHR18]FRI 有这样一段话，如何去理解这个映射呢？如何理解这句话呢？

The map $x \mapsto \text{Zero}_{L_0}(X)$ maps each additive coset $S$ of $L_0$ to a single field element, which will be denoted by $y_S$

其中 $\text{Zero}_{L_0}$ 为

$$ \prod_{x \in L_0}(X - x), $$

并且 $L_0 \subset L$ ， $L = \{\alpha + \sum_{i = 1}^{k} b_i \beta_i |b_1, \cdots, b_k \in \mathbb{F}_2 \}$。

[wenjin1997]

翻译过来是，对于 $L_0$ 的每一个加法陪集 $S$ ，映射 $x \mapsto \text{Zero}_{L_0}(X)$ 都会把陪集 $S$ 中的每一个元素映射成域中的一个元素，记为 $y_S$ 。

我们可以举一个具体的例子来进行理解，论文中有 $L =\{\alpha + \sum_{i = 1}^{k} b_i \beta_i |b_1, \cdots, b_k \in \mathbb{F}_2 \}$ ，取 $\alpha = 0$ ， $k = 3$ ，那么

$$ \begin{aligned} L & = \{b_1 \beta_1 + b_2 \beta_2 + b_3 \beta_3 | b_1, b_2, b_3 \in \mathbb{F}_2 \} \\ & = \{0, \beta_1, \beta_2, \beta_3, \beta_1 + \beta_2, \beta_1 + \beta_3, \beta_2 + \beta_3, \beta_1 + \beta_2 + \beta_3\} \end{aligned} $$

由于 $L_0 \subset L$ ，这里取 $L_0 = \{0, \beta_1\}$ ， 那么映射为

$$ q^{(0)}(X) = \text{Zero}_{L_0}(X) $$

$$ = \prod_{x\in L_0}(X - x) = X(X-\beta_1) $$

一个个算下 $L$ 中的元素在映射 $q^{(0)}$ 下的值：

$$ \begin{aligned} & q^{(0)}(0) = 0 \\ & q^{(0)}(\beta_1) = 0 \\ & q^{(0)}(\beta_2) = \beta_2(\beta_2 - \beta_1) = \beta_2^2 - \beta_1 \beta_2 = \beta_2 (\beta_1 + \beta_2) \\ & q^{(0)}(\beta_3) = \beta_3(\beta_3 - \beta_1) = \beta_3^2 + \beta_1 \beta_3 = \beta_3(\beta_1 + \beta_3) \\ & q^{(0)}(\beta_1 + \beta_2) = (\beta_1 + \beta_2)(\beta_1 + \beta_2 - \beta_1) = \beta_2 (\beta_1 + \beta_2) \\ & q^{(0)}(\beta_1 + \beta_3) = (\beta_1 + \beta_3)(\beta_1 + \beta_3 - \beta_1) = \beta_3(\beta_1 + \beta_3) \\ & q^{(0)}(\beta_2 + \beta_3) = (\beta_2 + \beta_3)(\beta_2 + \beta_3 - \beta_1) = (\beta_2 + \beta_3)(\beta_1 + \beta_2 + \beta_3) \\ & q^{(0)}(\beta_1 + \beta_2 + \beta_3) = (\beta_1 + \beta_2 + \beta_3)(\beta_1 + \beta_2 + \beta_3 - \beta_1) = (\beta_2 + \beta_3)(\beta_1 + \beta_2 + \beta_3) \end{aligned} $$

Remark 1: 由于 $b_i \in \mathbb{F}_2 = \{0 ,1\}$ ，因此有 $-1 = -1 + 2 = 1$ ，上述计算中的减号也等于加号。

可以看到映射 $q^{(0)}$ 会将 $L$ 中的两个元素映射成同一个值，我们把映射到同一个值的两个元素放在一个集合里，这样我们就可以得到关于 $L$ 的一个划分，令

$$ \begin{aligned} & L_0^{(0)} = \{0, \beta_1\},\\ & L_1^{(0)} = \{\beta_2, \beta_1 + \beta_2\} = \beta_2 + L_0^{(0)} = \beta_1 + \beta_2 + L_0^{(0)}, \\ & L_2^{(0)} = \{\beta_3, \beta_1 + \beta_3\} = \beta_3 + L_0^{(0)} = \beta_1 + \beta_3 + L_0^{(0)}, \\ & L_3^{(0)} = \{\beta_2 + \beta_3, \beta_1 + \beta_2 + \beta_3\} = \beta_2 + \beta_3 + L_0^{(0)} = \beta_1 + \beta_2 + \beta_3 + L_0^{(0)}. \end{aligned} $$

以上面的 $L_1^{(0)}$ 举例，它就是 $L_0^{(0)}$ 的一个加法陪集，对于陪集有一个性质那就是其中的每一个元素都可以当作代表元，什么意思呢？就是我将 $L_1^{(0)}$ 中的第一个元素 $\beta_2$ 拿出来，分别加上 $L_0^{(0)}$ 中的两个元素，可以得到 $L_1^{(0)}$ ，换 $L_1^{(0)}$ 中的第二个元素 $\beta_1 + \beta_2$，同样可以得到 $\beta_1 + \beta_2 + L_1^{(0)} = \{\beta_1 + \beta_2, 2\beta_1 + \beta_2\} = \{\beta_1 + \beta_2, 0 + \beta_2\} = L_1^{(0)}$。换句话说 $L_1^{(0)}$ 中的每一个元素都是平等的，都可以当代表元，加上 $L_0^{(0)}$ 后都能得到自身的所有元素。类似地， $L_2^{(0)}$ ， $L_3^{(0)}$ 也都是 $L_0^{(0)}$ 的加法陪集。

这样我们就可以将 $L$ 划分为关于 $L_0^{(0)}$ 的陪集之并了，

$$ \begin{aligned} L & = L_0^{(0)} \cup L_1^{(0)} \cup L_2^{(0)} \cup L_3^{(0)} \\ & = L_0^{(0)} \cup \beta_2 + L_0^{(0)} \cup \beta_3 + L_0^{(0)} \cup \beta_2 + \beta_3 + L_0^{(0)}. \end{aligned} $$

所以映射 $q^{(0)} = \text{Zero}_{L_0}(X)$ 就起到了这样的一个作用，将 $L$ 中关于 $L_0 = L_0^{(0)}$ 的陪集中的所有元素都映射到了同一个值上。

Remark 2: 论文中给出的 $L = \{\alpha + \sum_{i = 1}^{k} b_i \beta_i |b_1, \cdots, b_k \in \mathbb{F}_2 \}$ ，这里 $b_i \in \mathbb{F}_2$ 。

$L$ 总是表示一个在 binary field $\mathbb{F}$ (binary field 是形如 $\mathbb{F}_{2^m}$ 的域，其中 $m$ 是一个正整数) 中的加法陪集，因此在 [BBHR18] 中的 COMMIT 协议中 $L^{(i)}$ 的维度公式是以 2 为底的，即 $\dim(L^{(i)}) = \log_2 |L^{(i)}|$ 。其实 FRI 协议并不局限于这里的 binary field 。