Ingonyama：一起Labrador
原文：https://hackmd.io/@Ingonyama/fast-labrador-prover
作者：Ashutosh Marwah (ash@ingonyma.com)
译者：Kurt Pan
Labrador [1] 是第一个基于格的实用 zkSNARK 协议。该协议可在实际应用所涉及的 R1CS 大小范围内生成约 50 kB 的紧凑证明。它已成为格密码学中的重要工具，并已在后量子签名聚合 [3] 等任务中得到应用。它也是迄今为止最实用的基于格的多项式承诺方案 Greyhound [2] 的基础。
本文将从头开始探索 Labrador 的构造，从简单的baby协议开始，逐步构建完整的递归 Labrador 协议。
安全性
深入研究格密码学前，重要的是要了解如何定义环上向量的范数 。对 ，定义的二范数为：
其中假设每个 。 上述右边操作是将视作实数进行的。类似地，可以定义无穷范数为：
Labrador 协议的安全性依赖于模短整数解（MSIS）假设，该假设建立在短整数解（SIS）假设之上。SIS 假设为，对于一个多项式时间（甚至量子）敌手而言，给定一个随机矩阵 ，在方程 中找到一个满足 （相对于 而言 很小）的解是计算上困难的。
MSIS 将该问题推广到了多项式环。与在 上的矩阵操作不同，MSIS 在环 上进行，其中矩阵元素是次数为 的多项式。该假设指出，对于适当选择的参数 ，在 下，寻找 且满足 与 的短解仍然是计算困难的。这里，长度为 的多项式向量 的范数通过将其视为长度为 的 元素向量来计算。
该假设可用于构造格密码学中也是 Labrador 协议中的最核心工具之一： Ajtai 承诺。假设对于参数 MSIS 问题是困难的，那么对于范数至多为 的向量 ，定义 即可作为一个具有绑定性的承诺。如果存在一个多项式时间算法能够找到两个不同的向量 ，使它们都对应同样的承诺 ，那么该算法也能解决 MSIS，因为
且 且 。
虽然我们在上述定义中使用了二范数，但在大多数参数范围内，当使用无穷范数来度量时，该问题同样是困难的。
Labrador 约束系统
假设Labrador 的见证具有形式 ，其中每个 （一个由 次多项式组成的长度为 的向量）。Labrador 中有两种约束：等式约束和常数零约束。
等式约束
一个等式约束由多项式 ，多项式向量 以及多项式 组成。当且仅当见证满足以下等式时，该约束被满足：
此处，多项式向量 与 的内积定义为
常数零约束
类似地，常数零约束由多项式 ，多项式向量 以及环元素 组成。当且仅当下式取常数项后为零时，该约束被满足：
其中 函数提取多项式的常数系数。
Labrador 协议允许证明者证明其持有满足多个等式约束和常数零约束且范数较小的见证，具体而言，对于给定的 ，满足
Labrador 论文的第 6 节 [1] 表明，可以将二进制和 上的 R1CS 约束归约到上述形式的约束。这里不赘述其细节。直观来说，上述约束是二次的，因此足够通用以描述 R1CS 约束；此外，R1CS 中见证的二进制性质能够为 Labrador 提供范数较小的见证。
高层思路
Labrador 协议采用递归方式工作。可以将其分为两部分：基础协议和递归重构。基础协议允许证明者证明其对一组等式约束和常数零约束持有见证 （这些约束可视为协议的“电路”）的知识。如果见证的总大小是 个多项式，那么基础协议生成的证明大小为 ，单独来看并不算特别小。这时递归就派上用场了。该证明所满足的关系（即验证者对基础证明的操作）依然是线性和二次约束，因此可以用上述等式约束来表示。然后可以将该证明视为另一组等式约束的见证，并对相应约束重新应用 Labrador 协议。如果对见证进行适当重构并构造相应的问题，那么递归之后的证明大小为 ，其中 是基础协议结束时证明的大小。因此，一次递归迭代后证明大小变为 。每次迭代都能迅速减少证明大小。 次迭代后，证明即可缩小到常数级 大小。对于实际相关的 R1CS 大小，仅需递归协议约 7 次，即可得到约 50 kB 的证明。
同时值得注意的是，在此协议中，验证者需要执行线性工作。这是该协议的主要缺点之一。
Baby Labrador
我们将从一个简单的协议开始，这是 Labrador 的核心，证明者能够聚合并证明约束。然后，我们会对其进行修改和改进，以支持递归。
假设证明者想要证明他拥有一个见证 （通常可以选择 ，，其中 是见证的总大小），该见证满足以下 条等式约束：
对每个 都成立；以及 条常数零约束：
对每个 都成立；并且还满足范数约束：
所有约束中的 、 和 都是公开参数，验证者也拥有。直接在这些参数上操作会使验证者工作量为线性时间。
证明者和验证者按照以下交互流程来完成证明：
对见证的 Ajtai 承诺：
对于每个 ，证明者向验证者发送
其中 是一个大小为 、元素来自多项式环 的矩阵。在此简化的基础协议中，我们仅利用这些承诺的同态性质。稍后我们将看到，Ajtai 承诺的线性特性可用于将递归实例的约束写成等式约束。
注意：此步骤中，证明者发送的消息总大小为 。可将 选为常数，因此这些消息属于亚线性规模。
2. 常数零约束聚合：
验证者向证明者发送 个随机挑战 证明者将 条常数零约束聚合为一条常数零约束，方法是对它们做随机线性组合：
因此，聚合后的参数定义为
见证需满足
验证者可自行计算该聚合约束。
这个时候，双方可以丢弃原始的 条常数零约束。直观上，如果有任一原约束未被满足，则聚合后的约束以高概率也不满足。
3. 证明者通过发送如下多项式将其转换为等式约束
并丢弃新构造的聚合常数零约束。
4. 验证者检查该多项式的常数项是否等于 。这也解释了为何随机挑战从 而非 中选取。
5. 证明者和验证者在各自的等式约束列表中添加：
安全性说明：添加约束只会增加证明者作弊的难度；且由于验证者验证了 的常数项正确性，我们可以确保聚合常数零约束已被满足。
注：为保证安全，实际操作中需要将上述聚合过程重复若干次，但为简化起见，此处省略该重复步骤。
现在只剩下等式约束。将把所有这些约束聚合成一个等式约束。设等式约束的数量为 (因为上面又添加了一条约束，所以 )。
验证者随机采样挑战多项式
并将它们发送给证明者。
最终聚合后的等式约束参数定义为：
则见证需满足：
同前一步骤，如果见证未满足任一原始等式约束，则也不会满足聚合后的约束。现在证明者只需证明其见证满足上述最终等式约束。
1. 对于 ，证明者向验证者发送：
2. 验证者检查：
此时，证明者只需证明 和 的计算是诚实的，便证明了见证满足该约束。
另外，注意此轮中证明者发送了 个多项式。通过利用对称性（，并对 做类似对称化）可将数量约减一半，但此处不做这些优化。
验证者向证明者发送挑战多项式 并要求证明者对 Ajtai 矩阵 下的承诺 进行开承诺。证明者总可以使用多项式向量 来完成开承诺。然而，如果挑战多项式“太大”，不诚实的证明者也能开承诺到其他向量，因为 Ajtai 承诺仅在输入范数较小时才具有绑定性。因此，验证者需要从某个特殊子集 中抽取挑战。该子集特意选择的，使得：
指数级大（约 ）。 对任意 和任意 ，都有对某个小正实数 （Labrador 中取 ）。
这样的挑战空间在格密码学中经常出现（例如在 Dilithium 中），以确保经挑战组合后的向量仍保持短范数。在 Labrador 中，挑战空间 由具有 23 个 0 系数、31 个 系数和 10 个 系数的多项式构成。采样时还需要利用拒绝采样以保证上述范数放大条件（条件 2）得到满足。
最后，证明者和验证者执行以下步骤：
验证者从挑战空间 中随机抽取 并发送给证明者。 证明者响应 验证者检查以下内容：以及下列等式满足：
大体上， 的范数界以及它能成功开承诺到 ，意味着 确实是由证明者诚实计算得到。其余两条等式则保证了多项式 和 的诚实性。直接将诚实的 代入可见，左侧 的系数正是诚实的 与 。由于 在大空间中随机采样，如果 或 不正确，上述等式将以高概率失效。
上述协议可形式化为一个亚线性大小的证明，表明证明者持有有效见证。注意，证明者的证明包含承诺集合 、“垃圾”多项式 以及多项式向量 。验证者在第 5.3 步中检验这些元素。很容易看出，这些验证条件（仅含二次与线性约束；其中 可视为约束定义的一部分，因为验证者已知它们）可重构为等式约束，其中见证即上述证明元素。此即 Labrador 协议的基本思路，只是此时由于 提取见证所需的范数放宽过大（约为 ），无法直接递归。为解决此问题，Labrador 中验证者使用称为 “JL 投影” 的随机投影来估计见证范数，并通过向常数零约束集中添加线性约束来确保证明者诚实计算该投影。最后，为保证每轮递归的通信量较小，证明者在每轮仅对 进行 Ajtai 承诺。
Labrador 基础协议
现在准备描述 Labrador 中使用的基础协议。此协议结束时生成的证明既可发送给验证者，也可用作下一轮递归的见证。与上述协议类似，假设证明者希望证明其持有见证 ，满足以下 条等式约束：
对每个 ；以及以下 条常数零约束：
对每个 ；且满足范数约束：
为此，证明者和验证者执行以下步骤：
Ajtai 对见证开承诺：
与 Baby Labrador 协议相同，证明者先计算承诺 。但我们希望避免直接发送所有 。因此，证明者对整个向量组 进行一次整体承诺。由于 的范数可能过大，需先将每个 分解。分解操作接受基数 和多项式向量 ，返回 ，使得其线性逆操作称为重构，可将分解结果线性重构回 。令
则有 ，该范数界限足以保证 Ajtai 承诺的绑定性。因此，证明者发送承诺 ，其大小为常数。
JL 投影：
验证者使用 Johnson–Lindenstrauss 引理来确保见证范数较小。该引理指出：对于向量 和由元素独立地以 采样的随机矩阵 ，有虽称为“JL 投影”，但它并非线性代数意义上的正交投影。具体流程：
验证者随机采样一个 的 JL 投影 并发送给证明者。 证明者将扁平化后的见证向量 投影，返回 。 验证者检查 的范数是否足够小：。 如果证明者诚实地计算了 且此检查通过，则验证者可以保证整个见证的范数小于约 。相比于上面 Baby 协议中的 ，这是显著的改进。选择界限 的原因是保证诚实的 有足够高的概率通过此测试（证明者和验证者需要对多个 重复此测试，直到通过为止）。 现在，我们必须确保证明者正确地计算了 。为此，证明者和验证者都在见证所满足的约束中添加一些约束。简单来说，证明者声称见证满足以下 方程：
这仅是对见证的 256 条线性约束，可表示为 256 条常数零约束（每行一条），其中 ， 由 的各行元素组成，。这些约束的具体形式详见论文。
其余协议步骤与上述 Baby Labrador 协议几乎相同。
证明者和验证者按照与上述 Baby 协议完全相同的方式，将他们的常数零约束聚合为等式约束。
他们同样按照 Baby 协议中的流程，将等式约束聚合为单一约束，形式如下：
如前所述，对于 Labrador 的递归轮次，证明者不再发送垃圾多项式，而是使用 Ajtai 承诺对它们进行承诺。再次注意， 和 的范数可能很大，因此需要使用合适的基（例如 和 ）对它们进行分解。假设分解后的版本存储在 和 中。然后证明者对这些向量进行承诺：
其中 和 是一些随机的公开矩阵。由于验证者并未以明文形式获得 和 ，因此他会推迟最终的约束验证。
与 Baby 协议类似，验证者从 中向证明者发送挑战多项式 。然而，此时证明者不再像之前那样发送 ，也无需对 进行承诺，因为验证者已知 。因此，从这个意义上讲，尚不存在真正的“开承诺”操作。
递归
在上述基础协议结束时，证明者声称其已知 ，满足：
范数条件
可重构并恢复：
并满足承诺方程：
约束条件：
上述论证保证，证明者知道 即已足够。如果这些向量的大小足够小，证明者可以直接将它们发送给验证者。这就是递归的基例。
另一方面，注意到上述约束都可以写成等式约束的形式。除最后一条外，所有约束均为线性约束，最后一条也仅是二次约束（重构操作是线性的，约束可直接用
重写）。此外，这些约束的见证 可证明其二范数较小（例如，利用维度为 的向量 有）。因此，可以将验证 Labrador 基础证明的问题重写为原始问题的一个实例，并对协议进行递归。
更详细地说，将基础证明 扁平化为多项式数组，再重塑为见证 ，其中每个
。参数 与 经精心选择，以在每次迭代中最大程度地减少证明大小（通常 ）。然后，将上述每条约束重写为关于 的等式约束并保存。注意，验证者可在无需证明者协助的情况下完成此重排。完成重排后，证明者和验证者即可再次执行一轮基础协议。
使用 ICICLE v4 实现
ICICLE v4 引入了对常见格原语的支持。我们使用这些原语构造了一个简单易读的 Labrador 协议的 C++ 实现（见此处），该实现与后端无关（可在 CPU 和 GPU 上运行）。
https://github.com/ingonyama-zk/icicle/releases/tag/v4.0.0 https://github.com/ingonyama-zk/icicle/pull/983
在我们的 Labrador 实现中，选择 ，其中 是 Koala bear 素数， 是 Baby bear素数。因此，我们称 为 Baby Koala 环。选择这些素数来定义 能够保证高效的算术运算和负循环 NTT。在代码中，该环用类型 Zq 表示。同样地，多项式环 用类型 Rq 表示，而在 NTT 域中表示的多项式环则用类型 Tq 表示。
下面来看一些在 C++ API 中用到的主要操作：
分解（Decomposition）：
以下代码演示了在 C++ 中如何分解向量 ：
// 计算以 base1 分解 Zq 元素所需的比特数
size_t l1 = balanced_decomposition::compute_nof_digits<Zq>(base1);
std::vector<Rq> T_tilde(l1 * r * kappa);
balanced_decomposition::decompose(
T.data(), // 输入数组
r * kappa, // 输入长度
base1, // 基数
{}, // 默认配置
T_tilde.data(), // 输出数组
T_tilde.size() // 输出长度
);
如果用户已知实际需要的输出长度小于 compute_nof_digits 返回的值，也可以将其作为输出长度传入。可使用同样 API 的balanced_decomposition::recompose 函数来验证重构是否正确。
以下代码演示了如何使用矩阵 计算分解后向量 的 Ajtai 承诺。在计算多项式矩阵乘积前，需先将 转入 NTT 域。假设矩阵 已以 NTT 形式存储：
// T_tilde_hat = NTT(T_tilde)
ntt(
T_tilde.data(), // 输入
T_tilde.size(), // 输入长度
NTTDir::kForward, // 正向 NTT
{}, // 默认配置
T_tilde_hat.data() // 输出
);
// 计算 u1 = T_tilde_hat @ B
matmul(
T_tilde_hat.data(), // A
1, // A 的行数
T_tilde_hat.size(), // A 的列数
B.data(), // B
T_tilde_hat.size(), // B 的行数
kappa1, // B 的列数
{}, // 默认配置
u1.data() // 输出
);
Labrador 协议中 JL 投影有两个用途。第一，给定随机种子，让证明者计算该种子生成的投影矩阵与向量的乘积：
// p = Pi * flatten(S)
labrador::jl_projection(
reinterpret_cast<const Zq*>(S.data()), // 输入扁平化见证
n * r * d, // 输入长度
jl_seed.data(), // 随机种子
jl_seed.size(), // 种子长度
{}, // 默认配置
p.data(), // 输出
JL_out // 输出长度
);
第二，需要提取 JL 矩阵的某些行（并可选地做共轭），ICICLE 提供了相应 API：
// 获取第 j 行并共轭
labrador::get_jl_matrix_rows(
jl_seed.data(), // 种子
jl_seed.size(), // 种子长度
r * n, // 行宽度
j, // 行索引
1, // 行数
true, // 是否共轭
{}, // 默认配置
Q_j.data() // 输出
);
ICICLE 还提供了检查 向量是否满足 2-范数或 ∞-范数上界的 API：
// JL_check = ||p|| < sqrt(JL_out/2) * beta
norm::check_norm_bound(
p.data(), // 输入向量
JL_out, // 向量长度
eNormType::L2, // 选择 L2 或 LInfinity
uint64_t(sqrt(JL_out/2) * beta), // 范数上界
{}, // 默认配置
&JL_check // 存放检查结果
);
最后，ICICLE 提供高效采样 Labrador 风格挑战空间多项式的 API：
sample_challenge_space_polynomials(
seed, // 种子
seed_len, // 种子长度
r, // 多项式数量
31, // ±1 系数个数
10, // ±2 系数个数
OP_NORM_BOUND, // 运算符范数上界
{}, // 默认配置
challenge.data() // 输出
);
为了提高效率，运算符范数检查与采样操作已合并。如果协议不需要运算符范数上界，只需将上述范数上界设置为 0。
欲了解 ICICLE 在 Rust 中的 API 概览，请参阅在线文档。
https://dev.ingonyama.com/api/rust-bindings/lattice/lattice-snarks
参考文献：
[^1]: Beullens, W., Seiler, G. (2023). LaBRADOR: Compact Proofs for R1CS from Module-SIS. In: Handschuh, H., Lysyanskaya, A. (eds) Advances in Cryptology – CRYPTO 2023. CRYPTO 2023. Lecture Notes in Computer Science, vol 14085. Springer, Cham. https://doi.org/10.1007/978-3-031-38554-4_17
[^2]: Ngoc Khanh Nguyen and Gregor Seiler. 2024. Greyhound: Fast Polynomial Commitments from Lattices. In Advances in Cryptology – CRYPTO 2024: 44th Annual International Cryptology Conference, Santa Barbara, CA, USA, August 18–22, 2024, Proceedings, Part X. Springer-Verlag, Berlin, Heidelberg, 243–275. https://doi.org/10.1007/978-3-031-68403-6_8
[^3]: Marius A. Aardal and Diego F. Aranha and Katharina Boudgoust and Sebastian Kolby and Akira Takahashi. Aggregating Falcon Signatures with LaBRADOR (2024)
https://eprint.iacr.org/2024/311