ZK-STARK 如何工作及其安全性

关于其证明系统，ZK-STARK证明系统已经有详细的描述，这里不再赘述。本文主要记录下STARK系统的基础和安全性的简单讨论。

1. 安全性和 bit 安全性

下面这段描述引用自 >When we say that a cryptographic system has a security level of λ bits, we mean, somewhat informally, that the best known attack on it requires running time ≥ $2^{\lambda }$^[1]

从中我们就可以明白，密码学中的所谓的“security strengh(security level)”就是在已知最好的破解方法下，需要多少时间能够破解。只不过这里的“时间”，是用算法需要进行尝试的次数来估计的。于是，“bit security level”就是这个次数的二进制表示而已。

安全性有以下几点需要注意：

• $\lambda$ bits并不代表就有 $2^{\lambda }$ 的计算机指令。具体的指令数目是由具体的硬件和指令集有关。
• 特别在公钥密码中，key bits的长度不一定就代表了bit security level。具体是与攻击方法有关的。比如： 2048-bit RSA就不具备2048 bits security level， 这是因为它的攻击方法是大质因数分解问题的复杂度。

2. FRI 的基本原理

概括来说，本质上，STARK最终是利用FRI证明了某一个多项式的次数是小于一个固定界限的，也就是所谓低度测试(Low-Degree-Testing)，而这个多项式表示了待证问题的计算过程。所以讨论STARK协议的安全性，可以等同于讨论FRI的安全性。

2.1 RS Proximity Testing/Verification

之所以简单介绍RS code， 是因为FRI论文就是为了解决RS proximity testing问题而提出的。同时，RS code是一组编码方法，它本质是一种 纠错码，最开始是为了解决通信中由于通信信道不可信导致的接收方来检测和更正发送方发来的原始数据的。它的基本思想很简单，就是通过发送方按照算法发送 冗余 来达成目的。

2.1.1 Original RS Code(RS60)

在FRI文献中所找到的RS60，就是指 I. S. REED 和 G. SOLOMON在1960年发表的《POLYNOMIAL CODES OVER CERTAIN FINITE FIELDS》^[2]论文所提出的纠错码编码方法，因而得名RS code。这种编码方法，其实很容易理解，它有如下几个要点。

• 它的目的是将一个 $m$ 长度的消息(message)编码成一个固定长度 $n$ 的消息(codeword)
• message与codeword的具体表示都是定义在一个域上的，通常是 $GF(2^k)$。这里可以把它简单理解为就是字符串的二进制表示，一般 $n=2^k$。
• 编码方法很简单，它首先构造了一个 $(m-1)$ 次多项式，这个多项式的系数就是待编码的消息(message)；而编码的结果(codeword)就是这个多项式在某个乘法子群各点处的值。

正式的过程是：

1. message: m-tuple $(a_0,a_1,...,a_{m-1})$
2. 构造一个 $(m-1)$ 次多项式 $P(X)$, 使得 $P(X)=a_0+a_{1}x+a_2{x}^2+...+a_{m-1}{x}^{m-1}$
3. 在本原根处求值，形成 codeword $$\begin{array}{rl}& P(0)=a_0\\ & P(\beta )=a_0+a_1\beta +a_2{\beta }^2+...+a_{m-1}{\beta }^{m-1}\\ & P({\beta }^2)=a_0+a_1{\beta }^2+a_2{\beta }^4+...+a_{m-1}{\beta }^{2(m-1)}\\ & ......\\ & P({\beta }^{2^n-2})=a_0+a_1{\beta }^{2^n-2}+a_2{\beta }^{2(2^n-2)}+...+a_{m-1}{\beta }^{(m-1)(2^n-2)}\\ & P(1)=a_0+a_1+a_2+...+a_{m-1}\end{array}$$

所以最终的 codeword 就是 $(P(0),P(\beta ),P({\beta }^2),...,P({\beta }^{2^n-2},P(1)))$。

接收者在接到codeword之后如果发生错误的位置在一定范围内，接收者是可以从接收到的codeword“恢复”出正确的数据的。这是因为上面任意 $m$ 个方程都是线性无关的，所以只要“正确”的值还占主要地位，就可以恢复出正确数据。

目前RS Code已经是一族编码方法，后面的一个改进就是将原始的消息也放到codeword中。由于与主题关系不大，就不介绍了。

2.1.2 RS code相关概念

以下内容撷取、综述于Block code Wiki

1. message length： 这个容易理解，记为 $m$。
2. block length: codeword的长度，记为 $n$。
3. Rate $R$: $R=m/n$
4. distance： 就是两个不同的codeword之间各个位置上不同的code的个数。并定义下面的最小距离 $d$，以及相对距离 $\delta$ $$\begin{array}{rl}& d:=\underset{\genfrac{}{}{0ex}{}{m_1,m_2\in {\Sigma }^k}{m_1\ne m_2}}{\min }\Delta [C(m_1),C(m_2)]\\ & \delta =d/n\end{array}$$ 下面讨论RS Code的 $d$ 的值。任何两个不相等的 $(m-1)$ 次多项式至少有 $(m-1)$ 个交点， 所以任意两个codeword之间的距离至多是 $n-(m-1)$ 。同时存在两个codeword是有 $(m-1)$ 个交点，所以 $d=n-(m-1)=n-m+1$。

进一步有， $$\begin{array}{rl}& \delta =d/n\\ & =(n-m+1)/n\\ & =1-m/n+1/n\\ & =1-R+o(1)\end{array}$$

2.1.3 RS Code相关定义与符号

单列本小节是因为FRI论文中大量采用，为方便以及精确起见，介绍于此。以下将对上述RS Code做一个形式化定义，该形式化引用自Relation between degree and Hamming distance, 该引用虽然是一个论坛问答，但是综合FRI论文中的定义，认为其定义是合理的，故直接采用。

Let F be a finite field. Let $S\subset F$ be some non-empty set. Define the relative Hamming distance between two function $f,g:S\to F$ by $${\Delta }_S(f,g):=\frac{1}{|S|}|\{s\in S:f(s)\ne g(s)\}|$$. Fix some $0<\rho <1$. Let $RS[F,S,\rho ]$ be the set of functions on $S$ who are evaluations of polynomials of degree $<\rho |S|$: $$RS[F,S,\rho ]:=\{f:S\to F:\exists p\in F[x^{<\rho |S|}],f=p{|}_S\}$$. For a function $f:S\to F$, let $$\delta (f):={\Delta }_S(f,RS[F,S,\rho ])=min\{{\Delta }_S(f,g):g\in RS[F,S,\rho ]\}$$

该定义直接定义了两个多项式（函数）的Hamming distance, 以及最重要的 $RS[F,S,\rho ]$ 与 $\delta (f)$。简单来说，$RS[F,S,\rho ]$ 是一个多项式的集合，并且多项式的次数都是 $<\rho |S|$ 的，而 $\delta (f)$ 则是 $f$ 与所有次数小于 $\rho |S|$ 的相对Hamming distance的最小值。

这里有一个需要注意的，不要受到前面介绍RS60的影响，这里的 $S$ 并不是原始消息(message)，而是对求多项式进行求值的定义域（即 $0,\beta ,{\beta }^2,...,$）。

2.1.4 RS proximity problems 和 RS proximity testing/verification

The RS proximity problem assumes a verifier has oracle access to $f:S\to F$, and asks that verifier to distinguish, with “large” confidence and “small” query complexity, between the case that $f$ is a codeword of $RS[F,S,\rho ]$ and the case that $f$ is $\delta$-far in relative Hamming distance from all codewords^[3]

所谓 proximity 问题就是一个概率问题，就是采取可接受的步骤，让verifier能区分出 $\delta (f)$ 是到达了预设的界限 $\delta$。

为了解决 RS proximity problems，有两大方法，一个是testing，一个是verification。二者的区别是，testing方法中prover提交证明后，不需要再提供额外的信息(意即verifier也不会再有额外的query)；而verification需要verifier多次query。而verification又分为，PCP model 和 IOPP model，区别是后者有多轮证明和多轮query。

最后，FRI 就是一种基于 IOPP model 解决RS proximity problems的一个方法。

2.2 FRI 与 DEEP FRI

2.2.1 FRI 折叠

FRI的核心是对欲承诺的多项式进行“折叠”，通过“折叠”将一个次数很高的多项式，逐步转化为次数较低，verifier可以接受的计算复杂度来验证的多项式。最后将结果多项式的系数发给verifier，verifier自己验证其次数。进而可以证明原始多项式的次数界限。

关于“折叠”的过程，ZK-STARK证明系统已经有较详细的阐述，这里只是换一种表达方式（论文方式），抛开复杂的数学符号和形式化的协议阐述，这里直接引用论文^[3]中的例子，并直接运用上文提到的一点点数学表示，就可以很清楚明白。

\begin{aligned} & prover \ claims:\ f^{(0)} : L^{(0)} → F \ is\ a\ member\ of\ RS[F,L (0) ,ρ] \ & i.e\ f^{(0)}\ is\ the\ evaluation\ of\ an
unknown\ polynomial\ P^{(0)} (X) ∈ F[X],\ deg(P) < ρ2^{n}\ \end{aligned}

很显然这是一个次数极高的多项式，于是做了如下变形：

$$\begin{array}{rl}& \forall x\in L^{(0)}{f}^{(0)}(x)=P^{(0)}(x)=P_0^{(1)}(x^2)+x\cdot P_1^{(1)}(x^2)\\ & letting{Q}^{(1)}(X,Y)\triangleq P_0^{(1)}(Y)+X\cdot P_1^{(1)}(Y)\\ & anddefining{q}^{(0)}(X)\triangleq X^2\end{array}$$

说的简单点就是按照类似于FFT的方法，对原多项式进行了变形，当然这里还有些其他推导，不过也不影响对主体过程的理解。

\begin{aligned} & verifier \ samples\ x^{(0)} ∈ F\ uniformly\ at\ random \ & and\ requests\ the\ prover\ to
send\ as\ its\ first\ oracle\ a\ function \ & f^{(1)} : L^{(1)} → F \ &that\ is\ supposedly\ the\ evaluation\ of \ & Q^{(1)}(x^{(0)} ,Y)\ on\ L^{(1)} . \end{aligned}

可以很清楚看到，$f^{(1)}$ 已经是 $<\frac{1}{2}\rho 2^n$ 的多项式。那么相对的，如果能证明 $f^{(1)}$ 的次数是小于 $\frac{1}{2}\rho 2^n$ 的那么也就证明了 $f^{(0)}$ 的次数是小于 $\rho 2^n$ 的。

以上就完成了一次“折叠”，prover的工作就是commit这些多项式，一直到最后一轮，最后一轮就直接把多项式发出来即可。

与之对应，verifier则需要针对该过程做两个检查：

• 确定最后一轮的多项式的次数
• 检查每一轮之间的约减是合法的(round consistency testing)。针对这个例子，采取的方法就是，所谓的 3-query test。以下是对该方法的综述。

$$\begin{array}{rl}& 1.sampleapairofdistinctelements{s}_0,s_1\in L^{(0)}suchthat{s}_0^2=s_1^2=y\\ & 2.query{f}^{(0)}(s_0),f^{(0)}(s_1)and{f}^{(1)}(y)denotethequeryanswersby{\alpha }_0,{\alpha }_{1}and\beta ,respectively\\ & 3.\because s_0\ne s_1,\therefore (s_0,{\alpha }_0),(s_1,{\alpha }_1)candetermineauniqueline,thisinpterpolatesthe{P}_Y^{(0)}(X)\\ & 4.check{f}^{(1)}(y)=P_Y^{(0)}(x^{(0)})\end{array}$$

这里有三点需要注意，

• 最后一步的左边是 $f^{(1)}(X)$，是verifier发给prover $x^{(0)}$之后确定的；而verifier自己插值出来的是 $P_Y^{(0)}(X)$。在正确的情况下，这两个多项式是 $Q^{(1)}(X,Y)$ 分别在固定 X， Y 时形成的。
• 该例中采用的是 $Y=X^2$，这是一个 $2-to-1$ 的一个映射，对定义域来讲完成了一个二分，就是分为两个coset（这就是论文反复提到的coset）。同时从值域角度来讲，也是将原来的求值域（也就是定义域）缩减到原来的一半，同时这也是下一轮的定义域。
• 个人理解所谓 3-query 是针对这个具体例子的。其代表的是verifier具体请求的点的个数，这里就是3个值，完成验证。如果有其他的“拆分”方法，query的个数也应该会不同。

2.2.2 FRI 协议

上面是“折叠”时，prover和verifier所做工作的一个示例。正式协议中，

• COMMIT PHASE 就是上述过程进行到最后一轮
• QUERY PHASE 最重要的一点是，round consistency testing要进行多次，这是为了提高协议的soundness lower bound，增强鲁棒性。

2.3 DEEP FRI

文献[4][5]主要都是在探讨（个人理解）怎样提高一种特定编码方式的lower bound(soundness)，只不过[4]在具体到RS问题时，对原始协议[3]并没有修改，其结果在[3]中的应用是改善了原协议的soundness，可以理解对原来bound分析的更精确化；而[5]则是在[4]的基础上进一步提高了soundness，提出了DEEP（Domain Extension for Eliminating Pretenders）方法，其在[3]上的应用，则是要对[3]的协议做出修改。

下图取自论文：

这两篇文献的特点都是讨论其方法在一般情况下的定理和性质，然后再具体到类似RS Code这种具体情况中。所以在查看论文时，如果不在意具体的对相关结论的铺陈和证明，则只需要关心其所要解决的问题，采用的方法和最后结论即可，只不过直接读论文，对这三点的掌握有可能淹没在茫茫公式中。

同时，直接查看 DEEP-FRI 或者是 ethSTARK，DEEP 方法的出现个人认为还是有点匪夷所思，所以以个人理解记录如下。

文献[4][5]总体来说都在讨论仿射结构 $u_x=u^{\ast }+x\ast u$ 与线性空间 $V$ 的平均距离和最大距离的关系。那么一个方向时在 $u^{\ast },u$ 与 $V$ 的距离是 $\delta$ 时，$u_x$ 与 $V$ 的距离；另一个方向就是 $u_x$ 与 $V$ 的距离为 $\delta$ 时， $u^{\ast },u$ 与 $V$ 的距离。

由于文献[4]作为过渡文献，虽然讨论的内容其实是很重要，但是其结果并未在 ethSTARK 中直接体现，更关键的是，它对于原本的 FRI 协议并未做修改，所以这里就直接简单记录下 DEEP 方法。

2.3.1 DEEP method for RS Code

弄清楚以下几点就可以明白该定理的含义：

• $V$ 是一大堆次数小于 $\rho |D|$ 的多项式的合集
• $V_{z,b}$ 是 $V$ 中在 $z$ 处值为 $b$ 的多项式的集合
• 图中(7)应该是一个条件，它描述了 $u^{\ast }+x\ast u$ 与集合 $V_{z,B_z(x)}$ 的距离在某一 $\delta$ 之内的概率，注意由于 $q$ 很大， $q>>d$ 且 $L_{\delta }^{\ast }$ 很小 这个概率值是很小的。翻译成普通话可以理解为，$u^{\ast }+x\ast u$ 所代表的多项式只要有可能是一个在 $z$ 处的值是 $B_z(x)$ 的次数小于 $\rho |D|$ 的多项式。
• $B_z(X)$ 的理解。设 $u^{\ast },u$ 代表的多项式分别为 $P^{\ast }(X),P(X)$，其在 $z$ 处的值为 $P\ast (z)={\alpha }^{\ast },P(z)=\alpha$。令 $B(Y,X)=P\ast (Y)+X\ast P(Y)$，则当 $Y=z$ 时， $B_z(X)=P\ast (z)+X\ast P(z)$ 就是一个一次多项式，当 $X=x$ 时就是具体的值 $B_z(x)$。虽然这是该定理的逆过程（该定理直接写出多项式$B$)，但是还是有助于理解，定理表达的就是一个高次多项式与 $B$ 相交于一个点。
• 由于 $v^{\ast },v\in V$ 的存在以及它们与 $u^{\ast },u$ 在 $C$ 上的值相等，那么结论就是 $u^{\ast },u$ 都是次数小于 $\rho |D|$ 的多项式。

通俗来说，只要 $u_x$有可能是一个在大域($Fq$) $z$ 处取值为 $b$ 的，次数小于 $\rho |D|$ 的多项式，那么它的两个组成部分 $u^{\ast },u$ 的次数也就都是小于 $\rho |D|$ 的。

2.3.2 DEEP-FRI

有了上述定理的铺垫，就能理解 DEEP-FRI 了，所谓 DEEP-FRI 就是采用了 DEEP 方法的 FRI。我的理解是，

$$\begin{array}{rl}& f^{(i)}代表第i轮的待证多项式\\ & H_x[f^{(i)}](Y)=P_0^{(i)}(Y)+x\ast P_1^{(i)}(Y)\\ & 如果H_x[f^{(i)}](Y)能够以一定的概率是小于d^{(i+1)}次的，那么P_0^{(i)}(Y)，P_1^{(i)}(Y)也都是小于d^{(i+1)}次的。\\ & 那么f^{(i)}就是小于d^{(i)}次的。\end{array}$$

上面这个想法就是 FRI，而 DEEP 会在接下来的过程中有所差异，原始 FRI 就此一直递归下去，而 DEEP 则是：

$$\begin{array}{rl}& DEEP方法要求证明H_x[f^{(i)}](X)是在z^{(i)}处的值为B_{z^{(i)}}(x^{(i)})的小于(d^{(i)}{)}^{{}^{\prime }}次多项式。\\ & 于是构造商多项式\\ & Quotient(H_{x^{(i)}}(X),z^{(i)},B_{z^{(i)}}(x^{(i)}))\\ & =\frac{H_{x^{(i)}}(X)-B_{z^{(i)}}(x^{(i)})}{X-z^{(i)}}=f^{(i+1)}\\ & 问题就转化成了证明f^{(i+1)}的次数d^{(i+1)}<(d^{(i)}{)}^{{}^{\prime }}-1\end{array}$$

有了以上思路整理，就可以明白 DEEP-FRI 协议了，下图取自[5]：

与之相应，协议对 round consistency testing 也有所调整。

note： $d^{(i+1)}=\frac{d^{(i)}}{2}-1$

2.3.3 DEEP ALI

这部分描述可能比较抽象，所以结合了 ethSTARK 的具体，看起来就明白了。下图取自论文[5]:

关于这段话，掌握以下三个要点：

• $f$ 是什么？答：可以理解为 ethSTARK 中的 $trace$ 多项式，就是 $witness$ 多项式
• $g$ 是什么？答：就是由 $f$ 构成（表示）的 $constraints$ 多项式。
• 有哪些事关 $g$ 的满足性的测试？答：一是 $g$ 本身是一个低度多项式，这是与 $g$ 本身的构造有关；二是，$g$ 确实是由先前提供的 $f$ 所组成的，这也就是文中所谓 consistency test。

标准做法就是 verifier 选择一个随机点 $\alpha$，要求提供（或者访问 oracle）所有相关 $f_i(\alpha \ast g^s)$ 的值（就是 $constraints$ 多项式各个组成部分在 $\alpha$ 处的值），以及 $g(\alpha )$，然后按照规则利用 $f_i(\alpha \ast g^s)$ 值计算 $g_{Verifier}(\alpha )$，然后检查 $g(\alpha )\stackrel{?}{=}{g}_{Verifier}(\alpha )$。上文指出这种方式 soundness 较低。（文中所说 $gap=\gamma \le \frac{1}{8}$，这里的 $\gamma$ 就是相对距离 $\delta$，$\delta$ 小，那么 soundness 就低，这是因为这说明两个多项式比较接近，只有少数不同，那算法检测出来的概率就低；理解这个还有一个关键，$\delta$是低度测试算法的输入，是事先就定好的，并且通常跟$\rho$有关）

DEEP 方法是，截图取自[5]：

简单说就是

• 把约束多项式做一个线性组合，产出 $g$。 (1 - 3)
• 将以前的随机点由 $\alpha$ 换成 $z$，注意，区别是 $z$ 是从一个比原来的求值域大得多的域上取来的。(4)
• 仍然分别求 $f,g$ 在 $z$ 处的值，并检查是否相等。(5)
• 对 $f,g$ 分别构造商多项式，这里说说我的理解。这是因为 $z$ 并非取自原有的求值域，所以不能在 commit 中直接检查 $f,g$ 在 $z$ 处的值是否正确，因此构造商多项式来证明。(6)
• 对商多项式进行低度测试。如成立，则证明了 (6) 的取值合法，又由于 (4) 则证明了 $f,g$ 的取值对应关系成立。还有一点，个人理解，对 $f,g$ 的商多项式的低度测试本身也证明了 $f,g$ 的本身是低度多项式（论文定理5.3^[5]），特别是 $g$ 多项式的低度测试，证明约束的满足。

2.3.4 DEEP 方法

从上面的讨论和总结来看，DEEP 方法本身不是什么高深莫测的方法，其要义是要对待证多项式在比原求值域大的多的域上，verifier 选取一个随机点 $z$，要求 prover 提供该处待证多项式的值，然后要求提供相应的商多项式的低度测试证明。它的功能有三个：

• 证明 prover 提供的点值确在某一多项式上
• 该多项式是次数低于某一次数的多项式
• 提高了以上两项证明的 soundness

从中也体会了文献[5]标题的含义，DEEP-FRI: Sampling Outside the Box Improves Soundness。

3. STARK 协议及其安全性

3.1 STARK 协议综述

目前 ethSTARK^[1] 就是基于 DEEP-ALI 的一套证明系统，该系统已经在ZK-STARK证明系统已经详细介绍。所以这里只做几个要点概述：

• 为什么需要 LDE？答：从前文对 RS Code 的介绍，在处理 RS Code 的问题时，相当于为了纠错而扩大了多项式的求值域。而在我们的场景下，是为了增强安全性，以降低 prover 在接受verifier 的检查时，“猜对”的概率。
• LDE 发生在何时？ 答：所有该承诺的多项式的commit值的求取，都应该发生在 LDE 域上（evaluation domain）；此外还有 FRI。
• 什么是 blowup factor？答：就是 RS Code 中的 R 的倒数，也就是 $\rho$ 的倒数。
• 除 FRI 外，哪些多项式需要 commit？答：所有的 $trace$ 多项式，以及 $Composition$ 多项式。注意 $Composition$ 多项式可能因为出现高次面临拆分。此时，其拆分出来的各个部分与 $trace$ 多项式次数相同，因此称为 $CompositionPolynomialTrace$，它们需要分别进行与 $trace$ 多项式相同的 LDE，然后进行 commit。
• commit的方式是什么？有何优化？答：方式是 Merkle Tree。优化是所有 $trace$ 多项式组成一棵 Merkle Tree，其叶子是各 $trace$ 多项式在同一点求值（所谓同一个 row）的拼接。$CompositionPolynomialTrace$ 亦然。
• 什么是 Compostion 多项式？答：就是约束多项式的线性组合。
• DEEP 多项式是什么？为何要构造它？答：将在下一小节简要说明。

3.2 DEEP 多项式

有了 2.3.3 的阐述，对于 DEEP 多项式就有比较清楚的认识了。实际上，没有 DEEP 多项式，从 Composition 多项式构造完毕开始，直接开始 FRI，并辅以 witness 与 constraints 的一致性检查，就完全可以称为一套证明系统了。

而运用了 DEEP-ALI 则如 2.3.3 与 2.3.4 所阐述，达到了一箭五雕的目的。

• 证明了 $z$ 处各值在对应的多项式上
• 证明了 $trace,composition$ 的一致性
• 证明了约束的成立
• 证明了 $trace$ 多项式是定义在 $F_q$ 上的，即：它的所有系数都是来自于 $F_q$。（具体方法参见3.8.2^[1]）
• 以上各项的概率都比上面的传统方法要强

这里有两点需要注意：

• 乍一看 DEEP 多项式的前面的求和项好似 $trace$ 多项式的线性组合，这是不了解时容易犯的错误。
• DEEP 多项式是三个商多项式的线性组合： $CompositionPolynomialTrace$，约束中出现的 $trace$，$trace$ 多项式为 $F_q$ 上而构造。

3.3 STARK 的安全性

3.3.1 DEEP + FRI 的安全性

所以对于STARK安全性的讨论就首先就要对 DEEP 多项式构造后的安全性的讨论。这里直接引用手册^[1]中的例子，并做简单的阐述。

这里只要明确几个问题就可以完全明白：

1. 作弊后如何通过 verifier 的检查？答：这要根据 verifier 的检查来分别讨论，一个是 DEEP 多项式自身值的一致性检查，一个是 FRI 的正确性。
2. 如何通过 FRI 测试？ 答：所有正式参与 FRI 的多项式都是“真”的。
3. 如何通过 DEEP 一致性的检查？ 答：只有一定的概率可以通过，参与 DEEP 值的计算的各个部分的值都是承诺过的。
4. 综合2，3，如果要伪造一个 $DEE{P}_{fake}$，它满足：
   • 在求值域 $D$ 的一个 $\rho -fraction$ 集合 $S$ 上与 $DEE{P}_{real}$ 值相等。这也达到了一个 $|S|-1$ 次多项式 $DEE{P}_{fake}$ 与一个高次多项式 $DEE{P}_{real}$ 交点个数的上限。（因为 $|S|=\rho |D|$，“真”多项式的次数是 $|S|-1$）
   • $DEE{P}_{fake}$ 必然能通过 FRI 测试。

综上，就很容易看出，在一次测试中，能通过 verifier 检查的概率就是 $\rho$。所以一次测试可以提供 $\log \frac{1}{\rho }$ bits 的安全性。假设测试需要进行 $l$ 次，那么就提供了 $$k(bitssecuritylevel)=\log \frac{1}{\rho }\ast l$$

3.3.2 grinding 安全性

这个过程和简单，大家很熟悉，就是证明在hash后要满足先导 0 的要求。其目的是通过增加造假的计算代价，来减轻 $l$ 的压力。而由于该过程只能 brute-force，因此设置几个先导 0 就是几个 bits security level。

3.3.3 STARK 安全性

所以，就基本可以看懂论文中如下公式：

参考文献

• [1] ethSTARK Documentation – Version 1.1
• [2] POLYNOMIAL CODES OVER CERTAIN FINITE FIELDS
• [3] Fast Reed-Solomon Interactive Oracle Proofs of Proximity
• [4] Worst-case to average case reductions for the distance to a code
• [5] DEEP-FRI: Sampling Outside the Box Improves Soundness