译自 halo2 book：background/pc-ipa.md

使用内积论证(inner product argument)的多项式承诺(polynomial commitment)

我们想要承诺(commit)某个多项式 $p(X)\in {\mathbb{F}}_p[X]$，并能够可证明地在任意点处对所承诺的多项式求值。朴素的方案是让证明者(prover)直接把多项式的系数发给验证者(verifier)：然而，这需要 $O(n)$ 的通信量。我们的多项式承诺方案则用 $O(\log n)$ 的通信量完成这件事。

Setup

给定参数 $d=2^k,$ 我们生成公共参考串(common reference string) $\sigma =(\mathbb{G},\mathbf{G},H,{\mathbb{F}}_p)$，它为本方案定义了若干常数：

• $\mathbb{G}$ 是一个素数阶 $p$ 的群；
• $\mathbf{G}\in {\mathbb{G}}^d$ 是一个由 $d$ 个随机群元素组成的向量；
• $H\in \mathbb{G}$ 是一个随机群元素；以及
• ${\mathbb{F}}_p$ 是阶为 $p$ 的有限域。

Commit

Pedersen 向量承诺 $\text{Commit}$ 定义为

$$\text{Commit}(\sigma ,p(X);r)=⟨\mathbf{a},\mathbf{G}⟩+[r]H,$$

其中 $p(X)\in {\mathbb{F}}_p[X]$ 是某个多项式，$r\in {\mathbb{F}}_p$ 是某个盲化因子(blinding factor)。这里，向量的每个元素 ${\mathbf{a}}_i\in {\mathbb{F}}_p$ 是 $p(X)$ 第 $i$ 次项的系数，而 $p(X)$ 的最高次数为 $d-1.$

Open（证明者）与 OpenVerify（验证者）

改进版的内积论证是关于如下关系的知识论证(argument of knowledge)

$$\boxed{\{((P,x,v);(\mathbf{a},r)):P=⟨\mathbf{a},\mathbf{G}⟩+[r]H,v=⟨\mathbf{a},\mathbf{b}⟩\}},$$

其中 $\mathbf{b}=(1,x,x^2,\cdots ,x^{d-1})$ 由求值点 $x$ 的递增幂次组成。这使得证明者能向验证者证明：承诺 $P$"内部"所含的多项式在 $x$ 处求值为 $v,$ 而且，所承诺的多项式具有最高次数 $d-1.$

内积论证进行 $k={\log }_{2}d$ 轮。就我们的目的而言，只需了解它的最终输出即可，对于中间各轮我们仅提供直觉。（完整解释请参阅 Halo 论文第 3 节。）

在开始论证之前，验证者选取一个随机群元素 $U$ 并把它发给证明者。我们在第 $k$ 轮初始化论证，使用向量 ${\mathbf{a}}^{(k)}:=\mathbf{a},$ ${\mathbf{G}}^{(k)}:=\mathbf{G}$ 和 ${\mathbf{b}}^{(k)}:=\mathbf{b}.$ 在每一轮 $j=k,k-1,\cdots ,1$ 中：

• 证明者通过取 ${\mathbf{a}}^{(j)}$ 与 ${\mathbf{G}}^{(j)}$ 和 ${\mathbf{b}}^{(j)}$ 的某个内积来计算两个值 $L_j$ 和 $R_j$。注意它们在某种意义上是"交叉项(cross-terms)"：$\mathbf{a}$ 的下半部分与 $\mathbf{G}$ 和 $\mathbf{b}$ 的上半部分一起使用，反之亦然：

$$\begin{array}{rl}{L}_j& =⟨{\mathbf{a}}_{\mathbf{lo}}^{(\mathbf{j})},{\mathbf{G}}_{\mathbf{hi}}^{(\mathbf{j})}⟩+[l_j]H+[⟨{\mathbf{a}}_{\mathbf{lo}}^{(\mathbf{j})},{\mathbf{b}}_{\mathbf{hi}}^{(\mathbf{j})}⟩]U\\ R_j& =⟨{\mathbf{a}}_{\mathbf{hi}}^{(\mathbf{j})},{\mathbf{G}}_{\mathbf{lo}}^{(\mathbf{j})}⟩+[r_j]H+[⟨{\mathbf{a}}_{\mathbf{hi}}^{(\mathbf{j})},{\mathbf{b}}_{\mathbf{lo}}^{(\mathbf{j})}⟩]U\end{array}$$

• 验证者发出一个随机挑战 $u_j$；
• 证明者使用 $u_j$ 来压缩 ${\mathbf{a}}^{(j)}$ 的下半部分和上半部分，从而产生一个长度为原来一半的新向量 $${\mathbf{a}}^{(j-1)}={\mathbf{a}}_{\mathbf{hi}}^{(\mathbf{j})}+{\mathbf{a}}_{\mathbf{lo}}^{(\mathbf{j})}\cdot u_j^{-1}.$$ 向量 ${\mathbf{G}}^{(j)}$ 和 ${\mathbf{b}}^{(j)}$ 被类似地压缩以给出 ${\mathbf{G}}^{(j-1)}$ 和 ${\mathbf{b}}^{(j-1)}$（使用 $u_j$ 而不是 $u_j^{-1}$）。
• ${\mathbf{a}}^{(j-1)}$、${\mathbf{G}}^{(j-1)}$ 和 ${\mathbf{b}}^{(j-1)}$ 被输入到下一轮 $j-1.$

注意在最后一轮 $j=1$ 结束时，我们剩下 $a:={\mathbf{a}}^{(0)}$、$G:={\mathbf{G}}^{(0)}$、$b:={\mathbf{b}}^{(0)},$ 它们各自的长度都为 1。其直觉是，这些最终的标量，连同每一轮的挑战 $\{u_j\}$ 和"交叉项" $\{L_j,R_j\}$，编码了每一轮中的压缩。由于证明者事先并不知道挑战 $U,\{u_j\}$，他们将无法操纵各轮的压缩。因此，对这些最终项检查一个约束，应当能强制保证压缩是正确执行的，并且原始的 $\mathbf{a}$ 在经历压缩之前满足该关系。

注意 $G,b$ 只是公开已知的 $\mathbf{G},\mathbf{b}$ 的重新排列，其中混入了各轮挑战 $\{u_j\}$：这意味着验证者可以独立地计算 $G,b$，并验证证明者提供的是同样的值。