玩转 LaBRADOR：利用递归构建紧凑的基于格的证明

在上一篇博客文章中，我们介绍了 Greyhound，一种基于标准格假设的多项式承诺方案。在最后一步，我们看到实际上可以将 Greyhound 表达为一系列点积约束。这使我们能够使用一种名为 LaBRADOR 的证明系统，该系统在一篇更早的论文中被提出，对于这类约束系统具有次线性的证明大小。在这篇博客文章中，我们将讨论 LaBRADOR 及其核心思想。

LaBRADOR 是格基证明领域的一项重要改进，它表明在后量子系统中，除了基于哈希的证明系统之外，还存在一种实用的替代方案。它是透明的，证明者和验证者时间都是线性的，并通过递归实现了次线性的证明大小（对于 $n$ 个 R1CS 约束为 $O(\log n)$）。目前已有多个库实现了 LaBRADOR，例如 Lattirust/Labrador、LaZeR、icicle-labrador 以及 Lazarus。

高层概览

在深入 LaBRADOR 的细节之前，我们先从非常高的层面概览一下协议，以把握其主要思想。

证明者希望证明自己知道一些满足特定点积约束的（短）向量 $\vec{s}_i$。首先，证明者对这些向量以及这些点积进行承诺。

然后，验证者需要检查这些承诺是否被正确计算，以及点积约束是否确实满足。与其要求所有 $\vec{s}_i$ 的打开并逐一检查，验证者会要求证明者提供它们的随机线性组合（称为 摊销打开）。这只是一个向量 $\vec{z}$，现在验证者只需要用它来检查承诺和约束。

这里的关键观察是：验证者最后的检查其实只是另一个点积检查的案例，只不过见证是 $\vec{z}$（以及一些其他项）。这意味着我们可以再次运行协议来完成这个检查，而此时的见证比之前更短。在实践中，为了获得最佳结果，这种递归会运行六到七次。

当然，这只是协议的轮廓。实际上，我们省略了这类格基方案中的一个关键部分：检查这些向量确实是短的。我们稍后会处理这个问题，并且正如我们将看到的，这可能非常棘手。

但首先，介绍一些背景。

格假设

关于格、其困难问题以及密码学中使用的一些假设的简要介绍，请参阅我们关于 Greyhound 的博客文章。在本文中，我们将使用 M-SIS 问题和 Ajtai 承诺。

LaBRADOR 基于 模块短整数解（M-SIS）问题。

SIS 问题是要在一个矩阵中寻找向量的线性组合，使其结果为零向量。这个线性组合不能是平凡的（即不能是零向量），并且标量必须很小（即必须小于某个定义的界）。在普通 SIS 中，向量的元素属于 $\mathbb{Z}_q$，而在模块 SIS 中，元素属于一个多项式环 $R_q$，我们稍后会定义它。

更正式地说，根据 M-SIS，给定一个元素在 $R_q$ 中的格 $B$，找到一个向量 $\vec{x}\in R_q^n$ 使得 $B\cdot \vec{x}=\vec{0}\mod q$，且满足 $0<|\vec{x}|\le \beta$ 是困难的。我们将在后文定义 LaBRADOR 中使用的范数 $|\cdot|$。

Ajtai 承诺

Ajtai 承诺是 LaBRADOR 的核心。我们在上一篇博客文章中更详细地介绍了它们。

回顾一下，要使用一个（公开的）矩阵 $A$ 对一个短向量 $\vec{s}$ 进行承诺，证明者必须将承诺计算为 $\vec{t}=A\vec{s}\in R_q^\kappa$。

注意

该承诺的维度 $\kappa$ 可以远小于 $\vec{s}$ 的维度。还要注意，$\kappa$ 是根据所需的安全级别来选择的，并不依赖于 $\vec{s}$ 的维度，这对于使用 Ajtai 承诺的构造在渐近复杂度上非常有利。

绑定性基于 M-SIS 问题。为同一个承诺 $\vec{t}$ 寻找第二个打开 $\vec{s},'$ 会推出 $A(\vec{s}-\vec{s},')=0$。因此，$(\vec{s}-\vec{s},')$ 将构成 M-SIS 问题的一个非平凡解。

多项式环

LaBRADOR 使用的多项式环定义为：

$$ R_q=\mathbb{Z}_q[X]/(X^d+1) $$

本质上，它包含所有次数不超过 $d-1$ 的多项式，其系数在 $\mathbb{Z}_q$ 中，且其元素之间的运算都在 $X^d+1$ 下取模。实践中，LaBRADOR 使用 $d=64$。

将多项式运算结果对 $X^d+1$ 取模的一个快速方法，是用 $-1$ 替换 $X^d$（注意在环中 $X^d+1\equiv 0\iff X^d\equiv -1$）。

注意

使用多项式环是格基密码学中的常见做法。它使我们能够利用它们所具有的“结构”，从而使诸如乘法之类的运算在相同安全级别下比其整数对应运算更高效。 回想一下，多项式乘法在某些条件下可以非常高效，例如使用数论变换（NTT），复杂度为 $O(n\log n)$，而朴素方法为 $O(n^2)$。

我们将用粗体字母表示环元素 $a\in R_q$，用粗体向量表示由环元素组成的向量 $\vec{a}=(a_1,a_2,\dots,a_n)\in R_q^n$，并用普通字体表示 $\mathbb{Z}q$ 元素。我们也可以用系数向量来表示环元素 $\vec{a}=(a_0,a_1,\dots,a{d-1})\in \mathbb{Z}_q^d$。

在 LaBRADOR 中，“短”指的是 $\ell_2$-范数，其对环元素定义为：

$$ |a|=|a|_2=|a_0|2+\cdots+|a{d-1}|_2 $$

而对环元素向量定义为：

$$ |\vec{a}|=|\vec{a}|_2=|a_1|_2+\cdots+|a_n|_2 $$

我们还定义点积 $\langle\cdot,\cdot\rangle:R_q^n\times R_q^n\to R_q$ 为：

$$ \langle \vec{a},\vec{b}\rangle=a_1b_1+\cdots+a_nb_n $$

主关系

正如我们已经提到的，LaBRADOR 允许证明者证明自己知道 $r$ 个满足某些点积约束的（短）向量 $\vec{s}_i$。一个陈述是一组约束，形式上定义为一组函数 $f:R_q^n\times R_q^n\times\cdots\times R_q^n\to R_q^n$，其形式为：

$$ f(\vec{s}_1,\vec{s}2,\dots,\vec{s}r)=\sum{i,j=1}^r a{i,j}\langle \vec{s}_i,\vec{s}j\rangle+\sum{i=1}^r\langle \vec{\phi}_i,\vec{s}_i\rangle-b $$

我们可以看到，这些约束可以非常灵活。第一个求和项可以捕捉 $\vec{s}_i$ 之间的交叉相互作用，而第二个求和项捕捉各个 $\vec{s}_i$ 的单独项。这让人联想到其他允许这种二次约束的约束系统，例如 R1CS。事实上，任何 R1CS 实例都可以转换为此系统。

形式化地说，我们的约束系统将是一族这样的函数 $F$，而我们的主关系将是：

$$ R={(F,(\vec{s}_1,\vec{s}_2,\dots,\vec{s}_r))\mid f(\vec{s}_1,\vec{s}_2,\dots,\vec{s}_r)=0\ \forall f\in F,\ \vec{s}_i\text{ 短}} $$

同样，我们将把“短”的含义推迟到后面再讨论。为简化起见，我们也省略一种特殊类型的约束，即我们只关心常数项的情况。

现在我们可以给出主协议的一个基本版本。

一个（简化的）主协议

首先，我们定义“短” $\vec{s}_i$ 为满足 $\sum_i |\vec{s}_i|_2\le \beta^2$，其中 $\beta$ 是一个固定界。对于该版本的协议，我们假设存在一个交互式子协议 NormCheck(${\vec{s}_i},\beta^2$)，它能使验证者确信这一点成立。

交互从证明者逐一计算对 $\vec{s}_i$ 的承诺开始，也就是 $\vec{t}_i=A\vec{s}_i$，并将 $\vec{t}_i$ 发送给验证者。

然后，在证明者和验证者之间执行子协议 NormCheck(${\vec{s}_i},\beta^2$)。

接下来，协议必须处理这些约束。为此，证明者将计算并发送以下内容，对 $i,j=1,\dots,r$：

• $g_{ij}=\langle \vec{s}_i,\vec{s}_j\rangle$
• $h_{i,j}=\frac{1}{2}(\langle \vec{\phi}_i,\vec{s}_j\rangle+\langle \vec{\phi}_j,\vec{s}_i\rangle)$

验证者从挑战空间 $C\subset R_q$ 中采样 $r$ 个挑战 $c_1,c_2,\dots,c_r$ 并发送给证明者。

注意

挑战空间 $C$ 必须选择得使所有成对差值 $c_i-c_j$ 在 $R_q$ 中可逆。这对于证明系统的安全性很重要。更正式地说，这对于提取器的存在是必要的，从而可以证明知识可靠性。 实践中，这类挑战可以通过固定一些系数并反复采样，直到挑战的范数小于某个阈值来获得。

然后证明者将执行所谓的 摊销打开。也就是说，不是发送所有 $\vec{s}_i$ 的打开并让验证者检查它们，而是计算并发送线性组合：

$$ \vec{z}=c_1\vec{s}_1+\cdots+c_r\vec{s}_r $$

验证者检查：

$$ A\vec{z}\stackrel{?}{=}\sum_{i=1}^r c_i\vec{t}_i $$

这本质上是一个批量验证，验证这些承诺是否由证明者正确计算。为了安全性，验证者还需要检查 $\vec{z}$ 是短的。

最后，验证者将通过检查以下等式来判断约束是否满足：

$$ \langle \vec{z},\vec{z}\rangle\stackrel{?}{=}\sum_{i,j=1}^r g_{ij}c_ic_j,\quad \sum_{i=1}^r\langle \vec{\phi}i,\vec{z}\rangle c_i\stackrel{?}{=}\sum{i,j=1}^r h_{ij}c_ic_j,\quad \sum_{i,j=1}^r a_{ij}g_{ij}+\sum_{i=1}^r h_{ii}-b\stackrel{?}{=}0 $$

这三个检查验证了 $g_{ij}$ 和 $h_{ij}$ 是否由证明者正确计算，以及主关系是否成立。

这就完成了协议的一个基本版本。然而，显然这并不高效。证明者一开始必须发送所有承诺，然后发送多项式 $g_{ij},h_{ij}$，它们是 $O(r^2)$ 个环元素。验证者接着必须显式检查这些点积约束。好的一面是，我们没有逐一检查所有约束和承诺，而是通过摊销打开技术减少了检查次数。

注意

我们在这里假设只有一个约束 $f$ 来描述协议。不过这仍然是准确的，因为在完整协议中，所有函数会通过取随机线性组合而聚合为一个。

递归：第一种方法

仔细观察，我们可以看到验证者需要做的检查是一组涉及 $\vec{z}$、$\vec{t}i$ 以及多项式 $g{ij},h_{ij}$ 的点积。我们还注意到，摊销打开使我们的“主”见证 ${\vec{s}_i}$ 缩小了 $r$ 倍，因为我们把 $r$ 个向量折叠成了一个。与其让验证者显式计算并检查这些点积，为什么不再次运行协议，并把这些点积作为约束，而以 $\vec{z}$ 作为见证呢？

这就是 LaBRADOR 的核心思想。与其直接检查，不如用新的见证 $\vec{z}$ 递归地运行协议。

注意

我们将该关系的见证定义为 $r$ 个（短）向量 $\vec{s}i$ 的集合。如果我们关心的见证只有一个（短）向量 $\vec{s}$，而不是许多个这样的向量，就像 R1CS 中那样，我们该怎么做？我们只需把向量 $\vec{s}$ 切分成 $r$ 个块即可。实际上，“短”的定义正是考虑到这一点，因为 $\sum{i=1}^r |\vec{s}_i|_2^2\le \beta^2\iff |\vec{s}|_2^2\le \beta^2$。对于递归，我们可以完全这样做：先把所有不同的见证部分连接起来，然后再切分成 $r$ 个块。

不过需要注意的是，$r$ 的选择会直接影响证明系统的效率。较大的 $r$ 会让摊销打开大幅缩小主见证，但也会增加多项式 $g_{ij},h_{ij}$ 的数量，而这是 $O(r^2)$。 实践中，对于第 $i+1$ 轮，会将 $r_{(i+1)}$ 选为 $O(|\vec{s}_{(i)}|^{1/3})$，从而得到 $O(\log\log n)$ 轮递归。

充分利用递归

虽然我们现在在验证的最后一步受益于递归，但仍有改进空间。就目前而言，证明者仍然需要发送所有承诺 $\vec{t}i$ 以及所有多项式 $g{ij},h_{ij}$，这仍然是相当大的通信量。

LaBRADOR 通过使用 外部承诺 来充分利用递归。外部承诺本质上就是对承诺的承诺。正如我们所见，Ajtai 承诺是“压缩型”的，这意味着通过发送这些外部承诺，总通信量（在非交互式情况下就是证明大小）会降低。

如果验证者必须显式检查这些外部承诺是否被正确计算，那么这就意义不大了。然而在我们的情形中，我们可以把这些检查作为递归中的约束，并把 $\vec{t}i,g{ij},h_{ij}$ 放入见证。

更严格地说，会有用于承诺 $\vec{t}i$ 的外部承诺，也会有用于多项式 $g{ij},h_{ij}$ 的外部承诺。证明者将发送：

$$ \vec{u}_1=B\vec{t}\in R_q^{\kappa_1},\quad \vec{u}_2=C\vec{g}+D\vec{h}\in R_q^{\kappa_2} $$

其中 $\vec{t}$ 是所有 $\vec{t}i$ 的拼接，而 $\vec{g},\vec{h}$ 分别是包含 $g{ij},h_{ij}$ 的向量。

现在，上面描述的简化协议看起来大体相同，只是这些外部承诺被发送出来，并且验证者需要额外检查两个方程，正如上面所示。新的见证将是 $(\vec{z},\vec{t},\vec{g},\vec{h})$。

处理 Ajtai 承诺的细节

到目前为止，在这篇文章中我们基本上忽略了 Ajtai 承诺的一个关键部分，也就是 LaBRADOR 的一个关键部分。我们还没有定义被承诺的向量“短”到底意味着什么，也没有定义验证者如何检查这一点。回顾一下，如果这不成立，那么承诺就不会是绑定的。

不出所料，对于某个界 $\gamma$，我们希望被承诺的向量 $\vec{x}$ 满足范数 $|\vec{x}|\le \gamma$。这个界取决于所需的安全级别，并与承诺的维度 $\kappa$ 有关。

在 LaBRADOR 中，$\vec{s}_i$ 的短性通过 NormCheck 子协议来检查。到目前为止我们还没有检查的是：

• 在外部承诺中被承诺的向量是短的，即：$|\vec{t}|\le \gamma_1$ 且 $|\vec{g}|_2+|\vec{h}|_2\le \gamma_2$
• 向量 $\vec{z}$ 是小的，即：$|\vec{z}|\le \gamma$

按照我们目前给出的协议，这是个问题。例如，虽然诚实证明者实际上知道短向量 $\vec{s}_i$，但并不能保证承诺 $\vec{t}_i=A\vec{s}_i$ 是短的，因为 $A$ 是一个均匀随机矩阵，所以他们无法用外部承诺对其做承诺。

为了解决这个问题，LaBRADOR 进行 分解。向量中每个环元素在 $\mathbb{Z}_q$ 中的系数会根据某个基 $b$ 被分解。例如，对于基 $b_1$：

$$ \vec{t}_i=\vec{t}_i(0)+\vec{t}_i(1)b_1+\cdots+\vec{t}_i(t_1-1)b_1^{t_1-1} $$

结果，我们现在有了 $t_1$ 个系数在 $\mathbb{Z}_{b_1}$ 中的向量，并且可以把它们连接起来得到 $\vec{t},'_i\in R_q^{\kappa\cdot t_1}$。对于合适的 $b_1$ 选择，这现在就是一个短向量，证明者可以对其做承诺以获得一个绑定的 Ajtai 承诺。$\vec{g},\vec{h}$ 也是同理。

注意

LaBRADOR 使用带中心代表元的分解，这意味着系数将位于 $\left[-\frac{b_1}{2},\dots,0,\dots,\frac{b_1}{2}\right]$，而不是常用的 $\left[0,\dots,b_1-1\right]$。 下面是 Python 中的分解算法（小端序）：

def decompose(num, b):
    if num == 0:
        return [0]

    mid = b // 2
    res = list()

    while num != 0:
        m = num % b
        if m > mid:
            m = m - b
        res.append(m)
        num = (num - m) // b

    return res

对于实际的范数检查，我们只需在以这些向量作为见证递归协议时设置一个合适的界 $\beta'$。

顺便说一下，向量 $\vec{z}$ 在递归之前也会被分解成两部分，不是因为它会被承诺，而是因为反复折叠它会很快使其系数膨胀。这会稍微改变 $\langle \vec{z},\vec{z}\rangle$ 的检查，如我们很快会看到的那样。

新的主协议

将前几节详细说明的所有优化整合起来，我们现在可以给出一个非常接近最终版本的主协议。

证明者首先像之前一样计算承诺 $\vec{t}i$，并且还计算多项式 $g{ij},h_{ij}$。然后，他们将这些内容进行分解，并生成外部承诺 $\vec{u}_1,\vec{u}_2$，发送给验证者。

证明者和验证者像之前一样进行 NormCheck(${\vec{s}_i},\beta^2$) 子协议。

验证者采样并发送挑战 $c_1,c_2,\dots,c_r\in C$。

证明者像之前一样响应 $\vec{z}$。

最后，验证者必须执行与简化版本相同的检查，但有一些细微差别：

• 对 $\langle \vec{z},\vec{z}\rangle$ 的检查将变为 $\langle \vec{z}(0),\vec{z}(0)\rangle+2b\langle \vec{z}(1),\vec{z}(0)\rangle+b^2\langle \vec{z}(1),\vec{z}(1)\rangle$，因为在递归之前 $\vec{z}$ 被分解为 $\vec{z}(0)+b\vec{z}(1)$
• 还要增加两个检查，以确认外部承诺被正确计算：

$$ \vec{u}_1\stackrel{?}{=}B\vec{t},' ,\quad \vec{u}_2\stackrel{?}{=}C\vec{g},'+D\vec{h},' $$

递归会把上述检查作为约束。见证将是 $(\vec{z}(0),\vec{z}(1),\vec{t},',\vec{g},',\vec{h},')$，而范数界 $(\beta')^2$ 将是上一节中我们看到的各个界的综合。

NormCheck 子协议

用于检查向量 $\vec{s}_i$ 确实是短的子协议，是 LaBRADOR 的核心部分之一。这样的子协议实际上存在于大多数基于格的证明系统中，因为基于 M-SIS 假设的承诺方案要求被承诺的向量必须是短的，才能保证它们是绑定的。

LaBRADOR 使用一种基于模化 Johnson-Lindenstrauss 引理 的协议。这个引理说明，如果我们使用一个随机投影矩阵 $\Pi$（从特定分布中抽取）将向量 $\vec{s}$ 投影到更低维空间，那么投影向量 $\vec{p}$ 的 $\ell_2$-范数将与原始向量 $\vec{s}$ 的 $\ell_2$-范数相差一个明确定义的范围。

这种投影在降低维度的同时还能（几乎）保留原始向量的范数。这对我们的使用场景非常有用：验证者可以发送随机投影矩阵 $\Pi_i$，而证明者可以回复投影后的向量 $\vec{p}_i$。然后验证者可以检查 $|\vec{p}_i|$ 是否在允许范围内并接近界 $\beta$。由于 JL 引理，这将意味着原始的 $\vec{s}_i$ 也被 $\beta$ 所约束。

让我们深入细节，看看它在实践中如何工作。

首先，请注意我们处理的是 $\mathbb{Z}_q^n$ 中的向量，这意味着投影不是应用于 $\vec{s}_i\in R_q^n$ 本身，而是应用于其“展开”后的系数向量 $\vec{s}_i\in \mathbb{Z}_q^{nd}$。

投影矩阵将是 $\Pi:\mathbb{Z}_q^{nd}\to \mathbb{Z}_q^{256}$。它是一个随机矩阵，其元素可以是 $0,1,-1$，对应概率分别为 $\frac{1}{2},\frac{1}{4},\frac{1}{4}$。

投影按 $\vec{p}_i=\Pi\cdot \vec{s}_i$ 计算。模化 Johnson-Lindenstrauss 引理的重要结论是，以极高概率：

$$ 30|\vec{s}_i|\le |\vec{p}_i|\le 337|\vec{s}_i| $$

LaBRADOR 使用这一点来检查 $\vec{s}_i$ 的范数，而证明者只需为每个向量发送一个维度为 256 的向量。若 $|\vec{p}_i|\le 128\beta$，验证者就接受。对于一个范数接近 $\beta$ 的诚实执行，这以大约 $1/2$ 的概率成立，因此诚实证明者可以请求新的投影矩阵直到通过为止。

注意

在这个检查可能接受的范围与实际界之间，存在一点松弛。具体而言，这里大约是 $\frac{128}{30}\approx 2.07$。 为了直观理解为什么会这样，假设一个作弊证明者的向量 $\vec{s}^{}$ 的范数为 $b' > \beta$。我们想看看证明者最多能“蒙混过关”到多大的 $b'$。 对于作弊证明者来说，最好的情况是随机投影取得尽可能小的范数。根据 JL 引理，这会是 $30b'$。为了让检查通过，必须满足 $|\vec{p}_i^|\le 128\beta \implies 30b'\le 128\beta \implies b'\le \frac{128}{30}\beta$。 因此，作弊证明者成功时 $b'$ 的最大值是 $b'=\frac{128}{30}\beta$，这大约比所需界 $\beta$ 大 2 倍。LaBRADOR 通过选择合适的参数和界来弥补这一点，即使存在这个松弛因子，也能确保所需的安全级别。

将子协议整合进去

这种方法与 LaBRADOR 非常契合，因为投影本质上就是投影矩阵各行与展开后的向量 $\vec{s}_i$ 之间的一系列点积。通过将这些点积作为约束加入系统，验证者可以以很小的开销检查投影是否被正确计算。

因此，主协议中上面的交互式子协议 NormCheck 会被替换为：验证者发送随机投影矩阵，而证明者计算投影并回复投影后的向量 $\vec{p}_i$。

在论文所描述的主关系中，还有一个我们只是顺带提到的小优化：有一组约束 $f'$，我们只关心常数项。然后，这些约束通过取随机线性组合被聚合到主约束 $F$ 中。用于正确计算投影的约束实际上就是这类约束。

最后说明

我们介绍了 LaBRADOR，这是一种基于标准格假设的证明系统，它利用递归实现了次线性证明大小。

LaBRADOR 论文包含了各种优化以及关于界的讨论，还包括从 R1CS 到主关系的归约，这些内容与我们在这里选择并介绍的概念同样重要。我们强烈建议阅读论文以更深入地理解该协议。

zkSecurity 提供密码学系统的审计、研究和开发服务，包括零知识证明、MPC、FHE 和共识协议。

了解更多 →

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