基于格的签名聚合

原文：https://ethresear.ch/t/lattice-based-signature-aggregation/22282

作者：David Nevado, Dohoon Kim, and Miha Stopar

译者：Kurt Pan

在以太坊的权益证明中，BLS 签名用于将多个验证者的证明聚合为单一紧凑的签名。然而，BLS 并不具有量子安全性，在后量子时代，它将需要被取代。一个有前途的方向是基于格的聚合，例如最近的《使用 LaBRADOR 聚合 Falcon 签名》这篇论文 ，它探索了如何高效地聚合后量子 Falcon 签名，同时保持小尺寸和快速验证。

• https://eprint.iacr.org/2024/311.pdf

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

• https://ethresear.ch/t/signature-merging-for-large-scale-consensus/17386

在本文最后，我们将 LaBRADOR 方法与最近的基于杂凑的签名聚合方法进行了比较。在那个方案中，签名用 Poseidon2 实例化，而聚合依赖 Keccak 来实现基于 Merkle 树的多项式承诺方案。聚合本身包括在 Plonk 风格的证明系统中对签名验证者进行的算术化。

LaBRADOR 是一个相对较新的协议，且实现支持仍然有限。虽然一些 Rust 实作正在出现，但它们尚未准备好，因此目前原始的 C 参考程式码仍是主要选择。为了进行基准测试，我们使用了 Lazer 库中的 agg_sig.py 脚本，该脚本封装了LaBRADOR 的 C 实作 。下面，我们先介绍一些基准结果，然后解释 Lazer 方法与原始论文《使用 LaBRADOR 聚合 Falcon 签名》中所描述的方法有何不同。

• https://github.com/lazer-crypto/lazer/blob/2fb8d336201445320e837b6b7805f5ac0f77c7c2/python/agg_sig.py
• https://github.com/lattice-dogs/labrador

性能结果

方法 ：

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

• https://github.com/privacy-scaling-explorations/labrador

结果 ：

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

重点 ：

10k Falcon-512 签名可以用 LaBRADOR 聚合，得到：

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

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

验证细目

Falcon 签名的聚合是使用 LaBRADOR 库中提供的打包证明和 Dachshund 前端（有关 Dachshund 的简要描述，请参阅Lazer 论文进行的。我们对Dachshund测试中的验证过程进行了分析，以确定瓶颈和潜在的最佳化机会。虽然我们尝试透过并行化来改善原始验证时间，但这些努力并没有成功。

• https://eprint.iacr.org/2024/1846.pdf

分析

打包证明的验证需要 1.2510 秒，发生在 composite_verify_simple 中，该过程包含两个步骤：

1. simple_reduce ：从简单语句 st 和证明 p 导出原始複合语句 tst （1.1356 秒，约佔总时间的 90%）。
2. Composite_verify ：根据 tst 验证 p （剩馀 10%）。

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

simple_reduce 分析

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

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

LIFTS 迴圈细分（每次迭代）

优化尝试

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

1. 菲亚特-沙米尔依赖关係 ：
   FS 挑战的推导不可避免地是串行的，这限制了并行化的机会。
2. 矩阵运算 ：
   使用 OpenMP 并行化 polxvec_jlproj_collapsmat （ simple_reduce 的 30%） 会导致效能下降 ，可能是因为：
• 错误共享 （快取行的执行线程争用）。
• 内存带宽饱和 （AVX-512 已达到最大带宽）。

然而，需要进一步分析来找出根本原因。

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

乍一看， 使用 LaBRADOR 聚合Falcon签名的技术似乎与 Lazer 的技术有很大不同，但事实并非如此。

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

Falcon 签名

Falcon 签名由  组成，使得：

其中  是公钥的一部分，  是讯息的杂凑值。

我们正在使用除  之外的其他模数的证明系统来证明  和  的知识，因此该等式被重写为：

对于某个多项式  。

Falcon 签名的聚合

我们希望聚合  个Falcon 签名，这意味着证明：

对于  ．

注意到 是 Falcon 方案中的模量，并且方程式需要在  中成立，其中  ，但具有相同的环的次数  。为了证明方程式在  上成立，方程式中不能出现迴绕的模 。

《使用 LaBRADOR 聚合 Falcon 签名》 这篇论文使用 LaBRADOR作为证明系统。在提交论文时，由于我们下面描述的问题，LaBRADOR 无法在没有一些额外限制的情况下使用。 LaBRADOR 原始码及其 Dachshund 前端是后来发布的，事实上，Dachshund 前端直接解决了最初阻碍 LaBRADOR 按原样使用的问题。

问题1：范数检查

使用 LaBRADOR 中的Johnson－Lindenstrauss投影进行的范数检查既是近似的，又应用于整个见证。这种方法现在在 LaBRADOR 原始码中被称为 Chihuahua 前端。相较之下，Dachshund 前端对每个见证向量单独执行范数检查。回想一下，在签名聚合的背景下，我们有多个见证向量： 和  。

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

Johnson－Lindenstrauss 投影的想法是使用随机投影矩阵  ：对于见证  ，计算投影 （矩阵向量乘法），然后验证者直接计算投影向量的范数。有一个引理粗略地指出，如果投影很小，那麽原始向量也很小 ：如果  对于某个边界  ，那麽  。对于安全等级  和某个常数  ，它也必须满足  。这对聚合方案中使用的模数  施加了限制－这是本文使用更大模量  而不是 Falcon 的原始模数  的原因之一。

然而，在签名聚合的情况下，有必要证明每个单独的见证向量（所有  和  ）都很小，这正是 Dachshund 的设计目的。由于 Dachshund 尚未面世，本文作者转而引入了额外的显式约束来强制实现各见证向量的范数界。本文仍然使用Johnson－Lindenstrauss投影，但目的不同：防止模数迴绕。下面我们总结了显式的范数约束和使用 Johnson－Lindenstrauss 投影来防止模迴绕。

单个见证向量范数约束

证明  等同于证明  非负。

拉格朗日四平方定理指出，任何非负整数都可以写成四个平方数的总和。因此，我们可以找到四个整数  使得：

第  个签名的值  被加到见证中作为多项式的係数

注意，有了多项式  ，，我们就可以计算它的范数（利用共轭自同构  和  的  这一事实  ：

我们表示  ．

现在我们可以将范数约束改写为 LaBRADOR 约束，如下：

但我们还需要检查新的见证元素是否已正确构建，以及见证元素的係数是否足够小，以至于它们不会迴绕  。

让我们来观察一下如何表示一个约束，即多项式  的第  个係数是某个值，比如说  ：

对于每个  ，我们需要准备约束以确保  为零。

我们还需要确保  是从  正确建构的，例如 ：

 和  同样如此。

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

防止迴绕

依照本文的方法，需要确保以下两个方程式不会出现迴绕：

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

从第二个方程式我们得到：

为了确保这一点，我们使用Johnson－Lindenstrauss投影。

问题二：重塑见证

在签名聚合方面，Chihuahua 前端的另一个限制是，由于需要计算大量所谓的垃圾多项式，因此在处理许多见证向量时效率低。

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

• 多重性  ：见证向量的数量
• 秩  ：每个见证向量中的多项式数量

论文建议重塑见证，以达到更平衡的配置，目标是  个秩为  的见证向量，其中  是签名的数量。

最初，见证由  个向量组成（当新增精确范数限制时更多），每个向量的秩为  。这是一个极不平衡的配置。为了让 LaBRADOR 的递归压缩更有效率， 和  的幅度最好更接近。

为了解决这个问题，该方案引入了一种填充策略：将见证重塑为  和  ，并根据需要用零填充新的见证向量。

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

环的选择

另一个方面是环的选择。虽然论文分析了几种选择，但最终採用了与 Lazer 相同的配置。将多项式与几个小质数  进行模乘（使用 NTT），然后使用显式 CRT 模  将结果组合起来。使用完全拆分为  的小的 16 位元素数 （介于  和  之间）可以实现高效的 Montgomery 算术（有关更多信息，请参阅 Greyhound 论文）。

• https://eprint.iacr.org/2024/1293.pdf

总结

两种签名聚合方法（来自论文 《使用 LaBRADOR 聚合 Falcon 签名》和 Lazer 的方法）非常相似，因此我们相信我们的基准（基于 Lazer 程式码）对两者都适用。

基准的基于格的签名聚合方案最引人注目的特点是其证明大小，而採用的最大障碍可能是验证时间。使用多线程技术可能会提高验证效能，但这需要进一步研究。话虽如此，LaBRADOR 作者已经在对 LaBRADOR 协议及其 C 实现进行改进，这些改进有望加快验证速度——儘管目前很难量化改进幅度。

虽然验证时间可能会随着未来的最佳化而改善，但它可能无法与基于杂凑的方法相比（见下表），其中验证仅需几毫秒。

• https://hackmd.io/@han/hash-sig-agg

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

• https://eprint.iacr.org/2020/1274.pdf

原文：https://ethresear.ch/t/lattice-based-signature-aggregation/22282

作者：David Nevado, Dohoon Kim, and Miha Stopar

译者：Kurt Pan

在以太坊的权益证明中，BLS 签名用于将多个验证者的证明聚合为单一紧凑的签名。然而，BLS 并不具有量子安全性，在后量子时代，它将需要被取代。一个有前途的方向是基于格的聚合，例如最近的《使用 LaBRADOR 聚合 Falcon 签名》这篇论文 ，它探索了如何高效地聚合后量子 Falcon 签名，同时保持小尺寸和快速验证。

• https://eprint.iacr.org/2024/311.pdf

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

• https://ethresear.ch/t/signature-merging-for-large-scale-consensus/17386

在本文最后，我们将 LaBRADOR 方法与最近的基于杂凑的签名聚合方法进行了比较。在那个方案中，签名用 Poseidon2 实例化，而聚合依赖 Keccak 来实现基于 Merkle 树的多项式承诺方案。聚合本身包括在 Plonk 风格的证明系统中对签名验证者进行的算术化。

LaBRADOR 是一个相对较新的协议，且实现支持仍然有限。虽然一些 Rust 实作正在出现，但它们尚未准备好，因此目前原始的 C 参考程式码仍是主要选择。为了进行基准测试，我们使用了 Lazer 库中的 agg_sig.py 脚本，该脚本封装了LaBRADOR 的 C 实作 。下面，我们先介绍一些基准结果，然后解释 Lazer 方法与原始论文《使用 LaBRADOR 聚合 Falcon 签名》中所描述的方法有何不同。

• https://github.com/lazer-crypto/lazer/blob/2fb8d336201445320e837b6b7805f5ac0f77c7c2/python/agg_sig.py
• https://github.com/lattice-dogs/labrador

性能结果

方法 ：

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

• https://github.com/privacy-scaling-explorations/labrador

结果 ：

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

![[Pasted image 20250518120559.png]]

重点 ：

10k Falcon-512 签名可以用 LaBRADOR 聚合，得到：

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

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

验证细目

Falcon 签名的聚合是使用 LaBRADOR 库中提供的打包证明和 Dachshund 前端（有关 Dachshund 的简要描述，请参阅Lazer 论文进行的。我们对Dachshund测试中的验证过程进行了分析，以确定瓶颈和潜在的最佳化机会。虽然我们尝试透过并行化来改善原始验证时间，但这些努力并没有成功。

• https://eprint.iacr.org/2024/1846.pdf

分析

打包证明的验证需要 1.2510 秒，发生在 composite_verify_simple 中，该过程包含两个步骤：

1. simple_reduce ：从简单语句 st 和证明 p 导出原始複合语句 tst （1.1356 秒，约佔总时间的 90%）。
2. Composite_verify ：根据 tst 验证 p （剩馀 10%）。

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

simple_reduce 分析

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

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

LIFTS 迴圈细分（每次迭代）

优化尝试

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

1. 菲亚特-沙米尔依赖关係 ：
   FS 挑战的推导不可避免地是串行的，这限制了并行化的机会。
2. 矩阵运算 ：
   使用 OpenMP 并行化 polxvec_jlproj_collapsmat （ simple_reduce 的 30%） 会导致效能下降 ，可能是因为：
• 错误共享 （快取行的执行线程争用）。
• 内存带宽饱和 （AVX-512 已达到最大带宽）。

然而，需要进一步分析来找出根本原因。

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

乍一看， 使用 LaBRADOR 聚合Falcon签名的技术似乎与 Lazer 的技术有很大不同，但事实并非如此。

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

Falcon 签名

Falcon 签名由  组成，使得：

其中  是公钥的一部分，  是讯息的杂凑值。

我们正在使用除  之外的其他模数的证明系统来证明  和  的知识，因此该等式被重写为：

对于某个多项式  。

Falcon 签名的聚合

我们希望聚合  个Falcon 签名，这意味着证明：

对于  ．

注意到 是 Falcon 方案中的模量，并且方程式需要在  中成立，其中  ，但具有相同的环的次数  。为了证明方程式在  上成立，方程式中不能出现迴绕的模 。

《使用 LaBRADOR 聚合 Falcon 签名》 这篇论文使用 LaBRADOR作为证明系统。在提交论文时，由于我们下面描述的问题，LaBRADOR 无法在没有一些额外限制的情况下使用。 LaBRADOR 原始码及其 Dachshund 前端是后来发布的，事实上，Dachshund 前端直接解决了最初阻碍 LaBRADOR 按原样使用的问题。

问题1：范数检查

使用 LaBRADOR 中的Johnson－Lindenstrauss投影进行的范数检查既是近似的，又应用于整个见证。这种方法现在在 LaBRADOR 原始码中被称为 Chihuahua 前端。相较之下，Dachshund 前端对每个见证向量单独执行范数检查。回想一下，在签名聚合的背景下，我们有多个见证向量： 和  。

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

Johnson－Lindenstrauss 投影的想法是使用随机投影矩阵  ：对于见证  ，计算投影 （矩阵向量乘法），然后验证者直接计算投影向量的范数。有一个引理粗略地指出，如果投影很小，那麽原始向量也很小 ：如果  对于某个边界  ，那麽  。对于安全等级  和某个常数  ，它也必须满足  。这对聚合方案中使用的模数  施加了限制－这是本文使用更大模量  而不是 Falcon 的原始模数  的原因之一。

然而，在签名聚合的情况下，有必要证明每个单独的见证向量（所有  和  ）都很小，这正是 Dachshund 的设计目的。由于 Dachshund 尚未面世，本文作者转而引入了额外的显式约束来强制实现各见证向量的范数界。本文仍然使用Johnson－Lindenstrauss投影，但目的不同：防止模数迴绕。下面我们总结了显式的范数约束和使用 Johnson－Lindenstrauss 投影来防止模迴绕。

单个见证向量范数约束

证明  等同于证明  非负。

拉格朗日四平方定理指出，任何非负整数都可以写成四个平方数的总和。因此，我们可以找到四个整数  使得：

第  个签名的值  被加到见证中作为多项式的係数

注意，有了多项式  ，，我们就可以计算它的范数（利用共轭自同构  和  的  这一事实  ：

我们表示  ．

现在我们可以将范数约束改写为 LaBRADOR 约束，如下：

但我们还需要检查新的见证元素是否已正确构建，以及见证元素的係数是否足够小，以至于它们不会迴绕  。

让我们来观察一下如何表示一个约束，即多项式  的第  个係数是某个值，比如说  ：

对于每个  ，我们需要准备约束以确保  为零。

我们还需要确保  是从  正确建构的，例如 ：

 和  同样如此。

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

防止迴绕

依照本文的方法，需要确保以下两个方程式不会出现迴绕：

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

从第二个方程式我们得到：

为了确保这一点，我们使用Johnson－Lindenstrauss投影。

问题二：重塑见证

在签名聚合方面，Chihuahua 前端的另一个限制是，由于需要计算大量所谓的垃圾多项式，因此在处理许多见证向量时效率低。

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

• 多重性  ：见证向量的数量
• 秩  ：每个见证向量中的多项式数量

论文建议重塑见证，以达到更平衡的配置，目标是  个秩为  的见证向量，其中  是签名的数量。

最初，见证由  个向量组成（当新增精确范数限制时更多），每个向量的秩为  。这是一个极不平衡的配置。为了让 LaBRADOR 的递归压缩更有效率， 和  的幅度最好更接近。

为了解决这个问题，该方案引入了一种填充策略：将见证重塑为  和  ，并根据需要用零填充新的见证向量。

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

环的选择

另一个方面是环的选择。虽然论文分析了几种选择，但最终採用了与 Lazer 相同的配置。将多项式与几个小质数  进行模乘（使用 NTT），然后使用显式 CRT 模  将结果组合起来。使用完全拆分为  的小的 16 位元素数 （介于  和  之间）可以实现高效的 Montgomery 算术（有关更多信息，请参阅 Greyhound 论文）。

• https://eprint.iacr.org/2024/1293.pdf

总结

两种签名聚合方法（来自论文 《使用 LaBRADOR 聚合 Falcon 签名》和 Lazer 的方法）非常相似，因此我们相信我们的基准（基于 Lazer 程式码）对两者都适用。

基准的基于格的签名聚合方案最引人注目的特点是其证明大小，而採用的最大障碍可能是验证时间。使用多线程技术可能会提高验证效能，但这需要进一步研究。话虽如此，LaBRADOR 作者已经在对 LaBRADOR 协议及其 C 实现进行改进，这些改进有望加快验证速度——儘管目前很难量化改进幅度。

虽然验证时间可能会随着未来的最佳化而改善，但它可能无法与基于杂凑的方法相比（见下表），其中验证仅需几毫秒。

• https://hackmd.io/@han/hash-sig-agg

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

• https://eprint.iacr.org/2020/1274.pdf