译自 halo2 book:https://zcash.github.io/halo2/design/proving-system/vanishing.html

消失论证(Vanishing argument)

在对电路赋值完成承诺后,证明者(prover)现在需要证明各种电路关系都被满足:

• 自定义门(custom gate),由多项式 ${\text{gate}}_i(X)$ 表示。
• 查找论证(lookup argument)的规则。
• 等式约束置换(equality constraint permutation)的规则。

这些关系中的每一个都被表示为一个关于电路列的、度数为 $d$(任意关系的最大度数)的多项式。鉴于每一列的赋值多项式度数为 $n-1$,这些关系多项式关于 $X$ 的度数为 $d(n-1)$。

在我们的示例中,这些就是门多项式,度数为 $3n-3$:

• ${\text{gate}}_0(X)=a_0(X)\cdot a_1(X)\cdot a_2(X{\omega }^{-1})-a_3(X)$
• ${\text{gate}}_1(X)=f_0(X{\omega }^{-1})\cdot a_2(X)$
• ${\text{gate}}_2(X)=f_0(X)\cdot a_3(X)\cdot a_0(X)$

如果一个关系的多项式等于零,则该关系被满足。证明这一点的一种方式是把每个关系多项式除以消失多项式(vanishing polynomial)$t(X)=(X^n-1)$,它是在每个 ${\omega }^i$ 处都有根的最低度数多项式。如果某个关系的多项式能被 $t(X)$ 整除,那么它在整个域(domain)上等于零(正如所期望的)。

这个简单的构造将需要对每个关系做一次多项式承诺(polynomial commitment)。我们改为同时对所有电路关系做承诺:验证者(verifier)采样 $y$,然后证明者构造商多项式(quotient polynomial)

$$h(X)=\frac{{\text{gate}}_0(X)+y\cdot {\text{gate}}_1(X)+\cdots +y^i\cdot {\text{gate}}_i(X)+\dots }{t(X)},$$

其中分子是各电路关系的一个随机(证明者在验证者采样 $y$ 之前已对单元格赋值做出承诺)线性组合。

• 如果分子多项式(以形式不定元 $X$ 表示)能被 $t(X)$ 完美整除,那么以高概率所有关系都被满足。
• 反之,如果至少有一个关系不被满足,那么以高概率 $h(x)\cdot t(x)$ 将不等于分子在 $x$ 处的求值。在这种情况下,分子多项式将不能被 $t(X)$ 完美整除。

对 $h(X)$ 做承诺

$h(X)$ 的度数为 $d(n-1)-n$(因为除数 $t(X)$ 的度数为 $n$)。然而,我们在 Halo 2 中使用的多项式承诺方案只支持对度数为 $n-1$ 的多项式做承诺(这是协议其余部分需要承诺的最大度数)。为了不增加多项式承诺方案的成本,证明者把 $h(X)$ 拆分成多个度数为 $n-1$ 的片段

$$h_0(X)+X^n{h}_1(X)+\cdots +X^{n(d-1)}{h}_{d-1}(X),$$

并对每个片段生成盲化承诺(blinding commitment)

$$\mathbf{H}=[\text{Commit}(h_0(X)),\text{Commit}(h_1(X)),\dots ,\text{Commit}(h_{d-1}(X))].$$

对多项式求值

到此为止,我们已经对电路的所有性质做出了承诺。验证者现在想要查看证明者是否承诺了正确的 $h(X)$ 多项式。验证者采样 $x$,证明者生成各个多项式在 $x$ 处的声称求值,涵盖电路中使用的所有相对偏移,以及 $h(X)$。

在我们的示例中,这将是:

• $a_0(x)$
• $a_1(x)$
• $a_2(x)$, $a_2(x{\omega }^{-1})$
• $a_3(x)$
• $f_0(x)$, $f_0(x{\omega }^{-1})$
• $h_0(x)$, ..., $h_{d-1}(x)$

验证者检查这些求值是否满足 $h(X)$ 的形式:

$$\frac{{\text{gate}}_0(x)+\cdots +y^i\cdot {\text{gate}}_i(x)+\dots }{t(x)}=h_0(x)+\cdots +x^{n(d-1)}{h}_{d-1}(x)$$

现在确信这些求值整体上满足门约束后,验证者需要检查这些求值本身与原始的电路承诺以及 $\mathbf{H}$ 是一致的。为了高效地实现这一点,我们使用多点打开论证(multipoint opening argument)。