消退证明

在电路的所有赋值都已经承诺之后，证明者现在需要证明各种各样的电路关系都是满足的：

• 自定义门，用多项式 ${\text{gate}}_i(X)$ 表示。
• 查找证明的约束
• 相等约束置换的约束

从电路的列的角度看，每个关系都由一个 $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)$

如果描述关系的多项式为 $0$，我们就说关系是满足的。一种表示这种此种约束的方法，就是将每个多项式关系都除以消除多项式 $t(X)=(X^n-1)$，消除多项式是以 ${\omega }^i$ 作为根的最低次数的单项式。如果关系多项式能被 $t(X)$ 整除，那么在域上这个关系多项式就等于 $0$。

这种朴素的构造方式的弊端在于，其需要对每个关系都需要有一个多项式承诺。相反，我们可以对电路中所有关系同时进行承诺：验证者取一个 $y$，然后证明者构造一个商多项式，

$$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)$ 整除，那么所有的关系都满足的概率就是非常高的
• 相反地，哪怕只有一个关系是不满足的，那么在点 $x$ 处，$h(x)\cdot t(x)$ 与分子多项式在该处的值就几乎不可能相等。也就是说，在此种情况下，分子多项式不能整除 $t(X)$。

承诺 $h(X)$

$h(X)$ 的次数是 $(d-1)n-d$ （因为分母 $t(X)$ 的次数是 $n$）。但是我们在 Halo 2 中的多项式承诺机制仅仅支持次数 $n-1$ 次的多项式的承诺（这是因为除了关系多项式的承诺，协议其他部分所需承诺的多项式的最大次数就是 $n-1$）。为了不给多项式承诺机制增加额外的成本，验证者就需要把 $h(X)$ 分割成多个，每个只有 $n-1$ 次的多项式的和，

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

并对每一部分产生一个具有隐藏承诺。

$$\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}$ 是否一致。为了高效实现此一目的，我们使用了多点打开证明。