STARK基本上是这样
[19:20]
你有一个想要证明的多项式$P(x)$和条件比如在一定x区间内P在一定范围
[19:20]
然后用条件多项式让满足的x可算出C(P(x))=0
[19:21]
接下来用另一个指定x范围的多项式Z(x)=(x-1)(x-2)...
[19:21]
C范围也可以是C(x)=(x-1)(x-2)
[19:21]
然后在x满足条件的时候我们就能知道C(P(x)) = Z(x) (已编辑)
[19:22]
因为他们共享这部分解
[19:23]
数学上两个共享部分解的多项式呈倍数关系
[19:23]
于是可以得到另一个D(x)多项式等于C(P(X))/Z(x)
[19:24]
所以C(P(x)) = Z(x) * D(x)
[19:24]
对于所有x都成立
Rorical — 昨天19:24
C(P(x)) = Z(x) 只在这一串特定的X成立，但是 C(P(x)) = Z(x) * D(x) 对于所有的X都成立
[19:24]
于是就拉开了差距
[19:26]
也就是说验证者可以检测任意x的 C(P(x)) = Z(x) * D(x) 是否成立，如果一旦 P(x) 有一点不符合那么对于绝大多数x这个等式都会变得不成立
Rorical
于是可以得到另一个D(x)多项式等于C(P(X))/Z(x)
Rorical — 昨天19:26
D(x) 可以通过长除法得到，所以 C(P(x)) 和 Z(x) * D(x) 的degree是一样的
[19:27]
数学上两个degree相同但是系数不同的多项式最多共享degree个交点
[19:27]
所以当抽查范围远远大于degree的时候就可以实现少量抽查则大概率证明正确性
[19:29]
验证的时候需要用merkle tree做个关于C(P(x))的大范围抽查结果并且提交merkle root来做commitment
[19:30]
这个就是Low-Degree Extension，论文里描述的也是用来boost error的一种方式，让一丁点错误被无限放大
[19:30]
但是有个问题是验证者只知道Z，而C和D的值是证明者给的
[19:31]
如果证明者瞎jb选C值然后计算D=C/Z也是能蒙混过关
[19:32]
所以引入FRI对两个多项式C和D做检查，也就是检查证明者是否提供的值都在degree小于一定值的多项式上面
[19:33]
这样就避免造假C和D，因为D是长除法之类出来的所以随机选或者错误选C就没法长除出来一个完整的D来
Rorical — 昨天19:33
FRI本身又是对于测试一些点是否在同一个degree<D多项式上原始方法的改进
[19:34]
原始的是随机选D个点做拉格朗日插值得出一个多项式，然后再随机拿一个点看在不在这个插值出来的多项式上，如果是那就大概率都是一个多项式的
[19:36]
但是这样太麻烦，因为当D很大的时候就需要很多通讯成本，于是就把它分解成一个low degree但是两个输入的函数f(x) = y(x, x^1000)