基于格的签名聚合 - 密码学

基于格的签名聚合

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

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

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

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

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

性能结果

方法：

我们使用了我们的 LaBRADOR 的 fork，其中包括修改以支持更大的签名批次（超过 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 聚合 10k 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} 之间）的使用使得可以进行有效的蒙哥马利算术（有关更多信息，请参见 Greyhound 论文）。

总结

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

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

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

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

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