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

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

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

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

如果向量 $\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_iu_i(x)\sum_{i=1}^4a_iv_i(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*} u_1(x) = \mathcal{L}(\mathbf{L}{(*,1)}) =u{12}x^2 + u_{11}x+u_{10}\\ u_2(x) = \mathcal{L}(\mathbf{L}{(*,2)}) =u{22}x^2 + u_{21}x+u_{20}\\ u_3(x) = \mathcal{L}(\mathbf{L}{(*,3)}) =u{32}x^2 + u_{31}x+u_{30}\\ u_4(x) = \mathcal{L}(\mathbf{L}{(*,4)}) =u{42}x^2 + u_{41}x+u_{40}\\ \end{align*} $$

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

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

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

$$ \begin{align*} v_1(x) = \mathcal{L}(\mathbf{O}{(*,1)}) =v{12}x^2 + v_{11}x+v_{10}\\ v_2(x) = \mathcal{L}(\mathbf{O}{(*,2)}) =v{22}x^2 + v_{21}x+v_{20}\\ v_3(x) = \mathcal{L}(\mathbf{O}{(*,3)}) =v{32}x^2 + v_{31}x+v_{30}\\ v_4(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_iu_i(x)\sum_{i=1}^4a_iv_i(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_iu_i(x)\sum_{i=1}^4a_iv_i(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) &= a_1(u_{12}x^2 + u_{11}x+u_{10}) + a_2(u_{22}x^2 + u_{21}x+u_{20}) + a_3(u_{32}x^2 + u_{31}x+u_{30}) + a_4(u_{42}x^2 + u_{41}x+u_{40})\\ &= (a_1u_{12}+a_2u_{22}+a_3u_{32}+a_4u_{42})x^2 + (a_1u_{11}+a_2u_{21}+a_3u_{31}+a_4u_{41})x + (a_1u_{10}+a_2u_{20}+a_3u_{30}+a_4u_{40})\\ &=u_{2a}x^2+u_{1a}x+u_{0a}\\ \sum_{i=1}^4 a_iv_i(x) &= a_1(v_{12}x^2 + v_{11}x+v_{10}) + a_2(v_{22}x^2 + v_{21}x+v_{20}) + a_3(v_{32}x^2 + v_{31}x+v_{30}) + a_4(v_{42}x^2 + v_{41}x+v_{40})\\ &= (a_1v_{12}+a_2v_{22}+a_3v_{32}+a_4v_{42})x^2 + (a_1v_{11}+a_2v_{21}+a_3v_{31}+a_4v_{41})x + (a_1v_{10}+a_2v_{20}+a_3v_{30}+a_4v_{40})\\ &=v_{2a}x^2+v_{1a}x+v_{0a}\\ \sum_{i=1}^4 a_iw_i(x) &= a_1(w_{12}x^2 + w_{11}x+w_{10}) + a_2(w_{22}x^2 + w_{21}x+w_{20}) + a_3(w_{32}x^2 + w_{31}x+w_{30}) + a_4(w_{42}x^2 + w_{41}x+w_{40})\\ &= (a_1w_{12}+a_2w_{22}+a_3w_{32}+a_4w_{42})x^2 + (a_1w_{11}+a_2w_{21}+a_3w_{31}+a_4w_{41})x + (a_1w_{10}+a_2w_{20}+a_3w_{30}+a_4w_{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)$ 具有相同的幂...