[BBHR18] FRI 论文 soundness 解析

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

本篇文章主要讲解 Eli Ben-Sasson 等人在 2018 年发表的论文 [BBHR18b] ，重点放在对 FRI 协议的 completeness 和 soundness 证明上。他们在这篇论文中针对 Reed-Solomon (RS) 编码提出了一种新的 IOPP (Interactive Oracle Proof of Proximity, IOPP)，称之为 FRI (Fast RS IOPP, FRI)。随后，在 [BBHR18a] 中使用 FRI 协议构建了一个实用的 ZK 系统，即我们熟知的 STARK。

首要问题¶

对于在有限域 $\mathbb{F}$ 中的求值 (evaluation) 集合 $S$ ，假设 $S$ 中的元素个数为 $N$ ，给定一个码率参数 $\rho \in (0,1]$ ，编码 $\text{RS}[\mathbb{F},S,\rho]$ 表示的是所有函数 $f: S \rightarrow \mathbb{F}$ 的集合，其中 $f$ 是次数 $d < \rho N$ 的多项式的求值 (evaluations)，即存在次数 $d < \rho N$ 的多项式 $\hat{f}$ 使得 $f$ 与 $\hat{f}$ 在 $S$ 上的值是一致的。

论文主要关注的就是 RS proximity problem：假设我们能获得关于函数 $f: S \rightarrow \mathbb{F}$ 的 oracle ，需要 Verifier 用较少的查询复杂度，同时有很高的把握能辨别出 $f$ 属于下面哪一种情况：

1. $f \in \text{RS}[\mathbb{F},S,\rho]$
2. $\Delta(f, \text{RS}[\mathbb{F},S,\rho]) > \delta$

也就是要么 $f$ 是 RS 编码 $\text{RS}[\mathbb{F},S,\rho]$ 中的一个码字，要么距离所有 $\text{RS}[\mathbb{F},S,\rho]$ 中的码字的相对 Hamming 距离都大于接近参数 $\delta$ 。一个自然的想法是 verifier 可以轮讯 $d + 1$ 次，然后判断 $f$ 属于上述哪一种情况，如果属于第一种，则接受，如果属于第二种，则拒绝。此时的轮讯复杂度为 $d + 1 = \rho N$ 。在计算 Testing 方法的复杂度时，没有额外的信息提供给 verifier ，那么说 prover 尝试让 verifier 相信 $f \in \text{RS}[\mathbb{F}, S,\rho]$ 所消耗的计算复杂度为 0 ，交互的轮数为 0 ，以及产生的证明长度为 0 。对比此方法 (Testing, [RS92]) 与FRI 的复杂度，如下表所示([BBHR18b])。

可以看出，FRI 中 prover 的计算复杂度是严格线性的并且 verfier 的计算复杂度是严格对数的，而查询复杂度是对数级别的([BBHR18b])。

FRI 性质¶

上文提到 FRI 是一种 IOPP，下面给出 IOPP 的定义。

Definition 1 [BBHR18b, Definition 1.1] (Interactive Oracle Proof of Proximity (IOPP)). An $\textbf{r}$-round Interactive Oracle Proof of Proximity (IOPP) $\textbf{S} = (\text{P}, \text{V})$ is a ($r + 1$)-round IOP. We say $\textbf{S}$ is an ($\textbf{r}$-round) IOPP for the error correcting code $C= \{f:S \rightarrow \Sigma\}$ with soundness $\textbf{s}^{-}: (0,1] \rightarrow [0,1]$ with respect to distance measure $\Delta$ , if the following conditions hold:

• First message format: the first prover message, denote $f^{(0)}$ , is a purported codeword of $C$ , i.e., $f^{(0)}: S \rightarrow \Sigma$
• Completeness: $\Pr[\left \langle \text{P} \leftrightarrow \text{V} \right \rangle = \text{accept}|\Delta(f^{(0)}, C) = 0] = 1$
• Soundness: For any $\text{P}^*$ , $\Pr[\left \langle \text{P}^* \leftrightarrow \text{V} \right \rangle = \text{reject}|\Delta(f^{(0)}, C) = \delta] \ge \textbf{s}^{-}(\delta)$

意思是 Prover 和 Verifier 会进行 $\textbf{r}$ -轮的交互，需要满足三个条件。

1. 第一个消息 $f^{(0)}$ 是 Prover 初始声称的在 $C$ 中的码字。
2. 完备性：说的是对于诚实的 Prover ，如果 $f^{(0)}$ 在 $C$ 中，那么 Verifier 一定会输出 accept 。
3. Soundness：分析的是作恶的 Prover ，经过交互之后 Verifier 拒绝的概率是多少。定义中的 soundness $\textbf{s}^{-}: (0,1] \rightarrow [0,1]$ 是一个函数，自变量 $\delta \in (0,1]$ ，这也表示在分析 soundness 时，我们考虑的是作恶的 Prover ，也就是初始的 $\Delta(f^{(0)}, C) = \delta > 0$ ，在这种情况下 Prover 和 Verifier 进行交互，来算拒绝的概率是多少，这个概率的下界就是 $\textbf{s}^{-}(\delta) \in [0,1]$ ，由于这里表示的是概率，自然 $\textbf{s}^{-}(\delta)$ 函数值在闭区间 $[0,1]$ 中。

FRI 协议¶

下面摘录下论文 [BBHR18b] 中对 FRI 协议的描述。

定义和记号¶

Interpolant For a function $f : S \rightarrow \mathbb{F}$ , $S \subset \mathbb{F}$ , let $\text{interpolant}^f$ denote the interpolant of $f$ , defined as the unique polynomial $P(X) = \sum_{i=0}^{|S|-1} a_iX^i$ of degree less than $|S|$ whose evaluation on $S$ equals $f|_S$ , i.e., $\forall x \in S, f(x) = P(x)$ . We assume the interpolant $P(X)$ is represented as a formal sum, i.e., by the sequence of monomial coefficients $a_0, \cdots, a_{|S|-1}$ .

Subspace polynomials Given a set $L_0 \subset \mathbb{F}$ , let $\text{Zero}_{L_0} \triangleq \prod_{x \in L_0} (X - x)$ be the unique non-zero monic polynomial of degree $|L_0|$ that vanishes on $L_0$ . When $L_0$ is an additive coset contained in a binary field, the polynomial $\text{Zero}_{L_0}(X)$ is an affine subspace polynomial, a special type of a linearized polynomial. We shall use the following properties of such polynomials, referring the interested reader to [LN97, Chapter 3.4] for proofs and additional background:

1. 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$ .
2. If $L \supset L_0$ are additive cosets, then $\text{Zero}_{L_0}(L) \triangleq \{ \text{Zero}_{L_0}(z) | z \in L \}$ is an additive coset and $\dim(\text{Zero}_{L_0}(L)) = \dim(L) - \dim(L_0)$ .

Subspace specification Henceforth, the letter $L$ always denotes an additive coset in a binary field $\mathbb{F}$ , we assume all mentioned additive cosets are specified by an additive shift $\alpha \in \mathbb{F}$ and a basis $\beta_1, \cdots, \beta_k \in \mathbb{F}^k$ so that $L = \left\{ \alpha + \sum_{i=1}^k b_i\beta_i | b_1, \cdots, b_k \in \mathbb{F}_2 \right\}$ ; we assume $\alpha$ and $\vec{\beta} = (\beta_1, \cdots, \beta_k)$ are agreed upon by prover and verifier.

COMMIT 阶段¶

协议的轮数为 $r \triangleq \left \lfloor \frac{k^{(0)} - \mathcal{R}}{\eta}\right\rfloor$ ，其中 $\mathcal{R} = \log(1/\rho)$ ，$\rho$ 表示码率。在 COMMIT 阶段的第 $i$ 轮，$i \in \{0, \cdots, r - 1\}$ ，Verifier 可以访问一个由 Prover 提交的函数 $f^{(i)}: L^{(i)} \rightarrow \mathbb{F}$ 的 oracle，其中 $\dim(L^{(i)}) = k^{(i)} = k^{(0)} - \eta \cdot i$ ，并且空间 $L^{(i)}$ 是预先固定的，特别地，它们不依赖于 Verifier 的消息。

FRI-COMMIT: Common input:

• Parameters $\mathcal{R}, \eta, i$ , all are positive integers: – rate parameter $\mathcal{R}$ : logarithm of RS code rate ($\rho = 2^{-\mathcal{R}}$) – localization parameter $\eta$ : dimension of $L_0^{(i)}$ (i.e., $|L_0^{(i)}| = 2^{\eta}$); let $r \triangleq \left \lfloor \frac{k^{(0)} - \mathcal{R}}{\eta}\right\rfloor$ denote round complexity – $i \in \{0, \cdots, r\}$: round counter
• A parametrization of $\text{RS}^{(i)} \triangleq \text{RS}[\mathbb{F},L^{(i)},\rho = 2^{-\mathcal{R}}]$ , denote $k^{(i)} = \log_2 |L^{(i)}|$ (notice $k^{(i)} = \dim (L^{(i)})$);
• $L_0^{(i)} \subset L^{(i)}$ , $\dim(L_0^{(i)})=\eta$ ; let $q^{(i)}(X) = \text{Zero}_{L_0^{(i)}}(X)$ and denote $L^{(i+1)} = q^{(i)}(L^{(i)})$

Prover input: $f^{(i)}:L^{(i)} \rightarrow \mathbb{F}$, a purported codeword of $\text{RS}^{(i)}$

Loop: While $i \le r$ :

1. Verifier sends a uniformly random $x^{(i)} \in \mathbb{F}$
2. Prover defines the function $f_{f^{(i)},x^{(i)}}^{(i+1)}$ with domain $L^{(i+1)}$ thus, for each $y \in L^{(i+1)}$ :

• Let $S_y = \{x \in L^{(i)} | q^{(i)}(x) = y\}$ be the coset of $L_0^{(i)}$ mapped by $q^{(i)}$ to $\{y\}$ ;
• $P_y^{(i)}(X) \triangleq \text{interpolant}^{f^{(i)}|_{S_y}}$ ;
• $f_{f^{(i)},x^{(i)}}^{(i+1)}(y) \triangleq P_y^{(i)}(x^{(i)})$ ;

3. If $i = r$ then:

• let $f^{(r)} = f_{f^{(r-1)},x^{(r-1)}}^{(r)}$ for $f^{(r)} = f_{f^{(r-1)},x^{(r-1)}}^{(r)}$ defined in step 2 above;
• let $P^{(r)}(X) = \sum_{j \ge 0} a_j^{(r)}X^j \triangleq \text{interpolant}^{f^{(r)}}(X)$ ;
• let $d = \rho \cdot |L^{(r)}| - 1$ ;
• prover commits to first $d + 1$ coefficients of $P^{(r)}(X)$ , namely, to $\langle a_0^{(r)}, \cdots, a_d^{(r)} \rangle$
• COMMIT phase terminates;

4. Else ($i < r$ ):

• let $f^{(i+1)} = f^{(i+1)}_{f^{(i)}, x^{(i)}}$ for $f^{(i+1)}_{f^{(i)}, x^{(i)}}$ defined in step 2 above;
• prover commits to oracle $f^{(i+1)}$
• both parties repeat the COMMIT protocol with common input
  • parameters $(\mathcal{R}, \eta, i + 1)$
  • a parametrization of $\text{RS}^{(i+1)} \triangleq \text{RS}[\mathbb{F},L^{(i+1)},\rho = 2^{-\mathcal{R}}]$ and $L_0^{(i+1)} \subset L^{(i+1)}$ , $\dim(L_0^{(i+1)})=\eta$ and prover input $f^{(i+1)}$ defined at the beginning of this step;

QUERY 阶段¶

FRI-QUERY: verifier input:

• parameters $\mathcal{R}, \eta$ as defined in the COMMIT phase
• repetition parameter $l$
• sequence of rate-$\rho$ RS-codes $\text{RS}^{(0)}, \cdots, \text{RS}^{(r)}$, where $\text{RS}^{(i)} \triangleq \text{RS}[\mathbb{F},L^{(i)},\rho]$ and $\log_2|L^{(i)}| = k^{(i)} = k^{(0)} - \eta$; (notice $k^{(i)} = \dim(L^{(i)})$);
• sequence of affine spaces $L_0^{(0)}, \cdots, L_0^{(r-1)}$, each $L_0^{(i)}$ is of dimension $\eta$ and contained in $L^{(i)}$ ;
• transcript of verifier messages $x^{(0)}, \cdots, x^{(r-1)} \in \mathbb{F}$
• access to oracles $f^{(0)}, \cdots, f^{(r-1)}$
• access to last oracle $P^{(r)}(X) = \sum_{j \ge 0} a_j^{(r)}X^j$ for $d = \rho \cdot |L^{(r)}| - 1$ ;

Terminal function reconstruction:

• query $a_0^{(r)}, \cdots, a_d^{(r)}$ ;(a total of $d + 1 \le 2^{\eta}$ queries)
• let $P'(X) \triangleq \sum_{j \ge 0} a_j^{(r)}X^j$ ;
• let $f^{(r)}$ be the evaluation of $P'(X)$ on $L^{(r)}$ ; (notice $f^{(r)} \in \text{RS}^{(r)}$ )

Repeat $l$ times: {

1. Sample uniformly random $s^{(0)} \in L^{(0)}$ and for $i = 0, \cdots, r - 1$ let

• $s^{i + 1} = q^{(i)}(s^{(i)})$
• $S^{(i)}$ be the coset of $L_0^{(i)}$ in $L^{(i)}$ that contains $s^{(i)}$

2. For $i = 0, \cdots, r - 1$ ,

• query $f^{(i)}$ on all of $S^{(i)}$; (a total of $2\eta$ queries)
• compute $P^{(i)}(X) \triangleq \text{interpolant}^{f^{(i)}|_{S^{(i)}}}$; (notice $\deg(P^{(i)}) < 2^{\eta}$)

3. round consistency: If for some $i \in \{ 0, \cdots, r - 1\}$ it holds that

$$> > f^{(i+1)}(s^{(i+1)}) \neq P^{(i)}(x^{(i)}) > >$$

(1)

then reject and abort;

}

Return accept

FRI 协议的主要性质¶

下面的定理给出了 FRI 协议的主要性质，包括完备性(Completeness)、Soundness、Prover 复杂度以及 Verifier 复杂度。其实论文中还给出了一个稍微简略的版本，见论文 [BBHR18b] Theorem 1.3，该定理可以通过在下述定理中设置 $\eta = 2$ 与 $l = 1$ 证明得到的，这里就主要阐述这个更加复杂的版本。

Theorem 1 [BBHR18b, Theorem3.3] (Main properties of the FRI protocol). The following properties hold when the FRI protocol is invoked on oracle $f^{(0)}:L^{(0)} \rightarrow \mathbb{F}$ with localization parameter $\eta$ and rate parameter $\mathcal{R}$ (and rate $\rho = 2^{- \mathcal{R}}$) such that $\rho |L^{(0)}| > 16$ :

1. Completeness If $f^{(0)} \in \text{RS}^{(0)} \triangleq \text{RS}[\mathbb{F}, L^{(0)}, \rho = 2^{- \mathcal{R}}]$ and $f^{(1)}, \cdots, f^{(r)}$ are computed by the prover specified in the COMMIT phase, then the FRI verifier outputs accept with probability 1.

2. Soundness Suppose $\delta^{(0)} \triangleq \Delta^{(0)}(f^{0}, \text{RS}^{(0)}) > 0$ . Then with probability at least

   $$1 - \frac{3|L^{(0)}|}{\mathbb{F}}$$

   (2)

   over the randomness of the verifier during the COMMIT phase, and for any (adaptively chosen) prover oracles $f^{(1)}, \cdots, f^{(r)}$ the QUERY protocol with repetition parameter $l$ outputs accept with probability at most

   $$\left (1 - \min \left \{\delta^{(0)}, \frac{1-3\rho-2^{\eta}/\sqrt{|L^{(0)}|}}{4} \right \}\right )^{l}$$

   (3)

   Consequently, the soundness of FRI is at least

   $$\textbf{s}^{-}(\delta^{(0)}) \triangleq 1 - \left ( \frac{3|L^{(0)}|}{|\mathbb{F}|} + \left (1 - \min \left \{\delta^{(0)}, \frac{1-3\rho-2^{\eta}/\sqrt{|L^{(0)}|}}{4} \right \}\right )^{l} \right).$$

   (4)

3. Prover complexity The $i^{th}$ step of commit phase can be computed by a parallel random access machine (PRAM) with concurrent read and exclusive write (CREW) in $2\eta + 3$ cycles — each cycle involves a single arithmetic operation in $\mathbb{F}$ — using $2|L^{(i)}| + \eta$ processors and a total of $4|L^{(i)}|$ arithmetic operations over $\mathbb{F}$. Consequently, the total prover complexity is at most $6|L^{(0)}|$ arithmetic operations, which can be carried out in at most $4 |L^{(0)}|$ cycles on a PRAM-CREW with $2n + 3$ processors.

4. Verifier complexity Verifier communication during the COMMIT phase equals $\textbf{r}$ field elements; query complexity (during QUERY phase) equals $l 2^{\eta} \textbf{r} = l 2^{\eta} \left ( 1 + \left \lfloor \frac{\log |L^{(0)}| - \mathcal{R}}{\eta} \right \rfloor \right )$. On a PRAM with exclusive read and exclusive write (EREW) with $l \textbf{r}\cdot2 \eta$ processors, the verifier’s decision is obtained after $2\eta + 3 + \log l$ cycles and a total of $l\cdot \textbf{r} \cdot (6 \cdot 2\eta + 6 \eta + 6)$ arithmetic operations in $\mathbb{F}$.

在第 2 项，Soundness 结论中，先给了一个参数 $\delta^{(0)} \triangleq \Delta^{(0)}(f^{0}, \text{RS}^{(0)}) > 0$ ，这里的 $\Delta^{(0)}(f^{0}, \text{RS}^{(0)})$ 其实并不是常见的相对 Hamming 距离，下面给出此测度的定义，同时说明它与相对 Hamming 距离之间的关系。

Block-wise 距离测度¶

Definition 2 [BBHR18b, Definition3.2] (Block-wise distance measure). Let $\mathcal{S} = \{S_1, \cdots, S_m\}$ be a partition of a set $S$ and $\Sigma$ be an alphabet. The relative $\mathcal{S}$-Hamming distance measure on $\Sigma^{S}$ is defined for $f, g \in \Sigma^{S}$ as the relative Hamming distance over $\Sigma^{S_1} \times \cdots \times \Sigma^{S_m}$ ,

Thus, for $\mathcal{F} \subset \Sigma^{S}$ let $\Delta^{\mathcal{S}}(g,\mathcal{F}) = \min \{ \Delta^{\mathcal{S}}(g,f) | f \in \mathcal{F}\}$.

为了更好的理解这个定义，在 FRI 协议中，考虑在 $\mathbb{F}^{L^{(i)}}$ 上的 block-wise 距离，即用 FRI 协议中在第 $i$ 步的 $L^{(i)}$ 来替代上述定义中的集合 $S$ ，用 $\mathbb{F}$ 替换上述定义中的字母表 $\Sigma$。在第 $i$ 步，我们能够确定集合 $L_0^{(i)}$ 。$L_0^{(i)}$ 其实可以设为映射 $q^{(i)}$ 的核，也就是在 $L^{(i)}$ 集合中那些被 $q^{i}$ 映射为 $L^{(i+1)}$ 中单位元 $e$ 的元素的集合，用数学符号表示出来即

那么通过 $L_0^{(i)}$ 的陪集可以对集合 $L^{(i)}$ 进行划分，假设划分成 $m$ 个集合，则对 $L^{(i)}$ 的划分可记为 $\mathcal{S}^{(i)} = \{L_0^{(i)}, \cdots, L_{m-1}^{(i)}\}$ 。那么简记

对于两个函数 $f,g : L^{(i)} \rightarrow \mathbb{F}$ ，定义域均为 $L^{(i)}$ ，值域均为 $\mathbb{F}$ ，现在这个 Block-wise 距离说的是这两个函数在 $\mathcal{S}^{(i)}$ 中这些陪集中不完全一致的陪集个数的比值。例如在 $\mathcal{S}^{(i)} = \{L_0^{(i)}, \cdots, L_{m-1}^{(i)}\}$ 中 (假设 $m \ge 2$)，只有在 $L_0^{(i)}$ 与 $L_1^{(i)}$ 这两个集合上函数 $f$ 与 $g$ 对应的函数值不完全相同，即 $f|_{L_0^{(i)}} \neq g|_{L_0^{(i)}}$ 且 $f|_{L_1^{(i)}} \neq g|_{L_1^{(i)}}$ ，在其余的陪集上函数 $f$ 与 $g$ 完全一致，那么可以计算出 $\Delta^{(i)}(f,g) = \frac{2}{m}$ 。

上面的 $\Delta^{(i)}(f, g)$ 说的是 $\mathbb{F}^{L^{(i)}}$ 中两个元素的测度，下面解释下定义中关于集合中一个元素 $f^{(i)} \in \mathbb{F}^{L^{(i)}}$ 与一个子集 $\text{RS}^{(i)} \subset \mathbb{F}^{L^{(i)}}$ ($\text{RS}^{(i)} = RS[\mathbb{F}, L^{(i)}, \rho]$ 自然是 $\mathbb{F}^{L^{(i)}}$ 的子集)对应的 block-wise 距离测度，表示成

其含义是取遍集合 $\text{RS}^{(i)}$ 中所有的码字 $g^{(i)}$ ，算出这些 $\Delta^{\mathcal{S}^{(i)}}(f^{(i)},g^{(i)})$ ，其中最小的那个值就是 $\Delta^{\mathcal{S}^{(i)}}(f^{(i)},\text{RS}^{(i)})$ 。 关于该 Block-wise 距离测度，一个重要的不等式是

该等式会在 FRI 的 Soundness 证明中反复用到，比较重要，这里给出其证明。

证明：先证明不等式的左半边，即 $1 - \rho \ge \Delta^{\mathcal{(i)}}(f^{(i)},\text{RS}^{(i)})$ 。总是存在这样一个多项式 $g^{(i)} \in \text{RS}^{(i)}$ ，其次数 $deg(g^{(i)}) < \rho |L^{(i)}|$ ，同时 $\Delta^{\mathcal{(i)}}(f^{(i)},g^{(i)}) = 1 - \rho$ 。下面说明 $g^{(i)}$ 的存在性。我们进行如下的构造： 在划分集合$\mathcal{S}^{(i)} = \{L_0^{(i)}, \cdots, L_{m-1}^{(i)}\}$ 中，按顺序可得到集合序列 $\{ L_0^{(i)}, \cdots, L_{m-1}^{(i)}\} = \{x_0, x_1, \cdots, x_{|L^{(i)}| - 1}\}$ ，连续选择前 $\rho |L^{(i)}|$ 个点 $\{x_0,x_1, \cdots, x_{\rho |L^{(i)}| - 1}\}$，得到这些点对应的 $f^{(i)}$ 的值 $\{f^{(i)}(x_0),f^{(i)}(x_1),\cdots, f^{(i)}(x_{\rho |L^{(i)}| - 1})\}$ ，拿到这些点值对可以进行 Lagrange 插值，得到一个次数 $< \rho |L^{(i)}|$ 的多项式 $g^{(i)}$ ，同时易得这样构造的 $g^{(i)} \in \text{RS}^{(i)} = RS[\mathbb{F}, L^{(i)}, \rho]$ 。同时根据前面的构造发现在集合 $\{L_0^{(i)}, \cdots, L_{\rho m - 1}^{(i)}\} = \{x_0, x_1, \cdots, x_{\rho |L^{(i)}| - 1} \}$ 上函数 $f^{(i)}$ 与 $g^{(i)}$ 的函数值是完全相等的 (这里 $\rho |L^{(i)}|$ 个点刚好完全占满在 $\rho m$ 个集合中，不会出现最后一些点只占最后一个集合的一部分的情况，这是由于选取 $\rho$ 、$|L^{(i)}|$ 都是 2 的幂次形式，能够整除)，那么可计算出

因此 $\Delta^{\mathcal{(i)}}(f^{(i)},\text{RS}^{(i)})$ 计算的 $\text{RS}^{(i)}$ 中元素与 $f^{(i)}$ 在测度 $\Delta^{(i)}$ 下的最小值，那肯定不会超过找到的 $g^{(i)} \in \text{RS}^{(i)}$ 的距离，也就证明了不等式的左半边 $1 - \rho \ge \Delta^{\mathcal{(i)}}(f^{(i)},\text{RS}^{(i)})$ 。 接下来证明不等式的右半边 $\Delta^{\mathcal{(i)}}(f^{(i)},\text{RS}^{(i)}) \ge \Delta_H(f^{(i)},\text{RS}^{(i)})$ 。 假设 $\Delta^{(i)}(f^{(i)}, g^{(i)} \in \text{RS}^{(i)}) = \delta$，不失一般性，假设 $f^{(i)}$ 与 $g^{(i)}$ 在陪集 $\{L_0^{(i)}, \cdots, L_{\delta m - 1}^{(i)}\} = \{x_0, \cdots, x_{\delta |L^{(i)}| - 1}\}$ 上不完全一致，在剩余的集合 $\{L_0^{(i)}, \cdots, L_{m-1}^{(i)}\} \backslash \{L_0^{(i)}, \cdots, L_{\delta m - 1}^{(i)}\}$ 上是完全一致的。那么考虑在 $L^{(i)}$ 上的所有点时，$g^{(i)}$ 最多在 $\{L_0^{(i)}, \cdots, L_{\delta m - 1}^{(i)}\} = \{x_0, \cdots, x_{\delta |L^{(i)}| - 1}\}$ 这 $\delta |L^{(i)}|$ 点上都与 $f^{(i)}$ 不一致，因此也就说明了 $\Delta_H(f^{(i)},g^{(i)}) \le \delta$ ，进而如果设 $\Delta^{\mathcal{(i)}}(f^{(i)},\text{RS}^{(i)}) = \delta^*$ 可得出 $\Delta_H(f^{(i)},\text{RS}^{(i)}) \le \delta^* = \Delta^{\mathcal{(i)}}(f^{(i)},\text{RS}^{(i)})$ 。 \Box

定理 1 完备性证明¶

下面说明定理 1 中完备性证明的思路，复述下完备性：

Completeness If $f^{(0)} \in \text{RS}^{(0)} \triangleq \text{RS}[\mathbb{F}, L^{(0)}, \rho = 2^{- \mathcal{R}}]$ and $f^{(1)}, \cdots, f^{(r)}$ are computed by the prover specified in the COMMIT phase, then the FRI verifier outputs accept with probability 1.

完备性说的是对于诚实的 Prover ，初始的函数 $f^{(0)}$ 是在 $\text{RS}^{(0)}$ 编码空间中的，那么通过 FRI 的 COMMIT 阶段会产生一些列的函数 $f^{(1)}, \cdots, f^{(r)}$ ，那么 Verifier 在 QUERY 阶段结束后肯定会输出 accept 。

首先给出了一个递归的引理，再用该引理来证明完备性，引理表述的是在第 $i$ 步如果 $f^{(i)} \in \text{RS}^{(i)}$ ，那么在 COMMIT 阶段，Verifier 会从 $\mathbb{F}$ 中随机选取 $x^{(i)}$ 发给 Prover ，Prover 用该随机数来构造下一步的函数 $f^{(i+1)}_{f^{(i)}, x^{(i)}}$ ，那么对于 $\mathbb{F}$ 中任意一个 $x^{(i)}$ ，都有构造出来的 $f^{(i+1)}_{f^{(i)}, x^{(i)}}$ 都在 $\text{RS}^{(i+1)}$ 空间中。递归的引理正式表述如下，关于该引理的证明留在后面进行说明。

Lemma 1 [BBHR18b, Lemma 4.1] (Inductive argument). If $f^{(i)} \in \text{RS}^{(i)}$ then for all $x^{(i)} \in \mathbb{F}$ it holds that $f^{(i+1)}_{f^{(i)}, x^{(i)}} \in \text{RS}^{(i+1)}$ .

完备性证明的思路是，在 QUERY 阶段，Verifier 主要是在检查第 3 步的 round consistency 是否成立，一旦某一步的 $i \in \{0, \cdots, r - 1\}$ 不成立就会直接输出 reject，直到对所有的 $i$ 的检测都通过，最终才会输出 accept 。那么对于 $i < r - 1$ ，根据 COMMIT 阶段 $f^{(i + 1)}$ 的构造过程，round consistency 都会通过。对于 $i = r - 1$，根据根据完备性的初始条件 $f^{(0)} \in \text{RS}^{(0)}$ ，该定理递归的说明了 $f^{(r)} \in RS^{(r)}$ ，最后根据该结论说明在 QUERY 阶段也会检测通过 round consistency，最终 Verifier 也就一定会输出 accept 了。具体的完备性证明如下。

定理 1 第一项完备性证明： 对于诚实的 Prover，对于任意的一个函数 $f^{(i)}$ ，在 COMMIT 阶段的第 2 步中，对于任意的 $i < r - 1$ ，构造出

根据该构造，那么一定能在 QUERY 阶段的第 3 步一定会通过 round consistency ，即

成立。

下面只需证明对于 $i = r - 1$ 时，round consistency 也能通过。根据完备性的假设知 $f^{(0)} \in \text{RS}^{(0)}$ ，由 Lemma 1 递归可得 $f^{(r)} \in RS^{(r)}$ ，那么一定存在一个次数 $<\rho |L^{(r)}|$ 的多项式 $P^{(r)}(X)$ 使得 $f^{(r)}(X)$ 与 $P^{(r)}(X)$ 在 $L^{(r)}$ 上是完全一致的。因此 Prover 会在 COMMIT 阶段的第 3 步发送 $P^{(r)}(X)$ 的 $d + 1 = \rho |L^{(r)}|$ 个系数 $\langle a_0^{(r)}, \cdots, a_d^{(r)} \rangle$ ，Verifier 在 QUERY 阶段的 “Terminal function reconstruction” 阶段会根据发送过来的 $d + 1$ 个系数构造出 $P'(X) \triangleq \sum_{j \le d} a_j^{(r)}X^j$ ，再根据 $P'(X)$ 得到函数 $f'^{(r)}$ ，函数 $f'^{(r)}$ 是 $P'(X)$ 在 $L^{(r)}$ 上的估计 (evaluation) 。那么可以推断出 $f'^{(r)}|_{L^{(r)}} = P'(X) = P^{(r)}(X) = f^{(r)}|_{L^{(r)}}$ 。自然会通过第 $i = r - 1$ 轮的 round consistency ，即

从而得证 Verifier 最后一定会输出 accept 。\Box

命题 1 的引入¶

在证明引理 1 前先给出一个重要的命题，再用该命题来证明引理 1 。在下述命题中，用小写字母 $x, y$ 来表示域中的元素，用大写字母 $X,Y$ 来表示自变量。

Claim 1 [BBHR18b, Claim 4.2]. For every $f^{(i)}: L^{(i)} \rightarrow \mathbb{F}$ there exists $Q^{(i)}(X,Y) \in \mathbb{F}[X,Y]$ satisfying

1. $f^{(i)}(x) = Q^{(i)}(x,q^{(i)}(x))$
   for all $x \in L^{(i)}$
2. $\deg_X(Q^{(i)}) < |L_0^{(i)}|$
3. If $f^{(i)} \in RS[\mathbb{F},L^{(i)},\rho]$ then $\deg_Y(Q^{(i)}) < \rho |L^{(i+1)}|$

该命题对于理解 FRI 协议是比较重要的。Vitalik 在其博客文章 STARKs, Part II: Thank Goodness It’s FRI-day 的 A First Look at Sublinearity 小节中给出了一个具体的例子，其协议过程已初具 FRI 协议的雏形，我们在这里用命题 1 的视角来重新看看这个例子。 假设有限域 $L$ 的大小为 $N = 10^9$ ， 设多项式 $f(X): L \rightarrow \mathbb{F}$ ，且其次数 $< 10^6$ ，那么有 $f \in RS[\mathbb{F}, L, \rho = 10^{-3}]$ 。根据命题 1 可得，一定存在一个二元多项式 $g(X,Y) \in \mathbb{F}[X,Y]$ 满足：

1. 对于 $\forall x \in L$ 都有 $g(x,q(x)) = f(x)$ ，其中 $q(x) = x^{1000}$
2. $\deg_X(g) < |L_0| = 10^3$
3. 由于 $f \in RS[\mathbb{F}, L, \rho = 10^{-3}]$ ，则 $\deg_Y(g) < \rho |L^{(1)}| = 10^{-3} \times 10^6 = 10^3$ 现在 Prover 想向 Verifier 证明 $f(x)$ 的次数确实是小于 10⁶ 的。在文章中用了直观的几何图形来说明证明的过程。

在图中，正方形的横向表示的是自变量 $X$ ，取值范围就是 $L$ ，总共有 10⁹ 个，而纵向表示的是自变量 $Y$ ，其取值范围是 $\{x^{1000} | x \in L\}$ 。正方形中的一个点 $(x,y)$ 对应的值表示的就是计算出的 $g(x,y)$ 的值。对于在正方形的对角线上的点 $(x, y)$，满足 $x = y$ ，那么 $g(x,y) = g(x, x^{1000}) = f(x)$ 。

证明的过程如下：

1. Prover 承诺上述正方形中关于 $g(X,Y)$ 的所有点的估计，例如使用 Merkle 树来进行承诺。
2. Verifier 随机选取大约几十行和列，对于选择的每一行或列，Verifier 会要求例如 1010 个点的样本，确保在每种情况下所需的点之一位于对角线上。比如 Verifier 选取第 5 列，那么此时 $x = x_4$ ，此时需要选取 1010 个样本点，那么这些点的横坐标已经确定了，只需随机纵坐标就行，在纵坐标中选取 $y = x_4^{1000}$ 就确保了该点 $(x_4,x_4^{1000})$ 在对角线上了。
3. Prover 回复 Verifier 要求的点对应的值 $g(x,y)$ ，并带上对应的 Merkle 分支，证明它们是 Prover 原来承诺的数据的一部分。
4. Verifier 检查 Merkle 分支是否匹配，同时对于每一行或每一列，Verifier 验证 Prover 提供的这些点是否真的对应一个次数 $<1000$ 的多项式。Verifier 可以通过对这些点进行插值来验证这一点。

原文提到：

This gives the verifier a statistical proof that (i) most rows are populated mostly by points on degree $<1000$ polynomials, (ii) most columns are populated mostly by points on degree $<1000$ polynomials, and (iii) the diagonal line is mostly on these polynomials. This thus convinces the verifier that most points on the diagonal actually do correspond to a degree $<1,000,000$ polynomial.

这几点与结论可以联系命题 1 给出的那三项：

1. 对于大多数行，对应的是次数 $<1000$ 的多项式，也就是说明 $\deg_X(g) < 1000$ 。
2. 对于大多数列，对应的是次数 $<1000$ 的多项式，也就是说明 $\deg_Y(g) < 1000$ 。
3. 对角线主要由这些多项式上的点组成，也就是说明这些点的值满足 $g(x,x^{1000})$ 。