二次算术程序

Last updated on Mar 22, 2026

二次算术程序（Quadratic Arithmetic Program）是一种算术电路，具体来说是将秩 1 约束系统（R1CS）表示为一组多项式。它是在秩 1 约束系统上使用拉格朗日插值推导出来的。与 R1CS 不同，二次算术程序（QAP）可以通过 Schwartz-Zippel 引理在 $\mathcal{O}(1)$ 时间内进行相等性测试。

核心思想

在关于 Schwartz-Zippel 引理的章节中，我们看到可以通过将两个向量转换为多项式，然后对多项式运行 Schwartz-Zippel 引理测试，从而在 $\mathcal{O}(1)$ 时间内测试它们是否相等。（需要澄清的是，测试本身是 $\mathcal{O}(1)$ 时间的，而将向量转换为多项式会产生额外的开销）。

因为秩 1 约束系统完全由向量运算组成，我们的目标是测试

\mathbf{L}\mathbf{a}\circ\mathbf{R}\mathbf{a}\stackrel{?}{=}\mathbf{O}\mathbf{a}

是否在 $\mathcal{O}(1)$ 时间而不是 $\mathcal{O}(n)$ 时间内成立（其中 $n$ 是 $\mathbf{L}$ 、 $\mathbf{R}$ 和 $\mathbf{O}$ 中的行数）。

但在此之前，我们需要了解表示向量的多项式与向量之间关系的一些关键属性。

对于这里的所有数学运算，我们假设我们在有限域中进行，但为了简洁起见，我们省略了 $\mod p$ 符号。

向量加法和多项式加法之间的同态

向量加法同态于多项式加法

如果我们取两个向量，用多项式对它们进行插值，然后将这些多项式相加，我们得到的多项式，与我们将向量相加然后再对求和后的向量进行插值得到的多项式是相同的。

用更数学化的语言来说，令 $\mathcal{L}(\mathbf{v})$ 为对向量 $\mathbf{v}$ 使用 $(1, 2, ..., n)$ 作为 $x$ 值进行拉格朗日插值所得到的多项式，其中 $n$ 是 $\mathbf{v}$ 的长度。以下等式成立：

\mathcal{L}(\mathbf{v} + \mathbf{w}) = \mathcal{L}(\mathbf{v}) + \mathcal{L}(\mathbf{w})

换句话说，对向量 $\mathbf{v}$ 和 $\mathbf{w}$ 进行插值后得到的多项式之和，与对向量 $\mathbf{v} + \mathbf{w}$ 进行插值得到的多项式是相同的。

示例演示

令 $f_1(x) = x^2$ 且 $f_2(x) = x^3$ ， $f_1$ 插值 $(1, 1), (2, 4), (3, 9)$ 或向量 $[1,4,9]$ ， $f_2$ 插值 $[1,8,27]$ 。

向量之和为 $[2,12,36]$ ，很明显 $x^3 + x^2$ 对其进行了插值。令 $f_3(x) = f_1(x) + f_2(x) = x^3 + x^2$ 。

\begin{align*} f_3(1) &= 1 + 1 = 2\\ f_3(2) &= 8 + 4 = 12\\ f_3(3) &= 27 + 9 = 36 \end{align*}

用 Python 测试数学逻辑

对提出的数学恒等式进行单元测试并不能证明它的绝对真实性，但它确实说明了正在发生的事情。鼓励读者尝试几个不同的向量，以验证该恒等式是否成立。

import galois
import numpy as np

p = 17
GF = galois.GF(p)

xs = GF(np.array([1,2,3]))

# two arbitrary vectors
v1 =  GF(np.array([4,8,2])) 
v2 =  GF(np.array([1,6,12]))

def L(v):
    return galois.lagrange_poly(xs, v)

assert L(v1 + v2) == L(v1) + L(v2)

标量乘法

令 $\lambda$ 为一个标量（具体来说，是有限域中的一个域元素）。那么

\mathcal{L}(\lambda \mathbf{v}) = \lambda \mathcal{L}(\mathbf{v})

示例演示

假设我们的 3 个点对应 $[3, 6, 11]$ 。对其进行插值的多项式为 $f(x) = x^2 + 2$ 。如果我们将向量乘以 3，我们得到 $[9, 18, 33]$ 。对其进行插值的多项式是

from scipy.interpolate import lagrange

x_values = [1, 2, 3]
y_values = [9, 18, 33]

print(lagrange(x_values, y_values))

#    2
# 3 x + 6

$3x^2 + 6$ ，它等于 $3 \cdot (x^2 + 2)$ 。

代码示例演示

import galois
import numpy as np

p = 17
GF = galois.GF(p)

xs = GF(np.array([1,2,3]))

# arbitrary vector
v =  GF(np.array([4,8,2]))

# arbitrary constant
lambda_ =  GF(15)

def L(v):
    return galois.lagrange_poly(xs, v)

assert L(lambda_ * v) == lambda_ * L(v)

标量乘法本质上是向量加法

当我们说“将向量乘以 3”时，我们实际上是在说“将向量自身相加三次”。因为我们只在有限域中进行运算，所以我们不需要关心像“0.5”这样标量的解释。

我们可以将逐元素加法下的向量（在有限域中）和加法下的多项式（也在有限域中）都视为群（groups）。

本章最重要的结论是

有限域中加法下的向量群同态于有限域中加法下的多项式群。

这很关键，因为向量相等性测试需要 $\mathcal{O}(n)$ 时间，而多项式相等性测试只需 $\mathcal{O}(1)$ 时间。

因此，尽管测试 R1CS 的相等性需要 $\mathcal{O}(n)$ 时间，我们可以利用这种同态性在 $\mathcal{O}(1)$ 时间内测试 R1CS 的相等性。

这就是二次算术程序（Quadratic Arithmetic Program）的本质。

多项式形式的秩 1 约束系统

考虑矩形矩阵和向量之间的矩阵乘法可以写成向量加法和标量乘法的形式。

例如，如果我们有一个 $3 \times 4$ 的矩阵 $A$ 和一个 4 维向量 $v$ ，那么我们可以将矩阵乘法写为

\mathbf{A} \cdot \mathbf{v} = \begin{bmatrix} a_{11} & a_{12} & a_{13} & a_{14}\\ a_{21} & a_{22} & a_{23} & a_{24}\\ a_{31} & a_{32} & a_{33} & a_{34} \end{bmatrix} \begin{bmatrix} v_1\\ v_2\\ v_3\\ v_4 \end{bmatrix}

我们通常将向量 $v$ 想象为“翻转”并与每一行进行内积（广义点积），即

\mathbf{A}\cdot \mathbf{v} = \begin{bmatrix} a_{11}\cdot v_1 + a_{12}\cdot v_2 + a_{13}\cdot v_3 + a_{14}\cdot v_4\\ a_{21}\cdot v_1 + a_{22}\cdot v_2 + a_{23}\cdot v_3 + a_{24}\cdot v_4\\ a_{31}\cdot v_1 + a_{32}\cdot v_2 + a_{33}\cdot v_3 + a_{34}\cdot v_4 \end{bmatrix}

然而，我们也可以将矩阵 $A$ 拆分为一系列向量，如下所示：

\mathbf{A} = \begin{bmatrix} a_{11} \\ a_{21} \\ a_{31} \end{bmatrix} , \begin{bmatrix} a_{12} \\ a_{22} \\ a_{32} \end{bmatrix} , \begin{bmatrix} a_{13} \\ a_{23} \\ a_{33} \end{bmatrix} , \begin{bmatrix} a_{14} \\ a_{24} \\ a_{34} \end{bmatrix}

然后将每个向量乘以向量 $\mathbf{v}$ 中的一个标量：

\mathbf{A}\cdot \mathbf{v} = \begin{bmatrix} a_{11} \\ a_{21} \\ a_{31} \end{bmatrix}\cdot v_1 + \begin{bmatrix} a_{12} \\ a_{22} \\ a_{32} \end{bmatrix}\cdot v_2 + \begin{bmatrix} a_{13} \\ a_{23} \\ a_{33} \end{bmatrix}\cdot v_3 + \begin{bmatrix} a_{14} \\ a_{24} \\ a_{34} \end{bmatrix}\cdot v_4

我们已纯粹用向量加法和标量乘法表达了 $\mathbf{A}$ 和 $\mathbf{v}$ 之间的矩阵乘法。

因为我们之前已经确定，有限域中加法下的向量群同态于有限域中加法下的多项式群，所以我们可以用表示这些向量的多项式来表达上述计算。

简洁地测试 $\mathbf{A}\mathbf{v}_1 = \mathbf{B}\mathbf{v}_2$

假设我们有矩阵 $\mathbf{A}$ 和 $\mathbf{B}$ 满足

\begin{align*} \mathbf{A} = \begin{bmatrix} 6 & 3\\ 4 & 7\\ \end{bmatrix}\\ \mathbf{B} = \begin{bmatrix} 3 & 9 \\ 12 & 6\\ \end{bmatrix} \end{align*}

以及向量 $\mathbf{v}_1$ 和 $\mathbf{v}_2$

\begin{align*} \mathbf{v}_1 = \begin{bmatrix} 2 \\ 4 \\ \end{bmatrix}\\ \mathbf{v}_2 = \begin{bmatrix} 2 \\ 2 \\ \end{bmatrix} \end{align*}

我们想要测试

\mathbf{A}\mathbf{v}_1 = \mathbf{B}\mathbf{v}_2

是否成立。

显然，我们可以执行矩阵算术运算，但最终的检查将需要 $n$ 次比较，其中 $n$ 是 $\mathbf{A}$ 和 $\mathbf{B}$ 的行数。我们希望在 $\mathcal{O}(1)$ 时间内完成。

首先，我们将矩阵乘法 $\mathbf{A}\mathbf{v}_1$ 和 $\mathbf{B}\mathbf{v}_2$ 转换为加法下的向量群：

\begin{align*} \mathbf{A} &= \begin{bmatrix} 6 \\ 4 \\ \end{bmatrix} , \begin{bmatrix} 3 \\ 7 \\ \end{bmatrix}\\ \mathbf{B} &= \begin{bmatrix} 3 \\ 12 \\ \end{bmatrix} , \begin{bmatrix} 9 \\ 6 \\ \end{bmatrix} \end{align*}

我们现在希望在多项式群中找到

\begin{bmatrix} 6 \\ 4 \\ \end{bmatrix}\cdot 2+ \begin{bmatrix} 3 \\ 7 \\ \end{bmatrix}\cdot 4\stackrel{?}{=} \begin{bmatrix} 3 \\ 12 \\ \end{bmatrix}\cdot 2+ \begin{bmatrix} 9 \\ 6 \\ \end{bmatrix}\cdot 2

的同态等价物。

让我们在 $x$ 值 $[1,2]$ 的区间内将每个向量转换为多项式：

\underbrace{ \begin{bmatrix} 6 \\ 4 \\ \end{bmatrix}}_{p_1(x)}\cdot 2+ \underbrace{ \begin{bmatrix} 3 \\ 7 \\ \end{bmatrix}}_{p_2(x)}\cdot 4\stackrel{?}{=} \underbrace{ \begin{bmatrix} 3 \\ 12 \\ \end{bmatrix}}_{q_1(x)}\cdot 2+ \underbrace{ \begin{bmatrix} 9 \\ 6 \\ \end{bmatrix}}_{q_2(x)}\cdot 2

我们将调用一些 Python 代码来计算拉格朗日插值：

import galois
import numpy as np

p = 17
GF = galois.GF(p)

x_values = GF(np.array([1, 2]))

def L(v):
    return galois.lagrange_poly(x_values, v)

p1 = L(GF(np.array([6, 4])))
p2 = L(GF(np.array([3, 7])))
q1 = L(GF(np.array([3, 12])))
q2 = L(GF(np.array([9, 6])))

print(p1)
# 15x + 8 (mod 17)
print(p2)
# 4x + 16 (mod 17)
print(q1)
# 9x + 11 (mod 17)
print(q2)
# 14x + 12 (mod 17)

最后，我们可以通过调用 Schwartz-Zippel 引理来检查

p_1(x) \cdot 2+ p_2(x) \cdot 4 \stackrel{?}= q_1(x) \cdot 2 + q_2(x) \cdot 2

是否为真：

import random
u = random.randint(0, p)
tau = GF(u) # a random point

left_hand_side = p1(tau) * GF(2) + p2(tau) * GF(4)
right_hand_side = q1(tau) * GF(2) + q2(tau) * GF(2)

assert left_hand_side == right_hand_side

最后的 assert 语句能够通过进行单次比较（而不是 $n$ 次比较）来测试 $\mathbf{A}\mathbf{v}_1 = \mathbf{B}\mathbf{v}_2$ 。

R1CS 到 QAP：简洁地测试 $\mathbf{L}\mathbf{a}\circ\mathbf{R}\mathbf{a}=\mathbf{O}\mathbf{a}$

既然我们知道如何简洁地测试 $\mathbf{A}\mathbf{v}_1 = \mathbf{B}\mathbf{v}_2$ ，我们是否也可以简洁地测试 $\mathbf{L}\mathbf{a}\circ\mathbf{R}\mathbf{a}=\mathbf{O}\mathbf{a}$ 呢？

这些矩阵有 $m$ 列，因此让我们将每个矩阵分解为 $m$ 个列向量，并在 $(1, 2, ..., n)$ 上对它们进行插值，以各自生成 $m$ 个多项式。

令 $u_1(x), u_2(x), ..., u_m(x)$ 为对 $\mathbf{L}$ 的列向量进行插值的多项式。

令 $v_1(x), v_2(x), ..., v_m(x)$ 为对 $\mathbf{R}$ 的列向量进行插值的多项式。

令 $w_1(x), w_2(x), ..., w_m(x)$ 为对 $\mathbf{O}$ 的列向量进行插值的多项式。

不失一般性，假设我们有 4 列（ $m = 4$ ）和 3 行（ $n = 3$ ）。

直观上，这可以表示为

\begin{array}{c} \mathbf{L} = \begin{bmatrix} \quad l_{11} \quad& l_{12} \quad& l_{13} \quad& l_{14} \quad\\ \quad l_{21} \quad& l_{22} \quad& l_{23} \quad& l_{24} \quad\\ \quad l_{31} \quad& l_{32} \quad& l_{33} \quad& l_{34} \quad \end{bmatrix} \\ \\ \qquad u_1(x) \quad u_2(x) \quad u_3(x) \quad u_4(x) \end{array} \begin{array}{c} \mathbf{R} = \begin{bmatrix} \quad r_{11} \quad& r_{12} \quad& r_{13} \quad& r_{14} \quad\\ \quad r_{21} \quad& r_{22} \quad& r_{23} \quad& r_{24} \quad\\ \quad r_{31} \quad& r_{32} \quad& r_{33} \quad& r_{34} \quad \end{bmatrix} \\ \\ \qquad v_1(x) \quad v_2(x) \quad v_3(x) \quad v_4(x) \end{array}

\begin{array}{c} \mathbf{O} = \begin{bmatrix} \quad o_{11} \quad& o_{12} \quad& o_{13} \quad& o_{14} \quad\\ \quad o_{21} \quad& o_{22} \quad& o_{23} \quad& o_{24} \quad\\ \quad o_{31} \quad& o_{32} \quad& o_{33} \quad& o_{34} \quad \end{bmatrix} \\ \\ \qquad w_1(x) \quad w_2(x) \quad w_3(x) \quad w_4(x) \end{array}

因为将列向量乘以标量同态于将多项式乘以标量，所以每个多项式都可以乘以见证（witness）中各自对应的元素。

例如，

\mathbf{L}\mathbf{a} = \begin{bmatrix} \quad l_{11} \quad& l_{12} \quad& l_{13} \quad& l_{14} \quad\\ \quad l_{21} \quad& l_{22} \quad& l_{23} \quad& l_{24} \quad\\ \quad l_{31} \quad& l_{32} \quad& l_{33} \quad& l_{34} \quad \end{bmatrix} \begin{bmatrix} a_1 \\ a_2 \\ a_3 \\ a_4 \end{bmatrix}

变成了

\begin{align*} &=\begin{bmatrix} u_1(x) & u_2(x) & u_3(x) & u_4(x) \end{bmatrix} \begin{bmatrix} a_1 \\ a_2 \\ a_3 \\ a_4 \end{bmatrix}\\ &=a_1u_1(x) + a_2u_2(x) + a_3u_3(x) + a_4u_4(x)\\ &=\sum_{i=1}^4 a_iu_i(x) \end{align*}

观察最终结果是一个度数至多为 $n - 1$ 的单一多项式，因为 $u_1(x), \ldots, u_n(x)$ 的度数至多为 $n - 1$ 。
这源于我们构造它们的方式： $\mathbf{L}$ 的每一列都有 $n$ 个项，并且通过拉格朗日插值对 $n$ 个点进行插值会产生一个度数至多为 $n - 1$ 的多项式。

在一般情况下，将 $m$ 个列分别转换为多项式之后， $\mathbf{L}\mathbf{a}$ 可以写为

\sum_{i=1}^m a_iu_i(x)

使用与上面相同的步骤，R1CS $\mathbf{L}\mathbf{a}\circ\mathbf{R}\mathbf{a} = \mathbf{O}\mathbf{a}$ 中的每个矩阵-见证乘积可以转换为

\begin{align*} \mathbf{L}\mathbf{a} \rightarrow \sum_{i=1}^m a_iu_i(x) \\ \mathbf{R}\mathbf{a} \rightarrow \sum_{i=1}^m a_iv_i(x) \\ \mathbf{O}\mathbf{a} \rightarrow \sum_{i=1}^m a_iw_i(x) \end{align*}

由于每个求和项都产生一个单一多项式，我们可以将它们写为：

\begin{align*} \mathbf{L}\mathbf{a} &\rightarrow \sum_{i=1}^m a_iu_i(x) = u(x)\\ \mathbf{R}\mathbf{a} &\rightarrow \sum_{i=1}^m a_iv_i(x) = v(x)\\ \mathbf{O}\mathbf{a} &\rightarrow \sum_{i=1}^m a_iw_i(x) = w(x) \end{align*}

为什么要对所有的列进行插值？

由于同态性 $\mathcal{L}(\mathbf{v}_1) + \mathcal{L}(\mathbf{v}_2) = \mathcal{L}(\mathbf{v}_1 + \mathbf{v}_2)$ 和 $\mathcal{L}(\lambda \mathbf{v}) = \lambda \mathcal{L}(\mathbf{v})$ ，如果我们将 $u(x)$ 计算为 $\mathcal{L}(\mathbf{L}\mathbf{a})$ ，得到的结果与对 $\mathbf{L}$ 的各列应用拉格朗日插值，然后将每个多项式乘以 $\mathbf{a}$ 中对应的元素并对结果求和得到的结果是相同的。

换句话说，

\sum_{i=1}^m a_iu_i(x) = \mathcal{L}(\mathbf{L}\mathbf{a}) \mid u_i(x) \text{ is the Lagrange interpolation of column } i \text{ of } \mathbf{L}

那么为什么不只计算一次拉格朗日插值而不是 $m$ 次呢？

我们需要区分是谁在使用 QAP。验证者（以及我们稍后将介绍的可信设置）不知道见证 $\mathbf{a}$ ，因此无法计算 $\mathcal{L}(\mathbf{L}\mathbf{a})$ 。这是证明者可以做的一个优化，但零知识（ZK）协议中的其他参与方无法使用该优化。

所有相关方都需要在进行任何证明和验证之前，对 QAP——即矩阵的多项式插值——达成共识。

多项式度数不平衡

然而，我们不能简单地将最终结果表达为

u(x)v(x) = w(x)

因为多项式的度数（degree）不匹配。

将两个多项式相乘，其结果多项式的度数等于相乘的两个多项式度数之和。

因为 $u(x)$ 、 $v(x)$ 和 $w(x)$ 各自的度数都是 $n - 1$ ，所以 $u(x)v(x)$ 通常的度数将是 $2n - 2$ ，而 $w(x)$ 的度数是 $n - 1$ ，因此尽管它们相乘所对应的底层向量是相等的，但多项式本身并不相等。

这是因为我们之前建立的同态仅针对向量加法，而不是哈达玛乘积（Hadamard product）。

然而， $u(x)v(x)$ 所插值的向量，即

((1, u(1)v(1)), (2, u(2)v(2)), ..., (n, u(n)v(n)))

与 $w(x)$ 所插值的向量是相同的，即

((1, w(1)), \quad (2, w(2)), \quad ..., \quad (n, w(n)))

换句话说

((1, u(1)v(1)), (2, u(2)v(2)), ..., (n, u(n)v(n))) = ((1, w(1)), (2, w(2)), ..., (n, w(n)))

尽管“底层”的向量相等，但对它们进行插值的多项式并不相等。

底层相等的例子

假设 $u(x)$ 是对以下点进行插值的多项式

(1,\boxed{2}), (2,\boxed{4}), (3,\boxed{8})

而 $v(x)$ 是对以下点进行插值的多项式

(1,\boxed{4}), (2,\boxed{2}), (3,\boxed{8})

如果我们视 $u(x)$ 插值了向量 $[2,4,8]$ 而 $v(x)$ 插值了向量 $[4,2,8]$ ，那么我们可以看到它们的乘积多项式插值了这两个向量的哈达玛乘积。 $[2,4,8]$ 和 $[4,2,8]$ 的哈达玛乘积为 $[8,8,64]$ 。

如果我们将 $u(x)$ 和 $v(x)$ 乘在一起，我们得到 $w(x) = 4x^4 - 18x^3 + 36x^2 - 42x + 28$ 。

我们可以从下面的图表中看到，乘积多项式插值了这两个向量的哈达玛乘积 $[8, 8, 64]$ 。

那么如果它们在 $(1,2,...,n)$ 上插值了相同的 $y$ 值，我们怎么才能“使得” $w(x)$ 等于 $u(x)v(x)$ 呢？

对 $\mathbf{0}$ 向量进行插值

如果 $\mathbf{v_1} \circ \mathbf{v_2} = \mathbf{v_3}$ ，那么 $\mathbf{v_1} \circ \mathbf{v_2} = \mathbf{v_3} + \mathbf{0}$ 。

我们不需要用拉格朗日插值对 $\mathbf{0}$ 进行插值并得到 $f(x) = 0$ （记住拉格朗日插值会找到最低度数的插值多项式），我们可以使用一个更高度数的多项式来平衡度数的不匹配。

例如，下图中黑色的多项式（ $b(x)$ ）插值了 $[(1,0), (2,0), (3,0)]$ ：

现在，由于 $4x^4 -18x^3 + 8x^2 + 42x - 36$ 是 $[0,0,0]$ 的有效插值，我们可以将原始等式写为

$u(x)v(x) = w(x) + b(x)$

等式就平衡了！

$b(x)$ 是简单地通过 $u(x)v(x) - w(x)$ 计算得出的（蓝色多项式减去红色多项式）

然而，我们不能让证明者挑选任意的 $b(x)$ ，否则他们即使在没有插值相同向量（在我们的例子中是 $[8, 8, 64]$ ）的情况下，也可以挑选一个能平衡 $u(x)v(x)$ 和 $w(x)$ 的 $b(x)$ 。证明者在选择 $b(x)$ 时拥有太多的灵活性。具体来说，我们希望要求 $b(x)$ 在 $x = 1,2,\dots,n$ 处有根——也就是说，去插值 $\mathbf{0}$ 向量。这样一来， $\mathbf{v}_1 \circ \mathbf{v}_2 = \mathbf{v}_3 + \mathbf{0}$ 的多项式转换依然会遵循底层的向量。

为了限制他们对 $b(x)$ 的选择，我们可以使用以下定理：

多项式乘积的根的并集

定理：如果 $h(x) = f(x)g(x)$ ，且 $f(x)$ 有根的集合 $\set{r_f}$ ， $g(x)$ 有根的集合 $\set{r_g}$ ，那么 $h(x)$ 拥有的根为 $\set{r_f} \cup \set{r_g}$ 。

示例

令 $f(x) = (x - 3)(x - 4)$ 且 $g(x) = (x - 5)(x - 6)$ 。那么 $h(x) = f(x)g(x)$ 的根为 $\set{3,4,5,6}$ 。

我们可以利用上面的定理强制使得 $b(x)$ 的根在 $x = 1,2,\dots,n$ 处。

强制 $b(x)$ 为零向量

我们将 $b(x)$ 分解为 $b(x) = h(x)t(x)$ ，其中 $t(x)$ 是多项式

t(x) = (x-1)(x-2)\dots(x-n)

那么与 $t(x)$ 相乘的任何多项式对应的也将是零向量，因为它必然会在 $x = 1,2,\dots,n$ 处有根。

因此，我们将在我们的等式中把 $b(x)$ 替换为 $h(x)t(x)$ 。

从而，我们的等式将变为

u(x)v(x) = w(x) + h(x)t(x)

我们利用基础代数就可以计算出 $h(x)$ ：

h(x) = \frac{u(x)v(x) - w(x)}{t(x)}

QAP 端到端

假设我们有一个具备矩阵 $\mathbf{L}$ 、 $\mathbf{R}$ 和 $\mathbf{O}$ 以及见证向量 $\mathbf{a}$ 的 R1CS。

\mathbf{L}\mathbf{a}\circ\mathbf{R}\mathbf{a} = \mathbf{O}\mathbf{a}

这些矩阵有 $n$ 列和 $m$ 行，其中 $n = 4$ 且 $m = 3$ 。

即， $\mathbf{L}$ 、 $\mathbf{R}$ 和 $\mathbf{O}$ 如下所示：

\begin{array}{c} \mathbf{L} = \begin{bmatrix} \quad l_{11} \quad& l_{12} \quad& l_{13} \quad& l_{14} \quad\\ \quad l_{21} \quad& l_{22} \quad& l_{23} \quad& l_{24} \quad\\ \quad l_{31} \quad& l_{32} \quad& l_{33} \quad& l_{34} \quad \end{bmatrix} \\ \\ \mathbf{R} = \begin{bmatrix} \quad r_{11} \quad& r_{12} \quad& r_{13} \quad& r_{14} \quad\\ \quad r_{21} \quad& r_{22} \quad& r_{23} \quad& r_{24} \quad\\ \quad r_{31} \quad& r_{32} \quad& r_{33} \quad& r_{34} \quad \end{bmatrix} \\ \\ \mathbf{O} = \begin{bmatrix} \quad o_{11} \quad& o_{12} \quad& o_{13} \quad& o_{14} \quad\\ \quad o_{21} \quad& o_{22} \quad& o_{23} \quad& o_{24} \quad\\ \quad o_{31} \quad& o_{32} \quad& o_{33} \quad& o_{34} \quad \end{bmatrix} \end{array}

且见证向量 $\mathbf{a}$ 是

\mathbf{a} = \begin{bmatrix} a_1 \\ a_2 \\ a_3 \\ a_4 \end{bmatrix}

我们将每个矩阵分解为 $m$ 个列向量，并在 $(1, 2, ..., n)$ 上对它们进行插值，每个矩阵生成 $m$ 个多项式。

\begin{array}{c} \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)} \end{array}

\begin{array}{c} \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)} \end{array}

\begin{array}{c} \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)} \end{array}

每一个矩阵-向量乘积 $\mathbf{L}\mathbf{a}$ 、 $\mathbf{R}\mathbf{a}$ 和 $\mathbf{O}\mathbf{a}$ 在同态上等价于以下多项式：

\begin{align*} \sum_{i=1}^4 a_iu_i(x) &= a_1u_1(x) + a_2u_2(x) + a_3u_3(x) + a_4u_4(x) = u(x) \\ \sum_{i=1}^m a_iv_i(x) &= a_1v_1(x) + a_2v_2(x) + a_3v_3(x) + a_4v_4(x) = v(x) \\ \sum_{i=1}^m a_iw_i(x) &= a_1w_1(x) + a_2w_2(x) + a_3w_3(x) + a_4w_4(x) = w(x) \\ \end{align*}

在我们的例子中， $t(x)$ 将是

t(x) = (x - 1)(x - 2)(x - 3)

而 $h(x)$ 将是

h(x) = \frac{u(x)v(x) - w(x)}{t(x)}

原始 R1CS 的 QAP 表示的最终公式为

\sum_{i=1}^4 a_iu_i(x)\sum_{i=1}^4 a_iv_i(x) = \sum_{i=1}^4 a_iw_i(x) + h(x)t(x)

QAP 的最终公式

QAP 就是以下公式：

\sum_{i=1}^m a_iu_i(x)\sum_{i=1}^m a_iv_i(x) = \sum_{i=1}^m a_iw_i(x) + h(x)t(x)

其中 $u_i(x)$ 、 $v_i(x)$ 和 $w_i(x)$ 分别是对 $\mathbf{L}$ 、 $\mathbf{R}$ 和 $\mathbf{O}$ 的列进行插值的多项式， $t(x)$ 为 $(x - 1)(x - 2)...(x - n)$ ，其中 $n$ 是 $\mathbf{L}$ 、 $\mathbf{R}$ 和 $\mathbf{O}$ 的行数，而 $h(x)$ 是

h(x) = \frac{\sum_{i=1}^ma_iu_i(x)\sum_{i=1}^ma_iv_i(x) - \sum_{i=1}^ma_iw_i(x)}{t(x)}

使用二次算术程序的简洁零知识证明

假设我们有一种方法使得验证者可以向证明者发送一个随机值 $\tau$ ，并且证明者会以如下形式回应：

\begin{align*} A &= u(\tau)\\ B &= v(\tau)\\ C &= w(\tau) + h(\tau)t(\tau) \end{align*}

验证者可以检查 $AB = C$ 并接受证明者拥有一个有效的、同时满足 R1CS 和 QAP 的见证 $\mathbf{a}$ 。

然而，这将要求验证者信任证明者正在正确地求值这些多项式，而我们目前并没有一种机制来强制证明者这样做。

在下一章中，我们将基于本章的讨论展示将 R1CS 转换为 QAP 的 Python 代码。

接下来我们将讨论可信设置（trusted setups），开始着手解决如何让证明者诚实地对多项式进行求值的问题。

原文首发于 2023 年 8 月 23 日

核心思想

向量加法和多项式加法之间的同态

向量加法同态于多项式加法

示例演示

用 Python 测试数学逻辑

标量乘法

示例演示

代码示例演示

标量乘法本质上是向量加法

多项式形式的秩 1 约束系统

简洁地测试 Av1=Bv2\mathbf{A}\mathbf{v}_1 = \mathbf{B}\mathbf{v}_2Av1​=Bv2​

R1CS 到 QAP：简洁地测试 La∘Ra=Oa\mathbf{L}\mathbf{a}\circ\mathbf{R}\mathbf{a}=\mathbf{O}\mathbf{a}La∘Ra=Oa

为什么要对所有的列进行插值？

多项式度数不平衡

底层相等的例子

对 0\mathbf{0}0 向量进行插值

多项式乘积的根的并集

示例

强制 b(x)b(x)b(x) 为零向量

QAP 端到端

QAP 的最终公式

使用二次算术程序的简洁零知识证明

简洁地测试 $\mathbf{A}\mathbf{v}_1 = \mathbf{B}\mathbf{v}_2$

R1CS 到 QAP：简洁地测试 $\mathbf{L}\mathbf{a}\circ\mathbf{R}\mathbf{a}=\mathbf{O}\mathbf{a}$

对 $\mathbf{0}$ 向量进行插值

强制 $b(x)$ 为零向量