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

电路承诺(Circuit commitments)

对电路赋值做承诺

在证明创建之初,证明者持有一张单元格赋值表,它声称这些赋值满足约束系统。该表有 $n=2^k$ 行,并被划分为建议(advice)列、实例(instance)列和固定(fixed)列。我们定义 $F_{i,j}$ 为第 $i$ 个固定列第 $j$ 行的赋值。不失一般性,我们类似地定义 $A_{i,j}$ 来表示建议列和实例列的赋值。

我们在这里把固定列单独区分出来,因为它们由验证者提供,而建议列和实例列由证明者提供。在实践中,对实例列和固定列的承诺由证明者和验证者双方各自计算,只有建议列的承诺被存入证明中。

为了对这些赋值做承诺,我们在一个大小为 $n$ 的求值域(evaluation domain)上,为每一列构造次数为 $n-1$ 的拉格朗日多项式(其中 $\omega$ 是第 $n$ 个本原单位根,primitive root of unity):

• $a_i(X)$ 插值得到 $a_i({\omega }^j)=A_{i,j}$。
• $f_i(X)$ 插值得到 $f_i({\omega }^j)=F_{i,j}$。

然后,我们对每一列的多项式创建一个盲化承诺(blinding commitment):

$$\mathbf{A}=[\text{Commit}(a_0(X)),\dots ,\text{Commit}(a_i(X))]$$ $$\mathbf{F}=[\text{Commit}(f_0(X)),\dots ,\text{Commit}(f_i(X))]$$

$\mathbf{F}$ 作为密钥生成(key generation)的一部分构造,使用值为 $1$ 的盲化因子(blinding factor)。$\mathbf{A}$ 由证明者构造并发送给验证者。

对查表置换做承诺

验证者首先采样 $\theta$,它用于保持查表内部各个列彼此独立。然后,证明者按如下方式对每个查表的置换做承诺:

• 给定一个查表,其输入列多项式为 $[A_0(X),\dots ,A_{m-1}(X)]$,表列多项式为 $[S_0(X),\dots ,S_{m-1}(X)]$,证明者构造两个压缩多项式

  $$A_{\text{compressed}}(X)={\theta }^{m-1}{A}_0(X)+{\theta }^{m-2}{A}_1(X)+\cdots +\theta A_{m-2}(X)+A_{m-1}(X)$$ $$S_{\text{compressed}}(X)={\theta }^{m-1}{S}_0(X)+{\theta }^{m-2}{S}_1(X)+\cdots +\theta S_{m-2}(X)+S_{m-1}(X)$$

• 然后证明者按照查表论证的规则对 $A_{\text{compressed}}(X)$ 和 $S_{\text{compressed}}(X)$ 做置换,得到 $A^{\prime }(X)$ 和 $S^{\prime }(X)$。

证明者为所有查表创建盲化承诺

$$\mathbf{L}=\left[(\text{Commit}(A^{\prime }(X))),\text{Commit}(S^{\prime }(X))),\dots \right]$$

并将它们发送给验证者。

在验证者收到 $\mathbf{A}$、$\mathbf{F}$ 和 $\mathbf{L}$ 之后,它采样挑战 $\beta$ 和 $\gamma$,这两个挑战将用于置换论证以及下文中查表论证的剩余部分。(由于这些论证彼此独立,这些挑战可以复用。)

对等式约束置换做承诺

设 $c$ 为启用了等式约束的列数。

设 $m$ 为在不超过 PLONK 配置的最大约束次数的前提下,一个列集所能容纳的最大列数。

设 $u$ 为置换论证一节中定义的"可用"行数。

设 $b=\mathsf{ceiling}(c/m).$

证明者构造一个长度为 $bu$ 的向量 $\mathbf{P}$,使得对每个列集 $0\le a<b$ 和每一行 $0\le j<u$,

$${\mathbf{P}}_{au+j}=\prod _{i=am}^{\min (c,(a+1)m)-1}\frac{v_i({\omega }^j)+\beta \cdot {\delta }^i\cdot {\omega }^j+\gamma }{v_i({\omega }^j)+\beta \cdot s_i({\omega }^j)+\gamma }.$$

然后,证明者从 $1$ 开始计算 $\mathbf{P}$ 的连续乘积(running product),并按照置换论证一节所述,得到一个多项式向量 $Z_{P,\mathrm{0..}b-1}$,其中每个多项式的拉格朗日基表示对应于该连续乘积的一个大小为 $u$ 的切片。

证明者对每个 $Z_{P,a}$ 多项式创建盲化承诺:

$${\mathbf{Z}}_{\mathbf{P}}=\left[\text{Commit}(Z_{P,0}(X)),\dots ,\text{Commit}(Z_{P,b-1}(X))\right]$$

并将它们发送给验证者。

对查表置换乘积列做承诺

除了对各个置换后的查表做承诺之外,对于每个查表,证明者还需要对置换乘积列做承诺:

• 证明者构造一个向量 $P$:

$$P_j=\frac{(A_{\text{compressed}}({\omega }^j)+\beta )(S_{\text{compressed}}({\omega }^j)+\gamma )}{(A^{\prime }({\omega }^j)+\beta )(S^{\prime }({\omega }^j)+\gamma )}$$

• 证明者构造一个多项式 $Z_L$,其拉格朗日基表示对应于 $P$ 的连续乘积,从 $Z_L(1)=1$ 开始。

$\beta$ 和 $\gamma$ 用于组合关于 $A^{\prime }(X)$ 和 $S^{\prime }(X)$ 的置换论证,同时保持它们彼此独立。这里重要的一点是:验证者在证明者已创建 $\mathbf{A}$、$\mathbf{F}$ 和 $\mathbf{L}$(从而已对查表列中用到的所有单元格值、以及每个查表的 $A^{\prime }(X)$ 和 $S^{\prime }(X)$ 做出承诺)之后,才采样 $\beta$ 和 $\gamma$。

与之前一样,证明者对每个 $Z_L$ 多项式创建盲化承诺:

$${\mathbf{Z}}_{\mathbf{L}}=\left[\text{Commit}(Z_L(X)),\dots \right]$$

并将它们发送给验证者。