- [Anatomy of a STARK, Part 3: FRI](https://aszepieniec.github.io/stark-anatomy/fri) https://eprint.iacr.org/2022/1216.pdf FRI: Ben-Sasson, Bentov, Horesh, and Riabzev [BSBHR18] analysis [BKS18a, SGKS20, BSCI+20] 油炸 Deep-FRI ：一种多项式烹饪技巧 The prover's first message in FRI specifies a function $g: L_0 \rightarrow \mathbb{F}$, where $L_0$ is carefully chosen subset of $\mathbb{F}$. The prover claims that $g$ is a polynomial of degree at most $d$; an equivalent way of saying this is that $g$ is a codeword in the Reed-Solomon code of degree $d$. Rate: $0<\rho<1$ $L_0$ is chosen to have size $\rho^{-1} \cdot d$ In practice, protocols that use FRI choose $\mathbb{F}$ to be significantly bigger than $L_0$, because the message size (and hence prover runtime) is lower-bounded by $\left|L_0\right|$ (hence $\left|L_0\right|$ should be kept as small as possible) yet $|\mathbb{F}|$ should be large to ensure a strong soundness guarantee. The "remainder" of the FRI protocol is an IOP with the following guarantee. relative distance: $\delta \in(0,1-\sqrt{\rho})$, if the verifier accepts, then with overwhelming probability (say, at least $1-2^{-128}$ ), $g$ is within relative distance $\delta$ of some polynomial $p$ of degree at most $d$. That is, the number of points $r \in L_0$ for which $g(r) \neq p(r)$ is at most $\delta \cdot\left|L_0\right|$. The query complexity of the FRI IOP is the dominant factor determining the proof length in succinct argument systems derived thereof, as each IOP query translates into a Merkle-tree authentication path that must be sent in the resulting argument system (see Section 9.2). Meanwhile, the prover runtime in FRI is mainly determined by the rate parameter ρ. This is because the smaller ρ is chosen, the longer the prover’s messages in the IOP, and hence the bigger the prover runtime to generate those messages. However, we will see that smaller choices of ρ potentially permit the FRI verifier to make fewer queries for a given security level, and hence keeps the proof shorter when the IOP is ultimately converted into an argument system. Argument system designers can choose ρ to obtain their preferred tradeoff between prover time and proof size. To commit to a degree $d$ polynomial $p$, the prover would send a function $g$ (claimed to equal $p$ ) by specifying $g$ 's values over $L_0$ (a strict subset of $\mathbb{F}$ ). And the verifier can run FRI to confirm that (with overwhelming probability) $g$ has relative distance at most $\delta$ from some degree $d$ polynomial $p$. Note that if $\delta<\frac{1-d /\left|L_0\right|}{2}=\frac{1-\rho}{2}$, then $p$ is unique, i.e., there can be only one degree $d$ polynomial within relative distance $\delta$ of $g$. This is because any two distinct polynomials of degree at most $d$ can agree on at most $d$ points (Fact 2.1 ). ## 10.2 prover's “special” messages $h_i$ $d_i$ entire R1CS instance $h_i(r)$ $v_i$ PCS: special messages themselves to be “implemented” via standard IOPs. $m_i$ | | | | ---- | ---- | | | | | | | | | |