# FRI低度测试中的示例及思考
## 针对某FRI文章：
针对[此FRI介绍](https://blog.nowcoder.net/n/f9742fdb7b2c459ca2be87c7ff5a7f46?from=nowcoder_improve),做一个思考及示例研究。
此文章中，对应于经典的FRI（按degree折半的方式进行验证），与[此版本对应Python代码]（https://github.com/aszepieniec/stark-anatomy） 的方式相同。

### 选取案例：
$f_{0}(X)=2X^4+3X^3+5X^2+X+3$ 作为示例,则 $Q(X,Y)=(2Y^2+5Y+3)+X(3Y+1)$
- step1
Verifier，对 $Q(X,Y）$随机选取 $x$，使得 $x=\alpha=2$,
Prover计算得到: $f_{1}(Y)=2Y^2+11Y+5$
- step2
Verifier选取 $y=1$,则对应的 $x0=1, x1=-1$, 且query得到： $f_{0}(x0)=14, f_{0}(x1)=6$
然后，取 $y=1$ 处的$f_{1}(y)=f_{1}(1)=18$
验证共线性可知： $(x0,f_{0}(x0)),(x1,f_{0}(x1)),(\alpha,f_{1}(y))=(1,14),(-1,6),(2,18)$ 是共线性的
- step3
低度测试：判断 $f_{1}(Y)$ 是对应的低度，即 $f_{1}∈[F,L,ρ]$

### 分析关键：

一开始是对这个共线性测试，百思不得其解，仔细思考后发现如下：
- 对于下图的定义域为 $X∈L0,而Y∈L1$ , 定义域为 $L0*L1$，即为对应的绿色区域，其实相当于将最起初的 $f_{0}(X)$ 转变为了 $Q(X,Y)$ 了，即将一个1D的函数变为2D的，因此其定义域也是2D的了。
- 在红色曲线（实际为离散点，画为连续时为示意）时，方有 $f_{0}(X)=Q(X,Y)$ 而不是红色曲线上的点，是不等的。即，红色曲线上时，方有 $Y=X^2$ ,此时还原为了原曲线。
- 之所以会共线性，是因为此时是将 $y$ 固定住了。从而将 $Q(X,Y)$ 变为以 $X$ 为单变量的一阶线性函数，即为 $f(X)=a+bX$ 因此，在X取不同值时，a与b保持不变。因此是线性的。**特别要注意的是**：上述例子中，取 $y=1$ 时， $x0=1,与x0=-1$ 为原始 $f0(X)$ 曲线上的点。而 $y=1,x0=2$ 时，并不是原始曲线 $f0(X)$ 上的点,需要注意这个点是怎么来的：它是针对 $Q(x,y)$ 取随机点 $x=2，y=1$ 得到。
- 正确的叙述流程其实是先对 $Q(x,y)$ 取了随机点 $(x=2,y=1)$ ,然后根据 $y=1$ 得到 $y=x^2$ 曲线(也就是由 $f0(x)$ 折半为 $f1(x)$ 的约束曲线)上的点 $(x0,x1)$ 。而 $Q(x,y)=f(x)=a+bX$ ,在本案例中为 $f(x)=10+4x$,即对应的点为$(1,14)与(-1,6)$
- 最终：这三点的共线性。因为固定y时， $Q(x,y)$可表达为 $a+bx$
- 如果将这个例子进行下去，再做一轮：由 $f_1(x)=2x^2+11x+5=Q(X,Y)=(2Y+5)+X*11$ 我们可以再取： $x=\alpha=3,y=1$,则可以迭代下一轮的多项式 $f_2(x)=7+11x$，照样得到此时的点 $(1,18)$ 与 $(-1,-4)$，验证： $(1,18),(-1,4),(3,1)$共线性。
注：这张图中的纵坐标是y，如果将纵坐标的刻度改为x^2，那么抛物线应该变成一条直线（同V神文章中的图）

### 为何要做多轮测试？何为Proximity要求？
考虑到一些点并不是在原始曲线上，需要对这种验证过程重复多次。
例如：我们知道大部分的点，在 $f_{0}(X)=2X^4+3X^3+5X^2+X+3$ 曲线上
我们再做一次正确性的验证，过程如下：
- step1
$x=\alpha=2，f_{1}(Y)=2Y^2+11Y+5$
- step2
取 $x0=3, f_{0}(3)=294, x1=-3, f_{0}(-3)=126$ 对应于 $y=9$
计算， $f_{1}(9)=122$
可以轻松验证共线性。
- 假设，有一个点不在此曲线上
设针对 $x0=3时，f_{0}(3)=2X^4+3X^3+5X^2+X+4=295$ 那么我们知道，(3,295)实际上不是在该曲线上。那么，此时验证共线性则必失败。

所以，我们可以得出结论：共线性测试是保证了由 $f_{0}到f_{1}$ 选取的每个随机点，都是在对应曲线上的。

而之所以需要做多次：提高正确验证的概率，防止因为未能抽取到那个不在曲线上的点，而误判为正确。（降低这种误判的风险。假设存在10%概率的错误点，没有抽种这个错误点的概率为0.9，十次未抽中的概率为 $0.9^{10}=0.349$ 也就是说10次都（错将不正确误判为对）的概率很低。
如果本身100个点只有一个点为错误点，概率则为 $0.99^{10}=0.90$ 虽可能有误判，但很接近正确。可以说是概率上的接近。

## 针对V神stark文章第二部分：
[V神文章 Stark II:FRI](https://vitalik.eth.limo/general/2017/11/22/starks_part_2.html)

### 原始验证示例
Prover：复杂度为10^18^

#### 小示例举例
原始 $f(x)=1+x+x^{1001}+x^{3005}+x^{12}+x^{11001}$
取 $y=x^{1000}$ 后，上式变为
$g(x,y)=1+x+xy+x^5y^3+x^{12}+xy^{11}$
1. 固定 $x=x_{0}$ ,随机取1010个 $y$ 值进行query，看是否满足 $degree<1000$
此时 $g(x,y)=g(y)=(1+x_{0}+x_{0}^{12}+x_{0}y+x_{0}^{5}y^3+x_{0}y^{11})$
这是一个关于y的多项式。此时，若该多项式满足： $degree<1000$ ，则说明原多项式 $f(x)$ 满足 $degree<1000000$
2. 固定 $y=y_{0}$，则此时：
$g(x,y)=g(x)=1+(1+y_{0}+y_{0}^{11})x+y_{0}^{3}x^5+x^{12}$
这是一个关于x的多项式。此时，若该多项式满足： $degree<1000$ ，则说明原多项式 $f(x)$ 满足 $degree<1000000$
3. 此时还要验证：对于对角线上的点，满足 $y=x^{1000}$ 时：当固定 $x=x0$ 时，query $g(y)$ 与固定 $y=y0$ 时，query $g(x)$ ，二者是否相等，即为同一多项式？
**<p style="color: red;">第三点有些不确定，存疑问</p>**

### 优化验证1
原始方案，Prover要commit每个点，是 $10^9 * 10^9 = 10^{18}$
优化步骤：取p=1,000,005,001 $\forall x \in[0,|P| ]$
那对于y按x^1000 modulus p进行取值，可知 y为0,1,... 1000006
此时：降为 $10^9 * 10^6=10^{15}$


### 优化验证2
进一步优化
固定y值，取一行。并且只取1000个点（只取x^1000=y的点？）
注意图中的对象线只有1000条。因此每一行只有1000个数据点？针对这1000个点，构造一个多项式。
**这一部分有一些存疑**
然后取一个列（固定x值），这里应该是10^6^个点，同样验证这里的多项式是否degree<1000
然后，做验证？
**<p style="color: red;">总结，自己在这一段，好像没有懂。先搁置一下，再看一下其它的内容**</p>

## v神文章继续研究
### part2:原始计算法
#### 证明过程
- 证明目标：
- 要证明：在N=10^9^ points上，其多项式degree<10^6^
- 定义域：
- $x \in N={0,1,2...10^9}$
- $y \in M=[{x^{1000}:1<=x<=N}]$
- Commit：
- 将整个$x \in N, y \in M$ 的点进行commit，则须commit的数量为：$10^18$
- Verify
- 取部分行（固定y值）、且该行取1010个点；取部分列（固定x值）、且该行取1010个点；
- 取对象线上，
- V神举例，取30行，30列。相当于取：x=x0,x1...x30，那么在固定x的情况下，可对应插值出g0(y)、g1(y)...g30(y)，同理g0(x)、g1(x)...g30(x)

#### 疑问
- 为何不是只取对象线上的10^6个点即可？如果只取对象线上的点可以验证，那是不是不用取colunm或row了？
- 下图的疑问

### part2:优化一
- 定义域变换：
- x仍然是1~10^9,略扩大一点到p=1000005001
- y取x^1000^ mod p
- 图形中的对象线，变为循环围绕式
- Prover
- 优化后：需要Commit 10^9^ * 10^6^ =10^15^ 个点
- Verify
- 取任意一个y=y0值，取各条对角线上的对应点（共1000个），将其插值为一个degree<1000的多项式f(x)。（这些点就是原始点？多项式相当于是原始多项式，当y=x^1000^时）
- 然后：任取一个x值(x0)，验证(x0,y0)在f(x)上。（因为y值被固定，所以必在此曲线上）
- 最后：针对固定这个x值的colunm，取1000个y值点形成f(y)，验证其degree<1000
- 该优化后的计算量：
- Verifier:仍然是亚线性？
- Prover：降至10^9？是否是，现在只commit在对角线上的这些点？
- **<p style="color: red;">（即：10^3^ 根对角线，每根为10^6^ 个点，这样，其它点不用？但是不对呢，不是还要取一个colunm吗？那这样不还是要commit其它点吗？）**</p>

### part2:进一步优化：折半的低度测试

关于Jade分享中的困惑


另外，这个数学公式的含义？可否解释一下？


这里应该就是FRI的不断折半的过程
但是：（1）commit的范围仍然没有变吧？x取值，仍然是从1~10^9，而y的范围则是1~10^9/2?
(2)各轮次之间的f(x)有怎样的关系？好像不是像图中说的，上一轮f(x)，怎么做为下一轮的f(x)