二次算术程序

二次算术程序是一个 算术电路，具体来说是一个 等级 1 约束系统 (R1CS)，表示为一组多项式。它是通过在等级 1 约束系统上使用拉格朗日插值法得出的。与 R1CS 不同，二次算术程序 (QAP) 可以通过施瓦茨-齐佩尔引理在 $\mathcal{O}(1)$ 时间内测试相等性。

关键思想

在施瓦茨-齐佩尔引理的章节中，我们看到我们可以通过将两个向量转换为多项式来测试它们是否相等，然后在多项式上运行施瓦茨-齐佩尔引理测试，测试是在 $\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})$ 是使用 $(1, 2, …, n)$ 作为 $x$ 值对向量 $\mathbf{v}$ 进行拉格朗日插值所得到的多项式，其中 $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]))

## 两个任意向量
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]))

## 任意向量
v =  GF(np.array([4,8,2]))

## 任意常数
lambda_ =  GF(15)

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

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

标量乘法实际上是向量加法

当我们说“向量乘以 3”时，我们实际上是说“将向量自身加三次”。由于我们只在有限域中工作，我们不担心标量例如“0.5”的解释。

我们可以将元素加法（在有限域中）下的两个向量看作与多项式下的加法（同样在有限域中）作为 群。

这一章最重要的收获是：

在有限域中，向量的加法群与多项式的加法群是同态的。

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

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

这就是 二次算术程序。

一种多项式中的 Rank 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 v1 + a{12}\cdot v2 + a{13}\cdot v3 + a{14}\cdot v4\\ a{21}\cdot v1 + a{22}\cdot v2 + a{23}\cdot v3 + a{24}\cdot v4\\ a{31}\cdot v1 + a{32}\cdot v2 + a{33}\cdot v3 + 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 v1 + \begin{bmatrix} a{12} \\ a{22} \\ a{32} \end{bmatrix}\cdot v2 + \begin{bmatrix} a{13} \\ a{23} \\ a{33} \end{bmatrix}\cdot v3 + \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}}_{p1(x)}\cdot 2 + \underbrace{ \begin{bmatrix} 3 \\ 7 \\ \end{bmatrix}}{p2(x)}\cdot 4 \stackrel{?}{=} \underbrace{ \begin{bmatrix} 3 \\ 12 \\ \end{bmatrix}}{q1(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)

最后，我们可以检查

$$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) # 随机点

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

最后的断言语句能够通过一次比较来测试 $\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$）和三行（$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 u4(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} $$

由于将列向量乘以标量同态于将多项式乘以标量，因此每个多项式可以乘以见证中的相应元素。

例如，

$$ \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_4u4(x)\\ &=\sum{i=1}^4 a_iu_i(x) \end{align} $$

请注意，最终结果是一个度数至多为 $n-1$（因为 $\mathbf{L}$ 中有 $n$ 行，$u_1(x), …, u_n(x)$ 的度数至多为 $n-1$） 的单一多项式。

在一般情况下，$\mathbf{L}\mathbf{a}$ 可以写成

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

在将每列的 $m$ 列转换为多项式后。

使用上述相同步骤，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_iui(x) \\ \mathbf{R}\mathbf{a} \rightarrow \sum{i=1}^m a_ivi(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_iui(x) = u(x)\\ \mathbf{R}\mathbf{a} &\rightarrow \sum{i=1}^m a_ivi(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{ 是 } \mathbf{L} 是列 } i \text{ 的拉格朗日插值 } $$

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

我们需要在 谁 使用 QAP 之间做出区别。验证者（以及后面将讨论的可信设置）并不知道见证 $\mathbf{a}$，因此不能计算 $\mathcal{L}(\mathbf{L}\mathbf{a})$。这是证明者可以做的优化，但 ZK 协议中的其他方无法利用这一优化。

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

多项式度数的不平衡

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

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

因为度数不会匹配。

将两个多项式相乘的结果是一个什么多项式，其度数是被乘的两个多项式的度数之和。

由于 $u(x)$、$v(x)$ 和 $w(x)$ 的度数都是 $n - 1$，$u(x)v(x)$ 通常具有 $2n - 2$ 的度数，而 $w(x)$ 将具有 $n - 1$ 的度数，因此即使它们被乘的基础向量相等，它们也不会相等。

这是因为我们之前建立的同态仅仅涉及向量加法，而不是哈达玛乘积。

但是，$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]$。

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

插值 $\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}$，从而抵消度数不匹配的情况。

例如，图中黑色多项式 ($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)$，否则他们可以选择一个 $b(x)$ 来平衡 $u(x)v(x)$ 和 $w(x)$，即使它们没有插值相同的向量（在我们的例子中是 $[8, 8, 64]$）。证明者在选择 $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,…,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,…,n$ 处必须有根。

因此，我们将在我们的方程中用 $h(x)t(x)$ 替换 $b(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 端到端

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

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

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

也就是说， $\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}}_{u1(x)} \quad \underbrace{\begin{bmatrix} l{21} \\ l{22} \\ l{23} \\ l{24} \end{bmatrix}}{u2(x)} \quad \underbrace{\begin{bmatrix} l{31} \\ l{32} \\ l{33} \\ l{34} \\ \end{bmatrix}}{u3(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}}_{v1(x)} \quad \underbrace{\begin{bmatrix} r{21} \\ r{22} \\ r{23} \\ r{24} \end{bmatrix}}{v2(x)} \quad \underbrace{\begin{bmatrix} r{31} \\ r{32} \\ r{33} \\ r{34} \\ \end{bmatrix}}{v3(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}}_{w1(x)} \quad \underbrace{\begin{bmatrix} o{21} \\ o{22} \\ o{23} \\ o{24} \end{bmatrix}}{w2(x)} \quad \underbrace{\begin{bmatrix} o{31} \\ o{32} \\ o{33} \\ o{34} \\ \end{bmatrix}}{w3(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_4u4(x) = u(x) \\ \sum{i=1}^m a_iv_i(x) &= a_1v_1(x) + a_2v_2(x) + a_3v_3(x) + a_4v4(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_iui(x)\sum{i=1}^4 a_ivi(x) = \sum{i=1}^4 a_iw_i(x) + h(x)t(x)$$

QAP 的最终公式

QAP 是以下公式：

$$\sum_{i=1}^m a_iui(x)\sum{i=1}^m a_ivi(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_iui(x)\sum{i=1}^ma_ivi(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}$。

然而，这需要验证者信任证明者正确评估多项式，而我们没有机制强迫证明者这样做。

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

然后我们将讨论可信设置，以开始解决如何让证明者诚实地评估多项式的问题。

最初发布时间：2023年8月23日

• 原文链接： rareskills.io/post/quadr...
• 登链社区 AI 助手，为大家转译优秀英文文章，如有翻译不通的地方，还请包涵～