零知识证明：深入理解理解 QAP

本文记录我对著名的 Quadratic Arithmetic Programs: from Zero to Hero | by Vitalik Buterin | Medium 的理解。但已经按照更容易理解的思路重写，并且增加了诸多更为深入的内容。

这篇文章会介绍如何将一个命题转换为电路（或者说分解到每个操作的子问题），然后构建 R1CS 约束系统（或者说一系列的等式约束），进一步转换为 QAP（或者说一个能同时实现这些约束的多项式），最后构建一个简单的证明系统。

引入

先理解我们要解决什么问题。

比如，你想证明对于一个很复杂的函数 $f(a,b,c,d)$ ，当函数值为 $42$ 时，你真的知道一个解是 $*(a,b,c,d)=(8,8,4,8)$ . 并且这个问题计算需要花费大量的时间（得解一个复杂的方程，可能需要指数级别的时间），而验证这个问题只需要很快的时间（比如只需要对数级别的时间）。而你，需要给别人验证的机会，证明你知道答案并且你的答案是对的，但你不需要给出你答案。

这种场景，零知识证明就会发挥作用。你就是 Prover，证明者，要证明你知道答案。别人会挑战你，和你交谈，从而确认你真的知道答案，这些人就是 Verifier。

实现零知识证明有很多方案，我们这次需要理解一种叫 QAP 的方法。

让我们用更有条理的方式梳理 QAP 方法：

以下输入给 Prover：

一个需要证明的程序。一个命题。或者一个计算任务。反正都可以抽象为一个数学命题。
一些证明过程用到的秘密。你不想泄露的知识。比如答案。

输出：

证明。证明是一个数学对象，能够让 Verifier 验证你确实知道秘密，但不会泄露任何关于秘密的知识。换句话说，不会为 Verifier 自己计算出秘密降低任何一丝计算量。

然后这个输出再输入给 Verifier。

Verifier 输出：

一个验证结果，接受或拒绝。

为了理解容易，以经典例题， $x^3+x+5=35$ 为例，看看如何零知识地证明 Prover 知道 $x=3$ 是方程的解。这个过程会比较漫长，我会做最细致的分解，帮助自己，以及可能的读者理解，以及重理解。

从源程序到代数电路（Computation to Circuit）

输入：

1def qeval(x):
2    y = x**3
3    return x + y + 5

输出：

一个“电路”。其实就是一种汇编语句，或者硬件描述语言。

1sym_1 = x * x
2y = sym_1 * x  
3sym_2 = y + x  
4~out = sym_2 + 5

它相当于把输入按照编译器编译的方式展平。这很好理解。这一步的目的就是把复杂的程序简单化，变成简单指令的集合。或者说分解为电路的简单连接。

从代数电路到一阶约束系统（Circuit to R1CS）

R1CS（Rank-1 Constraint System）是由三个向量构成的向量组，分别是 $\vec{a}$ 、 $\vec{b}$ 和 $\vec{c}$ 。解向量 $\vec{s}$ 满足以下约束条件： $(\vec{s} \cdot \vec{a}) \cdot (\vec{s} \cdot \vec{b}) - (\vec{s} \cdot \vec{c}) = 0$ ，其中 $\cdot$ 表示向量内积， $\cdot$ 表示算数乘法。 $\vec{s}$ 表示方程的

解。

电路虽然很简单了，但它却是线性执行的。所以我们为了提高验证效率，就必须把它转换成向量运算。所以 R1CS 出现的目的很明确，把电路的约束转换成上面这个向量运算约束。

这个转换必须不损失任何信息量。方法是这样的：

首先，把所有中间变量编号，从 0 开始。

变量名	位置
~one	0
x	1
~out	2
sym_1	3
y	4
sym_2	5

其中这里我们引入一个虚拟变量（dummy variable）叫做 ~one，这样我们就可以表示 1.

然后就是构造向量 $\vec{a},\vec{b},\vec{c}$ 。实际上，对于赋值语句 c = a op b，我们只需要把对应位置标 1，即可生成对应的向量

对于 sym_1 = x * x，第一个 x 对应位置是 1，得到对应向量 $\vec{a} = [0,1,0,0,0,0]$ . 第二个也一样。

可以结合我画的图理解：

1dde5c0b38314aa7403da4eef7ec2610.png

据此继续算出各个电路成分对应的向量：

sym_1 = x * x
a = [0, 1, 0, 0, 0, 0]  
b = [0, 1, 0, 0, 0, 0]  
c = [0, 0, 0, 1, 0, 0]

y = sym_1 * x  
a = [0, 0, 0, 1, 0, 0]  
b = [0, 1, 0, 0, 0, 0]  
c = [0, 0, 0, 0, 1, 0]

sym_2 = y + x  
a = [0, 1, 0, 0, 1, 0]  
b = [1, 0, 0, 0, 0, 0]  
c = [0, 0, 0, 0, 0, 1]


~out = sym_2 + 5
a = [5, 0, 0, 0, 0, 1]  
b = [1, 0, 0, 0, 0, 0]  
c = [0, 0, 1, 0, 0, 0]

如果你真的动手算了，就会发现 sym_2 = y + x 实际上要处理成 sym_2 = (y + x) * 1。这是因为约束必须是两个因式相乘，那么只能把 y + x 看作一个因式。这也就是引入 ~one 的原因。

最后就是 $\vec{s}$ ，它是所有的变量值：

[1, 3, 35, 9, 27, 30]

计算过程是这样的，首先代入解 $x=3$ ，以及特殊值 ~one=1：

变量名	位置	value
~one	0	1
x	1	3
~out	2
sym_1	3
y	4
sym_2	5

接下来，根据给定的规则计算并填充 “value” 列：

sym_1 = x x = 3 3 = 9
y = sym_1 x = 9 3 = 27
sym_2 = y + x = 27 + 3 = 30
~out = sym_2 + 5 = 30 + 5 = 35

更新后的表格如下：

变量名	位置	value
~one	0	1
x	1	3
~out	2	35
sym_1	3	9
y	4	27
sym_2	5	30

对应的向量就是 $\vec{s}=[1, 3, 35, 9, 27, 30]$

再加上矩阵 A:


$$
  
A = \begin{bmatrix}  
0 & 1 & 0 & 0 & 0 & 0 \\
0 & 0 & 0 & 1 & 0 & 0 \\  
0 & 1 & 0 & 0 & 1 & 0 \\
5 & 0 & 0 & 0 & 0 & 1 \\
\end{bmatrix}  
$$

矩阵 B:


$$
  
B = \begin{bmatrix}  
0 & 1 & 0 & 0 & 0 & 0 \\
0 & 1 & 0 & 0 & 0 & 0 \\
1 & 0 & 0 & 0 & 0 & 0 \\
1 & 0 & 0 & 0 & 0 & 0 \\
\end{bmatrix}  
$$

矩阵 C:


$$
  
C = \begin{bmatrix}  
0 & 0 & 0 & 1 & 0 & 0 \\
0 & 0 & 0 & 0 & 1 & 0 \\
0 & 0 & 0 & 0 & 0 & 1 \\
0 & 0 & 1 & 0 & 0 & 0 \\
\end{bmatrix}  
$$

对于矩阵的每一行 $i$ ，成立：


$$
(A_{i}\cdot \vec{s})\cdot(B_{i}\cdot \vec{s}) - (C_{i}\cdot \vec{s}) = 0
$$

这就构成了 R1CS.

从 R1CS 到 QAP（R1CS to QAP）

下面这一步有一定跳跃性。我当时并不理解为什么要做，以及可以做这样的转换。下面是我思考后的答案：

R1CS 到 QAP 这一步，本质上就是把基于矩阵运算的约束，转换成关于多项式的约束。目的在于：

保持约束：这样的转换可以在不损失信息量的前提下保持约束
提高效率：转换后，稀疏的大矩阵运算变成了简单的多项式运算，提高了验证效率。

所以问题化为如何完成这样的转换。思考多项式的性质，多项式可以看成是空间中的曲线，因此点在曲线上就是满足约束。

因此问题进一步转换为如何找到一条曲线，满足和 R1CS 等价的约束。后者其实就是关于解 $\vec{s}$ 的方程，如果解正确，则满足约束，如果给出一个错误的解，那么 R1CS 等式不成立，对应于曲线就是点不在曲线上。

而因为 Prover 知道真实解 $\vec{s}$ ，所以它有能力直接根据 R1CS 计算出曲线上的一些点。

因此现在的问题就是：

如何找到这些曲线上的点。
如何根据曲线上的一些点，求解出曲线的解析式。这个问题就很经典了，是多项式插值问题。

如何找到插值点

对于上述 R1CS，首先计算 $\vec{s}$ 的转置矩阵：


$$
\vec{s}^T =
\begin{bmatrix}
1 \\
3 \\
35 \\
9 \\
27 \\
30 \\
\end{bmatrix}
$$

注意到 R1CS 约束等价于：


$$
A s^T\odot Bs^T=Cs^T
$$

其中矩阵与 $s^T$ 的乘积使用矩阵乘法， $\odot$ 表示 Hadamard 乘积（逐项乘积）。

实际上也可以具体计算验证，会发现：


$$

\begin{align*}

A \vec{s}^T = \begin{bmatrix} 3 \\ 9 \\ 30 \\ 35 \end{bmatrix} \quad

B \vec{s}^T = \begin{bmatrix} 3 \\ 3 \\ 1 \\ 1 \end{bmatrix} \quad

C \vec{s}^T = \begin{bmatrix} 9 \\ 27 \\ 30 \\ 35 \end{bmatrix}

\end{align*}

$$

可以验证。

那么，如果 A 中每个元素可以用 $A_{j}(x)$ 这个多项式表示（其中 $j$ 表示第 $j$ 列， $x$ 表示第 $x$ 行，也即对第 $x$ 个表达式的约束）。


$$

A = \begin{bmatrix}

A_{1}(1) & A_{2}(1) & A_{3}(1) & A_{4}(1) & A_{5}(1) & A_{6}(1) \\

A_{1}(2) & A_{2}(2) & A_{3}(2) & A_{4}(2) & A_{5}(2) & A_{6}(2) \\

A_{1}(3) & A_{2}(3) & A_{3}(3) & A_{4}(3) & A_{5}(3) & A_{6}(3) \\

A_{1}(4) & A_{2}(4) & A_{3}(4) & A_{4}(4) & A_{5}(4) & A_{6}(4) \\

\end{bmatrix}

$$

由于 $A_{j}(x)$ 代表列向量， $B$ 、 $C$ 同理，采取相同的操作。


$$

\begin{bmatrix}

A_{1}(x) \

A_{2}(x) \

\vdots \

A_{n}(x)

\end{bmatrix} \odot

\begin{bmatrix}

B_{1}(x) \

B_{2}(x) \

\vdots \

B_{n}(x)

\end{bmatrix} =

\begin{bmatrix}

C_{1}(x) \

C_{2}(x) \

\vdots \

C_{n}(x)

\end{bmatrix}

$$

展开等式后，我们可以得到以下逐个分量的等式：


$$

\begin{align*}

A_{1}(x)B_{1}(x) &= C_{1}(x) \\

A_{2}(x)B_{2}(x) &= C_{2}(x) \\

&\vdots \\

A_{n}(x)B_{n}(x) &= C_{n}(x)

\end{align*}

$$

给定等式 $As^T\odot Bs^T = Cs^T$ ，考虑到可加性，我们可以表示其加和为：


$$

\sum_{j=1}^{n} (A_{j}(x)B_{j}(x)) - \sum_{j=1}^{n} C_{j}(x) = 0

$$

因此整个约束变成一个多项式的约束。这个约束就是 QAP 的多项式。

那么， $A_{j}(x)$ 的含义明确后，我们就可以得到插值的点。

插值的点则可以通过矩阵的坐标 $(x,j)$ 和 此坐标的值 获得，例如 $A_1(x)$ 经过 $(1,0),(2,0),(3,0),(4,5)$ 。这是因为当 $x=1$ ， $A_1(1) = 0$ 。当 $x = 4$ ， $A_{1}(4) = 5$

如何插值

就之前的例子继续， $A_1(x)$ 经过 $(1,0),(2,0),(3,0),(4,5)$ 。目标是找到一个三次多项式 $A_1(x)$ ，我们可以使用拉格朗日插值法或者牛顿插值法。

其实用哪种无所谓，因为只要 Prover 真的有 $s$ ，则多项式约束一定满足。插值的方法只决定了出错的时候错成什么样。

这里使用比较简单好懂的拉格朗日插值法。

拉格朗日插值法中，一个多项式 $A_1(x)$ 可以表示为：


$$

A_1(x) = \sum_{i=1}^{n} y_i L_i(x)

$$

其中 $n$ 是点的个数， $y_i$ 是第 $i$ 个点的 $y$ 坐标，而 $L_i(x)$ 是拉格朗日基多项式，定义为：


$$

L_i(x) = \prod_{j=1, j \neq i}^{n} \frac{x - x_j}{x_i - x_j}

$$

对于我们的情况，我们有四个点，所以 $n=4$ ，且我们的点是 $(x_1, y_1) = (1, 0)$ , $(x_2, y_2) = (2, 0)$ , $(x_3, y_3) = (3, 0)$ , $(x_4, y_4) = (4, 5)$ 。

我们可以计算出每个基多项式 $L_i(x)$ ：


$$

L_1(x) = \frac{(x - 2)(x - 3)(x - 4)}{(1 - 2)(1 - 3)(1 - 4)} = \frac{(x - 2)(x - 3)(x - 4)}{6}

$$


$$

L_2(x) = \frac{(x - 1)(x - 3)(x - 4)}{(2 - 1)(2 - 3)(2 - 4)} = \frac{(x - 1)(x - 3)(x - 4)}{-2}

$$


$$

L_3(x) = \frac{(x - 1)(x - 2)(x - 4)}{(3 - 1)(3 - 2)(3 - 4)} = \frac{(x - 1)(x - 2)(x - 4)}{2}

$$


$$

L_4(x) = \frac{(x - 1)(x - 2)(x - 3)}{(4 - 1)(4 - 2)(4 - 3)} = \frac{(x - 1)(x - 2)(x - 3)}{6}

$$

用这些基多项式和点的 $y$ 坐标来构建 $A_1(x)$ ：


$$

A_1(x) = 0 \cdot L_1(x) + 0 \cdot L_2(x) + 0 \cdot L_3(x) + 5 \cdot L_4(x)

$$


$$

A_1(x) = 5 \cdot \frac{(x - 1)(x - 2)(x - 3)}{6}

$$

简化一下：


$$

A_1(x) = \frac{5}{6}(x - 1)(x - 2)(x - 3)

$$

这就是通过这四个点的三次多项式 $A_1(x)$ 的解析式。暴力展开得到各次系数：


$$

A_1(x) = \frac{5}{6}x^3 - 5x^2 + \frac{55}{6}x - 5

$$

这完全对应于 V 神给出的 $A_{1}$ 多项式系数：

[-5.0, 9.166, -5.0, 0.833]

所以知道他怎么算出来的了吧

这样的过程还需要进行五次才能覆盖 A 的所有列。

(1,0) (1,1) (1,0) (1,0) (1,0) (1,0)
(2,0) (2,0) (2,0) (2,1) (2,0) (2,0)
(3,0) (3,1) (3,0) (3,0) (3,1) (3,0)
(4,5) (4,0) (4,0) (4,0) (4,0) (4,1)

此外还有 B、C。当然，交给计算机吧。

基于 QAP 的验证

下一个难点就是得到多项式之后，怎么应用到零知识证明中。我们知道零知识证明需要一个多项式 $p(x)$ ，且可进行因式分解：

$p(x) = h(x) t(x)$ ，其中 $t(x)$ 叫做目标多项式，是一系列零点乘积 $t(x) = (x-z_{0})(x-x_{1}) \dots$

这些零点是 Prover 和 Verifier 都知道的，但方程的解只有 Prover 知道。Verifier 只负责验证 $p(s)$ 是否整除 $t(s)$ 。

在本例中，存在以下对应关系：

$t(x)=(x - 1)(x - 2) (x - 3) (x - 4)$ ，它对应于电路在 1、2、3、4 点等于0。
$p(x)$ 就是上面提到的多项式约束，它在 $x$ 正确时为 $0$
$h(x)$ 基于上面两个算出来。这个计算过程由 Prover 执行。

对于第一点，读者可能会感觉到跳跃性，那我们回顾公式：


$$

\sum_{j=1}^{n} (A_{j}(x)B_{j}(x)) - \sum_{j=1}^{n} C_{j}(x) = 0

$$

注意到对于任意 $x$ ，此算是总是成立，而 $x$ 的定义域是 $\{ 1,2,3,4 \}$ 。所以我们可以断定 $\forall x_{0} \in {1,2,3,4}$ ， $x_{0}$ 是 $p(x)$ 的一个零点。

或者从直观上理解，这意味着对于 $x=3$ 为例，四个元件中除了第三个都会被消去，此时第三个电路成立。

一个常识是，经过某几个零点的多项式必须是按这几个零点因式分解式的整数倍。例如 $f(x)=(x^2+1)(x-1)(x-2)$ ，有零点 $x=1,x=2$ ，那么 $f(x)$ 一定是 $(x-1)(x-2)$ 的整数倍。这一点告诉我们如何验证答案是否正确。

基于 QAP 的一种交互式零知识证明

据此我们已经掌握了从源程序到 QAP 的转换。我们可以设计一套零知识证明协议。

目的：Prover 证明自己知道使程序 $x^3+x+5=35$ 成立的一个解是 $x_{0}=3$ . 但不能透露这个解给 Verifier

两方已知的信息：

1. 源程序。
2. $p(x)$ 的一些零点。这些零点是各个元件的编号，从 1 开始。知道这些信息不需要预先知道 $p(x)$ 的表达式。

再次强调，Verifier 并不知道 $p(x)$ ，换言之不知道 $p(x)$ 的系数。因为这些系数的计算依赖于知道 $\vec{s}^T$ ，后者依赖于知道解向量。


$$

	\sum_{j=1}^{n} (A_{j}(x)B_{j}(x)) - \sum_{j=1}^{n} C_{j}(x) = h(x)t(x)

$$

Prover 的事前准备：

将自己算出来的解 $x_{0}=3$ 代入程序，得到一系列中间变量值。也即前文提到的 $\vec{s}^T$
- 务必注意的是，这里的 $x_{0}$ 相关的 $x$ ，和 $p(x)$ 的 $x$ 没有关系。前者是程序的输入，后者是 R1CS/QAP 中对不同元件的编号。千万不要把 $x_{0}$ 代入 $p(x)$ ，这完全错误。
基于 $\vec{s}^T$ 向量可以得到 $p(x)$ 的表达式。
问题转换为证明 Prover 知道 $p(x)$ 的所有系数。

交互过程：

Verifier
1. 随机抽取一个数字 $r$ 。发送给 Prover
Prover
1. 计算 $p(r)$ ， $t(r)$
2. 将 $r$ 代入 $h(x) = \dfrac{p(x)}{t(x)}$ ，得到 $h(r)$
3. **如果 Prover 其实不知道 $p(x)$ ，那么大概率算出来的 $h(r)$ 会产生余项。
Verifier：
1. 验证 $p(x) = h(x) t(x)$ 满足，且 $h(x)$ 是一个整数，说明 Verifier 大概率没作弊。
重复此过程直到 Verifier 确信 Prover 没有碰运气。

这个协议可以让读者体会到 QAP 如何使用。

不过上面的交互协议太过于简陋，存在很多 Bug，并不会运用到真实世界。例如 $r$ 值泄露给了 Prover，余项可能凑巧相消等等，因此需要同态加密、双线性配对等过程，来进一步重构、加固。