零知识证明 二 多项式

多项式

零知识采用多项式充当证明的媒介。

其中涉及到代数基本定理：

• 任何复系数一元n次多项式，方程在复数域上至少有一根(n≥1)，由此推出，n次复系数多项式方程在复数域内有且只有n个根。

进而可推出，当两个次数相同的一元n次多项式有且只有n个交点。

示例

假设验证者手中有一个一元n次多项式。

证明者声称他知道验证者的多项式。

他们可以使用以下的方式进行交互：

• 验证者选出一个随机的值$x$，并求出多项式结果。
• 验证者把$x$给证明者，要求证明者对$x$进行求值。
• 证明者将结果给验证者。
• 验证者检验证明者给的值是否与自己计算的一致。如果一致那么这个语句将会有很大程度是真的。

例如，如果我们考虑$x$的整数范围从1到$10^{77}$，不同多项式的非交点最少为是$10^{77}-d$ ($d$：次数)，因此$x$意外“命中”任何$d$的交点的概率等于(微不足道的) :

$$\frac{d}{10^{77}}$$

假设$d$足够小于范围的上限，几乎是100%

参考资料

https://medium.com/@imolfar/why-and-how-zk-snark-works-1-introduction-the-medium-of-a-proof-d946e931160