玩转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 中，向量的条目在 $Z_q$ 中，而在模块 SIS 中，条目在多项式环 $R_q$ 中，我们稍后将定义它。

更正式地说，根据 M-SIS，假设一个具有 $R_q$ 中条目的格 $B$，很难找到一个向量 $\vec{x} \in R^n$，使得 $B \cdot \vec{x} = \vec{0} \mod q$，并且 $0 < |\vec{x}| \leq \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 = Z_q[X]/(X^{d}+1)$

本质上，它包含所有次数高达 $d-1$ 的多项式，系数在 $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)$。

我们将对环元素使用粗体字母 $\mathbf{a} \in R_q$，对环元素向量使用粗体向量 $\vec{\mathbf{a}} = (\mathbf{a}_1, \mathbf{a}_2, \dots, \mathbf{a}_n) \in R_q^n$，对 $Z_q$ 元素使用常规字体。我们还可以用它们的系数向量 $\vec{a} = (a_0, a1, \dots, a{d-1}) \in Z_q^d$ 来表示环元素。

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

$|\mathbf{a}| = |\mathbf{a}|_2 = \sqrt{|a0|^2 + \dots + |a{d-1}|^2}$

对于环元素的向量，定义为：

$|\vec{\mathbf{a}}| = |\vec{\mathbf{a}}|_2 = \sqrt{|\mathbf{a}_1|^2 + \dots + |\mathbf{a}_n|^2}$

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

$\langle \vec{\mathbf{a}}, \vec{\mathbf{b}} \rangle = \mathbf{a}_1\mathbf{b}_1 + \dots + \mathbf{a}_n\mathbf{b}_n$

主要关系

正如我们已经提到的，LaBRADOR 允许证明者证明其知道 $r$ 个（短）向量 $\vec{s}_i$，这些向量满足一些点积约束。一个语句是一组约束，正式定义为一组函数 $f: R_q^n \times R_q^n \times \dots \times R_q^n \rightarrow 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 \leq \beta^2$，其中 $\beta$ 是一个固定的界限。对于此版本的协议，我们将假设我们有一个交互式子协议 $\text{NormCheck}({\vec{s}_i}, \beta^2)$，它可以说服验证者这是正确的。

交互开始于证明者逐个计算 $\vec{s}_i$ 的承诺，即 $\vec{t}_i = A\vec{s}_i$，并将 $\vec{t}_i$ 发送给验证者。

然后，在证明者和验证者之间执行子协议 $\text{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 + \dots + c_r\vec{s}_r$

验证者检查：

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

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

最后，验证者将通过检查以下内容来检查约束是否满足：

$\langle \vec{z}, \vec{z} \rangle =? \sum{i,j=1}^{r} g{ij}c_icj, \quad \sum{i=1}^{r} \langle \vec{\phi}_i, \vec{z} \rangle ci =? \sum{i,j=1}^{r} h_{ij}c_icj, \quad \sum{i,j=1}^{r} a{ij}g{ij} + \sum{i=1}^{r} h{ii} - b =? 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$。如果我们只有与 R1CS 中一样的一个我们关心的（短）向量 $\vec{s}$ 作为见证，我们该怎么办？我们可以简单地将向量 $\vec{s}$ 分成 $r$ 块。“短”实际上就是考虑到这一点来定义的，因为 $\sum{i=1}^{r} |\vec{s}_i|_2^2 \leq \beta^2 \iff |\vec{s}|_2^2 \leq \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}| \leq \gamma$。此界限取决于所需的安全性级别，并且与承诺的维度 $\kappa$ 相关。

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

• 外部承诺中承诺的向量很短，即：$|\vec{t}| \leq \gamma_1$ 并且 $|\vec{g}|^2 + |\vec{h}|^2 \leq \gamma_2$
• 向量 $\vec{z}$ 很小，即：$|\vec{z}| \leq \gamma$。

使用我们到目前为止提出的协议，这是一个问题。例如，虽然诚实的证明者实际上知道短向量 $\vec{s}_i$，但不能保证承诺 $\vec{t}_i = A\vec{s}_i$ 很短，因为 $A$ 是一个均匀随机矩阵，因此他们无法使用外部承诺来承诺它。

为了处理这个问题，LaBRADOR 执行分解。根据某个基数 $b$，将向量中每个环元素的 $Z_q$ 中的系数分解。例如，对于基数 $b_1$：

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

因此，我们现在有 $t1$ 个向量，其系数在 $Z{b_1}$ 中，我们可以将它们连接起来以获得 $\vec{t}_i' \in R_q^{\kappa \cdot t_1}$。对于 $b_1$ 的合适选择，这现在是一个短向量，证明者可以承诺这一点以获得有约束力的 Ajtai 承诺。类似地，对于 $\vec{g}, \vec{h}$。

注意

LaBRADOR 使用以中心表示的分解，这意味着系数将在 $[-\frac{b_1}{2}, \dots, 0, \dots, \frac{b_1}{2}]$ 中，而不是常用的 $[0, \dots, b_1-1]$ 中。 这是 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$，这些承诺被发送给验证者。

证明者和验证者参与 $\text{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 =? B\vec{t}', \quad \vec{u}_2 =? 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$ 为界。

让我们进入细节，看看它在实践中是如何运作的。

首先，请注意，我们正在使用 $Z_q^n$ 中的向量，这意味着投影将应用于系数的“展平”向量 $\vec{s}_i \in Z_q^{nd}$，而不是 $\vec{s}_i \in R_q^n$。

投影矩阵将是 $\Pi: Z_q^{nd} \rightarrow 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| \leq |\vec{p}_i| \leq 337|\vec{s}_i|$

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