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

证明系统(Proving system)

Halo 2 的证明系统可以分解为五个阶段:

对编码电路主要组成部分的多项式做承诺(commit):
- 单元格赋值(cell assignment)。
- 每个查表论证(lookup argument)的置换值(permuted value)与乘积(product)。
- 等式约束置换(equality constraint permutation)。
构造消失论证(vanishing argument),以将所有电路关系约束为零:
- 标准门(standard gate)与自定义门(custom gate)。
- 查表论证规则。
- 等式约束置换规则。
在所有必要的点上对上述多项式求值:
- 所有列上、所有自定义门所用的相对旋转(relative rotation)。
- 消失论证的各个分片。
构造多点打开论证(multipoint opening argument),以检查所有求值与各自的承诺保持一致。
运行内积论证(inner product argument),为多点打开论证的多项式创建一个多项式承诺打开证明(polynomial commitment opening proof)。

本章接下来将依次介绍这些阶段。

示例

为了便于讲解,我们有时会引用如下示例约束系统(constraint system):

四个建议列(advice column) $a, b, c, d$ 。
一个固定列(fixed column) $f$ 。
三个自定义门:
- $a \cdot b \cdot c_{- 1} - d = 0$
- $f_{- 1} \cdot c = 0$
- $f \cdot d \cdot a = 0$

下表对 Halo 2 协议给出一个(可能过于)简洁的描述。这一描述很可能会被 Halo 2 论文及其安全性证明所取代,但目前可作为接下来各小节内容的摘要。

Prover(证明者)		Verifier(验证者)
	$\leftarrow$	$t (X) = (X^{n} - 1)$
	$\leftarrow$	$F = [F_{0}, F_{1}, \dots, F_{m - 1}]$
$A = [A_{0}, A_{1}, \dots, A_{m - 1}]$	$\to$
	$\leftarrow$	$θ$
$L = [(A_{0}^{'}, S_{0}^{'}), \dots, (A_{m - 1}^{'}, S_{m - 1}^{'})]$	$\to$
	$\leftarrow$	$β, γ$
$Z_{P} = [Z_{P, 0}, Z_{P, 1}, \dots]$	$\to$
$Z_{L} = [Z_{L, 0}, Z_{L, 1}, \dots]$	$\to$
	$\leftarrow$	$y$
$h (X) = \frac{gate _{0} ( X ) + \dots + y ^{i} \cdot gate _{i} ( X )}{t ( X )}$
$h (X) = h_{0} (X) + \dots + X^{n (d - 1)} h_{d - 1} (X)$
$H = [H_{0}, H_{1}, \dots, H_{d - 1}]$	$\to$
	$\leftarrow$	$x$
$e v a l s = [A_{0} (x), \dots, H_{d - 1} (x)]$	$\to$
		检查 $h (x)$
	$\leftarrow$	$x_{1}, x_{2}$
构造多点打开多项式 $h^{'} (X)$
$U = Commit (h^{'} (X))$	$\to$
	$\leftarrow$	$x_{3}$
$q_{evals} = [Q_{0} (x_{3}), Q_{1} (x_{3}), \dots]$	$\to$
$u_{eval} = U (x_{3})$	$\to$
	$\leftarrow$	$x_{4}$

然后证明者与验证者:

TODO:撰写提供零知识(zero-knowledge)的协议组件。