在可信设置中评估和二次算术程序

在可信设置下评估二次算术程序

在可信设置下评估 二次算术程序 (QAP) 使得 prover 可以证明 QAP 被满足，而不泄露见证，同时使用固定大小的证明。

具体来说，QAP 多项式在一个未知点 $\tau$ 处被评估。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)$$

如果向量 $\mathbf{a}$ 满足该方程，则方程将是平衡的，否则以压倒性概率是不平衡的。

此处展示的方案不是安全的 ZK 证明，但它是展示 Groth16 如何工作的一个重要步骤。

具体示例

为了让这个概念不那么抽象，假设 秩1约束系统 (R1CS) 的矩阵 $\mathbf{L}$、$\mathbf{R}$ 和 $\mathbf{O}$ 具有 3 行和 4 列。

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

由于我们有 3 行，这意味着我们的插值多项式的度数将是 2。由于我们有 4 列，每个矩阵将生成 4 个多项式（总共 12 个多项式）。

我们的 QAP 将是

$$\sum_{i=1}^4a_iui(x)\sum{i=1}^4a_ivi(x) = \sum{i=1}^4a_iw_i(x) + h(x)t(x)$$

记号和初步知识

我们将群 $\mathbb{G}_1$ 和 $\mathbb{G}_2$ 中的生成椭圆曲线点称为 $G_1$ 和 $G_2$。群 $\mathbb{G}_1$ 中的元素表示为 $[X]_1$。群 $\mathbb{G}_2$ 中的元素表示为 $[X]_2$。如果下标可能和列表中的索引造成歧义，我们将说 $X \in \mathbb{G}_1$ 或 $X \in \mathbb{G}_2$。两个点之间的 椭圆曲线配对 表示为 $[X]_1 \bullet [Y]_2$。

设 $\mathbf{L}{(*,j)}$ 是 $\mathbf{L}$ 的第 $j$ 列。在我们的示例中，行将是 $(1,2,3)$ 和列将是 $(1,2,3,4)$。设 $\mathcal{L}(\mathbf{L}{(*,j)})$ 是对 $\mathbf{L}$ 的第 $j$ 列运行拉格朗日插值得到的多项式，使用 $x$ 值 $(1,2,3)$ 和 $y$ 值为第 $j$ 列的值。

由于我们有 4 列，我们从 $\mathbf{L}$ 中得到四个多项式

$$ \begin{align} u1(x) = \mathcal{L}(\mathbf{L}{(,1)}) =u{12}x^2 + u{11}x+u_{10}\\ u2(x) = \mathcal{L}(\mathbf{L}{(,2)}) =u{22}x^2 + u{21}x+u_{20}\\ u3(x) = \mathcal{L}(\mathbf{L}{(,3)}) =u{32}x^2 + u{31}x+u_{30}\\ u4(x) = \mathcal{L}(\mathbf{L}{(,4)}) =u{42}x^2 + u{41}x+u_{40}\\ \end{align} $$

从 $\mathbf{R}$ 中得到四个多项式

$$ \begin{align} v1(x) = \mathcal{L}(\mathbf{R}{(,1)}) =v{12}x^2 + v{11}x+v_{10}\\ v2(x) = \mathcal{L}(\mathbf{R}{(,2)}) =v{22}x^2 + v{21}x+v_{20}\\ v3(x) = \mathcal{L}(\mathbf{R}{(,3)}) =v{32}x^2 + v{31}x+v_{30}\\ v4(x) = \mathcal{L}(\mathbf{R}{(,4)}) =v{42}x^2 + v{41}x+v_{40}\\ \end{align} $$

和从 $\mathbf{O}$ 中得到的四个多项式

$$ \begin{align} v1(x) = \mathcal{L}(\mathbf{O}{(,1)}) =v{12}x^2 + v{11}x+v_{10}\\ v2(x) = \mathcal{L}(\mathbf{O}{(,2)}) =v{22}x^2 + v{21}x+v_{20}\\ v3(x) = \mathcal{L}(\mathbf{O}{(,3)}) =v{32}x^2 + v{31}x+v_{30}\\ v4(x) = \mathcal{L}(\mathbf{O}{(,4)}) =v{42}x^2 + v{41}x+v_{40}\\ \end{align} $$

多项式 $p_{ij}$ 意味着第 $i$ 个多项式和第 $j$ 个系数（次方）。例如，$j=2$ 表示与 $x^2$ 相关的系数。

我们的示例 QAP 是

$$ \sum_{i=1}^4a_iui(x)\sum{i=1}^4a_ivi(x) = \sum{i=1}^4a_iw_i(x) + h(x)t(x) $$

其中 $t(x) = (x – 1)(x – 2)(x – 3)$，而 $h(x)$ 是

$$ h(x)=\frac{\sum_{i=1}^4a_iui(x)\sum{i=1}^4a_ivi(x) – \sum{i=1}^4a_iw_i(x)}{t(x)} $$

QAP 中相对于 R1CS 大小的多项式的度数

关于一般情况下多项式的度数，有以下几点观察：

• $u(x)$ 和 $v(x)$ 的度数可能高达 $n – 1$，因为它们插值 $n$ 个点，其中 $n$ 是 R1CS 中的行数。
• 如果多项式的总和 $\sum_{i=0}^m a_iw_i(x)$ 得到零多项式，则 $w(x)$ 的度数可能低至 0，即系数相互抵消。
• $t(x)$ 按定义是度数 $n$。
• 乘法多项式会把它们的度数相加，而除法多项式则会把它们的度数相减。

因此，$h(x)$ 的度数最多为 $n – 2$，因为

$$\underbrace{n – 1}{ \deg{u(x)}} + \underbrace{n – 1}{\deg{v(x)}} – \underbrace{n}_{\deg{t(x)}} = n – 2$$

扩展项

如果我们展开之前示例中的和，我们得到以下结果

$$ \begin{align} \sum_{i=1}^4 a_iu_i(x) &= a1(u{12}x^2 + u{11}x+u{10}) + a2(u{22}x^2 + u{21}x+u{20}) + a3(u{32}x^2 + u{31}x+u{30}) + a4(u{42}x^2 + u{41}x+u{40})\\ &= (a1u{12}+a2u{22}+a3u{32}+a4u{42})x^2 + (a1u{11}+a2u{21}+a3u{31}+a4u{41})x + (a1u{10}+a2u{20}+a3u{30}+a4u{40})\\ &=u{2a}x^2+u{1a}x+u{0a}\\ \sum{i=1}^4 a_iv_i(x) &= a1(v{12}x^2 + v{11}x+v{10}) + a2(v{22}x^2 + v{21}x+v{20}) + a3(v{32}x^2 + v{31}x+v{30}) + a4(v{42}x^2 + v{41}x+v{40})\\ &= (a1v{12}+a2v{22}+a3v{32}+a4v{42})x^2 + (a1v{11}+a2v{21}+a3v{31}+a4v{41})x + (a1v{10}+a2v{20}+a3v{30}+a4v{40})\\ &=v{2a}x^2+v{1a}x+v{0a}\\ \sum{i=1}^4 a_iw_i(x) &= a1(w{12}x^2 + w{11}x+w{10}) + a2(w{22}x^2 + w{21}x+w{20}) + a3(w{32}x^2 + w{31}x+w{30}) + a4(w{42}x^2 + w{41}x+w{40})\\ &= (a1w{12}+a2w{22}+a3w{32}+a4w{42})x^2 + (a1w{11}+a2w{21}+a3w{31}+a4w{41})x + (a1w{10}+a2w{20}+a3w{30}+a4w{40})\\ &=w{2a}x^2+w{1a}x+w_{0a}\\ \end{align} $$

在每个情况下，由于我们在添加 4 个度数为 2 的多项式，所以我们得到的是一个度数为 2 的多项式。

通常表达式 $\sum_{i=1}^m a_ip_i(x)$ 产生的多项式最多与 $p(x)$ 具有相同的幂...