# FRI协议之，共线性测试的通用概述
## 概述
本文针对FRI中的split and fold环节，对于从 $f_{i}(x)$ 迭代成 $f_{i+1}(x)$ 过程，所需要满足的约束，进行演进概述。
并试图，揭示更General的，折 $N=2^k$ 情况下(而非对半折，N=2), 更通用的由 $f_{i}(x)$ 迭代成 $f_{i+1}(x)$ 的演进证明。

## 经典FRI
定义fold前的函数为 $f_{i}(x)$ ,将其进行按奇偶项进行split and fold，
$$f_{i}(x)=f_{E}(x^2)+xf_{O}(x^2)$$
这里，我们若取用 $y$ 来代替 $x^2$,即 $y=x^2$ 时,则上式变为：
$$f_{i}(x,y)=f_{E}(y)+xf_{O}(y)$$
需要注意的是：这个函数视为一个关于（x,y)的二元函数，并不要求 $y=x^2$
我们若在这个式子中，固定y值 $y=\beta$，则变为一个关于x的degree=1的线性函数：
$$f_{i}(x)=f_{E}(\beta)+xf_{O}(\beta)$$
那么，在这个线性函数上，我们任取三点，这三点都是共线的(degree=1)。
我们取 $y=\beta$ 时，对应的两点 $x_{0}$、 $x_{1}$ ,即 $\beta=x_{0}^2=x_{1}^2$ 。我们再随机取一点 $x=\alpha$ 可知在 $y$ 被固定为 $\beta$ 时,可知这三点 $(\alpha,f_{i+1}(\alpha)),(x0,f_{i}(x0)),(x1,f_{i}(x1)$是共线性的。

这里需要注意到，由于$\beta=x_{0}^2=x_{1}^2$ ，那么$f_{E}(\beta)+xf_{O}(\beta)$的计算，其实与原使的 $f_{i}(x)$是一样的。
而对于 $x=\alpha$ 时，我们将 $f_{i}(x)$ 看作为一个固定了 $x=\alpha$ ,的关于 $y$ 的函数，变化为 $f_{i}(y)$ ，最终为方便统一形式，其实就可以表达为split后下一Layer的 $f_{i+1}(x)$
$$f_{i}(x)=f_{i}(y)=f_{E}(y)+\alpha f_{O}(y)$$ $$f_{i+1}(x)=f_{E}(x)+\alpha f_{O}(x)$$

综上可知：$(\alpha,f_{i+1}(x)),(x0,f_{i}(x0)),(x1,f_{i}(x1)$

## 对于折N折的情况
对于折N折的情况，我们参考V神的文章，其实可以知道，具有类似的属性。
如上图，当按 $y=x^N$ 来折叠为时，那么有图中的N+1个点,其构成了 $degree=N-1$ 的一个多项式。
将一个多项式fi(x)，按 $y=x^N$ 折叠后，变为：
$$f_{i}(x)=f_{4}(y)+x^3 f_{3}(y)+x^2 f_{2}(y)+x f_{1}(y)$$ 这里按 $x$ 幂次，拆成了四个函数。那么，当固定 $y=\beta=x_{0}^4=x_{1}^4=x_{2}^4=x_{3}^4$ 时,上式变为一个关于 $x$ 的degree为3的函数。
$$f_{i}(x)=f_{4}(\beta)+x^3 f_{3}(\beta)+x^2 f_{2}(\beta)+x f_{1}(\beta)$$同样，当固定 $x=\alpha$时，该式可视为 $f_{i+1}(y)$是关于 $y$ 的函数。
同理可以得到： $(x_{0},f_{i}(x_{0})),(x_{1},f_{i}(x_{1})),(x_{2},f_{i}(x_{2})),(x_{3},f_{i}(x_{3}))与 (\alpha, f_{i+1}(\beta))$，这五点是构成一个degree为3的函数。这里只需要验证这一点即可。

## 共线性测试，与从$f_{i}$到$f_{i+1}$的进化，是等价的
直接将手算的过程放上。可见是等价的。代码中可按三点的degree=1 来进行测试即可。

## 扩展研究
### V神文章中的N折
V神文章中，举了1000为例。实际上是类似的，即取一个固定的y值，得到的1001个点（1000个在 $y=x^{1000}$ 上,另一个是 $(\alpha,f_{i+1}(y))$ ，是形成一个degree<1000的多项式。

### 按N折需要研究的
1、按N=2^k折，那么其安全性，计算量，是与N=2是一样的吗？
2、这样，能证明的degree跨度更大了？原来只能证明degree在 $2^k$ 的区间，现在只能证明在 $N^k$ 的取间了。
3、研究Keep说的RISC0是按16折
https://www.youtube.com/watch?v=wqRuoyH3Mqk 在这个视频中的32分钟 ～ 35 分钟提到RISC0 按照16 来折叠的