基于格的签名聚合

基于格的签名聚合

这是 David Nevado、Dohoon Kim 和 Miha Stopar 的联合报告。

在以太坊的权益证明中，BLS 签名用于将多个验证者的证明聚合为单个紧凑的签名。然而，BLS 不具备抗量子性，在后量子时代，它需要被替换。一个很有希望的方向是基于格的聚合，例如最近的 使用 LaBRADOR 聚合 Falcon 签名，它探讨了如何在保持小尺寸和快速验证的同时，有效地聚合后量子 Falcon 签名。

虽然 LaBRADOR 提供了一种很有前景的方法来聚合具有紧凑证明的 Falcon 签名（对于 10,000 个签名约为 74 KB），但也存在其他后量子替代方案。一种是使用 STARK 以零知识证明许多基于哈希的签名是有效的。这些方法通常会导致更大的证明大小——对于 1 万个签名约为 300KB——但受益于更快的验证时间。

在本报告的结尾，我们将 LaBRADOR 方法与最近的一种基于哈希的签名聚合方法进行比较。在该方案中，签名使用 Poseidon2 进行实例化，而聚合依赖于 Keccak 进行基于 Merkle 树的多项式承诺方案。聚合本身包括在 Plonk 风格的证明系统中对签名验证器进行算术化。

LaBRADOR 是一种相对较新的协议，实现支持仍然有限。虽然一些 Rust 实现正在出现，但它们尚未准备好，目前只能使用原始 C 参考代码。对于基准测试，我们使用了 Lazer 存储库中的 agg_sig.py 脚本，该脚本包装了 LaBRADOR C 实现。下面，我们首先展示一些基准测试结果，然后解释 Lazer 的方法与原始论文《使用 LaBRADOR 聚合 Falcon 签名》中描述的方法有何不同。

性能结果

方法：

我们使用了我们的 LaBRADOR 分支，其中包括支持更大签名批次（超过 2,000 个签名）的修改。进行这些修改是为了能够将模数增加到大约 2^{48}，以处理聚合过程中产生的更大的中间值。

结果：

我们测量了 3,000 到 10,000 个 Falcon-512 签名批次的聚合证明时间。基准测试是在 11th Gen Intel(R) Core(TM) i5-11400H @ 2.70GHz 处理器上使用单线程执行获得的。

\ upload_4dcc9d5e61dff3c5e795face79d4a0c21007×1094 78.2 KB

注意：虽然图中未显示，但此配置支持更大的签名批次。较小的批次（<2,000 个签名）可实现更好的性能，因为模数可以减小到 2^{40}，从而缩短证明/验证时间和证明大小。

主要结论：

可以使用 LaBRADOR 聚合 1 万个 Falcon-512 签名，从而产生：

• 74.07KB 证明大小。
• 5.95s 证明生成。
• 2.65s 证明验证。

从这些结果来看，验证时间是采用的最大障碍。我们分析了验证以提高其性能。

验证细分

Falcon 签名的聚合是使用打包证明和 Dachshund 前端（有关 Dachshund 的简要描述，请参见 Lazer 论文）进行的，该前端在 LaBRADOR 库中提供。我们在 Dachshund 测试中分析了验证过程，以识别瓶颈和潜在的优化机会。虽然我们试图通过并行化来提高原始验证时间，但这些努力并未成功。

分析

打包证明的验证需要 1.2510 秒，并且发生在 composite_verify_simple 中，它由两个步骤组成：

1. simple_reduce：从简单语句 st 和证明 p 导出原始复合语句 tst（1.1356s，约占总时间的 90%）。
2. composite_verify：验证 p 是否符合 tst（剩余 10%）。

鉴于其主导地位，我们专注于优化 simple_reduce。

simple_reduce 分析

使用 48 位模数，常量 LIFTS = 3。LIFTS 循环消耗了 77% 的运行时，但其顺序依赖性（由于 Fiat-Shamir 挑战）阻止了并行化。

在循环中，我们发现几个可以优化的函数。特别是 collaps_jlproj_raw()。

LIFTS 循环细分（每次迭代）

优化尝试

LaBRADOR 经过 AVX-512 指令的大量优化，但仍然是单线程的。我们探索了并行化，但遇到了挑战：

1. Fiat-Shamir 依赖性：

FS 挑战的推导不可避免地是顺序的，这限制了并行化的机会。

2. 矩阵运算：

使用 OpenMP 并行化 polxvec_jlproj_collapsmat（占 simple_reduce 的 30%）降低了性能，可能是因为：

• 伪共享（线程对缓存行的争用）。
• 内存带宽饱和（AVX-512 已经达到最大带宽）。

但是，需要进一步分析以找出根本原因。

比较：Lazer 和使用 LaBRADOR 聚合 Falcon 签名

乍一看，使用 LaBRADOR 聚合 Falcon 签名 中的技术可能与 Lazer 的技术截然不同，但事实并非如此。

让我们首先观察 Falcon 签名的聚合是如何工作的，然后深入研究这两种方法之间的差异。

Falcon 签名

Falcon 签名由 (s_1, s_2) 组成，使得：

\mathbf{s}_1 + \mathbf{h} \mathbf{s}_2 = \mathbf{t} \mod q

其中 \mathbf{h} 是公钥的一部分，\mathbf{t} 是消息的哈希。

我们正在使用某种模数不同于 q 的证明系统来证明 \mathbf{s}_1 和 \mathbf{s}_2 的知识，因此该等式被重写为：

\mathbf{s}_1 + \mathbf{h} \mathbf{s}_2 + q \mathbf{v} = \mathbf{t}

对于某个多项式 \mathbf{v}。

Falcon 签名的聚合

我们想要聚合 N 个 Falcon 签名，这意味着证明：

\mathbf{s}_{i,1} + \mathbf{h}_i \mathbf{s}_{i,2} + q \mathbf{v}_i = \mathbf{t}_i

对于 i = 1,...,N。

请注意，q 是 Falcon 方案中的模数，并且该等式需要在 R_{q'} 中成立，其中 q' > q，但环的度数 d 相同。为了证明该等式在 R 上成立，等式中不得出现环绕模 q' 的情况。

论文 使用 LaBRADOR 聚合 Falcon 签名 使用 LaBRADOR 作为证明系统。在论文提交时，LaBRADOR 无法在没有一些额外约束的情况下使用，原因是我们下面描述的问题。LaBRADOR 源代码（及其 Dachshund 前端）稍后发布，事实上，Dachshund 前端直接解决了最初阻止 LaBRADOR 按原样使用的问题。

问题 1：范数检查

LaBRADOR 中使用 Johnson–Lindenstrauss 投影的范数检查既是近似的，又一次性地应用于整个 witness。在 LaBRADOR 源代码中，此方法现在称为 Chihuahua 前端。相比之下，Dachshund 前端对每个 witness 向量单独执行范数检查。回想一下，在上面的签名聚合的上下文中，我们有多个 witness 向量：\mathbf{s}_{i,1} 和 \mathbf{s}_{i,2}。

由于 Dachshund 尚未发布，因此该论文是在假设使用 Chihuahua 前端的情况下编写的。此前端证明整个 witness（即所有 witness 向量的组合）的范数很小——这种方法适用于某些应用程序。

Johnson–Lindenstrauss 投影的思想是使用随机投影矩阵 \Pi：对于 witness \mathbf{s}，计算投影 \Pi \mathbf{s}（矩阵向量乘法），并且验证者直接计算投影向量的范数。有一个引理大致指出，如果投影很小，那么原始向量也很小：如果 |\Pi \mathbf{s}|_2 \leq \sqrt{30} b 对于某个边界 b，则 |\mathbf{s}|_2 \leq b。还必须满足 \sqrt{\lambda} b \leq \frac{q}{C_1} 对于某个安全级别 \lambda 和某个常数 C_1。这限制了聚合方案中使用的模数 q——这是该论文使用更大的模数 q' > q 而不是 Falcon 的原始模数 q 的原因之一。

然而，在签名聚合的情况下，有必要证明每个单独的 witness 向量（所有 \mathbf{s}_{i,1} 和 \mathbf{s}_{i,2}）的范数很小，这正是 Dachshund 旨在支持的。由于 Dachshund 尚未可用，因此该论文的作者引入了额外的显式约束来强制执行对单个 witness 向量的范数限制。Johnson–Lindenstrauss 投影仍然在该论文中使用，但用于不同的目的：防止模环绕。我们在下面总结了显式范数约束和使用 Johnson–Lindenstrauss 投影来防止模环绕的内容。

单个 witness 向量范数约束

证明 ||\mathbf{s}_{i,1}||^2_2 + ||\mathbf{s}_{i,2}||^2_2 \leq \beta^2 等效于证明 \beta^2 - ||\mathbf{s}_{i,1}||^2_2 - ||\mathbf{s}_{i,2}||^2_2 非负。

拉格朗日的四平方和定理指出，任何非负整数都可以写成四个平方和。因此，我们可以找到四个整数 \epsilon_{i,0}, \epsilon_{i,1}, \epsilon_{i,2}, \epsilon_{i,3} \in \mathbb{Z}，使得：

\beta^2 - ||\mathbf{s}_{i,1}||^2_2 - ||\mathbf{s}_{i,2}||^2_2 = \epsilon_{i,0}^2 + \epsilon_{i,1}^2 + \epsilon_{i,2}^2 + \epsilon_{i,3}^2

第 i 个签名的值 \epsilon_{i,j} 作为多项式的系数添加到 witness 中

\epsilon_i = \epsilon_{i,0} + \epsilon_{i,1} X + \epsilon_{i,2} X^2 + \epsilon_{i,3}X^3 \in R_{q'}

请注意，如果有一个多项式 \mathbf{a} = a_0 + a_1 X + ... + a_{d-1} X^{d-1}，我们可以将其范数计算为（使用 ||\mathbf{a}||^2 = ct(\langle \mathbf{a}, \sigma_{-1}(\mathbf{a}) \rangle) 这一事实，对于共轭自同构 \sigma_{-1} 且 X^d = -1）：

cnst((a_0 + a_1 X + ... + a_{d-1} X^{d-1})(a_0 - a_{d-1} X - ... - a_1 X^{d-1}))

我们表示 \mathbf{a}' = a_0 - a_{d-1} X - ... - a_1 X^{d-1}。

现在我们可以将范数约束重写为 LaBRADOR 约束：

cnst(\epsilon_i \epsilon'_i + \mathbf{s}_{i,1} \mathbf{s}'_{i,1} + \mathbf{s}_{i,2} \mathbf{s}'_{i,2} - \beta^2) = 0 \; mod \; q'

但是我们还需要检查新的 witness 元素是否已正确构建，并且 witness 元素的系数是否足够小，以至于它们不会环绕 q'。

让我们观察如何表达多项式 \mathbf{a} 的第 j 个系数是某个值的约束，假设为 b：

cnst(X^{-j} \mathbf{a}) = cnst(a_0 X^{-j} + ...+ a_{j-1} X^{-1} + a_j + a_{j+1} X + ... + a_{d-1}X^{d-j-1}) = b

对于每个 \epsilon_i，我们需要准备约束，以确保 \epsilon_{i,4},..., \epsilon_{i, d-1} 为零。

我们还需要确保 \mathbf{s}'_{i,1} 是从 \mathbf{s}_{i,1} 正确构建的，例如：

const(X^{-1} \mathbf{s}'_{i,1}) = -const(X^{-(d-1)} \mathbf{s}_{i,1})

对于 \mathbf{s}_{i,2} 和 \epsilon_i 也是如此。

与基于四平方和的方法相反，Dachshund 使用以 2 为底分解的向量，这些向量与具有布尔系数的多项式相乘。性能上可能没有显着差异。

防止环绕

按照论文中的方法，有必要确保在以下两个等式中不会发生环绕：

cnst(\epsilon_i \epsilon'_i + \mathbf{s}_{i,1} \mathbf{s}'_{i,1} + \mathbf{s}_{i,2} \mathbf{s}'_{i,2} - \beta^2) = 0 \; mod \; q'

\mathbf{s}_{i,1} + \mathbf{h}_i \mathbf{s}_{i,2} + q \mathbf{v}_i = \mathbf{t}_i

事实证明，第一个更具限制性，我们得到：

||(\mathbf{s}_{i,1} | \mathbf{s}_{i,2} | \mathbf{s}'_{i,1} | \mathbf{s}'_{i,2} | \mathbf{\epsilon}_i | \mathbf{\epsilon}'_i )||_{\infty} < \sqrt{\frac{q'}{2(2d+4)}}

从第二个等式，我们得到：

||\mathbf{v}_1 | ... | \mathbf{v}_N||_{\infty} < \frac{q'}{6q}

为了确保这一点成立，使用了 Johnson–Lindenstrauss 投影。

问题 2：重塑 witness

在签名聚合的上下文中，Chihuahua 前端的另一个限制是它在处理许多 witness 向量时的效率低下，因为需要计算许多所谓的垃圾多项式。

证明者的运行时——以及 LaBRADOR 多快收敛到基本情况（即压缩证明大小需要多少个递归步骤）——取决于两个关键参数：

• 重数 r：witness 向量的数量
• 秩 n：每个 witness 向量中的多项式数量

该论文建议重塑 witness 以实现更平衡的配置，目标是 r = O(\sqrt{N}) 个秩为 n = N 的 witness 向量，其中 N 是签名数。

最初，witness 由 r = 2N 个向量组成（当添加精确范数约束时，甚至更多），每个向量的秩为 n = 1。这是一种高度不平衡的配置。为了使 LaBRADOR 的递归压缩有效，最好让 r 和 n 的大小更接近。为了解决这个问题，该方案引入了一种填充策略：重塑 witness，使得 n \approx N 且 r \approx \sqrt{N}，并根据需要用零填充新的 witness 向量。

然而，Dachshund 前端也解决了这个问题——Dachshund 旨在有效地处理大量 witness 向量。

环的选择

另一个方面是对环的选择。虽然该论文分析了几个选项，但最终采用了与 Lazer 相同的配置。多项式以几个小素数 p_i 为模相乘（使用 NTT），然后使用显式 CRT 以 q 为模组合结果。在 \mathbb{Z}_r[X]/(X^{64} + 1) 中完全分裂的小的 16 位素数 p_i（介于 2^{12} 和 2^{14} 之间）可以实现高效的 Montgomery 算术（有关更多信息，请参见 Greyhound 论文）。

总结

签名聚合的两种方法——论文 使用 LaBRADOR 聚合 Falcon 签名 中的方法和 Lazer 方法——非常相似，因此我们相信我们的基准测试（基于 Lazer 代码）对两者都适用。

经过基准测试的基于格的签名聚合方案最引人注目的特点是其证明大小，而采用的最大障碍可能是验证时间。通过使用多线程技术，验证性能可能会得到提高，但这需要进一步研究。也就是说，LaBRADOR 协议及其 C 实现的改进已经在 LaBRADOR 作者的进行中，预计这些改进将加速验证——尽管目前很难量化加速多少。

虽然验证时间可能会随着未来的优化而提高，但它可能无法与 基于哈希的方法 相提并论（见下表），在基于哈希的方法中，验证仅需几毫秒。

总而言之，LaBRADOR 方案似乎非常适合 Falcon 签名聚合中出现的特定约束。为了缩短验证时间，探索类似于 Dory 的委托技术可能是一个很有希望的方向。

• 以太坊的 WHIR

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