从R1CS构建零知识证明

给定一个算术电路，可以将其编码为等级1约束系统，从而创建一个有见证的ZK证明，尽管不是简洁的。本文描述了如何实现这一点。

对于R1CS的零知识证明是通过将见证向量转换为有限域椭圆曲线点，并将Hadamard乘积替换为每一行的双线性配对。

给定一个等级1约束系统，其中每个矩阵有$n$行和$m$列，我们将其表示为

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

其中 $\mathbf{L}$, $\mathbf{R}$, $\mathbf{O}$ 是具有 $n$ 行和 $m$ 列的矩阵，而 $\mathbf{a}$ 是见证向量（包含算术电路中每个信号的满足赋值）。向量 $\mathbf{a}$ 具有1列和$m$行，$\circ$是逐元素相乘（Hadamard乘积）。

扩展形式看起来是

$$ \left[ \begin{array}{ccc} l{1,1} & \cdots & l{1,m} \\ \vdots & \ddots & \vdots \\ l{n,1} & \cdots & l{n,m} \end{array} \right] \left[ \begin{array}{c} a_1 \\ \vdots \\ am \end{array} \right] \circ \left[ \begin{array}{ccc} r{1,1} & \cdots & r{1,m} \\ \vdots & \ddots & \vdots \\ r{n,1} & \cdots & r_{n,m} \end{array} \right] \left[ \begin{array}{c} a_1 \\ \vdots \\ am \end{array} \right] = \left[ \begin{array}{ccc} o{1,1} & \cdots & o{1,m} \\ \vdots & \ddots & \vdots \\ o{n,1} & \cdots & o_{n,m} \end{array} \right] \left[ \begin{array}{c} a_1 \\ \vdots \\ a_m \end{array} \right] $$

$$ = \left[ \begin{array}{ccc} a1 l{1,1} + \cdots + am l{1,m} \\ \vdots \\ a1 l{n,1} + \cdots + am l{n,m} \end{array} \right] \circ \left[ \begin{array}{ccc} a1 r{1,1} + \cdots + am r{1,m} \\ \vdots \\ a1 r{n,1} + \cdots + am r{n,m} \end{array} \right] = \left[ \begin{array}{ccc} a1 o{1,1} + \cdots + am o{1,m} \\ \vdots \\ a1 o{n,1} + \cdots + am o{n,m} \end{array} \right] $$

$$ = \left[ \begin{array}{ccc} \sum_{i=1}^m ai l{1,i} \\ \sum_{i=1}^m ai l{2,i} \\ \vdots \\ \sum_{i=1}^m ai l{n,i} \end{array} \right] \circ \left[ \begin{array}{ccc} \sum_{i=1}^m ai r{1,i} \\ \sum_{i=1}^m ai r{2,i} \\ \vdots \\ \sum_{i=1}^m ai r{n,i} \end{array} \right] = \left[ \begin{array}{ccc} \sum_{i=1}^m ai o{1,i} \\ \sum_{i=1}^m ai o{2,i} \\ \vdots \\ \sum_{i=1}^m ai o{n,i} \end{array} \right] $$

$$ = \begin{array}{ccc} \sum_{i=1}^m ai l{1,i} \sum_{i=1}^m ai r{1,i} = \sum_{i=1}^m ai o{1,i} \\ \sum_{i=1}^m ai l{2,i} \sum_{i=1}^m ai r{2,i} = \sum_{i=1}^m ai o{2,i} \\ \vdots \\ \sum_{i=1}^m ai l{n,i} \sum_{i=1}^m ai r{n,i} = \sum_{i=1}^m ai o{n,i} \end{array} $$

在此设置中，我们可以向验证者证明我们有一个满足R1CS的见证向量 $\mathbf{a}$，只需将向量$\mathbf{a}$提供给他们，但显然的缺陷是这不是一个零知识证明！

R1CS的零知识证明算法

如果我们通过将每个条目与$G_1$或$G_2$相乘来“加密”见证向量，那么数学仍然有效！

为了理解这一点，考虑如果我们执行矩阵乘法

$$ \begin{bmatrix} 1 & 2 \\ 3 & 4 \\ \end{bmatrix} \begin{bmatrix} 4 \\ 5 \end{bmatrix} = \begin{bmatrix} 14 \\ 32 \end{bmatrix} $$

也可以得到：

$$ \begin{bmatrix} 1 & 2 \\ 3 & 4 \\ \end{bmatrix} \begin{bmatrix} 4G_1 \\ 5G_1 \end{bmatrix} = \begin{bmatrix} 14G_1 \\ 32G_1 \end{bmatrix} $$

第二次矩阵乘法中的两个椭圆曲线点的离散对数与第一次矩阵乘法的元素相同。

换句话说，每次我们将列向量与平方矩阵的一行相乘时，我们都会进行两个椭圆曲线点乘法和一次椭圆曲线加法。

椭圆曲线的符号

我们说 $[aG_1]_1$ 是由将域元素 $a$ 倍乘 $G_1$ 创建的 $\mathbb{G}_1$ 椭圆曲线点。我们说 $[aG_2]_2$ 是通过将 $a$ 乘以生成元 $G_2$ 生成的 $\mathbb{G}_2$ 椭圆曲线点。由于离散对数问题，我们无法从 $[aG_1]_1$ 或 $[aG_2]_2$ 中提取出 $a$。给定点 $A \in \mathbb{G}_1$ 和 $B \in \mathbb{G}_2$，我们说两个点的配对是 $A\bullet B$。

证明步骤

让我们通过将每个条目与生成元点 $G_1$ 相乘来加密我们的 $\mathbf{a}$ 向量，从而生成椭圆曲线点 $[a_iG_1]_1$。

对于矩阵 $\mathbf{L}$，我们做如下操作：

$$ \left[ \begin{array}{ccc} l{1,1} & \cdots & l{1,m} \\ \vdots & \ddots & \vdots \\ l{n,1} & \cdots & l{n,m} \end{array} \right] \left[ \begin{array}{c} [a_1 G_1]_1 \\ \vdots \\ [a_m G_1]1 \end{array} \right] = \left[ \begin{array}{ccc} l{1,1}[a_1 G_1]1 & + \cdots + & l{1,m}[a_m G_1]1 \\ \vdots & \ddots & \vdots \\ l{n,1}[a_1 G_1]1 & + \cdots + & l{n,m}[a_m G_1]1 \end{array} \right] = \left[ \begin{array}{c} \sum{i=1}^m l_{1,i}[a_i G_1]1 \\ \sum{i=1}^m l_{2,i}[a_i G_1]1 \\ \vdots \\ \sum{i=1}^m l_{n,i}[a_i G_1]_1 \end{array} \right] $$

为了 anticipate Hadamard乘积变成椭圆曲线配对，我们还可以用 $G_2$ 点加密 $\mathbf{a}$ 向量，以便验证者可以执行配对。

$$ \left[ \begin{array}{ccc} r{1,1} & \cdots & r{1,m} \\ \vdots & \ddots & \vdots \\ r{n,1} & \cdots & r{n,m} \end{array} \right] \left[ \begin{array}{c} [a_1 G_2]_2 \\ \vdots \\ [a_m G_2]2 \end{array} \right] = \left[ \begin{array}{ccc} r{1,1}[a_1 G_2]2 & + \cdots + & r{1,m}[a_m G_2]2 \\ \vdots & \ddots & \vdots \\ r{n,1}[a_1 G_2]2 & + \cdots + & r{n,m}[a_m G_2]2 \end{array} \right] = \left[ \begin{array}{c} \sum{i=1}^m r_{1,i}[a_i G_2]2 \\ \sum{i=1}^m r_{2,i}[a_i G_2]2 \\ \vdots \\ \sum{i=1}^m r_{n,i}[a_i G_2]_2 \end{array} \right] $$

完成此操作后，我们得到来自乘法 $\mathbf{L}\mathbf{a}$ 的 $G_1$ 椭圆曲线点的单列，和来自 $\mathbf{R}\mathbf{a}$ 的 $G_2$ 点的单列。

下一步的天真做法是用 $G{12}$ 点加密 $\mathbf{a}$ 向量，以便验证者可以配对 $\mathbf{L}\mathbf{a}$ 和 $\mathbf{R}\mathbf{a}$ 的结果，看它是否等于 $\mathbf{O}\mathbf{a}$，但 $G{12}$ 点相当大，因此我们宁愿让验证者配对 $G_1$ 中的 $\mathbf{O}\mathbf{a}$ 椭圆曲线点，然后将每个条目与 $G_2$ 点配对。与 $G_2$ 点的配对在某种意义上是“乘以一”，但将 $G1$ 点转变为 $G{12}$ 点。

然后，证明者将 $G_1$ 向量和 $G_2$ 向量交给验证者。

验证步骤

因此，验证步骤变为

$$\left[ \begin{array}{c} \sum{i=1}^m l{i,1}[a_i G_1]1 \\ \sum{i=1}^m l_{i,1}[a_i G_1]1 \\ \vdots \\ \sum{i=1}^m l_{i,1}[a_i G_1]1 \end{array} \right] \begin{matrix} \bullet \\ \bullet \\ \vdots \\ \bullet \end{matrix} \left[ \begin{array}{c} \sum{i=1}^m r_{i,1}[a_i G_2]2 \\ \sum{i=1}^m r_{i,1}[a_i G_2]2 \\ \vdots \\ \sum{i=1}^m r_{i,1}[a_i G_2]2 \end{array} \right]\stackrel{?}{=} \left[ \begin{array}{c} \sum{i=1}^m o_{i,1}[a_i G_1]1 \\ \sum{i=1}^m o_{i,1}[a_i G_1]1 \\ \vdots \\ \sum{i=1}^m o_{i,1}[a_i G_1]_1 \end{array} \right] \begin{matrix} \bullet \\ \bullet \\ \vdots \\ \bullet \end{matrix} \left[ \begin{array}{c} G_2 \\ G_2 \\ \vdots \\ G_2 \end{array} \right] $$

$$ = \begin{array}{c} \sum{i=1}^m l{i,1}[a_i G_1]1\bullet \sum{i=1}^m r_{i,1}[a_i G_2]2 \\ \sum{i=1}^m l_{i,2}[a_i G_1]1\bullet \sum{i=1}^m r_{i,2}[a_i G_2]2 \\ \vdots \\ \sum{i=1}^m l_{i,n}[a_i G_1]1\bullet \sum{i=1}^m r_{i,n}[a_i G_2]2 \end{array} \stackrel{?}{=} \begin{array}{c} \sum{i=1}^m o_{i,1}[a_i G_1]_1\bullet G2 \\ \sum{i=1}^m o_{i,2}[a_i G_1]_1\bullet G2 \\ \vdots \\ \sum{i=1}^m o_{i,n}[a_i G_1]_1 \bullet G_2 \end{array} $$

上述 $G_{12}$ 元素的向量在逐元素相等的情况下，只有在证明者提供了有效的见证时成立。

几乎是这样。我们将在后面的部分中讨论这一点。

首先，我们需要提到一个重要的实现细节。

公共输入

如果我们的知识声明是“我知道 $x$ 使得 $x³ + 5x + 5 = y$，其中 $y = 155$”，那么我们的见证向量可能看起来像这样：

$$[1, y, x, v]$$

其中$v = x^2$。在这种情况下，我们需要让 $[1, y]$ 成为公共的。为了实现这一点，我们只需不加密见证的前两个元素。验证者将检查公共输出，然后通过将公共输入乘以 $G_1$ 或 $G_2$ 点来加密，以便验证公式不变。

处理恶意证明者

由于向量被加密，验证者不能立即知道 $\mathbb{G}₁$ 点的向量是否与 $\mathbb{G}₂$ 点的向量加密了相同的值。

即，证明者提供了 $\mathbf{a}G_1$ 和 $\mathbf{a}G_2$。由于验证者不知道点的向量的离散对数，验证者如何知道 $\mathbb{G}₁$ 点的向量与 $\mathbb{G}₂$ 点的向量具有相同的离散对数？

验证者可以通过用相反生成元的点向量与两个点向量配对来检查离散对数的相等（而不需要知道它们），并检查结果的 $\mathbb{G}_{12}$ 点是否相等。具体为：

$$ \begin{bmatrix} a_1G_1 \\ a_2G_1 \\ \vdots \\ a_mG_1 \end{bmatrix} \begin{matrix} \bullet \\ \bullet \\ \vdots \\ \bullet \end{matrix} \begin{bmatrix} G_2 \\ G_2 \\ \vdots \\ G_2 \end{bmatrix} \stackrel{?}{=} \begin{bmatrix} a_1G_2 \\ a_2G_2 \\ \vdots \\ a_mG_2 \end{bmatrix} \begin{matrix} \bullet \\ \bullet \\ \vdots \\ \bullet \end{matrix} \begin{bmatrix} G_1 \\ G_1 \\ \vdots \\ G_1 \end{bmatrix} $$

这个算法主要是学术性的

这个算法对验证者来说非常低效。如果R1CS中的矩阵很大（对于有趣的算法来说，它们将是），那么验证者需要进行大量的配对和椭圆曲线加法。椭圆曲线加法相对较快，但椭圆曲线配对则很慢（并且在以太坊上消耗大量Gas）。

然而，目前能够看到，零知识证明是可能的，如果你对椭圆曲线操作有很好的理解（而且没有忘记你的矩阵算术），它们并不难理解。

使这项技术真正实现零知识

目前，我们的见证向量无法被解密，但它可以被猜测。如果攻击者（试图发现未加密见证的人）利用一些辅助信息对见证进行有根据的猜测，他们可以通过将猜测的见证向量乘以椭圆曲线点生成器，检查他们的工作并查看结果是否与证明者的见证向量相同。

我们将学习如何防止猜测见证问题，相关内容将在对Groth16的讲解中出现。

此外，牢记没有人在现实世界中执行上述算法，因为它过于低效。然而，如果你实现它，它将帮助你练习实现有意义的椭圆曲线算术，并构建一个功能齐全的（几乎是）零知识证明。

你可以在这个代码库中查看Obront描述的算法的示例实现。

了解更多

本材料来自我们的零知识课程。

最初发布于2023年8月26日

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