想研究零知识证明能不能进一步压缩、加速，首先得熟悉现在的实现方法。

然后一查发现零知识证明的技术基础有一点丰富。

参考教程：https://learnblockchain.cn/column/117

1 前置准备

1.0 数学知识

参考这篇文章：BLS、BBS、BBS+与其数学基础

或者参考教程的前几章。

1.1 将解决方案变成布尔表达式

所有密码学算法（NP难问题）都有一个共通的特点：解决问题困难、验证答案简单。

所以期待能有一种通用的语言来描述NP问题和解决方案。

Cook-Levin 定理：所有的P类问题和NP类问题都可以表示为一个布尔表达式。

直观理解：任何问题都能翻译成一堆二进制状态 + 状态变换规则，而这些规则最后都能被写成布尔公式。

布尔表达式就是一个典型的求解困难、验证简单的问题。

1.2 算数电路

布尔电路：仅限于布尔输入（True、False）和基本的布尔运算（与、或、非）。

但是，用布尔电路表达加法这类算数运算就会非常冗长。比如三个4bit的整数相加 $a+b=c$ 写成布尔表达式：

((a₄ ∧ b₄ ∧ c₄) ∨ (¬a₄ ∧ ¬b₄ ∧ c₄) ∨ (¬a₄ ∧ b₄ ∧ ¬c₄) ∨ (a₄ ∧ ¬b₄ ∧ ¬c₄)) ∧

((a₃ ∧ b₃ ∧ ((a₂ ∧ b₂) ∨ (b₂ ∧ (a₁ ∧ b₁) ∨ (b₁ ∧ c₀) ∨ (a₁ ∧ c₀)))) ∨
 (¬a₃ ∧ ¬b₃ ∧ ((a₂ ∧ b₂) ∨ (b₂ ∧ (a₁ ∧ b₁) ∨ (b₁ ∧ c₀) ∨ (a₁ ∧ c₀)))) ∨
 (¬a₃ ∧ b₃ ∧ ¬((a₂ ∧ b₂) ∨ (b₂ ∧ (a₁ ∧ b₁) ∨ (b₁ ∧ c₀) ∨ (a₁ ∧ c₀)))) ∨
 (a₃ ∧ ¬b₃ ∧ ¬((a₂ ∧ b₂) ∨ (b₂ ∧ (a₁ ∧ b₁) ∨ (b₁ ∧ c₀) ∨ (a₁ ∧ c₀))))) ∧

((a₂ ∧ b₂ ∧ ((a₁ ∧ b₁) ∨ (b₁ ∧ c₀) ∨ (a₁ ∧ c₀))) ∨
 (¬a₂ ∧ ¬b₂ ∧ ((a₁ ∧ b₁) ∨ (b₁ ∧ c₀) ∨ (a₁ ∧ c₀))) ∨
 (¬a₂ ∧ b₂ ∧ ¬((a₁ ∧ b₁) ∨ (b₁ ∧ c₀) ∨ (a₁ ∧ c₀)))) ∨
 (a₂ ∧ ¬b₂ ∧ ¬((a₁ ∧ b₁) ∨ (b₁ ∧ c₀) ∨ (a₁ ∧ c₀))))) ∧

((a₁ ∧ b₁ ∧ c₀) ∨ (¬a₁ ∧ ¬b₁ ∧ c₀) ∨ (¬a₁ ∧ b₁ ∧ ¬c₀) ∨ (a₁ ∧ ¬b₁ ∧ ¬c₀)) ∧

((a₀ ∧ b₀ ∧ c₀) ∨ (¬a₀ ∧ ¬b₀ ∧ c₀) ∨ (¬a₀ ∧ b₀ ∧ ¬c₀) ∨ (a₀ ∧ ¬b₀ ∧ ¬c₀)) ∧

¬ ((a₄ ∧ b₄) ∨
     (b₄ ∧ (a₃ ∧ b₃) ∨ (b₃ ∧ (a₂ ∧ b₂) ∨ (b₂ ∧ (a₁ ∧ b₁) ∨ (b₁ ∧ c₀) ∨ (a₁ ∧ c₀))) ∨
     (a₃ ∧ (a₂ ∧ b₂) ∨ (b₂ ∧ (a₁ ∧ b₁) ∨ (b₁ ∧ c₀) ∨ (a₁ ∧ c₀))))

这显然把一个常用的运算写成了过于复杂的形式，并且3个变量却又12个输入。因此考虑能否用另一种方式等价表示电路。

算数电路：算术电路是一个仅使用加法、乘法和相等的方程系统。例如：

6 = x₁ + x₂
9 = x₁x₂

我们说布尔电路是满足的，如果我们对输入变量有一个赋值，使输出为真。类似地，算术电路是满足的，如果可以对变量赋值，使所有的方程均成立。

例如，上述电路由 x1=3,x2=3x1=3,x2=3 满足，因为电路中的两个方程都成立。相反，电路由 x₁ = 1, x₂ = 6 不满足，因为方程 9 = x₁x₂ 不为真。

与布尔电路一样，它检查所提出的输入集合是否有效，但不计算解决方案。

可以证明，算数电路和布尔电路是等效的。

简单来说，与或非三个布尔运算都可以通过加法和乘法表示，并且可以约束输入为0或1。

1.2.1 记号

算术电路中的变量被称为信号（Signal）。

=== 运算符表示相等。电路中，相等并非赋值，而是检查。可以等价理解成断言 assertEq(a, b)。

见证：一个让电路成立的解。例如，考虑以下电路：

x₁(x₁ - 1) === 0
x₁x₂ === x₁

以下对 (x₁, x₂) 的赋值都是有效的见证：

(x1,x2)=(1,1)
(x1,x2)=(0,2)
(x1,x2)=(0,1337)
(x1,x2)=(0,404)

1.2.2 对比布尔电路

下表显示布尔电路和算术电路之间的区别，但请牢记，它们服务于相同的目的：验证见证。

布尔电路	算术电路
变量为0, 1	信号为数字
唯一的运算是AND, OR, NOT	唯一的运算是加法和乘法
当输出为真时满足	当所有方程的左侧等于右侧时满足（没有输出）
见证是使布尔电路满足的布尔变量的赋值	见证是使所有相等约束满足的信号赋值

2 Rank 1 Constraint System(R1CS)

这一节讲的是一种算数电路的约束。

可以回想一下数据库、编译原理里的各种约束。

就是把一个人类更易懂的表达，通过一种可以程序编码的方法，转换成一个更机器友好的形式。

R1CS是对算数运算的一种约束，要求一个等式里最多出现一次乘法。

例如：

z = 2x^2y + 3x

不满足R1CS，需要改写成等价的两个等式：

\begin{align} v_1 &= 2xx \\ z &= v_1y + 3x \end{align}

其中第二个式子可以改写成 $z - 3x = v_1y$ ，改写后得到：

\begin{align} v_1 &= 2xx \\ z - 3x&= v_1y \end{align}

将算数运算改写成符合R1CS约束的形式，是为了后续更方便的生成电路。

每个等式都形如：

多项式 \times 多项式 = 多项式

由一系列等式组成的方程组，可以用线性代数抽象，得到矩阵形式的表达：

\textbf{O} \, \mathbf{a} = (\textbf{L} \, \mathbf{a}) \circ (\textbf{R} \, \mathbf{a})

其中， $\mathbf{a}$ 为见证向量（即输入的所有信号），运算 $\circ$ 表示逐元素相乘。在上述例子中：

\mathbf{a} = \begin{bmatrix}1\\ x\\ y \\ v_1 \\z\end{bmatrix}

约定第一个元素是 $1$ 用来表示常量运算。同理可以写出对应的系数：

\begin{align} \textbf{O} &= \begin{bmatrix} 0 &0 &0 &1 &0 \\ 0 &-3 &0 &0 &1 \end{bmatrix} \\ \textbf{L} &= \begin{bmatrix} 0 &2 &0 &0 &0 \\ 0 &0 &0 &1 &0 \end{bmatrix} \\ \textbf{R} &= \begin{bmatrix} 0 &1 &0 &0 &0 \\ 0 &0 &1 &0 &0 \end{bmatrix} \\ \end{align}

最终，任意复杂的算数电路，都可以转换成符合R1CS约束的形式，变成4个向量的运算。

3 二次算数程序（QAP）

3.1 目的

R1CS 左右两侧的结果是一个向量：

\textbf{O} \, \mathbf{a} = (\textbf{L} \, \mathbf{a}) \circ (\textbf{R} \, \mathbf{a})

假设现在有 3 个约束，见证向量 4 维，展开：

\begin{bmatrix} O_{11} & O_{12} & O_{13} & O_{14} \\ O_{21} & O_{22} & O_{23} & O_{24} \\ O_{31} & O_{32} & O_{33} & O_{34} \end{bmatrix} \begin{bmatrix} 1 \\ a_1 \\ a_2 \\ a_3 \end{bmatrix} = \begin{bmatrix} L_{11} & L_{12} & L_{13} & L_{14} \\ L_{21} & L_{22} & L_{23} & L_{24} \\ L_{31} & L_{32} & L_{33} & L_{34} \end{bmatrix} \begin{bmatrix} 1 \\ a_1 \\ a_2 \\ a_3 \end{bmatrix} \circ \begin{bmatrix} R_{11} & R_{12} & R_{13} & R_{14} \\ R_{21} & R_{22} & R_{23} & R_{24} \\ R_{31} & R_{32} & R_{33} & R_{34} \end{bmatrix} \begin{bmatrix} 1 \\ a_1 \\ a_2 \\ a_3 \end{bmatrix}

其中 $\circ$ 表示逐元素相乘。

可见等式两边最终的结果是 4 维的向量。

要比较两个 n 维向量是否相等，最朴素的方法就是遍历，逐个对比。

因此，R1CS 验证需要遍历所有约束，时间复杂度是 $\mathcal{O}(n)$ 。

如果见证向量维度很大，验证的时间成本就会很高。

有没有方法快速验证？

3.2 Schwatz-Zippel引理

Schwatz-Zippel引理：如果有两个多项式 $p(x)$ 和 $q(x)$ ，他们的次数分别为 $d_p$ 和 $d_q$ ，并且 $p(x) \ne q(x)$ ，那么 $p(x)$ 与 $q(x)$ 的交点数量**小于等于 ** $\max(d_p, d_q)$ 。

该引理对于有限域中的多项式也成立。

这个引理其实挺符合直觉的，但是有什么用？举个例子：判断两个多项式是否相等。

理论上，我们得判断两个多项式的每个系数，时间复杂度是 $\mathcal{O}(d)$ 。

但是，在一个比较大的有限域上，随机取一个点，他们相交的概率非常小。几乎就可以通过随机取点以 $\mathcal{O}(1)$ 的时间复杂度判断。

进一步延伸：判断多项式相等→判断两个向量是否相等。

向量可以转换成多项式。

转换的方法有：

直接把向量的值当做多项式的系数
拉格朗日差值

虽然转换和计算这个多项式仍然需要很多时间，但是验证者可以高速验证。

QAP里采用的转换方式是拉格朗日差值，为什么不直接把向量当做系数？

主要原因：拉格朗日插值具有同态性。

把向量当做系数构造的多项式，我不能预先知道这个多项式会通过哪些点。拉格朗日差值构造的多项式，我可以保证当 x = i 时，多项式的结果是向量的第 i 个值

3.3 方法

将 R1CS 中的系数矩阵纵向拆分，每一列用拉格朗日差值得到一个多项式：

\mathbf{L} = \underbrace{\begin{bmatrix} l_{11}\\ l_{12}\\ l_{13}\\ l_{14} \end{bmatrix}}_{u_1(x)} \quad \underbrace{\begin{bmatrix} l_{21}\\ l_{22}\\ l_{23}\\ l_{24} \end{bmatrix}}_{u_2(x)} \quad \underbrace{\begin{bmatrix} l_{31}\\ l_{32}\\ l_{33}\\ l_{34} \end{bmatrix}}_{u_3(x)} \quad \underbrace{\begin{bmatrix} l_{41}\\ l_{42}\\ l_{43}\\ l_{44} \end{bmatrix}}_{u_4(x)} \\ \mathbf{R} = \underbrace{\begin{bmatrix} r_{11}\\ r_{12}\\ r_{13}\\ r_{14} \end{bmatrix}}_{v_1(x)} \quad \underbrace{\begin{bmatrix} r_{21}\\ r_{22}\\ r_{23}\\ r_{24} \end{bmatrix}}_{v_2(x)} \quad \underbrace{\begin{bmatrix} r_{31}\\ r_{32}\\ r_{33}\\ r_{34} \end{bmatrix}}_{v_3(x)} \quad \underbrace{\begin{bmatrix} r_{41}\\ r_{42}\\ r_{43}\\ r_{44} \end{bmatrix}}_{v_4(x)} \\ \mathbf{O} = \underbrace{\begin{bmatrix} o_{11}\\ o_{12}\\ o_{13}\\ o_{14} \end{bmatrix}}_{w_1(x)} \quad \underbrace{\begin{bmatrix} o_{21}\\ o_{22}\\ o_{23}\\ o_{24} \end{bmatrix}}_{w_2(x)} \quad \underbrace{\begin{bmatrix} o_{31}\\ o_{32}\\ o_{33}\\ o_{34} \end{bmatrix}}_{w_3(x)} \quad \underbrace{\begin{bmatrix} o_{41}\\ o_{42}\\ o_{43}\\ o_{44} \end{bmatrix}}_{w_4(x)}

每个矩阵向量乘积 $\textbf{La} ~ \textbf{Ra} ~ \textbf{Wa}$ 的同态等价于以下多项式：

\sum_{i=1}^{4} a_i u_i(x) = a_1 u_1(x) + a_2 u_2(x) + a_3 u_3(x) + a_4 u_4(x) = u(x) \\ \sum_{i=1}^{m} a_i v_i(x) = a_1 v_1(x) + a_2 v_2(x) + a_3 v_3(x) + a_4 v_4(x) = v(x) \\ \sum_{i=1}^{m} a_i w_i(x) = a_1 w_1(x) + a_2 w_2(x) + a_3 w_3(x) + a_4 w_4(x) = w(x)