| title | tags | |||||
|---|---|---|---|---|---|---|
51. 线性 PCP 第二部分 QAP |
|
在上一讲中，我们介绍了构建线性 PCP 的第一步：将计算问题转换为 R1CS。这一讲，我们将介绍如何进一步转换为 QAP，并利用它构造线性 PCP。
QAP（Quadratic Arithmetic Program，二次算数程序）通过低度拓展将 R1CS 转换为多项式形式，让我们可以高效的验证证明，从而构造线性 PCP。如果你不熟悉低度拓展，可以参考 WTF zk 第 49 讲：PCP 。
QAP 的本质就是将 R1CS 中的系数矩阵
其中：
-
域
$\mathbb{F}$ ：多项式所在的有限域，通常是一个大素数域$\mathbb{F}_p$ ，所有计算都在该域中进行。 -
变量向量
$\mathbf{w}(x) = (w_0, w_1, ..., w_n)$ ：电路中所有的变量，包括输入、输出和中间变量。 -
系数多项式
${\hat{A_{:j}}(x)}, {\hat{B_{:j}}(x)}, {\hat{C_{:j}}(x)}$ ，其中$j = 0, 1, ..., n$ （$n$ 表示变量个数），$\hat{A_{:j}}$ 表示$A$ 的第$j$ 列。也就是说，系数矩阵$A, B, C$ 的每一列都要通过低度拓展转换为相应的多项式。 -
目标多项式
$T(x)$ ：由验证者选择，用于验证多项式关系。$T(x)$ 的根通常对应于电路中各个约束的位置。例如，如果我们有$m$ 个约束，可以选择$m$ 个不同的点$0, 1, ..., m-1$ ，那么：
-
商多项式
$H(x)$ ：验证者需要提供的证明的一部分，用于验证多项式的整除关系，有：
从 R1CS 到 QAP 的构造方法如下：
我们可以将 R1CS 的系数矩阵
我们得到 QAP 的系数矩阵，满足下列等式（由
为了方便，我们计
另外根据低度拓展的特性，我们知道对于
对于
我们记目标多项式
因为
对于正确的证明
下面我们将示例中的 R1CS 转换为 QAP 表示。在上一节，我们得到了 R1CS 系统：
变量向量
满足约束的原方程的根
下面，我们需要对系数矩阵
然后，我们可以要计算多项式
- 计算
$\hat{A_{:1}}$ ：矩阵$A$ 的第 1 列是$[0, 0, 0, 5]$ ，那么我们对$(1, 0), (2, 0), (3, 0), (4, 5)$ 进行插值，得到：
你可以验证下
- 计算
$\hat{A_{:4}}$ ：矩阵$A$ 的第 4 列是$[0, 0, 0, 0]$ ，那么我们对$(1, 0), (2, 0), (3, 0), (4, 0)$ 进行插值，结果就是零多项式：
同理，我们可以计算
手算效率太低，我们可以利用下面 python 代码计算它们：
import numpy as np
import galois
GF = galois.GF(67)
A = np.array([
[0, 1, 0, 0, 0, 0], # 约束 1
[0, 0, 1, 0, 0, 0], # 约束 2
[0, 1, 0, 1, 0, 0], # 约束 3
[5, 0, 0, 0, 1, 0], # 约束 4
])
B = np.array([
[0, 1, 0, 0, 0, 0], # 约束 1
[0, 1, 0, 0, 0, 0], # 约束 2
[1, 0, 0, 0, 0, 0], # 约束 3
[1, 0, 0, 0, 0, 0], # 约束 4
])
C = np.array([
[0, 0, 1, 0, 0, 0], # 约束 1
[0, 0, 0, 1, 0, 0], # 约束 2
[0, 0, 0, 0, 1, 0], # 约束 3
[0, 0, 0, 0, 0, 1], # 约束 4
])
A_galois = GF(A)
B_galois = GF(B)
C_galois = GF(C)
x = GF(3)
v1 = x * x
v2 = v1 * x
v3 = v2 + x
y = v3 + GF(5)
witness = GF(np.array([1, x, v1, v2, v3, y]))
print(witness)
assert all(np.equal(np.matmul(A_galois, witness) * np.matmul(B_galois, witness), np.matmul(C_galois, witness))), "not equal"
## low-degree extension for A, B, C
def interpolate_column(col):
xs = GF(np.array([1,2,3,4]))
return galois.lagrange_poly(xs, col)
# axis 0 is the columns. apply_along_axis is the same as doing a for loop over the columns and collecting the results in an array
A_polys = np.apply_along_axis(interpolate_column, 0, A_galois)
B_polys = np.apply_along_axis(interpolate_column, 0, B_galois)
C_polys = np.apply_along_axis(interpolate_column, 0, C_galois)
# matrix A becomes 6 polynomials
print("poly A: ", A_polys)
print("poly B: ", B_polys)
print("poly C: ", C_polys)
# poly A:
# [Poly(12x^3 + 62x^2 + 65x + 62, GF(67))
# Poly(44x^3 + 5x^2 + 11x + 8, GF(67))
# Poly(34x^3 + 63x^2 + 43x + 61, GF(67))
# Poly(33x^3 + 37x^2 + 60x + 4, GF(67))
# Poly(56x^3 + 66x^2 + 13x + 66, GF(67))
# Poly(0, GF(67))]
# 多项式
$A_{:0}(x) = 12x^3 + 62x^2 + 65x + 62$ $A_{:1}(x) = 44x^3 + 5x^2 + 11x + 8$ $A_{:2}(x) = 34x^3 + 63x^2 + 43x + 61$ $A_{:3}(x) = 33x^3 + 37x^2 + 60x + 4$ $A_{:4}(x) = 56x^3 + 66x^2 + 13x + 66$ $A_{:5}(x) = 0$
多项式
$B_{:0}(x) = 22x^3 + 36x^2 + 6x + 3$ $B_{:1}(x) = 45x^3 + 31x^2 + 61x + 65$ $B_{:2}(x) = 0$ $B_{:3}(x) = 0$ $B_{:4}(x) = 0$ $B_{:5}(x) = 0$
多项式
$C_{:0}(x) = 0$ $C_{:1}(x) = 0$ $C_{:2}(x) = 11x^3 + 35x^2 + 18x + 4$ $C_{:3}(x) = 34x^3 + 63x^2 + 43x + 61$ $C_{:4}(x) = 33x^3 + 37x^2 + 60x + 4$ $C_{:5}(x) = 56x^3 + 66x^2 + 13x + 66$
注意，以上的步骤都没有用到见证（证明）
from functools import reduce
def inner_product_polynomials_with_witness(polys, witness):
mul_ = lambda x, y: x * y
sum_ = lambda x, y: x + y
return reduce(sum_, map(mul_, polys, witness))
A_term = inner_product_polynomials_with_witness(A_polys, witness)
B_term = inner_product_polynomials_with_witness(B_polys, witness)
C_term = inner_product_polynomials_with_witness(C_polys, witness)
print(A_term)得到：
因此：
接下来，我们计算目标多项式：
最后，我们用上面两式相除，最终得到商多项式：
下面，我们验证结果：
与
## Target polynomial T = (x-1)(x-2)(x-3)(x-4)
T = galois.Poly([1, 67-1], field = GF) * galois.Poly([1, 67-2], field = GF) * galois.Poly([1, 67-3], field = GF) * galois.Poly([1, 67-4], field = GF)
## Quotient polynomial Q = (A * B - C) / T
Q = (A_term * B_term - C_term) // T
print(T * Q)
poly_big = A_term * B_term - C_term
assert poly_big // T * T == poly_big如果证明者不知道正确的 witness，比如
而它无法整除
## wrong witness
witness_wrong = GF(np.array([1, 3, 9, 27, 30, 36]))
A_term_wrong = inner_product_polynomials_with_witness(A_polys, witness_wrong)
B_term_wrong = inner_product_polynomials_with_witness(B_polys, witness_wrong)
C_term_wrong = inner_product_polynomials_with_witness(C_polys, witness_wrong)
print(A_term_wrong * B_term_wrong - C_term_wrong)
poly_big_wrong = A_term_wrong * B_term_wrong - C_term_wrong
assert poly_big_wrong // T * T == poly_big_wrong
## Error: A*B - C can not divide T得到 QAP 后，我们可以非常容易的构造线性 PCP。验证者期望的证明形式为
验证者
线性 PCP 的查询都是线性查询，即查询向量的内积。比如要查询
同理，我们可以提交
注意：
最后，我们还需要查询
验证者
因此，线性 PCP 的证明长度仅为
下面，我们来分析线性 PCP 的完备性和可靠性。
-
完备性（Completeness）：对于
$x \in L$ ，那么$Q(r)\prod_{i\in H}(r-i) = \mathcal{A}(r) \cdot \mathcal{B}(r) - \mathcal{C}(r)$ 成立，验证者能够以 1 的概率正确验证证明。 -
可靠性（Soundness）：对于
$x \notin L$ ，那么根据 Schwartz–Zippel 引理，$Q(r)\prod_{i\in H}(r-i) = \mathcal{A}(r) \cdot \mathcal{B}(r) - \mathcal{C}(r)$ 的概率小于$\frac{2m}{|\mathbb{F}|}$ 。我们选择的域$\mathbb{F}$ 余额大，那么可靠性错误概率就越小。
我们基于 QAP 的示例继续构造线性 PCP。
- 采样：验证者
$V$ 随机选择$r = 6 \mod{67}$ 。 - 查询：验证者
$V$ 查询$\mathcal{A}(r), \mathcal{B}(r), \mathcal{C}(r), Q(r)$ ，得到结果：
最后，我们验证：
显然，
## Linear PCP
# random number generation, we choose 6 for education purpose
r_random = GF(6)
# check A, B, C
A_random = A_term(r_random)
B_random = B_term(r_random)
C_random = C_term(r_random)
Q_random = Q(r_random)
T_random = T(r_random)
print("A_random: ", A_random)
print("B_random: ", B_random)
print("C_random: ", C_random)
print("Q_random: ", Q_random)
print("T_random: ", T_random)
assert A_random * B_random - C_random == Q_random * T_random
# pass若证明者提供的 witness 错误，假如
这一讲，我们介绍了构建线性 PCP 的第二部分：将 R1CS 转换为 QAP，并利用它构造线性 PCP。QAP 通过将 R1CS 系数矩阵扩展为多项式，让我们可以利用 Schwartz–Zippel 引理更高效的验证证明：仅需查询证明中的 4 位就可以验证一个 NP 问题。