title
tags
50. 线性 PCP 第一部分 R1CS
zk
computation theory
probabilistically checkable proof
linear PCP
R1CS
WTF zk 教程第 50 讲：线性 PCP 第一部分 R1CS 在上一讲中，我们介绍了概率可检验证明（PCP）的基本概念。这一讲，我们将介绍构造线性 PCP 的第一部分：R1CS。
线性 PCP（Linear PCP, LPCP）是一种特殊的 PCP 系统，它的证明是线性函数 ，而验证者可以对证明进行线性查询（查询某个位置的线性组合）来验证某个命题。
线性 PCP 的核心特征：
线性函数证明 ：证明者提供的证明是一个线性函数，也就是证明内容可以看作一个向量，每个元素是某个线性函数的结果。线性查询 ：验证者通过对证明的线性函数进行查询来获取特定信息，从而验证证明的正确性。
给定一个域 $\mathbb{F}$ 和向量 $\pi \in \mathbb{F}^{\ell}$ ，证明者提供的函数为 $f_{\pi}(x) = \langle \pi, x \rangle$ ，即 $\pi$ 与 $x$ 的内积，而验证者通过线性查询 $f_{\pi}$ 来验证证明的正确性。
一个线性 PCP 系统 $(P, V)$ 对于某个语言 $L$ 满足以下性质：
完备性（Completeness） ：对于 $x \in L$ ，存在一个证明 $\pi$ 使得验证者 $V$ 在随机选择某个 $\rho$ 后，能够正确验证证明，满足：
$$
\Pr_{\rho} \left[ V^{f_{\pi}}(x; \rho) = 1 \right] \geq 1 - \epsilon_c
$$
其中 $\epsilon_c$ 是完备性误差。
可靠性（Soundness） ：对于 $x \notin L$ ，无论证明者提供怎样的证明 $\tilde{\pi}$ ，验证者 $V$ 验证后拒绝错误证明的概率较高，满足：
$$
\Pr_{\rho} \left[ V^{f_{\tilde{\pi}}}(x; \rho) = 1 \right] \leq \epsilon_s
$$
其中 $\epsilon_s$ 是可靠性误差。
线性 PCP 是最简单的非平凡 PCP 系统，但构造它并不容易。将一个 NP 问题转换为线性 PCP 主要包含以下步骤（图中红框部分）：
电路表示 ：将 NP 问题表示为一个代数电路。R1CS 表示 ：将代数电路表示为 R1CS（Rank-1 Constraint System）。QAP 表示 ：将 R1CS 转换为 QAP（Quadratic Arithmetic Program）。线性 PCP 构造 ：利用 QAP 构造线性 PCP。
从下图可以看出，构建线性 PCP 后，我们只需要额外两步就可以构造出零知识证明系统 zkSNARK 了。这一讲，我们将介绍前 2 步，电路表示和 R1CS。
这一步，我们需要将要证明的 NP 问题转化为一个算数电路。因为 circuit SAT （电路满足性问题）是 NP 完全问题，且每个 circuit SAT 都可以转化为一个算数电路，因此所有 NP 问题都可以转化为算数电路。
我们在 WTF zk 第 46 讲 中介绍过算数电路，不熟悉的可以复习下。
我们一般用“扁平化” (flatenning)的方法进行这一步转换。它的核心思想是将复杂的计算分解成一系列简单的算术操作，每个操作只涉及基本的加法和乘法（或者它们的逆运算）。每个操作只涉及两种形式：$y = x$ 或 $z = x \square y$ ，其中 $\square$ 表示加法或乘法门，$x, y, z$ 是变量，度数限制为 1（或者是常数）。
举个例子，比如我们要证明一个方程 $y = x^3 + x + 5$ 的根为 $x = 3$ ，我们可以通过引入中间变量的方法将其扁平化：
$$
\begin{align}
v1 &= x * x \\
v2 &= v1 * x \\
v3 &= v2 + x \\
y &= v3 + 5
\end{align}
$$
可以看到，原来方程只有 2 个变量 $x, y$ ，扁平化之后引入了 3 个中间变量 $v1, v2, v3$ ，外加一个常数变量 $1$ 。我们将扁平后的变量向量（数组）记为 $w$ ：
$$
w = [1, x, v1, v2, v3, y]
$$
对于根 $x = 3$ ，变量向量的取值为：
$$
w(x=3) = [1, 3, 9, 27, 30, 35]
$$
下面是扁平化后的算数电路示意图，共有 6 个变量和 4 个算数门：
R1CS（Rank-1 Constraint System，秩-1约束系统）是一种表示计算的标准化方法，广泛用于零知识证明系统中。它将电路的每个门转换为一个约束，进而将电路的计算问题转化为一个矩阵方程，方便后续构造线性 PCP。
约束系统定义了一组变量和这些变量之间必须满足的关系，比如最简单的线性约束系统：
$$
a_1x_1 + a_2x_2 + a_0 = 0
$$
$$
b_1x_1 + b_2x_2 + b_0 = 0
$$
其中 $x_i$ 是变量, $a_i, b_i$ 是系数。它的矩阵形式可以写为 $Aw = 0$ ，其中 $A$ 是系数矩阵，$w = [1, x_1, x_2]$ 是变量向量。中国剩余定理解决的同余方程组也属于约束系统。
再比如二次约束系统，每个约束等式的变量最高次为 2：
$$
a_{11} x_1^2 + a_{12} x_1x_2 + a_{22} x_2^2 + a_{20} x_2 + a_{00} = 0
$$
$$
b_{11} x_1^2 + b_{02} x_2 + b_{00} = 0
$$
其中每个约束都可以化简为 $w^T A w = 0$ 的形式，其中 $A$ 是系数矩阵，也被称为约束矩阵，$w$ 是变量向量（包含一个常数 1）。这个示例中， $w = [1, x_1, x_2]$ ，第一个约束矩阵可以表示为：
$$
A = \begin{bmatrix}
a_{00} & 0 & a_{20} \\
0 & a_{11} & 0 \\
0 & a_{12} & a_{22} \\
\end{bmatrix}
$$
R1CS 是一种特殊的二次约束系统，它的约束矩阵 $A$ 的秩为 1，即可表示为两个向量的外积 $A = a \otimes b = a b^T$ 。等价的，每个约束的形式可以简化为：
$$
\langle a, w \rangle \langle b, w \rangle = \langle c, w \rangle
$$
其中 $a, b, c$ 是系数向量，$w$ 是变量向量， $\langle a, w \rangle = a^T w = \sum_{i} a_i w_i$ 表示向量内积。你可以自行推导下它为什么成立。
因此， R1CS 中的多个约束可以表示为矩阵形式：
$$
Aw \circ Bw = Cw
$$
其中 $A, B, C$ 是系数矩阵（和之前的约束矩阵不同），每一行代表一个约束中的 $a, b, c$ ，而 $w$ 是变量向量， $\circ$ 表示向量逐元素乘法（Hadamard积）。
R1CS 可以表示任意的电路计算问题，而电路满足性问题（Circuit SAT）是 NP 完全的，因此 R1CS 问题也是 NP 完全的。这意味着通过 R1CS，我们可以将任何 NP 问题转换为约束系统，方便后续的证明构造。
下面我们将示例中扁平化的电路转换为 R1CS 表示。在上一节，我们得到了 4 个约束：
$v_1 = x \cdot x$ $v_2 = v_1 \cdot x$ $v_3 = v_2 + x$ $y = v_3 + 5$
变量向量 $w$ 为：
$$
w = [1, x, v_1, v_2, v_3, y]
$$
约束 1 ：
$$
(x) \cdot (x) - v_1 = 0
$$
对应的向量表示为：
$a_1 = [0, 1, 0, 0, 0, 0]$ $b_1 = [0, 1, 0, 0, 0, 0]$ $c_1 = [0, 0, 1, 0, 0, 0]$
约束 2 ：
$$
(v_1) \cdot (x) - v_2 = 0
$$
对应的向量表示为：
$a_2 = [0, 0, 1, 0, 0, 0]$ $b_2 = [0, 1, 0, 0, 0, 0]$ $c_2 = [0, 0, 0, 1, 0, 0]$
约束 3 ：
$$
(v_2 + x) \cdot 1 - v_3 = 0
$$
对应的向量表示为：
$a_3 = [0, 1, 0, 1, 0, 0]$ $b_3 = [1, 0, 0, 0, 0, 0]$ $c_3 = [0, 0, 0, 0, 1, 0]$
约束 4 ：
$$
(v_3 + 5) \cdot 1 - y = 0
$$
注意加法和乘法的处理有区别，对应的向量表示为：
$a_4 = [5, 0, 0, 0, 1, 0]$ $b_4 = [1, 0, 0, 0, 0, 0]$ $c_4 = [0, 0, 0, 0, 0, 1]$
然后，我们将上述向量组合成矩阵 $A, B, C$ ，矩阵的行数与约束（算术门）数一致，为 4；列数与变量数一致，为 6：
$$
A = \begin{bmatrix}
0 & 1 & 0 & 0 & 0 & 0 \\
0 & 0 & 1 & 0 & 0 & 0 \\
0 & 1 & 0 & 1 & 0 & 0 \\
5 & 0 & 0 & 0 & 1 & 0 \\
\end{bmatrix}
$$
$$
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 = \begin{bmatrix}
0 & 0 & 1 & 0 & 0 & 0 \\
0 & 0 & 0 & 1 & 0 & 0 \\
0 & 0 & 0 & 0 & 1 & 0 \\
0 & 0 & 0 & 0 & 0 & 1 \\
\end{bmatrix}
$$
下面，我们验证约束是否成立，即对于每个约束，我们验证 $\langle a_i, w \rangle \langle b_i, w \rangle = \langle c_i, w \rangle$ 。
对于约束 3，有：
$a_3 w = x + v_2$ $b_3 w = 1$ $c_3 w = v_3$
也就是，
$$
(x + v_2) \cdot 1 = v_3
$$
这与原始约束 $v_3 = v_2 + x$ 一致，证明我们成功的将扁平化电路转换为 R1CS 表示。
这一讲，我们介绍了线性 PCP 的基本概念，以及构建它的第一步：将计算问题转换为 R1CS。下一讲，我们将介绍如何进一步转换为 QAP，并利用它构造线性 PCP。
