证明系统

Halo2的证明系统可以分解成五个部分：

这些部分依次在本章节讲解。

举个例子

为了辅助我们的解释，我们时不时地用如下的约束系统：

四个advice列 $a, b, c, d$
一个fixed列 $f$
三个自定义门：
- $a \cdot b \cdot c_{- 1} - d = 0$
- $f_{- 1} \cdot c = 0$
- $f \cdot d \cdot a = 0$

Halo2协议的简洁描述整理在如下的表格中。这部分会被Halo2的论文和安全性证明替代，目前作为后面子章节的总结：

证明者		验证者
	$\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}$

Then the prover and verifier:

Construct $finalPoly (X)$ as a linear combination of $Q$ and $U$ using powers of $x_{4}$ ;
Construct $finalPolyEval$ as the equivalent linear combination of $q_{evals}$ and $u_{eval}$ ; and
Perform $InnerProduct (finalPoly (X), x_{3}, finalPolyEval) .$

TODO: Write up protocol components that provide zero-knowledge.