从 R1CS 构建零知识证明

Last updated on Oct 31, 2024

给定一个编码为一阶约束系统（Rank 1 Constraint System）的算术电路（arithmetic circuit），我们有可能创建一个证明拥有见证（witness）的 ZK-proof，尽管它并不是简洁的（succinct）。本文将描述如何实现这一目标。

针对 R1CS 的零知识证明，其实现方式是将见证向量转换为有限域椭圆曲线点，并将每一行的阿达马乘积（Hadamard product）替换为双线性配对（bilinear pairing）。

给定一个 Rank 1 Constraint System，其中每个矩阵有 $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$ 表示逐元素乘法（阿达马乘积）。

展开后如下所示：

\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 \\ a_m \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 \\ a_m \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} a_1 l_{1,1} + \cdots + a_m l_{1,m} \\ \vdots \\ a_1 l_{n,1} + \cdots + a_m l_{n,m} \end{array} \right] \circ \left[ \begin{array}{ccc} a_1 r_{1,1} + \cdots + a_m r_{1,m} \\ \vdots \\ a_1 r_{n,1} + \cdots + a_m r_{n,m} \end{array} \right] = \left[ \begin{array}{ccc} a_1 o_{1,1} + \cdots + a_m o_{1,m} \\ \vdots \\ a_1 o_{n,1} + \cdots + a_m o_{n,m} \end{array} \right]

= \left[ \begin{array}{ccc} \sum_{i=1}^m a_i l_{1,i} \\ \sum_{i=1}^m a_i l_{2,i} \\ \vdots \\ \sum_{i=1}^m a_i l_{n,i} \end{array} \right] \circ \left[ \begin{array}{ccc} \sum_{i=1}^m a_i r_{1,i} \\ \sum_{i=1}^m a_i r_{2,i} \\ \vdots \\ \sum_{i=1}^m a_i r_{n,i} \end{array} \right] = \left[ \begin{array}{ccc} \sum_{i=1}^m a_i o_{1,i} \\ \sum_{i=1}^m a_i o_{2,i} \\ \vdots \\ \sum_{i=1}^m a_i o_{n,i} \end{array} \right]

= \begin{array}{ccc} \sum_{i=1}^m a_i l_{1,i} \sum_{i=1}^m a_i r_{1,i} = \sum_{i=1}^m a_i o_{1,i} \\ \sum_{i=1}^m a_i l_{2,i} \sum_{i=1}^m a_i r_{2,i} = \sum_{i=1}^m a_i o_{2,i} \\ \vdots \\ \sum_{i=1}^m a_i l_{n,i} \sum_{i=1}^m a_i r_{n,i} = \sum_{i=1}^m a_i o_{n,i} \end{array}

在这种设置下，我们只需向验证者（verifier）提供向量 $\mathbf{a}$ ，就可以向其证明我们拥有一个满足该 R1CS 的见证向量 $\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}

第二个矩阵乘法中两个椭圆曲线点的离散对数（discrete logs）与第一个矩阵乘法中元素的值完全相同。

换句话说，每次我们将列向量与方阵中的某一行相乘时，我们实际上是在执行两次椭圆曲线点乘法和一次椭圆曲线加法。

椭圆曲线的符号表示

我们用 $[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$ ，我们称这两个点的配对（pairing）为 $A\bullet B$ 。

证明者步骤

让我们将 $\mathbf{a}$ 向量中的每个元素乘以生成元点 $G_1$ 来对其进行加密，从而生成椭圆曲线点 $[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]

考虑到阿达马乘积将变成一系列椭圆曲线配对，我们也可以使用 $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$ 点配对在某种意义上等同于“乘以 1”，但会将 $G_1$ 点转化为 $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 G_2 \\ \sum_{i=1}^m o_{i,2}[a_i G_1]_1\bullet G_2 \\ \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 中的矩阵很大（对于有实际意义的算法而言必然如此），那么验证者将需要执行大量的配对和椭圆曲线加法运算。椭圆曲线加法相当快，但椭圆曲线配对却很慢（并且在 Ethereum 上会消耗大量的 Gas）。

然而，很高兴能看到在现阶段，零知识证明在数学上是可行的。如果你对椭圆曲线运算有很好的掌握（并且没有忘记矩阵算术），它们其实并不难理解。

让这项技术实现真正的零知识

就目前而言，我们的见证向量无法被解密，但它可以被猜测。如果攻击者（试图发现未加密见证的人）利用某些辅助信息对见证进行了合理的猜测，他们可以将猜测的见证向量乘以椭圆曲线点生成元，看看结果是否与证明者的见证向量相同，以此来验证他们的猜测。

我们将在关于 Groth16 的内容中学习如何防御见证猜测。

此外，请记住，现实世界中没有人会使用这里描述的算法，因为它实在太低效了。不过，如果你动手实现它，这将有助于你练习编写有意义的椭圆曲线算术逻辑，并构建一个功能完善的端到端（准）零知识证明系统。

你可以在此代码库中看到 Obront 对本文描述算法的一个示例实现。

通过 RareSkills 了解更多

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

原文首发于 2023 年 8 月 26 日