1. 主页
  2. 文档
  3. zk-SNARKS验证教程
  4. 多项式盲估

多项式盲估

这篇文章的目的是回顾多项式的概念以及解释什么是多项式盲估,还有如何使用同态隐藏来实现多项式盲估,在未来的文章中,会讲述多项式盲估如何作为 SNARk 的核心构建工具。

$\mathbb{F}_p$ 表示大小为 p 的域,它的元素是 {0,…,$p$-1} ,加法和乘法操作在第一部分中已经完成。

多项式和线性组合

回顾一下,域 $\mathbb{F}_p$ 上的阶数为 d 的多项式表达形式:
对于域 $\mathbb{F}_p$ 上的 $a_0,…,a_d$
$P(X) = a_0+a_1*X+a_2*X^2+…+a_d*X^d$

我们可以通过替换多项式中的 X 来评估域 $\mathbb{F}_p$ 上点 s 的 P 多项式,即

$P(s)=a_0+a_1*s+a_2*s+…+a_d*s^d$

对熟悉多项式 P 的人来说, P(s) 的值是 $1,s…,s^d$的线性组合,其中线性组合指的是“加权平均”,在 P(s) 中特指 $a_0,a_1…a_d$

在先前的文章中,同态隐藏 E 的定义式为 $E(x)=g^x$,其中 g 用来生成离散对数问题的群。

同态隐藏支持加法操作,即可通过 E(x)和 E(y)来计算 E(x+y);同时它也支持线性组合,即给定 a,b,E(x),E(y),可计算 E(ax+by) 。这非常容易证明,即:

$E(ax+by)=g^{ax+by}=g^{ax}*g^{by}=(g^x)^{a}*(g^y)^{b}=E(x)^a*E(y)^b$

多项式的盲估

假设 Alice 有 d 次多项式 P, Bob 有他随机选择的点 s ,其中 $s \in \mathbb{F}_p$

Bob 的目的是知道 E(P(s)) ,即多项式 P 在点 s 处的同态隐藏。Alice 向 Bob 发送多项式 P, 由 Bob 自行计算 E(P(s)) ;

Bob 向 Alice 发送 s , Alice 以此计算 E(P(s)) 并把它发还给 Bob .

其实多项式盲估的目的是让 Bob 在不知道多项式 P 本身的情况下获取 E(P(s)) ,这在第一步已经呈现。更重要的是让 Alice 无法获知域$\mathbb{F}_p$ 上的点 s ,这是第二步要做的工作。

基于同态隐藏,可通过以下步骤来执行多项式盲估:

  1. Bob 向 Alice 发送 $1,s….s^d$ 的同态隐藏 $E(1),E(2),….,E(s^d)$
  2. Alice 通过第一步中的元素计算 E(P(s)),并将其发送给 Bob(这是因为 E 支持线性组合,而 P(s) 是 $1,s,…,s^d$ 的线性组合)

值得注意的是,此时 Alice 不知道 s,而 Bob 不知道 P.

多项式盲估的用处

之后的文章会详细介绍 SNARK 中如何使用多项式盲估。
比较粗略浅显的理解是验证者知道正确的多项式,并以此检查证明者是否知道这个多项式,让证明者在随机选择的点上盲估多项式,确保如果证明者在不知道正确多项式的情况下有极高的概率给出错误的答案,而这所依赖于 Schwartz-Zippel 引理 ,即“不同的多项式在大多数点上是不同的”。

我们要如何帮助您?